18
$\begingroup$

This is a repost from my post at Math Stack Exchange

2 criminals A and B, were recently captured and brought to prison. They were then locked in two separate rooms.

Known for being exceedingly smart, the prison warden set a test for them. The Warden flips a fair coin an infinite number of times and tells the outcomes of odd numbered trials to A and even numbered trials to B.

Now A and B are separately told to pick a trial whose outcome they don't know, i.e., A is supposed to pick an even trial number, and B is supposed to pick an odd trial number. If the outcomes of the trials picked are the same, the prison warden will release them. If they are different, they will spend their life in jail.

Note: A and B don't know of each other's guesses.

The Warden told them what they were going to do and let them agree upon a common strategy in advance, but after that they can't communicate.

Find a strategy such that the chance of winning is higher than 0.5.

Strategies so Far

  1. 70% chance of winning by @Jaap Scherphuis
  2. 2/3 probability of winning by @Mike Earnest
  3. 62.5% chance of winning by @Teo Miklethun

I was told there was a greater chance to find an optimal solution on this platform. This problem was extremely intriguing to me! For reference, I'm a maths student and this was a problem in an extra class I take.

Edit: I realize that an optimal solution may be impossible at the moment, but any strategy that can beat 2/3 probability of winning would be interesting!

$\endgroup$
6
  • 1
    $\begingroup$ "the prison warden set a test for them. They flip a fair coin". You should really change the 'they' to 'the warden'. $\endgroup$ Commented Sep 14, 2021 at 3:32
  • 1
    $\begingroup$ @mathworker21 Done! Thanks for pointing it out. $\endgroup$
    – Igor
    Commented Sep 14, 2021 at 8:18
  • 1
    $\begingroup$ Similar to the original Levine Hat Puzzle, optimal strategy is very unlikely to be found with proof. $\endgroup$
    – WhatsUp
    Commented Sep 14, 2021 at 13:56
  • 1
    $\begingroup$ I put in an edit request adding the clarification "Note: A and B don't know of each other's guesses." because this clarification was made by you in the MathSE comments. $\endgroup$
    – Ankit
    Commented Sep 15, 2021 at 1:49
  • 2
    $\begingroup$ The paper shows that the best result we can hope for is $81/224*2 \sim= 72.3\%$, so we are pretty close to that already. $\endgroup$ Commented Sep 17, 2021 at 13:56

1 Answer 1

11
$\begingroup$

In this paper about Levine's hat puzzle there is a better strategy with a winning probability of $0.7$.

Let $a_i$ be the coin toss outcomes that are told to $A$, and $b_i$ the ones that are given to $B$. This is a bit easier than having the tosses interleaved as a single sequence.

The strategy is as follows:

Split the coin tosses into triplets. Both players skip over any triplets that have three heads or three tails to get to the first triplet containing both heads and tails.
For player $A$, if there is a single tail then pick that index. If there is a single head, then pick the index to the right of that one (wrapping around to the first of the triplet if the head is already at the right end).
For player $B$, if there is a single tail then pick that index. If there is a single head, then pick the index to the left of that one (wrapping around to the last of the triplet if the head is already at the left end).

For example, if $A$ sees $\{a_i\}=(H,H,H,T,T,T,T,H,T,...)$ then he skips the triplet of heads and the triplet of tails, arriving at $THT$. This triplet has one head, $a_8$, so he asks for $b_9$ to be used, i.e. the other player's coin toss to the right of this one.
If $B$ sees $\{b_i\}=(T,T,T,H,T,T,...)$ then he skips the triplet of tails, arriving at $HTT$. This triplet has one head, $b_4$. He would normally want the index to the left of this, but has to wrap around to the end of the triplet and so asks for $a_6$ to be used.

Now let's calculate the probability of winning.

Let $r$ be the probability of $A$ and $B$ skipping the same number of triplets. A triplet has probability of $\frac14$ being all the same. Then clearly $$r = \frac34\cdot\frac34+\frac14\cdot\frac14\cdot r$$ where the first terms represent both players not skipping, and the second term is both players skipping the first triplet and then still having to skip the same number of further triplets. This gives $r=\frac35$.

If the two players did not skip the same number of triplets, their decisions and outcomes are independent, so there will be a probability of $\frac12$ of winning. If however they did skip the same number of triplets, then the result is as shown in the following table:
$$\begin{array}{l|llllll} & THH & HTH & HHT & HTT & THT & TTH \\ \hline THH & TT & HH & HH & HH & HT & TT \\HTH & HH & TT & HH & TT & HH & HT \\HHT & HH & HH & TT & HT & TT & HH \\ HTT & HH & TH & TT & TT & TT & HH \\THT & TT & HH & TH & HH & TT & TT \\TTH & TH & TT & HH & TT & HH & TT \end{array}$$
$A$'s triplets are along the top, $B$'s triplets along the left. The pairs in the table show the result of $A$'s choice followed by the result of $B$'s choice.
Only $6$ of the $36$ outcomes fail, so in this case there is a win probability of $\frac56$.

The total probabiliy of winning is therefore $r \cdot \frac56 + (1-r) \cdot \frac12 = \frac12 + \frac15 = \frac7{10}$.

$\endgroup$
4
  • $\begingroup$ Impressive. Do you have any motivation or intuition or heuristics that leads to this strategy? $\endgroup$
    – loopy walt
    Commented Sep 15, 2021 at 12:11
  • $\begingroup$ A great solution and excellently described! I will be sharing your answer to the linked math StackExchange post. $\endgroup$
    – Igor
    Commented Sep 15, 2021 at 12:11
  • 1
    $\begingroup$ @loopywalt Not really. As I wrote, I took it from the linked paper. Grouping together coin tosses and skipping particularly unfavorable groups seems reasonable, but the way that this particular choice of group size and rules leads to that table of outcomes seems almost miraculous. In the paper they conjecture that this is an optimal strategy. They do mention that other rule sets exist (with the same group size) that work just as well, but that this one is the easiest to describe. $\endgroup$ Commented Sep 15, 2021 at 13:03
  • 2
    $\begingroup$ Nice! I ran a quick simulation in R and on 100,000 trials got 70% success, exactly as predicted. Such a good puzzle and solution. $\endgroup$
    – C8H10N4O2
    Commented Sep 20, 2021 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.