Formal approach to (countable) prisoners and hats problem.

Question

I've found this nice puzzle about AC (I'm referring to the countable infinite case, with two colors). The puzzle has been discussed before on math.SE, but I can't find any description of what is happening from a formal point of view. I'm not really into probability theory, therefore I apologize in advance if I do any mistake or if I can't understand something which is obvious. In particular, I don't know much about infinite sequences of random variables.

Intuitively, the solution is quite paradoxical, and this seems to be the reason: it seems that each prisoner has 50% chance to go free and 50% chance to be killed and nothing (i.e. no strategy) can change this probability, since each prisoner gets no data about his hat from the others and from "the environment". Furthermore, every prisoner's guess is independent from the others. Thus, for the way we intuitively think about probability, it seems that the expected value of prisoners going free should be "a half of $\mathbb N$" (whatever this means). It turns out that (using AC) there exists a strategy which allows all but a finite number of prisoners go free (and for sure this is not "a half of $\mathbb N$", whatever this means).

Now, the above intuitive explanation seems really bugged and unclear to me. For example, even the fact that the prisoners can adopt any kind of strategy seems to me a "violation of the rules" (doesn't that change the probability distribution, since the choice is not random anymore?).

Therefore I would like to understand what is formally happening. If you look at the comments in that page, it seems that many people are quite confused about a formal explanation (someone writes even about non-standard integers). The only comment which does really make sense to me is Terence Tao's one:

This paradox is actually very similar to Banach-Tarski, but involves a violation of additivity of probability rather than additivity of volume.

Consider the case of a finite number $N$ of prisoners, with each hat being assigned independently at random. Your intuition in this case is correct: each prisoner has only a 50% chance of going free. If we sum this probability over all the prisoners and use Fubini’s theorem, we conclude that the expected number of prisoners that go free is $N/2$. So we cannot pull off a trick of the sort described above.

If we have an infinite number of prisoners, with the hats assigned randomly (thus, we are working on the Bernoulli space ${\Bbb Z}_2^{\Bbb N}$), and one uses the strategy coming from the axiom of choice, then the event $E_j$ that the j^th prisoner does not go free is not measurable, but formally has probability $1/2$ in the sense that $E_j$ and its translate $E_j + e_j$ partition ${\Bbb Z}_2^{\Bbb N}$ where $e_j$ is the j^th basis element, or in more prosaic language, if the j^th prisoner’s hat gets switched, this flips whether the prisoner gets to go free or not. The “paradox” is the fact that while the $E_j$ all seem to have probability $1/2$, each element of the event space lies in only finitely many of the $E_j$. This can be seen to violate Fubini’s theorem – if the $E_j$ are all measurable. Of course, the $E_j$ are not measurable, and so one’s intuition on probability should not be trusted here.

So, the trick seems to be that we can't expect probability to be $\sigma$-additive and to measure the probability of every event, at the same time (which seems really similar to Vitali's and Banach-Tarski's arguments). This explanation makes quite sense to me, but I can't fully understand it. How is the event $E_j$ formally defined? And how is Tao precisely using Fubini's theorem in order to get to a contradiction? Could someone give me a formal definition of $E_j$ and a formal proof which shows that, for every $j \in \Bbb N$, $E_j$ is not measurable?

Answer 1

I'm not sure why Terry Tao compared this to the Banach-Tarski paradox. This is, essentially, just a Vitali set.

To see this, note that in the space $2^\omega$ the finite sequences (or rather, eventually zero sequences) are a dense countable set call it $Q$. If you think about $2^\omega$ as a Boolean ring, then symmetric difference is addition, and saying that two sequences are equal up to a finite difference is exactly to say that $x-y=x+y\in Q$.

So the set of representatives is really just a Vitali set. And from there the paradoxical result should be easier to swallow as a familiar "issue". And we see why additivity causes problems.

Answer 2

Here are some details on Tao's comment:

$E_j$'s are defined relative to the strategy coming from the choice function. Let $c: 2^{\omega} \rightarrow 2^{\omega}$ be a choice function where $\mathbb{Z}_2 = 2$: So for every $x \in 2^{\omega}$, $c(x)$ agrees with $x$ on all but finitely many bits and whenever $x, y \in 2^{\omega}$ agree on all but finitely many bits, $c(x) = c(y)$. Now $E_j = \{x \in 2^{\omega}: c(x)(j) \neq x(j) \}$ is the set of hat arrangements on which the $j$th prisoner got his guess wrong. I think that the measurability of a particular $E_j$ depends on the choice of $c$ and for any $N$, you can choose $c$ such that $E_j$ for every $j < N$ is measurable. Still, for every $c$ all but finitely many $E_j$'s are non measurable. You can prove this by using the following: Suppose $\mu(A_n) = 1/2$ for each $n \geq 1$ and every $x \in 2^{\omega}$ belongs to finitely many $A_n$'s. Put $B_n = \bigcup_{k \geq n} A_k$. Then $B_n$'s are decreasing to empty set but $\mu(B_n)$ always stays above $1/2$ which is impossible.