The power of randomness
Here's a puzzle:
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. Is there a strategy that will give you a greater than 50% chance of choosing the larger number, no matter which two numbers I write down?
At first it seems the answer is no. Whatever number you see, the other number could be larger or smaller. There's no way to tell. So obviously you can't get a better than 50% chance of picking the hand with the largest number - even if you've seen one of those numbers!
But "obviously" is not a proof. Sometimes "obvious" things are wrong!
It turns out that, amazingly, the answer to the puzzle is yes. You can find a strategy to do better than 50%. But the strategy uses randomness.
I'd seen this puzzle before - do you know who invented it?
If you want to solve it yourself, stop now or read Quanta magazine for some clues - they offered a small prize for the best answer.
Otherwise, you can read Greg Egan's answer, which seems like the best answer to me.
I'll paraphrase it here:
Pick some function f(x) defined for all real numbers, such that:
the limit as x → -∞ of f(x) is 0,
the limit as x → +∞ of f(x) is 1,
whenever x > y, f(x) > f(y).
(There are lots of functions like this; choose any one.)
Next, pick one hand at random. If the number you are shown is x, compute f(x). Then generate a uniform random number z between 0 and 1. If z is less than or equal to f(x) guess that x is the larger number, but if z is greater than f(x) guess that the larger number is in the other hand.
The probability of guessing correctly can be calculated as the probability of seeing the larger number initially and then, correctly, sticking with it, plus the probability of seeing the smaller number initially and then, correctly, choosing the other hand.
This is
0.5 f(x) + 0.5 (1 - f(y)) = 0.5 + 0.5(f(x) – f(y))
This is strictly greater than 0.5, since x > y so f(x) - f(y) > 0.
So, you have a more than 50% chance of winning! But as you play the game, there's no way to tell how much more than 50%. If the numbers on the other players hands are very large, or very small, your chance will be just slightly more than 50%.
Puzzle 1: Prove that no deterministic strategy can guarantee you have a more than 50% chance of choosing the larger number.
Puzzle 2: There are perfectly specific but 'algorithmically random' sequences of bits, which can't predicted well by any program. If we use these to generate a uniform algorithmically random number between 0 and 1, and use the strategy Egan describes, will our chance of choosing the larger number be more than 50%, or not?
You can see Egan's solutions to these here:
https://johncarlosbaez.wordpress.com/2015/07/20/the-game-of-googol/
Here's a puzzle:
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. Is there a strategy that will give you a greater than 50% chance of choosing the larger number, no matter which two numbers I write down?
At first it seems the answer is no. Whatever number you see, the other number could be larger or smaller. There's no way to tell. So obviously you can't get a better than 50% chance of picking the hand with the largest number - even if you've seen one of those numbers!
But "obviously" is not a proof. Sometimes "obvious" things are wrong!
It turns out that, amazingly, the answer to the puzzle is yes. You can find a strategy to do better than 50%. But the strategy uses randomness.
I'd seen this puzzle before - do you know who invented it?
If you want to solve it yourself, stop now or read Quanta magazine for some clues - they offered a small prize for the best answer.
Otherwise, you can read Greg Egan's answer, which seems like the best answer to me.
I'll paraphrase it here:
Pick some function f(x) defined for all real numbers, such that:
the limit as x → -∞ of f(x) is 0,
the limit as x → +∞ of f(x) is 1,
whenever x > y, f(x) > f(y).
(There are lots of functions like this; choose any one.)
Next, pick one hand at random. If the number you are shown is x, compute f(x). Then generate a uniform random number z between 0 and 1. If z is less than or equal to f(x) guess that x is the larger number, but if z is greater than f(x) guess that the larger number is in the other hand.
The probability of guessing correctly can be calculated as the probability of seeing the larger number initially and then, correctly, sticking with it, plus the probability of seeing the smaller number initially and then, correctly, choosing the other hand.
This is
0.5 f(x) + 0.5 (1 - f(y)) = 0.5 + 0.5(f(x) – f(y))
This is strictly greater than 0.5, since x > y so f(x) - f(y) > 0.
So, you have a more than 50% chance of winning! But as you play the game, there's no way to tell how much more than 50%. If the numbers on the other players hands are very large, or very small, your chance will be just slightly more than 50%.
Puzzle 1: Prove that no deterministic strategy can guarantee you have a more than 50% chance of choosing the larger number.
Puzzle 2: There are perfectly specific but 'algorithmically random' sequences of bits, which can't predicted well by any program. If we use these to generate a uniform algorithmically random number between 0 and 1, and use the strategy Egan describes, will our chance of choosing the larger number be more than 50%, or not?
You can see Egan's solutions to these here:
https://johncarlosbaez.wordpress.com/2015/07/20/the-game-of-googol/
