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 students, he randomly assigns the quizzes back to these 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 students is a match?
- What is the probability that none of the students is a match?
- What is the probability that exactly of the students are matches?
- What is the probability that at least one of the 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 , it turns out that the answer is independent of and is approximately . 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 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 ). 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 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 students are labeled . Let be the even that the student is assigned his or her own quiz by the professor. Then is the probability that there is at least one correct match.
Note that . This is the case since we let the student be fixed and we permute the other students. Likewise, , since we fix the and students and let the other students permute. In general, whenever are distinct integers and are increasing, we have:
We now apply the formula (1). First we show that for each where , . Since there are many ways to have matches out of students, we have:
Applying the formula for the union of events, we have:
Note that the left-hand side of the above equality is the first terms in the expansion of . Thus we have:
The above limit converges quite rapidly. Let . The following table lists out the first several terms of this limit.
Sketch of Proof for the Formula
The key idea is that any sample point in the union is counted in exactly one time in the right hand side of (1). Suppose that a sample point is in exactly of the events . Then the following shows the number of times the sample point is counted in each expression:
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 .
- 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