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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s