I was given a nice riddle, and solved it, and I can't tell if my solution is optimal or not.
The riddle is a follows:
Two infinite sequences $a_n, b_n$ of bits are randomized. The sequence $a_n$ is shown to you, and the sequence $b_n$ to your friend. Each of you has to guess a number, say $n_1, n_2$, respectively. If $a_{n_2} = b_{n_1}$ you (both) win, otherwise you (both) lose. Formulate a strategy to win more than 50% of the games.
I've thought of the following solution:
Each player guesses the index of the first bit that equals $1$.
There's a probability of $\frac{1}{4^n}$ that both of us guessed the $n$-th index, which will be a win, as both indexes will have the value $1$. Hence, there's a probability of $\ \sum\frac{1}{4^n} = \frac{1}{3}\ $ that both of us guessed the same index and therefore won.
Otherwise, WLOG I guessed a smaller index ($n_1 < n_2$), and therefore $b_{n_1} = 0$, and $a_{n_2}$ is some random bit. Therefore, If we didn't guess the same index, the probability of us winning is $\frac{1}{2}$.
Therefore this solution gives a winning probability of $\frac{2}{3}$.
Is this an optimal solution to this question?
- Is there a better solution?
- If not, can someone provide a proof?