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

$\endgroup$
7
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Oct 4, 2012 at 6:35
  • $\begingroup$ 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. :) $\endgroup$ Commented Oct 4, 2012 at 6:37
  • 2
    $\begingroup$ 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. $\endgroup$
    – mjqxxxx
    Commented Oct 4, 2012 at 6:44
  • $\begingroup$ 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. $\endgroup$
    – user22805
    Commented Oct 4, 2012 at 7:48
  • $\begingroup$ @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". $\endgroup$ Commented Oct 4, 2012 at 11:16

2 Answers 2

1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .