1.2 A die is rolled repeatedly. Determine which of the following processes are Markov 1. The largest number Xn shown up to the n-th roll. 2. The number Nn of sixes in n rolls 3. At time n the time On since the most recent six. 4. At time n the time Bn until the next six1.1 Consider the process Xn+1 = axn + 6Wn, n = 0, 1, 2, ... where a, b are given constants. 1. Assume that (Wn)n is a sequence of independent ru's that are also independent of Xo. Prove that (Xn)n is a Markov process. 2. Suppose the random process (Wn)n is such that Wn+1 = fWn + Un where f is a constant and Uo, U1, ... is a sequence of independent ru's that are also independent of Xo, Wo. Define the sequence (Zn)n where Zn = (Xn, Wn). Prove that (Zn)n is a Markov process. Solution 1. We have P(Xn+1 E BIXn = Xn, . . ., Xo = To) = P(aXn + bWn E BIXn = In, . .., Xo = X0) (1) = P(axn + bWn E BIXn = Xn, . .., Xo = 0). (2) Now the variables on the conditioning part of the above expression relate only to the basic rv's Xo, Wo, . .., Wn-1 which are all independent of Wn, and thus we can drop the conditioning, thus having P(axn + bWn E BIXn = In, . . ., Xo = X0) = P(axn + bWn E B) (3) We now repeat the derivation for the quantity P(Xn+1 ( BIXn = Xn) = P(aXn + bWn E BIXn = In) (4) = P(axn + bWn E BIXn = En) (5) = P(axn + bWn E B), (6) where the last equation is due to the independence of Xn and Wn.2. We have P(Zn+l E B|Zn = zn, . . ., Zo = 20) P((Xn+1, Wn+1) E BIXn = In, . .., Xo = To, Wn = Wn, . .., Wo = Wo) (7 ) = P((aXn + bWn, fWn + Un) E BIXn = In, . .., Xo = To, Wn = Wn, . .., Wo = Wo) (8 = P((axn + bun, fun + Un) E BIXn = In, . .., Xo = To, Wn = Wn, . .., Wo = Wo) (9) = P((axn + bun, fun + Un) E B) (10) where the last equation is due to the fact that the variables on the conditioning part of the above expression relate only to the rv's Xo, Wo, ..., Wn-1 and Uo, ..., Un-1 and thus only on the basic rv's Xo, Wo and Uo, ..., Un-1, which are all independent of Un. Repeating the same derivation for the quantity P(Zn+1 E B|Zn = Zn) we get P( Zn+ 1 E B| Zn = Zn) = P((Xn+1, Wn+1) E BIXn = In, Wn = Wn) (11) = P((axn + bun, fun + Un) E BIXn = In, Wn = Wn) (12) = P((arn + bun, fun + Un) E B), (13) where the last equation is due to the independence of Un and the random variables Xn and Wn (which are functions of Xo, Wo and Uo, . . ., Un-1).1.2 A die is rolled repeatedly. Determine which of the following processes are Markov 1. The largest number Xn shown up to the n-th roll. 2. The number Nn of sixes in n rolls 3. At time n the time On since the most recent six. 4. At time n the time Bn until the next six Solution Let (Zn)n be the iid sequence of rv's denoting the face of the die at the n-th role (where Zn E {1, 2, 3, 4, 5, 6}). 1. Xn can be represented through a recursive equation of the form Xn+1 = max{ Xn, Znti } n = 1, 2, ... and X1 = Z1. Using a technique similar to the one presented in the previous problem it is straightforward to show that (Xn)n is Markov. 2. Similarly, Nn can be expressed as Nn+1 = Nn + 1(6} (Zin+1) n = 1,2, ... and N1 = 1(6) (Z1). Using a technique similar to the one presented in the previous problem it is straightforward to show that (Nn)n is Markov. 3. Cn can be expressed as Cn+1 = (Cn + 1)1(1,2,3,4,5} (Zin+1) and C1 = 0 (by convention) so for the same reason as above it is Markov.4. Bn can be expressed as Bn = min{k > n : Zk = 6} - n. To see the evolution of Bn consider a realization of (Zn)n as follows: Z1 = 1, Z2 = 3, Z3 = 5, Z4 - 6, Z5 = 2, Z6 = 1, Z7 = 3, Zg = 5, Zg = 6, Z10 = 1, ... Then the corresponding realization for (Bn)n is B1 = 3, B2 = 2, B3 = 1, B4 = 5, B5 = 4, B6 = 3, B7 - 2, Bg = 1, . .. As can be seen (Bn)n is a decreasing sequence up until it reaches the value Bn = 1 which is equivalent to Zn+1 = 6. Thus we can write Bn - 1, Bn > 2 But1 = min {k > n : Zk =6} - n, Bn =14> Zn+1 =6 We now have P(Bn+1 = m|Bn = bn, . . ., B1 = b1) = 1, bn 2 2 and m = bn - 1 10, bn _ 2 and m # bn - 1 (1) = P(Bn+1 = m|Bn = bn), (2)while for the case where bn = 1 we have P(Bn+1 = m|Bn = 1, . .., B1 = b1) = P(min {k > n +1 : Zk =6} = m|Bn = 1, . .., B1 = b1). (3) Clearly the event min {k > n + 1 : Zx = 6} = m depends only on rv's Zn+2, Zn+3, ... while the conditioning implies only information about Zn+1 = 6 and the value of previous Zi's. Since the sequence of (Zn)n consists of iid rv's we have P(Bn+1 = m|Bn = 1, ..., B1 = b1) = P(min {k > n + 1 : Zk = 6} = m) ( 4 ) = P(Bn+1 = m). (5) Thus in all cases corresponding to the value of on the Markov property is satisfied