Guessing each other's coins 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.
 A: 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}.$$
A: 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$.
