# Matching hats problem: how to calculate expectation for a finite number of cases.

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?

• A way to check your probability in part 3, is to use it to calculate the expectaion in part 1. If it yields E[k]=1, then it might be correct (just an idea, I didn't any calculation by myself. – Jimmy R. Dec 12 '15 at 9:45
• @Stef thanks for the edit and the trick. I will try it out. – user286838 Dec 13 '15 at 1:45

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}$.

• Yes. That hint is something I don't wish to use. I understand the answer is 7*(1/7) = 1. Is there a more direct approach? Well I guess calculating probability for each case and then finding expectation is something I should do but then is my part 3 correct? – user286838 Dec 12 '15 at 9:30
• Thanks, this gives me more confidence that the general formula I wrote down for part 3 might be correct. – user286838 Dec 12 '15 at 9:47
• A look here might be useful. – drhab Dec 12 '15 at 10:48