0
$\begingroup$

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.

$\endgroup$

3 Answers 3

1
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – supremacy
    Apr 21, 2023 at 9:04
  • $\begingroup$ 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$. $\endgroup$
    – A.J.
    Apr 21, 2023 at 9:18
  • $\begingroup$ 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. $\endgroup$
    – A.J.
    Apr 21, 2023 at 9:38
  • $\begingroup$ 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? $\endgroup$
    – supremacy
    Apr 22, 2023 at 9:17
  • $\begingroup$ 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. $\endgroup$
    – A.J.
    Apr 22, 2023 at 20:34
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$
    – Godfather
    Apr 20, 2023 at 23:19
-2
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .