Solution
Ten Letters, Ten Envelopes
Show the problem again
A secretary has 10 letters and 10 envelopes, each letter addressed to a different recipient and each envelope labelled for one of them. She places the letters into the envelopes uniformly at random, one letter per envelope (every one of the 10! arrangements is equally likely). What is the expected number of letters that end up in their correct envelope? Give an exact number.
Worked solution
The answer is 1. Let X_i be the indicator that letter i lands in its own envelope. Letter i is equally likely to be in any of the 10 envelopes, so P(X_i = 1) = 1/10. The number of correctly placed letters is X_1 + ... + X_10, and by linearity of expectation its mean is 10 × (1/10) = 1. The indicators are far from independent (if nine letters are correct, the tenth must be too), but linearity does not care. The same argument shows the answer is 1 for any number of letters, which is why the matching problem is the standard first example of the indicator method.
Source: Montmort's matching problem (problème des rencontres), classic since the early 18th century. Statement written for AxiomIQ.