# Gambler's ruin (calculating probabilities--hitting time)

Im meant to produce the transition matrix which I've already done (in the picture) and list the communication classes. But Im not sure how to find the probability regarding the hitting times (see question). Any suggestions?

Cheers.

-
This will be helpful: math.stackexchange.com/questions/47627/… –  Byron Schmuland Nov 7 '11 at 21:59

HINT:

Let $\pi_i = \mathbb{P}\left(\tau_N < \tau_0 \vert X_0 = i \right)$, then $\pi_0 = 0$, and $\pi_N = 1$. Conditioning on the first transition we get $\pi_i = \pi_{i-1} (1-p) + \pi_{i+1} p$. Now solve this recurrence equation.

-
Thanks, apprecaite it! –  John Southall Nov 8 '11 at 19:37

Keyword: martingale.

Fix $a\ne0$ and consider $M_n=a^{X_n}$ for every $n\geqslant0$. Then, as long as $1\leqslant M_n\leqslant N-1$, $M_{n+1}=M_n\cdot a$ with probability $p$ and $M_{n+1}=M_n\cdot a^{-1}$ with probability $q=1-p$. Assume that $pa+qa^{-1}=1$, then $(M_n)_{n\geqslant0}$ is a bounded martingale (called de Moivre's martingale) hence $\mathrm E(M_T)=\mathrm E(M_0)$ for every stopping time $T$. If $T=\inf\{\tau_0,\tau_N\}$, $M_T=a^N$ on $[\tau_N<\tau_0]$ and $M_T=1$ on $[\tau_0<\tau_N]$, hence $$\mathrm E(M_T)=\mathrm P(\tau_N<\tau_0)\cdot a^N+1-\mathrm P(\tau_N<\tau_0).$$ Since $M_0=a^i$, this yields $\mathrm P(\tau_N<\tau_0)=\dfrac{1-a^i}{1-a^N}$ if $a\ne1$. It remains to compute $a$. Since $pa^2-a+q=0$, $a=q/p$ will do for every $p\ne1/2$, in which case one gets $$\mathrm P(\tau_N<\tau_0\mid X_0=i)=\dfrac{1-(q/p)^i}{1-(q/p)^N}.$$ If $p=1/2$, either one takes the limit when $p\to1/2$ of the formula above or one notes that, in this case, $M_n=X_n$ defines a martingale, to which one can apply the stopping time theorem. Both methods yield $$\mathrm P(\tau_N<\tau_0\mid X_0=i)=\frac{i}N.$$

-
The other, more general, method is to solve the linear system described by @Sasha. –  Did Nov 8 '11 at 6:34
Thanks, I've tried learning both yours and sasha's method, it was helpful. Most appreciated! –  John Southall Nov 8 '11 at 19:37
@DidierPiau Thanks for the new technique! (+1) –  Sasha Nov 8 '11 at 20:08
@Sasha, new? If only! No, as they say, je suis venu trop tard dans un monde trop vieux... –  Did Nov 8 '11 at 21:34
@DidierPiau Sorry, I was not clear. I meant the technique is new to me. –  Sasha Nov 8 '11 at 21:47