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 letters with 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 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 , it turns out that the answer is practically independent of and is roughly .
We first states the formula for the union of 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 events that are defined on the same sample space, we have the following formula:
Note that in the general term , the sum is taken over all increasing sequence , i.e. . For , we have the following familiar formulas:
The matching problem
Suppose that the letters are numbered . Let be the event that the letter is stuffed into the correct envelop. Then is the probability that at least one letter is matched with the correct envelop.
The probability of the intersection of events is:
For , we have . Note that the position is fixed and we permute the other positions. For , we have . Here, the and positions are fixed and we permute the other positions.
We now show that . There are number of ways to have matches out of letters. Thus we have:
Using the formula for the union of events, we have:
Note that the left hand side of the above is the first terms of the expansion of . Thus we have:
The above limit converges quite rapidly. Let . The following matrix shows the first several terms of this limit.
Sketch of proof
We now discuss the union formula:
The key idea is that any sample point in the union is counted exactly one time in the right hand side of the formula. Suppose that a sample point is in exactly events . Then the following shows the number of times the sample point is counted in each expression:
times and so on
Thus the sample point in question will be counted exactly times in the right hand side of the formula.
The following is the derivation that .