Matching Problem

There are $n$ letters and $n$ corresponding envelopes. Insert each letter into an envelope at random. Let $X$ be the number of correct matches between the letter and envelope.

Mean

Let $X_i$ be the indicator random variable that equals 1 when the $i$th letter is put into the correct envelope, and equals 0 otherwise. By symmetry, we know that $X_i$ have the same distribution, and $P(X_i=1)=\frac{1}{n}$. Then we have

$$\mathbb{E}[X]=\sum _{i=1}^n\mathbb{E}[X_i]=n/n=1.$$

Variance

We have

$$\begin{array}{rl}\mathrm{Var}\left(\sum _i{X}_i\right)& =\sum _{i,j}\mathrm{Cov}(X_i,X_j)\\ & =n\mathrm{Var}(X_1)+n(n-1)\mathrm{Cov}(X_1,X_2)\\ & =n\left(\frac{1}{n}-\frac{1}{n^2}\right)+n(n-1)\left(\frac{1}{n(n-1)}-\frac{1}{n^2}\right)\\ & =1,\end{array}$$

where in the second equality we utilize the symmetry of $X_i$s; and in the third equality we use $E[X_1^2]=1/n$ and $E[X_1{X}_2]=1/(n(n-1))$.

PMF

For any $r\in [n]$, the event $\{X=r\}$ is equivalent to that there exists a set of $r$ letters ($S$) such that each letter is put into the correct envelope ($B_S$), and the remaining $n-r$ letters are put into the wrong envelopes ($C_S$). Formally, we have

$$\{X=r\}=\bigcup _{S:|S|=r}\left(B_S\cap C_S\right).$$

Note that $B_S\cap C_S$ for different subset $S$ are disjoint sets in $|\Omega |=n!$. Thus,

$$P(X=r)=\sum _{S:|S|=r}P(B_S\cap C_S)=\left(\genfrac{}{}{0ex}{}{n}{r}\right)P(B_S)P(C_S\mid B_S),$$

where the last equality uses symmetry. The probability of $B_S$ is straightforward:

$$P(B_S)=\frac{(n-r)!}{n!}.$$

The probability of $P(C_S\mid B_S)$ is the same as if there are only $n-r$ letters and envelopes, and there is no match. By the inclusion-exclusion principle, we have

$$\begin{array}{rl}P(C_S\mid B_S)=& P(\tilde{X}=0)\\ =& 1-P({\cup }_{i=1}^{n-r}\{{\tilde{X}}_i=1\})\\ =& 1-\left(\sum _{i=1}^{n-r}P({\tilde{X}}_i=1)-\sum _{i<j}P({\tilde{X}}_i={\tilde{X}}_j=1)+\dots \right)\\ =& 1-\left(\left(\genfrac{}{}{0ex}{}{n-r}{1}\right)\cdot \frac{(n-r-1)!}{(n-r)!}-\left(\genfrac{}{}{0ex}{}{n-r}{2}\right)\cdot \frac{(n-r-2)!}{(n-r)!}+\dots \right)\\ =& 1-\left(1-\frac{1}{2!}+\frac{1}{3!}-\cdots +(-1{)}^{n-r+1}\frac{1}{(n-r)!}\right)\\ =& \frac{1}{2!}-\frac{1}{3!}+\cdots +(-1{)}^{n-r}\frac{1}{(n-r)!}.\end{array}$$

Together, we get

$$P(X=r)=\left(\genfrac{}{}{0ex}{}{n}{r}\right)\frac{(n-r)!}{n!}\left(\frac{1}{2!}-\frac{1}{3!}+\cdots +(-1{)}^{n-r}\frac{1}{(n-r)!}\right)=\frac{1}{r!}\left(\frac{1}{2!}-\frac{1}{3!}+\cdots +(-1{)}^{n-r}\frac{1}{(n-r)!}\right).$$

Note that the above formula is only valid for $r\le n-2$. When $r=n$, we have $P(X=n)=P({\cap }_{i=1}^n\{X_i=1\})=1/n!$. And $\{X=n-1\}$ is impossible.

• Additionally, the probability $P(X=r)$ converges to $e^{-1}/r!$ as $n\to \infty$, which corresponds to the Poisson Distribution with $\lambda =1$. An intuitive justification is that $X_i$ are not independent; on the other hand, as $n\to \infty$, they are “approximately independent”. Furthermore, the success probability for each match is $1/n\to 0$, giving a similar situation as in Poisson Distribution as Approximation to Binomial Distribution.