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 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 people in the party. Let be the event that the person selects his or her own gift. The event is the event that at least one person selects his or her own gift (i.e. there is at least one match). The probability is the solution of the matching problem as described in the beginning. The following is the probability .
The answer in 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 for a few iterations.
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 are related to the Taylor’s series expansion of . We show that the probability in will always converge to . Note that the Taylor’s series expansion of is:
Consequently, the Taylor’s series expansion of is:
Note that the sum of the first terms of the series in is the probability in . As the number of partygoers increases, the probability will be closer and closer to . We have:
The equation says that it does not matter how many people are in the random gift exchange, the answer to the matching problem is always in the limit. The equation says that the probability of having no matches approaches . There is a better than even chance ( 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 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:
To find the probability of the union of events, we first add up the probabilities of the individual events . Because the resulting sum overshoots, we need to subtract the probabilities of the intersections . Because the subtractions remove too much, we need to add back the probabilities of the intersections of three individual events . The process of inclusion and exclusion continues until we reach the step of adding/removing of the intersection . The following is the statement of the inclusion-exclusion principle.
In , is the sum of all probabilities , is the sum of all possible probabilities of the intersection of two events and and 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 . The event is the event that the person gets his or her own gift while the other people are free to select gifts. The probability of this event is . There are many ways of fixing 1 gift. So .
Now consider the intersection of two events. The event is the event that the person and the person get their own gifts while the other people are free to select gifts. The probability of this event is . There are many ways of fixing 2 gifts. So .
By the same reasoning, we derive that and and so on. Then plugging into , we obtain the answers in .
The matching problem had been discussed previously in the following posts.