You are probably already familiar with the usual number guessing game. But for concreteness I restate it.

### The usual game

The **Oracle** chooses a positive integer $n$ between 1 and 1024 (or any power of 2).

At each turn, you make a guess $g$, and the Oracle tells you whether $n \leq g$ or $n > g$. The game ends when you can determine what $n$ is.

It is pretty easy to see that the optimal strategy requires exactly 10 turns.

### The modified game

In this game, the game runs almost exactly the same as the usual game. Except that there is a probability $p \in [0,1/2)$ (which is known to you) that the Oracle lies.

More precisely, at each turn, the Oracle flips a (biased) coin and determines, independently of previous actions and other things in the game, whether to lie to you or not. When she lies she gives the exact opposite of the correct answer for the comparison $n \leq g$ or $n > g$.

The game ends when you can determine, to a previously-agreed-upon confidence level, what is the answer $n$. (For argument sake, say that you can say with 95% probability what the value of $n$ is.)

To model this, imagine you starting with 0 knowledge, so that each number between 1 and 1024 is equally likely. At each step you can update the probability distribution using the usual Bayesian updating procedure. The game ends when one of the numbers has probability 95% or higher.

### Question

Can we estimate the expected number of guesses before the conclusion of the game, as a function of the lying probability $p$? (... and of the desired confidence level, and the number of bins?)

Obviously, if the confidence level is anything above 50%, and if $p = 0$, the game reduces the usual game.

As $p \to 1/2$, the expected number of guesses tend to infinity (at $p = 1/2$ the Oracle just responds randomly).

So in particular, what are the asymptotics of the number of guesses as $p \to 0$ and as $p \to 1/2$?

### Numeric Data

The simulations below using the following naive strategy for guesses:

At each step, based on the current "prior" probability, guess the number $g$ such that the difference $|P(n \leq g) - P(n > g)|$ is minimized.

In the case $p = 0$ this reduces (one can check) to the binary search method. This choice is made to "maximize information gained" from that step. I don't have a proof that this is the optimal strategy.

From numerical simulations, with 1024 numbers, 95% confidence interval, and 3000 trials,

```
p = 2^-2 avg = 56.806666666666665
p = 2^-3 avg = 23.315
p = 2^-4 avg = 16.112666666666666
p = 2^-5 avg = 13.047666666666666
p = 2^-6 avg = 11.633
p = 2^-7 avg = 10.604333333333333
p = 2^-8 avg = 10.285333333333334
p = 2^-9 avg = 10.156666666666666
p = 2^-10 avg = 10.069
p = 2^-11 avg = 10.029666666666667
p = 2^-12 avg = 10.011333333333333
p = 2^-13 avg = 10.005666666666666
p = 2^-14 avg = 10.0
p = 2^-15 avg = 10.0
```

For the other end, as $p \to 1/2$, as expected simulations take much longer, and so far I have the following data, based on 10000 simulation runs.

```
p = 0.5 - 2^-3 avg = 234.0019 min=48 max=763
p = 0.5 - 2^-4 avg = 937.3372 min=236 max=3437
p = 0.5 - 2^-5 avg = 3750.5765 min=896 max=13490
```

### Frequentist versus Bayesian

James Martin brought up a very good point about frequentist versus Bayesian. Let me illustrate that with data from two runs using the strategy described above, with $p = 2^{-8}$.

```
Starting game with 1024 bins.
Running game now with secret answer: 857
Guessing 512
Is secret number (857) bigger than guess? Oracle truthfully responds true
Update probabilities
Sanity check, total probabilities sum to 1.0
My best guess is that the secret answer is 513 with probability 0.00194549560546875
Guessing 767
Is secret number (857) bigger than guess? Oracle truthfully responds true
Update probabilities
Sanity check, total probabilities sum to 1.0000000000000002
My best guess is that the secret answer is 768 with probability 0.003875850705270716
Guessing 895
Is secret number (857) bigger than guess? Oracle truthfully responds false
Update probabilities
Sanity check, total probabilities sum to 0.9999999999999999
My best guess is that the secret answer is 768 with probability 0.007721187532297775
Guessing 831
Is secret number (857) bigger than guess? Oracle truthfully responds true
Update probabilities
Sanity check, total probabilities sum to 1.0000000000000004
My best guess is that the secret answer is 832 with probability 0.015441436261097105
Guessing 863
Is secret number (857) bigger than guess? Oracle truthfully responds false
Update probabilities
Sanity check, total probabilities sum to 0.9999999999999986
My best guess is that the secret answer is 832 with probability 0.030880965812145108
Guessing 847
Is secret number (857) bigger than guess? Oracle truthfully responds true
Update probabilities
Sanity check, total probabilities sum to 1.0000000000000013
My best guess is that the secret answer is 848 with probability 0.0617618727298829
Guessing 855
Is secret number (857) bigger than guess? Oracle truthfully responds true
Update probabilities
Sanity check, total probabilities sum to 0.9999999999999987
My best guess is that the secret answer is 856 with probability 0.12256258895055303
Guessing 859
Is secret number (857) bigger than guess? Oracle truthfully responds false
Update probabilities
Sanity check, total probabilities sum to 0.9999999999999982
My best guess is that the secret answer is 856 with probability 0.24704724796624977
Guessing 857
Is secret number (857) bigger than guess? Oracle truthfully responds false
Update probabilities
Sanity check, total probabilities sum to 0.9999999999999997
My best guess is that the secret answer is 856 with probability 0.4903092482458648
Guessing 856
Is secret number (857) bigger than guess? Oracle truthfully responds true
Update probabilities
Sanity check, total probabilities sum to 0.9999999999999998
My best guess is that the secret answer is 857 with probability 0.9881889766208873
I did it! And it only took me 10 tries; the Oracle lied 0 times.
```

Note that in binary, the number 857 is 1101011001 with more or less even distributions of zeros and ones. For 513 whose distribution is more extreme:

```
Starting game with 1024 bins.
Running game now with secret answer: 513
Guessing 512
Is secret number (513) bigger than guess? Oracle truthfully responds true
Update probabilities
Sanity check, total probabilities sum to 1.0
My best guess is that the secret answer is 513 with probability 0.00194549560546875
Guessing 767
Is secret number (513) bigger than guess? Oracle truthfully responds false
Update probabilities
Sanity check, total probabilities sum to 1.0000000000000033
My best guess is that the secret answer is 513 with probability 0.003875733349545551
Guessing 639
Is secret number (513) bigger than guess? Oracle truthfully responds false
Update probabilities
Sanity check, total probabilities sum to 0.9999999999999948
My best guess is that the secret answer is 513 with probability 0.007721187532297778
Guessing 575
Is secret number (513) bigger than guess? Oracle truthfully responds false
Update probabilities
Sanity check, total probabilities sum to 0.9999999999999996
My best guess is that the secret answer is 513 with probability 0.015323132493622977
Guessing 543
Is secret number (513) bigger than guess? Oracle truthfully responds false
Update probabilities
Sanity check, total probabilities sum to 1.0000000000000004
My best guess is that the secret answer is 513 with probability 0.030180182919776057
Guessing 527
Is secret number (513) bigger than guess? Oracle truthfully responds false
Update probabilities
Sanity check, total probabilities sum to 1.0000000000000004
My best guess is that the secret answer is 513 with probability 0.05857858737666496
Guessing 519
Is secret number (513) bigger than guess? Oracle truthfully responds false
Update probabilities
Sanity check, total probabilities sum to 0.999999999999996
My best guess is that the secret answer is 513 with probability 0.1106260320552282
Guessing 515
Is secret number (513) bigger than guess? Oracle truthfully responds false
Update probabilities
Sanity check, total probabilities sum to 1.0000000000000002
My best guess is that the secret answer is 513 with probability 0.19905831824030176
Guessing 513
Is secret number (513) bigger than guess? Oracle truthfully responds false
Update probabilities
Sanity check, total probabilities sum to 0.9999999999999991
My best guess is that the secret answer is 513 with probability 0.3315926624554764
Guessing 385
Is secret number (513) bigger than guess? Oracle truthfully responds true
Update probabilities
Sanity check, total probabilities sum to 1.0000000000000002
My best guess is that the secret answer is 513 with probability 0.6614346507956576
Guessing 512
Is secret number (513) bigger than guess? Oracle truthfully responds true
Update probabilities
Sanity check, total probabilities sum to 0.9999999999999979
My best guess is that the secret answer is 513 with probability 0.9902152355556972
I did it! And it only took me 11 tries; the Oracle lied 0 times.
```

Incidentally, this also explains (partly) the drop between $2^{-13}$ and $2^{-14}$ seen in the numerical results above. When $p = 2^{-13}$, when $n = 513$, after *10 truthful responses* the confidence that 513 is the correct answer is "only" 94%. But the 95% threshold is breached when $p = 2^{-14}$.

3more comments