3.6 Gambler's ruin

Conditioning on the first step, $P_a = pP_{a+1} + qP_{a-1}$ for $0 < a < N$, with $P_0 = 1$, $P_N = 0$. Try $P_a = \lambda^a$: $p\lambda^2 - \lambda + q = 0$, whose roots are $\lambda = 1$ and $\lambda = q/p$ (their product is $q/p$ and $\lambda = 1$ is a root since $p + q = 1$). For $p \ne q$ the roots are distinct, so $P_a = A + B\rho^a$. The boundary conditions give $A + B = 1$ and $A + B\rho^N = 0$, so $B = 1/(1 - \rho^N)$, $A = -\rho^N/(1 - \rho^N)$, which is (3.16). For $p = q$ the root 1 is double, $P_a = A + Ba$, and the boundary conditions give $1 - a/N$. The limits as $N \to \infty$: if $\rho < 1$, $\rho^N \to 0$; if $\rho > 1$, divide numerator and denominator by $\rho^N$ to get $(\rho^{a-N} - 1)/(\rho^{-N} - 1) \to 1$; if $\rho = 1$, $1 - a/N \to 1$.

$M_n = \rho^{X_n}$ is a martingale: $E[\rho^{X_{n+1}} \mid X_n] = \rho^{X_n}(p\rho + q\rho^{-1}) = \rho^{X_n}(q + p) = \rho^{X_n}$. The stopping time $\tau$ is a.s. finite: from any state, $N$ consecutive up-steps end the game, so $P(\tau > kN) \le (1 - p^N)^k \to 0$. The stopped process $M_{n\wedge\tau}$ is bounded (by $\max(1, \rho^N)$), so optional stopping applies: $\rho^a = E[\rho^{X_\tau}] = P_a\rho^0 + (1 - P_a)\rho^N$. Solve for $P_a$.∎

$D_a = 1 + pD_{a+1} + qD_{a-1}$, $D_0 = D_N = 0$. A particular solution of the inhomogeneous equation is $D_a = a/(q - p)$ (check: $1 + p(a+1)/(q-p) + q(a-1)/(q-p) = 1 + (a + p - q)/(q-p) = a/(q-p)$). The general solution adds $A + B\rho^a$; the boundary conditions give $A = -B$ and $B = N/((q-p)(1 - \rho^N))$, which yields (3.17). For $p = q$, a particular solution is $-a^2$, and $D_a = -a^2 + A + Ba$ with the boundary conditions gives $a(N - a)$. Alternatively, $X_n - (p - q)n$ is a martingale, and optional stopping (justified since $E\tau < \infty$) gives $(p-q)D_a = E[X_\tau] - a = N(1 - P_a) - a$.∎