Linear Algebra/Topic: Markov Chains

Linear Algebra Topic: Markov Chains Topic: Geometry of Linear Maps Topic: Orthonormal Matrices 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. stateWe say that the player is in the state , , ..., or . A game consists of moving from state to state. For instance, a player now in state has on the next flip a chance of moving to state and a chance of moving to . The boundary states are a bit different; once in state or stat , the player never leaves. Let be the probability that the player is in state after flips. Then, for instance, we have that the probability of being in state after flip is . This matrix equation summarizes. With the initial condition that the player starts with three dollars, calculation gives this. <TR> <TD style="border-right:2px black solid;border-bottom:2px black solid;">    <TD style="border-bottom:2px black solid;">       <TD style="border-bottom:2px black solid;">       <TD style="border-bottom:2px black solid;">       <TD style="border-bottom:2px black solid;">       <TD style="border-bottom:2px black solid;">       <TD style="border-bottom:2px black solid;">       <TR> <TD style="border-right:2px black solid;">    <TD>       <TD>       <TD>       <TD>       <TD>       <TD>       As this computational exploration suggests, the game is not likely to go on for long, with the player quickly ending in either state or state . For instance, after the fourth flip there is a probability of that the game is already over. absorbing(Because a player who enters either of the boundary states never leaves, they are said to be absorbing.) Markov chainThis game is an example of a Markov chain, named for A.A. Markov, who worked in the first half of the 1900's. probability vectorEach vector of 's is a probability vector and the matrix is a transition matrix. historylessThe 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 by starting in state , then going to state , then to , and then to has at this point exactly the same chance of moving next to state as does a player whose history was to start in , then go to , and to , and then to . Here is a Markov chain from sociology. A study Macdonald Ridge 1988 p. 202 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. For instance, a child of a lower class worker has a 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. <TR> <TD style="border-right:2px black solid;border-bottom:2px black solid;"> <TD style="border-bottom:2px black solid;">       <TD style="border-bottom:2px black solid;">       <TD style="border-bottom:2px black solid;">       <TD style="border-bottom:2px black solid;">       <TD style="border-bottom:2px black solid;">       <TR> <TD style="border-right:2px black solid;">       <TD>       <TD>    <TD>    <TD>    <TD>    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 that the American League team wins each game then we have the following transition matrix. An especially interesting special case is ; this table lists the resulting components of the through vectors. (The code to generate this table in the computer algebra system Octave follows the exercises.) <TR> <TD style="border-bottom:2px black solid;text-align:right"> <TD style="border-right:2px black solid;border-bottom:2px black solid;">    <TD style="border-bottom:2px black solid;">       <TD style="border-bottom:2px black solid;">       <TD style="border-bottom:2px black solid;">       <TD style="border-bottom:2px black solid;">       <TD style="border-bottom:2px black solid;">       <TD style="border-bottom:2px black solid;">       <TD style="border-bottom:2px black solid;">       <TR> <TD> 0-0    <TD style="border-right:2px black solid;">    1    <TD>    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0    <TR> <TD> 1-0    <TD style="border-right:2px black solid;">    0    <TD>    0.5    <TD>    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0    <TR> <TD> 0-1    <TD style="border-right:2px black solid;">    0    <TD>    0.5    <TD>    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0    <TR> <TD> 2-0    <TD style="border-right:2px black solid;">    0    <TD>    0    <TD>    0.25    <TD>    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0    <TR> <TD> 1-1    <TD style="border-right:2px black solid;">    0    <TD>    0    <TD>    0.5    <TD>    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0    <TR> <TD> 0-2    <TD style="border-right:2px black solid;">    0    <TD>    0    <TD>    0.25    <TD>    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0    <TR> <TD> 3-0    <TD style="border-right:2px black solid;">    0    <TD>    0    <TD>    0    <TD>    0.125    <TD>    0    <TD>    0    <TD>    0    <TD>    0    <TR> <TD> 2-1    <TD style="border-right:2px black solid;">    0    <TD>    0    <TD>    0    <TD>    0.325    <TD>    0    <TD>    0    <TD>    0    <TD>    0    <TR> <TD> 1-2    <TD style="border-right:2px black solid;">    0    <TD>    0    <TD>    0    <TD>    0.325    <TD>    0    <TD>    0    <TD>    0    <TD>    0    <TR> <TD> 0-3    <TD style="border-right:2px black solid;">    0    <TD>    0    <TD>    0    <TD>    0.125    <TD>    0    <TD>    0    <TD>    0    <TD>    0    <TR> <TD> 4-0    <TD style="border-right:2px black solid;">    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0.0625    <TD>    0.0625    <TD>    0.0625    <TD>    0.0625    <TR> <TD> 3-1    <TD style="border-right:2px black solid;">    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0.25    <TD>    0    <TD>    0    <TD>    0    <TR> <TD> 2-2    <TD style="border-right:2px black solid;">    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0.375    <TD>    0    <TD>    0    <TD>    0    <TR> <TD> 1-3    <TD style="border-right:2px black solid;">    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0.25    <TD>    0    <TD>    0    <TD>    0    <TR> <TD> 0-4    <TD style="border-right:2px black solid;">    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0.0625    <TD>    0.0625    <TD>    0.0625    <TD>    0.0625    <TR> <TD> 4-1    <TD style="border-right:2px black solid;">    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0.125    <TD>    0.125    <TD>    0.125    <TR> <TD> 3-2    <TD style="border-right:2px black solid;">    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0.3125    <TD>    0    <TD>    0    <TR> <TD> 2-3    <TD style="border-right:2px black solid;">    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0.3125    <TD>    0    <TD>    0    <TR> <TD> 1-4    <TD style="border-right:2px black solid;">    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0.125    <TD>    0.125    <TD>    0.125    <TR> <TD> 4-2    <TD style="border-right:2px black solid;">    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0.15625    <TD>    0.15625    <TR> <TD> 3-3    <TD style="border-right:2px black solid;">    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0.3125    <TD>    0    <TR> <TD> 2-4    <TD style="border-right:2px black solid;">    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0.15625    <TD>    0.15625    <TR> <TD> 4-3    <TD style="border-right:2px black solid;">    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0.15625    <TR> <TD> 3-4    <TD style="border-right:2px black solid;">    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0    <TD>    0.15625    Note that evenly-matched teams are likely to have a long series— there is a probability of 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 Kemeny Snell 1960 and Iosifescu 1980. Exercises Use a computer for these problems. You can, for instance, adapt the Octave script given below. Problem 1 These questions refer to the coin-flipping game. <li> Check the computations in the table at the end of the first paragraph. <li> Consider the second row of the vector table. Note that this row has alternating 's. Must be when is odd? Prove that it must be, or produce a counterexample. <li> Perform a computational experiment to estimate the chance that the player ends at five dollars, starting with one dollar, two dollars, and four dollars. Problem 2 We consider throws of a die, and say the system is in state if the largest number yet appearing on the die was . <li> Give the transition matrix. <li> Start the system in state , and run it for five throws. What is the vector at the end? Feller 1968 p. 424 Problem 3 There has been much interest in whether industries in the United States are moving from the Northeast and North Central regions to the South and West, motivated by the warmer climate, by lower wages, and by less unionization. Here is the transition matrix for large firms in Electric and Electronic Equipment Kelton 1983 p. 43 <TR> <TD style="border-bottom:2px black solid;border-right:2px black solid;">       <TD style="border-bottom:2px black solid;">    NE    <TD style="border-bottom:2px black solid;">    NC    <TD style="border-bottom:2px black solid;">    S    <TD style="border-bottom:2px black solid;">    W    <TD style="border-bottom:2px black solid;">    Z <TR> <TD style="border-right:2px black solid;">NE    <TD>    0.787    <TD>    0    <TD>    0    <TD>    0.111    <TD>    0.102 <TR> <TD style="border-right:2px black solid;">NC    <TD>    0    <TD>    0.966    <TD>    0.034    <TD>    0    <TD>    0 <TR> <TD style="border-right:2px black solid;">S    <TD>    0    <TD>    0.063    <TD>    0.937    <TD>    0    <TD>    0 <TR> <TD style="border-right:2px black solid;">W    <TD>    0    <TD>    0    <TD>    0.074    <TD>    0.612    <TD>    0.314 <TR> <TD style="border-right:2px black solid;">Z    <TD>    0.021    <TD>    0.009    <TD>    0.005    <TD>    0.010    <TD>    0.954 <TR> For example, a firm in the Northeast region will be in the West region next year with probability . (The Z entry is a "birth-death" state. For instance, with probability a large Electric and Electronic Equipment firm from the Northeast will move out of this system next year: go out of business, move abroad, or move to another category of firm. There is a probability that a firm in the National Census of Manufacturers will move into Electronics, or be created, or move in from abroad, into the Northeast. Finally, with probability a firm out of the categories will stay out, according to this research.) <li> Does the Markov model assumption of lack of history seem justified? <li> Assume that the initial distribution is even, except that the value at is . Compute the vectors for through . <li> Suppose that the initial distribution is this. <TR> <TD style="border-bottom:2px black solid;">NE    <TD style="border-bottom:2px black solid;">    NC    <TD style="border-bottom:2px black solid;">    S    <TD style="border-bottom:2px black solid;">    W    <TD style="border-bottom:2px black solid;">    Z <TR> <TD>0.0000    <TD>    0.6522    <TD>    0.3478    <TD>    0.0000    <TD>    0.0000    Calculate the distributions for through . <li> Find the distribution for and . Has the system settled down to an equilibrium? Problem 4 This model has been suggested for some kinds of learning Wickens 1982 p. 41. The learner starts in an undecided state . Eventually the learner has to decide to do either response (that is, end in state ) or response (ending in ). However, the learner doesn't jump right from being undecided to being sure is the correct thing to do (or ). Instead, the learner spends some time in a "tentative-" state, or a "tentative-" state, trying the response out (denoted here and ). Imagine that once the learner has decided, it is final, so once or is entered it is never left. For the other state changes, imagine a transition is made with probability in either direction. <li> Construct the transition matrix. <li> Take and take the initial vector to be at . Run this for five steps. What is the chance of ending up at ? <li> Do the same for . <li> Graph versus the chance of ending at . Is there a threshold value for , above which the learner is almost sure not to take longer than five steps? Problem 5 A certain town is in a certain country (this is a hypothetical problem). Each year ten percent of the town dwellers move to other parts of the country. Each year one percent of the people from elsewhere move to the town. Assume that there are two states , living in town, and , living elsewhere. <li> Construct the transistion matrix. <li> Starting with an initial distribution and , get the results for the first ten years. <li> Do the same for . <li> Are the two outcomes alike or different? Problem 6 For the World Series application, use a computer to generate the seven vectors for and . <li> What is the chance of the National League team winning it all, even though they have only a probability of or of winning any one game? <li> Graph the probability against the chance that the American League team wins it all. Is there a threshold value— a above which the better team is essentially ensured of winning? (Some sample code is included below.) Problem 7Markov matrix A Markov matrix has each entry positive and each column sums to . <li> Check that the three transistion matrices shown in this Topic meet these two conditions. Must any transition matrix do so? <li> Observe that if and then is a transition matrix from to . Show that a power of a Markov matrix is also a Markov matrix. <li> Generalize the prior item by proving that the product of two appropriately-sized Markov matrices is a Markov matrix. /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 William Feller An Introduction to Probability Theory and Its Applications 1 3rd Wiley 1968. Marius Iosifescu Finite Markov Processes and Their Applications UMI Research Press 1980. Christina M.L. Kelton Trends on the Relocation of U.S. Manufacturing Wiley 1983. John G. Kemeny J. Laurie Snell Finite Markove Chains D.~Van Nostrand 1960. Kenneth Macdonald John Ridge Social Mobility British Social Trends Since 1900 Macmillian 1988. Thomas D. Wickens Models for Behavior W.H. Freeman 1982. Linear Algebra Topic: Markov Chains Topic: Geometry of Linear Maps Topic: Orthonormal Matrices