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.
 A: 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.
$$
A: 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.
