1
$\begingroup$

Problem

Let $N$ be the number of cards in a deck. Each card is different and unique. One after the other each player:

  • draws $M$ many cards from the deck
  • writes down/memorizes what cards (s)he got
  • puts the cards back in the deck
  • shuffles the deck
  • and passes it to the next player

If there are $X$ many players in the game, what is the probability of one or more cards having been drawn by more than 1 player?

Question

I would like to know a formula for how to calculate the probability for a given combination of $(N, M, X)$. It would be really nice to get an example calculation too, for $N = 100, M = 5, X = 3$.

Motivation

Just for fun I am working on a little card game. I need to find out how many cards I need in the deck to maximize the probability of "fun" gameplay interactions. My assumption is that the game would be most fun if it was possible for two players to have drawn the same card, but unlikely for them to have drawn the same hand.

Thank you all very much.

$\endgroup$
  • $\begingroup$ Try working out the complementary probability: that no two players draw the same card. That's pretty straightforward. $\endgroup$ – saulspatz Oct 24 at 19:58
1
$\begingroup$

Suppose no two players have drawn the same card. The probability you seek is the complement.

So, this gives the probability you are looking for as:

$$1-\dfrac{\displaystyle \prod_{k=0}^{X-1}\dbinom{N-kM}{M}}{\dbinom{N}{M}^X} = 1- \dfrac{(N-M)!}{(N-MX)!\left( M!\dbinom{N}{M} \right)^{X-1}}$$

So, given your sample values:

$$1-\dfrac{95!}{85!\left(5!\dbinom{100}{5}\right)^2} \approx 55\%$$

So, there is a better than average chance that at least two people will have drawn at least one card the same.

$\endgroup$
  • $\begingroup$ thanks a bunch! What would I do to calculate the average number of cards drawn two or more times? $\endgroup$ – DudeDoesThings Oct 24 at 20:28
  • $\begingroup$ For that, I would recommend a separate question. That is a much more difficult question. That is the complement of the Coupon Collector's problem. $\endgroup$ – InterstellarProbe Oct 24 at 20:47

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.