Linear Algebra/Topic: Markov Chains

Template:Navigation Here is a simple game: a player bets on coin tosses, a dollar each time, and the game ends either when the player has no money left or is up to five dollars. If the player starts with three dollars, what is the chance that the game takes at least five flips? Twenty-five flips?

At any point, this player has either $0, or $1, ..., or $5. Template:AnchorWe say that the player is in the state $s_0$, $s_1$, ..., or $s_5$. A game consists of moving from state to state. For instance, a player now in state $s_3$ has on the next flip a $0.5$ chance of moving to state $s_2$ and a $0.5$ chance of moving to $s_4$. The boundary states are a bit different; once in state $s_0$ or stat $s_5$, the player never leaves.

Let $p_i(n)$ be the probability that the player is in state $s_i$ after $n$ flips. Then, for instance, we have that the probability of being in state $s_0$ after flip $n+1$ is $p_0(n+1)=p_0(n)+0.5\cdot p_1(n)$. This matrix equation summarizes.

$\left(\begin{array}{cccccc}1& 0.5& 0& 0& 0& 0\\ 0.5& 0& 0.5& 0& 0& 0\\ 0& 0.5& 0& 0.5& 0& 0\\ 0& 0& 0.5& 0& 0.5& 0\\ 0& 0& 0& 0.5& 0& 0.5\\ 0& 0& 0& 0& 0.5& 1\end{array}\right)\left(\begin{array}{c}{p}_0(n)\\ p_1(n)\\ p_2(n)\\ p_3(n)\\ p_4(n)\\ p_5(n)\end{array}\right)=\left(\begin{array}{c}{p}_0(n+1)\\ p_1(n+1)\\ p_2(n+1)\\ p_3(n+1)\\ p_4(n+1)\\ p_5(n+1)\end{array}\right)$

With the initial condition that the player starts with three dollars, calculation gives this.

$n=0$	$n=1$	$n=2$	$n=3$	$n=4$	$\cdots$	$n=24$
$\left(\begin{array}{c}0\\ 0\\ 0\\ 1\\ 0\\ 0\end{array}\right)$	$\left(\begin{array}{c}0\\ 0\\ 0.5\\ 0\\ 0.5\\ 0\end{array}\right)$	$\left(\begin{array}{c}0\\ 0.25\\ 0\\ 0.5\\ 0\\ 0.25\end{array}\right)$	$\left(\begin{array}{c}0.125\\ 0\\ 0.375\\ 0\\ 0.25\\ 0.25\end{array}\right)$	$\left(\begin{array}{c}0.125\\ 0.1875\\ 0\\ 0.3125\\ 0\\ 0.375\end{array}\right)$	$\cdots$	$\left(\begin{array}{c}0.39600\\ 0.00276\\ 0\\ 0.00447\\ 0\\ 0.59676\end{array}\right)$

As this computational exploration suggests, the game is not likely to go on for long, with the player quickly ending in either state $s_0$ or state $s_5$. For instance, after the fourth flip there is a probability of $0.50$ that the game is already over. Template:Anchor(Because a player who enters either of the boundary states never leaves, they are said to be absorbing.)

Template:AnchorThis game is an example of a Markov chain, named for A.A. Markov, who worked in the first half of the 1900's. Template:AnchorEach vector of $p$'s is a probability vector and the matrix is a transition matrix. Template:AnchorThe notable feature of a Markov chain model is that it is historyless in that with a fixed transition matrix, the next state depends only on the current state, not on any prior states. Thus a player, say, who arrives at $s_2$ by starting in state $s_3$, then going to state $s_2$, then to $s_1$, and then to $s_2$ has at this point exactly the same chance of moving next to state $s_3$ as does a player whose history was to start in $s_3$, then go to $s_4$, and to $s_3$, and then to $s_2$.

Here is a Markov chain from sociology. A study Template:Harv divided occupations in the United Kingdom into upper level (executives and professionals), middle level (supervisors and skilled manual workers), and lower level (unskilled). To determine the mobility across these levels in a generation, about two thousand men were asked, "At which level are you, and at which level was your father when you were fourteen years old?" This equation summarizes the results.

$\left(\begin{array}{ccc}0.60& 0.29& 0.16\\ 0.26& 0.37& 0.27\\ 0.14& 0.34& 0.57\end{array}\right)\left(\begin{array}{c}{p}_U(n)\\ p_M(n)\\ p_L(n)\end{array}\right)=\left(\begin{array}{c}{p}_U(n+1)\\ p_M(n+1)\\ p_L(n+1)\end{array}\right)$

For instance, a child of a lower class worker has a $.27$ probability of growing up to be middle class. Notice that the Markov model assumption about history seems reasonable— we expect that while a parent's occupation has a direct influence on the occupation of the child, the grandparent's occupation has no such direct influence. With the initial distribution of the respondents's fathers given below, this table lists the distributions for the next five generations.

$n=0$	$n=1$	$n=2$	$n=3$	$n=4$	$n=5$
$\left(\begin{array}{c}0.12\\ 0.32\\ 0.56\end{array}\right)$	$\left(\begin{array}{c}0.23\\ 0.34\\ 0.42\end{array}\right)$	$\left(\begin{array}{c}0.29\\ 0.34\\ 0.37\end{array}\right)$	$\left(\begin{array}{c}0.31\\ 0.34\\ 0.35\end{array}\right)$	$\left(\begin{array}{c}0.32\\ 0.33\\ 0.34\end{array}\right)$	$\left(\begin{array}{c}0.33\\ 0.33\\ 0.34\end{array}\right)$

One more example, from a very important subject, indeed. The World Series of American baseball is played between the team winning the American League and the team winning the National League (we follow [Brunner] but see also [Woodside]). The series is won by the first team to win four games. That means that a series is in one of twenty-four states: 0-0 (no games won yet by either team), 1-0 (one game won for the American League team and no games for the National League team), etc. If we assume that there is a probability $p$ that the American League team wins each game then we have the following transition matrix.

$\left(\begin{array}{ccccc}0& 0& 0& 0& \dots \\ p& 0& 0& 0& \dots \\ 1-p& 0& 0& 0& \dots \\ 0& p& 0& 0& \dots \\ 0& 1-p& p& 0& \dots \\ 0& 0& 1-p& 0& \dots \\ ⋮& ⋮& ⋮& ⋮\end{array}\right)\left(\begin{array}{c}{p}_{\text{0-0}}(n)\\ p_{\text{1-0}}(n)\\ p_{\text{0-1}}(n)\\ p_{\text{2-0}}(n)\\ p_{\text{1-1}}(n)\\ p_{\text{0-2}}(n)\\ ⋮\end{array}\right)=\left(\begin{array}{c}{p}_{\text{0-0}}(n+1)\\ p_{\text{1-0}}(n+1)\\ p_{\text{0-1}}(n+1)\\ p_{\text{2-0}}(n+1)\\ p_{\text{1-1}}(n+1)\\ p_{\text{0-2}}(n+1)\\ ⋮\end{array}\right)$

An especially interesting special case is $p=0.50$; this table lists the resulting components of the $n=0$ through $n=7$ vectors. (The code to generate this table in the computer algebra system Octave follows the exercises.)

	$n=0$	$n=1$	$n=2$	$n=3$	$n=4$	$n=5$	$n=6$	$n=7$
0-0	1	0	0	0	0	0	0	0
1-0	0	0.5	0	0	0	0	0	0
0-1	0	0.5	0	0	0	0	0	0
2-0	0	0	0.25	0	0	0	0	0
1-1	0	0	0.5	0	0	0	0	0
0-2	0	0	0.25	0	0	0	0	0
3-0	0	0	0	0.125	0	0	0	0
2-1	0	0	0	0.325	0	0	0	0
1-2	0	0	0	0.325	0	0	0	0
0-3	0	0	0	0.125	0	0	0	0
4-0	0	0	0	0	0.0625	0.0625	0.0625	0.0625
3-1	0	0	0	0	0.25	0	0	0
2-2	0	0	0	0	0.375	0	0	0
1-3	0	0	0	0	0.25	0	0	0
0-4	0	0	0	0	0.0625	0.0625	0.0625	0.0625
4-1	0	0	0	0	0	0.125	0.125	0.125
3-2	0	0	0	0	0	0.3125	0	0
2-3	0	0	0	0	0	0.3125	0	0
1-4	0	0	0	0	0	0.125	0.125	0.125
4-2	0	0	0	0	0	0	0.15625	0.15625
3-3	0	0	0	0	0	0	0.3125	0
2-4	0	0	0	0	0	0	0.15625	0.15625
4-3	0	0	0	0	0	0	0	0.15625
3-4	0	0	0	0	0	0	0	0.15625

Note that evenly-matched teams are likely to have a long series— there is a probability of $0.625$ that the series goes at least six games.

One reason for the inclusion of this Topic is that Markov chains are one of the most widely-used applications of matrix operations. Another reason is that it provides an example of the use of matrices where we do not consider the significance of the maps represented by the matrices. For more on Markov chains, there are many sources such as Template:Harv and Template:Harv.

Exercises

Use a computer for these problems. You can, for instance, adapt the Octave script given below. Template:TextBox Template:TextBox Template:TextBox Template:TextBox Template:TextBox Template:TextBox Template:TextBox

/Solutions/

Computer Code

This script markov.m for the computer algebra system Octave was used to generate the table of World Series outcomes. (The sharp character # marks the rest of a line as a comment.)

# Octave script file to compute chance of World Series outcomes.
function w = markov(p,v)
q = 1-p;
A=[0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 0-0
p,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 1-0
q,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 0-1_
0,p,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 2-0
0,q,p,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 1-1
0,0,q,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 0-2__
0,0,0,p,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 3-0
0,0,0,q,p,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 2-1
0,0,0,0,q,p, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 1-2_
0,0,0,0,0,q, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 0-3
0,0,0,0,0,0, p,0,0,0,1,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 4-0
0,0,0,0,0,0, q,p,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 3-1__
0,0,0,0,0,0, 0,q,p,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 2-2
0,0,0,0,0,0, 0,0,q,p,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0;  # 1-3
0,0,0,0,0,0, 0,0,0,q,0,0, 0,0,1,0,0,0, 0,0,0,0,0,0;  # 0-4_
0,0,0,0,0,0, 0,0,0,0,0,p, 0,0,0,1,0,0, 0,0,0,0,0,0;  # 4-1
0,0,0,0,0,0, 0,0,0,0,0,q, p,0,0,0,0,0, 0,0,0,0,0,0;  # 3-2
0,0,0,0,0,0, 0,0,0,0,0,0, q,p,0,0,0,0, 0,0,0,0,0,0;  # 2-3__
0,0,0,0,0,0, 0,0,0,0,0,0, 0,q,0,0,0,0, 1,0,0,0,0,0;  # 1-4
0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,p,0, 0,1,0,0,0,0;  # 4-2
0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,q,p, 0,0,0,0,0,0;  # 3-3_
0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,q, 0,0,0,1,0,0;  # 2-4
0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,p,0,1,0;  # 4-3
0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,q,0,0,1]; # 3-4
w = A * v;
endfunction

Then the Octave session was this.

> v0=[1;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0]
> p=.5
> v1=markov(p,v0)
> v2=markov(p,v1)
...

Translating to another computer algebra system should be easy— all have commands similar to these.

References

• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.