Monday, July 18, 2016

Solution to the Alice-Bob-Box problem.

In my last blog I solved one problem and asked another (when will it end!).  Damien Roberts provided an answer in the comments to the last blog, so kudos to Damien! I summarize the question asked and answer it (same answer as Damien, though more long winded)  and then some comments and further questions.

Peter Winkler told me this problem at the Joel Spencer 70th Bday conference.  He got it from Sergui Hart who does not claim to be the inventor of it.

PROBLEM:
Alice and Bob play the following (non-fun) game:

Alice puts natural numbers in the boxes 1,2,3,4,... She can put any number in any box. She can put the number 12 in two boxes. She can refuse to put primes in any box. The world is her burito!

Bob opens all but a finite number of  boxes. He chooses one of the boxes that is NOT opened and guesses what is in it and then opens it.  If his guess is correct he wins! (not clear what he wins, but he wins).If not he is, as one of our candidates for prez would say, a LOOOOOOOSER.

Would you rather be Alice or Bob?
END OF PROBLEM

(Added Later- below is an answer that I believe to be correct. Some people disagree. See some of the comments below and also the comments on this)

I would rather be Bob:

As you might have guessed, Bob takes the set of all infinite sequences of natural numbers and looks at the equivalence x==y iff x and y differ on only a finite number of positions. He then picks a representative from each part of the induced partition.

(When I tried to solve the problem thats as far as I got. Some commenters thought that was the solution, or the solution was obvious from that point. I don't see how.)

Here is what Bob does;

STEP 1: (I used to have Bob takes a random perm of the naturals and relabels the boxes but commenters pointed out that this was not needed and might not even make sense. So there is no Step 1, but I keep
it in case someone sees this post and wonders what happened to step 1.)

STEP2: Bob rearranges the boxes into (say) 100 rows.  We'll say

ROW1: BOXES: 1,101,201,301,...

ROW2: BOXES: 2,102,202,302,...
...
ROW100: BOXES: 100,200,300,...

STEP3: Bob picks a Row AT RANDOM (second use of probability). We will say ROW8:

STEP4: Bob opens the boxes in all of the rows EXCEPT ROW8 (he will open some in ROW8 later). For each Row i NE 8 he does the following:

ROWi is in one of the parts of the partition. Bob had ahead of time chosen a representative in that part. Let x(i) be such that from the x(i)th element on ROWi and the Representative AGREE.

Let x  = max of the x(i).

So, for all rows i NE 8, if you look past the xth position, ROWi and the represenative for that equivalance class are the same.

STEP5: Bob opens up, in ROW8, the boxes x+2, x+3,...

STEP6: Bob knows the part that ROW8 is in the partition. Bob looks at the representative. Bob guesses that the number in box x+1 of ROW8 is the same as the number in the (x+1)th position of the representative.

WHY is this a good idea?

Consider ROWi. Let x(i) (as above) be such that past x(i) ROWi agrees with its rep. In order for the guess to be wrong you would need x(8) > all other x(i). How likely is that? Since we began with a random perm, the prob that x(8) is the largest (for that matter, the prob that any particular i_o has max x(i_0) ) is 1/100. So Bob wins with prob 1- 1/100

Bob can do even better with 1000 rows or 10,000 rows, etc. For any eps>0 he can make the prob that he'll win 1-eps.

One issue I've been trying to get at in this post and the last one was, is this a real solution? I think so, but some students don't like it. Even those that understand it. What do you think?

There is no deterministic solution to the Alice-Bob-Box problem since if the adversary knows what box Bob will guess he can make it so that Bob gets it wrong.

Some asked if there was a computable solution. For both the infinite-hats problem and the box-problem if the players have a strategy depending on only a finite number of inputs they can't win. There are ways to measure the complexity of a strategy and it would be interesting to get upper and lower bounds on the complexity of a strategy. And one can look at the following: If the adversary's strategy is of complexity BLAH then what complexity do the players need to beat it?

Also, in both games AC is used by the players. Eddie Fisher pointed out that if you toss out AC and instead have the AC AM (all sets are measurable) then the Adversary wins the hat game. Not sure about the box game.  One can look at what happens in various axiom systems.

So many open questions, so little time!

1. What's the purpose of Bob choosing a random permutation of the natural numbers? It seems that everything works even without this (with randomness only used in choosing which row to look at last).

1. You are right, in fact, there is no such thing as infinite random permutation of the naturals, we cannot even uniformly select a single natural number, so STEP1 is incorrect.

2. So, is the resolution of the seeming "paradox" that - under the axiom of choice - Alice simply cannot uniformaly and indpendetly chose random numbers from 1 to N for an infinite number of boxes? (Eddie Fisher's comment seems to point that way.)
A second question: Is it obvious/clear that in Step 1 Bob can pick a infinite random permutation of the naturals so that whatever he does next Alice cannot have anticipated?

3. Let's make Bob's job easier by restricting Alice's box-filling options as follows:

-------------
The Restricted Alice-Bob Box Game  Alice's Turing Machine (TM) puts natural numbers in the boxes 1,2,3,4,... Alice's TM accepts an input tape of any finite length, such that Alice can design her TM to put any number in any box. Her TM can put the number 12 in two boxes. Her TM can refuse to put primes in any box. The world is Alice's TM-defined burrito!
-------------

Question  Is it valid to argue that if Bob has a strategy that wins the general Alice-Bob Box Game with probability >1-eps, then that same strategy necessarily will win the restricted Alice-Bob Box Game with probability >1-eps?

The answer is "yes" (as I understand the statement of the problem), and the point of this comment is to suggest that there is nothing particularly counterintuitive about this answer, in the sense that strings generated by Alice's TM necessarily have finite Kolmogorov complexity, and these strings therefore present informatic order that Bob's algorithm can exploit.

4. There is some subtle problem, related to the relation of the Choice Axiom and immeasurable sets. Take a deep breath, this one is long.

Let's assume for now two rows, and all numbers being 0 or 1 (essentially the hats problem). Now assume that each number is independently chosen to be 0 or 1 with uniform probability. By "strategy" I mean a family of one representative from each equivalence class of almost-equal number sequence.

Let X be the highest index mismatch in the first row, Y be the highest index mismatch in the second row.

These look like random variables, but they are not. The existence of a strategy implies that there are immeasurable sets. In other words, it cannot be that all sets of type "X=j" are events with probabilities, as otherwise they would all be Probability 0, while their sum is Probability 1 (if X were a random variable it would always get some value...)

Back to us: Unlike the hat problem, the solution to the box problem actually mentions probabilities, so now there is the question of whether we analyse probabilities of measurable sets. Even if "X=j" is not measurable, maybe "X<=Y", which is the type of thing we actually analyse, is measurable?

My claim is that at least for some strategies this is not a measurable set, or in other words we cannot say anything about "the probability of X<=Y".

Let's assume that the strategy has an additional feature: If an equivalence class of sequences A is obtained from B by removing the first item of each sequence and shifting the others one place down, then the representative of A is the corresponding shift of the representative of B.

It is not immediate how to show the existence of such a strategy, but I believe it can be done through Zorn's Lemma (which is equivalent to the Choice Axiom).

Now assume we have such a strategy, and that "X>=Y" is measurable (i.e. an event). But then instead of the original two rows, we can feed the first row, and then the shift of the second row - call the largest mismatch there Y'. Since the probability space is the same, "X>=Y'" is also measurable and with the same probability. But "X>=Y'" is the exact same set as "X>=Y-1" (due to our special strategy). So, by taking event difference we get that "X=Y-1" is measurable, and specifically an event of Probability 0.

But we can do more of these gymnastics, and get that every set of the type "X-Y=j" for any j (positive negative or zero) is in fact a Probability 0 event. But this cannot be, because X-Y will always equal something.

1. I believe this is correct. The problem with the presented solution is that if you try to formalize it, you'll find "the prob that x(8) is the largest" requires a probability measure to be assigned. But--as you may guess from using the axiom of choice--you don't have measurable sets. So it's not correct to speak of probabilities of the event.

Despite having 100 symmetrical events, and knowing one of them must occur, we can't talk about probabilities of the events! We need the events to be measurable.

The intuitive solution is correct: Alice can win 1-1/N probability for any N, by putting a uniform random number selected from 1 to N in each box. She can generate these numbers, for example, by picking a random real number between 0 and 1 and writing it in base N. The event of any box containing a particular number is a measurable set, and so we can prove that Bob has at most 1/N chance of guessing right.

2. Wow, brilliant, I was completely fooled! So to summarize, Alice is more likely to win if they both must have a "measurable" strategy, and if not, then it doesn't make sense to ask what's more likely.

5. The probability is not on the values of X and Y (which as you point out I am pretty sure are not measurable anyways). We don't give a measure of probability to the way Alice put her numbers in the box. What we do is the following: *once* Alica has put her numbers, and Bob splits into 100 columns, only one of these columns may give a wrong answer. There is no probability at all in this statement. Now if Bob selects uniformly the column he leaves unopened (this is perfectly defined on the finite set {1,...,100}), he has 99% chance of not getting the "wrong" column.

If I go back to the hat problem, what may be confusing is the following: assume the color is white or black and is chosen uniformly at random for each hat. Then for each set of N persons, there is an esperance of N/2 of them getting the correct color. Yet with the strategy outlined in the previous blog post over the naturals there is only a finite number of wrong calls. This simply means that the esperance is not continuous (which we would not expect: we have a simply converging sequence of functions which are not bounded by a L^1 function).

Another way to understand the "paradox": the cardinal of a set is not continuous (where a limit of a sequence of sets is when the lim sup of their indicator function is equal to the lim inf, or in other words when the union of the intersections is equal to the intersection of the unions). Here is my favorite story that showcase this: a man earns 2 coins every day that he adds to the top of his coin stack and spends one. Should he take the one he spends on the top or on the bottom of the stack? The answer is that it should take the one on the top because if he takes the one on the bottom then the limit of the stack of coins is the empty set!

6. No, I don't like it. The solutions violate the implied rules.

I would object to a puzzle solution that required a person to take different actions depending on whether a given TM halted or not (unless the problem statement implied that it is allowed). But the halting function definitely exists, and is a much simpler (or at least smaller) object than the choice functions used in these solutions. Evaluating it only requires countably infinite computation. I don't really know how to talk about the amount of computation required to implement these solutions, but I doubt it is countable.

The halting function is unique, but the choice functions are *very* far from that (I'm not sure, but I think there may be one for every subset of the reals). The axiom of choice certainly does not imply that it is possible for infinitely many agents to agree on a common choice function (as required by the hat problem) by any means whatsoever, even with an uncountable amount of communication.

7. Here is a nice discussion of the problem: http://mathoverflow.net/questions/151286/probabilities-in-a-riddle-involving-axiom-of-choice