The Race

Two players share an unbiased coin and take it in turns to play The Race.
On Player 1’s turn, the coin is tossed once. If it comes up Heads, then Player 1 scores one point; if it comes up Tails, then no points are scored.
On Player 2’s turn, a positive integer, $T$, is chosen by Player 2 and the coin is tossed $T$ times. If it comes up all Heads, then Player 2 scores $2^{T-1}$ points; otherwise, no points are scored.
Player 1 goes first and the winner is the first to 100 or more points.
Player 2 will always selects the number, $T$, of coin tosses that maximises the probability of winning.
What is the probability that Player 2 wins?
Give your answer rounded to eight decimal places in the form 0.abcdefgh.

To solve this problem, we would use dynamic programming again.

First, we observe that in order for Player 2 to have any chance of winning, Player 1’s score must be at most 99. Once Player 1 reaches 100 points, the game is over. Another observation is that Player 2 should choose the smallest $T$ that gives him a winning score if he obtains all heads, as this maximizes the probability of getting all heads.

Let’s use a function `f(i, j)` to represent the probability that Player 2 wins when it is Player 2’s turn, Player 1 has `i` points and Player 2 has `j` points. The initial condition is `f(i, j) = 1` when `j` is greater or equal to 100, because Player 2 already won reaching 100 points and `f(i, j) = 0` when `i` is greater or equal to 100, because Player 1 already won.

Player 2 will toss the smallest possible number of coins `T` such that `j + 2^(T-1) >= 100`, trying to reach or surpass 100 points in one move. So, the recurrence formula to calculate `f(i, j)` is `f(i, j) = (1 – (1/2)^T) + (1/2)^T * (1 – f(j, i + 1))`.

Let’s use another function `g(i, j)` to represent the probability that Player 2 wins when it is Player 1’s turn, Player 1 has `i` points and Player 2 has `j` points. If Player 1 gets a head, he gets one point and it becomes Player 2’s turn; if Player 1 gets a tail, he gets no point and it’s still his turn, so `g(i, j) = 0.5 * f(i + 1, j) + 0.5 * g(i, j)`.

Start with `f(i, j) = 1` for `j >= 100` and `f(i, j) = 0` for `i >= 100` (with `i` and `j` in `99, 98,…, 0`) and cycle downwards to smaller $i$ for every $j$ down to 0 using the recurrence function. Then do the same with `g(i, j)`, cycling downwards for $i$ and $j$ from 99 down to 0.

The probability that Player 2 wins when the score is 0-0, and Player 1 plays first, is given by `g(0, 0)`.

Since the solution involves running simulations, it’s not possible to provide a fixed numeric answer without running this simulation or having the programming capability here, however, this approach would give the answer to the problem. One would implement this procedure in a programming language such as Python or C++. Round your answer to 8 decimal places in the form 0.abcdefgh.

The expected number of significant digits in the answer is 8.

More Answers: