# How many numbers will I get right?

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 and try to guess the number on the card every time I draw. On every guess, a genie will tell me if I am correct or not (but he won't tell me the actual number on the card).

I start by guessing that the card has 1 on it. I keep guessing that the card has 1 on it until I am correct, after which I will keep guessing 2 until I am correct again, after which I will keep guessing 3, and so on until the bag is empty. How many correct guesses should I expect?

My current hunch is that the answer is 1 since this looks like a binomial distribution, and $52\frac{1}{52} = 1$. However, I feel suspicious since there's that genie that gives me extra information...

-
Are you asking about that particular strategy, or an optimal strategy? Even for the $1,1,\dots,2,\dots$ strategy, the expectation is $\gt 1$, since for sure you will get at least $1$ right, and maybe more. –  André Nicolas Oct 4 '12 at 6:35
Just for that particular "strategy." It would be interesting to look at the optimal strategy... but I think that might open up a new can of worms. :) –  Minden Petrofsky Oct 4 '12 at 6:37
I think this is the optimal strategy. The most likely next draw is the one you've guessed most often so far but haven't yet seen. –  mjqxxxx Oct 4 '12 at 6:44
What happens if you draw 2 before you draw 1? Do you then guess 3 (or whatever number is the next unseen one) once you find 1? If so, that would be optimal. If you don't skip the numbers that you've seen, then it's definitely not optimal. –  user22805 Oct 4 '12 at 7:48
@David Wallace - if he is not correct, the genie will not tell him the actual number on the card. So he will only know that a sequence of "not-1"s was followed by a "1". –  Viliam Búr Oct 4 '12 at 11:16

You’re certain to get at least one correct guess, and in many cases you’ll get more than one, so the expected number of correct guesses is clearly more than one. You’ll get a second correct guess whenever you draw the $1$ before you draw the $2$; the probability of that is $\frac12$, so the expected number of correct guesses can already be seen to be at least $\frac12\cdot1+\frac12\cdot2=\frac32$.

In general you’ll get at least $n$ correct guesses if the numbers $1,\dots,n$ appear in their correct order, ignoring any larger numbers that may appear between them. The probability of that is $\frac1{n!}$, since all $n!$ orders in which they could appear are equally likely. The probability that $n+1$ is the last of the set $\{1,\dots,n+1\}$ to be drawn is $\frac1{n+1}$, so the probability that it is drawn before you draw all of the smaller numbers is $\frac{n}{n+1}$.

Thus, the probability that you’ll get exactly $n$ correct guesses is $$\frac1{n!}\cdot\frac{n}{n+1}=\frac{n}{(n+1)!}\;,$$ and the expected number of correct guesses is

$$\sum_{n=1}^{100}\frac{n}{(n+1)!}\cdot n=\sum_{n=1}^{100}\frac{n^2}{(n+1)!}\;.$$

Now $$e^x=\sum_{n\ge 0}\frac{x^n}{n!}\;,$$ so $$\frac{e^x-1}x=\sum_{n\ge 1}\frac{x^{n-1}}{n!}=\sum_{n\ge 0}\frac{x^n}{(n+1)!}\;,$$

$$x\frac{d}{dx}\left(\frac{e^x-1}x\right)=\sum_{n\ge 0}\frac{nx^n}{(n+1)!}\;,$$ and

$$\frac{d}{dx}\left(x\frac{d}{dx}\left(\frac{e^x-1}x\right)\right)=\sum_{n\ge 0}\frac{n^2x^{n-1}}{(n+1)!}\;.\tag{1}$$

Finally, $$\frac{d}{dx}\left(x\frac{d}{dx}\left(\frac{e^x-1}x\right)\right)=\frac{d}{dx}\left(\frac{xe^x-e^x+1}x\right)=e^x-\frac{(x-1)e^x}{x^2}-\frac1{x^2}\;.\tag{2}$$

Evaluating the righthand sides of $(1)$ and $(2)$ at $x=1$, we see that

$$\sum_{n\ge 1}\frac{n^2}{(n+1)!}=e-1\;,$$ so the expected number of correct guesses is just a hair less than $e-1\approx 1.718281828459045$.

-

Though you don't say so, I assume that cards are discarded once they're removed from the bag. The key observation is that you will get at least $n$ correct guesses if and only if the first $n$ cards (that is, the cards numbered $1,2,\ldots,n$) appear in the correct order among your draws. Since each of the $n!$ orderings of the first $n$ cards within your random list of draws is equally likely, you'll get at least $n$ correct guesses with probability $(1/n!)$. Therefore the probability of getting exactly $n$ correct guesses must be $$\frac{1}{n!}-\frac{1}{(n+1)!}=\frac{1}{n!}\left(1-\frac{1}{n+1}\right)=\frac{n}{(n+1)!},$$ and the expected number of correct guesses is $$\sum_{n=1}^{100}\frac{n^2}{(n+1)!} \approx (e-1) = 1.718281828\ldots$$

-