1
$\begingroup$

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

  • 0
    Oh, sorry, my mis$t$ake. I shouldn't post comments late at night. Yes, this strategy is certainly optimal then.2012-10-04

2 Answers 2

1

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

1

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$