Choosing a number between $1$ and $100$, and randomly guessing it. What is the expected value of the number of guesses?

I was watching Steve Balmer’s interview and he was talking about questions they’d ask from candidates. This is a question he gave, he says-

I choose a number between $1$ to $100$, the other person has to guess the number. If he gets it right the first time he gets $5$ bucks, if he misses the first time steve tells you whether the number is higher or lower( he does this every time you miss), if he gets it right the second time he gets $4$ bucks, third time $3$, fourth $2$ and so on and if he gets it right in the seventh guess the person has to give a buck to Steve and so on, the value goes decreasing. I am trying to calculate the expected value of this game, how can I solve this, I can’t seem to come up with a way.

P.S. I have edited the question with a slight variation, in the previous version steve doesn’t tell you anything after you have guessed the wrong number.

Solution 1:

The answer posted by Jorge is right. Just to add some clarifications.

In the first try you have $\frac 1 {100}$ chance of guessing it right. On the second guess, your chance increases to $\frac 1 {99}$ as you know the answer isn't your guess and you aren't going to make the same guess. However, the probability that you are going to make the second guess (i.e. you guess the first one wrong) is $\frac {99} {100}$ so the probability is again, $\frac 1 {99}$ * $\frac {99} {100}$ = $\frac 1 {100}$. With same logic, your probability of guessing it right on the nth try is always $\frac 1 {100}$

The rest of the calculation checks out.

$$\sum\limits_{i=1}^{100} \frac{6-i}{100} = 6 - \frac{100\times 101}{2\times 100}=6-50.5=-45.5$$

Solution 2:

The probability you get it right at the i'th time is $\frac{1}{100}$.

Thus the expected value of the game is $$\sum\limits_{i=1}^{100} \frac{6-i}{100} = 6 - \frac{100\times 101}{2\times 100}=6-50.5=-44.5$$

Solution 3:

If Steve tells you whether the number is higher or lower then, you will at most lose a dollar. Going by the binary approach, you start with 50, worst situation: more numbers on the side which Steve's number is, up you go 75(as 50 on higher side and 49 on the lower side), then 88, then 94, then 97, 99 and finally 98 or 100. Even if you start with 50 and the number is lower than 50, you still pay a dollar at most.

I have arbitrarily chosen the higher end in each case to have equal to or more numbers than the lower end.

Taking this to be the most conservative approach and that you only follow this, if you want to find the average amount gained or lost, find the value for each number (formulate, no need to solve for each) and take average.

Solution 4:

Let $X_t:=1\{\text{guess at stage $t$ is correct}\}$ and let $T:=\min\{t:X_t=1\}$. Then for $1\le t\le 100$, \begin{align} \mathsf{P}(T=t)&=\mathsf{P}(X_t=1,X_{t-1}=0,\ldots,X_1=0) \\ &=\mathsf{P}(X_t=1|X_{t-1}=0,\ldots,X_1=0)\times\mathsf{P}(X_{t-1}=0,\ldots,X_1=0) \\ &=\frac{1}{100-(t-1)}\times\binom{99}{t-1}\binom{100}{t-1}^{-1}=\frac{1}{100}. \end{align} Thus, the stopping time $T$ is uniformly distributed on $\{1,\ldots,100\}$ and its mean is $50.5$. Since at each step you loose $1$\$, the mean loss is $6-50.5=-44.5$.