If two people each draw $n$ cards out of a deck of 52 distinct cards with replacement, find $n$ such that the expected number of common cards that both people drew is at least 1.

Since each card is replaced immediately after it's drawn, I am not sure how to compute this.

I was thinking that each card in drawing $n$ cards would have $\dfrac{n}{52}$ chance to be the same as one of the cards that are drawn by the first person. Then using properties of expectation, can I just sum up different $n$ values starting from 1 until the sum is greater than 1? Using this approach, I got $n$ should be 10 but I don't think that's right. Also, since it is at least 1, am I supposed to calculate the complement instead somewhere and subtract it by 1?

Thank you!

  • $\begingroup$ How did you get 10? Assuming that there is replacement only after the first person draws, then your idea seems right. Let $X_i$ be the indicator of the $i$th card of the second person being in the cards the first person drew. Then indeed $E[X_i]=\frac{n}{52}$ for all $i$, so if $Y$ is the number of common cards, $E[Y]=E[\sum_{i=1}^n X_i]=\sum_{i=1}^n E[X_i]=\frac{n^2}{52}$ (I think this is where your mistake is, the summands are all independent of $n$). What $n$ do you need to be greater than 1? $\endgroup$ – user293121 Jul 16 '17 at 2:13
  • $\begingroup$ Suppose A draws the king of spades, replaces it, B draws the jack of hearts, replaces it. Is a note kept of the cards drawn, so that if B draws the king of spades later, we say that a match has occurred, or is it round by round matching that counts ? $\endgroup$ – true blue anil Jul 16 '17 at 2:41
  • $\begingroup$ Yes. A note is kept for each person then we compare at the end after both drew n cards. $\endgroup$ – user463768 Jul 16 '17 at 3:07
  • $\begingroup$ I am not sure I understand what is meant by "the number of common cards". Suppose one player draws the ace of spades twice, the other draws the ace of spades three times, and there are no other common cards. What is the number of common cards? $\endgroup$ – awkward Jul 16 '17 at 14:21

$N$=52. Let $X_i, Y_i$ be the indicator that the $i$-th card was picked at least once by the first and second persons, respectively. By symmetry, $$\mathbb{E}[X_i]=\mathbb{E}[Y_i] = 1 - \mathbb{P}(i\textrm{-th card not picked in }n \textrm{ draws}) = 1 - \left(1 - \frac{1}{N}\right)^n$$ for all $i\in[N]$. The expected number of common cards is $$\mathbb{E}\left[ \sum_{i \in [N]} X_iY_i\right] = \sum_{i \in [N]} \mathbb{E}\left[X_iY_i\right] = \sum_{i \in [N]} \mathbb{E}\left[X_i\right] \mathbb{E}\left[Y_i\right] = N\left[1 - \left(1 - \frac{1}{N}\right)^n\right]^2.$$ For this to be at least 1, we need $$ N\left[1 - \left(1 - \frac{1}{N}\right)^n\right]^2 \geq 1 \Rightarrow n \geq \left\lceil \frac{\log\left( 1 - \frac{1}{\sqrt{N}}\right) }{ \log \left( 1-\frac{1}{N}\right) } \right\rceil = 8.$$

  • 1
    $\begingroup$ Does this take into account that the cards A drew could be $8$ all of one kind, $7-1$ of a kind, $6-2$ of a kind, and so on ? $\endgroup$ – true blue anil Jul 16 '17 at 9:13
  • $\begingroup$ @trueblueanil You point out a critical flaw in my solution, although the final answer remains unchanged (since $N$ is "large"). I believe I have fixed it now. Thanks. $\endgroup$ – ChargeShivers Jul 16 '17 at 16:56


The choices are:

For n=0 it is not possible, hence implies 0, over one case: the null case.

For n=1 trivially implies 52, over $52^2 $ choicss.

For n=2, at least one common implies $52 \ 52^2$, over $52^4$ choices.

For n=3, at least one common implies $52\ 52^4$, over $52^6$ choices.

For n=k, at least one common implies $52\ 52^{2k-2}$, over $52^{2k}$ choices.

Hence the expectation of n when having at least one common choice is: $$ \mathbb{E}\{n\}=\sum_{k=1}^{n} k p(k)=\sum_{k=1}^{n} {1 \over 52} k ={1 \over 52} {n(n+1) \over 2} $$

Which must be equal to 1, so: $$ n^2+n-104=0\\ n=\frac 12 (-1 \pm \sqrt{1+4 \ 104})= \frac 12 (-1 \pm \sqrt{417})\\ n = 10 $$

  • $\begingroup$ Is it possible to use a indicator variable to simplify this problem? $\endgroup$ – user463768 Jul 16 '17 at 3:14

Your Answer

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