Guessing game with infinity coin flips

Question

Evan and Ollie are going to play a game as a team. The two friends placed in separate rooms, and then a coin is flipped infinitely many times*. Evan is told the results of the even numbered flips, while Ollie is told the result of the odd numbered flips.

Next, Evan chooses an odd number $d$, and Ollie chooses an even number $e$, each without knowledge of the other's choice. The pair wins if results of the $d^\text{th}$ flip and the $e^\text{th}$ flip are the same.

Before they are separated, the two can agree on a strategy. What strategy can they use to win with probability more than 50%?

I do not know what the optimal strategy is. The best strategy I know of has a success rate of...

2/3.

Source: https://www.reddit.com/r/mathriddles/comments/7gmo1l/alice_and_bob_and_infinite_binary_sequences/

---

^{* To achieve this, flip the coin at noon, then again 30 seconds later, then 15 seconds later, then 7.5 seconds later, etc, and you will infinitely many coin flips by 12:01. We assume that Evan and Ollie are able to process this infinite amount of information.}

Answer 1

A possible strategy is for them to

Say the odd/even number that corresponds to the same position in which they see heads for the first time. So, for example, if Ollie sees heads in position 3, which is the second odd number, he will say 4, which is the second even number.

To get the probability of success,

Note that if they have heads for the first time in the same position, they win: this happens with probability $\frac14 + \frac {1}{16} + ... = \frac13$.

For the remainder of the cases, this strategy is no better than a guess - one of them (the one with the earlier position) will surely guess tails, and there is no information for what the other guess will be. So they win these half of the time.

The total probability is then $\frac13 + \frac12 ( 1 - \frac13 ) = \frac23$.

Answer 2

This isn't really a new answer, but rather a different way of explaining why ffao's answer works. When I first saw that answer, it didn't quite sit right with me, so I worked through it another way. Hopefully this helps anyone else who is unsure of how that strategy gives that probability:

As in ffao's answer, each will choose the turn corresponding to when we first saw a heads. Now, for the first two coin flips, there are 4 possible outcomes, each with a probability of .25:

A. HH
B. HT
C. TH
D. TT

Now, in option A, Evan will choose 1, and Ollie will choose 2, which are both heads, so given outcome A, the probability of both choosing the same is 1.
With outcome B, Ollie will choose 2, which is tails. Evan will choose whatever is directly before the first time he sees heads. There's a probability of .5 that this will also be tails. So, given outcome B, the probability of winning is .5
Outcome C works almost identically to option B, and has a probability of winning of .5 as well.
With outcome D, neither of them choose anything within the first two flips, so the probability of winning with choice D is the same as the overall probability of winning.

Lets call this overall probability of winning P, and the probability of winning under A, B, C, or D A, B, C, and D, respectively. We then have: $$P = .25A + .25B + .25C + .25D$$ But we know what A, B, and C are, and can substitute P for D, giving us: $$P = .25(1) + .25(.5) + .25(.5) + .25P$$ Which simplifies to $$P = .5 + .25P$$ Which, when solved for P, gives us $$P = \frac{2}{3}$$

Answer 3

Nice puzzle. Here are a couple of notes:

Note that in the linked reddit thread, there is a user who with a clever computer search found a series of strategies that seem to approach a 70% chance of winning.

Also, I thought about trying to upper bound their chances of winning and found

they cannot win with probability more than 75%. Why? Let $D$ be the sequence of odd flips and $E$ be the sequence of even flips. So Ollie is choosing an element of $E$, Evan chooses an element of $D$, and they win if those elements match.

Let's say the game is played in the following manner: $D$ is chosen, but with probability $\frac{1}{2}$ we totally invert $D$ (changing each head to tails and vice versa) to create $D'$, and give that to Ollie instead. Of course an inverted random sequence is just a random sequence, so that doesn't really change the game. Assume that Ollie will choose the $i$th element of $E$ if given $D$, and the $j$th element of $E$ if given $D'$ (and note it is possible $i = j$).

Looking at things from Evan's point of view, if the $i$th and $j$th elements of $E$ are the same (both heads or both tails -- this happens at least 50% of the time), now they have a problem. Suppose, for example, the $i$th and $j$th elements of $E$ are both heads. Then Evan has to find a heads in $D$ or $D'$. But since they are inverted sequence, no matter what element Evan guesses, it has a 50% chance of being heads and a 50% chance of being tails.

In other words, 50% of the time they can only win 50% of the time. So they can win with probability at most 75%.

This gives a possible range of values

from 70% to 75%. Can someone close the gap?