How to calculate the average number of guesses made to guess a number between 0 and 31?

Question

I know this question is very basic, but my question is more about Mathematical thinking. How to think mathematically:

Suppose person $A$ chooses a number from numbers between $0$ and $31$, and person $B$ has to guess which number he chose. Suppose $B$ will guess by Linear Search, i.e. they will check $1$, if incorrect then they will guess $2$ if incorrect, they will guess $3$ and so on $\dots$

If $A$ had chosen 1, then $B$ would make $1$ guess; if $A$ had chosen $30$, then $B$ would make $30$ guesses. So the question is: How many guesses does $B$ make on average?

I have been told that the answer is $15$.

My question is how? How would I know that B will make $15$ guesses on average?

Answer 1

Here is a symmetry argument for you. Call an ordering of $\{0,1,2,\ldots,31\}$ a strategy. Two sample strategies are $0,1,2,\ldots, 31$ and $0,31,1,30,\ldots,15,16$. Each strategy leads to a payoff, depending on what number A picked.

Now, for each strategy, there is an "opposite" strategy, which consists of the same numbers in opposite order. The opposite strategy to $0,1,2,\ldots, 31$ is $31,\ldots, 2,1,0$. Now, suppose we play the game twice. A must pick the same number both times. B can pick whatever strategy he or she wants for the first game, but must pick the opposite strategy for the second game. It is easy to see that regardless of what number A picks, and regardless of the strategy B uses, for the two games combined the total number of guesses will be exactly 33. Hence, on average, it takes 16.5 guesses (33/2).

Since every strategy has exactly one opposite, we can see that on average it takes 16.5 guesses (not 15). This assumes that 0 and 31 are valid numbers. If not, then 15.5 is correct.

Answer 2

I'm assuming you mean $A$ is selecting from the numbers $1, 2, \dots, 29, 30$.

We're going to have to assume $A$ chooses uniformly at random (that is, with probability $\frac{1}{30}$ for each number).

Then write $X_a$ for the number of guesses $B$ makes, given that $A$ picked number $a$. We have $X_a = a$, because if $A$ picked $1$ then $B$ guesses once and is correct on that guess, so $X_1 = 1$, and so on.

Then the mean of the $X_a$ is what we're looking for, and that is $$\mathbb{E}(X_A) = \sum_{a=1}^{30} \mathbb{P}(A = a) \mathbb{E}(X_A \mid A = a) = \sum_{a=1}^{30} \frac{1}{30} \times a = \frac{1}{30} \sum_{a=1}^{30} a = \frac{1}{30} \times \frac{30 \times 31}{2}$$

That is $$\frac{31}{2} = 15.5$$