I have $50$ dollars and I’m gambling on a series of coin flips. For each head I win $2$ dollars and for each tail I lose $1$ dollar. What’s the probability that I will run out of money?
Hint: Suppose we have $x$ dollars, then the probability of ruin satisfies the recursive equation
$$p(x+2) – p(x) = p(x) – p(x-1)$$
Find function $p(x)$.
Best Answer
As indicated, the following recursion holds $$p(n+2)-2p(n)+p(n-1)=0.$$ It only has a solutions on the form $r^n$, where $r$ is a root of the characteristic polynomial $$r^3-2r^1+r^0=0.$$ Finding the roots one has that a general solution of $p$ is given by $$p(n)=A1^n+B\left(\frac{-1+\sqrt{5}}{2}\right)^n+C\left(\frac{-1-\sqrt{5}}{2}\right)^n.$$ Since the underlying random walk has increments with positive mean, $p(n)\rightarrow 0$, as $n\rightarrow\infty$. This gives $A=C=0$. Further, $p(0)=1$, so $B=1$. In conclusion, $$p(n)=\left(\frac{\sqrt{5}-1}{2}\right)^n.$$ $p(50)$ is now easy to calculate.