MATH 126A: Markov Chains and stopping times
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
MATH 126A: Markov Chains and stopping times
After the break, we will see that for irreducible and aperiodic Markov chains with invariant measure π, the expected return time to state i is E[T (i)] = π
1 . Some problems will already use this result below.
Exercise 1. Stopping times Let (Xn) be a Markov chain on {1, . . . , N}. Are the following random
variables stopping times?
(a) τ = min{n 2 1, Xn = i}.
SolutionIt is a stopping time . Indeed, if {τ = n}, then X0 , . . . , Xn − 1 cannot be equal to i and Xn = i . These do not depend on the future (any Xk for k > n) so τ is a stopping time .
(b) τ = min{n 2 3, Xn −2 = 1, Xn − 1 = 2, Xn = 1}.
SolutionIt is a stopping time . Indeed, if {τ = n}, then in the sequence X0 , . . . , Xn − 1 , the patter 1 - 2 - 1 has never appeared before (i. e ., it was never the case that Xk −2 = 1, Xk − 1 = 2, Xk = 1 for a k < n), and moreover it did appear at n, i. e . Xn −2 = 1, Xn − 1 = 2, Xn = 1 . These conditions do not depend on the future (any Xk for k > n) so τ is a stopping time .
(c) τ = min{n 2 1, Xn = 1 or Xn = 2 or Xn = 3}.
SolutionYes, stopping time - you will need a similar explanation as the first exercise to get full credit.
(d) τ = min{n 2 1, Xn −2 = 1 and Xn 
2}.
SolutionYes, stopping time, very similar writing needed as in the 2nd example .
(e) τ = min{n 2 1, Xn = 1 and Xn+2 
2}.
SolutionNo it’s not. To find out that τ = n, I need to make sure that Xn+2 = 2, which
induces a dependence on Xn+2, a state in the future .
(f) τ = max{n 2 1, Xn = i} for i a transient state.
SolutionNo it’s not. To find out that τ = n, I need to make sure that the chain never returns to i after time n, which requires knowledge of the chain in the future . Rigorously, {τ = n} = {Xn = i and Xk 
i Ak > n} .
Exercise 2. Lunch Menu
Assume you love having burgers for lunch. You would also eat pizza, and sometimes you may just take a bowl of lettuce. You want to keep a strict diet, and therefore have decided to make the following choices:
． If you had lettuce yesterday, you compensate today by taking a burger with probability
3/4, and pizza with probability 1/4.
． If you had a burger yesterday, you will eat lettuce with probability 1/2, and otherwise
choose burger or pizza with probability 1/4.
． If you had pizza yesterday, you will eat lettuce with probability 1/2, or burger with
probability 1/2.
Let Xn be your lunch at day n.
(a) Explain why (Xn) forms time-homogeneous Markov chain; Draw a diagram of the tran-
sitions and write the transition matrix.
(b) Compute the communication classes;
(c) Compute the period of the burger state.
(d) Compute the invariant measure
(e) What is the average time you wait between two burgers.
Solution
(a) Because the probabilities for each lunch on a given day only depend on the lunch taken
the previous day only, independently of lunches taken on days before the previous day and independently of which day of the week we are, the sequence (Xn) forms a time- homogeneous Markov chain. I leave it to you to draw the diagram. The transition matrix is, ordering the states as (L,B,P) for lettuce, burger and pizza:
L B P
1/4
1/4
0
(b) The chain is irreducible, since the transitions in the following loop all have strictly pos-
itive probability: L → P → B → L .
(c) The period is 1 because the probability to return in 1 step to burger is positive, so the period needs to divide 1 .
(d) To compute the invariant measure we look for π such that πP = π yielding the system:
．πL = 
(πB + πP )
．πB = 
πL + 
πB + 
πP
．(πP = 
(πL + πB )
Solving this system and enforcing the normalization condition πL + πB + πP = 1 we get
π = ( 1 7 1 ).
(e) The expected return time to a burger is the inverse of the invariant measure, E[TB] =
15/7, that is a little more than 2 days without a burger. With the same reasoning, you would find that in average, I would eat pizza every 5 days and salad every 3 days .
Exercise 3. Variations on random walks
Find communication classes and periods for the following random walks:
(a) the symmetric random walk on {0, 1, 2, 3} with periodic boundaries, Pij = 1/2 for |i-j| =
1, with at the boundaries P03 = P30 = 1/2.
(b) the symmetric random walk on {0, 1, 2, 3, 4} with periodic boundaries, Pij = 1/2 for
|i - j| = 1, with at the boundaries P04 = P40 = 1/2.
(c) the double-jump symmetric random walk on {0, 1, 2, 3, 4} with periodic boundaries, Pij = 1/2 for |i - j| = 2, with at the boundaries P03 = P41 = 1/2.
(d) the double-jump symmetric random walk on {0, 1, 2, 3, 4, 5} with periodic boundaries, Pij = 1/2 for |i - j| = 2, with at the boundaries P04 = P51 = 1/2.
Solution
(a) All transitions in the closed loop 0 → 1 → 2 → 3 → 0 have strictly positive probability
so the chain is irreducible . Denoting C0 = {0, 2} and C1 = {1, 3} we have probability 1 to go from C1 to C2 and probability 1 to go from C2 to C1 so the chain has period 2.
(b) All transitions in the closed loop 0 → 1 → 2 → 3 → 4 → 0 have strictly positive probability so the chain is irreducible . We have P0(2)0 > 0 (e .g. 0 → 1 → 0) and P0(5)0 > 0 (the closed loop used for irreducibility) so the period has to divide both 2 and 5, so it is 1 and the chain is aperiodic .
(c) All transitions in the closed loop 0 → 2 → 4 → 1 → 3 → 0 have strictly positive probability so the chain is irreducible . It is aperiodic because P0(2)0 > 0 (by e .g., 0 → 2 → 0) and P0(5)0 > 0 (the closed loop used for irreducibility) so the period has to divide both 2 and 5, so it is 1 and the chain is aperiodic .
(d) All transitions in the closed loop 0 → 2 → 4 → 0 have strictly positive probability so the communication class of 0 includes {0, 2, 4} . None of the elements in this class can reach {1, 3, 5} so the communication class of 0 is {0, 2, 4} . Moreover, {1, 3, 5} communicate with each other (with positive proba, 1 → 3 → 5 → 1) and they are all the states remaining outside of the communication class, so the chain has two communication classes: {0, 2, 4} and {1, 3, 5} . Both classes have period 1, because we can return to an element in 2 steps (going away and coming back immediately) or 3 steps (using the loops identified above) so both classes are aperiodic .
2023-05-12