0
$\begingroup$

Suppose you played two rounds of a game of cards. Each round you are independently dealt an $n$-card hand from a shuffled deck (e.g., n=5 $n=13$ for Bridge, $n=7$ for Hold'em, etc) .

Q1 (Motivating): In a game involving $n$-card hands, what is the probability that your first hand is disjoint from your second hand? That is, what is the probability your successive hands share no cards in common?

Where I'm getting stuck is generalizing this question to an $m$-card deck, $n$-card hand, and, in particular, a $k$-round game:

Q2 (General): After $k$ independent rounds of a game of $n$-card hands from a shuffled $m$-card deck, what's the probability all hands are disjoint (i.e., that you don't see the any card more than once)?

Clearly $P(disjoint\; hands)=1$ after just $k=1$ round, and by the pigeonhole principle $P(disjoint\; hands)=0$ after $k=\lceil\frac{n}{m}\rceil$ rounds. But I'm stuck reasoning through a closed-form equation.

Ultimately I'm interested in the $P=0.5$ scenario, something akin to the birthday paradox, namely:

Q3 (Goal): How many rounds of a (generalized) card game do you have to play before you would expect to see one (or more) cards repeated across hands?

Thanks for the help!

$\endgroup$
  • $\begingroup$ Bridge uses 13-card hands not 5. No clue as to author's thoughts or context of this question. $\endgroup$ – BruceET Apr 2 '15 at 0:09
1
$\begingroup$

Given an $m$ card deck, how likely are you to to draw $k$ consecutive, disjoint hands, each of which have $n$ cards?

Let's assume, for some $k\geq 2$, that your previous $k-1$ hands have been disjoint. Then you have seen exactly $n*(k-1)$ cards thus far. Therefore your next hand must come solely from the remaining $m-n*(k-1)$ cards in the deck that you have not seen. There are $$ \binom{m-n*(k-1)}{n} $$ ways of choosing such a hand, and there are $$ \binom{m}{n} $$ total hands that you could be dealt. Thus the probability that your $k$th hand will consist of cards that you have not see yet, given that your previous $k-1$ hands have been disjoint, is $$ \frac{\binom{m-n*(k-1)}{n}}{\binom{m}{n}}. $$ Letting $P(k)$ be the probability of getting $k$ consecutive disjoint hands, we thus have the recurrence relation $$ P(1)=1, \:P(k)=\frac{\binom{m-n*(k-1)}{n}}{\binom{m}{n}}P(k-1). $$ Therefore $$ P(k)=\frac{\prod_{j=1}^{k-1}\binom{m-n*j}{n}}{\binom{m}{n}^k} $$

$\endgroup$
0
$\begingroup$

Q1 (Motivating): In a game involving n -card hands, what is the probability that your first hand is disjoint from your second hand? That is, what is the probability your successive hands share no cards in common?

Assume this is using a deck of $52$ unique cards. You want the probability of selecting $n$ from the $52-n$ cards you did not select last time out of all the ways to select $n$ from $52$.

$$\begin{align} \mathsf P_2 & = \dfrac{\dbinom{52-n}{n}}{\dbinom{52}{n}} \\[1ex] & = \dfrac{(52-n)!^2}{52!(52-2n)!} \end{align}$$

Alternatively, this is the way to select $2n$ cards out of $52$ then sort them into ordered collections of $2$ unordered sets of $n$, out of all the ways to select any $n$ cards from $52$ twice.

$$\begin{align} \mathsf P_2 & = \dfrac{\dbinom{52}{2n}\dfrac{(2n)!}{n!^2}}{\dbinom{52}{n}^2} \\[1ex] & = \dfrac{(52-n)!^2}{52!(52-2n)!} \end{align}$$

Q2 (General): After k independent rounds of a game of n -card hands from a shuffled m -card deck, what's the probability all hands are disjoint (i.e., that you don't see the any card more than once)?

So you want to count the ways to choose $nk$ distinct cards from $52$, then sort them into into an ordered collection of $k$ unordered groups of $n$, then divide this count by all ways to select any $n$ from $52$ cards, $k$ times over.

$$\mathsf P_k = \dfrac{\dbinom{52}{nk}\dfrac{nk!}{n!^k}}{\dbinom{52}{n}^k}$$

Now, can you simplify and complete?

$\endgroup$

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.