Guessing each other's coins

Question

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.

Answer 1

I discussed this with Arvind Singh a while ago and I think we can show the non trivial inequality $p_{opt}\leqslant\frac{3}{8}$ with simple arguments. The proof relies on the symmetry of the problem and the intuition is that one can not find a strategy wich is good simultaneously for a configuration and its inverse.

It will be simpler to work with the sets of indices such that the coin is on $1$: $$A=\{1\leqslant i\leqslant n : A_i=1\},\quad B=\{1\leqslant i\leqslant n : B_i=1\}.$$ We want to bound $$G=\mathbb P (f_a(B)\in A, f_b(A) \in B).$$ Introducing the function $$g(A,B)=\frac{1}{4}\left(1_{f_a(B)\in A, f_b(A) \in B}+1_{f_a(B^c)\in A^c, f_b(A^c) \in B^c}+1_{f_a(B)\in A^c, f_b(A^c) \in B}+1_{f_a(B^c)\in A, f_b(A) \in B^c}\right),$$ we get by symmetry (since for example $A^c,B$ has the same law than $A,B$): $$G=\mathbb E [g(A,B)].$$ But there are some incompatibilities in $g$: the first term and the third term can not be both equal to $1$ since one contains $f_a(B)\in A$ and the other $f_a(B)\in A^c$. The same thing applies for the second and the fourth. Thus $g(A,B)\in\{0;\frac{1}{4};\frac{1}{2}\}$ almost surely.

On the event $E_1=\{f_b(A)\in B, f_b(A^c)\in B\}$, only the first and the third term can be non vanishing and since they are incompatible $g(A,B)$ is at most $1/4$ (in fact it is equal to $1/4$). Besides, by first conditionning on $A$ we see that $E_1$ is of probability at least $1/4$ (the probability that $B$ contains (one or) two elements).

The same applies to $E_2=\{f_b(A)\in B^c, f_b(A^c)\in B^c\}$. If we consider the event $$E=\{f_b(A)\in B, f_b(A^c)\in B\}\cup\{f_b(A)\in B^c, f_b(A^c)\in B^c\}.$$ we have built an event such that $g1_E\leqslant \frac{1}{4}$ and $\mathbb P(E)\geqslant \frac{1}{2}$ (the union is disjoint). Thus since $g\leqslant \frac{1}{2}$, $$G=\mathbb E[g(A,B)]\leqslant \mathbb E[g1_E]+\mathbb E[g1_{E^c}]\leqslant \frac{1}{4}\mathbb P(E)+\frac{1}{2}(1-\mathbb P(E))\leqslant \frac{1}{4}\frac{1}{2}+\frac{1}{2}(1-\frac{1}{2})=\frac{3}{8}.$$

Answer 2

First, Alice chooses minimal $n_a$ divisible by 3 such that her bits at positions $n_a, n_a + 1, n_a + 2$ are not all the same, and Bob similarly chooses $n_b$. Looking at triplet $A_{n_a}, A_{n_a + 1}, A_{n_a + 2}$. Alice chooses $m_a$ according to following rule: {010: 2, 011: 2, 001: 1, 110: 0, 100: 0, 101: 1}. Bob chooses $m_b$ in the same way.

Now Alice says $n_a + m_a$, and Bob says $n_b + m_b$. It's easy to check that probability of $n_a = n_b$ is $\frac{3}{5}$, probability of winning in this case is $\frac{5}{12}$. If $n_a \neq n_b$, then probability of winning is default $\frac{1}{4}$. So winning probability for this strategy is $\frac{3}{5} \cdot \frac{5}{12} + \frac{2}{5} \cdot \frac{1}{4} = 0.35$.