Coin Flipping Puzzle

Question

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!

Answer 1

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}$.