Number of ‘acceptable’ pairs in card drawing game

Question

A deck contains six cards, one pair labelled '1', another pair labelled '2' and the last labelled '3'. The deck is shuffled and you a pair of cards at a time until there are no cards left. A pair of cards $(i,j)$ is called acceptable if $|i-j|\leq1$. What is the probability you have drawn only acceptable pairs? How does your answer change if there are $n$ pairs and the condition becomes $|i-j|\leq k$?

I'm quite stuck on the last bit of the problem. Here's my approach to the first part:

My solution so far:  My idea is that as long as a pair $(1,3)$ or $(3,1)$ is drawn, then set contains an unacceptable pair. The probability $(1,3)$ or $(3,1)$ is drawn first is $$2\left(\frac26\times\frac25\right)=\frac4{15},$$

the probability $(1,3)$ or $(3,1)$ is drawn second is $$\left(1-\frac4{15}\right)\frac4{15}=\frac{44}{225},$$

and the probability $(1,3)$ or $(3,1)$ is drawn last is $$\left(1-\frac4{15}-\frac{44}{225}\right)\frac4{15}=\frac{484}{3375},$$

so the probability of having only acceptable pairs is $$1-\frac4{15}-\frac{44}{225}-\frac{484}{3375}=1-\frac{900}{3375}-\frac{660}{3375}-\frac{484}{3375}=\frac{1331}{3375}.$$

(Correct me if this is wrong please!)

However, I am unsure of how to extend this to a more general number of cards and relaxed constraint. Taking the complement seems to be less efficient compared to finding the actual probability, but I'm not sure if there's a closed form. Qualitatively, all I can see is the probability dropping to zero as the number of cards increases. Could someone provide better insight? Cheers!

Answer 1

Not a complete answer, but it might help.

---

Let $[n]=\{1,2,\ldots,n\}$ . The deck of cards is represented by the multiset $D_n=[n]\cup[n]$. For each $m$, let $S_m^n$ be a partitioning of $D_n$ into subsets of $2$, and $S^n=\bigcup_m S_m^n$ (note that the order in which the pairs are drawn doesn't actually matter, so it isn't necessary to count the permutations).

Call the $m^\text{th}$ partitioning $k$-acceptable iff, for all $\{i,j\}\in S_m^n$, $|i-j|\le k$, and $k$-unacceptable otherwise. The task is now to find the total number of partitionings (the largest $m$) for each $n$, and the subset of $k$-acceptable partitionings.

The first part is relatively easy. I'm not great with combinatorics, so I just used the formula from this question, played with Mathematica, and searched the OEIS until I got this:

$$|S^n|=(2n-1)!!$$

For the second part, let $A_k^n$ be the set of $k$-acceptable partitionings of $D_n$. Then, the probability that a particular partitioning is $k$-acceptable is:

$$P(k,n)=\frac{|A_k^n|}{|S^n|}=\frac{|A_k^n|}{(2n-1)!!}$$

All that's left is to determine the size of $A_k^n$.

Note:

Assuming that I haven't made any mistakes, if Christopher Well's answer is correct and $P(1,3)=\frac{1}{3}$, then $|A_1^3|=5$.

Answer 2

I'm afraid your answer to the first half of the question is incorrect.

For one thing, there are 720 ways to shuffle a six-card deck, so whatever the probability is it must be a fraction with 720 on the denominator. Or at least a factor of 720.

You're correct that $2 \times \frac{2}{6} \times \frac{2}{5}$ is the probability that the first pair is unacceptable. But it's not the probability that the second pair is given that the first was acceptable. That would be something different, as there are only 4 cards left in the deck and they're not an equal distribution of all three numbers.

---

The 3s can only be acceptably paired with the other 3 or with a 2. In particular, if one 3 is paired with a 2, the other 3 must be paired with the other 2.

The probability that the 3s are paired with each other is $\frac{1}{5}$. This leaves the 1s and 2s to be paired - any arrangement of these is acceptable.

If they are not paired with each other, they must both be paired with the 2s. The probability of this is $\frac{2}{15}$. This leaves the 1s to be paired with each other, which is acceptable.

In total, the probability that all pairs are acceptable is: $$\frac{1}{3}$$

---

You can extend this approach to more cards. Let $n > 3$. In a deck with $n$ pairs numbered $1$ to $n$, the $n$s can only be acceptably paired with each other or with the $n-1$s.

If they are paired with each other, the rest of the cards must be an acceptable arrangement of a deck with pairs numbered $1$ to $n-1$.

If they are paired with the $n-1$s, the rest of the cards must be an acceptable arrangement of a deck with pairs numbered $1$ to $n-2$.

By finding the probability of the $n$s being paired with each other. and the probability of them being paired with the $n-1$s, you can get a recursive formula for the probability that all pairs are acceptable.

---

I don't know if this solution extends to weaker constraints, too.