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!
Best Answer
$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.$$