Here is a game. You are presented with countably infinitely many boxes. Each containing a single real number, you're allowed to open as many boxes as you like and view the number inside the now opened box. However to end this game you need at some point in time to point to a specific box and before opening it guess the number inside it. Due to horribly unimaginative rules, you win if you guess right and lose if you guess wrong.

At first glance this seems like a game you're bound to lose all the time. However if you arm yourself with the axiom of choice it is possible to win with large probability. Your challenge is to find the optimal solution.

Hat tip to Zach Hamaker for showing me this problem which I believe originally comes from his advisor Peter Winkler

Consider all the sequences of assignments of numbers to boxes, then use axiom of choice to pick one such sequence from each set of all sequences that differ only in a finite number of places. Open all the boxes except a random one of them, then guess that the unopened box contains the number that is assigned to it by the representative sequence you chose that differs from the revealed numbers in only finitely many places. Since there are infinitely many boxes and you'd only be wrong if the one you chose were one of the finite number of boxes that differs from your representative, you guess correctly with probability 1.

ReplyDeleteVery nice.

DeleteWhat does it mean to choose a box randomly from among countably many boxes?

DeleteNothing, that bit was slightly badly worded. To make it more precise assign the boxes labels 1 ,2,3 etc and then open all boxes except box 1.

DeleteI think there's something missing from the specification. Win with large probability relative to what random choice? The randomness in your moves? Because the boxes are randomly chosen?

DeleteAs written, it's easy for an opponent to beat this strategy---place any number in the boxes, figure out what your canonical representative for the sequence is, then make sure box 1 has something different.

Well the idea is that your opponent puts numbers in the boxes first. This is followed by you choosing the ordering on the boxes and the representatives of the (infinitely many) sequences. Given this set up (which I thought was clear) there is no way for the opponent to figure out your canonical representation, or even if there was there is nothing he could do about as he's already put the numbers in the boxes.

DeleteI guess the question is then if we choose finitely many natural numbers (the boxes which differ from the canonical representative) what is the probability of a particular box (e.g. 1) being chosen? I guess it somehow depends on the distribution of numbers your opponent is picking.

It might be instructive to assume something like. Each box is 0 or 1 with probability 0.5 independent of every other box (yes this is a non-malicious (and also non-benevolent) opponent).

Lastly I'll say that the solution I had in mind is slightly different from this one I'll reveal it soon.