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

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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);
}