Gambler's Ruin

September 01, 2022

As a professional gambler, it seems natural to start with gambler’s ruin.

As a professional gambler, I’m extremly senstive about the house edge. That’s why I mostly just play fair games like flipping a coin. After a coin is flipped, I win 1 dollar for head (H) and lose 1 dollar for tail (T). I play until I got broke or the casino got broke (ambitious plan). As ridiculous it seems, I almost always got broke, even though it’s a “fair” game.

Let’s consider a more general version of the problem. Two gamblers Alice and Bob flip a biased coin with probability $p$ to get a head and $q = 1-p$ to get a tail. Alice wins 1 dollar from Bob if head is flipped and loses 1 dollar to Bob if tail is flipped. Alice has $a$ dollars and Bob has $b = n-a$ dollars to start with. The game ends when one party owns all $n$ dollars.

Let $A_i$ be the probability that Alice gets all $n$ dollars starting with $i$ dollars, and $B_i$ be the probability that Bob gets all $n$ dollars starting with $i$ dollars. We have $A_n = B_n = 1$ and $A_0=B_0=0$ .

Suppose Alice has $i$ dollars now and they flip a coin. If a head comes, Alice will own $i+1$ dollars and the probability that she wins in the end is exactly $A_{i+1}$ ; similarly, the probability that she wins is $A_{i-1}$ if a tail is flipped. Thus, we have

A_i = p A_{i+1} + q A_{i-1} \implies A_{i+1} - A_{i} = \frac{q}{p}(A_{i} - A_{i-1})

Using the equations on the right recursively, we have that

A_i - A_{i-1} = \frac{q}{p} (A_{i-1} - A_{i-2}) = \Big(\frac{q}{p}\Big)^2 (A_{i-2} - A_{i-3}) = \cdots = \Big(\frac{q}{p}\Big)^{i-1} (A_{1} - A_{0}) = \Big(\frac{q}{p}\Big)^{i-1} A_{1}

Using the equations on the right and $A_0 = 0$ , we have

A_i = A_i - A_0 = \sum_{j=1}^i A_j - A_{j-1} = A_i \sum_{j=1}^i \Big(\frac{q}{p}\Big)^{j-1} = \begin{cases} iA_i & q = p = \frac{1}{2} \\ \frac{\displaystyle 1-\Big(\frac{q}{p}\Big)^{i}}{\displaystyle 1-\frac{q}{p}} A_1 & q \neq p \end{cases}

Substitute in $A_n = 1$ ,

A_1 = \begin{cases} \frac{\displaystyle 1}{\displaystyle n} & q = p = \frac{1}{2} \\ \frac{\displaystyle 1-\frac{q}{p}}{\displaystyle 1-\Big(\frac{q}{p}\Big)^{n}} & q \neq p \end{cases}

Thus, we have

A_i = \begin{cases} \frac{\displaystyle i}{\displaystyle n} & q = p = \frac{1}{2} \\ \frac{\displaystyle 1-\Big(\frac{q}{p}\Big)^{i}}{\displaystyle 1-\Big(\frac{q}{p}\Big)^{n}} & q \neq p \end{cases}

By symmetry, we have

B_i = \begin{cases} \frac{\displaystyle i}{\displaystyle n} & q = p = \frac{1}{2} \\ \frac{\displaystyle 1-\Big(\frac{p}{q}\Big)^{i}}{\displaystyle 1-\Big(\frac{p}{q}\Big)^{n}} & q \neq p \end{cases}

It takes some algebra to show that $A_i + B_{n-i} = 1$ . This apparently makes sense, since either Alice wins or Bob wins. However, it is actually a non-trivial result because it suggests the game is finite.