Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I play a guessing game. In this game, there are 100 equally-sized, folded-up cards randomly dispersed in a bag. The cards are labeled 1 through 100. I draw out the cards one by one without replacement and try to guess the number on the card every time I draw. On every guess, I open up the card and see the actual number on it to see if I am correct.

I start by guessing a random number from 1 to 100. I will keep guessing randomly, but I will not guess a number that has already been revealed since that would be silly. How many numbers will I guess correctly?

I wonder if there is a difference between this problem and the problem in which I do not actually get feedback on what specific number I just drew. If there is no difference, then the expected value of correct guesses should be $\sum_{n = 1}^{100} \frac{n^2}{(n + 1)!}$, right?

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

When you make your $k$-th guess, you’ve seen $k-1$ numbers, so the probability of guessing correctly is $\frac1{101-k}$. This is also the expected value of the $k$-th guess, counting $1$ for a correct guess and $0$ for an incorrect guess. Thus, you want

$$\sum_{k=1}^{100}\frac1{101-k}=\sum_{k=1}^{100}\frac1k=H_{100}\;,$$

the $100$-th harmonic number.

In this version of the game, unlike the other one, the expected number of correct guesses grows without bound as the number of cards increases, albeit very slowly.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.