1
$\begingroup$

We choose a random number from 1 to 10. We ask someone to find what number it is by asking a yes or no question. Calculate the expected value if the person ask if it is $x$ number till you got it right?

I know the answer is around 5 but i can't find how to get there.

I tried $\frac{1}{10}(1)+\frac{1}{9}(2)+\frac{1}{8}(3)+\frac{1}{7}(4)+\frac{1}{6}(5)+\frac{1}{5}(6)+\frac{1}{4}(7)+\frac{1}{3}(8)+\frac{1}{2}(9)$

but it doesn't work. Any help to point me in the right direction would be greatly appreciated.

Thank you

$\endgroup$
  • 1
    $\begingroup$ The probability, that the person has to be asked two times is $\frac{9}{10}\cdot \frac{1}{9}$ It is comprehensible ? What is the probability, that a person has to be asked three times ? $\endgroup$ – callculus Nov 10 '15 at 23:23
  • $\begingroup$ actually the answer is 5.5 in the book. Maybe I did not ask the question clearly since i had to translate. $\endgroup$ – spexel Nov 10 '15 at 23:34
  • $\begingroup$ Your question is quite clear. Have you understood my comment ? Can you answer my question in the comment ? $\endgroup$ – callculus Nov 10 '15 at 23:38
1
$\begingroup$

If you have to guess one from $n$

  • your first guess has $\frac 1 n$ chance of being right; and
  • if it isn't, you are faced with guessing $1$ from $n - 1$.

So the expected number of guesses $$ X_ n = \frac 1 n + \frac {n - 1} n (1 + X_{n - 1})$$ kicking off with $$X_1 = 1$$

The first two or three cases suggest

$$X_n = \frac {n + 1} 2$$

Let's prove it by induction:

If, for some $n$,

$$X_{n - 1} = \frac n 2 $$

then

$$\begin{align} X_ n & = \frac 1 n + \frac {n - 1} n (1 + \frac n 2) \\ & = 1 + \frac {n - 1} 2 \end{align}$$

So $$ X_n = \frac {n + 1} 2 $$

So it's true for $n + 1$.

For your example,

$$X_{10} = 5.5$$

$\endgroup$
1
$\begingroup$

I will assume, as seems clear from the post, that our guesses all have to be of the kind "Is the number $k$?" With smarter questions, one can do considerably better, particularly if the number of possibilities is large.

I will also assume that even if we have asked $9$ times and gotten the answer no, we need to go through the formal process of asking the 10th time. In that case the number of questions is equally likely to be any of the numbers $1$ to $10$. That gives mean $\frac{1}{10}(1+2+\cdots+10)$, which is $5.5$.

If we don't need to formally ask a tenth question once we have made $9$ wrong guesses, the mean is $\frac{1}{10}(1+2+\cdots+9+9)$, which is $5.4$.

$\endgroup$
  • $\begingroup$ $\frac{1}{10}\cdot\frac{1+2+\cdots+10}{2}=2.75\neq 5.5$ I don´t know why you have a 2 in the denominator. $\endgroup$ – callculus Nov 10 '15 at 23:49
  • $\begingroup$ Thanks! When I was writing it up, I had the explanation that $1+\cdots+10=\frac{(10)(11)}{2}$, which I decided to omit, but the pasting was then done incorrectly. $\endgroup$ – André Nicolas Nov 10 '15 at 23:55
  • $\begingroup$ what is the formula you used to get that? $\endgroup$ – spexel Nov 11 '15 at 0:21
  • $\begingroup$ Well, the sum $1+2+\cdots+10$ is short, we could do it without formula. But in general $1+2+3+\cdots+n=\frac{(n)(n+1)}{2}$. Here $n=10$, so the sum is $(10)(11)/2$, which is $55$. Finally, we multiply by $1/10$ as in the answer, getting $5.5$. $\endgroup$ – André Nicolas Nov 11 '15 at 0:22

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.