# Expected number of unseen cards when drawing $2n$ cards from a deck of size $n$

We have a deck of $n$ cards. We draw cards from it uniformly at random with replacement. After $2n$ draws what is the expected number of cards never chosen?

This question is part 2 of problem 2.12 in

M. Mitzenmacher and E. Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press, 2005.

Also, for what it's worth, this is not a homework problem. It's self-study and I'm just stuck.

My answer thus far is:

Let $X_i$ be the number of distinct cards seen after the $i$th draw. Then:

$E[X_i] = \displaystyle \sum_{k=1}^{n} k (\frac{k}{n}P(X_{i-1}=k) + \frac{n-k-1}{n} P(X_{i-1}=k-1))$

The idea here is that each time we draw, we either draw a card we've seen or we draw a card we have not seen, and that we can define this recursively.

Finally, the answer to the question, how many have we not seen after $2n$ draws, will be $n-E[X_{2n}]$.

I believe this is correct, but that there must be a simpler solution.

Any help would be greatly appreciated.

• Have you simulated it and compared results?
– Adam
Nov 30, 2011 at 4:32

## 3 Answers

Hint: On any given draw, the probability that a card is not chosen is $\frac{n-1}{n}$. And since we're drawing with replacement, I assume we can say that each draw is independent of the others. So the probability that a card is not chosen in $2n$ draws is...

• (+1) This gives a good first start. Combining this with linearity of expectation leads to an economical and elegant solution. Nov 30, 2011 at 10:31

Thank you Mike for the hint.

This is what I came up with.

Let $X_i$ be a Bernoulli random variable where $X_i = 1$ if the $i^{th}$ card has never been drawn. Then $p_i = P(X_i=1) = (\frac{n-1}{n})^{2n}$, but since $p_i$ is the same for all $i$, let $p=p_i$.

Now let $\displaystyle X = \sum_{i=1}^n X_i$ be the number of cards not drawn after $2n$ draws.

Then $\displaystyle E[X] = E[\sum_{i=1}^n X_i] = \sum_{i=1}^n E[X_i] = \sum_{i=1}^n p = np$

And that does it I think.

• (+1) Also notice that for $n$ large, $p \approx e^{-2}$. Nov 30, 2011 at 20:23
• It may be a little more complicated than that. The probability that card(i) is missed is as you wrote. However, once we know that card(i) was missed, the probability of missing card(j) changes. I don't know whether the independence issue will change the final result but complicates the derivation. Sep 11, 2012 at 19:28
• @Emil Friedman: Expectation is linear whether the summands are independent or not. The lack of independence affects quantities like the variance, but not the expectation. Sep 24, 2012 at 20:16

Here is some R code to validate the theory.

evCards <- function(n)
{
iter <- 10000;
cards <- 1:n;
result <- 0;
for (i in 1:iter) {
draws <- sample(cards,2*n,T);
uniqueDraws <- unique(draws,F);
noUnique <- length(uniqueDraws);
noNotSeen <- n - noUnique;
result <- result + noNotSeen;
}
simulAvg <- result/iter;
theoryAvg <- n * ((n-1)/n)^(2*n);
output <-list(simulAvg=simulAvg,theoryAvg=theoryAvg);
return (output);
}