9
$\begingroup$

I was reading this webpage a few months ago about the following problem-

A countable infinite number of prisoners are placed on the natural numbers, facing in the positive direction (ie, everyone can see an infinite number of prisoners). Hats will be placed and each prisoner will be asked what his hat color is. However, to complicate things, prisoners cannot hear previous guesses or whether they were correct. In this new situation, what is the best strategy?

(I won't link the best strategy in case someone wants to give it a go but note that my question is about the solution)

and I recall my friend and I were trying to come up with a formal argument for why the probability is ill-defined. We kept going in circles so we left it in the end.

Recently though I stumbled upon the page and I see Terrence Tao's comment, where I copied the relevant paragraph,

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.

It feels like he concludes the non-measurability of $E_j$ from a violation of Fubini, but I don't see it. Can someone flesh this argument out for me? It has been nagging me for a long time now and I would be very grateful :)

$\endgroup$
3
$\begingroup$

The problem, as far as I can see, is with this sentence

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.

I don't understand it either. Say, we denote by $n(\omega)$ the number of sets where $\omega$ belongs to. Then, by double counting (= Fubini), $$\mathsf E[n(\omega)] = \sum_{j\ge 1} \mathsf P(E_j) = +\infty.$$ However, this in no way contradicts the finiteness of $n(\omega)$.

So I dare to doubt (this part of) Terence Tao's argument, and will give my own, adding more details about the objects involved.

We have $\Omega = \{0,1\}^{\mathbb N} = \{\omega = (\omega_1,\omega_2,\dots)\mid \forall\, i\ge 1\ \omega_{i}\in\{0,1\}\}$. The $\sigma$-algebra $\mathcal F$ of events is generated by cylindrical sets $C_{a_1,a_2,\dots,a_N} = \{\omega\mid \omega_i = a_i,i=1,\dots,N\}$, and the probability $\mathsf P$ is obtained as the extension of $\mathsf P(C_{a_1,\dots,a_N}) = 2^{-N}$.

Define the flipping operators: $$ T_i\omega = (\omega_1,\dots,\omega_{i-1},1-\omega_i,\omega_{i+1}, \omega_{i+2},\dots).$$ Obviously, they preserve the probability $\mathsf P$.

Now assume that all the events $E_j = \{j\text{th prisoner escapes}\}$ are in $\mathcal F$. It is obvious that $T_j E_j = \Omega\setminus E_j$, so $\mathsf P(E_j) = 1/2$, as $T_j$ is $P$-preserving. Thus, by Fatou's lemma, $$ \mathsf P(\text{all but finite number of prisoners escape}) = \mathsf P(\liminf_{j\to\infty} E_j)\le \liminf_{j\to\infty} \mathsf P(E_j) = 1/2.\tag{1} $$ However, the event $E:= \{\text{all but finite number of prisoners escape}\} = \liminf_{j\to\infty} E_j$ is a tail event, that is, it does not depend on any finite number of $\omega_j$'s1. Since $\omega_j$'s are independent, Kolmogorov's 0-1 law implies that $\mathsf P(E) \in\{0,1\}$. Consequently, $\mathsf P(E)=0$, contradicting the sure escape.


1 Here I use that the $j$th prisoner sees only hats in front of him and does not hear what is going on behind him. However, (1) stays valid (thanks to PhoemueX for pointing this out) even in the case where the $j$th prisoner knows everything except his own hat.

$\endgroup$
  • 2
    $\begingroup$ Very nice argument. But I think that the last paragraph is not strictly speaking necessary, since even $P(E) \leq 1/2$ contradicts the sure escape. $\endgroup$ – PhoemueX Sep 11 '15 at 6:09
  • 1
    $\begingroup$ @PhoemueX, you are right. I just wanted to show additionally that the probability of "all but finite escape" cannot even be positive. $\endgroup$ – zhoraster Sep 11 '15 at 6:57
  • $\begingroup$ I'm happy with this answer and could very well be what Terrence had in mind. Thanks a lot! :) $\endgroup$ – Calvin Khor Sep 11 '15 at 7:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.