The matching problem
Before an exam, n students drop their phones in a basket. Afterwards the phones are handed back completely at random. How likely is it that nobody gets their own phone back?
From the slides: Additional material and Probability and what happens when you learn something.
Press Hand back once. Each circle is a student; the number below is whose phone they got.
Handouts
0
Nobody gets their own phone
—
Average number of matches
—
exactly 1, for every n
What to notice
- P(no match) = 1 − 1 + 1/2! − 1/3! + … ± 1/n!, which tends to 1/e ≈ 0.3679. By n = 7 it is already 1/e to four decimal places, so ten students or ten thousand give about the same answer.
- Two effects cancel: with more students each is less likely to get their own phone, but there are more students who could.
- The number of matches has P(exactly k) = Pn−k/k! → e−1/k!, a Poisson distribution. Exactly n − 1 matches is impossible: the last phone left would be the last student's own.