[Math] Matching hats problem: how to calculate expectation for a finite number of cases.

combinatoricsprobability

This is from my practice final exam. A variation with '$8$' instead of '$7$' can also be seen in an exam paper from MIT ocw probability course here: http://ocw.mit.edu/courses/mathematics/18-440-probability-and-random-variables-spring-2014

$7$ people throw their hats into a box and then randomly redistribute the hats among themselves (each person getting one hat, all $7!$ permutations equally likely). Let $X$ be the number of people who get their own hats back. Compute the following:

  1. $E(X)$
  2. $P(X = 6)$
  3. $P(X = 5)$

For the 1st part: Is there a way to derive the expression without resorting to the approach of expressing the RV $X$ as 'sum of $k$ simpler experiments'. The answer is $1$ for this but I don't get any reason why it should be so.

For the 2nd part: $P(X=6) = 0$ since if $X=6$ the last hat ends up on its owner automatically so this case is not possible.

For the 3rd part: I get the probability for any $k < 6$ as follows

$$P(X=k)={n \choose k}\frac{(n-k)!}{n!}\cdot \left(1 – 1/2! + 1/3! – 1/4! + \ldots (-1)^n\cdot \frac1{(n-k)!}\right)$$

The 1st half of the expression simplifies to $1/k!$. $n \choose k$ is for selecting $k$ elements out of n and then selecting $1/n,\ldots,1/(n-k+1)$ hats for the $k$ owners. The second half is to make sure the remaining $(n-k)$ people do NOT get their hats back. I used the general inclusion-exclusion principle here. Substituting $n=7,k=5$ here gives the answer as $(1/5!\cdot1/2)=\frac{1}{240}$

Is any of this correct?

Best Answer

Hint on first part:

For $i=1,\dots,7$ let $X_i$ take value $1$ if person $i$ gets his own hat, and value $0$ if he does not. Then:$$X=X_1+\cdots+X_7$$ Find the expectation by making use of linearity of expectation.


On the third part:

Let's say that they take their hat one by one and look at the possibility that the first $5$ get their own hat and the others do not.

That gives probability $\frac{1}{7}\frac{1}{6}\frac{1}{5}\frac{1}{4}\frac{1}{3}\times\frac{1}{2}\frac{1}{1}=\frac{1}{7!}$.

That results in a probability of $\binom{7}{5}\frac{1}{7!}=\frac{1}{240}$.