Three Children, One Coin, and Eight Thirds of a Flip

Three children, one apple, one fair coin, nothing else in the room. Each child has to end up with exactly the same chance of getting the apple. A coin cuts things in half, then in quarters, then in eighths. It never seems to cut them in thirds, and most people conclude the job cannot be done.

That conclusion is half right, which is what makes the problem interesting. A theorem really does stand in the way, and it has a loophole that costs 8/3 of a flip on average.

What a coin can cut, and what it cannot

Fix the number of flips in advance at some $n$. The result is one of the $2^n$ words in $\{H,T\}^n$, all equally likely. Any procedure that reads those $n$ flips and names a child is a function from words to children, so the first child receives some collection of $m$ words with total probability $m/2^n$. If that is to equal a third, then

and three would have to divide a power of two, which it does not. No procedure with a bounded number of flips gives three equal chances, however clever. The obstruction is the prime factorisation of $2^n$ rather than any lack of ingenuity.

Equation (1) also says what to give up. Nothing in the argument constrains a procedure that sometimes needs more flips than it planned.

Two flips and a bin

Flip the coin twice. There are four words, each with probability a quarter. Give HT to the first child, TH to the second, HH to the third, and if TT comes up, throw the round away and flip twice again. Whichever word finally decides the matter, the three children were equally placed to receive it:

Conditioning is the step that does the work, and it is legitimate for two small reasons. The discard event has probability a quarter, strictly less than one, so conditioning on its complement is well defined. And the three surviving words started out equally likely, so dividing each by the same 3/4 leaves them equal. Symmetry does everything.

Which word goes to which child does not matter, and neither does binning TT rather than another. This is rejection sampling: generate from a distribution you can build, discard the part of the sample space you did not want, keep the conditional law on the rest.

Counting the flips

Let $E$ be the expected number of flips from a fresh start. You always pay two. With probability 1/4 the round is discarded and you are standing exactly where you began, with the same coin and no memory of anything. So

The word doing the work there is “exactly”. First-step analysis with one unknown is valid only when the failing branch returns you to the state you started in, and a discarded pair of flips leaves nothing behind. Where the failing branch lands somewhere subtly different, an equation of the same shape gives a confidently wrong answer.

A second route confirms the number without sharing any machinery. The number of rounds is geometric with success probability 3/4, so it averages 4/3, and each round costs two flips. Two times four thirds is eight thirds.

The tempting wrong answer here is 2.5, which comes from allowing one retry and stopping: $2(1 + \tfrac14) = 2.5$. It is short by a sixth of a flip. The partial sums of equation (4) climb towards 8/3 from below and never arrive, so any truncation undercounts, and stopping after the first retry undercounts by more than a tenth of a flip.

How long it can run

Nothing bounds the number of flips, so the worry is whether the procedure ends at all. It does. The probability of still flipping after $r$ rounds is $4^{-r}$, which goes to zero, so the protocol terminates with probability one though no fixed number of flips would ever have sufficed. The gap between “always finishes” and “finishes within a known number of steps” is the loophole equation (1) left open.

The distribution is friendlier than its average. Three rounds in four finish immediately, so the median cost is two flips rather than 2.667, the standard deviation of the flip count is 4/3, and the chance of needing more than ten flips is $4^{-5} = 1/1024$. A thin tail drags the mean above the median.

The same trick for any number of children

For $k$ children, flip $n = \lceil \log_2 k\rceil$ times, hand $k$ of the $2^n$ words to the children and discard the surplus. Each round costs $n$ flips and succeeds with probability $k/2^n$, so the same renewal argument gives

At $k = 3$ that is $2 \cdot 4/3 = 8/3$, as it should be. The formula also exposes something odd. Five children cost $3 \cdot 8/5 = 4.8$ flips while six cost $3 \cdot 8/6 = 4$, so adding a child makes the job cheaper: three flips give eight words either way, and at five you throw three of them away instead of two. Cost is worst just above a power of two and best exactly on one, where nothing is discarded and $E_k = \log_2 k$.

Is eight thirds the best anyone can do

A uniform choice among three carries $\log_2 3 \approx 1.585$ bits, and one fair flip supplies at most one bit, so no procedure averages fewer than 1.585 flips. Two flips and a bin spends 2.667, which is 68% above that floor, and the waste is visible: every discarded TT sends usable randomness straight to the bin.

Knuth and Yao settled the general question in 1976. Any procedure that consumes fair flips and halts is a binary tree whose leaves carry the outcomes, a leaf at depth $d$ has probability $2^{-d}$, and the cheapest tree puts as many leaves at depth $d$ as the $d$-th binary digit of the target probability calls for. The expansion of a third is $0.010101\ldots$, a one at every even depth, so the optimal cost for three equal outcomes is

Two flips and a bin is therefore optimal. The entropy floor of 1.585 is not reachable with a coin, and the 68% overhead is the price of the problem rather than a flaw in the method. The answer you produce in ten seconds under pressure happens to be the one nobody can improve.

The coincidence does not survive to other values of $k$. Applied to the expansion of a fifth, equation (6) gives 18/5, so 3.6 flips against the 4.8 of naive rejection, and for six children the optimum is 11/3 against 4. Rejection is optimal in two families and nowhere else: when $k$ is a power of two, where nothing is ever discarded, and when $k$ is one less than a power of two, which covers 3, 7, 15 and 31. Everywhere else it wastes flips.

The problem in reverse, with a crooked coin

The same idea run backwards solves a harder-sounding problem. Suppose the coin lands heads with some probability $p$ you neither know nor can measure. Flip it twice, call HT a fair head, call TH a fair tail, and discard both HH and TT. Since the flips are independent,

so the two surviving words are equally likely whatever $p$ happens to be, and conditioning on a decision gives an exactly fair bit. You never learn the bias. What you do need is independence between flips, and that is the assumption that fails on physical devices, where consecutive readings tend to be correlated.

The cost is high. A round decides with probability $2p(1-p)$, so the expected number of flips per fair bit is $1/\big(p(1-p)\big)$, which is 4 for a coin that was already fair and grows without bound as $p$ approaches either end. Four flips for one fair bit from a fair coin is the price of robustness against a bias you never measure.

Both directions rest on the same observation. A fair coin cannot be argued out of producing dyadic probabilities in a fixed number of flips, and it does not need to be, because you are allowed to refuse some of its answers. Rejection buys probabilities no bounded procedure can reach, at the price of a worst case with no ceiling.

Sources and further reading

• The method behind equation (2) — Rejection sampling
• The waiting time in equations (3) and (4) — Geometric distribution
• Why equation (1) rules out a bounded procedure — Dyadic rational
• The 1.585 floor — Entropy (information theory)
• The construction in equation (7), and the correlation caveat — Randomness extractor
• Donald Knuth and Andrew Yao, The complexity of nonuniform random number generation, in Algorithms and Complexity: New Directions and Recent Results, 1976. The source of equation (6).

Both headline numbers were checked in exact rational arithmetic, by enumerating the four two-flip words, and by four hundred thousand seeded games, which measured 2.6652 flips and shares of 0.3325, 0.3326 and 0.3349.