The Matching Problem

The matching experiment is a random experiment that can the formulated in a number of colorful ways. Let $n \in N_{+}$ .

Suppose that $n$ male-female couples are at a party and that the males and females are randomly paired for a dance. A match occurs if a couple happens to be paired together.
An absent-minded secretary prepares $n$ letters and envelopes to send to $n$ different people, but then randomly stuffs the letters into the envelopes. A match occurs if a letter is inserted in the proper envelope.
$n$ people with hats have had a bit too much to drink at a party. As they leave the party, each person randomly grabs a hat. A match occurs if a person gets his or her own hat.

The experiments in [1] are equivalent from a mathematical point of view, and correspond to selecting a random permutation $X = (X_{1}, X_{2}, \dots, X_{n})$ of the population $D_{n} = {1, 2, \dots, n}$ .

Number the couples from 1 to $n$ . Then $X_{i}$ is the number of the woman paired with the $i$ th man.
Number the letters and corresponding envelopes from 1 to $n$ . Then $X_{i}$ is the number of the envelope containing the $i$ th letter.
Number the people and their corresponding hats from 1 to $n$ . Then $X_{i}$ is the number of the hat chosen by the $i$ th person.

Our modeling assumption, of course, is that

X

is uniformly distributed on the set of permutations of

D_{n}

. The number of objects

n

is the basic parameter of the experiment. We will also consider the case of sampling with replacement from the population

D_{n}

, because the analysis is much easier but still provides insight. In this case,

X

is a sequence of independent random variables, each uniformly distributed over

D_{n}

Matches

A match occurs at position $j \in {1, 2, \dots, n}$ if $X_{j} = j$ . So the number of matches is the random variable $N$ defined mathematically by $N_{n} = \sum_{j = 1}^{n} I_{j}$ where $I_{j} = 1 (X_{j} = j)$ is the indicator variable for the event of match at position $j$ .

Our problem is to compute the probability distribution of the number of matches. This is an old and famous problem in probability that was first considered by Pierre-Remond Montmort; it sometimes referred to as Montmort's matching problem in his honor.

Sampling With Replacement

First let's solve the matching problem in the easy case, when the sampling is with replacement. Of course, this is not the way that the matching game is usually played, but the analysis will give us some insight.

$(I_{1}, I_{2}, \dots, I_{n})$ is a sequence of $n$ Bernoulli Trials, with success probability $\frac{1}{n}$ .

Details:

The variables are independent since the sampling is with replacement. Since $X_{j}$ is uniformly distributed, $P (I_{j} = 1) = P (X_{j} = j) = \frac{1}{n}$ .

The number of matches $N_{n}$ has the binomial distribution with trial parameter $n$ and success parameter $\frac{1}{n}$ . $P (N_{n} = k) = (\binom{n}{k}) {(\frac{1}{n})}^{k} {(1 - \frac{1}{n})}^{n - k}, k \in {0, 1, \dots, n}$

Details:

This follows immediately from [4].

The mean and variance of the number of matches are

$E (N_{n}) = 1$
$var (N_{n}) = \frac{n - 1}{n}$

Details:

These results follow from [5]. Recall that the binomial distribution with parameters $n \in N_{+}$ and $p \in [0, 1]$ has mean $n p$ and variance $n p (1 - p)$ .

The distribution of the number of matches converges to the Poisson distribution with parameter 1 as $n \to \infty$ : $P (N_{n} = k) \to \frac{e^{- 1}}{k!} as n \to \infty for k \in N$

Details:

This is a special case of the convergence of the binomial distribution to the Poisson. For a direct proof, note that $P (N_{n} = k) = \frac{1}{k!} \frac{n^{(k)}}{n^{k}} {(1 - \frac{1}{n})}^{n - k}$ But $\frac{n^{(k)}}{n^{k}} \to 1$ as $n \to \infty$ and ${(1 - \frac{1}{n})}^{n - k} \to e^{- 1}$ as $n \to \infty$ by a famous limit from calculus.

Sampling Without Replacement

Now let's consider the case of real interest, when the sampling is without replacement, so that

X

is a random permutation of the elements of

D_{n} = {1, 2, \dots, n}

Counting Permutations with Matches

To find the probability density function of

N_{n}

, we need to count the number of permutations of

D_{n}

with a specified number of matches. This will turn out to be easy once we have counted the number of permutations with no matches; these are called derangements of

D_{n}

. We will denote the number of permutations of

D_{n}

with exactly

k

matches by

b_{n} (k) = # {N_{n} = k}

for

k \in {0, 1, \dots, n}

. In particular,

b_{n} (0)

is the number of derrangements of

D_{n}

The number of derrangements is $b_{n} (0) = n! \sum_{j = 0}^{n} \frac{(- 1)^{j}}{j!}$

Details:

By the complement rule for counting measure $b_{n} (0) = n! - # (⋃_{i = 1}^{n} {X_{i} = i})$ . From the inclusion-exclusion formula, $b_{n} (0) = n! - \sum_{j = 1}^{n} (- 1)^{j - 1} \sum_{J \subseteq D_{n}, # (J) = j} # {X_{i} = i for all i \in J}$ But if $J \subseteq D_{n}$ with $# (J) = j$ then $# {X_{i} = i for all i \in J} = (n - j)!$ . Finally, the number of subsets $J$ of $D_{n}$ with $# (J) = j$ is $(\binom{n}{j})$ . Substituting into the displayed equation and simplifying gives the result.

The number of permutations with exactly $k$ matches is $b_{n} (k) = \frac{n!}{k!} \sum_{j = 0}^{n - k} \frac{(- 1)^{j}}{j!}, k \in {0, 1, \dots, n}$

Details:

The following is two-step procedure that generates all permutations with exactly $k$ matches: First select the $k$ integers that will match. The number of ways of performing this step is $(\binom{n}{k})$ . Second, select a permutation of the remaining $n - k$ integers with no matches. The number of ways of performing this step is $b_{n - k} (0)$ . By the multiplication principle of combinatorics it follows that $b_{n} (k) = (\binom{n}{k}) b_{n - k} (0)$ . Using [8] and simplifying gives the results.

The Probability Density Function

The probability density function of the number of matches is $P (N_{n} = k) = \frac{1}{k!} \sum_{j = 0}^{n - k} \frac{(- 1)^{j}}{j!}, k \in {0, 1, \dots, n}$

Details:

This follows directly from [9], since $P (N_{n} = k) = # {N_{n} = k} / n!$ .

In the matching experiment, vary the parameter $n$ and note the shape and location of the probability density function. For selected values of $n$ , run the simulation 1000 times and compare the empirical density function to the true probability density function.

$P (N_{n} = n - 1) = 0$ .

Details:

A simple probabilistic proof is to note that the event is impossible—if there are $n - 1$ matches, then there must be $n$ matches. An algebraic proof can also be constructed from the probability density function in exericse [10].

The distribution of the number of matches converges to the Poisson distribution with parameter 1 as $n \to \infty$ : $P (N_{n} = k) \to \frac{e^{- 1}}{k!} as n \to \infty, k \in N$

Details:

From the power series for the exponential function, $\sum_{j = 0}^{n - k} \frac{(- 1)^{j}}{j!} \to \sum_{j = 0}^{\infty} \frac{(- 1)^{j}}{j!} = e^{- 1} as n \to \infty$ So the result follows from the probability density function in [10].

In the matching experiment, increase $n$ and note how the probability density function stabilizes rapidly. For selected values of $n$ , run the simulation 1000 times and compare the relative frequency function to the probability density function.

Moments

The mean and variance of the number of matches could be computed directly from the distribution. However, it is much better to use the representation in terms of indicator variables. The exchangeable property is an important tool in this section.

$E (I_{j}) = \frac{1}{n}$ for $j \in {1, 2, \dots, n}$ .

Details:

$X_{j}$ is uniformly distributed on $D_{n}$ for each $j$ so $P (I_{j} = 1) = P (X_{j} = x) = \frac{1}{n}$ .

$E (N_{n}) = 1$ for each $n$

Details:

This follows from [15] and the additive property of expected value.

So the expected number of matches is 1, regardless of

n

, just as in when the sampling is with replacement .

$var (I_{j}) = \frac{n - 1}{n^{2}}$ for $j \in {1, 2, \dots, n}$ .

Details:

This follows from $P (I_{j} = 1) = \frac{1}{n}$ .

A match in one position would seem to make it more likely that there would be a match in another position. Thus, we might guess that the indicator variables are positively correlated.

For distinct $j, k \in {1, 2, \dots, n}$ ,

$cov (I_{j}, I_{k}) = \frac{1}{n^{2} (n - 1)}$
$cor (I_{j}, I_{k}) = \frac{1}{(n - 1)^{2}}$

Details:

Note that $I_{j} I_{k}$ is the indicator variable of the event of a match in position $j$ and a match in position $k$ . Hence by the exchangeable property $P (I_{j} I_{k} = 1) = P (I_{j} = 1) P (I_{k} = 1 ∣ I_{j} = 1) = \frac{1}{n} \frac{1}{n - 1}$ . As before, $P (I_{j} = 1) = P (I_{k} = 1) = \frac{1}{n}$ . The results now follow from standard computational formulas for covariance and correlation.

Note that when

n = 2

, the event that there is a match in position 1 is perfectly correlated with the event that there is a match in position 2. This makes sense, since there will either be 0 matches or 2 matches.

$var (N_{n}) = 1$ for every $n \in {2, 3, \dots}$ .

Details:

This follows from [17] and [18], and basic properties of covariance. Recall that $var (N_{n}) = \sum_{j = 1}^{n} \sum_{k = 1}^{n} cov (I_{j}, I_{k})$ .

In the matching experiment, vary the parameter $n$ and note the shape and location of the mean $\pm$ standard deviation bar. For selected values of the parameter, run the simulation 1000 times and compare the sample mean and standard deviation to the distribution mean and standard deviation.

For distinct $j, k \in {1, 2, \dots, n}$ , $cov (I_{j}, I_{k}) \to 0$ as $n \to \infty$ .

So the event that a match occurs in position

j

is nearly independent of the event that a match occurs in position

k

n

is large. For large

n

, the indicator variables behave nearly like

n

Bernoulli trials with success probability

\frac{1}{n}

, which of course, is what happens when the sampling is with replacement.

A Recursion Relation

In this subsection, we will give an alternate derivation of the distribution of the number of matches, in a sense by embedding the experiment with parameter

n

into the experiment with parameter

n + 1

The probability density function of the number of matches satisfies the following recursion relation and initial condition:

$P (N_{n} = k) = (k + 1) P (N_{n + 1} = k + 1)$ for $k \in {0, 1, \dots, n}$ .
$P (N_{1} = 1) = 1$ .

Details:

First, consider the random permutation $(X_{1}, X_{2}, \dots, X_{n}, X_{n + 1})$ of $D_{n + 1}$ . Note that $(X_{1}, X_{2}, \dots, X_{n})$ is a random permutation of $D_{n}$ if and only if $X_{n + 1} = n + 1$ if and only if $I_{n + 1} = 1$ . It follows that $P (N_{n} = k) = P (N_{n + 1} = k + 1 ∣ I_{n + 1} = 1), k \in {0, 1, \dots, n}$ From the defnition of conditional probability argument we have $P (N_{n} = k) = P (N_{n + 1} = k + 1) \frac{P (I_{n + 1} = 1 ∣ N_{n + 1} = k + 1)}{P (I_{n + 1} = 1)}, k \in {0, 1, \dots, n}$ But $P (I_{n + 1} = 1) = \frac{1}{n + 1}$ and $P (I_{n + 1} = 1 ∣ N_{n + 1} = k + 1) = \frac{k + 1}{n + 1}$ . Substituting into the last displayed equation gives the recurrence relation. The initial condition is obvious, since if $n = 1$ we must have one match.

This result can be used to obtain the probability density function of

N_{n}

recursively for any

n

The Probability Generating Function

Next recall that the probability generating function of

N_{n}

is given by

G_{n} (t) = E (t^{N_{n}}) = \sum_{j = 0}^{n} P (N_{n} = j) t^{j}, t \in R

The family of probability generating functions satisfies the following differential equations and ancillary conditions:

$G_{n + 1}^{'} (t) = G_{n} (t)$ for $t \in R$ and $n \in N_{+}$
$G_{n} (1) = 1$ for $n \in N_{+}$

Note also that

G_{1} (t) = t

for

t \in R

. Thus, the system of differential equations can be used to compute

G_{n}

for any

n \in N_{+}

In particular, for $t \in R$ ,

$G_{2} (t) = \frac{1}{2} + \frac{1}{2} t^{2}$
$G_{3} (t) = \frac{1}{3} + \frac{1}{2} t + \frac{1}{6} t^{3}$
$G_{4} (t) = \frac{3}{8} + \frac{1}{3} t + \frac{1}{4} t^{2} + \frac{1}{24} t^{4}$

For $k, n \in N_{+}$ with $k < n$ , $G_{n}^{(k)} (t) = G_{n - k} (t), t \in R$

Details:

This follows from differential equation in [23].

For $n \in N_{+}$ , $P (N_{n} = k) = \frac{1}{k!} P (N_{n - k} = 0), k \in {0, 1, \dots, n - 1}$

Details:

This follows from [25] and basic properties of generating functions.

Examples and Applications

A secretary randomly stuffs 5 letters into 5 envelopes. Find each of the following:

The number of outcomes with exactly $k$ matches, for each $k \in {0, 1, 2, 3, 4, 5}$ .
The probability density function of the number of matches.
The covariance and correlation of a match in one envelope and a match in another envelope.

Details:

$k$ 0 1 2 3 4 5

$b_{5} (k)$ 44 45 20 10 0 1
$k$ 0 1 2 3 4 5

$P (N_{5} = k)$ 0.3667 0.3750 0.1667 0.0833 0 0.0083
Covariance: $\frac{1}{100}$ , correlation $\frac{1}{16}$

$k$	0	1	2	3	4	5
$b_{5} (k)$	44	45	20	10	0	1

$k$	0	1	2	3	4	5
$P (N_{5} = k)$	0.3667	0.3750	0.1667	0.0833	0	0.0083

Ten married couples are randomly paired for a dance. Find each of the following:

The probability density function of the number of matches.
The mean and variance of the number of matches.
The probability of at least 3 matches.

Details:

$k$	$P (N_{10} = k)$
0	$\frac{16 481}{44 800} \approx 0.3678795$
1	$\frac{16 687}{45 360} \approx 0.3678792$
2	$\frac{2119}{11 520} \approx 0.1839410$
3	$\frac{103}{1680} \approx 0.06130952$
4	$\frac{53}{3456} \approx 0.01533565$
5	$\frac{11}{3600} \approx 0.003055556$
6	$\frac{1}{1920} \approx 0.0005208333$
7	$\frac{1}{15 120} \approx 0.00006613757$
8	$\frac{1}{80 640} \approx 0.00001240079$
9	0
10	$\frac{1}{3 628 800} \approx 2.755732 \times 10^{- 7}$

$E (N_{10}) = 1$ , $var (N_{10}) = 1$
$P (N_{10} \geq 3) = \frac{145 697}{1 814 400} \approx 0.08030037$

In the matching experiment, set $n = 10$ . Run the experiment 1000 times and compare the following for the number of matches:

The true probabilities
The relative frequencies from the simulation
The limiting Poisson probabilities

Details:

See part (a) of [28].

$k$	$e^{- 1} \frac{1}{k!}$
0	0.3678794
1	0.3678794
2	0.1839397
3	0.06131324
4	0.01532831
5	0.003065662
6	0.0005109437
7	0.00007299195
8	$9.123994 \times 10^{- 6}$
9	$1.013777 \times 10^{- 6}$
10	$1.013777 \times 10^{- 7}$

5. The Matching Problem

Definitions and Notation

The Matching Experiment

Matches

Sampling With Replacement

Sampling Without Replacement

Counting Permutations with Matches

The Probability Density Function

Moments

A Recursion Relation

The Probability Generating Function

Examples and Applications