% LaTeX Article Template - using color
%\documentclass{article}
% Load the "color" package
%\usepackage{color}

% Switch the text to the given color
%\color{blue} This is switched to blue.  \color{black}  This is switched back to black.

% Set the text in a box with the given color as background
%\colorbox{yellow}{This is in a yellow box.}
% LaTeX Article Template - customizing header and footer
% Set left margin - The default is 1 inch, so the following 
% command sets a 1.25-inch left margin.
%\setlength{\oddsidemargin}{0.25in}

% Set width of the text - What is left will be the right margin.
% In this case, right margin is 8.5in - 1.25in - 6in = 1.25in.
%\setlength{\textwidth}{6in}

% Set top margin - The default is 1 inch, so the following 
% command sets a 0.75-inch top margin.
%\setlength{\topmargin}{-0.25in}

% Set height of the header
%\setlength{\headheight}{0.3in}

% Set vertical distance between the header and the text
%\setlength{\headsep}{0.2in}

% Set height of the text
%\setlength{\textheight}{9in}

% Set vertical distance between the text and the
% bottom of footer
%\setlength{\footskip}{0.1in}

% Redefine "plain" pagestyle
% LaTeX Article Template - customizing page format
%
% LaTeX document uses 10-point fonts by default.  To use
% 11-point or 12-point fonts, use \documentclass[11pt]{article}
% or \documentclass[12pt]{article}.
%\documentclass{article}

% Set left margin - The default is 1 inch, so the following 
% command sets a 1.25-inch left margin.
%\setlength{\oddsidemargin}{0.25in}

% Set width of the text - What is left will be the right margin.
% In this case, right margin is 8.5in - 1.25in - 6in = 1.25in.
%\setlength{\textwidth}{6in}

% Set top margin - The default is 1 inch, so the following 
% command sets a 0.75-inch top margin.
%\setlength{\topmargin}{-0.25in}

% Set height of the text - What is left will be the bottom margin.
% In this case, bottom margin is 11in - 0.75in - 9.5in = 0.75in
%\setlength{\textheight}{8in}
% Set the beginning of a LaTeX document
% LaTeX Article Template - using color
% Load the "color" package
%\usepackage{color}
%
% Set the text in the given color.
%\textcolor{red}{This is in red.}
% 
% Switch the text to the given color
%\color{blue} This is switched to blue.  \color{black}  This is switched back to black.

% Set the text in a box with the given color as background
%\colorbox{yellow}{This is in a yellow box.}

%\usepackage{color}


\documentclass{article}
\usepackage{graphicx} 
\input html.sty
%\usepackage{color}

\begin{document}

\section{Markov Chains}

Suppose in small town there are three places to eat, two restaurants one  Chinese and another one is  Mexican restaurant.
  The third place is a pizza place.  Everyone in  town   eats dinner in one of these places or has dinner at home.

Assume that 20\% of those who eat in Chinese restaurant go to Mexican next time, 20\% eat at home, and 30\% go to pizza place.
From those who eat in Mexican restaurant, 10\% go to pizza place, 25\% go to Chinese restaurant, and 25\% eats at home next time.
From those who eat at pizza place 30% go to Chinese, 29\% go to Mexican and 30% eat at home.
Those who eat at home 20\% go to Chinese, 25\% go to Mexican place, and 30\% to pizza place.
We call this situation a {\bf system}.  A person in the town can eat  dinner in one of these four places, each of them called a {\bf state}.  In our example, the system has four states. We are interested in success of these places in terms of their business. For example after a given period of time,  what percentage of people in town will go to pizza place?


Suppose there is a physical or mathematical system that has $k$  possible states and at any one time, the system is in one and only one of its $k$ states. 
And suppose that at a given observation period, say $n^{th}$ period, the probability of the system being in a particular state depends on its status at the n-1 period, such a system is called {\bf Markov Chain} or {\bf Markov process}.

In the example above there are four states for the system.  Define $a_{ij}$ to  be the probability of the system to be in state $ i$  after it was in state j ( at any observation ).  The matrix $A = (a_{ij}$) is called the {\bf Transition matrix of the Markov Chain}.

So transition matrix for example above, is 

$A= \left[ \begin{array}{rrrr}  
		.25&.20&.25&.30\\
		.20&.30&.25&.30\\
		.25&.20&.40&.10\\
		.30&.30&.10&.30\\
	\end{array}  
\right]$\\




The first column represents  state of eating at home,
the second column represents   state of  eating at the Chinese restaurant,
the third column represents state of eating at the Mexican restaurant,
and the fourth column represents state of eating at the Pizza Place.
\vspace{.2cm}

Similarly the  rows respectively  represent  eating at home, eating at the Chinese restaurant, eating at the Mexican restaurant and  eating at the Pizza Place.  
\vspace{.2cm}

\vspace{ .5cm}

$$ \begin{array}{rrrrrr}  
 \mbox{H}\ & \mbox{C}\ &\mbox{M}\  &\mbox{P}\  \\
\end{array}$$
$$A =\left[ \begin{array}{rrrrr}  
		.25&.20&.25&.30  \\
		.20&.30&.25&.30 \\
		.25&.20&.40&.10 \\
		.30&.30&.10&.30 \\
	\end{array}  
\right]
\begin{array}{r}  
 \mbox{H}\\
\mbox{C}\\
\mbox{M}\\
\mbox{P}\\
\end{array}
$$ 
\vspace{ .5cm}



Note that the sum of each column in this matrix is one.  Any matrix with this property is called a stochastic matrix probability matrix or a Markov matrix. We are interested in the following question:
\vspace{0.3cm}

What is the probability that the system is in the $i^{th}$ state, at the $n^{th}$ observation?
\vspace{0.3cm}

To answer this question, we first define the {\bf state vector}. For a Markov Chain, which has k states, the {\bf state vector} for an observation period $n$,  is a column vector defined by 

\vspace{ .5cm}


$$x^{(n)} = \left[ \begin{array}{c}  
		x_1\\
		x_2\\
	\vdots\\
		x_k\\		
	\end{array}  
\right]$$
\vspace{ .5cm}


where,  $x_i$ = probability that the system is in the $i^{th}$ state at the time of observation. 
 Note that the sum of the entries of the state vector has to be  one. 
Any column vector $x$, 
\vspace{ .5cm}


$$x  = \left[ \begin{array}{c}  
		x_1\\
		x_2\\
	\vdots\\
		x_k\\		
	\end{array}  
\right]$$
\vspace{ .5cm}


where  $x_1 + x_2 + \dots  + x_k = 1$ is called a {\bf probability vector.}  Consider our example, suppose at the beginning, every one eats at home, that is the initial state vector $x^{(0) }$ is 
\vspace{ .5cm}


$$x^{(0)} = \left[ \begin{array}{r}  
		1\\
		0\\
		0\\
		0\\		
	\end{array}  
\right]$$. 
In the next observation period, say end of the first week, the state vector will be 
$$x^{(1)} = A x^{(0)} = \left[ \begin{array}{r}  
		.25\\
		.20\\
		.25\\
		.30\\		
	\end{array}  
\right]$$.\\
\vspace{ .5cm}


At the end of $2^{nd}$ week the state vector is 
\vspace{ .5cm}


$x^{(2)} = Ax^{(1)} = \left[ \begin{array}{rrrr}  
		.25&.20&.25&.30\\
		.20&.30&.25&.30\\
		.25&.20&.40&.10\\
		.30&.30&.10&.30\\
	\end{array}  
\right] \left[ \begin{array}{r}  
		.25\\
		.20\\
		.25\\
		.30\\		
	\end{array}  
\right] = \left[ \begin{array}{r}  
		.2550\\
		.2625\\
		.2325\\
		.2500\\		
	\end{array}  
\right]$\\
\vspace{ .5cm}

Note that we can compute $x^{(2)}$ directly using $x^{(0)}$ as
\vspace{ .5cm}


$$x^{(2)} = Ax^{(1)} = A(Ax^{(0)}) = A^2 x^{(0)}.$$
\vspace{ .5cm}

Similarly, we can find the state vector for $5^{th}, 10^{th} and 20^{th}$ observation periods.
\vspace{ .5cm}


$$x^{(5)} = A^5 x^{(0)} = \left[ \begin{array}{r}  
		.2495\\
		.2634\\
		.2339\\
		.2532\\		
	\end{array}  
\right]$$
\vspace{ .5cm}


$$x^{(10)} = A^10 x^{(0)} = \left[ \begin{array}{r}  
		.2495\\
		.2634\\
		.2339\\
		.2532\\		
	\end{array}  
\right]$$
\vspace{ .5cm}


$$x^{(20)} = A^20 x^{(0)} = \left[ \begin{array}{r}  
		.2495\\
		.2634\\
		.2339\\
		.2532\\		
	\end{array}  
\right]$$
\vspace{ .5cm}


Computing $$x^{(30)} = \left[ \begin{array}{r}  
		.2495\\
		.2634\\
		.2339\\
		.2532\\		
	\end{array}  
\right], x^{(50)} = \left[ \begin{array}{r}  
		.2495\\
		.2634\\
		.2339\\
		.2532\\		
	\end{array}  
\right]$$, 

\vspace{ .5cm}

suggest  that the state vector approached  to some fixed vector, as the number of observation periods increase.  This is not the case for every Markov Chain.  For example if
\vspace{ .5cm}


$$A = \left[ \begin{array}{rr}  
		0&1\\
		1&0\\
	\end{array}  
\right]$$, and $$x^{(0)} = \left[ \begin{array}{r}  
		1\\
		0\\
	\end{array}  
\right]$$,\\
\vspace{ .5cm}

we can compute  the  state vectors for different observation periods:
\vspace{ .5cm}


$$x^{(1)} = \left[ \begin{array}{r}  
		0\\
		1\\
	\end{array}  
\right], x^{(2)} = \left[ \begin{array}{r}  
		1\\
		0\\
	\end{array}  
\right], x^{(3)} = \left[ \begin{array}{r}  
		0\\
		1\\
	\end{array}  
\right], x^{(4)} = \left[ \begin{array}{r}  
		1\\
		0\\
	\end{array}  
\right], \dots, x^{(2n)} = \left[ \begin{array}{r}  
		1\\
		0\\
	\end{array}  
\right], \mbox{and}  x^{(2n + 1)} = \left[ \begin{array}{r}  
		0\\
		1\\
	\end{array}  
\right]$$ 

\vspace{ .5cm}

These computations  indicates that this system oscillates and does not approach any fixed vector.


 \section{Regular Markov Chain }

An square matrix $A$ is called { \bf regular  } if for some integer $n$ all entries of $ A^n $ are positive.

{\bf Example}

 The matrix $$A = \left[ \begin{array}{rr}  
		0&1\\
		1&0\\
	\end{array}  
\right]$$  is not a regular matrix, because for all positive integer $n$,  

$$A^{2n}  = \left[ \begin{array}{rr}  
		1&0\\
		0&1\\
	\end{array}  
\right]\hspace{ 2cm}
\mbox {and }
\hspace{ 2cm}
 A^{2n+1}  = \left[ \begin{array}{rr}  
		0&1\\
		1&0\\
	\end{array}  
\right]$$

 
The matrix  $A =\left[ \begin{array}{rrrrr}  
		.25&.20&.25&.30  \\
		.20&.30&.25&.30 \\
		.25&.20&.40&.10 \\
		.30&.30&.10&.30 \\
	\end{array}  \right[
$ 

is a regular matrix, because $A^1 $ has all positive entries.


It can also be shown that all other eigenvalues of A are less than 1, and algebraic multiplicity of 1 is one.


It can be shown that if $A$ is a regular matrix then $ A^n $ approaches to a matrix $ Q $   whose columns are all equal to a probability vector $ q $ which is called the { \bf steady-state }  vector of the regular Markov chain.

 \vspace{ .5cm}

$$ \mbox{ if } A \mbox{  regular, then  } A^n \rightarrow Q = \left[ \begin{array}{rrrrrr}  
		q_1&q_1&.&.&.&q_1\\
		q_2&q_2&.&.&.&q_2\\
		.&.&&&&.\\
		.&.&&&&.\\
		.&.&&&&.\\
		q_k&q_k&.&.&.&q_k\\		
	\end{array}  
\right]$$ 
\vspace{ .5cm}


where  $q_{1} + q_{2} + \dots + q_{k} = 1$.

  It can be shown  that for any probability vector $x^{(0)}$  when
$n$  gets large, $A^n x^{(0)}$ approaches to the  { \bf steady-state } vector 
\vspace{ .5cm}

$${\bf  q } =  \left[ \begin{array}{r}  
		q_1\\
		q_2\\
		\vdots	\\
	q_k\\		
	\end{array}  
\right]$$.

\vspace{ .5cm}


That is
\vspace{ .5cm}


$$A^n x^{(0)} \longrightarrow  q=\left[ \begin{array}{r}  
		q_1\\
		q_2\\
		.\\
		.\\
		.\\
		q_k\\		
	\end{array}  
\right]$$ 
\vspace{ .5cm}

where  $q_{1} + q_{2} + \dots + q_{k} = 1$.


It can also be shown that the steady-state vector q is the only vector such that

$$Aq = q$$

Note that this shows q is an eigenvector of A and $ 1$ is  eigenvalue of A.\\



\subsection{Exercises}







\subsubsection{Exercise 1}

 Which of the following matrices are stochastic 
matrices?

a) $\left[ \begin{array}{rr}  
		.25&.75\\
		.75&.15\\
	\end{array}  
\right]$

b) $\left[ \begin{array}{rr}  
		2/7&2/5\\
		4/7&3/5\\
	\end{array}  
\right]$

c) $\left[ \begin{array}{rr}  
		.5&.85\\
		.5&.15\\
	\end{array}  
\right]$

d) $\left[ \begin{array}{rr}  
		0&1\\
		1&0\\
	\end{array}  
\right]$

\subsubsection{Solution to Exercise 1}

a) It is not a stochastic matrix. The second column does not add up to 1.\\
b) It is not a stochastic matrix. The first column does not add up to 1.\\
c) It is  a stochastic matrix. 
d) It is  a stochastic matrix. 


\subsubsection{Exercise 2}

 Suppose that  income from occupation of a child, as an adult, depends  upon the  income from the 
 occupation of his or her parents given by the following transition matrix, where \\
L= low income, M= middle income, U= High income


$$ \begin{array}{r}  
 \mbox{Parents income }  \\
\end{array}$$
$$\begin{array}{rrrrr}  
 \mbox{L}\ & \mbox{M}\ &\mbox{H}\    \\
\end{array}$$
$$ 
\begin{array}{r}  
 \mbox{ Chiled's}\\
\mbox{income}\\
\mbox{as an }\\
\mbox{adult }\\
\end{array}
\left[ \begin{array}{rrr}  
		0.5&0.2&0.1  \\
		0.3 &0.6&0.4 \\
		0.2&0.2&0.5 \\
	\end{array}  
\right]
\begin{array}{r}  
 \mbox{L}\\
\mbox{M}\\
\mbox{H}\\
\end{array}
$$ 






a) What is the probability that the grandchild of a family of low income to be in high income level?\\
b) In long run, what portion of the population will be in low income level?

\subsubsection{Solution to Exercise 2}

a)  The transition matrix  is $A = \left[ \begin{array}{rrr}  
		0.5&0.2&0.1  \\
		0.3 &0.6&0.4 \\
		0.2&0.2&0.5 \\
	\end{array}  
\right]
$

 Let $x^{(0)}  = 
\begin{array}{r}  
1\\
0\\
0\\
\end{array} $, then $ x^{(1) } =A x^{(0)} = 
\begin{array}{r}  
0.5\\
0.3\\
0.2\\
\end{array}$ 

And  $ x^{(2) } =A x^{(3)}=
\begin{array}{r}  
 0.3300\\
    0.4100\\
    0.2600\\
\end{array}$ 


Hence the probability that the grandchild of a family of low income to be in high income level is 0.26 .


b)  Since $A$ is a regular matrix, we need to find $A^n $ for large $n$. Here is some powers of $A$ computed by using MATLAB:

$
 A^{10}=
\left[ \begin{array}{rrr}  
	0.24490804170000 &  0.24490213680000 &  0.24488245380000\\
   0.46937935970000  & 0.46938526460000 &  0.46939904270000\\
   0.28571259860000   &0.28571259860000 &  0.28571850350000	\\
	\end{array}  
\right]
$ 

and 
$
 A^{100}=
\left[ \begin{array}{rrr}  
	0.24489795918367  & 0.24489795918367  & 0.24489795918367\\
   0.46938775510204   &0.46938775510204  & 0.46938775510204\\
   0.28571428571429   &0.28571428571429  & 0.28571428571429\\
	\end{array}  
\right]
$ 

This suggest that the steady-state vector can be approximate by 

$
 A^{100}=
\left[ \begin{array}{r}  
	0.245 \\
   0.469   \\
   0.288 \\
	\end{array}  
\right]
$ 


 therefore, in long run,  $29 \% $ of the population will be in   in low income level.



\subsection{References and further studies }

Gamerman, D. Markov Chain Monte Carlo: Stochastic Simulation for Bayesian Inference. Boca Raton, FL: CRC Press, 1997. 

Gilks, W. R.; Richardson, S.; and Spiegelhalter, D. J. (Eds.). Markov Chain Monte Carlo in Practice. Boca Raton, FL: Chapman \& Hall, 1996. 

Grimmett, G. and Stirzaker, D. Probability and Random Processes, 2nd ed. Oxford, England: Oxford University Press, 1992. 

Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 6, 1994. 

Kallenberg, O. Foundations of Modern Probability. New York: Springer-Verlag, 1997. 

Kemeny, J. G. and Snell, J. L. Finite Markov Chains. New York: Springer-Verlag, 1976. 

Papoulis, A. "Brownian Movement and Markoff Processes." Ch. 15 in Probability, Random Variables, and Stochastic Processes, 2nd ed. New York: McGraw-Hill, pp. 515-553, 1984. 

Stewart, W. J. Introduction to the Numerical Solution of Markov Chains. Princeton, NJ: Princeton University Press, 1995.


\section{Related Web Sites}
\htmladdnormallink{Markov chain tutorial
}{http://pespmc1.vub.ac.be/ASC/Markov_chain.html}    \\ 
\htmladdnormallink{Markov chain tutorial
}{http://mason.gmu.edu/~scannon/ }    \\ 
\htmladdnormallink{Teletraffic analysis software that allows users to solve structured Markov chains}{http://www.cstp.umkc.edu/org/tn/telpack/home.html}    \\ 
\htmladdnormallink{History of Markov Chain (Andrei Andreyevich Markov)
}{http://sci.hkbu.edu.hk/math/markov.html}    \\ 
\htmladdnormallink{A Markov chain is a sequence of random values }{http://www.taygeta.com/rwalks/node7.html}    \\ 
\htmladdnormallink{Markov chain}{http://www.mpi-sb.mpg.de/LEDA/MANUAL/markov_chain.html}    \\ 
\htmladdnormallink{Markov chain}{http://www.tnt.uni-hannover.de/js/soft/case/lang/c++/LEDA_doc/node112.html}    \\ 
\htmladdnormallink{Applications to Markov chains}{http://www.library.usyd.edu.au/Ejournals/NM/67/4/l0670475/node8.html}    \\ 
\htmladdnormallink{Baseball as a Markov chains}{http://www.retrosheet.org/mdp/markov/intro.htm}    \\ 
\htmladdnormallink{Software for Marca}{http://www.csc.ncsu.edu/faculty/WStewart/MARCA/marca.html}    \\ 
\htmladdnormallink{Website for Markov Chain Monte Carlo (MCMC)}{http://www.ssc.wisc.edu/~sanatoly/mcmc.htm}    \\ 

\htmladdnormallink{(Application of Markov Chain)}{Enrollment Projections (Markov Chain)}    \\ 
\htmladdnormallink{Good references of Markov Chain}{http://mathworld.wolfram.com/MarkovChain.html}    \\ 
\htmladdnormallink{Sensitivity of the Stationary Distribution of a Markov Chain}{http://epubs.siam.org/sam-bin/dbq/article/22890}    \\ 
\htmladdnormallink{Use of a Markov-Chain Model to Evaluate Employment Policies}{http://borg.lib.vt.edu/ejournals/JVME/V21-1/Montgomery.html
}    \\ 
\end{document}