Five Coins Against Four Is Exactly a Coin Flip

You toss five fair coins, I toss four. You win if you get strictly more heads than I do, and a tie goes to me. What is your probability of winning?

The extra coin looks like it must be worth something, so almost everyone answers a number above a half, and the more careful the person the more they want to compute the number rather than guess it. It is exactly a half. Not approximately, not a half to three decimal places. Exactly $256$ of the $2^9 = 512$ equally likely outcomes are yours.

The proof that needs no counting

The short argument uses the one asymmetry in the problem, which is the thing that looks like it should make the answer asymmetric. You hold exactly one coin more than I do. So the total number of coins is odd, nine, and no matter how they land the two of us cannot be level on both heads and tails at once.

Write $X$ for your heads out of five and $Y$ for mine out of four, and write $X'$ and $Y'$ for the tails, so that $X' = 5 - X$ and $Y' = 4 - Y$. Then

Read that slowly, because it is the whole article. The event "you do not have strictly more heads" and the event "you have strictly more tails" are not merely equally likely. They are the same event, holding on exactly the same outcomes. Every outcome falls on one side or the other, and never on both.

So $P(X > Y) = \tfrac{1}{2}$, and the argument never touches a binomial coefficient. Fairness enters in exactly one place, which is that the flip-everything map preserves probability. If the coins were biased the map would still be a bijection of outcomes, but the two halves would no longer carry the same probability mass.

The same answer, one coin at a time

The second route is the one most people find first, and it is worth having because it explains where the extra coin goes. Set the fifth coin aside and match four against four.

Two hands of four coins are exchangeable, so being ahead is exactly as likely as being behind. Counting over the $2^8 = 256$ pairs of hands, you are ahead in $93$, level in $70$, and behind in $93$. The tie count is the sum of the squares of the binomial coefficients of four,

which is Vandermonde's identity: pairing your $j$ heads against my $j$ heads is the same as choosing four objects from eight.

Now bring the fifth coin back and ask what it can possibly do.

• If you are already ahead after four against four, the fifth coin cannot take that away. You win whatever it shows.
• If you are behind, you are behind by at least one, and one extra coin cannot close a gap of one and overtake. You lose whatever it shows.
• If you are level, the fifth coin decides, and it is a fair coin.

What the fifth coin actually buys

There is a tempting way to state the punchline that happens to be false: the extra coin is worth nothing. It is worth a great deal. Without it the game is four against four with ties going to me, and your winning chance is $93/256$, which is about $36.3\%$. The fifth coin lifts that to fifty percent, so it is worth nearly fourteen percentage points.

What it buys none of is an edge. It repairs a handicap you had not noticed you were carrying, which is the tie rule, and it repairs it exactly. Two effects of the same size are pulling in opposite directions, and the coincidence in this problem is that the extra coin cancels the tie rule precisely rather than approximately.

Two hypotheses you cannot drop

The tie rule is load-bearing. If ties counted as wins for you, the five-coin against four-coin game would give you $191/256 \approx 0.746$, and in the four-against-four game "ahead or level" is $163/256$. The word strictly in the statement is doing real work, and a candidate who quotes a half without having noticed it has been lucky.

Fairness is load-bearing too, and this rules out the suspicion that the whole thing is a counting artefact. With heads landing with probability $3/5$ on every coin, the same game gives you

which is above a half, and the extra coin now really is an edge, because it is an extra draw on a favourable coin. The elegance of the fair case comes from the flip map, and a biased coin has no flip map.

The general statement

Nothing above used the numbers four and five except to have them differ by one. The identity in (1) reads the same way for $n+1$ coins against $n$, since the total of $2n+1$ coins is odd, so

The case $n = 0$ is a good check on whether the statement means anything: you toss one coin, I toss none, and you win when you get a head. That is a half, and it is the same theorem.

Two coins more is a different story. The flip map sends "strictly more heads" to "strictly more tails", but with an even total those two events no longer partition the space, because a tie is possible, so the map gives a symmetry without giving a value. There the extra coins do buy an edge, and you have to count.

Sources and further reading

• The distribution of heads in each hand — Binomial distribution
• The step in equation (1) — Complementary event
• The identity behind the seventy ties — Vandermonde's identity
• Why a bijection settles a probability — Bijective proof

Nothing in this article rests on sampling. The primary check enumerated all $512$ outcomes and counted, confirming both that you win in $256$of them and, outcome by outcome, that exactly one of "strictly more heads" and "strictly more tails" holds every time. Every probability was carried as an exact rational rather than a float. The generalisation in (5) was enumerated for $n = 0$ up to $n = 6$, and a seeded run of four hundred thousand simulated games landed at $0.49948$, which is a sanity check on the counting rather than the source of the answer.