Lecture Notes on Markov Chains - IEOR 4701

IEOR 4701 Professor Whitt Lecture Notes Monday July 16 2007 Introduction to Markov Chains 1 Markov Mouse The Closed Maze We start by considering how to model a mouse moving around in a maze The maze is a closed space containing nine rooms The space is arranged in a threebythree array of rooms with doorways connecting the rooms as shown in the figure below The Maze 1 2 3 4 5 6 7 8 9 There are doors leading to adjacent rooms vertically and horizontally In particular there are doors from 1 to 2 4 from 2 to 1 3 5 from 3 to 2 6 from 4 to 1 5 7 from 5 to 2 4 6 8 from 6 to 3 5 9 from 7 to 4 8 from 8 to 5 7 9 from 9 to 6 8 We assume that the mouse is a Markov mouse ie the mouse moves randomly from room to room with the probability distribution of the next room depending only on the current room not on the history of how it got to the current room This is the Markov property Moreover we assume that the mouse is equally likely to choose each of the available doors in the room it occupies That is a special property beyond the Markov property We now model the movement of the mouse as a Markov chain The state of the Markov chain is the room occupied by the mouse We let the time index n refer to the nth room visited by the mouse So we make a discretetime Markov chain Specifically we let Xn be the state room occupied by the mouse on step or time or transition n The initial room is X0 The room after the first transition is X1 and so forth Then Xn n 0 is the discretetime Markov chain DTMC it is a discretetime discretestate stochastic process The mouse is in room Xn a random variable after making n moves after having started in room X0 which could also be a random variable We specify the evolution of the Markov chain by specifying the onestep transition prob abilities We specify these transition probabilities by specifying the transition matrix For our example making a discretetime Markov chain model means that we define a 99 Markov transition matrix consistent with the specification above For the most part specifying the transition matrix is specifying the model We also must say how we start The starting point could be random in which case the initial position would be specified by a probability vector Notation It is common to denote the transition matrix by P and its elements by Pij ie Pij denotes the probability of going to state j next when currently in state i When the state space has m states is finite P is a square m m matrix For example for our Markov mouse model we have P12 12 and P14 12 with P1j 0 for all other j 1 j 9 And we have P21 P23 P25 13 with P2j 0 for all other j And so forth Here is the total transition matrix P 1 2 3 4 5 6 7 8 9 0 12 0 12 0 0 0 0 0 13 0 13 0 13 0 0 0 0 0 12 0 0 0 12 0 0 0 13 0 0 0 13 0 13 0 0 0 14 0 14 0 14 0 14 0 0 0 13 13 0 0 0 13 0 0 0 12 0 0 0 12 0 0 0 0 0 13 0 13 0 13 0 0 0 0 0 12 0 12 0 It is common to label the columns but we did not above They are numbered in the same way as the rows Here the columns are numbered from 1 to 9 starting at the left Hence the matrix element in the upper left corder is P11 while the matrix element in the lower right corner is P99 The matrix element P23 appears in the second row and third column The rows represent the starting state while the column represents the next step ie P23 is the probability of going next to state 3 given that you are starting in state 2 The Markov property implies that the probability does not depend on the earlier history Each time the Markov chain is in state 2 its transition probabilities are the same independent of how it happened to get there We are assuming that the transition probabilities do not depend on either time or the previous states visited 2 We can analyze the evolution of the Markov chain over time successive transitions by looking at powers of the matrix P In particular the kstep transition matrix is just the k power of the matrix P Thus P denotes the kstep transition matrix while P denotes the k power of the transition matrix P A main theorem is that P P You should look at the powers of the matrix P in MATLAB available for example in the IEOR Computer Lab in 301 Mudd or some other suitable programming language Even the T89 calculator can do matrix multiplication You can also access MATLAB from Butler Library and the Mathematics Building Sample MATLAB code is given in my webpage exam ples see the Computational Tools link Use the program statm or the program stationarym to analyze this example It is important here to know how to do matrix multiplication Suppose that A A is a k X m matrix while B B is an m x n matrix Then the matrix product AB is the k x nm matrix with matrix elements m ABij Ss Ai pPBpj p1 Hence if P is the transition matrix of an mstate DTMC then P and P are m x m matrices with Q p Py Pi So PipPoi p1 and kt pk YO ph PX PES PE Pyg for k2 p1 Much can be done by thinking Here are some probabilities to estimate P P P PIR PR 18 Py5 P P PR 2 18 P39 18 Pr 18 P55 3 The simple formulas that result can be seen as a consequence of periodicity and symmetry Note that the state necessarily alternates between even and odd You go from even to odd to even to odd and so forth Hence you can go from an oddnumbered state to an oddnumbered state only in an even number of steps Similarly you can go from an evennumbered state to an evennumbered state in an even number of steps This is a periodic DTMC with period 2 One of the key ideas is that there is statistical regularity in the long run This regularity can be seen by calculating high powers of the matrix P Because of the periodicity in this example we do not have P converge as n co We would have that without the periodicity but we have periodicity here The matrix powers converge if we look at the powers P or P1 We also obtain convergence if we look at P P2 average of the entries This convergence is remarkably fast You should convince yourself by performing calculations In order to determine what the longrun probabilities are for this example you can exploit symmetry By symmetry the longrun probabilities of being in the states 2 46 and 8 should be identical Hence for large k we should have 1 2k 2k 2k 2k Pro Pog Pro Peg 7 In fact it may be somewhat surprising but need not actually be too large You should verify this with Matlab Similarly the longrun probability of being in the odd states except state 5 should be identical The oddnumbered states are a bit tricky but we can work from the evennumbered states 1 1 1 1 1 p2k pk1p p1p2 22 1 12 f21tly4 Fat 4 3 1 3 6 With Markov chains we are often interested in the longrun transition probabilities These transition probabilities often converge as the number of transitions increases but in this ex ample they do not because of the periodicity Because of the periodicity the probabilities do not simply converge They alternate between positive values which converge and 0 These properties that can be deduced from detailed analysis can be confirmed by looking at powers of the transition matrix P So the probabilities above are 3 Pry 0 7 Pra 0 7 Pig 0 7 P 24 0 Prs 0 Pii 0 Py 14 Pih x 14 PiZ 14 PIS 14 Py 14 Pi 16 4 18 Piz 16 18 P35 16 18 Pis 13 18 P55 13 For any initial probability vector a a1m aP gives the new probability vector after one transition An important concept is the notion of a stationary probability vector An important theorem about irreducible finitestate DIMCs states that there exists a unique probability vector 7 717m such that n7P That is a matrix equation For the corresponding matrix elements we have m Tj SomPij forall 7 ljgm k1 A DTMC is irreducible if it is possible to go from any state to any other state in some number of transitions We can relate the positive limiting probability vectors to the stationary probabilities 7 These positive approximate limiting probabilities are exactly twice the elements of the station ary probability vector 7 because of the periodicity For example 72 18 while P35 x 14 Looking ahead to future classes As we will discuss later the Markov maze here as well as much larger mazes can be analyzed very quickly by exploiting the structure of a random walk on a graph The idea is to let the rooms by nodes in the graph The doors from room to room then become arcs in the graph There is an arc in the graph between node i and node j whenever there is a positive probability of going from room i to room j in the maze in one step Because of the structure of a random walk on a graph the stationary probability of being in room 7 turns out to be the number of doors out of room 7 divided by the sum over the rooms of the number of doors out of each room That simple formula is a consequence of the detailed balance that holds for this example Detailed balance is equivalent to the Markov chain being time reversible See Section 48 in the textbook We will get there in due course Summary So Far 1 For a finitestate DTMC the model is mostly just a matrix P There is also the initial distribution a probability vector 2 Multistep transition probabilities are given by powers of the transition matrix P 3 The longrun behavior can be seen from looking at high powers of the matrix P 4 We let X be the state of the Markov chain after the n transtion then X n 0 is the stochastic process Markov chain The transtion probability is Pig PXn41 Xn i 5 The Markov property asserts that the conditional probability of future states given the present states and information about past states depends only on the present state As a 5 formula the Markov property states that PXn1 jXn i X0 i0 X1 i1 Xn1 in1 PXn1 jXn i for all possible past events X0 i0 X1 i1 Xn1 in1 Additional Points 6 The longrun behavior can also be found from the stationary probabilities assuming the Markov chain is irreducible which it is We are also using the fact that the state space is finite When the state space is infinite we need to make extra assumptions The stationary probability can be found by solving π πP The stationary probability vector π is defined as being a probability vector such that if we then transition according to P the distribution after the transition is again π That is π is a stationary probability vector under the operator P In general the matrix P is thought of as an operator because it maps probability vectors into probability vectors Solving π πP is just solving a system of linear equations Subtle point there is one redundant equation The extra equation needed is obtained by the condition that the probabilities should add to 1 7 Often but not always the stationary probabilities of an irreducible Markov chain coincide with the longrun limiting probabilities They do when the DTMC is aperiodic period 1 They do not when the Markov chain is periodic The closed maze is an example of a periodic chain period 2 8 If a chain is periodic with period d then the stationary probabilities can be obtained approximately from the average of d successive high matrix powers eg from P n1 P n2 P ndd for large n 9 If a chain is periodic with period d then the longrun limiting probabilities are obtained from the stationary probabilities eg P nd ii dπi The probabilities P n ij assume the values dπj once and 0 d 1 times as n increases 10 Sample MATLAB output and programs are given on the computational tools web page for this course 2 Liberating Markov Mouse The Open Maze 21 The First Absorbing Chain Suppose that we add a door from room 9 to the outside and that we allow the mouse to leave room 9 from any of the doors available to it Now there are three doors out of room 9 one of which takes it outside Suppose also that the mouse does not reenter the maze after it has left This modification significantly changes the problem Now the mouse will eventually leave the maze with probability one There is no interesting longrun distribution of being in the different rooms Eventually the mouse will leave the maze However we can still model the process as a Markov chain We can add an extra state for the outside We can call the outside state 10 We thus have a 10 10 Markov transition matrix Now the probabilities of row 9 change Now we have P96 P98 P910 13 And there is a 10th row with entries P1010 10 and P10j 0 for all other j We also have Pi10 0 for all i 9 6 New questions become interesting for this absorbing Markov chain Now we want to know about the time it takes until the mouse leaves the maze Now we want to know about the expected number of visits to the various rooms before the mouse leaves the maze We now show how to compute the expected number of steps from each starting state until the mouse leaves the maze We obtain a system of 9 equations in 9 unknowns by conditioning on what happens in the first step Let Ti be the time number of steps until the mouse leaves the maze first enters state 10 starting in state i We cannot find ETi for one i directly but we can solve for all of the ETi in a system of equations For example the first equation is ET1 1 12ET2 12ET4 while the second equation is ET2 1 13ET1 13ET3 13ET5 We can use MATLAB again to solve this system of equations 22 The Second Absorbing Markov Chain We now consider a larger example with more possible absorbing states Now we put a door leading out of the maze from rooms 3 7 and 9 The probabilities of leaving through each of these doors is 13 As before we let the mouse choose each of the available doors with equal probability Wherever the mouse leaves the original 9 rooms we assume that the mouse cannot return He stays outside Here is the new picture The Maze with Outside Rooms 1 2 3 4 7 9 8 5 6 10 12 11 We now pay attention to the door from which the mouse leaves the maze We thus obtain the 12state absorbing Markov chain with 3 absorbing states We say that the Markov chain 7 enters state 10 if the mouse leaves through the door out of room 3 we say that the Markov chain enters state 11 if the mouse leaves through the door out of room 7 we say that the Markov chain enters state 12 if the mouse leaves through the door out of room 9 We let the mouse stay outside the maze when it leaves so the Markov chain is absorbing we have Pio0 Puy Pi22 1 Here is the new transition matrix 1 0 12 0 12 O 0 0 0 0 0 0 0 2 13 0 13 0 13 O 0 0 0 0 0 0 3 0 13 0 0 0 13 O 0 0 13 O 0 4 13 0 0 0 13 0 13 O 0 0 0 0 5 0 14 0 14 0 14 0 14 0 0 0 0 p 6 0 0 13 13 0 0 0 13 0 0 0 7 0 oO oO 13 0 0 0 13 0 0 13 0 8 0 0 0 0 13 0 13 0 13 O 0 0 9 0 0 0 0 0 13 0 13 O 0 0 13 10 0 0 0 0 0 0 0 0 0 1 0 0 11 0 0 0 0 0 0 0 0 0 0 1 0 12 0 0 0 0 0 0 0 0 0 0 0 1 This is an absorbing Markov chain which is reducible We analyze it in a different way than we analyze an irreducible Markov chain Use the program absorbingm on this example 23 Analyzing an Absorbing Chain We now indicate how to analyze an absorbing Markov chain This analysis applies to the absorbing Markov chain we have just defined but also to other absorbing Markov chains We first label the states so that all the absorbing states appear first and then afterwards we put the transient states the states that we will eventually leave never to return The transition matrix then has the block matrix form I oO rn ag where J is an identity matrix 1s on the diagonal and 0s elsewhere and 0 zero is a matrix of zeros In this case I would be 3 x 3 R is 9 x 3 and Q is 9 x 9 The matrix Q describes the probabilities of motion among the transient states while the matrix R gives the probabilities of absorption in one step going from one of the transient states to one of the absorbing states in a single step In general Q would be square say m by m while R would be m by k and I would be k by k 231 The Fundamental Matrix N First suppose that we want to calculate the expected number of times the chain spends in transient state j starting in transient state 7 Let 7 be the total number times and let Ni ETj be the expected number of times It is convenient to write ny 10 471 470 79 47694719 4 where 7 is the number of times at the k transition Clearly 7 is a random variable that is either 1 if the chain is in transient state j on the k transition or 0 otherwise By 8 definition we say that T 0 ij 1 if i j but 0 otherwise Since these random variables assume only the values 0 and 1 we have Nij ETij ET 0 ij T 1 ij T 2 ij T 3 ij T 4 ij T 5 ij ET 0 ij ET 1 ij ET 2 ij ET 3 ij ET 4 ij ET 5 ij PT 0 ij 1 PT 1 ij 1 PT 2 ij 1 PT 3 ij 1 PT 4 ij 1 Q0 ij Q1 ij Q2 ij Q3 ij Q4 ij Q5 ij To summarize Nij Q0 ij Q1 ij Q2 ij Q3 ij In matrix form we have N Q0 Q1 Q2 Q3 I Q Q2 Q3 where the identity matrix I here has the same dimension m as Q Since Q is the submatrix corresponding to the transient states Qn 0 as n where here 0 is understood to be a matrix of zeros Multiplying by I Q on both sides we get a simple formula because there is cancellation on the righthand side In particular we get I Q N I so that multiplying on the left by the inverse I Q1 which can be shown to exist yields N I Q1 In MATLAB we would write N invI Q The matrix N I Q1 is called the fundamental matrix of an absorbing Markov chain We can be a little more careful and write Nn I Q Q2 Q3 Qn Then the cancellation yields I QNn I Qn1 We use the fact that Q is the part of P corresponding to the transient states so that Qn converges to a matrix of zeros as n Hence I QNn I as n Writing I QN I we see that both N and I Q are nonsingular and thus invertible yielding N I Q1 as stated above 232 Other Quantities of Interest M and B Other quantities of interest can be computed using the fundamental matrix N as we now show Let Mi be the expected number of steps until absorption starting in transient state i and let M be the m1 column vector with elements Mi The total number of steps until absorption is 9 the sum of the numbers of steps spent in each of the transient states before absorption always starting in transient state i Hence Mi Ni1 Ni2 Nim assuming as before that there are m transient states In matrix form M N w where w is a m 1 column vector of ones Let Bil be the probability of being absorbed in absorbing state l starting in transient state i Breaking up the overall probability into the sum of the probabilities of being absorbed in state l in each of the possible steps we get Bil Ril Q Ril Q2 Ril so that B R Q R Q2 R Q3 R I Q Q2 R N R Hence B NR where N is the fundamental matrix above In summary it is easy to compute the matrices N M and B describing the evolution of the absorbing Markov chain given the key model elements the matrices Q and R You should do the escaping Markov mouse example using MATLAB The MATLAB pro gram absorbingm does that for you The data and the program are on my web page on the computationaltools page For some related material see Sections 451 and 46 of Ross 233 Summary 1 There are two kinds of basic Markov chains those considered in so far in these notes 2 The first kind illustrated by the closed maze is an irreducible Markov chain It has a unique stationary distribution obtained by solving π πP We have considered a DTMC with a finite state space There are issues about what happens with an infinite state space With an infinite state space such as the nonnegative integers it is possible that the DTMC is transient or nullrecurrent instead of positive recurrent With a finite state space the irreducible DTMC is always positive recurrent in which case the stationary probability vector π is proper sums to 1 In the other two cases it is the 0 vector 3 The second kind illustrated by the open maze the escaping mouse is an absorbing Markov chain 4 You ask different questions for the two kinds of chains And so there are different tools and different answers 5 There are even more complicated Markov chains but we usually decompose them and analyze component chains of the two types above 6 Finite matrices can be applied only when the state space is finite However the main story and results go over to infinitestate Markov chains Indeed Ross discusses the more 10 general case from the beginning A simple example is a simple random walk in which you go to the right or left at each step each with probability 12 3 Classification of States See Section 43 of the textbook 31 Concepts 1 State j is accessible from state i if it is possible to get to j from i in some finite number of steps notation i j 2 States i and j communicate if both j is accessible from i and i is accessible from j notation i j 3 A subset A of states in the Markov chain is a communication class if every pair of states in the subset communicate 4 A communication class A of states in the Markov chain is closed if no state outside the class is accessible from a state in the class 5 A communication class A of states in the Markov chain is open if it is not closed ie if it is possible for the Markov chain to leave that communicating class 6 A Markov chain is irreducible if the entire chain is a single communicating class 7 A Markov chain is reducible if there are two or more communication classes in the chain ie if it is not irreducible 8 A Markov chain transition matrix P is in canonical form if the states are relabelled reordered so that the states within closed communication classes appear together first and then afterwards the states in open communicating classes appear together The recurrent states appear at the top the transient states appear below The states within a communication class appear next to each other 9 State j is a recurrent state if starting in state j the Markov chain returns to state j with probability 1 10 State j is a transient state if starting in state j the Markov chain returns to state j with probability 1 ie if the state is not recurrent 11 State j is a positiverecurrent state if the state is recurrent and if starting in state j the expected time to return to that state is finite 12 State j is a nullrecurrent state if the state is recurrent but starting in state j the expected time to return to state j is infinite 32 Canonical Form for a Probability Transition Matrix Find the canonical form of the following Markov chain transition matrix a P 01 00 00 09 00 00 04 00 00 06 03 03 00 04 00 03 00 00 07 00 00 07 00 00 03 11 Notice that the sets 14 and 25 are closed communicating classes containing recurrent states while 3 is an open communicating class containing a transient state So you should reorder the states according to the order 1 4253 The order 25143 would be OK too as would 52413 We put the recurrent states first and the transient states last We group the recurrent states together according to their communicating class Using the first order 1 4253 you get 01 09 00 00 00 03 07 00 00 00 P 00 00 04 06 00 00 00 07 03 00 03 04 03 00 00 Notice that the canonical form here has the structure P 0 0 P 0 PF 0 Ri Ro Q where P and P are 2 x 2 Markov chain transition matrices in their own right whereas R is the onestep transition probabilities from the single transient state to the i closed set In this case Q 0 is the 1 x 1 submatrix representing the transition probabilities among the transient states Here there is only a single transient state and the transition probability from that state to itself is 0 The chain leaves that transient state immediately never to return 4 Some Underlying Theory Optional Extra Stuff For those who have a good mathematics background and might be looking for a bit more 41 The limit for aperiodic irreducible finitestate DTMCs There is a nice simple limit for aperiodic irreducible finitestate Markov chains For any initial probability vector u u1Un the probability vector at time n is n ni PXn j uP Sui Ph il ie in matrix notation nm yp The key limiting result is Theorem 01 Jf P is the transition matrix of an aperiodic irreducible mstate Markov chain with transition matrix P then for any initial probability vector u mm yuP 37 as nro 12 where the limiting probability vector a is the unique stationary probability vector 1e the unique solution to the fixedpoint equation n wT7P or T So mPij for all 3 il satisfying the condition m Ss My 1 il 42 The Contraction Proof One way to prove the theorem is to consider the transition matrix P as an operator on the space of all probability vectors An operator on a space maps the space into itself If u is a probability vector then P maps wu into the probability vector uP corresponding to the probability vector starting with u and then taking one step according to P ie n uP So uPij for all j il We want the underlying space to be a complete metric space and the operator to be a contrac tion map Then we can apply the Banach fixedpoint theorem also called the BanachPicard fixedpoint theorem or the contraction fixedpoint theorem see the book Principles of Real Analysis by Walter Rudin for example Those pages are posted online The proof can be done in two steps step 1 In the first step you prove the some power of P has all positive entries using the assumption that P is an m xm transition matrix of an irreducible aperiodic Markov chain It can be shown that the minimum such power for an m xm matrix is less than or equal to m2m2 m see pages 5859 of E Seneta Nonnegative Matrices and Markov Chains second edition Springer New York 1981 The minimum such power is called the index of primitivity The worst case occurs when the transition probabilities satisfy P1 1 for 17m1 but then Pp 0 and Py 0 but Pn 0 for all 7 3 step 2 In the second step you assume that one column of P has all positive elements By step 1 that will necessarily occur after at most m 1 steps We then want to show that P regarded as an operator is a contraction map assuming that at least one column of P has all positive elements That implies that there exists a unique fixed point and that there is convergence to that fixed point at a geometric rate For any initial probability vector u u1Un duP7 cdur forall k for the metric d That yields a geometric rate of convergence In Markovchain theory we speak of geometric ergodicity Finding the appropriate norm on R 13 The space we will be looking at is a subset of R containing all probability measures and their differences We will use a distance defined via a standard norm That means that the distance is dx y z yl where is the norm We will consider a standard norm on R the question is which one Some norms do not work but one does Consider the transition matrix 095 001 001 001 001 001 095 001 001 001 001 001 p 095 001 001 001 001 001 001 095 001 001 001 001 001 095 001 001 001 001 001 095 001 001 001 001 and the two probability vectors u 13 13 13 0 0 0 and v 0001313 13 Then consider the probability vectors uP and vP We want to have uP vP elluol where 0 c 1 for some norm then the desired distance is du v u v Look at the two vectors we get when we apply P to u and v uP 095 001 001 001 001 001 and vP 001 095 001 001 001 001 There are three natural norms to consider on R the Igo lg and J norms Izoo max x n lIrll2 i i1 n lIelh Soleil 1 i1 It is not difficult to see that Juvlo 13 Juvl2 V69 V231 ljuvlr 2 2 and it is not difficult to see that JuP vPn 094 JuP vPl2 2 x 094 1329 luP vP 2x 094188 3 14 By this example we prove that the norms x and x2 do not work However it turns out that the norm z does work Theorem 02 Let P be anxn Markovchain transition matrix associated with an irreducible Markov chain Assume that P1 0 for alli 1in Then IJwP vPi 1euof1 Proof Note that n n n IJuP Pll S So ui Pig 0 Pil jl il i1 Now write PieQir and Pi Qi for j Fi for all i Then Q is a nonnegative n x n matrix with row sums 1 Now observe that n n n n n n n n Solo uP So ePigl Soule Qia So wile Qia SO So wiQig do wiQis jl il i1 i1 i1 j2 il i1 n n n n n douQin So iQial So So wQi7 So viQisl i1 i1 j2 il i1 n n n Sod ouiQi5 So viQisl jl il i1 n n n n SOS C fui vilQig S 5S ui v1 Qi5 1 lu alla 4 jl i1 i1 jl with the equality in the second line holding because the epsilon terms can be dropped out using n Soui vi 0 i1 because u and v are probability vectors summing to 1 15