When to stop tossing a coin

When to stop looking solved the secretary problem — choose the best of a sequence of candidates, seen one at a time, with no going back — and found that the best rule waits through the first $1/e$ of the sequence and then takes the first candidate better than all before. The essays that followed it changed the information, the payoff and the memory allowed, and the rank that remembers every value ended on a problem whose answer is still unknown.

This essay takes a problem with no candidates at all. A fair coin is tossed repeatedly. After each toss the player may stop, and is then paid the proportion of tosses so far that came up heads. Yuan Shih Chow and Herbert Robbins posed it in 1965, and it is the cleanest example of optimal stopping with an infinite horizon: the player can always wait, the coin never runs out, and the question is entirely when.

The first toss, and why the game is not trivial #

If the first toss is a head, stop: the proportion is one, the most possible. The whole game is about what to do after a tail, or after a run that leaves heads only slightly ahead.

Waiting can never hurt in one sense. A fair coin’s lead — heads minus tails — performs a symmetric random walk, and a walk that comes home showed that such a walk returns to every level infinitely often. A player who waits will see heads lead again, and again, with certainty. So the player can always guarantee a proportion above a half, and the game is worth at least a half. But waiting also dilutes: a lead of one after three tosses is a proportion of $2/3$, a lead of one after a hundred tosses is $0.505$. The longer the wait, the less a given lead is worth, and the trade-off between waiting for a bigger lead and keeping the lead already in hand is the content of the problem.

Solving it backwards #

The standard tool is backward induction: the value of a position is the larger of the payoff for stopping now and the average of the values of the two positions the next toss leads to. That needs a last toss to start from, and the game has none. The figures supply an artificial horizon $N$: at $N$ tosses the value of a position with $h$ heads is replaced by $\max(h/N, \tfrac12)$, which the player can certainly secure from there by waiting for the lead to become positive. Working back from the horizon then gives, for every earlier position, a value that is a guaranteed lower bound on the true one — achieved by a rule that plays optimally until the horizon and then simply waits for a lead.

The lower bounds rise with the horizon — $0.79231$ at 500 tosses, $0.79281$ at 4,000, $0.79287$ at 8,000 — and approach the true value from below, slowly, because the positions close to the horizon are undervalued and that undervaluation seeps back. The true value is about $0.792953$. Olle Häggström and Johan Wästlund established it to six decimal places in 2013 by combining a lower bound of this kind, pushed to horizons of millions of tosses, with an upper bound obtained by replacing the far future with the Brownian motion that a long coin-tossing walk resembles. Before their work the value was known only roughly, although the game had been studied for almost fifty years.

Where the boundary lies #

The hero figure shows the rule that the induction produces. After one toss it stops on a lead of one — a single head. After two tosses it stops on a lead of two, both heads. After three, on a lead of three, all heads: $2/3$ is not enough. After four, a lead of two — three heads in four — is enough. The thresholds then grow, irregularly at first.

The tree shows the small-case structure. The least lead at which the rule stops after one to six tosses is $1, 2, 3, 2, 3, 2$: stop at $1/1$, $2/2$, $3/3$, $3/4$, $4/5$ and $4/6$, but toss on from $2/3$ and $3/5$. The zigzag comes from the lead changing by two at a time, so that an even number of tosses allows only even leads; the rule has to weigh a lead of two against a lead of four, with nothing between. Only after many tosses does the threshold settle into a smooth law.

That law is a square root. Chow and Robbins proved that the optimal rule stops as soon as the lead reaches some threshold $\beta(n)$, and Aryeh Dvoretzky showed that $\beta(n)/\sqrt n$ tends to a constant. The constant had been computed by Larry Shepp in 1969 for the continuous version of the game, in which a Brownian motion replaces the coin and the payoff is $W_t/t$: the optimal rule stops when $W_t \ge \alpha\sqrt t$ with $\alpha \approx 0.8399$, the root of an equation built from the normal distribution’s tail.

The ratio $\beta(n)/\sqrt n$ zigzags, because the lead moves in steps of two, and averages $0.794$ for $n$ between 1,000 and 3,000 — below Shepp’s $0.8399$ and creeping towards it. The approach is slow, and the finite horizon pulls the computed thresholds down a little, since the induction undervalues waiting near the horizon. The square root itself is the scale of a random walk: after $n$ tosses the lead is typically about $\sqrt n$ in size, so the rule stops when the coin is about $0.84$ standard deviations ahead.

Simple rules, and two exact numbers #

The best rule is complicated, and simpler rules are close to it. Two of them pay numbers that can be computed exactly.

Stop the first time heads lead. The lead first reaches $+1$ at some toss $T$, necessarily odd, and the proportion then is $(T + 1)/2T = \tfrac12 + \tfrac{1}{2T}$. The average payoff is $\tfrac12 + \tfrac12\,\mathbb{E}[1/T]$, and the distribution of $T$ is classical: the chance that the first lead comes at toss $2k - 1$ is a Catalan number over $2^{2k-1}$, the count that the path folded at its first touch obtained by reflection. Its generating function is $\mathbb{E}[s^T] = (1 - \sqrt{1 - s^2})/s$, and integrating it against $1/s$ from nought to one gives $\mathbb{E}[1/T] = \pi/2 - 1$. So the rule pays exactly

$$\frac12 + \frac12\left(\frac{\pi}{2} - 1\right) = \frac{\pi}{4} = 0.785398\ldots,$$

which the figure confirms by summing the series to two hundred thousand terms.

Stop the first time heads lead by two. Now the first passage is to $+2$, the proportion is $\tfrac12 + 1/T$, and the generating function is the square of the previous one. The same integral gives $\mathbb{E}[1/T] = \ln 2 - \tfrac12$, so the rule pays exactly $\ln 2 = 0.693147\ldots$ — far worse than stopping at a lead of one, because demanding two from the start throws away every game that would have stopped on a first head. The backward induction, evaluating the rule over 4,000 tosses, gives $0.693145$, the small deficit being the horizon.

Stop when the lead reaches $0.84\sqrt n$. Shepp’s rule, copied directly from the Brownian solution with a minimum lead of one, pays $0.79199$, within a thousandth of the best rule’s $0.79281$ on the same horizon. Its threshold is fractional while the lead is a whole number, so in practice it stops on the first whole-number lead at or above the curve, which early in the game means waiting for leads the best rule would not wait for. The best rule’s extra comes from the small-case corrections — stopping on $3/4$ rather than waiting, tossing on from $2/3$ — that a smooth curve cannot make.

That $\pi$ and $\ln 2$ appear as the payoffs of the two simplest rules, while the optimal payoff has no known closed form, is the same pattern as in much of this subject: the natural rules are exactly computable, and the best rule is a numerical object.

Where π comes from #

The appearance of $\pi$ in the payoff of the first-lead rule deserves a second look, because nothing in the game mentions a circle. The integral that produces it,

$$\mathbb{E}\!\left[\frac1T\right] = \int_0^1 \frac{1 - \sqrt{1 - s^2}}{s^2}\, ds,$$

is an integral of a square root of $1 - s^2$, which is the height of a unit circle above the point $s$; substituting $s = \sin\theta$ turns it into an integral over an angle, and the $\pi/2$ is a quarter-turn. The square root, in turn, comes from the Catalan numbers: their generating function solves a quadratic equation, because a path that first reaches $+1$ either does so at once or first dips and then makes two independent first passages, and solving the quadratic produces the square root. So the chain runs from a recursive decomposition of coin-tossing paths, through the Catalan numbers, to a quadratic, a square root, a circle and $\pi/4$.

The $\ln 2$ for a lead of two comes from the same square root, squared, because a first passage to $+2$ is two first passages to $+1$ in succession. The integral of the squared generating function has no circle in it: the square of $1 - \sqrt{1 - s^2}$ contains a term $1 - s^2$ that integrates to a logarithm. The two simplest stopping rules therefore pay the two most familiar transcendental constants, and for a structural reason. The pattern continues: waiting for a first lead of three pays $3 - 3\pi/4 \approx 0.6438$, back to $\pi$ because an odd power of the square root survives, and every longer wait pays less.

The game as a race between two scales #

The game can also be read as a contest between two quantities that grow at different rates with the number of tosses. The lead grows like $\sqrt n$ — that is the size of a random walk’s typical excursion — while the number of tosses grows like $n$. The proportion of heads exceeds a half by the lead divided by $2n$, which shrinks like $1/\sqrt n$. So every lead the player could hope for is worth less the longer the game runs, but the walk also produces larger leads given time. The optimal rule balances the two, and the balance is struck at a lead proportional to $\sqrt n$, where both effects scale the same way.

That is why the Brownian version of the game, which keeps only the scales and forgets the coin, captures the rule for large $n$ exactly. It is also why the rule’s small-case behaviour is irregular: for the first few tosses the lead can only take a few values, the square-root scale is not yet meaningful, and the rule is decided by the arithmetic of particular fractions — $3/4$ against waiting, $2/3$ against waiting — rather than by any smooth law. Add the odds from the end found the same contrast in the secretary problem, where an exact rule for small numbers of candidates gives way to a limiting rule, the $1/e$ threshold, as the number grows.

Two hundred thousand games #

The rule computed above can be played.

Half of all games end on the first toss, with a head. Three-quarters end within 46 tosses. One in ten lasts beyond 1,870 tosses, and one in a hundred beyond a hundred thousand — the games in which an early run of tails puts the player far behind, and the rule waits for the walk to come back, which it always does, but on a timescale with no finite average. The average payoff over the two hundred thousand games is $0.7923$, matching the computed value within sampling error. Fewer than seven per cent of games outlast the 4,000 tosses the rule was computed for, and those are finished by waiting for heads to lead.

The long tail is the price of the guarantee. A player who could not afford to wait — who had to stop by some fixed number of tosses — would face a different and less valuable game, and the secretary problem and its relatives are all games of that bounded kind. The Chow–Robbins game is worth $0.79$ because waiting is free, and the rule uses that freedom heavily in a few games to gain a little in many.

What an oracle would add #

A player who could see the whole sequence of tosses in advance would stop at the moment the proportion of heads is highest. Over twenty thousand seeded sequences of twenty thousand tosses, that highest proportion averages about $0.814$ — so an oracle, playing the same game with perfect foresight, earns only about two points more than the best honest rule’s $0.793$. Half of what an oracle takes found a guaranteed ratio of one half between an honest player and an oracle when the values are independent and arbitrary; here the honest player gets more than ninety-seven per cent of what the oracle gets. The difference is the structure of the coin: the proportion of heads changes slowly and predictably once many tosses have been made, so there is little for foresight to exploit, and much of the oracle’s advantage must come from the first few tosses, where a single head or tail moves the proportion a long way.

Waiting is a fair game #

The game sits on top of a fact that two barriers and a fair game proved: a fair game stays fair under any stopping rule that cannot see the future, provided the game cannot run too long. The lead of heads over tails is a fair game, and no rule can make its expected value at stopping positive if stopping times are bounded. Yet the Chow–Robbins player stops with a positive lead almost every time.

There is no contradiction, because the payoff is the proportion of heads, not the lead, and because the stopping times here are not bounded — some games last a hundred thousand tosses. The proportion is the lead divided by the number of tosses, and a rule that stops on small leads early and waits long when behind turns a fair walk into a positive expected proportion. Peeking until the answer is yes met the same mechanism in statistics, where an experimenter who stops a trial as soon as the data look significant manufactures significance from noise; the coin player is doing the same thing deliberately and is paid for it.

Lower bounds from a game cut short #

Every value in the figures is a lower bound on the true game, exact for the truncated game it solves. The thresholds are exact for the truncated game and very close to the true ones for positions far from the horizon; near the horizon they are biased towards stopping, which is why the square-root ratio sits a little low. The simulated games use the computed thresholds and a seeded generator, and agree with the computed value. The exact payoffs $\pi/4$ and $\ln 2$ are derived from first-passage generating functions, and the series and the induction confirm them numerically.

The computations do not give an upper bound, so by themselves they cannot fix the value’s sixth decimal; that took Häggström and Wästlund’s comparison with Brownian motion, which bounds what the far future can add.

Still open: the value’s closed form, and the exact boundary #

The value of the Chow–Robbins game is known numerically and has no known closed form; nobody knows whether it is expressible through familiar constants, as the simple rules’ payoffs are. The exact stopping boundary is also not fully known: Häggström and Wästlund determined the optimal decision in every position up to a very large number of tosses except for a handful of positions where the computed lower and upper bounds overlapped, and a few such positions — leads at which it is not known whether to stop — remained undecided. The question for each is whether the value of continuing exceeds the current proportion, and the margins are smaller than the methods could resolve. Whether a finer computation or an exact argument decides them all, and whether the boundary $\beta(n)$ is eventually exactly the integer nearest to some smooth function of $n$, are open questions about a game a child could play.