Here is a puzzle from Quanta magazine that I spent wayyy too many spare cycles on (and then a lot of cycles afterwards telling everybody the answers to the puzzle and also all the variations that I thought of). (EDIT: I saw that the Quanta article had a “solution” section after I wrote this, but I think it does a horrible job of explaining why randomness helps. Maybe this will be better.). Quote:
I write down two different numbers that are completely unknown to you, and hold one in my left hand and one in my right. You have absolutely no idea how I generated these two numbers. Which is larger? You can point to one of my hands, and I will show you the number in it. Then you can decide to either select the number you have seen or switch to the number you have not seen, held in the other hand, as your final choice. Is there a strategy that will give you a greater than 50 percent chance of choosing the larger number, no matter which two numbers I write down?
Rather than immediately give you the solution, which is technical, let’s introduce two easier versions of this puzzle to get the juices flowing. First, the easiest version:
Puzzle 1. Consider the following game. There are two players, Alice and Bob. Privately, Alice chooses two integers uniformly at random between 1 and 6 (say, by rolling two fair die), places one in each hand randomly, and shows her closed hands to Bob. Bob’s goal is to find the larger number, and he is allowed the following two actions. First, he chooses one of Alice’s hands, and Alice reveals her number to Bob. Then, he can either choose to take the number he has seen, or he can switch to the other hand. If he switches, he must take the number in the other hand. If the two numbers are the same then Bob always wins. Is there a strategy for Bob that will allow him to find the larger number with probability greater than 50%?
Here is a “dumb” solution. Bob picks a hand, ignores the number, and stays. The probability that he wins is the probability that the numbers are different and he chose the larger number, plus the probability that both numbers were the same (note that these events are disjoint!). Summing up, we get the probability that Bob wins is
However, he can do much better. Here is one of many possible strategies: Bob chooses a hand uniformly at random, and receives a number L. If 1 <= L <= 3, then Bob switches. If 4 <= L <= 6, then Bob stays.
To see that this works better, suppose that Bob chooses the hand and receives a value L. The probability that Bob wins is the probability that he chose the smaller number first and switched, or he chose the larger number first and stayed, or both numbers were the same. Clearly, the probability that he gets the smaller number first or the larger number first is 1/2 in both cases. The probability that the smaller number is no more than 3 is 2/3, and symmetrically the probability that the larger number is no less than 4 is 2/3. Finally, the probability that the numbers are the same is 1/6, in which case he always wins. Thus the probability of winning is
This strategy is both intuitive and surprisingly effective. If Alice instead chooses her random integers to be between 1 and k, for some positive k (let’s assume it is even, for simplicity), the above strategy generalizes in the obvious way, with Bob’s probability of success jumping to (exercise if you’re bored)
which is guaranteed to be above 3/4 = 75%.
While this game is tilted towards Bob even from the outset, the second strategy above reveals the remarkable power that randomization can have. In Computer Science, randomness tends to have two major applications:
- In any sort of optimization or problem solving, when you are confronted with a problem for which computing the best answer is hard, but you (via some other knowledge) know that most answers are high quality, then generating an answer uniformly at random will give you a good approximation most of the time. You can often improve the random answers through repeated independent trials: for example, you can take the best answer (i.e. the Monte-Carlo method), take a “majority vote” (in which case you need a concentration of measure phenomenon such as the Chernoff bounds), or perhaps you can somehow breed the results together and get a new answer for which the whole is greater than the sum of its parts (this type of argument often appears in extremal combinatorics, for example in the Rödl nibble). Of course, there is no need to sample answers uniformly: if instead there is an efficiently computable distribution of good answers you can sample from that. Let us call this the sampling regime.
- In cryptography, randomness is used almost exclusively for unpredictability, as not even the most powerful computer in the world can predict the outcome of a truly random bit. In this guise, randomness is used to help parties perform a computation correctly while maintaining some data privately either from each other, or from some adversaries who have compromised the method of communication. This is the privacy regime.
The strategy outlined above is an excellent example of the efficacy of the sampling regime of randomization. In the rest of this post we will show how randomization can be used to give a strategy to solve the puzzle at the top better than randomly guessing.
Before we get there, however, let’s first make the previous puzzle a bit harder. Introducing
Puzzle 2. Consider the following modification of the previous game. Now, Alice generates her numbers in some way known only to her (perhaps she always generates them randomly, or, perhaps she always picks the numbers 1 and 2 and places them in the left and right hand, respectively). Assume also that Alice always chooses numbers which are distinct. Is there now a strategy for Bob that will allow him to find the larger number with probability greater than 50%?
Notice that because Bob now has no information on how Alice is generating her numbers, the strategy from the previous puzzle will no longer work. However, by a suitable modification of the previous strategy, he can (surprisingly) do better than 1/2.
The key observation is this. Suppose Alice has generated two numbers, and let S be the smaller number and let L be the larger number. Then there are more numbers between S and 6 then there are between L and 6; symmetrically, there are more numbers between 1 and L than there are between 1 and S. Considering the sampling regime above, we arrive at the following strategy:
Strategy: Bob chooses a hand uniformly at random and receives a number N. He then chooses a uniformly random number R between 1 and 6. If R <= N, he stays. Otherwise, he switches.
We can calculate the probability that the above strategy succeeds as follows. The probability that Bob chooses the smaller number, S, first is 1/2, and the probability that he switches is (6 – S)/6. Similarly, the probability that Bob chooses the larger number first is 1/2, and the probability that he stays is L/6. So, the probability that Bob succeeds is
Since L and S are integers and L > S we know L – S is at least one, and so Bob succeeds with probability greater than 1/2 + 1/6 = 4/6. This strategy similarly generalizes: if Alice chooses a number between 1 and k instead of 1 and 6, we get that Bob succeeds with probability at least 1/2 + 1/k > 1/2.
So, despite the fact that Bob has no idea how Alice is choosing her numbers, by cleverly using randomization he can still strictly improve on randomly guessing (it’s not a great improvement, but the fact of it is still fascinating).
Of course, there are caveats. You have to play the game multiple times in order for Bob’s strategy to really quantitatively improve on random guessing — but, this is the same grain of salt that comes with any randomized strategy. In other words, the “gain” from using such a randomized strategy will really only start showing itself once you are allowed to do repeated and independent trials, as described in the sampling regime above.
Now, what about the puzzle that we first discussed? We will state it again, but using our language:
Puzzle 3: Consider the following modification of Puzzle 2. Now, Alice can choose any two distinct real numbers, by way of whatever strategy she wants. Is there a strategy for Bob that will allow him to find the larger number with probability greater than 50%?
The strategy from Puzzle 2 would dictate that Bob selects a hand uniformly at random, chooses a uniformly random real number R, and if R is less than the number he chose he stays, otherwise he switches. Unfortunately, there is no uniform distribution on the real numbers (there are “too many of them” in a certain sense: any attempt to create a distribution on the reals which has the properties of the uniform distribution will violate either the second or third axiom of probability).
To get around this, we will use a bijective mapping from the reals to the real interval [0, 1] that is monotonically increasing — i.e. if x < y then f(x) < f(y) —- then, we choose a random number on [0, 1] (this, fortunately, can be done to any degree of accuracy). There are many possible choices: an obvious one is the logistic function
The new strategy is as follows: we choose a hand at random, and receive a number N. Compute f(N), and choose a uniformly random number R from the interval [0, 1]. If f(R) <= f(N), then stay. Otherwise, switch. By a similar argument as before, the probability that Bob wins the new game will be
and since L > S we get that this will always be bounded away from 1/2 (although, it can be bounded away by an arbitrarily small fraction, and so success will crucially depend on the degree of accuracy by which we calculate the random number R).
We can interpret the role of the function f above in a similar way as the role of the uniform distributions in the previous two puzzles. Recall that the intuition in the other puzzles was as follows: Bob chooses a random hand, and if he gets the smaller number S first there are “more” numbers between the number he sees and the highest number, 6, so by choosing a random number R between 1 and 6 and switching if R > S he guarantees that more of the time he will be switching to the larger number (and symmetrically if he gets the larger number first). The problem in the case of the real numbers is that if x is any real number, then there are infinitely many numbers greater and less than x. The function f, by mapping the entire real line to [0, 1] monotonically, gives us a “measure” for S and L that allows us to re-use this intuition: there are still not more numbers greater than S then there are numbers greater than L, but the numbers greater than S have larger measure (according to f) then the corresponding measure for L.