Matrix Applications: Markov Chains and Game Theory

1 Matrix applications : Markov Chains and Game TheoryChristopher Carl HeckmanDepartment of Mathematics and Statistics, Arizona State important applications of matrices which are discussed in MAT 119 are Markov Chains andGame Theory . Here, we present a brief summary of what the textbook covers, as well as how tosolve certain problems in these Chains model a situation, where there are a certain number ofstates(which will unimaginitivelybe called 1, 2,..,n), and whether the state changes from stateito statejis a constant probability. Inparticular, it does not matter what happened, for the state to be in stateiin the first general, the state that the situation is in will only be known probabilistically; thus, there is a prob-ability ofp1that it is in state 1, a probability ofp2that it is in state 2, etc. A row vectorvwithnentriesrepresents the probabilistic knowledge of the state if each entry is nonnegative, and the sum of the entriesinvis 1; in that case,vis called aprobability change in state from one point in time to another point in time is determined by ann ntransitionmatrixP, which has the properties that:(a)Pi,j 0 for alli, (b)Pi,1+Pi,2+ +Pi,n= 1, for entryPi,jrepresents the probability that you will change from stateito probability vectorv0is used for the inital set-up.

2 Moving Around A instance, if you imagine 1, 2, 3, and 4 being corners of a square (where1 and 3 are non-adjacent, and 2 and 4 are non-adjacent), you start at corner #1, and in each step you deciderandomly and fairly which of the following to do:(a) Stay where you are;(b) Move fromnton+ 1 (Where you go to 1, if you re at 4); and(c) Move fromnton 1 (where you go to 4, if you re at 1);thenv0= [1,0,0,0] and the transition Matrix isP= 1/3 1/3 0 1/31/3 1/3 1/3 00 1/3 1/3 1/31/3 0 1/3 1/3 . for some vocabulary:A Markov chain is calledregularif there is some positive integerk >0 such that (Pk)i,j>0 for alli, means you can potentially get from any state to any other state inksteps. The example above( Moving Around A Square ) is regular, since every entry ofP2is probability vectortis afixed probability vectorift=tP. [ , , , ] is a fixed probabilityvector of Moving Around A Square (and is in fact the only one); [1,0,0,0,0] and [0,0,0,0,1] are fixedprobability vectors of Drunken Walk (covered in the Behavior of Absorbing Markov Chains section).

3 1Ai,jis my notation for the entry in theith row and thejth column ofA. Some books useai,jfor thisnumber. Also, for alli should be interpretted to mean for allifor which this makes sense. 2 Pnis defined in the sense of Matrix probability vectors probability of being in statejafter one iteration can be broken in to the sum of the probability of beingin statei, times the probability that you go from stateito statej, summed over all statesi. Thus, ifv0is the initial state, the probability vector after one iteration isv0P. Iterating, we find that the probabilityvector afterkstate isv(k)= instance, in Moving Around A Square , the probability vector after one iteration isv(1)=v0P= [1,0,0,0] 1/3 1/3 0 1/31/3 1/3 1/3 00 1/3 1/3 1/31/3 0 1/3 1/3 =[13,13,0,13],the probability vector after two iterations isv(2)=v0P2= [1,0,0,0] 1/3 1/3 0 1/31/3 1/3 1/3 00 1/3 1/3 1/31/3 0 1/3 1/3 2=[13,29,29,29],and so all fixed probability fixed probability vector satisfies the conditiont=tP, sot(P I) = 0.

4 Because we are used to solvingsystems of linear equations where the vector is a column vector, we will take the thetranspose reverses the order of the factors, we end up solving(P I)> t>= 0.(1)But a probability vector also has to have entries which add up to 1; we can incorporate this into thesystem of linear equations by writing this condition as[1,1, .. ,1] t>= 0.(2)SincePis a transition Matrix , the rows of (P I)>add up to [0,0, .. ,0]. This means that thenth equation in (1) is redundant, and we can incorporate (2) into the system by removing the last row of(P I)>and replacing it by [1,1, .. ,1]. If we call this new matrixR, then we need to find solutions toR = .(3)(Note that we have not insisted that the entries oftbe nonnegative. After we find all solutions, we willput restrictions on the free variables (if there are any) to make these entries nonnegative.)For instance, for Moving Around A Square , our system of equations in (3) becomes 2/3 1/30 1/31/3 2/3 1/3 001/3 2/3 1/31111 t1t2t3t4 = 0001.

5 3 IfAis anm nmatrix, then thetransposeofA(denotedA>) is then mmatrixBsuch thatBi,j=Aj,ifor alli, system has a unique solution, namelyt= [ , , , ].4 For an example of a Markov Chainwith more than one fixed probability vector, see the Drunken Walk example of absorbing Markov stateiis anabsorbing stateifPi,i= 1; it is one from which you cannot change to another state. ( MovingAround A Square has no absorbing states.) A Markov chain with at least one absorbing state, and forwhich all states potentially lead to an absorbing state, is called anabsorbing Markov is a street in a town with a De-tox center, three bars in a row, and a Jail, allin a row. A man is in the bar in the middle. Every hour, whenever he is in a bar, he takes a drink, goesoutside, chooses a direction at random with equal probability, and then walks one building in that he ends up at the De-tox center or the Jail, he is taken in for the rest of the night. If we use 1, 2,.., 5to denote the five buildings (where the De-tox center is 1), then we end up with a Markov chain with thefollowing transition Matrix :P= 1 0 0 0 0 0 00 0 00 0 0 0 0 0 1 and initial probability vectorv0= [0,0,1,0,0].

6 Drunken Walk is an absorbing Markov chain , since 1 and 5 are absorbing we look for allfixed probability vectors, we find that we need to solve the system 0 0 0 00 1 0 00 1 00 0 1 01 1 1 1 1 t1t2t3t4t5 = 00001 .There are an infinite number of solutions:t= [t1, t2, t3, t4, t5] = [a,0,0,0,1 a].Since every entry must be nonnegative, we must havea 0 and 1 a 0, which means 0 a an absorbing Markov chain , we can also ask the following questions: How many iterations shouldwe expect before entering an absorbing state? How many times do we expect to be in a non-absorbing statei? What is the probability of reaching absorbing statej, assuming we start at statei?7We answer thesequestions do this, we take the transition matrixPand shuffle the rows and columns so that all of the absorbingstates are together, and all the absorbing states are together. IfPi,i= 1, we can swap rowiofPwith row1, and then swap columniofPwith column 1, to get the 1 in the first row and first column.

7 After that, wecan take another absorbing state (say,Pj,j= 1, wherej6= 1) and place the 1 in the second row and secondcolumn, etc. By doing so, we can obtain a sort of canonical form forP, which is as follows:P=[Ir0S Q],(4)4If you have a regular Markov chain , then it can be proven that there is exactly one fixed probabilityvector, and the long-term behavior of that Markov chain is that fixed probability Drunken Walk is based on the Gambler s Ruin Markov chain is not regular. No absorbing Markov chain is last question, in the context of an interrupted dice game, was what led Blaise Pascal to startinvestigating the topic of the number of absorbing states; we will also letsbe the number of non-absorbing example of Drunken Walk , the matrixPbecomesP= 1 0 0 0 00 1 0 0 00 0 0 0 0 0 0 ,so thatr= 2,s= 3,S= 0 00 0 , andQ= 0 0 0 0 . Note that the rows ofS, the rows ofQ,and the columns ofQcorrespond to the states 3, 4, and 2, in that order, and the columns ofScorrespondto the absorbing states 1, 5 (in that order), so thatSiss randQiss Matrix associated with an absorbing Markov chain is the so-calledfundamental matrixT,given by:T=Is+Q+Q2+Q3+ = (Is Q) 1.

8 (5)The probability of getting from stateito statejinksteps is (Qk)i,j. ThusTi,jis the probability of gettingfrom stateito statejin 0 steps, plus the probability in 1 step, plus the probability in 2 steps, etc. Thissum is the expected number of times we go from stateito we add the entries in theith row ofT, we obtain the expected number of times that we are in a non-absorbing Drunken Walk ,T= 1 0 00 1 00 0 1 0 0 0 0 1= 2 1 11 .In terms of the problem, where the man starts in bar #3 (row 1), this states that the man will expect tobe in bar #3 two times, in bar #2 once, and in bar #4 once. The expected number of drinks he will get is2 + 1 + 1 = 4. (If he started in bar #2 or bar #4, the expected number of drinks is 1 + + = 3.)To find the probability that the man ends up in states 1 or 5 (De-tox or Jail), we calculate the matrixT S; then (T S)i,jis the probability that the Markov chain ends up in abosorbing statej, assuming itstarts in (the non-absorbing10) statei.

9 For Drunken Walk ,T S= 2 1 11 0 00 0 = .So the probability of the man ending up in De-tox is and in Jail is (We could have guessed this fromthe symmetry of the problem.) If he starts in bar #2, the probability he ends up in De-tox is , and theprobability he ends up in Jail is every state is an absorbing state, then the whole matrixP=In; but then the questions asked aboveare not sum converges because all the eigenvalues ofQturn out to be less than 1 in absolute value, thematrix equivalent of the geometric ratio the initial state is absorbing, the probability of ending up injis easy to , the row for bar #2 is the bottom row ofTandT to a situation where there are two or more players, who each have a set of options. If theseplayers choose particular options, the rules of the game determine which of the players get rewarded. ForMAT 119, all games are assumed to have two players, and the reward is determined by a matrixAcalledthepayoff Matrix , and each player will have only a finite number of options, which will be numbered.

10 ThenumberAijdetermines how many points Player I receives from Player II if Player I chooses optioniandPlayer II chooses addition, it will be assumed that both players have received the payoffmatrix in example of a game is Rock Scissors Paper , where we will let 1 denote Rock, 2 denote Scissors,and 3 denote Paper. In this game, Rock breaks (beats) Scissors, Scissors cut (beat) Paper, and Paper covers(beats) Rock. The payoff Matrix isA= 0 1 1 1 0 11 1 0 . optimal strategies: Saddle payoff matrices have one or moresaddle points. A saddle point is a pair of strategies (i, j) such thatAi,m Ai,jfor allm, andAm,j Ai,jfor allm. For instance, if the payoff Matrix isA=(2 13 4), then(2,1) is a saddle points represent optimum solutions. Remember that Player I is trying to maximize his payoff,and Player II is trying to minimize it. By choosing option 2 in the example in the previous paragraph,Player I is guaranteed of receiving 3 points, possibly more.