10
$\begingroup$

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.

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

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

| cite | improve this answer | |
$\endgroup$
  • 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 '11 at 10:31
6
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 4
    $\begingroup$ (+1) Also notice that for $n$ large, $p \approx e^{-2}$. $\endgroup$ – Dilip Sarwate Nov 30 '11 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$ – Emil Friedman Sep 11 '12 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$ – Douglas Zare Sep 24 '12 at 20:16
4
$\begingroup$

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);
}
| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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