# How to solve this random walk recursion?

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.

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

• I am aware of this solution and hence mentioned that I'm strictly looking to solve that recursion. What I meant by the difference eq. is $p_{k+1} - p_k = p_k - p_{k-1}$. I'm sorry I can't accept your answer despite the effort you put in; hope you understand. Apr 21, 2023 at 9:04
• No worries; the standard technique will easily yield the equation $p_k=\alpha + \beta k$, but I don't think your initial conditions will prove sufficient to determine $\alpha$ and $\beta$.
– A.J.
Apr 21, 2023 at 9:18
• Also, another potential issue that just popped into my head is that by using your definition of $p_k$, would $p_a = 1$? That would imply that $p_{a-1} + p_{a+1} = 2$ which of course can't be true. Perhaps $p_a$ would have to be the probability of returning to $a$, I'm not sure.
– A.J.
Apr 21, 2023 at 9:38
• You're right, even I'm confused about the initial condition. $p_a$ is the probability that he starts at $a$ or he comes from one of $\{a-1, a+1\}$. I don't know how to write that properly. I feel like it's $p_a = 1 + 0.5(p_{a-1} + p_{a+1})$, but then it suggests that $p_{a-1} = p_{a+1} = 0$ which can't be true, right? Apr 22, 2023 at 9:17
• Yes, it seems like the only way to reasonably define $p_a$ is as the probability of getting back to $a$ after the first game. But then you still have the problem that the initial conditions you have aren't sufficient (as far as I can see, anyway) to solve the recursion. It may just be that defining $p_k$ this way is simply not viable.
– A.J.
Apr 22, 2023 at 20:34

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

• I jumped into the solution because it's a standard technique for solving such recurrences. But it maybe helpful to do some background reading on why this works. Not sure about your background, but I can help you dig up some references if you need help Apr 20, 2023 at 23:19

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

• You're saying that if person 1 has 99 coins and person 2 just has 1 coin, then they're equally likely to win? Apr 20, 2023 at 22:51