I recently thought about the following game (has it been considered before?).

Alice and Bob collaborate. Alice observes a sequence of independent unbiased random bits $(A_n)$, and then chooses an integer $a$. Similarly, Bob observes a sequence of independent unbiased random bits $(B_n)$, independent from $(A_n)$, and then chooses an integer $b$. Alice and Bob are not allowed to communicate. They win the game if $A_b=B_a=1$.

What is the optimal winning probability $p_{opt}$? A strategy for each player is a (Borel) function $f : \{0,1\}^{\mathbf{N}} \to \mathbf{N}$, and we want to maximize the winning probability over pairs of strategies $(f_A,f_B)$.

Constant strategies win with probability $1/4$, and it is perhaps counterintuitive that you can do better. Choosing $f$ to be the index of the first $1$ wins with probability $1/3$. This is not optimal though, by running a little program trying randomly modified strategies on a finite window I could find that $p_{opt} \geq 358/1023 \approx 0.3499$, with some pair (with $f_A=f_B$) lacking any apparent pattern.

But a more interesting question is: can you prove any upper bound on $p_{opt}$, besides the trivial $p_{opt} \leq 1/2$?

**Edit**. As has been pointed out by Édouard Maurel-Segala, the problem has been studied in this paper, where it is proved (as is also proved in the present thread) that $0.35 \leq p_{opt} \leq 0.375$, stated without proof that $p_{opt} \leq \frac{81}{224} \approx 0.3616$, and conjectured that $p_{opt} = 0.35$.

**Edit** (clarifying what I said in the comments). You can ask the same question for the finite version of the game, with strings $(A_1,\dots,A_N)$ and $(B_1,\dots,B_N)$, giving optimal winning probability $p_N$. It can be checked than $(p_N)$ is non-decreasing with limit $p_{opt}$. Moreover the inequality $p_{opt} \geq \frac{4^N}{4^N-1} p_N$ holds, because in the infinite game, when a player sees a string of $N$ $0$s, he may discard them and apply the strategy to the next $N$ bits. We have $p_1=1/4$, $p_2=5/16$, $p_3=22/64 > p_2$. It seems that $p_4=89/256$ (therefore
$p_4 > p_3$, but $\frac{256}{255} p_4 < \frac{64}{63} p_3$, so $4$-bit strategies are worse than $3$-bit for the infinite game), and I know that $p_5 \geq 358/1024$ and $p_6 \geq 1433/4096$. For $p_3$ and $p_4$ one strategy achieving the value is: when the observed string contains a single block of $1$s, Alice (resp. Bob) picks the index of the $0$ immediately after (resp. before) that block; what they do in the remaining cases is irrelevant.

14more comments