Show whether the MC for the gambler's ruin problem (sec 4.5.1) is time reversable. If yes, why? If not why? Prove! Derive the expected time that the MC will spend in state 0 after many steps (in the limit).

Derive the proportion of time that the MC will spend in state 0 after many steps (in the limit).

Assume that N is infinity. Show whether the state 0 is null recurrent, positive recurrent or transient.

Here is some general information about the problem that may assist you:

If we let Xn denote the player's fortune at time n, then the process {Xn, n =

0, 1, 2, . . .} is a Markov chain with transition probabilities

P00 = PNN = 1,

Pi,i+1 = p = 1 ? Pi,i?1, i = 1, 2, . . . , N ? 1

Markov Chains 221

This Markov chain has three classes, namely, {0}, {1, 2, . . . , N ?1}, and {N}; the first

and third class being recurrent and the second transient. Since each transient state is

visited only finitely often, it follows that, after some finite amount of time, the gambler

will either attain his goal of N or go broke.

Let Pi , i = 0, 1, . . . , N, denote the probability that, starting with i, the gambler's

fortune will eventually reach N. By conditioning on the outcome of the initial play of

the game we obtain

\f