How to solve this random walk recursion?

Question

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.

Answer 1

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}$.

Answer 2

P(Person 1 wins) = { sum from k=ceil((a - b)/2) to a - b of (a - b choose k) / 2^(a - b) } if a - b is odd

P(Person 1 wins) = 1/2 if a - b is even

Answer 3

To solve $p_k = \alpha p_{k-1} + \beta p_{k+1}$, a linear homogenous recurrence, you have to find the roots of the characteristic equation:

$1 = \alpha/x + \beta x$, rearranged as

$\beta x^2 -x + \alpha =0$

Given the two roots of this equation ($r_1, r_2$), your result will be of the form:

$p_k = c_1 r_1^k + c_2 r_2^k$

You can compute $r_1, r_2$ using the standard quadratic formula. Then compute $c_1$ and $c_2$ using your initial conditions (since you know $p_0$ and $p_{a+b}$)