Card Game Probability Difficulties

Question

Construct a $30$ card deck including $w$ doubles in the following manner:

1) Remove all jokers, face cards, and spades, from both our permanent deck and a spare, temporary deck
2) Select $w$ of the remaining cards from the spare deck
3) Remove $w$ cards from our permanent deck, none of which are identical to the selected cards
4) Add the selected cards to our permanent deck

We now have a $30$ card deck including $w$ doubles (i.e., when $w = 5$, the deck contains $20$ unique cards and $5$ pairs of cards). The other cards involved in the setup can be forgotten. Shuffle and randomly select $l$ cards from the deck. What is the probability that there is at least one pair among these $l$ cards?

---

This is a "general knowledge" version of the actual problem I'm trying to solve, which involves some Hearthstone trading card game terminology. As an optional problem description for those with such knowledge, what I'm really trying to figure out is how the probabilities of effects like Reno Jackson being active change based on how many cards are left in one's deck, and how many doubles the deck began with (for simplicity, assuming that only random means have been used throughout a game to remove cards from the deck).

I sequentially arrived at a number of formulas with excess confidence, only to realize that each later seemed incorrect. My current reasoning is that when $l = 2$, the probability is $\frac{w}{15 * 29}$, since the odds of the first card being one for which a duplicate exists are $\frac{w}{15}$, and then the odds conditional upon that of the second card being a match are $\frac{1}{29}$.

If this is right, then I would reason that the probability when $l = 3$ should be $\frac{3w}{15 * 29}$, since a unique card and a pair together have $3$ permutations without replacement, and the probability addition rule would prescribe summing these possibilities. I questioned whether combinations apply rather than permutations, since order of the cards in the deck doesn't matter, but reasoned that I'd already accounted for the fact that order doesn't matter by declaring one card the "first card" and the other the "second card" in my earlier formula. I'm not certain I got this right in either formula.

When we get to $l = 4$, I guess we have to start subtracting the possibility of finding multiple pairs when applying the addition rule, so the probability should be $\frac{(6 - 1)w}{15 * 29}$.

Am I on the right track? How would this formula be generalized for any $l$?

Answer 1

Each of the $30!/(30-l)!$ [ordered] hands are equally likely, so it suffices to count hands.

Suppose the names of the $w$ doubled cards are $1,2,\ldots, w$. You want to count the hands where your hand has at least one of these pairs, i.e. $$\left|\{\text{hand has pair of $1$s}\} \cup \{\text{hand has pair of $2$s}\} \cup \cdots \cup \{\text{hand has pair of $w$s}\}\right|.$$

Using inclusion-exclusion, this is $$\sum_{i=1}^w |\{\text{hand has pair of $i$s}\}| - \sum_{i < j} |\{\text{hand has pair of $i$s and pair of $j$s}\}| + \sum_{i < j < k} |\{\text{hand has pair of $i$s, pair of $j$s, pair of $k$s}\}| - \cdots$$

The number of hands with a pair of $1$s (and possibly other pairs) is $l(l-1) \cdot \frac{28!}{(28-(l-2))!}$ (number of ways to position the two $1$s in your hand, and $\frac{28!}{(28-(l-2))!}$ ways to choose $l-2$ other cards and position them). So the first sum is $$\sum_{i=1}^w |\{\text{hand has pair of $i$s}\}| = wl(l-1) \cdot \frac{28!}{(28-(l-2))!}.$$

The number of outcomes with a pair of $1$s and a pair of $2$s is $\frac{l!}{(l-4)!}\frac{26!}{(26-(l-4))!}$, so the second sum is $$\sum_{i < j} |\{\text{hand has pair of $i$s and pair of $j$s}\}| = \frac{w(w-1)}{2} \frac{l!}{(l-4)!}\frac{26!}{(26-(l-4))!}$$

If you see the pattern, the number of hands that have a particular set of $p$ pairs (and possibly others) is $$\binom{w}{p} \frac{l!}{(l-2p)!} \frac{(30-2p)!}{(30-l)!}$$ so the full inclusion-exclusion formula becomes

$$\sum_{p=1}^{\lfloor l/2\rfloor} (-1)^{p-1} \binom{w}{p} \frac{l!}{(l-2p)!} \frac{(30-2p)!}{(30-l)!} \frac{(30-l)!}{30!} = \sum_{p=1}^{\lfloor l/2\rfloor} (-1)^{p-1} \binom{w}{p} \frac{l!}{(l-2p)!} \frac{(30-2p)!}{30!}$$ where the division by $\frac{30!}{(30-l)!}$ is to divide by the total number of possible hands.

---

Concrete example: when $l=5$ and $w=2$, then the computation is $$\begin{align} P(\text{hand has at least one pair}) &= [P(\text{hand has pair of $1$s}) + P(\text{hand has pair of $2$s})] - P(\text{hand has both pairs}) \\ &= 2 \cdot \frac{5!}{3!} \cdot \frac{28!}{30!} - 1 \cdot \frac{5!}{1!} \frac{26!}{30!} \\ &= \frac{251}{5481}. \end{align}$$

---

Comments: I wrote this hastily so I welcome any corrections or error-catching. I am not sure if inclusion-exclusion is avoidable, and if there is a neater formula for the probability.