P: Hats

September, 2026

Problem

Suppose there is a dinner party where $n$ men check their hats. The hats get mixed up during dinner, so that afterward each man receives a random hat. In particular, each man gets his own hat with probabilit of $\frac{1}{n}$ .

What is the expected number of men who get their own hat?

Discussion

$G$ - number of men who get their hat $E x [G] = ?$

We'll use the linearity of expectation and express $G$ as sum of random variables:

G = G_{1} + G_{2} + \dots + G_{n}

We will define $G_{i}$ as an indicator for the event that man $i$ gets his own hat.

G_{i} = {10 if man i got his hat otherwise

Variables are not mutually independant. We, however, do not need to worry, since linearity is preserved.

E x [G_{i}] = P r [G i = 1] = \frac{1}{n}

Now, according to linearity:

E x [G] = E x [G_{1} + G_{2} + \dots + G_{n}] = E x [G_{1}] + E x [G_{2}] + \dots + E x [G_{n}] = \frac{1}{n} + \frac{1}{n} + \dots + \frac{1}{n} = 1

Thus, on average, we expect only 1 man to get his hat!