Hat check problem

Textbook’s version of the problem

If $n$ people write their names on a card, place the $n$ cards in a hat, and each person draws a card at random (and independently, without replacement), what is the expected number of people that draw their own name?

We can let $X$ be the r.v. that equals the number of people that draw their own name. We want to find $\mathbb{E}(X)$. We can use an Indicator variable for each person, and let $X_i=1$ if the $i$th person draws their own name. By LOE, we have $\mathbb{E}(X)={\sum }_{i=1}^{n}P(X_i=1)$.

For the $i$th person to draw their name, the previous $i-1$ people must not have drawn their name. then we can express $P(X_i=1)$ as a chain of probabilities:

$$P(X_i=1)=\left(\frac{n-1}{n}\right)\left(\frac{n-2}{n-1}\right)\dots \left(\frac{n-i}{n-i+1}\right)\left(\frac{1}{n-i}\right)=\frac{1}{n}$$

The final $\frac{i}{n-i}$ term is the probability that the $i$th person draws their own card.

The result $\frac{1}{n}$ seems counterintuitive at first. Since we’re drawing cards without replacing, it seemed like the probability should depend on what $i$ is. But every indicator variable only depends on $n$.

We have $\mathbb{E}(X)={\sum }_{i=1}^{n}P(X_i=1)={\sum }_{i=1}^n\frac{1}{n}=1$.

Original question

The original version of this question involves returning $n$ hats back to their respective owner, and asked what the probability that no one gets their own hat back is, hence the name of the problem.

It turns out that as ${\lim }_{n\to \infty }$, the probability approaches $\frac{1}{e}$.

Also see

• Mathematics Stack Exchange
• Derangement - Wikipedia