{"id":3026,"date":"2021-05-08T22:55:17","date_gmt":"2021-05-09T03:55:17","guid":{"rendered":"https:\/\/laurentlessard.com\/bookproofs\/?p=3026"},"modified":"2021-05-10T09:50:24","modified_gmt":"2021-05-10T14:50:24","slug":"definitive-diffidence","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/definitive-diffidence\/","title":{"rendered":"Definitive diffidence"},"content":{"rendered":"

This week’s Riddler Classic<\/a> is an interesting back-and forth game trying to guess whose number is larger.<\/p>\n

\nMartina 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:<\/p>\n

Martina: My number is probably bigger.<\/p>\n

Olivia: My number is probably bigger.<\/p>\n

Martina: My number is probably bigger.<\/p>\n

Olivia: My number is probably bigger.<\/p>\n

Martina: Olivia\u2019s number is probably bigger.<\/p>\n

They are playing as a team, hoping to maximize the chances they correctly predict who has the greater number.<\/p>\n

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

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?\n<\/p><\/blockquote>\n

Here is my solution
\n[Show Solution]<\/a><\/p>\n

\n

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.<\/p>\n

If strategizing is permitted<\/h2>\n

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.<\/p>\n

    \n
  1. 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.\n
  2. 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.\n<\/ol>\n

    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.<\/p>\n

    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.<\/p>\n

    Extra credit:<\/strong> 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:<\/p>\n

      \n
    1. Martina begins by putting her number in binary form. For example, if her number is $0.6875$, then:
      \n\\begin{align}
      \n0.6875 &= 0.5000 + 0.1250 + 0.0625 \\\\
      \n&= \\tfrac{1}{2^1} + \\tfrac{1}{2^3} + \\tfrac{1}{2^4} \\\\
      \n&= 0.10110000\\dots \\text{ (in binary)}
      \n\\end{align}<\/p>\n
    2. 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$.\n
    3. Olivia simply parrots Martina’s most recent utterance so that the game does not end.\n
    4. 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.\n<\/ol>\n

      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<\/a>.<\/p>\n

      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.<\/p>\n

      If strategizing is forbidden<\/h2>\n

      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.<\/p>\n

      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$.<\/p>\n

        \n
      1. 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.\n
      2. 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.\n

        \"\"<\/a><\/p>\n

      3. 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.\n

        \"\"<\/a><\/p>\n

      4. 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:\n

        \"\"<\/a><\/p>\n

        Looks like a fractal made of sim cards<\/a>!
        \nSince 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.\n<\/ol>\n

        Extra credit:<\/strong> 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!<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

        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 … Continue reading “Definitive diffidence”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":3038,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_uf_show_specific_survey":0,"_uf_disable_surveys":false,"footnotes":""},"categories":[7],"tags":[33,23,2],"class_list":["post-3026","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-riddler","tag-game-theory","tag-logic","tag-riddler"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/3026","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/comments?post=3026"}],"version-history":[{"count":13,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/3026\/revisions"}],"predecessor-version":[{"id":3043,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/3026\/revisions\/3043"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media\/3038"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=3026"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=3026"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=3026"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}