# 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.

• I used a "genetic" (?) algorithm, i.e. start from arbitrary functions $\{0,1\}^N \to \{1,\cdots,N\}$ and apply random mutations which you keep when beneficial. The value $358/1023$ corresponds to $N=5$ and the function which maps the elements of $\{0,1\}^5$ listed in lexicographic order to (5,5,1,3,3,3,3,3,1,1,1,1,3,3,3,3,2,2,2,2,2,2,2,2,1,1,1,1,4,5,4,5). – Guillaume Aubrun Mar 29 '19 at 14:25
• I didn't understand $p = 1/3$ at first, so here goes: If $a < b$, then $B_a = 0$. If $a > b$, then $A_b = 0$. So the players win iff $a = b$, with probability $1/3$. The better strategies allow to get $a = b$ slightly wrong and still win. – student Mar 29 '19 at 22:13
• @student nice, here's another way: consider these cases for the first bits $(A_0,B_0)$ of the two sequences: (0,1), (1,0), (1,1). The players win $1/3$ of these equally-likely cases. In the fourth case (0,0), they recurse on the next bit. – usul Mar 30 '19 at 13:40
• By the way, if we just require the players' bits to match to win (so both finding a zero is also a win), is this the exact same problem with all probabilities doubled? Or is there a difference? – usul Mar 30 '19 at 13:48
• @usul that seems correct and it's a great observation. The reason for that is that, whatever the strategies, $\mathbf{P}(A_b=B_a=0)=\mathbf{P}(A_b=B_a=1)$, since each event $\{A_b=0\}$, $\{A_b=1\}$, $\{B_a=0\}$, $\{B_a=1\}$ has probability $1/2$. – Guillaume Aubrun Mar 30 '19 at 14:33

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}.$$

• This is really great, Édouard! Let me rephrase your argument. If switch from $\{0,1\}$ to $\{-1,1\}$, the inequality is equivalent to $\mathbf{E}[A_b B_a] \leq 1/2$. Now denote by $a$ and $a'$ Alice's output when seeing $(A_n)$ and $(-A_n)$, and same for $b$, $b'$. Your observation is that $$\mathbf{E}[A_b B_a] = \mathbf{E}[- A_{b'} B_a] = \mathbf{E}[- A_{b} B_{a'}] = \mathbf{E}[A_{b'} B_{a'}],$$ and therefore $$4 \mathbf{E}[A_bB_a] = \mathbf{E}[(A_b-A_{b'})(B_a-B_{a'})] \leq 2 \mathbf{E}[|B_a-B_{a'}|] \leq 2.$$ – Guillaume Aubrun Apr 2 '19 at 9:13
• Very nice and much more direct than my formulation ! – Édouard Maurel-Segala Apr 2 '19 at 11:13
• In fact there is a paper by Kariv, van Alten and Dmytro Yeroshkin which generalizes this problem to the case of a parameter p for the coin and they get some upper bounds which is also 3/8 for p=1/2. Besides, they claim that someone proved a better bound : which is 81/224 (>0,361...). Source : front.math.ucdavis.edu/1407.4711 – Édouard Maurel-Segala Apr 2 '19 at 12:31
• Has the 81/224-result been written down somewhere? – Johan Wästlund Apr 4 '19 at 21:12

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$$.

• In general, your method gives $p_\text{opt} \ge (4^N p_N-1)/(4^N-4)$. Using Guillaume's $p_5$ in this bound also gets you to $7/20$. – Yoav Kallus Mar 31 '19 at 1:18
• For what $N$, $7/20$ works in reverse direction, i.e. $p_N\geq \frac{7}{20} - \frac{2}{5\cdot 4^N}$ ? – Max Alekseyev Mar 31 '19 at 15:04
• @MaxAlekseyev, I found strategies for N=3,5,7,9 satisfying your inequality (with equality, I should note) using a very simple algorithm (fix random f_A and optimize f_B; fix f_B and optimize f_A; and so on until fixed point, repeat with different random initial condition). – Yoav Kallus Mar 31 '19 at 15:21
• A formula that matches the known estimates for even $N=2,4,6$ is $p_N = \frac{7}{20} - \frac{3}{5 \cdot 4^N}$ – Guillaume Aubrun Mar 31 '19 at 21:03
• For what it's worth, I have just used CPLEX to solve the cases $N\in\{2,3,4\}$ and verified that your proposed solution is optimal for these cases. That is, the optimal ratios are $0.3125$, $0.34375$, and $0.3477$. In fact, it remains optimal even if you allow a mixed strategy (i.e. for a given sequence, your selection of the digit is random) – John Gunnar Carlsson Apr 1 '19 at 23:02