EECS 126: Probability and Random Processes
Problem Set 4
1. Reducible Markov Chain
Consider the following Markov chain, for α, β, p, q ∈ (0, 1).
0 1 2 3 4 5
1 − α
α
β
1 − β
1/2
1/2
1/2
1/2
p
1 − p
q
1 − q
(a) Find all the recurrent and transient classes.
(b) Given that we start in state 2, what is the probability that we will reach state 0 before
state 5?
(c) What are all of the possible stationary distributions of this chain? Hint: Consider the
recurrent classes.
(d) Suppose we start in the initial distribution π0 :=
0 0 γ 1 − γ 0 0
for some
γ ∈ [0, 1]. Does the distribution of the chain converge, and if so, to what?
2. Finite Random Walk
Assume 0 < p < 1. Find the stationary distribution. Hint: Let q = 1 − p and ρ =
p
q
, but be
careful when ρ = 1.
3. Convergence in Probability
Let (Xn)∞
n=1, be a sequence of i.i.d. random variables distributed uniformly in [−1, 1]. Show
that the following sequences (Yn)∞
n=1 converge in probability to some limit.
(a) Yn =
Qn
i=1 Xi
.
(b) Yn = max{X1, X2, . . . , Xn}.
(c) Yn = (X2
1 + · · · + X2
n
)/n.
4. Gambling Game
Let’s play a game. You stake a positive initial amount of money w0. You toss a fair coin. If it
is heads you earn an amount equal to three times your stake, so you quadruple your wealth.
1
