This week’s Riddler Classic is an interesting back-and forth game trying to guess whose number is larger.

Martina and Olivia each secretly generate their own random real number, selected uniformly between 0 and 1. Starting with Martina, they take turns declaring (so the other can hear) who they think probably has the greater number until the first moment they agree. Throughout this process, their respective numbers do not change. So for example, their dialogue might go as follows:

Martina: My number is probably bigger.

Olivia: My number is probably bigger.

Martina: My number is probably bigger.

Olivia: My number is probably bigger.

Martina: Olivia’s number is probably bigger.

They are playing as a team, hoping to maximize the chances they correctly predict who has the greater number.

For any given round with randomly generated numbers, what is the probability that the person they agree on really does have the bigger number?

Extra credit: Martina and Olivia change the rules so that they stop when Olivia first says that she agrees with Martina. That is, if Martina says on her turn that she agrees with Olivia, that is not a condition for stopping. Again, if they play to maximizing their chances, what is the probability that the person they agree on really does have the bigger number?

Here is my solution

[Show Solution]

The question is ambiguous as stated, because of the phrase “they are playing as a team”. What does this mean? I will address two possible interpretations.

## If strategizing is permitted

The first interpretation is that Martina and Olivia can decide on a strategy ahead of time. In this case, any accuracy is possible, but this accuracy must be decided ahead of time. To this end, pick an integer $N \geq 1$, and use the following strategy.

- On turn $n=1,2,\dots$, Martina says her number is the largest if it is larger than $\tfrac{n}{N+1}$. Olivia does the same.
- The game continues until one of the players fails the comparison test. Most of the time, the player with the smaller number fails first, and agrees with their partner’s claim, which produces the correct outcome.

The only way this algorithm can fail is if both Martina and Olivia would have failed on the same turn, e.g. they both have numbers that are contained in the same interval $\tfrac{k}{N+1} \lt x \lt \tfrac{k+1}{N+1}$ for some $k=1,\dots,N$. This happens with probability $\tfrac{1}{N}$. In this case, the algorithm produces an incorrect outcome half of the time.

This strategy will take at most $N$ turns, and produces an error with probability $\frac{1}{2N}$. Therefore, arbitrary accuracy is possible with this approach, but the accuracy must be decided between the two players before the game begins.

**Extra credit:** If only Olivia has the power to end the game, then this allows Martina to say whatever she wants and the game will not end. In other words, she can communicate her number to Oliva! Here is a strategy that accomplishes this:

- Martina begins by putting her number in binary form. For example, if her number is $0.6875$, then:

\begin{align}

0.6875 &= 0.5000 + 0.1250 + 0.0625 \\

&= \tfrac{1}{2^1} + \tfrac{1}{2^3} + \tfrac{1}{2^4} \\

&= 0.10110000\dots \text{ (in binary)}

\end{align}
- On turn $n$, Martina utters the $n^\text{th}$ binary digit of her number. For example, Martina and Olivia can agree ahead of time that the response “my number is larger” corresponds to a $1$, while “your number is smaller” corresponds to a $0$.
- Olivia simply parrots Martina’s most recent utterance so that the game does not end.
- Once enough binary digits of Martina’s number have been accumulated, Olivia will know Martina’s number with sufficient accuracy to ascertain with certainty whose number is the largest. Since Olivia gets to choose when and how the game ends, she can bide her time and wait for Martina to speak the truth, and then Olivia can end the game by agreeing with Martina.

The only way this strategy can fail is if Martina’s infinite string of binary digits is eventually constant. Since Martina’s number was chosen uniformly at random, this will occur with probability zero.

So when only one of the two players has the power to end the game, it is possible to determine who has the largest number in finitely many turns, and we outlined an approach that succeeds with probability one.

## If strategizing is forbidden

In this interpretation, “working as a team” means that Martina and Olivia are always truthful with each other. Mathematically, this means for example that Martina will say her number is larger than Olivia’s if the conditional probability that her number is larger than Olivia’s is greater than $0.5$, where we are conditioning on all of the players’ past responses.

Since the game stops whenever somebody agrees with the other person, the only way the game continues is if there is constant disagreement. This means either both players argue their number is largest, or both players argue their number is smallest. Let’s start with the “largest” case. So suppose Martina has $x \gt \frac{1}{2}$ and Olivia has $y$.

- Since $x \gt \frac{1}{2}$, Martina will start by saying she thinks her number is largest. At this point, Martina’s belief of Olivia’s number is $y\in [0,1]$ (no prior information). Meanwhile, Olivia’s belief of Martina’s number is $x \in (\frac{1}{2},1]$ because of what Martina just said.
- Now, Olivia’s response will depend on her own number. If $y \lt \tfrac{3}{4}$ (the midpoint of her belief of Martina’s number), Olivia will agree with Martina and the game ends. At this point, the only thing anybody knows is that $x\in(\frac{1}{2},1]$ and $y\in[0,\frac{3}{4})$. The game ended with agreement that Martina’s number was largest. What is the probability that this was correct? Given a uniform point $(x,y) \in (\frac{1}{2},1] \times [0,\frac{3}{4})$, what is the probability that $x \gt y$? We can resolve this graphically. In the figure below, we see that the blue shaded region occupies $\frac{11}{12}$ of the red rectangle.

- Suppose instead that $y \gt \tfrac{3}{4}$. Then Olivia disagrees with Martina, and the game continues. At this point, Martina now knows that $y \in (\tfrac{3}{4},1]$ and Olivia still only knows that $x \in (\frac{1}{2},1]$. So we are in a situation similar to the first step, except now we’re checking whether we agree that Olivia’s number is the largest or not. In this case, Martina will end the game if $x \lt \frac{7}{8}$, and continue otherwise. Given a uniform point $(x,y)\in (\frac{1}{2},\frac{7}{8})\times (\frac{3}{4},1]$, what is the probability that $y \gt x$? We can answer graphically again. This shape is similar to the previous one, and again occupies $\frac{11}{12}$ of the red rectangle.

- Continuing in this fashion, we get a fractal! The regions keep shrinking and eventually tile the entire $[0,1]\times[0,1]$ square. Here is what the shape looks like when it’s complete:

Looks like a fractal made of sim cards!

Since each rectangle has $\frac{11}{12}$ of its area shaded and the square is completely tiled with similar rectangles, this means the entire square has $\frac{11}{12}$ of its area shaded, and this is the final answer to the problem.

**Extra credit:** If only Olivia has the power to end the game, it turns out the outcome is exactly the same, and we get the same picture as the one above. The reason is that in any scenario where Martina would have ended the game by agreeing with Olivia, instead the game continues, and then Olivia will just agree with Martina on the very next turn. For example, if Martina thinks her number is largest, then Olivia also thinks so, and then Martina agrees with Olivia but the game continues, we now have $(x,y) \in (0.5,0.875)\times(0.75\times 1]$. At this point, the midpoint of Martina’s interval is $\frac{0.5+0.875}{2} = 0.6875$. Therefore, Olivia will always agree with Martina and end the game. The same holds for all other scenarios; the game ends with the same outcome, but will sometimes take one extra turn to do so. For that matter, you could also put the power in Martina’s hands instead of Olivia’s and again we get the same result!

For the case of not strategizing, I think the result is the same regardless of the choice of distribution from which the random numbers are drawn. Being probably larger means that x > Median[dist], and the update to the distribution is to truncate the original distribution to one-half of the original support. At this point, the argument is analogous to what you already presented.

I disagree with your strategizing forbidden extra credit solution. I obtained 13/14 and wrote up my reasoning in FiveThirtyEight’s comment thread. In case you didn’t see it there, I’ve copied it below.

* * *

Represent both players’ digits in binary. Each round consists of one statement by Martina followed by one statement by Olivia. Split the players’ guesses into chunks of two digits at a time. There are thus 16 different possibilities for each round depending on which “bin” (separated by 0.25, 0.5, and 0.75) the two women’s numbers lie in.

If their numbers take the patterns

1x

0y

or

0x

1y

then they automatically win because Olivia correctly agrees (8 possibilities). The two will also agree if their digits are either

00

01

or

11

10

giving them a win for those two possibilities. If the pattern is either

10

11

or

01

00

then Martina will insist in all subsequent rounds that Olivia’s number (or hers, in the latter case) is bigger until Olivia agrees, still winning. If the pattern is

00

00

or

11

11

then guessing moves on to the next round. Finally, if the pattern is

01

01

or

10

10

then Olivia will agree on that round and they have a 50-50 chance at winning if the next digit that differs between them agrees with Olivia’s statement.

Let me make this a little more clear with some concrete values. Suppose Martina’s number is 0.1101… and Olivia’s number is 0.1100… According to the first version, in which either player can end the game, the conversation goes as follows:

Martina: My number is probably bigger.

Olivia: My number is probably bigger.

Martina: Your number is probably bigger.

And it ends there with a loss because Martina’s number is actually bigger but they have agreed that Olivia’s is larger. Under the modified rule in which Martina’s agreement doesn’t matter, the game plays out like this:

Martina: My number is probably bigger.

Olivia: My number is probably bigger.

Martina: Your number is probably bigger.

Olivia: Your number is probably bigger.

At this point, Martina knows that Olivia’s 4th digit is 0 and she will insist in all subsequent rounds that her own number is bigger since her 4th digit is 1. This will eventually result in a win whenever Olivia next has a 0 in an even place.

Another way of looking at this is after Oliva’s last “Your number is probably bigger,” Martina could then respond with, “My number is *definitely* bigger.”

Because the first strategy results in a loss and the second strategy results in a win, the second strategy must be more successful than the first. Based on the above probabilities of wins/losses/moving on to the next round, you can show that the actual probability of winning is 13/14.

I can make this even more clear by replacing, “My number is probably bigger,” with actual numerical statements. Still using those same two example numbers, we know Martina’s number is between 13/16 and 14/16 while Olivia’s is between 12/16 and 13/16. Here’s the first version of the game:

Martina: My number is greater than 1/2.

Olivia: My number is greater than 3/4.

Martina: My number is less than 7/8.

The pair loses.

And the second version of the game:

Martina: My number is greater than 1/2.

Olivia: My number is greater than 3/4.

Martina: My number is less than 7/8.

Olivia: My number is less than 13/16.

Now that Martina knows Olivia’s number is less than 13/16, they are guaranteed an eventual victory because Martina’s number is greater than 13/16.

Upon carefully rereading your write-up, I’m pretty sure you’re correct and I’m wrong. I retract the above comment.

Your explanation for the extra credit seems overly complex.

Both M and O find the binary expression for their number. On the n’th turn,

M says “my number is bigger” if the n’th bit past the decimal is 1 and “my number is smaller” if it’s 0.

O does the same.

If the bits are the same, they each claim to have the larger/smaller number.

This is a disagreement, so play continues.

If the bits are different, they agree and play stops with the correct answer.

The number of turns needed (a turn is a chance for both M and O speak)

is equal to the number of bits before the first bit where the numbers differ.

Each turn there is a 1/2 chance of the match ending; it only goes forever if the numbers are identical.