I’ve seen the problem various places, but I guess its not easily googled. It goes like this:
An infinite collection of gnomes is assembled, say for simplicity one for each integer 0, 1, 2, …. Each gnome is given a hat, whose color they cannot see. Say for simplicity that the colors of the gnomes hats are real numbers in the interval [0, 1) (certainly there is a continuum of possible colors—the problem would work no matter how many or how few colors there were). Each gnome is able to see the colors of every other gnome’s hat, but not his own. After looking around, each gnome guesses the color of his own hat.
The gnomes are allowed to agree on a strategy beforehand. The counterintuitive part is that we allow the gnomes to choose any strategy at all, not just one which they could physically implement. So, in particular, they can all agree on an infinite lookup table which has no finite description and use this lookup table.
The question is: can the gnomes choose a strategy such that all but finitely many gnomes guess the color of their hat correctly?
A simple probabilistic argument shows they cannot. Indeed, if there was only one gnome, and his hat color was chosen randomly, then clearly he can’t know the color of his hat with probability >0 (he’s trying to guess a real number, each of which is correct with probability exactly 0. This is not where the problem is). Clearly, if every gnome is given an independent uniformly random hat color, then each gnome can only guess their own hat color with probability 0. Indeed, suppose for a contradiction that a gnome were able to guess their own hat color with probability >0. Then he could also predict his own hat color with probability >0 even without this auxiliary information—just make up a bunch of fictional gnomes, assign them independent uniformly random hat colors, and use this fictional auxiliary information to make a guess.
Now we can apply linearity of expectation (even if there is some correlation between the accuracy of the gnome’s guesses) to conclude that the expected number of gnomes who guess correctly is zero. (This ISN’T where the flaw is. Summing up a countably infinite number of things is perfectly legal.) So in particular, with probability 1 it must be the case that zero gnomes guess correctly. So if there are infinitely many gnomes, then with probability 1 infinitely many of them guess incorrectly. In particular, there can be no way that all but finitely many gnomes are guaranteed to guess correctly!
On the other hand, the axiom of choice implies that the gnomes do have a strategy that guarantees that all but finitely many gnomes guess correctly. Say that two assignments of hats are equivalent if only finitely many gnomes get different hat colors in the two assignments. Note that this is transitive, reflexive, and symmetric, so it divides up the space of all possible hat assignments into equivalence classes. Moreover, after seeing the hat colors of all of the other gnomes, each gnome knows which equivalence class they are in. So before the game, the gnomes agree on one representative from each equivalence class using the axiom of choice. Then in the game, each gnome figures out which equivalence class the true hat assignment is in and guesses that hat color which he received in the representative assignment from that equivalence class. By construction, the truth differs from the representative of the equivalence class of the truth only in finitely many places, so only finitely many gnomes are incorrect.
Which of these two arguments is wrong? The impossibility argument is wrong, just at the point where I inserted “clearly” (this is a common trend in proofs. If you want to find the error, look for “clearly”...) This argument assumed a false dichotomy: either a gnome guesses his hat correctly with probability >0, or a gnome guesses his hat correctly with probability =0. As it turns out, there is no probability that the gnome guesses his hat correctly. Some events just don’t have probabilities if you believe the axiom of choice. Its very much analogous to the way that Banach-Tarski contradicts our intuition about volume in Euclidean space—if you believe the axiom of choice, you have to accept that some things just don’t have a definite volume.
It seems like you are demonstrating Jaynes point with the very argument you are using to criticize the quotation from him. Construct this argument using a well defined limiting process over strictly finite spaces (if you can), point out the paradox, and then you will have made your point.
They don’t all get the same hat, if thats what you mean. They receive arbitrary hats—some pairs might be the same color, or not. In the probability distribution I claimed was hard, all of the hat colors are different with probability 1.
An internet search for the gnomes example turned up the parent comment as the first hit. Any help?
I’ve seen the problem various places, but I guess its not easily googled. It goes like this:
An infinite collection of gnomes is assembled, say for simplicity one for each integer 0, 1, 2, …. Each gnome is given a hat, whose color they cannot see. Say for simplicity that the colors of the gnomes hats are real numbers in the interval [0, 1) (certainly there is a continuum of possible colors—the problem would work no matter how many or how few colors there were). Each gnome is able to see the colors of every other gnome’s hat, but not his own. After looking around, each gnome guesses the color of his own hat.
The gnomes are allowed to agree on a strategy beforehand. The counterintuitive part is that we allow the gnomes to choose any strategy at all, not just one which they could physically implement. So, in particular, they can all agree on an infinite lookup table which has no finite description and use this lookup table.
The question is: can the gnomes choose a strategy such that all but finitely many gnomes guess the color of their hat correctly?
A simple probabilistic argument shows they cannot. Indeed, if there was only one gnome, and his hat color was chosen randomly, then clearly he can’t know the color of his hat with probability >0 (he’s trying to guess a real number, each of which is correct with probability exactly 0. This is not where the problem is). Clearly, if every gnome is given an independent uniformly random hat color, then each gnome can only guess their own hat color with probability 0. Indeed, suppose for a contradiction that a gnome were able to guess their own hat color with probability >0. Then he could also predict his own hat color with probability >0 even without this auxiliary information—just make up a bunch of fictional gnomes, assign them independent uniformly random hat colors, and use this fictional auxiliary information to make a guess.
Now we can apply linearity of expectation (even if there is some correlation between the accuracy of the gnome’s guesses) to conclude that the expected number of gnomes who guess correctly is zero. (This ISN’T where the flaw is. Summing up a countably infinite number of things is perfectly legal.) So in particular, with probability 1 it must be the case that zero gnomes guess correctly. So if there are infinitely many gnomes, then with probability 1 infinitely many of them guess incorrectly. In particular, there can be no way that all but finitely many gnomes are guaranteed to guess correctly!
On the other hand, the axiom of choice implies that the gnomes do have a strategy that guarantees that all but finitely many gnomes guess correctly. Say that two assignments of hats are equivalent if only finitely many gnomes get different hat colors in the two assignments. Note that this is transitive, reflexive, and symmetric, so it divides up the space of all possible hat assignments into equivalence classes. Moreover, after seeing the hat colors of all of the other gnomes, each gnome knows which equivalence class they are in. So before the game, the gnomes agree on one representative from each equivalence class using the axiom of choice. Then in the game, each gnome figures out which equivalence class the true hat assignment is in and guesses that hat color which he received in the representative assignment from that equivalence class. By construction, the truth differs from the representative of the equivalence class of the truth only in finitely many places, so only finitely many gnomes are incorrect.
Which of these two arguments is wrong? The impossibility argument is wrong, just at the point where I inserted “clearly” (this is a common trend in proofs. If you want to find the error, look for “clearly”...) This argument assumed a false dichotomy: either a gnome guesses his hat correctly with probability >0, or a gnome guesses his hat correctly with probability =0. As it turns out, there is no probability that the gnome guesses his hat correctly. Some events just don’t have probabilities if you believe the axiom of choice. Its very much analogous to the way that Banach-Tarski contradicts our intuition about volume in Euclidean space—if you believe the axiom of choice, you have to accept that some things just don’t have a definite volume.
It seems like you are demonstrating Jaynes point with the very argument you are using to criticize the quotation from him. Construct this argument using a well defined limiting process over strictly finite spaces (if you can), point out the paradox, and then you will have made your point.
Is each hat color different? I didn’t notice where you specified that, if you did?
They don’t all get the same hat, if thats what you mean. They receive arbitrary hats—some pairs might be the same color, or not. In the probability distribution I claimed was hard, all of the hat colors are different with probability 1.