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

Alice and Bob collaborate. Alice observes a sequence of independent unbiased random bits $ (A_n) $, then choose an integer $ a $. Similarly, Bob observes a sequence of independent unbiased random bits $ (B_n) $, independent of $ (A_n) $, then choose 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 probability of winning $ p_ {opt} $? A strategy for each player is a function (Borel) $ f: {0,1 } ^ { mathbf {N}} to mathbf {N} $, and we want to maximize the probability of winning on pairs of strategies $ (f_A, f_B) $.

Constant strategies win with probability $ 1/4and it may be counterintuitive that you can do better. To choose $ f $ to be the index of the first $ 1 $ earn with probability 1/3 $. This is not optimal however, by running a small program trying randomly modified strategies on a finished window, I could find that $ p_ {opt} geq 358/1023 approx 0.3499 $, with a pair (with $ f_A = f_B $) devoid of any apparent motive.

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