14
$\begingroup$

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

Improve this question
$\endgroup$
8
  • $\begingroup$ Couldn't one bound the number of required queries by calculating the expected number of bits provided by each question ($-p \log p$) and dividing the required 10 bits by that number of bits per question? $\endgroup$
    – David G. Stork
    Commented Aug 17, 2018 at 5:25
  • 2
    $\begingroup$ OK, I understand a little better now. If you follow binary search, and the oracle says "bigger" once and then "smaller" 9 times in a row, the conditional probability that 513 is the correct answer (assuming all numbers a priori equally likely) is not as big as I thought; for example, if $(1-p)/(512p)<1$, then it's more likely that the original number was in $[1,512]$ and the first answer was a lie. So even when "follow the binary search strategy" DOES provide a 95% confidence answer in a frequentist sense, it needn't always give an answer with 95% posterior probability in a Bayesian sense. $\endgroup$
    – James Martin
    Commented Aug 17, 2018 at 13:07
  • 1
    $\begingroup$ @DavidG.Stork: in particular, my understanding of the information theoretic argument is that it gives a theorem of the following form: let $\epsilon > 0$ be arbitrary, and $p\in [0,1/2)$ (the lying probability) be fixed. Then there exists some $K > 0$ such that for all version of this game with $2^k$ bins when $k \geq K$, that the expected number of guesses to reach certainty $1-\epsilon$ is approximately $(1 - H_b(p)) k$. $\endgroup$
    – Willie Wong
    Commented Aug 17, 2018 at 13:17
  • 1
    $\begingroup$ @JamesMartin: thanks for calling me on that! I meant to include it but it was late last night and I forgot. I've edited the question to include my strategy. The idea is to naively follow as closely binary search as possible: choose the number so that, based on current estimates, the probability below and the probability above are as close to equal as possible. $\endgroup$
    – Willie Wong
    Commented Aug 17, 2018 at 13:22
  • 1
    $\begingroup$ @JamesMartin: Even though it doesn't work for the naive power $2^{-7.61}$, I think you are still onto something. It looks like for all sufficiently small $p$, binary search should yield the correct answer with sufficiently high probability. This would settle the question of the small $p$ asymptotics. $\endgroup$
    – Willie Wong
    Commented Aug 17, 2018 at 13:41

1 Answer 1

Reset to default
5
$\begingroup$

If $p$ is small enough that you can upper bound the number of lies by some $k_{max}$, the problem is called Ulam's game. Some coding theoretic approaches work in this case, Berlekamp has worked on this. See David DesJardin's PhD thesis, e.g.

See also, Rivest, Ronald L.; Meyer, Albert R.; Kleitman, Daniel J.; Winklmann, K. Coping with errors in binary search procedures 10th ACM Symposium on Theory of Computing. doi:10.1145/800133.804351.

and

Pelc, Andrzej (1989). "Searching with known error probability Theoretical Computer Science. 63 (2): 185–202. doi:10.1016/0304-3975(89)90077-7.

See also this recent paper on arxiv for a good review of related results including lies as well as inversions and other disorder here

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the useful references! The most relevant seems to be that of Pelc, the others seem to require some a priori bound on the number of lies. Interestingly, Pelc proposes a (non-optimal) algorithm which consists basically of asking the same question sufficiently many times to be sufficiently sure, doing a binary search, and estimating essentially as James Martin and I discussed. $\endgroup$
    – Willie Wong
    Commented Aug 17, 2018 at 13:58
  • 2
    $\begingroup$ Let me just add also that, following this answer, I found this review article by Pelc from 2002; the relevant discussion is in section 5.2. Summary: Renyi found a lower bound basically arguing as David Stork did in a comment above which grows like the log of the number of bins. For fixed $p\in [0,1/2)$ and confidence, Pelc gives algorithms with number of questions growing like log of the number of bins. $\endgroup$
    – Willie Wong
    Commented Aug 17, 2018 at 14:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .