3.6 Flips, Not 4, and the Beautiful Argument That Says Otherwise

Four boxes stand in a row and a pebble sits in the first one. Flip a fair coin. Heads moves the pebble forward one box, tails forward two. If a move would carry it past box 4, the pebble goes back to box 1 instead. The game stops the moment the pebble lands exactly on box 4. How many flips does that take on average?

There is a two-line argument for this problem that produces the answer 4, and it is good enough that it has been printed as the solution. It is wrong. The answer is $18/5 = 3.6$. What makes the problem worth an article rather than a footnote is that the wrong argument is not a slip. Every sentence in it is true except the one nobody writes down.

The argument that gives 4

Group the flips into rounds of two. From box 1 there are four equally likely two-flip outcomes. Heads then tails puts the pebble on box 4, since $1 + 1 + 2 = 4$. Tails then heads also puts it on box 4. So a round finishes the game with probability $1/2$, and that number is exactly right.

Now the shortcut. If half of all rounds finish, the game takes two rounds on average, so it takes four flips. Written as an equation, with $E$ the average number of flips from the start:

You pay two flips no matter what, and with probability $1/2$ you find yourself starting over. That is the renewal argument, and for a great many problems it is the fastest correct route there is. Roll a die until a six appears and the same reasoning gives $E = 1 + \tfrac{5}{6}E = 6$, which is the truth.

The failed round does not start over

Look at the other two outcomes. Tails then tails moves the pebble to box 3 and then tries to move it to box 5, which overshoots, so the pebble goes back to box 1. That half of the failure really is a fresh start. Heads then heads is different: the pebble walks to box 2 and then to box 3, where it is one heads away from finishing. It kept its progress.

So equation (1) charges the pebble a full fresh start for an outcome that left it one flip from the door. It over-prices half of the failures. The answer it returns is too big, and the error turns out to be exactly $2/5$ of a flip.

Three unknowns instead of one

The reliable route is to stop thinking about rounds and give every position its own unknown. Write $E_k$ for the average number of flips still needed when the pebble sits in box $k$, so $E_4 = 0$. One flip is spent, and then the pebble is somewhere new:

The middle equation loses a term because tails from box 2 lands on box 4 and ends the game. The right-hand equation is the interesting one: tails from box 3 would reach box 5, so the pebble is sent home and pays $E_1$ all over again. Box 2 is the only place where an overshoot is impossible, which is why the restart arrow in this problem only ever leaves box 3.

Substitute $E_3 = 1 + E_1/2$ into $E_2$ to get $E_2 = \tfrac{3}{2} + E_1/4$, then feed both into the first equation: $E_1 = \tfrac{9}{4} + \tfrac{3}{8}E_1$, so $\tfrac{5}{8}E_1 = \tfrac{9}{4}$.

There is the number the shortcut needed and did not have. Box 3 is worth $14/5$, cheaper than the start at $18/5$, and keeping a quarter of the probability mass in that cheaper place is what drags the answer below 4.

Repairing the shortcut without abandoning it

The round idea can be saved. Every round is exactly two flips, and after it the pebble has finished with probability $1/2$, sits in box 3 with probability $1/4$, or sits in box 1 with probability $1/4$. Price each branch at its own value:

Same round, same two flips, and now the answer agrees with equation (3). Comparing (1) with (4) shows exactly what the shortcut did: it wrote $\tfrac{1}{2}E_1$ where the honest bookkeeping wants $\tfrac{1}{4}E_1 + \tfrac{1}{4}E_3$.

How long the game actually runs

Pushing the exact distribution forward in fractions gives the chance that the finishing flip is the second, third, fourth and so on. The game ends on flip two half the time, and the tail decays geometrically after that.

Summing $t \cdot \Pr(T = t)$ over this distribution returns $18/5$ exactly, which is a check worth doing because it shares no algebra with the linear system. Notice also that the median is 2 while the mean is 3.6. The restart from box 3 is rare and expensive, and it is the whole reason the average sits so far above the typical game.

The answer depends on the rule you read

This problem is unusually sensitive to how the overshoot is phrased, so it is worth being explicit. Three readings, three different answers:

• An overshoot sends the pebble back to box 1, which is the version above: $18/5 = 3.6$.
• An overshoot is simply forbidden and the pebble stays put, wasting the flip: $3$ exactly.
• The game ends as soon as the pebble reaches or passes box 4: $9/4 = 2.25$.

If someone hands you this problem out loud, the overshoot rule is the thing to pin down before writing anything. Two of those three answers are perfectly defensible solutions to a problem you were not asked.

More boxes

With $n$ boxes and the same rules, the same first-step method gives a system of $n-1$ equations. The value from box 1 climbs unevenly because the restart penalty depends on how the parities line up:

No round-based shortcut survives any of these, for the same reason it failed at $n = 4$. What does survive is the method. Name one unknown per state, write one equation per state, and let the algebra find out which states are cheap.

The chain here is an absorbing Markov chain with three transient states, and equation (2) is the standard system for its expected absorption time. Nothing in the derivation needed that vocabulary, which is a good sign about the derivation. But knowing the name is useful, because the moment a problem has more than four or five states the matrix form is faster than hand elimination.

Sources and further reading

• The general machinery behind equation (2) — Absorbing Markov chain
• The shortcut in its correct habitat, where a failed round really does erase everything — Renewal theory
• The definition of the quantity being computed — Expected value

Every number here was checked three ways before publication: the exact distribution of the finishing flip in rational arithmetic, the linear system eliminated by hand, and four million seeded plays of the literal rules, which came back at 3.5992.