11
$\begingroup$

Alice has freely chosen to put either a gold coin or a silver coin in each of an infinite sequence of envelopes numbered 1,2,3,... Bob can open any number of envelopes and check the coins within, provided he leaves at least one envelope untouched. For all the untouched envelopes, Bob then must guess whether it's gold or silver coins within. If he gets all of them correct, Bob wins, otherwise Alice wins. Both seeks to maximize their own winning probabilities.

Clearly, Bob can just leave envelope #1 untouched and randomly guess silver or gold to ensure a 50% winning probability. Can he do better than that?


Hint

Bob can use the axiom of choice to his advantage.

$\endgroup$
22
  • 3
    $\begingroup$ I dont get it. If he leaves 2, he has a 1/4 chance of guessing correctly. If 3, then 1/8, etc... What am i missing? $\endgroup$
    – JLee
    Jul 22, 2022 at 15:34
  • 3
    $\begingroup$ Oh no, is this going to be a (rot13) "nkvbz bs pubvpr" thing? $\endgroup$
    – Deusovi
    Jul 22, 2022 at 15:53
  • 4
    $\begingroup$ Very spoiler: mathoverflow.net/questions/151286 $\endgroup$
    – tehtmi
    Jul 23, 2022 at 6:19
  • 1
    $\begingroup$ The answers to the linked question by tehtmi seem to suggest that defining a probability measure in this scenario is dubious. Is your strategy significantly different from what is proposed here? $\endgroup$
    – hexomino
    Jul 26, 2022 at 10:59
  • 1
    $\begingroup$ @FirstNameLastName I've already answered hexomino. $\endgroup$
    – Eric
    Jul 28, 2022 at 0:21

2 Answers 2

6
$\begingroup$

I feel like someone should discuss the axiom of choice in an answer.

Bob's strategy

First, let's consider a modified puzzle where Alice only has a finite number of gold coins. Here's a strategy Bob can use to win (without using the axiom of choice).

Since there are only finitely many gold coins, there is a last gold coin.

Bob divides the envelopes into 10 groups -- envelopes 1, 11, 21, 31, etc in the first group, 2, 12, 22, 32, etc in the second group and so on. Each group is itself a sequence of envelopes containing gold and silver coins.

Bob chooses one of the groups at random. He opens all the envelopes from the other groups. For each of the other groups, he finds the last gold coin in that group. Bob makes the assumption that the final gold coin overall was in one of the envelopes he already opened -- 9/10 of the time he will be right. If he is right, he can pick an envelope in the chosen sequence that is beyond all the gold coins from the other sequences -- this envelope will contain a silver coin. (He may as well open all the other envelopes in the chosen sequence, and this might reveal that the assumption was wrong, but that's okay. He can just guess randomly in that case.)

Of course, there was nothing special about 10. Bob could choose a larger number for a greater chance of success. Bob's success rate can get arbitrarily close to 100%.

Using the axiom of choice, it is possible for Bob to improve this strategy so that it works even if Alice uses an infinite number of gold coins.

Bob realizes he can classify all possible sequences of gold and silver coins in the following way: two sequences are in the same class if there as some point after which they are identical. For example, all the sequences with a finite number of gold coins are in the same class: if we take two such sequences, we can consider the greatest index at which either sequences contains a gold coin. After that index, both sequences only have silver coins and are thus identical. Notice that the index may have been different if we had chosen a different pair of sequences -- that is okay. Nothing else is in this example class: if a sequence has infinitely many gold coins, then it can't continue to match a sequence with finitely many gold coins after the finite gold coins have been exhausted. There are (uncountably) infinitely many classes like this (and each contains (countably) infinitely many sequences).

From each class, Bob decides to choose a canonical representative. There is no organized or quantifiable way of doing this, but the axiom of choice allows this to be done. It is a pretty straightforward application -- the axiom of choice says there is a set containing exactly one element of each class -- Bob takes the elements of this set to be the canonical representatives.

If Bob compares a sequence against the canonical representative from its class, there are only a finite number of deviations. This is because, by definition, there is an index after which the sequences are identical, and all deviations must occur in one of the envelopes before this index -- and only finitely many envelopes are before any particular index.

Now, instead of considering the last gold coin in each group, Bob can instead consider the last deviation from that sequence's class's representative. The argument proceeds exactly as before, except this time is it important that Bob can open the other envelopes in the chosen group, because this is necessary to determine what class the chosen group is in. The single unopened envelop cannot change what class the group is in -- it is at most one single deviation. Bob will simply guess that the coin in this envelope matches the representative.

(I did not invent this. I'm not sure where I heard it originally, but it is discussed in an equivalent context here on mathoverflow, and indeed a lot of my thoughts about this puzzle are probably inspired by that discussion. I suggest reading it if you want to see people who are more qualified than me talking about this and aren't afraid of things getting even more technical.)

What is probability

Alice seems to have an unbeatable strategy. If she fills each envelope randomly, it seems like there is no way Bob could win. What happens if we pit these strategies against one another? In finite cases, we can define probability by counting the number of successes out of a set of equally likely possibilities. Bob only has a finite number of choices, but Alice has an infinite number of outcomes. In the continuous infinite case, individual outcomes have probability zero, but if enough of them are grouped together, they might have a positive probability. Essentially, we need a concept of length or area (actually, we usually talk about measure, but this is just a generalization of concepts like length and area). For example, we can think of choosing a random number uniformly between 0 and 1. The probability of choosing a particular number, say exactly 0.4, is 0. But, the probability of choosing a number between 1/4 and 3/4 is 1/2 since that is the length of that segment. In fact, we can map Alice's strategy onto this case -- the coins can be thought of as the bits of an infinite binary fraction, and thus each possible outcome maps to a number between 0 and 1. (Technically, some numbers come from two different sequences because of the $0.999... = 1$ conundrum, but there are only countably many such collisions which doesn't actually break anything meaningful.)

When we combine Alice's random decision with Bob's random decision, we are looking at something called a product measure. Basically, we can line Alice's decisions up on one axis and Bob's on the other axis, and instead of "length" we are now concerned with "area" (although it is a little weird since Bob's axis is discrete). A common approach for calculating this kind of area is using Fubini's theorem. This basically says we can calculate the area by considering a fixed but unspecified choice of Bob or a fixed but unspecified choice of Alice, and then averaging that result over all the choices for the other player. This is a natural and intuitive way to approach this kind of problem. In fact, we've already done it implicitly.

When we analyzed Bob's strategy, we assumed Alice had already filled the envelopes -- her choice was already fixed. For a fixed choice of Alice, it is indeed true that (at least) 9 out of Bob's 10 choices will have him guess correctly. If we could use Fubini's theorem (spoiler: we probably can't), it would be correct to say the probability is at least 9/10.

It is hard to analyze precisely what happens if we fix Bob's choice. We can certainly pair up cases where Alice wins and loses by switching the coin in the envelope that Bob will choose. But, a bijection by itself is not enough to indicate that the length is the same -- for example the interval $[0, 1]$ can be put in bijection with the interval $[0, 2]$ by doubling. I think probably that Alice wins 1/2 of the time, or maybe the probability is not measurable.

What does it mean that a set is not measurable? Well, it's unfortunately a little complicated. But in fact, we have already constructed a set that is not measurable, so let's look at it and see what the problem is. Remember when Bob used the axiom of choice to create a set that contained a representative from each class? I claim this set of representatives is not measurable.

Consider one of Bob's classes, considering the sequences to be numbers as Alice did when we figuring out how to quantify their probability. If we take the difference between an arbitrary element and the canonical representative of that class, the common suffix will cancel out, and we will be left with a binary fraction that contains only a finite number of terms. If we do our subtraction modulo 1 (in other words, only considering the fractional part of the result), then each element has a distinct difference between 0 and 1, and each terminating binary fraction between 0 and 1 gives a different element of the class when added to the canonical representative. In particular, there are only countably many things in each class because there are only countably many rational numbers.

Now consider the set of representatives again. One of the rules we want our measure to follow says that we should be able to translate a set without changing the measure. We can consider the translations (modulo 1) of our set under all the terminating binary fractions. This gives countably many sets all with the same measure. They are disjoint because the translations of one representative will only be things from its class -- they can't collide with the translations of another representative which will be members of that representative's class. But, together, these translations will cover everything. Another rule of measures says that if there are countably many sets with measure zero, their union has measure zero. So, our translates can't have measure zero because they cover the whole space which has measure one. But, they also can't have any positive measure, because there are infinitely many of them, and adding infinitely many copies of any positive number would go off to infinity -- it can't converge to one. So there is no way to assign a measure to this set.

The existence of such sets is something that has to be accepted if you want to use the axiom of choice. (For example, this also famously leads to the Banach-Tarski paradox.)

I don't have a proof that the set we actual need to measure to calculate the probability we want is not measurable, but it seems plausible given that we used a set that is definitely not measurable in its construction. If we return our attention to Fubini's theorem, we will find that it states that it is only applicable if the set it's being used on is measurable. If considering the strategies in the opposite order gives a different result, then that would actually imply the set is not measurable -- or else if the slice we need to measure in that ordering is not measurable that's already a problem in itself.

So, if I am correct that the set is not measurable, then the probability that Bob's strategy works against Alice's strategy is simply not defined.

Philosophy

This is sort of unfortunate, but I don't know how it can really be avoided if you are working with probability and non-measurable sets. I don't think we can appeal to reality, as already the question uses an infinite number of envelopes which is pretty abstract, and Bob's invocation of the axiom of choice is also very abstract -- we can't really give Bob an algorithm without filling the axiom of choice gap somehow.

I think this means Bob's strategy discussed here is not an acceptable justification to affirmatively answer the question "does Bob have a strategy that wins more than 50% of the time?" which is how I think this particular puzzle is posed. If a probability can't be measured, that is not more than 50%.

This doesn't mean the problem is ill-posed necessarily. We could imagine non-measurable "solutions" to many problems in probability or geometry (and probably beyond), but that doesn't mean that such problems are all nonsense. However, this puzzle suggests using the axiom of choice and seems to have been posted because of interesting strategies of Bob that use the axiom of choice, so maybe it is unfortunate to try to bring probability into things in this case.

A traditional framing of this puzzle gives Bob nine friends and asks if they can devise a strategy beforehand such that at least nine of them are correct. Using the axiom of choice, this is perfectly acceptable. (Instead of Bob choosing one of the groups at random, each friend chooses a different group.)

I will also note that Bob's strategy doesn't have to cause problems -- it also depends on Alice's choice of strategy. For example, we have already considered the case where Alice's strategy only uses a finite number of gold coins. In this case, Bob doesn't need to resort to using the axiom of choice to choose representatives, as there is only one class in use, and everything can be calculated, and Bob can indeed win. But also, without the use of the axiom of choice in either strategy, no issues like this should arise.

$\endgroup$
2
  • $\begingroup$ I don't think the finite strategy for Bob works, even if Alice has finitely many gold coins. It assumes that each set has the same probability of containing the last gold coin, which is false. If Alice places 500 gold coins randomly in 1000 envelopes, then a set that contains {9, 19, ... 999} is much more likely to contain the last gold coin than the set which contains {0, 10, ..., 990}. $\endgroup$
    – Tim C
    May 16 at 20:53
  • $\begingroup$ Nevermind - I misunderstood it as being an entirely finite problem, with a finite number of envelopes as well as gold coins. $\endgroup$
    – Tim C
    May 16 at 20:59
5
$\begingroup$

Bob can't do better than 50%.

I admittedly don't follow all the axiom of choice discussion, but intuitively, Bob cannot do better than random chance. All the envelopes are filled independently - the contents of any one envelope has no bearing on the contents of any other envelope. Bob can't learn about the contents of an unopened envelope from the contents of another, but he may be able to learn about the method Alice is using to fill the envelopes.

To think about the problem another way, suppose that Alice doesn't pre-fill the envelopes, but instead rolls a die every time Bob selects one, and uses the result to choose whether to put a gold or silver coin inside. From Bob's perspective, this is almost no different from the original problem - all he can do is select an envelope, and look at what's inside. Bob clearly cannot predict the result of Alice's next die roll any better than random chance, no matter how many envelopes he opens. That said, Bob can't predict the result of the die roll, but he can learn about the characteristics of the die Alice is rolling.

What Bob can do is open all but one envelope, and simply guess the coin he saw more often. The proportion of gold coins among the infinite envelopes will characterize the method Alice used to fill the envelopes. And since Alice did, in fact, pre-fill the envelopes, the last unopened envelope is exactly like the others - Alice can't change her envelope-filling function for that one envelope, as she does not know which one Bob will pick to leave unopened at the time it's filled. If Bob sees 60% gold coins among the infinite envelopes, he should guess there's a gold coin in the unopened one, and he'll be right 60% of the time. If Bob opens the infinite envelopes and finds only gold coins, the last envelope almost surely contains a gold coin. But if Bob finds an equal number of gold and silver coins among the infinite envelopes, he cannot do any better than guessing with 50% probability.

Since Alice is trying to maximize her own win probability, though, she should put an equal number of gold and silver coins in the envelopes, leaving Bob with only a 50% chance of winning. Bob can do no better than 50% - there's actually no need for him to check the contents of any envelopes at all under the assumption that Alice is trying to win, the best Bob can do is to pick one envelope and guess randomly.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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