Probabilities in a riddle involving axiom of choice

Question

The question is about a modification of the following riddle (you can think about it before reading the answer if you like riddles, but that's not the point of my question):

The Riddle: We assume there is an infinite sequence of boxes, numbered $0,1,2,\dots$. Each box contains a real number. No hypothesis is made on how the real numbers are chosen. You are a team of 100 mathematicians, and the challenge is the following: each mathematician can open as many boxes as he wants, even infinitely many, but then he has to guess the content of a box he has not opened. Then all boxes are closed, and the next mathematician can play. There is no communication between mathematicians after the game has started, but they can agree on a strategy beforehand.

You have to devise a strategy such that at most one mathematician fails. Axiom of choice is allowed.

The Answer: If $\vec u=(u_n)_{n\in\mathbb N}$ and $\vec v=(v_n)_{n\in\mathbb N}$ are sequences of real numbers, we say that $\vec u\approx \vec v$ if there is $M$ such that for all $n\geq M$, $u_n=v_n$. Then $\approx$ is an equivalence relation, and we can use the axiom of choice to choose one representative per equivalence class. The strategy is the following: mathematicians are numbered from $0$ to $99$, and the sequence of boxes $(u_n)_{n\in\mathbb N}$ is split into $100$ sequences of the form $\vec u_i=(u_{100n+i})_{n\in\mathbb N}$ with $0\leq i\leq 99$. Mathematician number $i$ will look at all sequences $\vec u_j$ with $j\neq i$, and for each sequence, it will compute the index $M_j$ from which the sequence matches the representative of its $\approx$-class. He then takes $M$ to be the maximum of the $M_j+1$ and looks at the sequence $\vec u_i$ starting at this $M$. He can deduce the $\approx$-class of the sequence $\vec u_i$, and guesses that $u_{M-1}$ matches the representive. At most one mathematician will be wrong: the one who has the number $i$ with $M_i$ maximal.

The Modification: I would find the riddle even more puzzling if instead of 100 mathematicians, there was just one, who has to open the boxes he wants and then guess the content of a closed box. He can choose randomly a number $i$ between $0$ and $99$, and play the role of mathematician number $i$. In fact, he can first choose any bound $N$ instead of $100$, and then play the game, with only probability $1/N$ to be wrong. In this context, does it make sense to say "guess the content of a box with arbitrarily high probability"? I think it is ok, because the only probability measure we need is uniform probability on $\{0,1,\dots,N-1\}$, but other people argue it's not ok, because we would need to define a measure on sequences, and moreover axiom of choice messes everything up.

Answer 1

The probabilistic reasoning depends on a conglomerability assumption, namely that given a fixed sequence $\vec u$, the probability of guessing correctly is $(n-1)/n$, then for a randomly selected sequence, the probability of guessing correctly is $(n-1)/n$. But we have no reason to think the event of guessing correctly is measurable with respect to the probability measure induced by the random choice of sequence and index $i$, and we have no reason to think that the conglomerability assumption is appropriate.

A quick way to see that the conglomerability assumption is going to be dubious is to consider the analogy of the Brown-Freiling argument against the Continuum Hypothesis (see here for a discussion). Assume CH. Let $\prec$ be a well-order of $[0,1]$. Suppose $X$ and $Y$ are i.i.d. uniformly distributed on $[0,1]$. Consider the question of which variable is bigger. Fix a value $y\in [0,1]$ for $Y$. Then $P(X\preceq y)=0$, since there are only countably many points $\prec$-prior to $y$. By a conglomerability assumption, we could then conclude that $P(X\le Y)=0$, which would be absurd as the same reasoning would also show that $P(Y\le X)=0$. The argument fallaciously assumes conglomerability. We are neither justified in concluding that $P(X\le Y)=0$, nor that $\{ X \le Y \}$ is measurable (though for each fixed $y$, $\{ X \le y \}$ is measurable). And indeed it's not measurable: for were it measurable, we could use Fubini to conclude that it has null probability. Note that one can repeat the argument without CH but instead using an extension of Lebesgue measure that assigns null probability to every subset of cardinality $<\mathfrak c$, so clearly there is no refutation of CH here.

Here's another analogy: By the Hausdorff Paradox, decompose $S^2-D$ for a countable $D$ into disjoint $A_1,A_2,A_3$, where $A_1,A_2,A_3,A_1\cup A_2$ are all isometrically equivalent. Suppose a point $X$ is uniformly chosen in $S^2$. (I will ignore $D$ from now on, since it has zero measure. If you like, you can assume that the uniform choice is done so $X$ cannot lie in $D$.) Let $i$ be a random index in $\{1,2,3\}$, independent of $X$. How likely is it that the $X \in A_i$? It's very tempting to say that it's got to be $1/3$. Any fixed value of $X$ in $S^2$ is in one of the three subsets, after all, and so if we choose a random index $i$, surely we have probability $1/3$ that it'll be in $A_i$. Of course this easily leads to paradox. But we are not in fact entitled to assume that $J = \{ \omega : X(\omega) \in A_{i(\omega)} \}$ is measurable. (In fact, it's easy to see that it's not measurable.)

Let's go back to the riddle. Suppose $\vec u$ is chosen randomly. The most natural option is that it is a nontrivial i.i.d. sequence $(u_k)$, independent of the random index $i$ which is uniformly distributed over $[100]=\{0,...,99\}$. In general, $M_j$ will be nonmeasurable (one can prove this in at least some cases). We likewise have no reason to think that $M$ is measurable. But without measurability, we can't make sense of talk of the probability that the guess will be correct.

Here's an amusing thing that may help see how measurability enters into these things. Consider a single sequence of infinitely many independent fair coin flips. Our state space is $\Omega=\{0,1\}^{\mathbb N}$, corresponding to an infinite sequence $(X_i)_{i=0}^\infty$ of i.i.d.r.v.s with $P(X_i=1)=P(X_i=0)=1/2$. Start with $P$ being the completion of the natural product measure on $\Omega$.

Can you guess the first coin flip on the basis of all the others? You might think: "Of course not! No matter what function from the values of flips $X_1,X_2,...$ to $\{0,1\}$ is chosen, the probability that the value of the function equals $X_0$ is going to be $1/2$."

That's a fine argument assuming the function is measurable. But what if it's not? Here is a strategy: Check if $X_1,X_2,...$ fit with the relevant representative. If so, then guess according to the representative. If not, then guess $\pi$. (Yes, I realize that $\pi\notin\{0,1\}$.) Intuitively this seems a really dumb strategy. After all, we're surely unlikely to luck out and get $X_1,X_2,...$ to fit with the representative, and even if they do, the chance that $X_0$ will match it, given the rest of the sequence, seems to be only $1/2$.

But if you choose shift-invariant representatives (i.e., $r([\tau \vec u])=\tau r([\vec u])$ when $(\tau\vec u)_n = \omega$ is a left sequence shift--by Zorn, such a choice is possible), then the outer $P$-measure of the set of representatives is equal to $1$. So there is an extension $P'$ of $P$ such that $P'$-almost surely the dumb strategy works. Just let $P'$ be an extension on which the set of representatives has measure $1$ and note that the dumb strategy works on the set of representatives.

Answer 2

The counter-intuitiveness of the axiom of choice is clouding the real issue here ( I think). If I have a secret number and you try to guess a larger one, what are your odds of success? is there a way to make them better (if you have $99$ friends). You have only finitely many ways to fail and infinitely many to succeed, but we can't really assign a probability. That is also behind this puzzle

Going back to the given problem, suppose that each box has a guard. At a certain time each guard sees the contents of every other box then guesses the contents of their own. Under AoC with an agreed set of equivalence class representatives and the familiar protocol we know that all but finitely many will be correct. That is strange but we are used to this consequence of the axiom of choice. If you have full knowledge of all this and are required to become the guard for a box of your choice (after looking into as many other boxes as you wish) can we say that you are certain to make a correct guess? Not really.

The situation in the question above seems clearer to me if we stipulate ahead of time that all but finitely many boxes contain $0$ (no assumption , other than finiteness on which the exceptions are). If there are $100$ potential guards who are friends, can they be sure that each can pick a box and guess $0$ (what else can they do?) with at least $99$ correct? yes, as before split the boxes into $100$ subsequences, person $k$ looks at all the boxes in every subsequence other than his own then chooses a box further than the last non-zero box in every other subsequence.

If you are one member of this set of $100$ friends are your odds of being correct (when you guess $0$) improved $100$ fold, or at all? Not really.

Essentially $100$ people are assigned hidden integers and must name an integer greater than their assigned integer (so only finitely ways to fail and infinitely many to succeed!). If each person can see all the other integers then only one will fail.

In other words, given AoC, we may assume a known set of coset representatives such that every real sequence is is (uniquely) the termwise sum of a coset representative and a sequence with only finitely many non-zero terms. Once we accept that (which is weird but familiar) there is no loss in saying that the chosen sequence is in a certain coset (so why not the coset of the zero sequence)?

Answer 3

I also like this version of the riddle. To answer the actual question though, I would say that it is not possible to guess incorrectly with probability only $\frac{1}{N}$, even for $N=2$. In order for such a question to make sense, it is necessary to put a probability measure on the space of functions $f: \mathbb{N} \to \mathbb{R}$. Note that to execute your proposed strategy, we only need a uniform measure on $\{1, \dots, N\}$, but to make sense of the phrase it fails with probability at most $\frac{1}{N}$, we need a measure on the space of all outcomes. The answer will be different depending on what probability space is chosen of course.

Here's a concrete choice for a probability space that shows that your proposal will fail. Suppose that for each index $i$ we sample a real number $X_i$ from the normal distribution so that the $X_i$s are independent random variables. If there is only person, no matter which boxes they view, they gain no information about the un-opened boxes due to independence. Thus, their probability of guessing correctly is actually 0, not $\frac{N-1}{N}$, say.

If it were somehow possible to put a 'uniform' measure on the space of all outcomes, then indeed one could guess correctly with arbitrarily high precision, but such a measure doesn't exist.

Answer 4

I learned the puzzle only recently in the following variant, which I find even more amusing — and so I decided to share it here as a separate answer. The following was given to first-year undergrad students (!) as a problem in math logic course, and my friend (who happens to be one of those poor students) asked me for assistance.

Ann chooses a real function $f : \mathbb R \to \mathbb R$. Then Bob chooses a real number $a$ and tells Ann the value of $a$. Ann then reveals Bob the restriction of $f$ to $\mathbb R \setminus \{a\}$. Prove that Bob can guess the value of $f(a)$ with probability one.

The proposed (wrong!) solution was the following. Define the equivalence relation $\approx$ on the set of real functions as usual: $f \approx g$ if $f = g$ outside of a finite set. Fix a representative for each equivalence class. The strategy for Bob is as follows: he draws $a$ randomly so that the distribution of $a$ is continuous, and when Ann tells Bob the restriction $f$ to $\mathbb R \setminus \{a\}$, Bob knows the representative $g$ of the equivalence class of $f$, so he guesses $g(a)$. No matter what the function $f$ is, there are only finitely many values of $a$ which make Bob guess wrong, so his guess is correct with probability one.

---

As an addendum to Alexander Pruss's excellent answer, let me add two comments, which may possibly clarify some issues or questions raised in the comments to that answer.

Comment 1. It has been already pointed out that this question is very similar to Brown–Freiling argument against continuum hypothesis. Another, more widely known paradox similar to this one is the two envelopes problem.

In the two envelopes problem we cannot conclude about the unconditional expectation because it is not convergent. Here the reason is different: lack of measurability, but the idea is essentially the same.

Comment 2. In a series of comments, Denis asks (in the Ann–Bob language introduced abog) whether it is possible to make the notion of "Bob tells his strategy — then Ann chooses her function — then Bob applies his strategy" rigorous in probabilistic sense. No, it is not.

The reason was already discussed in Alexander Pruss's answers to these comments, but let me try to be more explicit here. Denis's arguments are of the form: The conditional probability of "Bob guessing right" given "Ann's choice is f" is always one, so no matter what Ann does, the overall probability of "Bob guessing right" is one. And this is true, but only if "Bob guessing right" is an event, and "Ann's choice" is a random variable. And if Ann decides to choose $f$ to be, say, a collection of i.i.d. random variables $f(x)$, we quickly run into measurability problems.

A more philosophical explanation is the following. Probabilities are all about frequencies, so, in particular, we expect that the experiment can be repeated indefinitely. In order to repeat the above game, one really needs to specify the way Ann chooses her function $f$.

Answer 5

I am a heavy user of the Axiom of Choice and I am comfortable with the consequences of it. My take on this riddle is that there is no problem with the proposed strategy as Mathematics, but it is unrealistic because it is impossible to implement it in reality, as I argue below. Axiomatic Mathematics is all about (non-)existence of sets with such and such properties and the way of implementing it is not a part of it. More precisely, the trick of this thought experiment is not in the Axiom of Choice nor in the way probability is used, but in covertly assuming an ability to do the impracticable. Thus the riddle is not as counter-intuitive (to me) as it may appear.

Imagine how possibly anybody could make paper instructions out of this strategy or how possibly anybody could perform this strategy in a finite time. In the real world, any single action takes a positive time. Even a mathematician can perform at most countably many actions in a finite time. However, the proposed strategy requires uncountably many actions and hence not practicable in a finite time. (I believe that one can actually prove that there is no practicable (=countable) strategy to solve this riddle.) It is not a big surprise that one can foresee the unseeable if they has the ability of doing what cannot be done in a finite time.

By the way, the Axiom of Choice has real applications to our daily life. For example, countable additivity of the Lebesgue measure is used almost everywhere in differential equations. It may be possible but will be unnecessarily painful to develop a theory for continuous objects without the Axiom of Choice.