This Riddler puts us in the shoes of a contestant on an unusual game show:
Two players go on a hot new game show called “Higher Number Wins.” The two go into separate booths, and each presses a button, and a random number between zero and one appears on a screen. (At this point, neither knows the other’s number, but they do know the numbers are chosen from a standard uniform distribution.) They can choose to keep that first number, or to press the button again to discard the first number and get a second random number, which they must keep. Then, they come out of their booths and see the final number for each player on the wall. The lavish grand prize — a case full of gold bullion — is awarded to the player who kept the higher number. Which number is the optimal cutoff for players to discard their first number and choose another? Put another way, within which range should they choose to keep the first number, and within which range should they reject it and try their luck with a second number?
I can't imagine this game show would draw great ratings, but it does make for a great puzzle.
As a first pass, let’s use a cutoff of 0.5. This seems intuitive - if we get a number greater than 0.5 on our first draw, we’re more likely to make it worse than better by drawing again. And we have no idea what our opponent is doing, so how could we possibly do anything other than this?
This is not a terrible strategy. Half of the time we’ll get a number greater than 0.5 and keep it (expected value = 0.75). The other half of the time we’ll get a number less than 0.5 and draw again (expected value 0.5). So overall our expected outcome using this cutoff is:
Not bad. But wait a minute - for this puzzle I'm assuming both contestants are equally intelligent, logical, etc. Your opponent will employ the same exact reasoning as above. So can we do better? If we assume that our opponent has an expected outcome of 0.625, then staying put on a first draw of, say, 0.55 seems suboptimal.
To solve this problem, perhaps we should us a cutoff of 0.625 instead! This way we are always re-drawing when our first number is less than what (we expect) our opponent's average outcome will be. Our expected outcome using this cutoff is:
Our reasoning seemed sound, but this new cutoff provides a lower expected value. What happened? It turns out that this is in fact an improvement over the naive cutoff of 0.5 - on average, we'll end up with a lower number coming out of the booth, but we'll win more frequently. Our expected value is lower because the magnitude of our wins will be relatively smaller than the magnitude of our losses, but we don't care about that. Losing by a little is the same as losing by a lot, all we care about is our probability of winning, and choosing a cutoff of our opponent's expected value increases that.
Are we done? Of course not! Remember, our opponent is just as skilled at this game as we are, so he'd do the same thing, no? In which case, we should choose a cutoff of 0.617 - but then he'd do the same, so we should recalculate a new cutoff... and suddenly we have a "wine in front of me" situation.
The key insights here, then, are the following:
- We should choose a cutoff equal to our opponent's expected value - this will maximize our probability of beating him.
- Our opponent is going to do the same.
So what we're really looking for is the cutoff at which our expected value is the cutoff itself. That is, we want to solve for C such that:
I showed the positive root there as our solution, and it's equal to , where is the golden ratio. How cool is that?
Using this as a cutoff maximizes our probability of winning. Of course our opponent will do the same, which means our probability of winning is 50%. And it should've been obvious all along that this is the maximum win probability we could hope to achieve, since by symmetry if we found a better strategy, our opponent would find it, too.