Let's say there are $n$ people who threw their hats in a box where they mixed up and each one of them randomly takes one hat from the box. What's the probability that nobody got the right hat?

I'm not sure how to define the events in this problem that will lead us to the solution.
For example, if I define the following events:
$A_i$ - $i$-th person took the wrong hat and
$A$ - nobody got the right hat

Does that mean that: $A=\bigcap\limits_{i=1}^{n}A_i$?
How can we then find $P(A)$ using the inclusion-exclusion principle: $$P(A)=\sum_{i=1}^nP(A_i)-\sum_{1\leq i\leq j \leq n}P(A_i\cap A_j)+\sum_{1\leq i\leq j \leq k \leq n}P(A_i\cap A_j\cap A_k)-\cdot\cdot\cdot+(-1)^{n-1}P(A_1\cap A_2\cap \cdot\cdot\cdot\cap A_n)$$

  • 4
    $\begingroup$ This is the classic derangement problem. en.wikipedia.org/wiki/Derangement $\endgroup$ – ncmathsadist Jul 9 '18 at 15:47
  • 1
    $\begingroup$ The answer to the first question is "yes." Nobody got the right hat is the same as everyone hot the wrong hat. $\endgroup$ – saulspatz Jul 9 '18 at 15:51
  • 1
    $\begingroup$ Yes. If $X$ is the number of people who get the the right hat, then inclusion-exclusion leads to $P(X=0) = 1/2! - 1/3! +- \cdots +(-1)^n/n!.$ The details are in Ross's Probability Models (1997), Feller (1957), and many other places. This is known at the 'hat check problem' and the 'problem of derangements'. For $n > 10, X$ is nearly $\mathsf{Pois}(1).$ (But obviously not exactly Poisson, because $P(X = n-1) = P(X > n) = 0.$ For any $n,$ you can use indicator functions to find $E(X) = 1.$ Also, $Var(X) = 1,$ but that's not so easy to prove. $\endgroup$ – BruceET Jul 9 '18 at 16:00

By way of enrichment we compute the expectation and the variance. We have for permutations with fixed points marked the combinatorial class

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SET}(\mathcal{U}\mathcal{Z} + \textsc{CYC}_{\ge 2}(\mathcal{Z})).$$

This gives the mixed generating function

$$G(z, u) = \exp\left(uz + \sum_{q\ge 2} \frac{z^q}{q}\right) = \exp\left(uz-z + \log\frac{1}{1-z}\right) \\= \frac{1}{1-z} \exp(uz-z).$$

The expectation of the number of fixed points is then given by (the term $u^k z^n/n!$ representing a permutation of $n$ elements with $k$ fixed points should contribute $k z^n/n!$ and here $n\ge 1$)

$$\mathrm{E}[X] = [z^n] \left. \frac{\partial}{\partial u} G(z, u) \right|_{u=1} \\ = [z^n] \left. \frac{1}{1-z} \exp(uz-z) z \right|_{u=1} \\ = [z^n] \frac{z}{1-z} = 1.$$

We get for the second factorial moment when $n\ge 2$

$$\mathrm{E}[X(X-1)] = [z^n] \left. \left(\frac{\partial}{\partial u} \right)^2 G(z, u) \right|_{u=1} \\ = [z^n] \left. \frac{1}{1-z} \exp(uz-z) z^2 \right|_{u=1} \\ = [z^n] \frac{z^2}{1-z} = 1.$$

Using that

$$\mathrm{Var}[X] = \mathrm{E}[X(X-1)] + \mathrm{E}[X] - \mathrm{E}[X]^2$$

we obtain

$$\mathrm{Var}[X] = 1.$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.