51
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ 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). $\endgroup$ – Guillaume Aubrun Mar 29 at 14:25
  • 8
    $\begingroup$ 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. $\endgroup$ – student Mar 29 at 22:13
  • 12
    $\begingroup$ @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. $\endgroup$ – usul Mar 30 at 13:40
  • 13
    $\begingroup$ 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? $\endgroup$ – usul Mar 30 at 13:48
  • 5
    $\begingroup$ @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$. $\endgroup$ – Guillaume Aubrun Mar 30 at 14:33
20
$\begingroup$

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

$\endgroup$
  • 12
    $\begingroup$ 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. $$ $\endgroup$ – Guillaume Aubrun Apr 2 at 9:13
  • $\begingroup$ Very nice and much more direct than my formulation ! $\endgroup$ – Édouard Maurel-Segala Apr 2 at 11:13
  • 12
    $\begingroup$ 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 $\endgroup$ – Édouard Maurel-Segala Apr 2 at 12:31
  • 1
    $\begingroup$ Has the 81/224-result been written down somewhere? $\endgroup$ – Johan Wästlund Apr 4 at 21:12
  • $\begingroup$ I have no idea how the 81/224 was proved. I tried (but failed) to improve on the bound around the following lines: instead of bounding $\mathbf{E} [(A_b-A_{b'})(B_a-B_{a'})]$ by Cauchy-Schwarz which gives also the bound $\sqrt{2}^2 = 2$, first project $A_b-A_{b'}$ onto the subspace (in $L^2$) spanned by variables of the form $B_{f(A_n)}$, which amounts to killing higher-order Walsh-Fourier coefficients on Bob side. If the $L^2$ norm doesn't decrease in the process, this means that Bob used a strategy encoded by low-order Fourier coefficients, for which we should be able to say more. $\endgroup$ – Guillaume Aubrun Apr 5 at 17:35
14
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ 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$. $\endgroup$ – Yoav Kallus Mar 31 at 1:18
  • 1
    $\begingroup$ For what $N$, $7/20$ works in reverse direction, i.e. $p_N\geq \frac{7}{20} - \frac{2}{5\cdot 4^N}$ ? $\endgroup$ – Max Alekseyev Mar 31 at 15:04
  • 3
    $\begingroup$ @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). $\endgroup$ – Yoav Kallus Mar 31 at 15:21
  • 3
    $\begingroup$ 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}$ $\endgroup$ – Guillaume Aubrun Mar 31 at 21:03
  • 4
    $\begingroup$ 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) $\endgroup$ – John Gunnar Carlsson Apr 1 at 23:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.