Solutions to Homework Assignment - Stochastic Models And Simulation

Solutions to Homework Assignment 4 (4.13) Let P be the transition matrix of a Markov chain. Argue that if for some positive integer r, Pr has all positive entries, then so does Pn for all integers n ≥ r. Hint: Chapman-Kolmogorov equations. Solution: Let E denote the state space of the Markov chain. We are given that r P i,k > 0 for all i, k ∈ E. Note that this means that all states communicate (the chain is irreducible). In turn, this implies that, for any state j and for any n > r, there n−r must exist a state m ∈ E such that Pm,j > 0. The Chapman-Kolmogorov equations then give r n−r r P n X P i,k P n−r for all i ∈ E, k,j ≥ P i,m P m,j > 0, i,j = k∈E where the first inequality follows from the fact thati,mP>r 0 since it is given that all the entries of Pr are positive. (4.31) A certain town never has two sunny days in a row. Each day is classified as being either sunny, cloudy (but dry), or rainy. If it is sunny one day, then it is equally likely to be either cloudy or rainy the next day. If it is rainy or cloudy one day, then there is one chance in two that it will be the same the next day (i.e., w.p. 1/2), and if it changes, then it is equally likely to be either of the other two possibilities. In the long run, what proportion of days are sunny? What proportion are cloudy? Solution: Let the states be 0 for sunny, transition matrix is 0 0 0 1 1/4 P = 2 1/4 1 for cloudy and 2 for rainy. Then the 1 1/2 1/ 2 1/ 4 2 1/2 1/ 4 1/2 We now compute π by solving π = πP, π0 + π1 + π2 = 1 (remembering that the normalizing equation makes one of the other equations redundant): π0 = 1/4π1 + 1/4π2 π1 = 1/2π0 + 1/2π1 + 1/4π2 π0 + π1 + π2 = 1 The long run proportions are just the stationary probabilities. π0 = 1/5, π1 = π2 = 2/5. (4.42) Let A be a set of states, and the let Ac be the set of the remaining states. (a) What is the interpretation of πi Pi,j X X j∈Ac i∈A (b) What is the interpretation of πi Pi,j X X j∈A i∈Ac (c) Explain the identity X X j∈Ac πi Pi,j = X X πi Pi,j j∈A i∈Ac i∈A Solution: (a) This is the long-run proportion of transitions from a state in A to a state in Ac . (b) This is the long-run proportion of transitions from a state in Ac to a state in A. (c) Between any two transitions from A to Ac there must be a transition from Ac to A, and vice versa. Therefore, the long-run proportion of transitions between A and Ac must equal to the long-run transitions from Ac to A. (4.56) Suppose that on each play of the game a gambler either wins 1 with probability p or loses 1 with probability 1 − p. The gambler continues betting until she or he is either up n or down m. What is the probability that the gambler quits a winner? solution: This is the probability that a gambler starting with a fortune of m reaches n+m before reaching 0 in the gambler’s ruin problem. Then from the formula developed in class, 1 − (q/p)m , q := 1 − p. 1 − (q/p)n+m (4.58) In the gambler’s ruin problem, suppose the gambler’s fortune is presently i, and suppose that we know that the gambler’s fortune will eventually reach N (before it goes to 0). Given this information, show that the probability he wins the next gamble is p[1−(q/p)i+1 ] 1−(q/p)i i+1 2i , , if p 6= 1/2 if p = 1/2 Hint: The probability we want is P(Xn+1 = i + 1|Xn = i, lim m→∞ Xm = N ) = P(Xn+1 = i + 1, limm→∞ Xm = N |Xn = i) P(limm→∞ Xm = N |Xn = i) Solution: In general, when dealing with Markov chains, we want to have the “future” on one side of the probability by itself, and to condition on all the “past” and/or “present”. In this problem, the “future” is limm Xm . Then using the hint, we have P(Xn+1 = i + 1|Xn = i, lim m→∞ Xm = N ) = P(Xn+1 = i + 1, limm→∞ Xm = N |Xn = i) P(limm→∞ Xm = N |Xn = i) = P(limm→∞ Xm = N |Xn+1 = i + 1, Xn = i)P(Xn+1 = i + 1|Xn = i) P(limm→∞ Xm = N |Xn = i) = P(limm→∞ Xm = N |Xn+1 = i + 1)P(Xn+1 = i + 1|Xn = i) P(limm→∞ Xm = N |Xn = i) = Pi+1p , Pi (a) where in Equality (a) we used the Markov property. We next use the formulas for Pi+1 and Pi, which were developed in class (and also in the book: