63

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.

domotorp
  • 18,332
  • 3
  • 54
  • 121
Guillaume Aubrun
  • 4,743
  • 33
  • 43
  • How did you determine $p_{opt} \geq 358/1023$, and what exactly was the winning strategy? – user44191 Mar 29 '19 at 14:11
  • 4
    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
  • If you drop the requirement that $f$ should be Borel, do you get bizarre axiom of choice strategies that win more often, as with hat guessing puzzles? – Nate Eldredge Mar 29 '19 at 14:44
  • 1
    I doubt so. I said Borel to make sure that "winning probability" is a well-defined concept. For that at least you want the functions to be measurable. – Guillaume Aubrun Mar 29 '19 at 14:48
  • Equivalently (by regularity of measure), you can define $p_{opt}$ as the supremum over strategies which depend only on finitely many variables. – Guillaume Aubrun Mar 29 '19 at 16:50
  • 1
    For N=2,3,4, it should be feasible to brute force to find the optimal strategy. The results might be suggestive. – Nate Eldredge Mar 29 '19 at 19:26
  • For N=3 one optimal strategy, which gives a probability $22/63$ is: for $f_A$, return the index of the $0$ which is after the block of $1$s, for $f_B$, return the index of the $0$ which is before the block of $1$s (before and after are understood modulo 3, and what you do when you see 000 or 111 is irrelevant) – Guillaume Aubrun Mar 29 '19 at 19:57
  • For N=4 I convinced myself (but didn't try to use brute force) that the optimum is $89/255$, achieved using the same strategy as for N=3 (what you do when you see 0000 or 1111 or 0101 or 1010 is irrelevant). This is worse than for N=3 (!) – Guillaume Aubrun Mar 29 '19 at 20:00
  • 1
    How can N=4 be worse than N=3? Can't Alice and Bob ignore their 4th inputs if they want? – Ryan O'Donnell Mar 29 '19 at 20:03
  • That's because I used the following convention: say for N=3, if a player sees 000, he discards these bits and applies the same strategy recursively to the next 3 bits. If you don't use this trick, the optimal winning probability is indeed increasing with N – Guillaume Aubrun Mar 29 '19 at 20:07
  • 8
    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. –  Mar 29 '19 at 22:13
  • 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
  • 13
    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
  • 5
    @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
  • 3
    By the way : here is another discussion on some closely related problems (if you accept that a problem on hats that comes in two colors can be translated into a coin problem) : https://blog.tanyakhovanova.com/2011/04/how-many-hats-can-fit-on-your-head/ – Édouard Maurel-Segala Apr 02 '19 at 12:06
  • 1
    I think it is worth editing the question to point out, as Édouard Maurel-Segala said, that this problem is explicitly studied in the paper: https://arxiv.org/abs/1407.4711 – Sam Hopkins Apr 04 '19 at 19:10
  • @usul, I don't understand the "recurse to the next bit" part. Isn't game over on the 1st attempt? Maybe I don't understand the statement of the problem. It sounds to me that $P(A_b)=1/2$ and $P(B_a)=1/2$ and I don't see how they could be correlate, leading to $1/4$ being the win probability regardless of strategy. What am I missing here? – Michael Apr 04 '19 at 20:50
  • Am I right in guessing that Alice and Bob lose the game if $A_b\ne B_a$ ? But they play again with the same binary sequences if $A_b=B_a=0$, with only that as added information ? Then a player's strategy is a function $f : {0,1}^{\mathbf{N}}\times\mathbf{N} \to \mathbf{N}$ that takes the number of past attempts into account, isn't it ? – Claude Chaunier Apr 07 '19 at 00:51
  • Or are the two chosen coins discarded from their respective binary sequences before the next attempt ? Is Alice allowed to remember what her different choices for $a$ have been ? – Claude Chaunier Apr 07 '19 at 01:08

2 Answers2

24

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

Édouard Maurel-Segala
  • 441
  • 13
    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 02 '19 at 09:13
  • 1
    Very nice and much more direct than my formulation ! – Édouard Maurel-Segala Apr 02 '19 at 11:13
  • 12
    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 : http://front.math.ucdavis.edu/1407.4711 – Édouard Maurel-Segala Apr 02 '19 at 12:31
  • 3
    Has the 81/224-result been written down somewhere? – Johan Wästlund Apr 04 '19 at 21:12
16

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

mihaild
  • 261
  • 4
    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 01:18
  • 1
    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
  • 3
    @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
  • 1
    Note that for even $N$, $p_N \neq \frac{7}{20} - \frac{2}{5\cdot 4^N}$ since the latter fraction is not of the form $k/4^N$. – Guillaume Aubrun Mar 31 '19 at 15:47
  • 3
    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
  • 4
    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 01 '19 at 23:02
  • Mixed strategy can't give better result then any pure strategy - just enumerate all possible results and for them one-by-one replace mix with number that maximizes winning probability. – mihaild Apr 02 '19 at 09:05
  • Does anybody have intuition about why one has to make the specific ordering: {010: 2, 011: 2, 001: 1, 110: 0, 100: 0, 101: 1}? In particular, it seems very far from the 1/3 strategy where I just guess on the first place where I myself have a 1. Can anyone prove that I can't have an ordering where I guess on a place where I have a 1 myself? – Frederik Ravn Klausen Apr 25 '22 at 08:16