Coin Flipping Riddle

Question

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. They flip a fair coin an infinite number of times and told outcomes of odd trials to A and even 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 number, and B is supposed to pick an odd number. If the outcomes of the trials A and B picked are the same, the prison warden will release them. If they are different, they will spend life in jail.

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

I recently tried this problem in university and I am interested to see other people's solutions, and perhaps the optimal solution.

Edit: My strategy is that both players agree that as soon as they see 2 tails in a row for themselves, they pick the number in the middle, i.e. A sees a tail on coin flip 2 and 4 so he picks 3, B does the same. After running this on a computer simulation I get a 60% winrate. Although I don't fully understand why.

Edit: a 70% chance of winning has been found on my Puzzling StackExchange duplicate post!

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

Answer 1

I can get a win probability of $2/3$. I have no clue if this is optimal.

Let me use a different numbering system for convenience. Say that player $A$ sees the flips $A_1,A_2,A_3,\dots,$ and player $B$ sees the flips $B_1,B_2,B_3,\dots$.

• Player $A$ finds the smallest $i$ for which $A_i$ is heads, and points to $B_i$.

• Player $B$ finds the smallest $j$ for which $B_j$ is heads, and points to $A_j$.

Let $p$ be the probability that $i=j$. In this case, they are guaranteed to win. If $i\neq j$, then the conditional probability of winning is exactly $\frac12$. Therefore, the overall probability of winning is $$ p+(1-p)\cdot \frac12=\frac12(p+1) $$ Since $$ p=\frac14+\frac1{4^2}+\frac1{4^3}+\dots=\frac{1}{3}, $$ the probability of winning is $2/3$.

To explain the above equation for $p$, we add up...

• The probability both player's first instance of heads is on the first flip. This probability is $(1/2)\times (1/2)=1/4$.

• The probability both players' first instance of heads in on the second flip. For this to happen, both sequences must start out with $T$, then $H$, so the probability is $(1/2\times 1/2)\times(1/2)\times (1/2)=(1/4)^2$.

• In general, the probability of both players' first instance of heads occurring on the $k^{th}$ flip is $[(1/2)^k]^2$, since they both need to get the sequence $TT\cdots TH$, with $(k-1)$ $T$'s. Therefore, we need to sum up $(1/2)^{2k}$ from $k=1$ to $\infty$. This is exactly the sum I had before.

Answer 2

Each person looks at the first flip they are allowed to see. If it's tails (represented by a 0), they pick the first flip they aren't allowed to see. Otherwise, if it's heads (represented by a 1), they pick the second flip they can't see.

You can draw out a table of possibilities to determine there is a 62.5% chance of winning with this strategy, but I'll describe the victory cases below anyways:

If A has "01" as their first two flips, and B has anything, then they'll win since A will pick the first flip from B, and B will pick "0" from A if B has a 0 as their first flip, and "1" if B has a 1 as their first flip. When examining the possible first 4 flips of the warden, the case above accounts for 4/16.

If B has "01", they win for the same reason, accounting for another 3/16 victory cases (since the "A:01 and B:01" case was counted above).

Moreover, since A and B's strategies are the same, if they get the same sequence of flips, they'll win. Again, this accounts for 3/16 new win cases (again the "A:01 and B:01" being the case that was already counted). These turn out to be the only ways to win with this strategy, leading to a (4+3+3)/16 = 62.5% > 50% chance of winning.