2
$\begingroup$

Suppose this game: There are two players who have a fair coin each. In every round, they toss their coin. If their coin shows heads, the respective player gets a point. Player 1 needs to collect $X$ points, player 2 needs to collect $Y$ points. The player who reaches his/her goal first wins the game. If both players reach their goal in the same round, nobody wins.

What is the probability that player 1 will win the game?

$\endgroup$
2
  • $\begingroup$ This can be solved with a Markov chain where the possible states are all the tuples (x, y) representing the remaining number of heads needed by each player. $\endgroup$
    – Stef
    Sep 26, 2023 at 9:56
  • $\begingroup$ And geometrically you can represent it as a random walk in the plane: you start at point (X, Y), and at every step you either remain on your point, or move one space down, or one space left, or one space diagonally leftdown, depending on whether none, player 2, player 1, or both players get a head. $\endgroup$
    – Stef
    Sep 26, 2023 at 9:58

1 Answer 1

1
$\begingroup$

My approach was this:

Player 1 wins in round $n$ if she observes her $X$th head at $n$, while player 2 has still less than $Y$ heads in round $n$.

The probability for the first event, i.e., that player 1 reaches exactly $X$ points after the $n$th round is

$$P(x = X| n) = \frac{1}{2} \cdot \textrm{Bino}(X - 1|0.5,~ n - 1)$$

where I denote with $\textrm{Bino}(k|p,~N)$ the binomial PMF to get $k$ successes after $N$ tosses of a coin with heads probability of $p$. The above equation basically means that, to get exactly $X$ heads at the $n$th round, you need to have $X - 1$ heads in round $n - 1$. Having this, the probability is $\frac{1}{2}$ to have exactly $X$ in round $n$.

The second event is that player 2 has less than $Y$ in round $n$. This occurs with probability

$$P(y < Y|n) = \sum_{y = 0}^{Y - 1} \textrm{Bino}(y| 0.5,~n) = CDF(Y - 1|0.5,~ n).$$

The probability that player 1 wins is therefore

$$P = \frac{1}{2}\sum_{n = 0}^\infty \textrm{Bino}(X - 1|0.5,~ n - 1)\cdot CDF(Y - 1|0.5,~ n).$$

Is this correct? Can this be simplified any further, e.g., can one find a closed-form expression for the series over $n$?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.