0
$\begingroup$

Consider a number drawn from $U(1,100)$. When we make an incorrect guess, we are told whether the target number is smaller or larger. So we employ a binary search approach, where the first guess is 50. If that is not the target, then that means our next guess is going to be 25 or 75.

What is the probability that binary search ends in 2 guesses?

At first, I thought it was $P(B|A)P(A)$ where $A$ is the event that the first guess is wrong and $B$ is the event that the second guess is right. We know $P(A) = 99/100$. When $A$ occurs, that means we would either search in the interval $[1,49]$ or $[51, 100]$, which has 49 and 50, elements, respectively. So I believe $P(B | A) = 49/100 * 1/49 + 50/100 * 1/50 = 2/100$.

So $P(B|A)P(A) = 99/100 * 2/100 = 0.198$.

Then I second guessed myself and started wondering why is it not $2/100$? If it ends in 2 guesses, it means the target number is 25 or 75. Since the target number is uniformly chosen, the probability that it being 25 or 75 is $2/100=1/50 = 0.2$.

Both of these answers seem right to me, but 1 one of them must be wrong. Which one is wrong?

$\endgroup$
1
$\begingroup$

The correct answer is $0.02$, and your second approach is correct.

Here is how you can make your first approach work: You should multiply 2/99 (probability of ending at the second round given you did not end in the first round -- see below) by 99/100 (probability of not ending in the first round) and you will get the same answer. $$ P(B|A) = \frac{49}{99} \frac{1}{49} + \frac{50}{99}\frac{1}{50} = \frac{2}{99}. $$

$\endgroup$
8
  • $\begingroup$ I just realized that as well, but I'm not super confident on this. Could you explain to me what the $49/99$ and $50/99$ probabilities are in words? I believe it is the probability that 50 is greater than the target number and 50 is less than the target number, respectively? $\endgroup$ – 24n8 Apr 18 at 4:26
  • $\begingroup$ 49/99 is the probability of the event that the unknown number is smaller than 50 given that it is not 50. That is why it is 49/99. Similarly for 50/99. $\endgroup$ – Ahmad Beirami Apr 18 at 4:29
  • $\begingroup$ That makes more sense than saying "Probability that the unknown number is smaller than 50," because this would actually be $49/100$ instead of $49/99$. When we condition on 50 not being the correct number, we remove it from the sample space and reduce the 100 to 99. $\endgroup$ – 24n8 Apr 18 at 4:31
  • $\begingroup$ yes, that is correct. $\endgroup$ – Ahmad Beirami Apr 18 at 4:34
  • $\begingroup$ Why do you say the correct answer is $0.02\;\;viz \; \frac2{100}\,$ when you have worked it out as $\frac2{99}$ $\endgroup$ – true blue anil Apr 18 at 9:15
1
$\begingroup$

The second calculation is correct.

The mistake in the first calculation is that $\Pr(B|A)$is not $\frac2{100}$ but $\frac2{99}$ Once we know that $50$ is not the number, only $99$ possibilities remain. If you want to do it by formula, $$\Pr(B|A)=\frac{\Pr(B\cap A)}{\Pr(A)}=\frac{\Pr(B)}{\Pr(A)}=\frac{2/100}{99/100}=\frac2{99}$$

$\endgroup$
7
  • $\begingroup$ How would you compute $P(B|A)$ without $P(B)$, since that's what we're ultimately trying to solve for? I was envisioning what Ahmad did in their answer. $\endgroup$ – 24n8 Apr 18 at 5:13
  • $\begingroup$ @anonuser01 I would compute $\Pr(B)$ the way you did it in the second calculation. I would compute $\Pr(B|A)$ by saying there are $2$ possibilities for $B$ out of $99$ equally like possibilities once we know that $A$ has occurred. I'm just showing that the formula holds. $\endgroup$ – saulspatz Apr 18 at 12:42
  • $\begingroup$ You can also generalize the second approach to 3,4,5, etc.. guesses right? Each time the number of possibilities would double. So for 3 guesses, the probability is 4/100, for 4, it's 8/100, for 5, it's 16/100, for 6, it's 32/100. But after 6 guesses, things work a little differently $\endgroup$ – 24n8 Apr 18 at 15:39
  • $\begingroup$ Actually after 6 guesses, it's simple because 7 is the maximum number of glasses for binary search here. So for 7 guesses, it's simply (100-1-2-4-8-16-32)/100 = 37/100 $\endgroup$ – 24n8 Apr 18 at 15:41
  • $\begingroup$ @anonuser01 The probability that it takes $7$ guesses is $\frac{37}{100}$ because $1+2+4+\cdots+32=63$ and $100-63=37$, and it never takes more than $7$ guesses. $\endgroup$ – saulspatz Apr 18 at 15:47
0
$\begingroup$

The probability that it ends in 1 guess is 1 in 100. For ending in 2 guesses, you must first miss the first then make the second.

Missing the first is probability 99/100. But now, your solution set is cut down to either 49 or 50 numbers (depending on whether you were above or below). If you are above, your probability of being correct is 1/49. If you are below, it is 1/50. We can average these two probabilities since they are equally likely.

The answer is approximately $.0202$.

$\endgroup$
4
  • $\begingroup$ It's only cut down to 49 numbers if 50 is larger than the target number. If 50 is less than the target number, then the solution could be in $\{51, \ldots, 100\}$, which is 50 numbers. $\endgroup$ – 24n8 Apr 18 at 4:23
  • $\begingroup$ Ah good point. Let me make an edit. $\endgroup$ – roddur Apr 18 at 4:24
  • $\begingroup$ I don't think 2/99 is right (as others are saying) though. There surely isn't 99 options left but rather 50 or 49. My intuition is that you average the probabilities of each. $\endgroup$ – roddur Apr 18 at 4:31
  • $\begingroup$ I initially thought this as well, but the "average" is a weighted average, and I think @Ahmad's solution for $P(B|A)$ shows what that weighted average should look like $\endgroup$ – 24n8 Apr 18 at 4:32

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.