CS 547 Lecture 34: Markov Chains

1 CS 547 Lecture 34: Markov ChainsDaniel MyersState Transition ModelsA Markov chain is a model consisting of a group ofstatesand specifiedtransitionsbetween the states. Oldertexts on queueing theory prefer to derive most of their results using Markov models, as opposed to the meanvalue analysis approach we ve used for most of this course. Understanding Markov Chains will allow us toderive some new results that would be difficult to get using MVA of Markov ChainsA Markov chain can have a finite or infinite number of states. In adiscrete time Markov chain (DTMC) eachstate change takes place at a fixed decision point and the time between changes is constant. In acontinuoustime Markov chain (CTMC), changes can happen at any you might expect, finite and discrete models are easier to analyze, so we ll use a DTMC for our examplesin this Lecture .

2 Queueing models rely on CTMCs with infinite states, which we ll cover in the next Markovian PropertySuppose we have a DTMC. LetXnbe a random variable denoting the state the model is in at time thing we might be interested in reasoning about is the probability of being in a given state, say statej,at time stepn. In general, this probability could depend on the entire time history of the chain ; that is, theprobability of being in statejat timenis influenced by the state the model was in at every previous timestep. Suppose the model was in stateiat time stepn 1 and some statestat each time step 0 t < n probability we re interested in could be written asP[Xn=j|Xn 1=iandXn 2=sn 2and.. X0=s0]TheMarkovian Propertysays that transitions in a Markov chain depend on only the current state, and noton any history of previous states.

3 That is, state transitions in a Markov model [Xn=j|Xn 1=iandXn 2=sn 2and.. X0=s0] =P[Xn=j|Xn 1=i]For any pair of statesiandj, letPijdenote theone-step transition probabilityof moving from stateitostatej, independent of the time step or previous history. Specifiying the one-step transition probabilities isa compact way of describing a Markov Example ModelConsider a model with just two states, called state 0 and state 1, and transition probabilities given by P00= 1 p P01=p1 P10=q P11= 1 qSo, the probability of moving from state 0 to state 1 isp, and the probability of moving from 1 to 0 isq, s convenient to collect the transition probabilities into a (1 ppq1 q)Now, let (n)be a vector denoting the probability of being in each state afterntransitions. Given a startingdistribution, (0), we can use total probability to calculate the probability to calculate the chance of beingin each state after one transition the model is state 0 after one transition, there are two ways it could have gotten there: by starting instate 0, then staying in state 0 with probability 1 p, or by starting in state 1 and transitioning to 0 withprobabilityq.

4 Similar arguments apply to being in state 1. (1)0= (0)0(1 p) + (0)1q (1)1= (0)0p+ (0)1(1 q)Writing these equation in matrix form,( (1)0 (1)1)=( (0)0 (0)1)(1 ppq1 q) (1)= (0)PUsing row vectors for the values is somewhat atypical (most linear algebra books use column vectors andplace the matrix on the left), but is necessary because of how we defined the Limiting ProbabilitiesIf we know (0)we can easily calculate any value of (n), just by repeatedly multiplying byP. (n)= (0)PnThe matrix elementsPnijrepresent the probability of being in statejafterntransitions, given that we startedin happens asn ? It isn t obvious, but it can be shown using induction that the matrixPwillconverge to a stable matrix with a single value in each column, and identical Pn=(qp+qpp+qqp+qpp+q)This is a surprising result! It turns out at least for this simple example that the probability of beingin state 0 converges to a constant value ofqp+q, regardless of the starting state.

5 Similarly, the probabilityof being in state 1 converges topp+q. Also note that these two probabilities sum to 1, so this is an = limn (n)be a vector denoting thelimiting probabilityof being in each state. If we want tocalculate , we can simply multiply the matrixPby itself until the values converge, then read the valuesfrom any one of the ,Performance Modeling and Design of Computer Systems, Stationary EquationsIf we don t want to perform repeated matrix multiplication, there is another way of obtaining the limitingprobabilities. The vector = ( 0, 1, .. , N 1) is astationary distributionfor the Markov chain if it satisfies = PN 1 j=0 j= 1It s possible to prove theorems demonstrating that the solution to the stationary equations will also be thelimiting s necessary to add the requirement that the elements of sum to 1 to obtain a solution.

6 Without theextra constraint, the system = Pis underdetermined the equations are not linearly independent andhas infinitely many of Existence and ConvergenceAt several points thus far, we ve taken limits without guaranteeing that the limit actually existed. Inparticular, there s no obvious reason whyPnshould converge asn , or that the long-run probability ofbeing in each state should be fact, there are a set of good properties for Markov Chains . Any model satisfying these good propertieswill have a limiting distribution, which can be calculated by iteratively multiplying thePmatrix, or bysolving the stationary equations. For now, we ll assume that all of our Chains have these properties, andwe ll look at them in more detail in a future