For the random walk of Example 4.19 use the strong law of large numbers to give another proof that the Markov chain is transient when p = 1 2 .

Hint: Note that the state at time n can be written as

n i=1Yi where the Yis are independent and P{Yi = 1} = p = 1 − P{Yi =−1}. Argue that if p > 1 2 , then, by the strong law of large numbers,

n1 Yi →∞as n→∞and hence the initial state 0 can be visited only finitely often, and hence must be transient.

A similar argument holds when p < 1 2 .