Probability of sharing cards drawn from different decks?

Question

I have been struggling with the following problem, which I have been trying to solve combinatorially, but without much success.

Suppose n players each have a deck of cards. Each player randomly draws a hand of m cards from their own deck.

The easier part of the question is: what is the probability that there is (at least) one card which appears in every player's hand?

But I am really more interested in the harder part of the question: what is the probability that there is (at least) one set of k cards such that every player has one of the k cards in his hand?

For example, when $k=2$, what is the probability that we can find a pair of cards A and B such that every player has either or both of A and B among his hand of m cards?

Any advice on how to proceed or where this might have been previously covered would be much appreciated.

Answer 1

Your calculation of the first case is not correct. Note that $\bigg( \binom{51}{m-1}\bigg/\binom{52}{m}\bigg)=\frac m{52}$ and you are correct that $\frac m{52}$ of the hands will contain a specific card. But you have double counted the cases where all hands share two cards. You need to use the inclusion-exclusion principle to correct for this.

Answer 2

Let $X_j$ be the number of cards that the first $j$ players have in common. Thus $X_1 = m$ and $P(X_{j+1}=x | X_j = y) = \dfrac{{y \choose x} {{52 - y} \choose {m-x}}}{52 \choose m}$ for $0 \le x \le y$, so you can calculate the probabilities from the recursion $$P(X_{j+1}=x) = \sum_{y=x}^m \dfrac{{y \choose x} {{52 - y} \choose {m-x}}}{52 \choose m} P(X_j = y)$$ For example, with $m=13$ I get the following approximate values for $P(X_j = 0)$:

$$\left[ \begin {array}{cc} j & P \left( X_{j}=0 \right) \\ 1& 0.0\\ 2& 0.01279094804 \\ 3& 0.4141821823\\ 4& 0.8121444120\\ 5& 0.9501446600\\ 6& 0.9873595189\\ 7& 0.9968294020 \\ 8& 0.9992067330\\ 9& 0.9998016469\\ 10& 0.9999504096\end {array} \right] $$

Answer 3

Thanks for the answers so far to this question. I think I have now solved the easier part of the question, using an inclusion-exclusion argument (as you suggest Ross) to count the number of possible combinations of hands where there is a card common to all players.

Suppose there are 3 players ($n=3$) and each draws 2 cards ($m=2$). The total number of possible arrangements of different hands is then $\binom{52}{2}^3$. Of these arrangements, the number where every player's hand includes some named card (say, ace of spades) is $\binom{51}{1}^3$. Summing over all possible cards gives $52 \times \binom{51}{1}^3$ but this will double count the $\binom{52}{2}$ arrangements where every player holds the same two cards. So the total number of arrangements where at least one card is shared is $52 \times \binom{51}{1}^3 - \binom{52}{2}$, and the probability of such an arrangement is:

$$\frac{52 \times \binom{51}{1}^3 - \binom{52}{2}}{\binom{52}{2}^3}$$

Generalising this argument to higher m and n gives the general formula for the probability:

$$\frac{\sum_{i=1}^{m}(-1)^{(i+1)}\binom{52}{i}\Big(\binom{52-i}{m-i}^n\Big)}{\binom{52}{m}^n}$$

I've done some quick calculations in Excel to check the case $m=13$ and agree with the numbers provided by Robert.

Moving on to the harder part of the question, I have found the probability that there are k (or fewer) cards that "cover" all players for the special case where $m=1$ (each player picks one card). Counting the ways of needing exactly j cards to cover all individuals, using an inclusion-exclusion argument, and summing j from 1 to k gives:

$$\frac{\sum_{j=1}^{k}\binom{52}{j}\sum_{i=0}^{j-1}(-1)^i\binom{j}{j-i}(j-i)^n}{52^n}$$

However, as yet I've got no further with generalising for $m>1$...