I recently attended a talk at Stanford by Professor Persi Diaconis. He used to be a magician, and in some sense, still is. In this post I'd like to present one of his "tricks" from the talk.
Alice and Bob play a game. There are a countably infinite set of boxes. Alice puts a real number in each box any way she wants. Bob is allowed to open all but one box (he can choose which one) and has to guess the number in the unopened box. Can you find any strategy for Bob to guess the number correctly with probability greater than 0? The answer is yes. In fact, Bob can guess the number in the unopened box correctly with probability as close to 1 as he wants. How could Bob possibly guess the number from an unopened box given Alice can put any number any way she likes? For example, Alice can choose all numbers randomly and independently so that no information from one box could influence another. How can Bob make information where there is none? It's really like magic, or as Persi said, a monster! A monster that displays the power of randomness, the weirdness of infinity and the axiom of choice. That's right, we're gonna need the axiom of choice: given any collection of bins, each containing at least one object, it is possible to make a selection of exactly one object from each bin, even if the collection is infinite. Here's how Bob does it. Let's say he wants to guess the number correctly 99% of the time. He first divides the boxes into 100 rows, each row contains a countably infinite number of boxes. He can do this any way he likes; for example, the first row contains boxes numbered 1, 101, 201, ..., the second row contains boxes numbered 2, 102, 202, ... and the last row contains boxes numbered 100, 200, 300, ... Let T denote the set of all tuples of countably infinitely many real numbers (in a more math-y notation, T = R^infinity where R denotes the set of all real numbers). Then each row of boxes that Bob constructed is a member of T. Define an equivalence relationship on T as follows: two tuples are equivalent if they are identical after a certain point. For example, (1, 2, 5, 3, 3, 3, 3....) and (4, 3, 3, 3, 3, 3...) where in both tuples all the numbers after ... are 3, are equivalent because their tails starting from the fourth position are the same. It is easy to check this is indeed an equivalence relationship:
A tuple x is always equivalent to itself
If x is equivalent to y then y is equivalent to x
If x is equivalent to y, y is equivalent to z then x is equivalent to z. Indeed, assume x is identical to y after m boxes, y is identical to z after n boxes, then x is identical to z after max(m, n) boxes
Here comes the axiom of choice. The above equivalence relation divides T into disjoint equivalence classes. By the axiom of choice, we can form a set that consists of exactly one representative in each class, let's call this set Rep. Now we can map each tuple t in T to a unique positive integer, say s_t, as follows: find an element in Rep that is equivalent to t, and let s_t be the last place where they are not identical. We call s_t the signature number of t.
Bob chooses a random row between row 1 and 100, let's say 52 (the original number picked by Persi - but there is nothing magical about that number except that it is close enough to the middle and hence is somehow more believable to be a random number than 1 - even though their chances are the same). He opens all the numbers in all rows but 52, and calculates the signature numbers of these 99 rows. Let N be the maximum of all these signature numbers plus 1. The magical box to be unopened will be box number N of row 52. After opening all other boxes in row 52, Bob can find the element in Rep corresponding to the tail of row 52, and guess the number in box N of row 52 to be the number in box N of this element of Rep. Bob will be correct unless the signature number of row 52 is greater than N, or equivalently 52 is the row with the highest signature number.
Given any setup by Alice, the set of the signature numbers of 100 rows are determined and the row that contains the highest signature number is determined. By choosing a random row, Bob will only fail (by choosing the row with the highest signature number) with probability 1/100. Voila! If Bob wants a more accurate guess, say 99.9%, he can divide the boxes into 1000 rows and proceeds similarly.
Voila, hope this trick will be a treat for the math lovers out there. Happy Halloween :)
Comments