Infinitely many guessers, finitely many wrong

The best-known consequence of the axiom of choice is the Banach–Tarski paradox, a ball cut into pieces and reassembled into two, and it has a reputation for being about geometry. The cleanest demonstration of what the axiom does is not geometric at all. It is a puzzle about hats.

Infinitely many people stand in a line, numbered $1, 2, 3, \dots$, facing forwards. Each wears a black or white hat placed at random. Each can see every hat in front of them — infinitely many — and none behind, and none of their own. At a signal all of them guess their own hat’s colour at once. They may agree a strategy beforehand; once the hats are on, no communication is allowed.

Any one person’s hat is independent of every hat they can see, so each seems to have an even chance of being right, whatever they do. And yet the axiom of choice provides a strategy under which all but finitely many of them are right, whatever the hats.

The finite line, where parity saves all but one #

The infinite puzzle is best approached through two finite ones that bracket it, and the first shows how much a strategy can do.

Put $n$ people in a line, each seeing the hats in front. This time they guess one at a time from the back, and everyone hears every guess. The last person calls not their own colour but a signal: “even” if the number of black hats in front of them is even, “odd” if not. The next person sees all the hats in front of them, so they know how many black hats are ahead of them, and the parity they heard tells them whether their own hat must be black to make the count come out. They call their colour correctly. Each person after them does the same, adjusting for the colours already called.

So with sequential guessing and one bit of shared information, everyone but the first is right, on every one of the $2^n$ hat assignments. The first person is right half the time; their guess was spent transmitting a parity.

The finite ring, where nothing can be gained #

Now take away the order. $n$ people each see every hat but their own and guess simultaneously, with nothing heard.

No strategy can do better on average, and the reason is independence. Whatever person $k$ decides, their guess is a function of the other hats only, and their own hat is independent of those, so on exactly half of all assignments their guess matches. The figure checks this on every assignment for the parity strategy and for strategies chosen at random: each person is right on exactly half, without exception.

What a strategy can do is correlate the outcomes. Under the parity strategy — each person guesses as if the total number of black hats were even — either the total is even and everyone is right, or it is odd and everyone is wrong. The expected number right is $n/2$ either way. The strategy has only arranged that the rightness arrives all at once. That is the lesson the finite puzzle teaches, and the infinite puzzle appears to contradict it.

Sequences that agree in the end #

The infinite strategy starts from a way of grouping hat sequences. Call two infinite sequences of black and white equivalent if they differ in only finitely many places — agreeing from some point on, for ever.

This is an equivalence relation — a sequence is equivalent to itself, the relation is symmetric, and two finite sets of differences combine into a finite set — so it divides all hat sequences into classes. Each class is countable, since a sequence in it is determined by the representative and a finite list of changes, and there are uncountably many classes.

Now the strategy. Before the hats are placed, choose one representative sequence from every class. That is a choice function on uncountably many classes, and no rule supplies one: the classes have no distinguished members, and a representative for each cannot be described. It is exactly an application of the axiom of choice, of the same kind as choosing one point from each class of reals that differ by a rational, which builds a set with no size.

Once the hats are on, person $k$ sees every hat from $k + 1$ onwards. That is enough to know which class the whole sequence is in, because the first $k$ hats, unseen by person $k$, are only finitely many and cannot change the class. So person $k$ looks up the chosen representative of that class and calls its colour at position $k$.

The actual sequence and the representative are in the same class, so they differ in finitely many places. Everyone standing after the last difference calls the representative’s colour, which is their true colour. Only the finitely many people up to the last difference can be wrong. In the first figure there are five of them, all before place fifteen, and everyone from fifteen on is right.

Everyone but one, again #

The infinite strategy can be combined with the finite parity trick, and then it does something even more extreme. Let the people guess in order from the front of the line — person $1$ first — with everyone hearing every guess, and let each see all the hats ahead.

Person $1$ looks at all the hats ahead, determines the class, and finds the chosen representative. The actual sequence from position $2$ onwards differs from the representative in finitely many places, so the number of differences is a finite number, and person $1$ announces whether it is even or odd. Every later person also sees the class, the same representative, and the differences among the hats ahead of them — and knowing the parity announced, and hearing the colours called by those behind them, deduces whether their own hat differs from the representative. Everyone but person $1$ is right, on every assignment of hats.

This is the finite line’s parity trick, made to work on an infinite line by the choice of representatives, which turns an infinite sequence into a finite list of differences whose parity can be counted.

The colours do not matter #

Nothing in the strategy used the fact that hats come in two colours. With a hundred colours, or with a colour for every real number, the argument is word for word the same: group the sequences by finite difference, choose a representative of each class, and have everyone call the representative’s colour at their own place. All but finitely many are still right.

That makes the contrast with the finite ring sharper still. With a continuum of equally likely colours, a single guesser who sees nothing relevant to their own hat has, in any measurable sense, no chance at all of naming it — the probability of hitting one particular real number is zero. Yet the strategy names it correctly for all but finitely many people. Two colours made the paradox look like a coin-flipping curiosity; a continuum of colours shows it is not about luck at all. The strategy never guesses; it looks something up in a table that exists, as a set of size beyond counting, and cannot be read.

What does matter is what each person sees. If everyone saw only finitely many other hats, the class of the sequence would be invisible to all of them — the class depends only on the tail — and the strategy would give nothing. The puzzle works because each guesser sees a tail, and a tail determines a class. Change the pattern of who sees whom, and whether a strategy exists becomes a genuine question about that pattern.

Why it contradicts nothing — and cannot be carried out #

The infinite strategy seems to defy the independence argument from the finite ring. Each person’s hat is independent of what they see, so how can almost all of them be right?

The answer is that the independence argument needs a probability, and the strategy defeats probability. The argument said: person $k$’s guess is a function of the other hats, their own hat is an independent fair coin, so the chance of a match is one half. That step requires the set of hat sequences on which person $k$ is right to have a probability — to be measurable. For the infinite strategy, it is not. The strategy depends on the chosen representatives, and the representatives were picked without any rule, so the sets they define have no size, exactly as the set built by choosing from classes of reals has none.

If those sets did have probabilities, the contradiction would be real. Each person would be right with probability one half, so among the first $N$ people the expected number wrong would be $N/2$, growing without bound — while the strategy guarantees that the number wrong is finite. Probability and the strategy cannot both be applied, and what gives way is the probability. That is why in Solovay’s model of set theory, where every set of reals is measurable and the axiom of choice fails for sets of this size, no such strategy exists: the finite ring’s lesson extends to the infinite line, and every strategy leaves each guesser at even odds.

And the strategy cannot be carried out even with the axiom. The people must agree on a representative for every class, and the agreement cannot be written down, because no definable choice exists. A strategy is supposed to be something followable; this one is a function whose existence is proved and whose values nobody could state. It works in the same sense that a Hamel basis spans the reals and a wild additive function adds: as a theorem about objects that exist, not as a procedure anyone can run.

A finite number that is not bounded #

There is a subtlety in “all but finitely many” worth making explicit. For each assignment of hats the number of wrong guesses is finite — but there is no bound on it that works for every assignment. A sequence can differ from its class’s representative in the first million places and then agree for ever; in that case up to a million guessers are wrong.

So the strategy does not say “at most ten people are wrong”. It says that for every hat assignment there is a point beyond which everyone is right, with the point depending on the assignment. That is exactly the shape of the statement the parity trick needs — a finite number of differences, whose parity exists — and exactly the shape that makes a probability impossible, since no finite bound would survive a random placement of hats.

The same shape appears throughout the theory of infinite sequences: two sequences that eventually agree define the same limit, the same tail behaviour, the same answer to any question that ignores finitely many terms. The hat strategy exploits that the class of a sequence is determined by its tail, and that a guesser who sees the tail knows the class.

Predicting the present from the past #

The same move has a continuous version that is, if anything, stranger, and it was published by Christopher Hardin and Alan Taylor in 2008 under the title A peculiar connection between the axiom of choice and predicting the future.

Replace the line of people by time, and the hats by the values of an arbitrary function $f$ from the real numbers to the real numbers — no continuity, no pattern, anything at all. At each moment $t$, a predictor sees the values of $f$ at every earlier moment and must guess $f(t)$. Hardin and Taylor showed that, given the axiom of choice, there is a single prediction rule that, for every function $f$, is right at all but a very small set of moments — a set that is well-ordered by time, so countable, and so of measure zero.

The proof is the hat strategy transplanted. Well-order all functions, which the axiom of choice permits; at time $t$, look at the functions that agree with $f$ at every moment before $t$, and predict the value at $t$ of the first of them in the well-ordering. That first function changes only at moments when the prediction was wrong, and the moments where a well-ordered sequence of functions changes form a well-ordered set of times.

It sounds as though it overturns everything known about prediction. It overturns nothing, for the reason the hat strategy overturns nothing: the rule cannot be written down, the sets it succeeds on are not measurable, and it says nothing about any process anybody can describe. The limits on prediction that matter in practice — a difference too small to draw growing until it dominates — are limits on what can be computed from measurements, and a rule that exists only by the axiom of choice computes nothing.

What the pictures cannot show #

The choice. Every figure shows a representative, and each representative shown was generated by a seeded random process for this page, which is a rule. The strategy needs a representative for every one of uncountably many classes, chosen without a rule; no figure can show that, because drawing one would be defining one.

The infinite line. The figures show forty hats. The class of a sequence depends only on its infinite tail, which no finite window reveals: the first forty hats of a sequence are consistent with every class. The guessers in the story see the infinitely many hats ahead; a reader of the figure sees a finite prefix and has to take the tail on trust.

The failure of probability. The claim that the success sets are non-measurable is proved by the contradiction above, not observed. The finite ring’s figure shows what measurable strategies do — exactly half right for each person — and the infinite strategy is what a non-measurable one does instead; nothing can be drawn of the non-measurable sets themselves.

Still open: how little choice the puzzle needs #

The strategy uses a choice function on the classes of eventually-equal sequences, which is weaker than the full axiom of choice. Exactly how much weaker is a live question. The existence of a winning strategy for the infinite hat puzzle implies the existence of a non-measurable set of reals, so it cannot be proved in set theory without some choice; whether it is equivalent to the existence of a non-measurable set, or strictly stronger, depends on the variant of the puzzle and has been settled for some variants only.

The puzzle also has many generalisations — more colours, people who see only some of the others, guessers arranged in more complicated patterns — and Christopher Hardin and Alan Taylor’s book on the subject in 2013 organised a large collection of them. Which patterns of visibility allow all but finitely many to be right, and which allow only positive fractions, is a classification with open cases. What all of them share is the move drawn here: group the possible worlds into classes that the visible part of the world identifies, choose a representative of each, and act as if the world were its representative.

A strategy that exists and cannot be followed #

Finite hat puzzles show the two things a strategy can do: transmit information, as the parity signal does on a line, and correlate outcomes, as the parity guess does in a ring. Neither can beat the even odds that independence imposes on each individual guess.

The infinite puzzle beats them anyway, by grouping the possible hat sequences into classes that differ only finitely, choosing one representative from each, and having everyone assume the world is its representative. All but finitely many are then right, with no appeal to luck. The price is that the choice has no rule, the strategy cannot be written down, and the events it controls have no probabilities — which is the same price the axiom of choice exacts everywhere it is used, in a setting small enough to see the whole bill.