Probability of paired combinations

There are 8 friends: Alfred, Alex, Billy, Barbara, Connie, Chris, David and Donna.

The friends are paired up at random. What is the probability that at least two pairs will share the same first initial?

I believe the probability of having all four pairs share the same first initial is:

$(4/28)*(3/15)*(2/6)$ = .0095

where the numerator is the number of remaining possible pairs who share a first initial, and the denominator is the number of possible pairs left (8/6/4 choose 2).

How can you determine the probability of at least 2 pairs having the same initial?

• By permutation test, it appears the answer is p=.1239, but I would still like to know how this is solved analytically
– Jeff
Commented Jan 24, 2015 at 20:50

Here's a less advanced approach than whuber's:

The total number of possible "pairings" (ways to divide the 8 friends into four pairs) is $$\frac{\binom{8}{2} \binom{6}{2} \binom{4}{2}}{4!} = 105.$$ This is because there are $\binom{8}{2}$ ways to choose the first pair, then $\binom{6}{2}$ ways to choose the second pair, then $\binom{4}{2}$ ways to choose the third pair, but because we don't distinguish between the "first pair", "second pair", "third pair" and "fourth pair", we divide by the $4!$ ways of labelling the four pairs as "first", "second", "third" and "fourth".

The number of "pairings" with the same initials in all 4 pairs is clearly 1.

There are no "pairings" with the same initials in exactly 3 pairs, because the last pair would then also have the same initials.

The number of "pairings" with the same initials in exactly 2 pairs is $$\binom{4}{2} \times 2 = 12,$$ because there are $\binom{4}{2}$ ways of choosing the "matched" initials from $\{A,B,C,D\}$, and then 2 possibilities for the unmatched pairs.

The probability that at least two pairs have the same initial is the number of "pairings" in which at least two pairs have the same initial divided by the total number of possible "pairings", which, from the above, is $$\frac{1 + 12}{105} = \frac{13}{105} \approx 0.124.$$

Formulation

Because the same question has been asked and answered with "at least 2" replaced by "none," let's obtain the full distribution. In other words, suppose there are $n$ pairs of objects and all $2n$ of those objects are randomly permuted, creating $n$ pairings. For any integer $k$, what is the chance exactly $k$ of those new pairings will bring back together some original pair?

One way to tackle this is to think of the random permutation as arising by putting all $2n$ objects in a jar, mixing them up, and drawing them out randomly in groups of two (without replacement). How many of these draws consist of the original pairs? Let that count be the random variable $X$. We seek its probability distribution.

Naturally we would like to consider what happens when we draw out the first group. Immediately we're confronted with yet a larger generalization of the original problem: unless that first group is a pair, there will be some objects left in the jar that have no pairs at all. A little thought indicates that the number of such unpaired objects will always be even, so let it be $2m$.

Here, then, is the formal question to be addressed:

What is the probability distribution of the number of pairs obtained when drawing objects without replacement in groups of two from a jar that contains $2n$ objects (forming $n$ pairs) and $2m$ unpaired objects?

Let's remark that for large $n$, the Poisson$(n/(2n-1))$ distribution will give an excellent approximation. The Poisson$(1/2)$ will be almost as good. That is because there are only $n$ pairs out of $\binom{2n}{2} = n(2n-1)$ possible groups of two objects, whence there is only a $n/(n(2n-1))=1/(2n-1)$ chance, which is rare for large $n$. This means the total number of pairs can be approximated by a Binomial$(n, 1/(2n-1))$ distribution, which in turn is extremely close to a Poisson$(n/(2n-1))$ distribution. This heuristic result is interesting because it shows that as the number of pairs in the jar grows, the chances associated with $X=k$ eventually don't change much. In particular, since there is only a one chance in a million that a Poisson$(1/2)$ variable will exceed $6$, it is highly likely $X \le 6$ no matter what $n$ might be!

Solution

Because this threatens to get complicated--so far there are variables $k, m, n$ to keep track of--let's deal with the entire probability distribution by means of its probability generating function (pgf), $p(m,n)$. By definition this is a polynomial whose coefficients are the desired probabilities:

$$p(m,n)(t) = \Pr(X=0) + \Pr(X=1)t + \Pr(X=2)t^2 + \cdots + \Pr(X=n)t^n.$$

Here, $t$ is the polynomial variable and I was able to stop the sum at $n$ since obviously no more than $n$ pairs can be drawn.

The question itself can be answered by computing $p(0,n)(t)$, with $n=4$, ignoring the coefficients of $1$ and $t$, and setting $t=1$ to obtain the sum $\Pr(X=2) + \Pr(X=3) + \cdots + \Pr(X=n)$.

If $n=0$, there are no pairs in the jar, making the answer clear: $p(m,0)(t) = 1$ for all $m \ge 0$, indicating there is $100\%$ chance that $X=0$.

So, suppose $n \ge 1$. This implies there are at least two objects in the jar. Draw two out at random. The following things can happen:

1. You draw a pair. Since there are $\binom{2(m+n)}{2}$ groups of two objects in the jar, $n$ of them are pairs, and every group has the same chance of being drawn, the chance of this event is $n/\binom{2(m+n)}{2}$. The jar now has $n-1$ paired objects and it still has $2m$ unpaired ones.

2. You draw two of the unpaired objects. (This can happen only when $m\ge 1$.) The chance of this event is $\binom{2m}{2}/\binom{2(n+m)}{2}$. Since the number of unpaired objects has been reduced by two, the jar still contains $n$ paired objects and $2(m-1)$ unpaired ones.

3. You draw two of the paired objects, but they do not form a pair. (This can happen only when $n \ge 2$.) There are $\binom{2n}{2}$ groups of two such objects, but we already counted $n$ of them in (1): they are the actual pairs. Therefore the chance of this event is $\left(\binom{2n}{2} - n\right)/\binom{2(m+n)}{2}$. The number of pairs remaining is only $n-2$, but there are now $2(m+1)$ unpaired objects.

4. You draw one paired object and one unpaired object. There are $(2n)(2m)$ ways to do this, so the chance is $(2n)(2m)/\binom{2(n+m)}{2}$. There is one less paired object left, so $n$ is reduced to $n-1$. You created a new unpaired object when you drew its mate, but you removed on unpaired object, too, so $m$ remains the same.

In case (1) you increased $X$ by $1$: that multiplies the pgf of the jar by $t$. In the remaining cases $X$ remained the same. Consequently, by the law of total probability, we may add the four pgfs, each weighted by the corresponding chance. To clarify the expression I have multiplied both sides by the common denominator, $\binom{2(m+n)}{2}$, which clears out all fractions:

\eqalign{ \binom{2(n+m)}{2}p(m,n)(t) &= &n\, t\, p(m,n-1)(t) \\ & &+ \binom{2m}{2}p(m-1,n)(t) \\ & &+ \left(\binom{2n}{2}-n\right) p(m+1,n-2)(t) \\ & &+ (2n)(2m) p(m, n-1)(t). }

This recursion can easily be solved with a dynamic program: start with the case $n=0$, use it to solve for the case $n=1$ by sweeping from $m=0$ upwards, and repeat until you reach the desired value of $n$. (A Mathematica implementation appears at the end of this post as a working illustration.) Although storage requirements can be reduced to $O(n^2)$, the computation time is proportional to $O(n^3)$, so it's not terribly efficient--but it will work just fine for values of $n$ into the hundreds.

Here are the first few pgfs:

\eqalign{ p(0,1)(t) &= \frac{1}{1}\left(t\right) \\ p(0,2)(t) &= \frac{1}{1\cdot 3}\left(2 + t^2\right) \\ p(0,3)(t) &= \frac{1}{1\cdot 3\cdot 5}\left(8 + 6 t + t^3\right)\\ p(0,4)(t) &= \frac{1}{1\cdot 3\cdot 5\cdot 7}\left(60 + 32 t + 12 t^2 + t^4\right) \\ \cdots}

In particular, the chance of two or more pairs when $n=4$ can be read directly from the terms in the last polynomial having powers of two or greater:

$$\frac{1}{1\cdot 3\cdot 5\cdot 7}\left(12 t^2 + t^4\right)\bigg|_{t=1} = \frac{13}{105} \approx 0.12381.$$

As a check, the Poisson$(4/7)$ approximation gives $0.113$, which--even though $n$ cannot be considered large--is quite close.

f implements the pgf and ff computes the distribution function.

Clear[f, ff];
f[_, 0] := 1;
f[m_, _] /; m < 0 := 0;
f[_, n_] /; n < 0 := 1;
f[m_, n_] := f[m, n] = Expand[((\[FormalX] n + (2 n) (2 m) ) f[m, n - 1] +
(Binomial[2 n, 2] - n) f[m + 1, n - 2] +
Binomial[2 m, 2] f[m - 1, n])/Binomial[2 m + 2 n, 2]];
f[n_] := f[0, n] ; (* PGF *)

ff[k_, n_] /; 0 <= k < n := With[{s = CoefficientList[f[n], \[FormalX]]},
Total[Take[s, Floor[k] + 1]] / Total[s]] (* CDF *)
ff[k_, _] /; k < 0 := 0;
ff[k_, n_] /; k >= n := 1;
ff[k_, n_] /; n < 0 := HeavisideTheta[k];


This takes about one second to compute all the pgfs up through $n=100$.

As an example of its use, here is a display of some of the pgfs:

Clear[t];
With[{n = 6},
TableForm[Array[f, n] /. \[FormalX] -> t,
TableHeadings -> {Array["n=" <> ToString[#] &, n], {}}]
]


$$\begin{array}{cc} \text{n=1} & t \\ \text{n=2} & \frac{t^2}{3}+\frac{2}{3} \\ \text{n=3} & \frac{t^3}{15}+\frac{2 t}{5}+\frac{8}{15} \\ \text{n=4} & \frac{t^4}{105}+\frac{4 t^2}{35}+\frac{32 t}{105}+\frac{4}{7} \\ \text{n=5} & \frac{t^5}{945}+\frac{4 t^3}{189}+\frac{16 t^2}{189}+\frac{20 t}{63}+\frac{544}{945} \\ \text{n=6} & \frac{t^6}{10395}+\frac{2 t^4}{693}+\frac{32 t^3}{2079}+\frac{20 t^2}{231}+\frac{1088 t}{3465}+\frac{1208}{2079} \\ \end{array}$$