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