Solving recursion (Gambler's ruin)

Question

Let $M_{i}$ denote the mean number of games until the gambler either goes broke or reaches a fortune of $N$, given that he starts with $i = 0,1,\ldots,N$.

I have shown that $M_{0} = M_{N} = 0$ and $M_{i} = 1 + pM_{i+1} + qM_{i-1}$ for $i=1,\ldots,N-1$

I want to solve these equations to obtain $$M_{i} = i(N-i)$$if $p=1/2$ or $$M_{i} = \frac{i}{q-p} - \frac{N}{q-p}\cdot\frac{1 - (q/p)^{i}}{1- (q/p)^{N}}$$ if $p \neq 1/2$.

I've tried verifying by direct substitution, but I don't think I'm substituting correctly. How can I solve these difference equations to show the desired result?

Answer 1

The recurrence relation

$$pM_{i+1} - m_i +qM_{i-1} = -1 \qquad\qquad (1)$$

is a non-homogeneous, second-order, linear recurrence relation with constant coefficients ($p,-1,q$) and can be solved by finding its "characteristic equation" as described here or here or in most texts on discrete mathematics.

Initially, consider the homogeneous relation

$$pM_{i+1} - m_i +qM_{i-1} = 0. \qquad\qquad (2)$$

The characteristic equation is $pr^2 - r + q = 0$ giving roots: $\;r=1 \text{ or } q/p$.

$$\\$$

Case $p=q$:

We have a double root $r=1$ so the general solution to $(2)$ is

$$M_i = A + Bi\qquad\qquad (3)$$

The particular solution for $(1)$ would normally have form $M_i=C$ because RHS $(1)$ is constant, but in view of $(3)$ we instead try $M_i = Ci^2$ and substitute this into $(1)$ to give

$$-1 = pC(i+1)^2 - Ci^2 + qC(i-1)^2 = C \qquad\text{using $p=q=1/2$}.$$

So our particular solution is $M_i=-i^2$ and our general solution to $(1)$ is $M_i = A+Bi-i^2$.

$M_0 = 0 \implies 0=A.$

$M_N = 0 \implies 0 =BN-N^2\;$ so $\;B=N$.

So the solution to $(1)$ is

$$M_i = Ni-i^2.$$

$$\\$$

Case $p\neq q$:

We have distinct roots $r=1,\; q/p\;$ so the general solution to $(2)$ is

$$M_i = A + B\left(q/p\right)^i \qquad\qquad (4)$$

Here we try the particular solution $M_i = Ci$ and substitute this into $(1)$ to give

$$-1 = pC(i+1) - Ci + qC(i-1) = C(p-q).$$

Therefore, $\; C=1/(q-p)\;$ and our general solution to $(1)$ is $M_i = A + B\left(q/p\right)^i + \dfrac{i}{q-p}$.

$M_0 = 0 \implies 0=A + B\;$ so $\;A=-B.$

$M_N = 0 \implies 0 = -B + B\left(q/p\right)^N + \dfrac{N}{q-p}\;$ so $\;B=\dfrac{N}{q-p}\cdot \dfrac{1}{1-\left(q/p\right)^N}$.

So the solution to $(1)$ is

\begin{align} M_i &= - \dfrac{N}{q-p}\cdot \dfrac{1}{1-\left(q/p\right)^N} + \dfrac{N}{q-p}\cdot \dfrac{\left(q/p\right)^i}{1-\left(q/p\right)^N} + \dfrac{i}{q-p} \\ & \\ &= \dfrac{i}{q-p} - \dfrac{N}{q-p}\cdot \dfrac{1-\left(q/p\right)^i}{1-\left(q/p\right)^N}. \end{align}

Answer 2

Let $X_0=i$ and $\{X_n\}$ be iid with $\mathbb P(X_1=1)=1-\mathbb P(X_1=-1)=p$. Let $$S_n = \sum_{k=0}^n X_k $$ be the gambler's wealth at time $n$ and $$\tau=\inf\{n: S_n\in\{0,N\}\} $$ be the time until he stops. Define $$Z_n = \left(\frac qp\right)^{S_n}. $$ Then \begin{align} \mathbb E[Z_{n+1}\mid \mathcal F_n] &= \mathbb E\left[\left(\frac qp\right)^{S_n+X_{n+1}}\mid\mathcal F_n \right]\\ &= \left(\frac qp\right)^{S_n} + \left(\frac qp\right)^{-1}\mathbb P(X_{n+1}=-1) + \left(\frac qp\right)^1\mathbb P(X_{n+1}=1)\\ &= Z_n + \left(\frac pq\right)q + \left(\frac qp\right)p\\ &= Z_n + p + q\\ &= Z_n, \end{align} so that $Z_n$ is a martingale. Then by the optional stopping theorem we have $$\mathbb E[Z_\tau] = \mathbb E[Z_0] = \left(\frac qp\right)^i. $$ It follows that \begin{align}\mathbb E[Z_\tau] &= \left(\frac qp\right)^0\mathbb P(Z_\tau=0) + \left(\frac qp\right)^N\mathbb P(Z_\tau=N)\\ &= \mathbb P(Z_\tau=0) + \left(\frac qp\right)^N (1-\mathbb P(Z_\tau=0) )\\ &= \left(\frac qp\right)^i,\end{align} and so \begin{align} \mathbb P(Z_\tau=0) &= \frac{\left(\frac qp\right)^i - \left(\frac qp\right)^N}{1-\left(\frac qp\right)^N},\\ \mathbb P(Z_\tau=N) &= \frac{1 - \left(\frac qp\right)^i}{1-\left(\frac qp\right)^N}.\\ \end{align} Therefore the gambler's expected total winnings are \begin{align} \mathbb E\left[\sum_{n=1}^\tau X_n \right] &= \mathbb E[S_\tau] - S_0\\ &= \mathbb E[S_\tau\mid Z_\tau=0]\mathbb P(Z_\tau=0) + \mathbb E[S_\tau\mid Z_\tau=N]\mathbb P(Z_\tau=N) - i\\ &= N\left(\frac{1 - \left(\frac qp\right)^i}{1-\left(\frac qp\right)^N}\right)-i \end{align} By Wald's identity, we have $$\mathbb E\left[\sum_{n=1}^\tau X_n \right] = \mathbb E[\tau]\mathbb E[X_1], $$ and so $$\mathbb E[\tau] = \frac1{p-q}\left[N\left(\frac{1 - \left(\frac qp\right)^i}{1-\left(\frac qp\right)^N}\right)-i\right], $$ when $p\ne q$.