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.

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

3 Answers 3


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

  • 3
    $\begingroup$ (+1) This gives a good first start. Combining this with linearity of expectation leads to an economical and elegant solution. $\endgroup$
    – cardinal
    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.

  • 4
    $\begingroup$ (+1) Also notice that for $n$ large, $p \approx e^{-2}$. $\endgroup$ Nov 30, 2011 at 20:23
  • $\begingroup$ 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. $\endgroup$ Sep 11, 2012 at 19:28
  • $\begingroup$ @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. $\endgroup$ 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);

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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