Definitive diffidence

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]

4 thoughts on “Definitive diffidence”

  1. 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.

  2. 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.

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

  4. 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.

Leave a Reply to Ethan Rubin Cancel reply

Your email address will not be published. Required fields are marked *