Markov Chains (I)

MASSACHUSETTS INSTITUTE OF TECHNOLOGY 6.436J/15.085J Lecture 21 Fall 2018 MARKOV CHAINS Contents 1. Homogeneous Finite State Markov Chain 2. Stationary Distribution 3. Recurrent and Transient States 1 INTRODUCTION d Recall a model we Pconsidered earlier: random walk. We have Xn = Ber(p), i.i.d. Then Sn = 1jn Xj was defined to be a simple random walk. One of its key property is that the distribution of Sn+1 conditioned on the state Sn = x at n is independent from the past history, namely Sm , m ≤ n − 1. To see this formally note that P(Sn+1 = y|Sn = x, Sn−1 = z1 , . . . , S1 = zn−1 ) P(Xn+1 = y − x, Sn = x, Sn−1 = z1 , . . . , S1 = zn−1 ) = P(Sn = x, Sn−1 = z1 , . . . , S1 = zn−1 ) P(Xn+1 = y − x)P(Sn = x, Sn−1 = z1 , . . . , S1 = zn−1 ) = P(Sn = x, Sn−1 = z1 , . . . , S1 = zn−1 ) = P(Xn+1 = y − x), where the second equality follows from the independence assumption for the sequence Xn , n ≥ 1. A similar derivation gives P(Sn+1 = y|Sn = x) = P(Xn+1 = y − x) and we get the required equality: P(Sn+1 = y|Sn = x, Sn−1 = z1 , . . . , S1 = zn−1 ) = P(Sn+1 = y|Sn = x). 1 Definition 1. A discrete time stochastic process (Xn , n ≥ 1) is defined to be a Markov chain if it takes values in some countable set X , and for every x1 , x2 , . . . , xn ∈ X it satisfies the property P(Xn = xn |Xn−1 = xn−1 , Xn−2 = xn−2 , . . . , X1 = x1 ) = P(Xn = xn |Xn−1 = xn−1 ) The elements of X are called states. We say that the Markov chain is in state s ∈ X at time n if Xn = s. Mostly for now we will consider the case when X is finite. In this case we call (Xn , n ≥ 1) a finite state Markov chain and, without the loss of generality, we will assume that X = {1, 2, . . . , N }. Let us establish some properties of Markov chains. Proposition 1. Given a Markov chain Xn , n ≥ 1. 1. For every collection of states s, x1 , x2 , . . . , xn−1 and every m P(Xn+m = s|Xn−1 = xn−1 , . . . , X1 = x1 ) = P(Xn+m = s|Xn−1 = xn−1 ). 2. For every collection of states x1 , x2 , . . . , xn and k = 1, 2 . . . , n P(Xn = xn , Xn−1 = xn−1 , . . . , X1 = x1 |Xk = xk ) = P(Xn = xn , Xn−1 = xn−1 , . . . , Xk+1 = xk+1 |Xk = xk )× × P(Xk−1 = xk−1 , . . . X1 = x1 |Xk = xk ). Proof. Exercise. 2 EXAMPLES We already have an example of a Markov chain - random walk. Consider now the following example (Exercise 2, Section 6.1 [1]). Suppose we roll a die repeatedly and Xn is the number of 6-s we have seen so far. Then Xn is a Markov chain and P(Xn = x + 1|Xn−1 = x) = 1/6, P(Xn = 6 x, x + 1. x|Xn−1 = x) = 5/6 and P(Xn = y|Xn−1 = x) = 0 for all y = Note, that we can think of Xn as a random walk, where the transition to the 2 right occurs with probability 1/6 and the transition to the same state with the probability 5/6. Now let Xn be the largest of the six possible outcomes observed up to time n. Then Xn is again a Markov chain. What are its transition probabilities? For our next example consider the following model of an inventory process. The inventory can hold finish goods up to capacity C ∈ N. Every month n there is some current inventory level In and a certain fixed amount of product x ∈ N is produced, as long as limit is not reached, namely In + x ≤ C. If In + x > C, than just enough C − In is produced to reach the capacity. Every month there is a random demand Dn , n ≥ 1, which we assume is i.i.d. If the current inventory level is at least as large as the demand, then the full demand is satisfied. Otherwise as much of the demand is satisfied as possible, bringing the inventory level down to zero. Let In be the inventory level in month n. Then In is a Markov chain. Note In+1 = min((In − Dn )+ + x, C). Specifically, the probability distribution of In+1 given In = i, is independent from the values Im , m ≤ n − 1. In is a Markov chain taking values in 0, 1, . . . , C. 3 HOMOGENEOUS FINITE STATE MARKOV CHAINS We say that the Markov chain Xn is homogeneous if P(Xn+1 = y|Xn = x) = P(X2 = y|X1 = x) for all n. Observe that all of our examples are homogeneous Markov chains. For a homogenous Markov chain Xn we can specify transition probabilities P(Xn+1 = y|Xn = x) by a sequence of values px,y = P(Xn+1 = y|Xn = x). For the case of finite state Markov chain, say the state space is {1, 2, . . . , N }. Then the transition probabilities are pi,j , 1 ≤ i, j ≤ N . We call P = (pi,j ) the transition P matrix of Xn . The transition matrix P has the following obvious property j pi,j = 1 for all i. Any non-negative matrix with such property is called stochastic matrix, for obvious reason. 3 Observe that P(Xn+2 = j|Xn = i) X = P(Xn+2 = j|Xn+1 = k, Xn = i)P(Xn+1 = k|Xn = i) 1kN = X P(Xn+2 = j|Xn+1 = k)P(Xn+1 = k|Xn = i) 1kN = X pk,j pi,k . 1kN This means that the matrix P 2 gives the two-step transition probabilities of the underlying Markov chain. Namely, the (i, j)-th entry of P 2 , which we denote by (2) pi,j is precisely P(Xn+2 = j|Xn = i). This observation is not hard to extend to the general case: for every r ≥ 1, P r is the transition matrix of r-steps of the Markov chain. One of our goals is understanding the long-term dynamics of P r as r → ∞. We will see that for a broad class of Markov chains the following (r) property holds: the limit limr!1 pi,j exists and depends on j only. Namely, the starting state i is irrelevant, as far as the limit is concerned. This property is called mixing and is a very important property of Markov chains. Let ej denote the j-th N -dimensional column vector. Namely ej has j-th coordinate equal to one, and all the other coordinates equal to zero. We also let e denote the N -dimensional column vector consisting of ones. Suppose X0 = i, for some state i ∈ {1, . . . , N }. Then the probability vector of Xn can be written as eTi P n in vector form. Suppose at time zero, the state of the chain is random and is given by some probability vector µ. Namely P(X0 = i) = µi , i = 1, 2, . . . , N . Then the probability vector of Xn is precisely µT P n in vector form. 4 STATIONARY DISTRIBUTION Consider the following simple Markov chain on states 1, 2: p1,1 = p1,2 = 1/2, p2,1 = 1, p2,2 = 0. Suppose we start at random at time zero with the following probability distribution µ: µ1 = P(X0 = 1) = 2/3, µ2 = P(X0 = 2) = 1/3. What is the probability distribution of X1 ? We have P(X1 = 1) = (1/2)P(X0 = 1) + P(X0 = 2) = (1/2)(2/3) + (1/3) = 2/3. From this we find P(X1 = 2) = 1 − P(X1 = 1) = 1/3. We see that the probability distribution of X0 and X1 are identical. The same applies to every n. 4 Definition 2. A probability vector ˇ = (ˇi ), 1 ≤ i ≤ N is defined to be a stationary distribution if P(Xn = i) = ˇi for all times n ≥ 1 and states i = 1, . . . , N , conditioned on P(X0 = i) = ˇi , 1 ≤ i ≤ N . In this case we also say that the Markov chain Xn is in steady-state. Repeating the derivation above for the case of general Markov chains, it is not hard to see that P the vector ˇ is stationary iff it satisfies the following properties: ˇi ≥ 0, i ˇi = 1 and X pk,i ˇk , ∀i. ˇi = 1kN In vector form this can be written as ˇ T = ˇ T P, (1) where wT denotes the (row) transpose of a column vector w. One of the fundamental properties of finite state Markov chains is that a stationary distribution always exists. Theorem 1. Given a finite state Markov chain with transition matrix P , there exists at least one stationary distribution ˇ. Namely the system of equation P (1) has at least one solution satisfying ˇ ≥ 0, i ˇi = 1. Proof. There are many proofs of this fundamental results. One possibility is to use Brower’s Fixed Point Theorem. Later on we will give another probabilistic proof which provides important intuition about the meaning of ˇi . For now let us give a quick proof, but one that relies on linear programming (LP). If you are not familiar with linear programming theory, you can simply skip the proof. Consider the following LP problem in variables ˇ1 , . . . , ˇN . X max ˇi 1iN Subject to: P T ˇ − ˇ = 0, ˇ ≥ 0. 5 Note that a stationary vector ˇ exists iff this LP has an unbounded optimal solution. Indeed, if ˇ is a stationary vector, then it clearly is a feasible P solution to this LP. Note that α ˇ is also a solution for every α > 0. Since α 1iN ˇi = α , then we can obtain a feasible solution as large as we want. On the other hand, suppose this LP has an Punbounded objective value.PIn particular, there exists a solution x satisfying i xi > 0. Taking ˇi = xi / i xi we obtain a stationary distribution. Now using LP duality theory, this LP has an unbounded solution iff the dual solution is infeasible. The dual solution is X min 0yi 1iN Subject to: P y − y ≥ e. Let us show that indeed this dual LP problem is infeasible. Suppose the contrary is true. Namely, there exists y satisfying P y − y ≥ e. Take any Psuch y and   find k , 1 ≤ k ≤ N such that yk = maxi yi . Observe that i pk ,i yi ≤ P i pk  ,i yk  = yk  < 1 + yk  , since the rows of P sum to one. Thus the constraint P y − y ≥ e is violated in the k  -th row. We conclude that the dual problem is indeed infeasible. Thus the primal LP problem is unbounded and the stationary distribution exists. As we mentioned above, stationary distribution ˇ is not necessarily unique, though in many special cases it is. The uniqueness can be verified byP checking T T whether the following system has a unique solution. ˇ = ˇ P, j ˇj = 1, ˇj ≥ 0. Example.[6.6 from [2]] An absent-minded professor has two umbrellas, used when commuting from home to work and back. If it rains and umbrella is available, the professor takes it. If umbrella is not available, the professor gets wet. If it does not rain the professor does not take the umbrella. It rains on a given commute with probability p, independently for all days. What is the steady-state probability that the professor will get wet on a given day? We model the process as a Markov chain with states j = 0, 1, 2. The state j means the location where the professor is currently in has j umbrellas. Then the corresponding transition probabilities are p0,2 = 1, p2,1 = p, p1,2 = p, p1,1 = 1 − p, p2,0 = 1 − p. The corresponding equations for ˇj , j = 0, 1, 2 are then ˇ0 = ˇ2 (1−p), ˇ1 = (1−p)ˇ1 +pˇ2 , ˇ2 = ˇ0 +pˇ1 . From the second equation ˇ1 = ˇ2 . Combining with the first equation and with the fact ˇ0 + ˇ1 + ˇ2 = 1, 6 1−p 1 we obtain ˇ1 = ˇ2 = 3−p , ˇ0 = 3−p . The steady-state probability that the professor gets wet is the probability of being in state zero times probability that it rains on this day. Namely it is P(wet) = (1−p)p 3−p . 5 CLASSIFICATION OF STATES. RECURRENT AND TRANSIENT STATES Given a finite state homogeneous Markov chain with transition matrix P , construct a directed graph as follows: the nodes are i = 1, 2, . . . , N . Put edges (i, j) for every pair of states such that pi,j > 0. Given two states i, j suppose there is a directed path from i to j. We say that i communicates with j and write i → j. By allowing paths of lengths zero, we obtain that i communicates with itself (i → i), although it is possible that starting from X0 = i, after time n = 0 the chain never returns to i. What is the probabilistic interpretation of this? It means there is a positive probability of getting to state j starting from i. P (n) Formally n pi,j > 0. Suppose, there is a path from i to j, but not from j to i. This means that if the chain starting from i, got to j, then it will never return to i again. Since, there is a positive chance of going from i to j, intuitively, this will happen with probability one. Thus with probability one we will never return to i. We would like to formalize this intuition. Definition 3. A state i is called transient if there exists a state j such that i → j, but j 9 i. Otherwise i is called recurrent. We write i ↔ j if states i and j communicate with each other. Observe that if i ↔ j then j ↔ i. Also, if i ↔ j and j ↔ k then i ↔ k. Finally, observe that if i is recurrent then it must be the case that i ↔ i. Indeed, consider any state j (possibly i itself) such that pi,j > 0. If there is a path from j to i, then there is a path from i to i as well and the assertion is established. Otherwise, we find that i → j, but j 6→ i, and therefore i is not recurrent. We conclude that ↔ is an equivalency relationship on the set of recurrent states, and we can partition all the recurrent states into equivalency classes R1 , R2 , . . . , Rr . The entire states space {1, 2, . . . , N } then can be partitioned as T ∪ R1 ∪ · · · ∪ Rr , where T is the (possibly empty) set of transient states. 7 References [1] G. R. Grimmett and D. R. Stirzaker, Probability and Random Processes, Oxford University Press, 3rd edition, 2001. [2] D. P. Bertsekas and J. N. Tsitsiklis, Introduction to probability, Athena Scientific, 2002. 8