# recurrence solution to gambler's ruin

From DeGroot 2.4.2, let $a_i$ be the conditional probability that the gambler wins all $k$ given gambler is at $i$.

$a_i = pa_{i+1} + (1 - p)a_{i-1}$

It's not clear from the text what steps are taken to solve for the general form $a_i$ (maybe Gaussian elimination). How do you solve the recurrence equation for $a_i$? If this can be found through the characteristic equation of a matrix $A$, then how do you construct $A$? As the problem is described, the first row has $a_0 = 0$, and last with $a_k = 1$.

-

We can rewrite the recurrence as $0=pa_{i+1} - a_i+(1-p)a_{i-1}$ and solve the characteristic equation $p\theta^{i+1}-\theta^i+(1-p)\theta^{i-1}=0.$ Ignoring $\theta=0$ we get $\theta=1,(1-p)/p.$ Thus, the probabilities satisfying the recurrence are of the form $a_i=c_1+c_2(\frac{1-p}{p})^i$ with $a_0=0$ and $a_k=1.$ Then we can solve the resulting system for $c_1,c_2.$ This link might help.

More explicitly: To find the roots of the characteristic equation of the recurrence, we solve $p\theta^2-\theta+(1-p)=0.$ We have two unique solutions $\theta_1=1,\theta_2=\frac{1-p}{p}.$ What the link tells us is that since these roots are distinct, the recurrence has general solution $a_i=c_1+c_2(\frac{1-p}{p})^i,$ where $c_1,c_2$ are constants. We can verify that $a_i=1^i=1$ is a solution, since $1=(p)(1)+(1-p)(1).$ Also, $$p(\frac{1-p}{p})^{i+1}+(1-p)(\frac{1-p}{p})^{i-1} = (\frac{1-p}{p})^i(1-p)+p(\frac{1-p}{p})^i=(\frac{1-p}{p})^i,$$ so indeed $(\frac{1-p}{p})^i$ is a solution.

Now, given $a_0=0$ and $a_k=1,$ we can solve for $c_1,c_2.$ First, $a_0 = 0$ implies $c_1+c_2(\frac{1-p}{p})^0=c_1+c_2=0$, or $c_1=-c_2.$ Second, $a_k=1$ implies $c_1-c_1(\frac{1-p}{p})^k=1,$ so $$c_1=\frac{1}{1-(\frac{1-p}{p})^k}=\frac{p^k}{p^k-(1-p)^k}.$$ We can see here that we should have $p\neq \frac{1}{2}.$

Thus, the solution should look something like: $$\frac{p^k}{p^k-(1-p)^k}-\frac{p^k}{p^k-(1-p)^k}(\frac{1}{1-p})^i.$$

I'm not sure I can help with a reference. To be honest, when I saw this in a class it was not well explained, and the text didn't help. Although maybe the wikipedia reference has something. Best of luck!

-
I am trying to follow your answer since my approach at this was with linear algebra, but my understanding of eigenvectors is not good.Please spell it out for me: I tried substituting the solution $(1 - p)/p$ into $a_i = pa_{i+1} + (1 - p)a_{i-1}$ and solve for $a_i$ but do not see how you go from there to $a_i=c_1+c_2(\frac{1-p}{p})^i$. I looked at the link, but don't quite get it yet. Suggestions on a good textbook would be appreciated. – T. Webster Aug 3 '12 at 21:00
Thanks for the extensive answer, very helpful, and has led me to ask a new, related question. – T. Webster Aug 4 '12 at 15:31

Hint: Rewrite our recurrence as $$pa_i+(1-p)a_i=pa_{i+1}+(1-p)a_{i-1}.$$ A little manipulation changes this to $$p(a_{i+1}-a_i)=(1-p)(a_i-a_{i-1}).$$ If $p \ne 0$, this can be rewritten as $$a_{i+1}-a_i=\frac{1-p}{p}(a_i-a_{i-1}).$$ Let $b_i=a_i-a_{i-1}$. Then the $b_i$ satisfy the simple recurrence $$b_{i+1}=\frac{1-p}{p}b_i.$$

-

This is best solved using generating functions. Let $f(x) = \sum_{k=0}^\infty a_k x^k$. Now multiply the recurrence equation with $x^k$ and perform the summation: $$f(x) - a_0 = \sum_{k=1}^\infty a_k x^k = \sum_{k=1}^\infty (p a_{k+1} + (1-p) a_{k-1}) x^k = \frac{p}{x} \sum_{k=1}^\infty a_{k+1} x^{k+1} + (1-p) x \sum_{k=1}^\infty a_{k-1}) x^{k-1} = \frac{p}{x} \left( f(x) - a_0 - a_1 x\right) + (1-p) x f(x)$$ Now solve for $f(x)$: $$f(x) = a_0 \frac{p-x}{(1-x)(1-(1-p)x)} + a_1 \frac{ p x}{(1-x)(1-(1-p)x)} \\ = \left(\frac{\left(a_1-a_0\right) p}{1-\frac{1-p}{p} x}+\frac{a_0 (1-p)-a_1 p}{ 1-x}\right) \frac{1}{1-2p} \\ = \frac{1}{1-2p} \sum_{n=0}^\infty \left( \left(a_1-a_0\right) \frac{(1-p)^n}{p^{n-1}} + \left(a_0 (1-p)-a_1 p\right) \right)x^n \\ = \sum_{n=0}^\infty \left( a_0 \frac{p^{n-1}(1-p) - (1-p)^{n}}{(1-2p) p^{n-1}} + a_1 \frac{(1-p)^n - p^n}{(1-2p)p^{n-1}} \right) x^n$$ where geometric series has been used. The case of $p =\frac{1}{2}$ requires taking a limit. Using L'Hospital's rule: $$a_k\left(\frac{1}{2}\right) = a_1 n + a_0 (1-n) = a_0 + (a_1-a_0) n$$

-