Suppose person$_1$ has $a$ coins and person$_2$ has $b < a$ coins. They play a game (where there's no draw) in which the winner, who wins with probability $1/2$, receives a coin from the loser. The game continues until one loses all the coins. What's the probability that person$_1$ wins?
I think these are called random walks. If we look at the game from $1$'s perspective, whenever he reaches $0$, he loses (and the game ends) and whenever he reaches $a+b$, he wins (and the game ends). Define $p_k$ as the probability that he reaches $k$. We need to calculate $p_{a+b}$.
I figured that
- $p_{k} = 0.5 p_{k-1} + 0.5 p_{k+1}$ for $k \in [2,a+b-2]$ (which is a difference equation)
- $p_{a+b} = 0.5 p_{a+b-1} = 0.5^2 p_{a+b-2}$
- $p_0 = 0.5 p_1 = 0.5^2 p_2$
How do I proceed from here?
I am strictly looking to solve this recursion and not a different one.
Best Answer
The standard technique for solving linear recurrences is already mentioned in @Godfather's answer. However in this instance, a slight modification to your definition of $p_n$ would yield a simpler solution even though the recursion equation would be the same.
Suppose, instead, you define $p_n$ as the probability that a player wins if they have $n$ coins. Note that your recursion equation
$$p_k^{\color{white}{\text{x}}} = \frac{1}{2} \, p_{k-1}^{\color{white}{\text{x}}} + \frac{1}{2} \, p_{k+1}^{\color{white}{\text{x}}}$$
would still hold, but this time for $k \in [1, a+b-1]$. Also note that with this definition, we have the much simpler initial conditions $p_0^{\color{white}{\text{x}}}=0$ and $p_{a+b}^{\color{white}{\text{x}}}=1$.
The recursion equation implies the sequence of probabilities is arithmetic (I'm not sure whether that's what you meant when you said it was a 'difference equation'), and combining this with the initial conditions immediately gives us that
$$p_k^{\color{white}{\text{x}}} = \frac{k}{a+b}$$
so that the probability player 1 wins is $\frac{a}{a+b}$.