Chapter 5 Discrete Markov process Suppose we have a sequence of random variables, {X0 , X1 , . . .} = {Xn } , which is also n=0 called a stochastic process. In this chapter, we study a commonly used stochastic process: Markov process. 5.1 Denition The following are some preparation before the denition of Markov process. 1. State space (S): all the possible values of {Xn } . n=0 2. State: i S is called State i. 3. Xn = i: means that the process is in state i at time n. For example, for simple random walk introduced in Section 4.3. The sample space is S = {0, 1, 2, } or S = all possible integers. 63 Denition 5.1. If the stochastic process {Xn } satises the following conditions: n=0 (1) the state space S is discrete or countable; (2) P (Xn+1 = j|Xn = i, Xn1 = in1 , . . . , X1 = i1 , X0 = i0 ) = P (Xn+1 = j|Xn = i) = P (X1 = j|X0 = i) (denoted by pij ), then {Xn } is called Markov process. n=0 The rst equality is often referred as \"Markov property\". The intuitive understanding for this property is that given the current information Xn , the future Xn+1 does not depend on the history (X0 , X1 , . . . , Xn1 ). The second equality further requires the Markov property is time homogeneous. That is, the conditional probability does not depend on time n. A very useful tool in studying the Markov process is one-step transition matrix: P . (We use double underlines to emphasize P is a matrix.) One-step transition matrix Let pij = P (X1 = j|X0 = i), which is the one-step transition probability from state i to state j for i S and j S. If we put all the transition probabilities into a matrix, we get the one-step transition matrix as follows: P = pij i,jS . The one-step transition matrix is often called a stochastic matrix since it has the following properties. Proposition 5.1. (1) pij 0; (2) jS pij = 1, i.e., the summation of the elements in each row of P is 1. 64 We now give some examples to illustrate the above concepts and denitions. Example 5.1. (Random walk on a circle) Consider a random walk on a circle with three positions: 0, 1, 2. At each step, the particle can move clockwise 1 unit with probability p or counter-clockwise 1 unit with probability q = 1 p. Let Xn be the position of the particle after n steps. Then 1. state space S = {0, 1, 2}; 2. intuitively, {Xn } is a Markov process since given Xn , Xn+1 does not depend on n=0 X1 , . . . , Xn1 . Further the conditional probability of Xn+1 given Xn does not depend on n; 3. the transition probabilities are p00 = 0, p01 = p, p02 = q; p10 = q, p11 = 0, p12 = p; p20 = p, p21 = q, p02 = 0; 4. therefore the one-step transition matrix is 0 p q P = q 0 p . p q 0 We can easily verify that the properties in Proposition 5.1 are satised by the above one-step transition matrix. Example 5.2. (Random walk with two absorbing boundaries 0 and k) Consider a gambler who, at each play of game, either wins $1 with probability p or loses $1 with probability 65 q = 1 p. Suppose the gambler will quit playing either when he goes bankrupt or he attains a fortune of $k. Let Xn be the fortune of the gambler after n games, n = 0, 1, 2, . . . . Then 1. state space S = {0, 1, 2, . . . , k}; 2. intuitively, {Xn } is a Markov process since given Xn , Xn+1 does not depend on n=0 X1 , . . . , Xn1 . Further the conditional probability of Xn+1 given Xn does not depend on n; 3. the transition probabilities are pi,i+1 = p, pi,i1 = q, pi,j = 0 if |i j| 2, i = 1, . . . , k 1; p0,0 = 1, p0,j = 0 if j = 0; pk,k = 1, pk,j = 0 if j = k. 4. therefore the one-step transition matrix for 1 0 q 0 P = 0 q 0 0 k = 3 is 0 0 p 0 . 0 p 0 1 We can easily verify that the properties in Proposition 5.1 are satised by the above one-step transition matrix. Here state 0 and state k are called absorbing boundaries. Example 5.3. (Forecasting the weather) Suppose that chance of rain tomorrow depends on previous weather conditions only thorough whether or not it is raining today and not on past weather conditions. Suppose that if it rains today, then it will rain tomorrow with probability ; and if it does not rain today, then it will rain tomorrow with probability . 66 For n = 0, 1, 2, . . . , let 1 Xn = 0 Then if it does not rain on the nth day . otherwise 1. state space S = {0, 1}; 2. intuitively, {Xn } is a Markov process since given Xn , Xn+1 does not depend on n=0 X1 , . . . , Xn1 . Further the conditional probability of Xn+1 given Xn does not depend on n; 3. the one-step transition matrix is P = 1 1 . Example 5.4. (Random walk with a reecting boundary) Consider a gambler who, at each play of game, either win $1 with probability p or loses $1 with probability q = 1 p. Further suppose the gambler will automatically get $ 1 in the next game from Casino if his fortune is currently 0. Let Xn be the fortune of the gambler after n games, n = 0, 1, 2, . . . . Then 1. state space S = {0, 1, 2, . . .}=all non-negative integers; 2. intuitively, {Xn } is a Markov process since given Xn , Xn+1 does not depend on n=0 X1 , . . . , Xn1 . Further the conditional probability of Xn+1 given Xn does not depend on n; 67 3. the transition probabilities are pi,i+1 = p, pi,i1 = q, pi,j = 0 if |i j| 2, i 1; p0,1 = 1, p0,j = 0 if j = 1. 4. therefore one-step transition matrix (an innite 0 1 0 0 q 0 p 0 P = 0 q 0 p 0 0 q 0 . . . . . . . . . . . . dimensional matrix) is . . . . Final remark: One-step transition matrix is the basis for investigating Markov process. Almost all the properties of Markov process start from the one-step transition matrix. Therefore writing down it correctly is the rst and most important step in the application of Markov process. 5.2 Chapman-Kolmogorov equations In this section, we mainly try to answer two questions: 1. suppose that one-step transition probabilities are given or obtained from other sources, how to nd the n-step transition probabilities? 2. suppose that one-step transition probabilities and the distribution of X0 are given, how to nd the distribution of Xn ? We rst dene the n-step transition probabilities and n-step transition matrix. n-step transition matrix 68 (n) Let pij = P (Xn = j|X0 = i) = P (Xn+m = j|Xm = i), which is the n-step transition probability from state i to state j for i S and j S. If we put all the n-step transition probabilities into a matrix, we get the n-step transition matrix as follows: (n) P (n) = pij i,jS . For example, consider the random walk on the circle with 3 state: 0, 1, and, 2 in Example 5.1. The two-step transition matrix (2) p 00 P (2) = p(2) 10 (2) p20 has the following form: (2) (2) p01 p02 (2) (2) p11 p12 . (2) (2) p21 p22 The next theorem tells us how to calculate the n-step transition matrix from one-step transition matrix. Theorem 5.1. Chapman-Kolmogorov equations: pointwise form: (n+m) pij (n) (m) = pik pkj ; kS Therefore P (n) = P n . 69 matrix form: P (n+m) = P (n) P (m) . Example 5.5. (Example 5.1 continued). For the random walk on the circle with 3 positions, the two-step transition matrix is P (2) = . Next we consider the distribution of Xn based on the distribution of X0 and one-step transition matrix. Let (0) i = P (X0 = i), i S and (0) (0) = i iS . Here (0) is a row vector and is called the distribution vector of X0 . Further let (n) i = P (Xn = i), i S and (n) (n) = i iS . Note that (n) is also a row vector and is called the distribution vector of Xn . The next theorem tells how to calculate (n) based on (0) and P . 70 Theorem 5.2. Given the distribution vector (0) of X0 and the one-step transition matrix P , we have (n) = (0) P (n) = (0) P n . Example 5.6. (Example 5.1 and Example 5.5 continued) For the random walk on the circle with 3 positions, suppose P (X0 = 0) = 0.25, P (X0 = 1) = 0.5, and P (X0 = 2) = 0.25. Find P (X2 = 0), P (X2 = 1), and P (X2 = 2). 71 5.3 Classication of states In this section, we investigate the properties of the states in S. Let i,i = returning to state i, given that th and Ti,i be the waiting time for the rst event i,i . Classication of state i Denition 5.2. According to the classication of Ti,i , we have the following classication of state i: 1. state i is called transient if Ti,i is improper, i.e., fi,i = P (Ti,i < ) < 1; 2. state i is called null recurrent if Ti,i is null proper, i.e., fi,i = P (Ti,i < ) = 1 and E(Ti,i ) = ; 3. state i is called positive recurrent if Ti,i is short proper, i.e., fi,i = P (Ti,i < ) = 1 and E(Ti,i ) < . In both cases 2 and 3, we call state i is recurrent. Number of times to visit state i Let Vi,i be the number of times that we visit state i, given that the process starts with state i. Then n P (Vi,i = n) = fi,i (1 fi,i ), n = 0, 1, 2, . . . .(Why?) Then E(Vi,i ) = n=0 n P (Vi,i = n) = n nfi,i (1 n=0 fi,i ) = n=1 n nfi,i (1 fi,i ) = fi,i n=1 n1 nfi,i (1 fi,i ) = fi,i E Geo(1 fi,i ) = The above results have several important applications. 72 fi,i . 1 fi,i 1. \"Transient\" means that fi,i < 1 and hence implies that E(Vi,i ) < . That is, if state i is transient, the process will visit state i nite number of times, given the process starts with state i. Sooner or later, the process will leave this state alone forever. 2. \"Recurrent\" means that fi,i = 1 and hence implies that E(Vi,i ) = . That is, if state i is recurrent, the process will visit the state i innite number of times, given the process starts with state i. Further, let In,i 1 visit state i at nth step, given the process starts with state i = . 0 o.w. Then Vi,i = n=1 In,i . (n) Note that E(In,i ) = P (In,i = 1) = pi,i . Then we have (n) E(Vi,i ) = pi,i . n=1 Combining the above results together, we have Theorem 5.3. (n) 1. State i is transient i E(Vi,i ) = n=1 pi,i < ; 2. State i is recurrent i E(Vi,i ) = n=1 pi,i = . (n) Period of state i Another important concept related to the state is called the period. It helps us to nd E(Ti,i ). Denition 5.3. The period of state i is dened to be (n) d = gcd{n|pi,i > 0, n 1}, 73 gcd means \"greatest common divisor\". We call state i aperiodic if state i has period 1; otherwise, we call state i periodic. (n) The following theorem helps us to nd E(Ti,i ) based on pi,i and d. Theorem 5.4. 1. if d = 1, E(Ti,i ) = 1 (n) limn pi,i 2. if d 2, E(Ti,i ) = ; d (dn) limn pi,i . Theorems 5.3 and Theorem 5.4 are mathematically elegant and beautiful. They are very useful if the n-step transition probabilities are very easy to nd. In the next section, we introduce some tools to help us determine the type and period of each state in state space S only based on P . We need: \"class\" and \"stationary distribution\". 5.4 Class in Markov process We need some concepts before the introduction of \"class\". Accessible: we say state j is accessible from state i (denoted by i j), if there exists (n) n 0, such that pij > 0. That is, it is possible to move from state i to j. Communicate: we say that state i and state j can communicate if i j and j i. That is, it is possible to move from state i to state j and also possible to move from state j to state i. The following are three basic properties of \"communication\". 1. i i; 74 2. if i j, then j i; 3. if i j and j k, then i k. Denition 5.4. (Class) Communication divides the state space S into several disjoint classes/sets. States can only communicate with the states in the same class. Denition 5.5. (Irreducible) If a Markov process only has one class, then it is called irreducible. In this situation, all states can communicate with each other. For example, the random walk on the circle with 3 positions only have one class since 0 1 2 0. Therefore it is irreducible. Example 5.7. Suppose a Markov process has the state space S = {0, 1, 2, 3, 4} and the 75 one-step transition matrix is given as 0.5 0.5 0 0 0 0.5 0.5 0 0 0 P = 0 0 0.5 0.5 0 0 0 0.5 0.5 0 0.25 0.25 0 0 0.5 Find the classes of this Markov process. 76 . The following theorem tells us why we need to introduce the concept of \"class\". Theorem 5.5. The states in the same class share similar properties: 1. all states in the same class should be (all) positive recurrent, or null recurrent or transient at the same time; 2. all states have the same period; 3. if there exists a state i in the class such that pii > 0, then all states in the same class have period 1 (aperiodic). The above theorem tells us that we only need to investigate the properties of one state in one class. Next, we introduce two dierent classes: open class and closed class, which will help us to classify the states. Open class. A class (denoted by C) is called a open class if there exists i C and j C / such that pij > 0. Closed class. A class (denoted by C) is called a closed class if for all i C and j C, / we have pij = 0. Based on the denitions of open class and closed class, we have that it is possible for the process to leave the open class and enter another class; but it is not possible for the process to leave the closed class. Further note that once the process leaves an open class it never returns to that open class. The following are two properties regarding the states in open class and closed class. Theorem 5.6. 1. (Open class) All states in open class are transient. 2. (Closed class with nite number of states) If the closed class has nite number of states, all the states in this class are positive recurrent. 77 Example 5.8. (Continue of Example 5.7) Determine which classes are closed and which classes are open; classify each state in the state space S. 78 5.5 Stationary distribution Up to Section 5.4, we can classify all the states in open class and we can also classify the states in closed class with nite number of states. How do we classify the states in a closed class with innite number of states? Also how do we nd the E(Ti,i ) from the one-step transition matrix? These two questions can be answered from the stationary distribution. Stationary distribution (). Denition 5.6. The vector is called a stationary distribution of a Markov process if the elements of satisfy: = P, i = 1, and iS i 0 for all i in S. The following are some comments regarding the stationary distribution. 1. may not exist and also may not be unique. 2. Understanding of the stationary distribution: if exists and is unique, the i is called the long-run proportion of the process in state i. 79 The following theorem gives the reason for introducing the stationary distribution. Theorem 5.7. If a Markov process is irreducible, then exists i all the states are positive recurrent; in this case, is unique and E(Ti,i ) = 1 i for i S. Example 5.9. Suppose a Markov process has the state space S = {0, 1} and the one-step transition matrix is given as P = 1/3 2/3 1/3 2/3 . Find the stationary distribution of the process; compute E(T0,0 ) and E(T1,1 ). 80 In a special case, it is easy to nd the stationary distribution. Denition 5.7. A one-step transition matrix P = pij iS pij = jS i,jS is called doubly stochastic if pij = 1. A Markov process with the doubly stochastic transition matrix has the following stationary distribution. Theorem 5.8. If the one-step transition matrix of Markov process is doubly stochastic and the Markov process is irreducible, then the stationary distribution of the Markov process is given as i = 1/M, for i S, where M is the number of states in S. Example 5.10. (Example 5.1 continued) Find the stationary distribution of the random walk on the circle with 3 positions; compute E(Ti,i ), i = 0, 1, 2. 81 5.6 Absorption probability In this section, we mainly cover what we can do if the Markov process is not irreducible. We use an example to cover all the material that we would like to cover. Example 5.11. Consider a Markov process with state space S = {0, 1, 2, 3, 4, 5, 6} and transition matrix P = 0 0 0 1/2 0 1/2 0 0 0 1/4 1/4 1/4 0 0 1/4 1/2 0 0 0 0 1/2 0 . 0 0 0 0 2/3 0 1/3 1/2 0 0 1/2 0 0 0 0 0 0 0 5/6 0 1/6 0 1/3 1/3 0 1/3 0 1. Find the classes of this process. Determine which are closed and which are open. 2. Rewrite the matrix in simple form. (Include the labels for the re-ordering of the state space.) 3. Find the period and stationary distribution for each closed class. 4. Find the absorption probability from the open class states to closed class. 5. Suppose X0 = 0, determine the stationary distribution. 6. Suppose X0 = 1, determine the stationary distribution. 7. Find the expectations of the waiting times for the states in open class leaving the open class. 82 83 84 5.7 Practice problems 1. Suppose that coin 1 has probability 0.7 of coming up heads, and coin 2 has probability 0.6 of coming up heads. If the coin ipped today comes up heads, then we select coin 1 to ip tomorrow, and if it comes up tails, then we select coin 2 to ip tomorrow. If the coin initially ipped is equally likely to be coin 1 and coin 2, then what is the probability that the coin ipped on the third day after the initial ip is coin 1? 2. Let P be the one-step transition matrix of a Markov process. Argue that if for some positive integer r, P (r) has all positive entries, then so does P (n) , for all n > r. 3. Specify the classes of the following Markov process and determine whether they are transient or recurrent, 0 0 0 0 0.5 0.5 0 0 0 P 1 = 0.5 0 0.5 , P 2 = 0.5 0.5 0 0.5 0.5 0 0 0 1 1 0.5 0 0.5 0 0 0.25 0.5 0.25 0 0 1 , P = 0.5 0 0.5 0 0 3 0 0 0 0 0.5 0.5 0 0 0 0 0.5 0.5 4. Prove that if the number of states in Markov process is M, and if state j can be reached from state i, then it can be reached in M steps or less. 5. Suppose numbers are randomly selected with replacement from the set {1, 2}. Let Yn be the sum of numbers in the rst n independent selections, n = 1, 2, . . . . Find the proportion that Yn be a multiple of 3 in the sequence {Yn } . n=1 6. Each morning an individual leaves his house and goes for a run. He is equally likely to leave either from his front or back door. Upon leaving the house, he chooses a 85 . pair of running shoes (or goes running barefoot if there are no shoes at the door from which he departed). On his return he is equally likely to enter and leave his running shoes, either by the front or back door. (a) If he owns a total of k = 2 pairs of running shoes, what proportion of the time does he run barefooted? (b) If he owns a total of k = 3 pairs of running shoes, what proportion of the time does he run barefooted? 7. A professor continually gives exam to his students. He can give three possible types of exams, and his class is graded as either having done well or badly. Let pi denote the probability that the class does well on a type i exam, and suppose that p1 = 0.3, p2 = 0.6, and p3 = 0.9. If the class does well on an exam, then the next exam is equally likely to be any of the three types. If the class does badly, then the next exam is always type 1. What proportion of the exams are type i, i = 1, 2, 3. 8. Consider a Markov process with state space S = {0, 1, . . . , 7} and transition matrix 1/2 1/4 0 0 0 0 1/4 0 1/4 0 0 0 0 0 3/4 0 0 0 1/3 0 0 0 0 2/3 0 1/5 1/5 1/5 1/5 1/5 0 0 1/6 0 0 0 1/3 1/6 1/6 1/6 0 0 0 0 0 1 0 0 1/4 0 0 0 0 0 3/4 0 0 0 2/3 0 0 0 0 1/3 (a) Determine the classes of this process, and organize the matrix into simple form. Which states are transient? Determine the period of each class. 86 (b) Find the stationary distribution corresponding to each closed class, and write down the general form of all stationary distributions for this process. (c) Find the absorption probability from each transient state into each closed class. (d) If X0 = 0, describe the long-run behavior of this process. Do the same for X0 = 3. 9. Suppose we have a revised random walk with a boundary at 0. That is, the walk takes values only in the nonnegative integers S + = {0, 1, 2, 3, ...} and moves in the following way: if Xn = 0 then at the next step it jumps to state 1 with probability 1. Otherwise it moves like an ordinary random walk, that is, if Xn = j for j = 0 then it jumps to the right with probability p and to the left with probability q = 1 p. Let i,i =\"returning to i, given that the process starts from i\"; Ti,i be the waiting time for the 1st i,i ; Vi,i be the number of times visiting state i, given that the process starts from state i. Our interest: classication of all states. (a) We rst answer the above question in the random walk setup. We start with 0,0 . i. Classify T0,0 . If we want to study all the states, we need to repeat the above steps innity number of times. (b) Next we answer the above question in the Markov process setup. Let Xn be the position of the walk after n steps. i. Is {Xn } a Markov process? n=0 ii. How many classes do we have for this process? 87 iii. Find the stationary distribution and determine when the stationary distribution exists. The above procedure can only tell you which one is positive recurrent, but can not tell you which one is null recurrent or transient. What is the best way for answering the question that we are interested? 10. Joe owns r = 2 umbrellas which he uses as needed going back and forth between his home and oce. If it is raining in the morning when he leaves his home, he takes an umbrella with him (provided there is one available). Similarly, if it is raining in the evening when he leaves the oce to go home, he will take an umbrella with him (again if there is one available). If it is not raining, he never takes an umbrella. Assume that, independent of the past, it rains in the morning (evening) with probability 0 < p < 1. The question of interest is the long-run proportion of time Joe gets wet. Note that Joe will get wet if it starts raining at his current location (home or oce) and all of his umbrellas are at the opposite location. (a) let Xn be the number of umbrellas in the current location. Write down the state space S and determine the transition matrix. Hint: Joes current location will be constantly switching between home and oce. (b) Find the stationary distribution and the long-run proportion that the number of umbrella at the current location is 0. (c) What proportion of time does Joe get wet? 88