Two numbers are randomly chosen from the closed interval [0,1]. Afterward, you see the first number. You now must guess if the unseen number is greater or smaller.
Can you find a strategy with more than a 50% probability of winning?
Understanding
Let a1 and a2 be the two uniformly random numbers selected in this order. After the values are generated, we see the value of a1.
There are a lot of possible strategies we can choose from, but it would be hard to instantly come up with one that has better than random chances of winning if we do not test some not-so-brilliant ones. One such strategy, albeit simple, is to announce that a2 will always have the bigger value.
The plot of pairs (a1, a2) is the unit square. Dividing it along the diagonal – the line with equation a1 = a2 – we get two triangles equal in surface area. Each represents the set of points where a1a2 (below the diagonal). Given that the two areas are equal, we have as good of a chance that a2 is the greater of the two as that a1 is greater. Hence, the win rate of this strategy cannot be anything other than 50%.
It’s not better for us to always say that a2 is lower, given that this strategy also has a 50% probability of success.
These strategies are indeed silly, but can we strive to do better? How can we increase our odds above mere chance? Until now, we have not included in our rationing the fact that we know the value of a1! It is tremendously relevant information. If we find that a1 equals 0,9, we could bet that a2 will be smaller. The probability of this is nine times the probability of the converse! Let’s construct a strategy for playing the game based on this observation.
Solution
Keep the previous image in mind. We want to choose if a1 is greater or not, based on the relative sizes of the two segments, which have as breaking point, 0.5.
- if a1 is greater than or equal to 0.5, say that a2 is less than it
- but if a1 is less than 0.5, say that a2 is more than it.
What is the probability that you will win in this case?
Using conditional probabilities, we condition on the events that a1 is greater than or equal to 0.5 and less than 0.5.
We can win when a1>a2 – given a1 more than a half- or when a1 is less than a2 – given a1 is less than a half-.
The probabilities of the events we condition on are equal to 1/2.
For the remaining values, let’s return to the 2D plot we drew in the beginning plus the vertical line of the equation a1=0.5.
Conditioning on the event that a1 >= 0.5 means that we restrict the probability space to the rectangle on the right side of the yellow line. Since a1 and a2 are known to be uniform and independent, the probability that a1 > a2 under this condition is the ratio between the green area and the entire restricted area.
The remaining term in our formula is computed similarly: the size of the green area (where a1 is less than a2 and a1 is less than 0.5) over the entire restricted area (where a1 is less than 0.5).
Plug the values in, and the probability of winning is 75%. We obatined a tremendous improvement over mere chance. The strategy proposed is facile, and yet it creates excelent results. It also opens up the idea that there might be a better strategy, more complex perhaps, with even higher odds.
In the previous strategy, we chose 0.5 as the threshold for changing our decision. But what if there were a way to foresee the value of a2? If we simulate a variable iid with a2, can this tell us on what side of a1 is a2 situated? Let x be this value. If x is higher than a1, we also say that a2 will be higher. And conversely, if x is less than a1, a2 is as well.
Thinking back to our axis of value for a1, this looks more promising. In the first version, when a1 were 0.9, we would always say that a2 is smaller. Clearly, in 10% of the cases in which a1 is 0.9, we would have been wrong. Now, using the value of x, we could assert that a2 is bigger than a1 in 10% of the cases. Which is the observed probability! The situation looks very promising! We only have to compute the winning chances to prove that this strategy is indeed better.
Starting from the same drawing as before, changing the position of the limit for a1 from 0.5 to x, we compute the probability of a win. One crucial difference is that now we have to condition on the value obtained from the uniform distribution, x. Previously, the value was fixed to 0.5, and no conditions were needed.
Replace the probabilities that a1 is more than x with 1-x and less than x with x.
The conditioned probability that a1 is greater than a2 when a1 is greater than x is computed just as before: the ratio of the green trapezoid and the containing rectangle.
Apply the same logic for the remaining probability, and expand the fractions. We have one single formula for the probability of winning conditioned on the value of x. Unfortunately, this is not enough to tell us what the general probability to win is. For that, we need to “average” over all possible values of x. Since x is uniform, with probability density function one, averaging is equivalent to the summation over the continuum of the interval [0,1]. This is simply, the integral!
After some trivial calculus, we get that the probability of winning is 2/3. We were tricked! The more complex algorithm (considering the genuine distribution of values) failed to provide a greater chance of winning.
So we have an ok formula for playing the game, requiring being able to generate uniform random values. But also, have a top-notch strategy that is both simple and intuitive. If this seems too good to be true, check the results above by simulating games (and values for the second strategy) and computing the win rates. It all checks out.