Problem 232: The Race

Detailed mathematical approach

Problem Summary

Two players share a fair coin and take turns. On Player 1's turn the coin is tossed once: heads scores one point, tails scores nothing. On Player 2's turn, Player 2 chooses a positive integer \(T\) and the coin is tossed \(T\) times; if all of them show heads, Player 2 scores \(2^{T-1}\) points, otherwise nothing. Player 1 moves first, and the first player to reach \(100\) or more points wins. Player 2 always chooses the \(T\) that maximises the probability of winning, and we must find the probability that Player 2 wins, rounded to eight decimal places in the form 0.abcdefgh. The statement gives no intermediate values. ^[1]

The whole solution in one sentence: describe each moment of the game by the points that each player still needs, notice that a failed gamble of Player 2 followed by a tail of Player 1 returns the game to exactly the same moment, solve this small loop with one line of algebra for every choice of \(T\), and fill a \(100\times100\) table of winning chances backwards from the finish line, keeping the best \(T\) in every cell.

Mathematical Approach

We derive one formula per position and choice of \(T\), prove that the best \(T\) in every position gives the best strategy, test it on races to one and two points, and examine the resulting strategy and the rounding errors.

1. Positions instead of scores

Only the distances to the finish matter. Let \(a\) and \(b\) be the numbers of points that Player 1 and Player 2 still need; the game starts at \(a=b=100\). Write \(F(a,b)\) for the probability that Player 2 wins when it is Player 2's turn, and \(G(a,b)\) for the same probability when Player 1 is about to toss, assuming that Player 2 plays as well as possible. The answer is \(G(100,100)\). The game ends as soon as a player reaches the target, so we set \(F(0,b)=0\) for \(b\ge1\), because Player 1 has won, and \(F(a,0)=G(a,0)=1\) for \(a\ge1\), because Player 2 has; the corner \((0,0)\) never occurs. The game ends with probability \(1\), since every turn of Player 1 scores with probability \(\tfrac12\).

2. Every choice has the same average

If Player 2 chooses \(T=t\), the gamble succeeds with probability \(q_t=2^{-t}\) and then brings \(d_t=2^{t-1}\) points, on average \(q_t\,d_t=\tfrac12\) point per turn whatever \(t\) is, exactly as much as Player 1's single toss. No choice makes Player 2 faster on average: \(T=1\) brings one point with probability \(\tfrac12\), and \(T=4\) brings eight points with probability \(\tfrac1{16}\). What Player 2 controls is the risk, and the problem is to know when a risk is worth taking. Points beyond the finish line are worth nothing, so a gamble should never be larger than necessary; Section 6 proves this.

3. The race to one point

Suppose that both players need one point. Player 2 then tosses once, since a larger \(T\) only lowers the chance of success, and the game is a sequence of rounds, each a toss of Player 1 followed by a toss of Player 2. In each round Player 1 wins at once with probability \(\tfrac12\), Player 2 wins with probability \(\tfrac12\cdot\tfrac12=\tfrac14\), and with probability \(\tfrac14\) both tosses fail and a new round begins. Player 2 wins in round \(k\) when the first \(k-1\) rounds bring nothing and Player 2 wins round \(k\), so the chances add up to a geometric series: ^[5]

$$\sum_{k\ge1}\Bigl(\frac14\Bigr)^{k-1}\cdot\frac14=\frac{1/4}{1-1/4}=\frac13.$$

The same number follows from two equations, and this is the method that works in general. At Player 2's turn a success wins and a failure passes the coin on, so \(F(1,1)=\tfrac12+\tfrac12\,G(1,1)\); at Player 1's turn a head ends the game and a tail passes the coin back, so \(G(1,1)=\tfrac12\,F(1,1)\). Hence \(F(1,1)=\tfrac12+\tfrac14\,F(1,1)\), so \(F(1,1)=\tfrac23\) and \(G(1,1)=\tfrac13\).

4. The equations of the game

In general, Player 1's toss leads to Player 2's turn at \((a-1,b)\) after heads and at \((a,b)\) after tails, so for \(a,b\ge1\)

$$G(a,b)=\frac{F(a-1,b)+F(a,b)}{2}.$$

If Player 2 chooses \(t\), a success either ends the game or passes the coin to Player 1 with \(d_t\) fewer points to go, so the value of a success is

$$S_t(a,b)=\begin{cases}1, & d_t\ge b,\\ G(a,\,b-d_t), & d_t\lt b.\end{cases}$$

A failure passes the coin to Player 1 with nothing changed. Player 2 takes the best \(t\), so

$$\begin{aligned}F(a,b)=\max_{t\ge1}\Bigl(&q_t\,S_t(a,b)\\&+(1-q_t)\,G(a,b)\Bigr).\end{aligned}$$

This is the Bellman equation of the game: the value of a position is the best, over the available choices, of the average value of the positions to which the choice leads. ^[3] Positions, choices and random transitions form a Markov decision process. ^[2] The difficulty is the failure branch: \(G(a,b)\) contains \(F(a,b)\) itself, so the equation does not yet say how to compute \(F(a,b)\).

5. Removing the loop

Fix one choice \(t\) and suppose that Player 2 keeps it while the game stays at \((a,b)\). With \(x\) the winning probability at Player 2's turn, \(S_t=S_t(a,b)\) and \(F'=F(a-1,b)\), the two equations of Section 4 give

$$x=q_t\,S_t+(1-q_t)\cdot\tfrac12\bigl(F'+x\bigr).$$

Solving this linear equation for \(x\) gives the value of the fixed choice \(t\); the second form below multiplies the numerator and the denominator by \(2^t\):

$$\begin{aligned}F_t(a,b)&=\frac{2q_t\,S_t+(1-q_t)\,F'}{1+q_t}\\&=\frac{2S_t+(2^t-1)\,F'}{2^t+1}.\end{aligned}$$

The formula can also be read off directly. Each round of the loop ends in one of three ways: the gamble succeeds, with probability \(q_t\); it fails and Player 1 scores, with probability \(\tfrac12(1-q_t)\); or it fails and Player 1 does not score, with the same probability, and the round starts again. So the success comes before the point of Player 1 with probability

$$\frac{q_t}{q_t+\frac12(1-q_t)}=\frac{2q_t}{1+q_t}=\frac{2}{2^t+1},$$

and the point comes first with probability \(\frac{2^t-1}{2^t+1}\). The two weights add up to \(1\), so \(F_t(a,b)\) is an average of the value of a success and of \(F'\). In the race to one point, \(t=1\) gives the weight \(\tfrac23\) to the success value \(1\), so \(F_1(1,1)=\tfrac23\), as in Section 3.

6. Gambles larger than necessary never help

Let \(t_0(b)\) be the smallest \(t\) with \(2^{t-1}\ge b\), the smallest gamble that wins at once; in other words \(t_0(b)=\lceil\log_2b\rceil+1\). For every \(t\ge t_0(b)\) a success wins, \(S_t=1\), and the formula of Section 5 can be rewritten as

$$1-F_t(a,b)=\frac{2^t-1}{2^t+1}\,\bigl(1-F'\bigr).$$

The factor equals \(1-\frac{2}{2^t+1}\) and grows with \(t\), so among these choices \(t_0(b)\) is the best: a larger gamble wins nothing more and succeeds less often. Only \(t=1,\dots,t_0(b)\) can be optimal, and since \(2^6\lt100\le2^7\), \(t_0(b)\le8\) for every \(b\le100\). In particular the maximum in Section 4 is taken over finitely many numbers.

7. The best fixed choice is the best strategy

Section 5 kept \(t\) fixed. A strategy may also change \(t\) from one visit of \((a,b)\) to the next, choose it at random, or let it depend on the whole history. None of this helps: we prove by induction on \(a+b\) that the best winning probability is

$$F(a,b)=\max_{t\ge1}F_t(a,b),$$

with \(F_t\) computed from the best values of the positions with a smaller \(a+b\), known by the induction hypothesis; the positions with \(a=0\) or \(b=0\) start the induction. Let \(V\) be the supremum, the least upper bound, of Player 2's winning probabilities at \((a,b)\) over all strategies; we do not assume that some strategy reaches it. Let

$$\varphi_t(x)=q_t\,S_t+\tfrac12(1-q_t)\bigl(F'+x\bigr).$$

Whatever Player 2 does on the first visit, a success or a point of Player 1 leads to positions with a smaller \(a+b\), where no strategy beats the best values, while a failure followed by a tail returns to \((a,b)\), where no strategy wins with probability more than \(V\). So every strategy wins with probability at most \(\max_t\varphi_t(V)\), since a random choice of \(t\) only averages these values, and therefore \(V\le\max_t\varphi_t(V)\). Each \(\varphi_t\) is a straight line with slope \(s_t=\tfrac12(1-q_t)\lt\tfrac12\), and its fixed point, the number \(x_t\) with \(\varphi_t(x_t)=x_t\), is \(x_t=F_t(a,b)\) by Section 5. Let \(x^*\) be the largest \(x_t\). For \(x\ge x^*\),

$$\begin{aligned}\varphi_t(x)&=(1-s_t)\,x_t+s_t\,x\\&\le x^*+\tfrac12\,(x-x^*).\end{aligned}$$

If \(V\) were larger than \(x^*\), this would give \(\max_t\varphi_t(V)\lt V\), a contradiction. So \(V\le x^*\), and the strategy that always chooses a maximising \(t\) at \((a,b)\) wins with probability exactly \(x^*\), by Section 5. This is the argument of the Banach fixed-point theorem on a small scale: a map that shrinks distances has only one fixed point. ^[6] Also, the equation of Section 4 at \((a,b)\), that is \(x=\max_t\varphi_t(x)\), has no solution other than \(x^*\): a larger one contradicts the inequality above, and for \(x\lt x^*\) the line of a maximising \(t\) gives \(\varphi_t(x)\gt x\).

8. Filling the table

The value \(F(a,b)\) needs \(F(a-1,b)\) from the previous row and, through \(S_t\), the values \(F(a,b-d_t)\) and \(F(a-1,b-d_t)\) with a smaller second index. So the table can be filled row by row, \(a=1,2,\dots,100\), and inside each row from \(b=1\) to \(b=100\): whenever a cell is computed, every cell it needs is already known. This is dynamic programming, the solution of a large problem built bottom-up from stored solutions of smaller subproblems. ^[4] At the end, one toss of Player 1 gives the answer

$$\begin{aligned}G(100,100)&=\tfrac12\,F(99,100)\\&\quad+\tfrac12\,F(100,100).\end{aligned}$$

9. Worked example: the race to two points

With the target \(2\) the table has four cells, and we use the second form of \(F_t\). By Section 6 only \(t=1\) matters when \(b=1\), and only \(t=1\) and \(t=2\) when \(b=2\). The cell \((1,1)\) is the race to one point, \(F(1,1)=\tfrac23\). In the cell \((2,1)\), \(t=1\) wins on success and \(F'=F(1,1)\):

$$F(2,1)=\frac{2\cdot1+\frac23}{3}=\frac89.$$

In the cell \((1,2)\) we have \(F'=F(0,2)=0\). A success of \(t=1\) leads to \(G(1,1)=\tfrac13\), while a success of \(t=2\) wins at once:

$$\begin{aligned}F_1(1,2)&=\frac{2\cdot\frac13+0}{3}=\frac29,\\F_2(1,2)&=\frac{2\cdot1+3\cdot0}{5}=\frac25.\end{aligned}$$

Player 2 picks the bold \(t=2\): Player 1 needs only one more head, so there may be no time for two successful turns. In the cell \((2,2)\) we have \(F'=F(1,2)=\tfrac25\), and a success of \(t=1\) leads to \(G(2,1)=\tfrac12\bigl(\tfrac23+\tfrac89\bigr)=\tfrac79\):

$$\begin{aligned}F_1(2,2)&=\frac{2\cdot\frac79+\frac25}{3}=\frac{88}{135},\\F_2(2,2)&=\frac{2\cdot1+3\cdot\frac25}{5}=\frac{16}{25}.\end{aligned}$$

Here the cautious \(t=1\) is better, since \(\tfrac{88}{135}\approx0.6519\) exceeds \(\tfrac{16}{25}=0.64\). So Player 2 wins the race to two points with probability

$$\begin{aligned}G(2,2)&=\tfrac12\cdot\tfrac25+\tfrac12\cdot\tfrac{88}{135}\\&=\tfrac{71}{135}\approx0.5259.\end{aligned}$$

If Player 2 always tossed once, the same steps would give \(F(1,2)=\tfrac29\), \(F(2,2)=\tfrac{16}{27}\) and \(G(2,2)=\tfrac{11}{27}\approx0.4074\). The single bold choice at \((1,2)\) turns a race that Player 2 usually loses into one that Player 2 usually wins.

10. The two edges of the table

When Player 2 needs one point, \(t_0(1)=1\) and \(T=1\) is optimal, so Section 5 gives \(F(a,1)=\tfrac13\bigl(2+F(a-1,1)\bigr)\), and induction from \(F(0,1)=0\) gives

$$F(a,1)=1-3^{-a}.$$

Indeed, Player 2 loses only if Player 1 scores \(a\) times before Player 2's first head, and in each round of a toss of Player 2 and a toss of Player 1, a point of Player 1 (probability \(\tfrac14\)) comes before a head of Player 2 (probability \(\tfrac12\)) with probability \(\tfrac13\). When Player 1 needs one point, Player 2 must go all in:

$$F(1,b)=\frac{2}{2^{t_0(b)}+1}.$$

The choice \(t=t_0(b)\) gives this value by Section 5, since \(F(0,b)=0\). For a smaller \(t\), the success value is \(G(1,b-d_t)=\tfrac12F(1,b-d_t)\), so \(F_t(1,b)=F(1,b-d_t)/(2^t+1)\). Assume the formula for every smaller \(b\) and let \(s=t_0(b-d_t)\). Then \(b\le2^{t-1}+2^{s-1}\le2^{\max(t,s)}\), so \(t_0(b)\le\max(t,s)+1\le t+s\), and

$$\begin{aligned}F_t(1,b)&=\frac{2}{(2^t+1)(2^s+1)}\\&\lt\frac{2}{2^{t+s}+1}\le\frac{2}{2^{t_0(b)}+1}.\end{aligned}$$

For example \(F(1,100)=\tfrac2{257}\): one step from defeat, splitting the missing points into two gambles costs more than one larger gamble. Both edge formulas give exact checks of the table.

11. What the best strategy looks like

In the race to \(100\), Player 2 tosses once in \(4685\) of the \(10000\) cells with \(1\le a,b\le100\). All but \(11\) of them have \(b\le a\), and \(4674\) of the \(5050\) cells with \(b\le a\) use \(T=1\): when not behind, Player 2 mostly plays safe. When behind, Player 2 gambles, the more the further behind; \(T=8\), the largest useful value, is chosen in \(500\) cells. The first choice of the game is \(T=4\), whether or not Player 1's first toss scored. The best \(T\) is not a simple function of the gap: it is \(T=3\) in the cell \((6,8)\) but \(T=1\) in the cell \((6,9)\), where one point would leave exactly \(8\) points, which one success of \(T=4\) covers, whereas \(9\) points need \(T=5\).

Player 2 wins the race to \(n\) points with probability \(\tfrac13\), \(\tfrac{71}{135}\), \(\tfrac{661}{1215}\) and \(\tfrac{6113}{10125}\approx0.6038\) for \(n=1,2,3,4\), and about \(0.6701\) for \(n=10\). Always tossing once would give only \(\tfrac13\), \(\tfrac{11}{27}\), \(\tfrac{35}{81}\), \(\tfrac{971}{2187}\approx0.4440\) and about \(0.4671\): moving second costs Player 2 a little, and choosing the risk well gains much more.

12. Rounding errors

The programs compute with double-precision numbers, which round every operation with a relative error of at most \(2^{-53}\approx1.1\cdot10^{-16}\). ^[7] Old errors are never amplified here: every candidate \(F_t\) is an average, with nonnegative weights that add up to \(1\), of numbers computed earlier and of \(0\) and \(1\), and neither an average nor a maximum increases the largest error of its inputs. The programs evaluate the first form of \(F_t\), and one candidate rounds at most four times, in the sum inside \(S_t\), the product \((1-q_t)\,F'\), the sum in the numerator and the division; the other operations are exact because \(q_t\) is a power of two. All numbers involved are at most \(2\), so one cell adds an error below \(8\cdot2^{-53}\lt10^{-15}\). Every step of a chain of dependencies lowers \(a+b\), so a chain has at most \(200\) steps, and every entry, like the final average, is within \(2\cdot10^{-13}\) of its exact value. The exact answer lies about \(8.5\cdot10^{-10}\) away from the nearest point at which rounding to eight decimals changes, so the printed digits are correct.

How the Code Works

The three programs follow the same plan; the C++ file ^[8] also contains the checks described below. compute_t_limit(target), called computeTLimit in Java, returns \(t_0\) of the target, as in Section 6, plus \(4\), so for the target \(100\) the programs try \(t=1,\dots,12\), of which \(9\) to \(12\) are never optimal. The table f has \((\mathrm{target}+1)^2\) entries, f[a][b] being \(F(a,b)\); the entries f[a][0] with \(a\ge1\) are set to \(1\), and \(F(0,b)=0\) enters through the tests a == 1. The arrays q and score hold \(q_t\) and \(d_t\); std::ldexp, 2.0 ** (-t) and Math.pow all give the exact power of two. p1_turn_value(f, a, b), called p1TurnValue in Java, is \(G(a,b)\) of Section 4, with \(0\) for \(a\le0\) and \(1\) for \(b\le0\).

The main loops, solve_closed_form in C++ and solve in Python and Java, run over \(a\) and then \(b\) in increasing order, as in Section 8. In each cell prev_same_b is \(F(a-1,b)\), the success value is \(1\) when the gain reaches \(b\) and p1_turn_value(f, a, b - gain) otherwise, and candidate is the first form of \(F_t\) in Section 5. The largest candidate is stored, a strict comparison keeping the smallest \(t\) among equal values, and the C++ version records its \(t\) in best_t. Finally p1_turn_value(f, target, target), that is \(G(100,100)\), is printed with eight decimals; Java formats with Locale.US so that the decimal separator is a point. The C++ program also accepts another target on the command line.

Only the C++ program checks itself. validate() requires the value \(\tfrac13\) for the target \(1\) (Section 3) up to \(10^{-13}\), and agreement within \(2\cdot10^{-12}\) with solve_value_iteration for the targets \(5\), \(10\) and \(20\); depending on the machine, a further check compares two runs of that verifier at the target \(35\) within \(10^{-12}\), and any failure stops the program with an error message. solve_value_iteration does not use the formula of Section 5. It keeps the tables p1 for \(G\) and p2 for \(F\) and repeats sweeps of the raw equations of Section 4, first the new \(G\) from the old \(F\), then the new \(F\) as the maximum over \(t\) of \(q_tS_t+(1-q_t)\,G\), until the largest change in a sweep is below \(10^{-14}\), or for at most \(5000\) sweeps. This is value iteration. ^[2] In exact arithmetic the entries start below their final values and never decrease, because every update is monotone; being bounded, they converge, and the limits solve the equations of Section 4, whose solution is unique by Section 7. The verifier stops after \(50\), \(71\) and \(103\) sweeps for the targets \(5\), \(10\) and \(20\).

Complexity and Verification

For the target \(N\) the table has \(N^2\) cells and each cell tries \(\lceil\log_2N\rceil+5\) values of \(t\), so the time is \(O(N^2\log N)\) and the memory \(O(N^2)\). For \(N=100\) the programs evaluate \(1.2\cdot10^5\) candidates; the \(101^2\) doubles of the table take about \(80\) KB in C++ and Java, plus best_t in C++, while Python's lists of float objects take about \(0.33\) MB. A sweep of the verifier costs as much as the main loop, and each program, checks included, runs in well under a second. All three programs print the same eight decimals, and the C++ checks pass.

Further checks, not part of the published solutions, were made for this article. An exact computation of the whole table for the target \(100\) with rational numbers shows that every double differs from the exact value by at most \(6.7\cdot10^{-16}\), that the exact maximum is never tied and the programs pick the same \(t\) in every cell, and that the exact starting value is a fraction with a \(480\)-digit denominator. For the races to \(2\) and \(3\) points, all \(4^4=256\) and \(4^9=262144\) strategies with a fixed \(T\in\{1,2,3,4\}\) in each cell were evaluated by solving the linear equations of the game; the best give \(\tfrac{71}{135}\) and \(\tfrac{661}{1215}\), with the choices of the table. The edge formulas of Section 10 hold exactly for \(a,b\le30\). A simulation that follows the rules literally, with Player 2 choosing \(T\) from the table, played \(10^7\) games for each of the targets \(1\), \(2\), \(3\) and \(100\); the frequencies differ from the computed probabilities by \(1.34\), \(0.81\), \(-1.15\) and \(1.29\) standard errors.

Footnotes and References

The references below supply the background facts used above. The formula for a fixed choice of \(T\), the proof that the best fixed choice is optimal, the edge formulas and the error bound are derived in this article.

1. Project Euler 232 — The Race. Player 1 tosses once per turn and scores one point for heads; Player 2 chooses T, tosses T times and scores 2^(T−1) points if all tosses are heads; Player 1 starts, the first to 100 or more points wins, and Player 2 always chooses T to maximise the probability of winning; the task asks for that probability, rounded to eight decimal places.
2. Wikipedia — Markov decision process. A model of sequential decisions with states, actions, transition probabilities and rewards; the optimal value function satisfies the Bellman recursion, and value iteration starts from a guess of it and repeats the update until the values converge.
3. Wikipedia — Bellman equation. It writes the value of a decision problem in terms of the payoff from some initial choices and the value of the remaining decision problem, following Bellman's principle of optimality.
4. Wikipedia — Dynamic programming. A problem is broken down into simpler sub-problems; bottom-up, the sub-problems are solved first, usually in tabular form, and their solutions build those of bigger sub-problems.
5. Wikipedia — Geometric series. For |r| < 1 the series a + ar + ar² + … converges to a/(1 − r); Section 3 uses a = r = 1/4.
6. Wikipedia — Banach fixed-point theorem. A contraction, a map with d(T(x), T(y)) ≤ q·d(x, y) for a constant q < 1, of a non-empty complete metric space has exactly one fixed point, and the iterates x_n = T(x_(n−1)) converge to it.
7. Wikipedia — Machine epsilon. For IEEE 754 double precision the unit roundoff is 2⁻⁵³ ≈ 1.11·10⁻¹⁶, a bound for the relative error of a rounded result.
8. C++ — Euler232.cpp. The linked immutable C++ revision contains compute_t_limit, p1_turn_value, solve_closed_form, solve_value_iteration and validate. It is the implementation record for this article.