How to derive recurrences for the mean time in the Gambler's Ruin Problem?

Question

$$\begin{array}{c}{\text { For the gambler's ruin model let } M_{i} \text { denote the mean number }} \\ {\text {of games that must be played until the gambler either goes broke or reaches a }} \\ {\text { fortune of } N, \text { given that he starts with } i, i=0,1, \ldots, N . \text { I know that } M_{i} \text { satisfies }} \\ {M_{0}=M_{N}=0 ; \quad M_{i}=1+p M_{i+1}+q M_{i-1}, \quad i=1, \ldots, N-1}\end{array} $$

Now I must derive the following equations $$\begin{aligned} M_{i} &=i(N-i), \quad \text { if } p=\frac{1}{2} \\ &=\frac{i}{q-p}-\frac{N}{q-p} \frac{1-(q / p)^{i}}{1-(q / p)^{N}}, \quad \text { if } p \neq \frac{1}{2} \end{aligned}$$

Here is my work

We know $M_i=pM_i+qM_i$ since $p+q=1$

Now

$M_2-M_1=\frac{q}{p}(M_1-M_0)-\frac{1}{p}$

$M_3-M_2=\frac{q}{p}(M_2-M_1)-\frac{1}{p} = \frac{q}{p}(\frac{q}{p}(M_1-M_0)-\frac{1}{p})-\frac{1}{p} = (\frac{q}{p})^2M_1-\frac{q}{p}\frac{1}{p}-\frac{1}{p}$

The next one gives

$M_4-M_3=\frac{q}{p}(M_3-M_2)-\frac{1}{p} =(\frac{q}{p})^3M_1-(\frac{q}{p})^2\frac{1}{p}-\frac{q}{p}-\frac{1}{p}$

I then tried adding up all of the recurrences from 1 to N but this did not give me the correct answer.

Does anyone know how to derive these equations that are given?

Answer 1

The problem is one of solving a linear inhomogeneous recurrence with constant coefficients. The usual method of solution is more or less guess-and-check, but we happen to know just the right way to guess-and-check for this class of equations (constant coefficients and polynomial inhomogeneity).

We solve the homogeneous recurrence (in this case where the $1$ is replaced by $0$) by positing solutions of the form $\lambda^i$ and adding these together in a linear combination. When we do this we have to find the roots of the so-called characteristic polynomial, in this case $px^2-x+q$, which is obtained by substituting in $x^i$ into the homogeneous equation and dividing both sides by the common factor $x^{i-1}$. In this case the characteristic polynomial is quadratic; if it has distinct roots, then the general homogeneous solution is $c_1 \lambda_1^i + c_2 \lambda_2^i$, otherwise it is $c_1 \lambda^i + c_2 i \lambda^i$. Both of these cases turn out to come up in this problem, depending on what $p$ is.

For the particular solution, we assume that the solution is a polynomial, basically because $x_i \mapsto px_{i+1}+qx_{i-1}-x_i$ maps polynomial sequences to polynomial sequences. We identify it by guessing it has an appropriate small degree and then checking whether our guess was correct. Again in this problem the degree that works turns out to depend on $p$.

Then we add the homogeneous solution to the particular solution and use the boundary conditions to identify the unknown coefficients in the homogeneous solution.

This "homogeneous plus linear" trick is standard for solving linear recursions as well as linear differential equations and linear algebraic systems.

Answer 2

You proved that $M_{i+1}-M_i=\frac{q}p(M_i-M_{i-1})-\frac1p$. Applying this relation enough times, you get that $$ M_{k+1}-M_k=(q/p)^k(M_1-M_0)-\sum_{i=0}^{k-1}(q^{i}/p^{i+1}) $$ for each $1\le k\le N-1$. Provided $p\neq 1/2$, this simplifies to $$ M_{k+1}-M_k=(q/p)^kM_1-\frac{1-(q/p)^k}{p-q}\tag{$*$} $$ Adding these all up, you get $$ M_N-M_1=M_1\sum_{k=1}^N(q/p)^k-\sum_{k=1}^N\frac{1-(q/p)^k}{p-q} $$ Now apply a couple of geometric series formulae, and $M_N=0$, and solve for $M_1$. Then, use $(*)$ again to compute $M_n$ for each particular $n$ via the telescope $(M_n-M_{n-1})+(M_{n-1}-M_{n-2})+\dots+(M_1-M_0)$.

When $p=1/2$, you instead have $$ \sum_{i=0}^{k-1}(q^{i}/p^{i+1})=\sum_{i=0}^{k-1}(1/2)=k/2, $$ so $k/2$ should replace the last summation in $(*)$. I leave it to you to figure out the details of this case. You will need a closed from expression for $1+2+\dots+n$.