Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
I found the equation to be correct, and I might be missing something, can you explain a situation where he "double counts". –  Vigneshwaren Jun 7 '12 at 15:55
    
Equation now removed - it was incorrect because it would count twice each arrangement of cards where all players had 2 out of m cards in common. Plus of course higher numbers of shared cards up to the case where all players are holding the same m cards. –  Nick Jun 7 '12 at 16:50

3 Answers 3

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.

share|improve this answer
1  
To clarify slightly: change "$\frac{m}{52}$ of the hands will contain" to "$\frac{m}{52}$ is the probability that a specific hand will contain"... –  Robert Israel Jun 7 '12 at 15:48
    
Thanks Ross - agree with you and had come to the same conclusion since posting the question. Am editing question to reflect this... –  Nick Jun 7 '12 at 16:15

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] $$

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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