What is the number of tries expected value

Question

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

Answer 1

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

Answer 2

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