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)$.
On
Here's an alternative approach (which appears on the surface to be very similar to the recurrence + characteristic polynomial approach) using Martingales.
Let $S_i=X_1+\dots+X_i$ be your money at time $i$; here the $X_j$'s are random variables for the profit (or loss) you make at time $j$. We will find $c$ such that $c^{S_i}$ is a martingale, and then use the Optional Stopping Theorem. Note we need
$$\mathbb{E}[c^{S_{i+1}}|M_1,\dots,M_i]=c^{S_i}\implies \mathbb{E}[c^{X_i}]=\frac{1}{2}c^2+\frac{1}{2}c^{-1}=1\implies c^3-2c+1=0$$ We will take the root $c=\frac{\sqrt{5}-1}{2}$ as it is positive and strictly less than 1, thus for stopping time $T$ representing the first time we hit $0$, $|M_{\min(T,t)}|\leq 1$ for all $t$ is strictly bounded by a finite constant, and thus we can apply Optional Stopping Theorem:
$$\mathbb{E}[M_T]=p\cdot c^0+(1-p)\cdot 0 = M_0=c^{50}\implies p=c^{50}$$
We only need find the probability $r$ that you lose 1 dollar since the probability that you lose 50 dollars is $r^{50}$ since you must lose 1 dollar 50 times. We can write $$ r = 0.5 + 0.5r^3 $$
since half the time we lose on the first flip, and half the time we win on the first flip, thereby increasing our 1 dollar bankroll to 3 dollars, at which point our risk of ruin becomes $r^3$ since we must now lose 1 dollar 3 times. This has solutions $r = (\sqrt{5}-1)/2$ and $r = 1$. We obviously want the first of these since we have the advantage, and our opponent's $r$ is 1. So $$ P(lose \: 50) = \left(\frac{\sqrt{5}-1}{2}\right)^{50} $$ or about $3.55e^-11$.