Looking for a Match

I recently gave an exam in my statistics course, which turned out to be an excellent example for the matching problem, a classic problem in probability. There were 66 students taking the test. I wrote down the names of the students in the order of turning in the exam. The following table shows the positions of the students in alphabetical order and in the order they turned in the exam.

For example, the first student in the alphabetical order was the 12th student who turned in the exam. The first student who turned in the exam was the 37th student in the alphabetical order. It turned out that there was a student who had the same position in both orders. Such a student is called a match (see the following table).

This example captures the essence of a classic problem in probability called the matching problem. There are many other colorful descriptions of the matching problem. All of them involve the pairing of two orderings on a set of objects. We have a set of objects or items that are ordered in some natural way. Then we scramble the items randomly (or according to some ordering that is unpredictable in advance). Whenever an item has the same position in both the original order and in the scrambled order, it is called a match.

In our exam example, one version of the matching problem asks: what is the probability that there is at least one student that is a match?

In fact, in matching two orderings, such as the one described here, a match happens more often than not. The probability of having at least one match is roughly 0.63. Specifically, when n is the number of students taking the exam, the probability of finding at least one match approaches 1-e^{-1}=0.632121 as n \rightarrow \infty. The derivation of this probability is based on the inclusion-exclusion principle and is discussed in the blog post called The Matching Problem.

Even though the probability of having at least one match is a function of n (the number of items), the probability converges to 1-e^{-1} pretty rapidly. Thus for all practical purposes, we can say that the probability of having at least one match is 0.63 (roughly two-third), whenever the number of items involved in the random scrambling is reasonably large (as in the 66 students taking the exam).

Instead of finding the probability of having at least one match, we can also ask for the probability of having exactly k matches, where k is any integer from 0 to n. Let X_n be the number of matches when we match the “exam turning in” order with the alphabetical order for n students. The probability function P(X_n=k) is derived in the blog post called More About the Matching Problem.

The blog post More About the Matching Problem also points out that P(X_n=k) is approximated by the Poisson distribution with parameter \alpha=1. Thus we have:

\displaystyle (1) \ \ \ \ \ P(X_n=k) \approx \frac{e^{-1}}{k!} \ \ \ \ \ \ \ \ \ \ k=0,1,2,\cdots,n

The following are the first 4 probabilities of P(X_n=k).

\displaystyle (2) \ \ \ \ \ P(X_n=0) \approx \frac{e^{-1}}{0!}=0.3679

\displaystyle (3) \ \ \ \ \ P(X_n=1) \approx \frac{e^{-1}}{1!}=0.3679

\displaystyle (4) \ \ \ \ \ P(X_n=2) \approx \frac{e^{-1}}{2!}=0.1839

\displaystyle (5) \ \ \ \ \ P(X_n=3) \approx \frac{e^{-1}}{3!}=0.0313

In the random experiment of matching two orderings on the same set of objects, about 37% of the time, there is no match and about 37% of the time there is exactly one match. Having no matches and having exactly one match are the mostly scenarios (occurring about 74% of the time). Having 2 matches is possible, but only happens about 18% of the time. It is rare to have 3 ore more matches.

Another interesting observation is that if a match occurs, it is mostly likely that there is only one match (such as the example discussed here).

There are many colorful descriptions of the matching problem. The possibilities are limitless. One example is that of n married couples going to a ball room dancing class. The instructor randomly assign the ladies to the gentlemen as dancing partners. A match occurs if a wife is assigned as
the dancing partner of her husband.

A previous blog post (Tis the Season for Gift Exchange) presents an example involving gift exchange. Each person attending a party brings a gift for gift exchange. The gifts are put in a pile and each person randomly selects a gift from the pile. A match occurs if a person selects his or her own gift.

In another blog post (A lazy professor who lets students do their own grading), a professor randomly returns quizzes to the students for grading. A match occurs if a students is assigned his or her own quiz.

A lazy professor who lets students do their own grading

After reading the example discussed here, any professor or instructor who is contemplating randomly distributing quizzes back to the students for grading perhaps should reconsider the idea! This is one of several posts discussing the matching problem. Go to the end of this post to find links to these previous posts.

Consider the following problem. Suppose that a certain professor is lazy and lets his students grade their own quizzes. After he collects the quizzess from his n students, he randomly assigns the quizzes back to these n students for grading. If a student is assigned his or her own quiz, we say that it is a match. We have the following questions:

  • What is the probability that each of the n students is a match?
  • What is the probability that none of the n students is a match?
  • What is the probability that exactly k of the n students are matches?
  • What is the probability that at least one of the n students is a match?

The above problem is called the matching problem, which is a classic problem in probability. In this post we solve the last question indicated above. Though the answer is in terms of the total number of quizzes n, it turns out that the answer is independent of n and is approximately \frac{2}{3}. Thus if the professor assigns the quizzes randomly, it will be very unusual that there is no match.

The last question above is usually stated in other matching situations. One is that there are n couples (say, each couple consists of a husband and a wife) in a class for ballroom dancing. Suppose that the dance instructor randomly matches the men to the ladies. When a husband is assigned his own wife, we say that it is a match. What is the probability that there is at least one couple that is a match?

The key to answering this question is the theorem stated in Feller (page 99 in chapter 4 of [1]). We state the theorem and make use of it in the solution of the last question above. A sketch of the proof will be given at the end. For ideas on the solutions to the first three questions above, see this previous post.

The union of n events
For any n events E_1,E_2, \cdots,E_n that are defined on the same sample space, we have the following formula:

(1) \ \ \ \ \ P[E_1 \cup E_2 \cup \cdots \cup E_n]=\sum \limits_{m=1}^{n} (-1)^{m+1} \thinspace S_m where

S_1=\sum \limits_{r=1}^{n}P[E_r],

S_2=\sum \limits_{j<k}P[E_j \cap E_k],

S_m=\sum P[E_{i(1)} \cap E_{i(2)} \cap \cdots \cap E_{i(m)}]

Note that in the general term S_m, the sum is taken over all increasing sequence i(\cdot), i.e. 1 \le i(1) < i(2) < \cdots < i(m) \le n. For n=2,3, we have the following familiar formulas:

\displaystyle P[E_1 \cup E_2]=P[E_1]+P[E_2]-P[E_1 \cap E_2]

\displaystyle \begin{aligned}P[E_1 \cup E_2 \cup E_3]=& \ \ \ \ P[E_1]+P[E_2]+P[E_3]\\&-P[E_1 \cap E_2]-P[E_1 \cap E_3]-P[E_2 \cap E_3]\\&+P[E_1 \cap E_2 \cap E_3] \end{aligned}

The Matching Problem

Suppose that the n students are labeled 1,2, \cdots, n. Let E_i be the even that the i^{th} student is assigned his or her own quiz by the professor. Then P[E_1 \cup E_2 \cup \cdots \cup E_n] is the probability that there is at least one correct match.

Note that P[E_i]=\frac{(n-1)!}{n!}=\frac{1}{n}. This is the case since we let the i^{th} student be fixed and we permute the other n-1 students. Likewise, P[E_i \cap E_j]=\frac{(n-2)!}{n!}, since we fix the i^{th} and j^{th} students and let the other (n-2)! students permute. In general, whenever i(1),i(2),\cdots,i(m) are m distinct integers and are increasing, we have:

\displaystyle P[E_{i(1)} \cap E_{i(2)} \cdots \cap E_{i(m)}]=\frac{(n-m)!}{n!}

We now apply the formula (1). First we show that for each m where 1 \le m \le n, S_m=\frac{1}{m!}. Since there are \binom{n}{m} many ways to have m matches out of n students, we have:

\displaystyle \begin{aligned}S_m&=\sum P[E_{i(1)} \cap E_{i(2)} \cdots \cap E_{i(m)}]\\&=\binom{n}{m} \frac{(n-m)!}{n!}\\&=\frac{1}{m!} \end{aligned}

Applying the formula for the union of n events, we have:

\displaystyle P[E_1 \cup E_2 \cup \cdots \cup E_n]=1-\frac{1}{2!}+\frac{1}{3!}-\cdots+(-1)^{n+1}\frac{1}{n!}

\displaystyle 1-P[E_1 \cup E_2 \cup \cdots \cup E_n]=1-1+\frac{1}{2!}-\frac{1}{3!}+\cdots+(-1)^{n}\frac{1}{n!}

Note that the left-hand side of the above equality is the first n+1 terms in the expansion of e^{-1}. Thus we have:

\displaystyle \begin{aligned}\lim_{n \rightarrow \infty}P[E_1 \cup E_2 \cup \cdots \cup E_n]&=\lim_{n \rightarrow \infty}\biggl(1-\frac{1}{2!}+\frac{1}{3!}-\cdots+(-1)^{n+1}\frac{1}{n!}\biggr)\\&=1-e^{-1}\\&=0.6321205588 \end{aligned}

The above limit converges quite rapidly. Let P_n=P[E_1 \cup E_2 \cup \cdots \cup E_n]. The following table lists out the first several terms of this limit.

\displaystyle \begin{pmatrix} n&\text{   }&P_n \\{2}&\text{   }&0.50000 \\{3}&\text{   }&0.66667 \\{4}&\text{   }&0.62500 \\{5}&\text{   }&0.63333 \\{6}&\text{   }&0.63194 \\{7}&\text{   }&0.63214 \\{8}&\text{   }&0.63212\end{pmatrix}

Sketch of Proof for the Formula
The key idea is that any sample point in the union E_1 \cup E_2 \cdots \cup E_n is counted in exactly one time in the right hand side of (1). Suppose that a sample point is in exactly t of the events E_1,E_2,\cdots,E_n. Then the following shows the number of times the sample point is counted in each expression:

\displaystyle \sum \limits_{m=1}^{n}P[E_m] \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ t \text{ times}

\displaystyle \sum \limits_{a<b}P[E_a \cap E_b] \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \binom{t}{2} \text{ times}

\displaystyle \sum \limits_{a<b<c}P[E_a \cap E_b \cap E_c] \ \ \ \ \ \ \ \ \ \binom{t}{3} \text{ times and so on}

Thus the sample point in question will be counted exactly H times in the right hand side of the formula.

\displaystyle H=\binom{t}{1}-\binom{t}{2}+\binom{t}{3}- \cdots + (-1)^{t+1}\binom{t}{t}

The following is the derivation that H=1.

\displaystyle 0=(1-1)^t=\sum \limits_{a=0}^{t} \binom{t}{a}(-1)^{a}(1)^{t-a}=\binom{t}{0}-\binom{t}{1}+\binom{t}{2}+ \cdots +(-1)^t \binom{t}{t}

\displaystyle 1=\binom{t}{0}=\binom{t}{1}-\binom{t}{2}- \cdots +(-1)^{t+1} \binom{t}{t}=H

Reference

  1. Feller, W., An Introduction to Probability Theory and its Applications, Vol. I, 3rd ed., John Wiley & Sons, Inc., New York, 1968

Previous Posts on The Matching Problem
The Matching Problem

More About the Matching Problem

Tis the Season for Gift Exchange

Tis the Season for Gift Exchange

Suppose that there are 10 people in a holiday party with each person bearing a gift. The gifts are put in a pile and each person randomly selects one gift from the pile. In order not to bias the random selection of gifts, suppose that the partygoers select gifts by picking slips of papers with numbers identifying the gifts. What is the probability that there is at least one partygoer who ends up selecting his or her own gift? In this example, selecting one’s gift is called a match. What is the probability that there is at least one match if there are more people in the party, say 50 or 100 people? What is the behavior of this probability if the size of the party increases without bound?

The above example is a description of a classic problem in probability called the matching problem. There are many colorful descriptions of the problem. One such description is that there are n married couples in a ballroom dancing class. The instructor pairs the ladies with the gentlemen at random. A match occurs if a married couple is paired as dancing partners.

Whatever the description, the matching problem involves two lists of items that are paired according to a particular order (the original order). When the items in the first list are paired with the items in the second list according to another random ordering, a match occurs if an item in the first list and an item in the second list are paired both in the original order and in the new order. The matching problem discussed here is: what is the probability that there is at least one match? Seen in this light, both examples described above are equivalent mathematically.

We now continue with the discussion of the random gift selection example. Suppose that there are n people in the party. Let E_i be the event that the i^{th} person selects his or her own gift. The event E=E_1 \cup E_2 \cup \cdots \cup E_n is the event that at least one person selects his or her own gift (i.e. there is at least one match). The probability P(E)=P(E_1 \cup E_2 \cup \cdots \cup E_n) is the solution of the matching problem as described in the beginning. The following is the probability P(E)=P(E_1 \cup E_2 \cup \cdots \cup E_n).

\displaystyle (1) \ \ \ \ \ \ P[E_1 \cup E_2 \cup \cdots \cup E_n]=1-\frac{1}{2!}+\frac{1}{3!}-\cdots+(-1)^{n+1} \frac{1}{n!}

The answer in (1) is obtained by using an idea called the inclusion-exclusion principle. We will get to that in just a minute. First let’s look at the results of (1) for a few iterations.

\displaystyle (2) \ \ \ \ \ \  \begin{bmatrix} \text{n}&\text{ }& P[E_1 \cup E_2 \cup \cdots \cup E_n]  \\\text{ }&\text{ }&\text{ } \\ 3&\text{ }&0.666667  \\ 4&\text{ }&0.625000  \\ 5&\text{ }&0.633333  \\ 6&\text{ }&0.631944  \\ 7&\text{ }&0.632143  \\ 8&\text{ }&0.632118 \\ 9&\text{ }&0.632121 \\ 10&\text{ }&0.632121 \\ 11&\text{ }&0.632121 \\ 12&\text{ }&0.632121 \end{bmatrix}

In a party with random gift exchange, it appears that regardless of the size of the party, there is a very good chance that someone will end up picking his or her own gift! A match will happen about 63% of the time.

It turns out that the answers in (1) are related to the Taylor’s series expansion of e^{-1}. We show that the probability in (1) will always converge to 1-e^{-1}=0.632121. Note that the Taylor’s series expansion of e^{-1} is:

\displaystyle (3) \ \ \ \ \ \ e^{-1}=\frac{1}{0!}-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\cdots+(-1)^n \frac{1}{n!}+\cdots

Consequently, the Taylor’s series expansion of 1-e^{-1} is:

\displaystyle \begin{aligned} (4) \ \ \ \ \ \   1-e^{-1}&=1-\biggl(1-1+\frac{1}{2!}-\frac{1}{3!}+\cdots+(-1)^n \frac{1}{n!}+\cdots \biggr) \\&=1-\frac{1}{2!}+\frac{1}{3!}-\cdots+(-1)^{n+1} \frac{1}{n!}+\cdots  \end{aligned}

Note that the sum of the first n terms of the series in (4) is the probability in (1). As the number of partygoers n increases, the probability P[E_1 \cup E_2 \cup \cdots \cup E_n] will be closer and closer to 1-e^{-1}=0.6321. We have:

\displaystyle (5) \ \ \ \ \ \ \lim \limits_{n \rightarrow \infty} P[E_1 \cup E_2 \cup \cdots \cup E_n]=1 - e^{-1}

\displaystyle (6) \ \ \ \ \ \ \lim \limits_{n \rightarrow \infty} P[(E_1 \cup E_2 \cup \cdots \cup E_n)^c]=e^{-1}

The equation (5) says that it does not matter how many people are in the random gift exchange, the answer to the matching problem is always 1-e^{-1} in the limit. The equation (6) says that the probability of having no matches approaches e^{-1}. There is a better than even chance (0.63 to be more precise) that there is at least one match. So in a random gift exchange as described at the beginning, it is much easier to see a match than not to see one.

The Inclusion-Exclusion Principle

We now want to give some indication why (1) provides the answers. The inclusion-exclusion principle is a formula for finding the probability of the union of events. For the union of two events and the union of three events, we have:

\displaystyle (7) \ \ \ \ \ \ P[E_1 \cup E_2]=P[E_1]+P[E_1]-P[E_1 \cap E_2]

\displaystyle \begin{aligned} (8) \ \ \ \ \ \   P[E_1 \cup E_2 \cup E_3]&=P[E_1]+P[E_1]+P[E_3] \\& \ \ \ \ -P[E_1 \cap E_2]-P[E_1 \cap E_3]-P[E_2 \cap E_3] \\& \ \ \ \ +P[E_1 \cap E_2 \cap E_3]  \end{aligned}

To find the probability of the union of n events, we first add up the probabilities of the individual events E_i. Because the resulting sum overshoots, we need to subtract the probabilities of the intersections E_i \cap E_j. Because the subtractions remove too much, we need to add back the probabilities of the intersections of three individual events E_i \cap E_j \cap E_k. The process of inclusion and exclusion continues until we reach the step of adding/removing of the intersection E_1 \cap \cdots \cap E_n. The following is the statement of the inclusion-exclusion principle.

\displaystyle (9) \ \ \ \ \ \ P[E_1 \cup E_2 \cdots \cup E_n]=S_1-S_2+S_3- \ \ \cdots \ \ +(-1)^{n+1}S_n

In (9), S_1 is the sum of all probabilities P[E_i], S_2 is the sum of all possible probabilities of the intersection of two events E_i and E_j and S_3 is the sum of all possible probabilities of the intersection of three events and so on.

We now apply the inclusion-exclusion principle to derive equation (1). The event E_i is the event that the i^{th} person gets his or her own gift while the other n-1 people are free to select gifts. The probability of this event is \displaystyle P[E_i]=\frac{(n-1)!}{n!}. There are \displaystyle \binom{n}{1}=\frac{n!}{1! (n-1)!} many ways of fixing 1 gift. So \displaystyle S_1=\binom{n}{1} \times \frac{(n-1)!}{n!}=1.

Now consider the intersection of two events. The event E_i \cap E_j is the event that the i^{th} person and the j^{th} person get their own gifts while the other (n-2) people are free to select gifts. The probability of this event is \displaystyle P[E_i \cap E_j]=\frac{(n-2)!}{n!}. There are \displaystyle \binom{n}{2}=\frac{n!}{2! (n-2)!} many ways of fixing 2 gifts. So \displaystyle S_2=\binom{n}{2} \times \frac{(n-2)!}{n!}=\frac{1}{2!}.

By the same reasoning, we derive that \displaystyle S_3=\frac{1}{3!} and \displaystyle S_4=\frac{1}{4!} and so on. Then plugging \displaystyle S_i=\frac{1}{i!} into (9), we obtain the answers in (1).

The matching problem had been discussed previously in the following posts.

The matching problem

Mote about the matching problem

More about the matching problem

We started the discussion on the matching problem in a previous post (The matching problem). We would like to add a little bit more information. The matching problem has many colorful descriptions. Here are some examples:

  • In a dance class with n married couples,¬†suppose that¬†the dance instructor assigns partners randomly. We have a match if a married couple is paired as dancing partners.
  • There are n letters with n matching envelops. Suppose that the letters are randomly stuffed into the envelops. We have a match if a letter is placed into the correct envelop.

In this post we use the generic example of a deck of shuffled cards. Suppose a deck of n cards is numbered 1 through n. After the deck is thoroughly shuffled, if the card numbered i is the i^{th} card in the shuffled deck, we say that it is a match. It is clear that the above two examples and the shuffled deck example are equivalent mathematically.

How many matches will there be in a shuffled deck? What is the probability that there will be at least one match? What is the probability that there will be exactly k matches where k=0,1, \cdots, n? On average, how many matches will there be? The number of matches is a random variable. We comment on this random variable resulting from the matching problem. We also derive the probability density function and its moments. We also comment the relation this random variable with the Poisson distribution.

Consider the set S=\lbrace{1,2, \cdots, n}\rbrace. The matching problem corresponds to the random selection of all the points in S without replacement. The random selection of points of the entire set S results in ordered samples (Y_1,Y_2, \cdots, Y_n) where each Y_i \in S and Y_i \neq Y_j for i \neq j. These ordered samples are precisely the permutations of the set S and there are n! many such permutations.

A match occurs when some element i \in S is selected in the i^{th} pick. In the card example, the i^{th} card is a match when the card that is numbered i is in the i^{th} position in the shuffled deck (Y_i=i). The matching problem is a counting problem. We demonstrate how to count the n! permutations that result in no matches, at least one match and exactly k matches using the inclusion-exclusion principle.

For each i \in S, we define the following indicator variable I_i:

\displaystyle I_i=\left\{\begin{matrix}1&\thinspace Y_i=i \ \ \ \text{(} i^{th} \text{card is a match)}\\{0}&\thinspace Y_i \neq i \ \ \ \text{(} i^{th} \text{card is not a match)}\end{matrix}\right.

Furthermore, let X_n=I_1+I_2+ \cdots +I_n. The random variable X_n is the number of matches when a deck of n cards (numbered 1 through n) are shuffled. We derive the probability function of X_n as well as its first and second moments.

The Inclusion-Exclusion Principle
For any events A_1,A_2, \cdots, A_n, the following is the cardinality of the event A_1 \cup A_2 \cup \cdots \cup A_n:

\displaystyle \lvert A_1 \cup A_2 \cup \cdots \cup A_n \lvert=\sum \limits_{m=0}^n (-1)^{m+1} S_m where the counts S_m are defined by the following:

\displaystyle S_1=\sum \limits_{i=1}^n \lvert A_i \lvert

\displaystyle S_2=\sum \limits_{i<j} \lvert A_i \cap A_j\lvert

\displaystyle S_m=\sum \limits_{i(1)< \cdots <i(m)} \lvert A_{i(1)} \cap \cdots \cap A_{i(m)}\lvert

Remark
In the inclusion-exclusion formula, we sum the cardinalities of the sets, subtract the cardinalities of intersections of pairs, add the cardinalities of the intersection of triples and so on. When n=2, we have the familiar formula:

\displaystyle \lvert A_1 \cup A_2 \lvert=\lvert A_1 \lvert +\lvert A_2 \lvert-\lvert A_1 \cap A_2\lvert

The Probability Density Function
For each i in S=\lbrace{1,2, \cdots, n}\rbrace, let A_i be the event that the i^{th} card is a match. The event A_1 \cup \cdots \cup A_n is the event that there is at least one match in the deck of n shuffled cards. We use the inclusion-exclusion principle to derive the count for this event. The union and its complement “no matches in the cards” will become the basis for deriving the density function of X_n.

For the event A_i, the i^{th} card is fixed and the other n-1 cards are free to permute. Thus \vert A_i \vert=(n-1)!. As a result, \displaystyle S_1=\binom{n}{1} (n-1)!=n!.

For the event A_i \cap A_j, the i^{th} card and the j^{th} card are fixed and the other n-2 cards are free to permute. Thus we have \vert A_i \cap A_j \vert=(n-2)! and \displaystyle S_2=\binom{n}{2} (n-2)!=\frac{n!}{2!}

In the general case, we have \displaystyle S_i=\binom{n}{i} (n-i)!=\frac{n!}{i!}

Applying the inclusion-exclusion principle, we have:

\displaystyle \lvert A_1 \cup A_2 \cup \cdots \cup A_n \lvert=\sum \limits_{i=1}^n (-1)^{i+1} S_i

\displaystyle \begin{aligned}\lvert (A_1 \cup A_2 \cup \cdots \cup A_n)^c \lvert&=n!-\sum \limits_{i=1}^n (-1)^{i+1} S_i\\&=n!-\sum \limits_{i=1}^n (-1)^{i+1} \frac{n!}{i!}\\&=n!+\sum \limits_{i=1}^n (-1)^{i} \frac{n!}{i!}\\&=\sum \limits_{i=0}^n (-1)^{i} \frac{n!}{i!} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)\end{aligned}

Out of the n! permutations, \displaystyle \lvert (A_1 \cup A_2 \cup \cdots \cup A_n)^c \lvert of them have no matches. Thus the probability of having no matches in a shuffled deck of n cards is:

\displaystyle \begin{aligned}P(\text{no matches in n cards})&=\displaystyle \biggl(\sum \limits_{i=0}^n (-1)^{i} \frac{n!}{i!}\biggr) \frac{1}{n!}\\&=\sum \limits_{i=0}^n \frac{(-1)^{i}}{i!}\\&=P(X_n=0)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)\end{aligned}

To derive P(X_n=1), we consider the event that 1 of the cards is a match and the other n-1 cards are not matches. Using (1) to obtain the count for the event that n-1 cards are not matches, we have:

\displaystyle \begin{aligned}P(X_n=1)&=\displaystyle \binom{n}{1}\displaystyle \biggl(\sum \limits_{i=0}^{n-1} (-1)^{i} \frac{(n-1)!}{i!}\biggr) \frac{1}{n!}\\&=\sum \limits_{i=0}^{n-1} \frac{(-1)^{i}}{i!}\end{aligned}

For the general case, we have:

\displaystyle \begin{aligned}P(X_n=k)&=\displaystyle \binom{n}{k}\displaystyle \biggl(\sum \limits_{i=0}^{n-k} (-1)^{i} \frac{(n-k)!}{i!}\biggr) \frac{1}{n!}\\&=\frac{1}{k!}\sum \limits_{i=0}^{n-k} \frac{(-1)^{i}}{i!}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)\end{aligned}

We point out that P(X_n=n-1)=0. It is impossible to have exactly n-1 matches while the remaining card is not a match. This can also be verified by looking at the probability density function. On the other hand, \displaystyle P(X_n=n)=\frac{1}{n!}. There is only one permutation out of n! many where all the cards are matches.

Poisson Distribution
We compare the probability density functions P(X_{10}=k), P(X_{20}=k) P(X_{150}=k) and the Poisson desnity function with parameter \lambda=1. The following matrix shows the results (rounded to eight decimal places).

\displaystyle \begin{pmatrix} \text{k}&P(X_{10}=k)&P(X_{20}=k)&P(X_{150}=k)&\displaystyle \frac{e^{-1}}{k!} \\{\text{ }}&\text{ }&\text{ } \\{0}&0.36787946&0.36787944&0.36787944&0.36787944 \\{1}&0.36787919&0.36787944&0.36787944&0.36787944 \\{2}&0.18394097&0.18393972&0.18393972&0.18393972 \\{3}&0.06130952&0.06131324&0.06131324&0.06131324 \\{4}&0.01533565&0.01532831&0.01532831&0.01532831 \\{5}&0.00305556&0.00306566&0.00306566&0.00306566 \\{6}&0.00052083&0.00051094&0.00051094&0.00051094 \\{7}&0.00006614&0.00007299&0.00007299&0.00007299 \\{8}&0.00001240&0.00000912&0.00000912&0.00000912 \\{9}&0&0.00000101&0.00000101&0.00000101 \\{10}&0.00000028&0.00000010&0.00000010&0.00000010 \\{\text{ }}&\text{ }&\text{ } \\{\text{Total}}&1.000000&0.99999997&0.99999997&0.99999997\end{pmatrix}

There is remarkable agreement among the density functions arising from the match problems with the Poisson distribution. The density function P(X_n=k) converges to the Poisson distribution with parameter \lambda=1 and the convergence occurs rapidly.

The probability of having exactly k matches in (3) above converges to \displaystyle \frac{e^{-1}}{k!}, which is the Poisson distribution with parameter \lambda=1.

The probability of no matches among the n cards in (2) above is the Taylor expansion of e^{-1}. Thus the probability of no matches in a shuffled deck of n cards when n is large is about 0.3678794412 and the probability of at least one match is approximately 0.6321205588. As the above example shows, the convergence occurs fairly rapidly.

The Moments
Since P(X_n=k) converges to the Poisson distribution with parameter \lambda=1, we might guess that the mean and variance of X_n approach \lambda=1. We now show that E(X_n)=1 and Var(X_n)=1 regardless of n.

Recall that X_n=I_1+I_2+ \cdots +I_n where for each j=1,2, \cdots, n, I_j is an indicator variable:

\displaystyle I_j=\left\{\begin{matrix}1&\thinspace Y_j=j \ \ \ \text{(} j^{th} \text{card is a match)}\\{0}&\thinspace Y_j \neq j \ \ \ \text{(} j^{th} \text{card is not a match)}\end{matrix}\right.

We claim that for all j=1,2, \cdots, n, \displaystyle P(I_j=1)=\frac{1}{n} and for all i<j, \displaystyle P(I_i=1,I_j=1)=\frac{1}{n(n-1)}. To see this, the event (I_j=1) is the event A_j defined in the derivation of the probability density function of X_n. We have \lvert A_j \vert=(n-1)!. Thus the probability that the j^{th} card is a match is:

\displaystyle P(I_j=1)=\frac{(n-1)!}{n!}=\frac{1}{n}

The event (I_i=1, I_j=1) is the event A_i \cap A_j defined in the derivation of the probability density function of X_n. We have \lvert A_i \cap A_j \vert=(n-2)!. Thus the probability that both the i^{th} card and the j^{th} card are matches is:

\displaystyle P(I_i=1,I_j=1)=\frac{(n-2)!}{n!}=\frac{1}{n(n-1)}

It follows that for all j=1,2, \cdots, n, I_j has the Bernoulli distribution with probability of success \displaystyle P(I_j=1)=\frac{1}{n}.

Knowing that I_j is Bernoulli, we know its mean and variance. For j=1,2, \cdots, n, we have:

\displaystyle E(I_j)=\frac{1}{n}

\displaystyle Var(I_j)=\frac{1}{n} \biggl(1-\frac{1}{n}\biggr)=\frac{n-1}{n^2}

It is now easy to see that E(X_n)=1. To find Var(X_n), we need to find the covariance Cov(I_i,I_j). Note that the indicator variables I_j are not independent. In evaluating Cov(I_i,I_j), we need to consider four possibilities: (I_i=0,I_j=0), (I_i=0,I_j=1), (I_i=1,I_j=0), (I_i=1,I_j=1). The only relevant case is the last one. Thus we have:

\displaystyle \begin{aligned}Cov(I_i,I_j)&=E(I_i I_j)-E(I_i) E(I_j)\\&=\biggl(\sum \limits_{x,y=0,1} x \ y P(I_i=x,I_j=y)\biggr)-E(I_i) E(I_j)\\&=P(I_i=1,I_j=1)-E(I_i) E(I_j)\\&=\frac{1}{n(n-1)}-\frac{1}{n^2}\\&=\frac{1}{n^2 (n-1)} \end{aligned}

The following derives the variance:

\displaystyle \begin{aligned}Var(X_n)&=\sum \limits_{i=1}^n Var(I_i)+2 \sum \limits_{i \ne j} Cov(I_i,I_j)\\&=n \frac{n-1}{n^2}+2 \binom{n}{2} \frac{1}{n^2 (n-1)}\\&=1 \end{aligned}

Reference

  1. Feller, W., An Introduction to Probability Theory and its Applications, Vol. I, 3rd ed., John Wiley & Sons, Inc., New York, 1968

The matching problem

One of the classic problems in probability theory is the “matching problem.” This problem has many variations and dated back to the early 18th century. There are many ways to describe the problem. One such description is the example of matching letters with envelops. Suppose there are n letters with n matching envelops (assume that each letter has only one matching envelop). Further suppose that the secretary stuffs the letters randomly into envelops. What is the probability that every letter is matched correctly, or that no letter is matched correctly or that exactly k letters are stuffed into the correct envelops? In this post we solve a simpler problem. What is the probability that at least one letter is stuffed into a correct envelop? Though the answer is in terms of the total number of letters n, it turns out that the answer is practically independent of n and is roughly \frac{2}{3}.

We first states the formula for the union of n events. After we apply this formula to obtain the answer to the matching problem, we give a sketch of a proof to the formula.

The union of n events
For any n events E_1,E_2, \cdots,E_n that are defined on the same sample space, we have the following formula:

P[E_1 \cup E_2 \cup \cdots \cup E_n]=\sum \limits_{m=1}^{n} (-1)^{m+1} \thinspace S_m where

S_1=\sum \limits_{r=1}^{n}P[E_r],

S_2=\sum \limits_{j<k}P[E_j \cap E_k],

S_m=\sum P[E_{i(1)} \cap E_{i(2)} \cap \cdots \cap E_{i(m)}]

Note that in the general term S_m, the sum is taken over all increasing sequence i(\cdot), i.e. 1 \le i(1) < i(2) < \cdots < i(m) \le n. For n=2,3, we have the following familiar formulas:

\displaystyle P[E_1 \cup E_2]=P[E_1]+P[E_2]-P[E_1 \cap E_2]

\displaystyle P[E_1 \cup E_2 \cup E_3]=
\displaystyle P[E_1]+P[E_2]+P[E_3]-P[E_1 \cap E_2]-P[E_1 \cap E_3]-P[E_2 \cap E_3]+P[E_1 \cap E_2 \cap E_3]

The matching problem
Suppose that the n letters are numbered 1,2, \cdots, n. Let E_i be the event that the i^{th} letter is stuffed into the correct envelop. Then P[E_1 \cup E_2 \cup \cdots \cup E_n] is the probability that at least one letter is matched with the correct envelop.

The probability of the intersection of m events is:

\displaystyle P[E_{i(1)} \cap E_{i(2)} \cap \cdots \cap E_{i(m)}]=\frac{(n-m)!}{n!}.

For m=1, we have P[E_i]=\frac{(n-1)!}{n!}=\frac{1}{n}. Note that the i^{th} position is fixed and we permute the other n-1 positions. For m=2, we have P[E_i \cap E_j]=\frac{(n-2)!}{n!}. Here, the i^{th} and j^{th} positions are fixed and we permute the other n-2 positions.

We now show that S_m=\frac{1}{m!}. There are \binom{n}{m} number of ways to have m matches out of n letters. Thus we have:

\displaystyle S_m=\binom{n}{m} \frac{(n-m)!}{n!}=\frac{1}{m!}

Using the formula for the union of n events, we have:

\displaystyle P[\bigcup_{m=1}^{n} E_m]=1-\frac{1}{2!}+\frac{1}{3!}- \cdots + (-1)^{n+1}\frac{1}{n!}

\displaystyle 1-P[\bigcup_{m=1}^{n} E_m]=1-1+\frac{1}{2!}-\frac{1}{3!}+ \cdots + (-1)^{n}\frac{1}{n!}

Note that the left hand side of the above is the first n+1 terms of the expansion of e^{-1}. Thus we have:

\displaystyle \lim_{n \rightarrow \infty}P[\bigcup_{m=1}^{n} E_m]=\lim_{n \rightarrow \infty}\biggl(1-\frac{1}{2!}+\frac{1}{3!}- \cdots + (-1)^{n+1}\frac{1}{n!}\biggr)

=1-e^{-1}=0.632121

The above limit converges quite rapidly. Let P_n=P[\bigcup_{m=1}^{n} E_m]. The following matrix shows the first several terms of this limit.

\displaystyle \begin{pmatrix} n&P_n \\{2}&0.50000 \\{3}&0.66667 \\{4}&0.62500 \\{5}&0.63333 \\{6}&0.63194 \\{7}&0.63214 \\{8}&0.63212\end{pmatrix}

Sketch of proof
We now discuss the union formula:

P[E_1 \cup E_2 \cup \cdots \cup E_n]=\sum \limits_{m=1}^{n} (-1)^{m+1} \thinspace S_m

The key idea is that any sample point in the union E_1 \cup \cdots \cup E_n is counted exactly one time in the right hand side of the formula. Suppose that a sample point is in exactly t events E_{i(1)}, \cdots E_{i(t)}. Then the following shows the number of times the sample point is counted in each expression:

\displaystyle \sum \limits_{m=1}^{n}P[E_m] \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ t times

\displaystyle \sum \limits_{a<b}P[E_a \cap E_b] \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \binom{t}{2} times

\displaystyle \sum \limits_{a<b<c}P[E_a \cap E_b \cap E_c] \ \ \ \ \ \ \ \ \ \binom{t}{3} times and so on

Thus the sample point in question will be counted exactly H times in the right hand side of the formula.

\displaystyle H=\binom{t}{1}-\binom{t}{2}+\binom{t}{3}- \cdots + (-1)^{t+1}\binom{t}{t}

The following is the derivation that H=1.

\displaystyle 0=(1-1)^t=\sum \limits_{a=0}^{t} \binom{t}{a}(-1)^{a}(1)^{t-a}=\binom{t}{0}-\binom{t}{1}+\binom{t}{2}+ \cdots +(-1)^t \binom{t}{t}

\displaystyle 1=\binom{k}{0}=\binom{t}{1}-\binom{t}{2}- \cdots +(-1)^{t+1} \binom{t}{t}=H