34
$\begingroup$

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 Anwser: 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 representant by 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 representant 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 representant. 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.

$\endgroup$
17
  • $\begingroup$ It is because each sequence $\vec u_i$ matches its representant $\vec v_i$ starting in $M_i$. Therefore, if a mathematician starts looking at $\vec u_i$ from position $M> M_i$, he will be able to guess what is $(u_i)_{M-1}$, since it is equal to $(v_i)_{M-1}$, and since he knows $\vec v_i$. $\endgroup$
    – Denis
    Dec 9, 2013 at 16:35
  • 1
    $\begingroup$ I really like this version of the riddle! It is already surprising when using only 2, rather than 100. $\endgroup$ Dec 9, 2013 at 16:36
  • 1
    $\begingroup$ Yes I find it's one of the most surprising use of the axiom of choice :) $\endgroup$
    – Denis
    Dec 9, 2013 at 16:39
  • 4
    $\begingroup$ This is beyond mind-boggling! What is the source of this riddle? Did you come up with it? I'll probably want to write about it at some point. The version with infinitely many people (where all but finitely many guess correctly) is described on Michael O'Connor's blog, xorshammer.com/2008/08/23/set-theory-and-weather-prediction and in C.S. Hardin and A.D. Taylor, "A Peculiar Connection Between the Axiom of Choice and Predicting the Future", Am. Math. Monthly 115, (February 2008), 91-96, where it is attributed to Yuval Gabay and Michael O'Connor. $\endgroup$ Dec 17, 2013 at 12:47
  • 2
    $\begingroup$ @JohanWästlund Even if there are countably infinite mathematicians, a strategy exists such that at most one mathematician fails. See Can an infinite number of mathematicians guess the number in a box with only one error? $\endgroup$ Jun 21, 2022 at 22:38

5 Answers 5

17
$\begingroup$

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.

$\endgroup$
13
  • 1
    $\begingroup$ In the probabilistic variant, I don't see that you can win against any strategy of the opponent. If we are making no probabilistic assumptions whatsoever, then in particular we are not assuming that our choice of index $i$ is independent of the opponent's choice of numbers. $\endgroup$ Dec 17, 2013 at 14:47
  • 1
    $\begingroup$ I was assuming that "independently" has the meaning it does in probability theory ($P(AB)=P(A)P(B)$ and generalizations for $\sigma$-fields). But that does require a probabilistic description of the opponent's choice. Of course, one could mean "independently" here in some non-mathematical causal sense. (And there may be philosophical reason for doing this: fitelson.org/doi.pdf ) Still, mixing the probabilistic with nonprobabilistic concepts might lead to some difficulties, though. $\endgroup$ Dec 18, 2013 at 15:21
  • 1
    $\begingroup$ What we have then is this: For each fixed opponent strategy, if $i$ is chosen uniformly independently of that strategy (where the "independently" here isn't in the probabilistic sense), we win with probability at least $(n-1)/n$. That's right. But now the question is whether we can translate this to a statement without the conditional "For each fixed opponent strategy". $\endgroup$ Dec 19, 2013 at 15:05
  • 1
    $\begingroup$ But the opponent can win by foreseeing what which value of i we're going to choose and which choice of representatives we'll make. I suppose we would ban foresight of $i$? $\endgroup$ Dec 19, 2013 at 21:25
  • 1
    $\begingroup$ yes the order would be: 1)describe the probabilistic strategy 2)opponent choses a sequence 3)probabilistic variable i is instanciated $\endgroup$
    – Denis
    Dec 19, 2013 at 23:02
3
$\begingroup$

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)?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
11
  • $\begingroup$ I'm not sure I agree. I think we can make sense of "fails with probability at most $1/N$", by saying that for all fixed sequence, the probability (which comes from the strategy) of failing is at most $1/N$. Moreover I don't understand your counter-example, because no matter how you choose the sequence, the strategy still has $\frac{N-1}{N}$ chance of guessing correctly. $\endgroup$
    – Denis
    Dec 9, 2013 at 17:41
  • 7
    $\begingroup$ That "for [each] fixed sequence, the probability of failing is at most $1/N$" basically says something like that $P(F|S)=1/N$ for each sequence $S$. But you can't infer that $P(F)=1/N$ unless you've got a probability measure on the whole space conglomerable with respect to the partition induced by the $S$s. (I bet the probabilities are going to be at best finitely additive, and if we have merely finitely additive probabilities, we can have failures of conglomerability.) I am reminded of the Brown-Freiling argument against CH (mdpi.com/2073-8994/3/3/636). $\endgroup$ Dec 9, 2013 at 17:53
  • $\begingroup$ I don't get why we need a probability measure on the sequences. Why can't we say that "winning with probability at least $\frac{N-1}{N}$" means that no matter the sequence chosen by an adversary opponent, we will win with probability at least $\frac{N-1}{N}$? $\endgroup$
    – Denis
    Dec 9, 2013 at 19:21
  • $\begingroup$ I now think the i.i.d. normally distributed counterexample doesn't work. The problem is that you're looking at a "randomly" indexed variable (I guess something like $X_{100M + i}$, where $i$ is randomly distributed over $\{0,...,99\}$ and $M$ is chosen by the algorithm), but the "random" index may not be a measurable function ($i$ is measurable, but $M$ presumably won't be). $\endgroup$ Dec 9, 2013 at 19:24
  • 1
    $\begingroup$ Perhaps it helps to clarify things to point out that if the whole sequence really is fixed, then there is an even better strategy: just announce the values of all the boxes without looking at any of them. $\endgroup$ Dec 9, 2013 at 20:21
1
$\begingroup$

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$.

$\endgroup$
6
  • $\begingroup$ Thanks for your answer and for this interesting variant. Unfortunately I must have some kind of block in my thinking, I still don't see why it is not correct to talk about probabilities in a game formulation. In the game you describe, when Bob plays his last move (applying his strategy), he will win with probability 1, and this probability is only computed in the context of the moves already played, ie with a fixed function $f$. The only source of randomness here is Bob's strategy. Maybe the misunderstanding is on whether a stronger claim can be made about an "overall" probability for all f. $\endgroup$
    – Denis
    Dec 13, 2022 at 23:40
  • $\begingroup$ My initial claim was about this "overall" formulation, and I understand now why it is flawed, but I was under the impression that specifying the problem as a game allows to avoid this issue, by explicitely quantifying on all functions in the formulation of the problem and specifying that the probabilities are computed only after this quantification. $\endgroup$
    – Denis
    Dec 13, 2022 at 23:48
  • $\begingroup$ I tried to address this in the last paragraph. If the experiment is repeated, does Ann keep choosing the same function $f$? If she does, then of course you can rigorously say that Bob guesses correctly with probability one, but in this case picking $a = 0$ and "guessing" the real value $f(0)$ is an equally good strategy for Bob. If she does not, then we hit the question of measurability. $\endgroup$ Dec 13, 2022 at 23:57
  • $\begingroup$ Yes I forgot to mention that we want to make this a game of incomplete information in order to make sense of it. So Ann chooses $f$, but Bob does not know what it is, nevertheless he has a probabilistic strategy working with probability 1. $\endgroup$
    – Denis
    Dec 14, 2022 at 10:36
  • $\begingroup$ On a formal level: I am no expert, but a "game with incomplete information" is a rigorously defined term in the theory of stochastic games, and, as far as I can tell, measurability assumption is unavoidable there. $\endgroup$ Dec 14, 2022 at 13:28
1
$\begingroup$

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 it is not about the Axiom of Choice (nor probability), but about impracticability of the proposed strategy. (Thus my cognitive dissonance is resolved.)

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 is uncountable and hence not practicable in a finite time. (I believe that one can really prove that there is no practicable (=countable) strategy to answer this riddle.) No wonder one can foresee the future if they has the ability of doing what cannot be done in a finite time.

$\endgroup$

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.