Answer: Probability No Man Gets His Own Hat in Hat Matching Problem

[hotvette]

Homework Statement

N men throw their hats on to the floor, mix them up, and draw at random. What is the probability that no man gets his own hat

Homework Equations

$$P(E_1^c E_2^c \dots E_N^c) = 1-P(E_1 \cup E_2 \dots \cup E_N)$$
$$P(\text{n-tuple}) = \frac{1}{n!}$$

The Attempt at a Solution

The way I've seen this explained appears to me to have an inconsistency that I don't know how to resolve.

1). Total # arrangements of N hats among N men is $N!$ This is the denominator in the probability expression.

2). Define $E_i$ as the event that n=1 man chooses his own hat. Imagine man #1 choosing a hat first. There is only 1 way he can choose his own hat. The remaining $(N-1)$ hats can be arranged $(N-1)!$ ways. But, since each man can choose first, we must multiply by $C_1^N = N$. Thus $P(E_1) = P(E_2) \dots = P_N) = N (N-1)!/N! = 1 = \frac{1}{n!}$

3) Same argument for k=2, k=3, etc. gives the result stated above.

Here is what doesn't make sense to me. If we argue that there are N ways that a man can choose first, that implies order of choosing is important. If order is important, then the order of choosing 2nd, 3rd, etc. is also important, which isn't accounted for in the above argument.

What am I missing?

 

[Ray Vickson]

Homework Statement

N men throw their hats on to the floor, mix them up, and draw at random. What is the probability that no man gets his own hat

Homework Equations

$$P(E_1^c E_2^c \dots E_N^c) = 1-P(E_1 \cup E_2 \dots \cup E_N)$$
$$P(\text{n-tuple}) = \frac{1}{n!}$$

The Attempt at a Solution

The way I've seen this explained appears to me to have an inconsistency that I don't know how to resolve.

1). Total # arrangements of N hats among N men is $N!$ This is the denominator in the probability expression.

2). Define $E_i$ as the event that n=1 man chooses his own hat. Imagine man #1 choosing a hat first. There is only 1 way he can choose his own hat. The remaining $(N-1)$ hats can be arranged $(N-1)!$ ways. But, since each man can choose first, we must multiply by $C_1^N = N$. Thus $P(E_1) = P(E_2) \dots = P_N) = N (N-1)!/N! = 1 = \frac{1}{n!}$

3) Same argument for k=2, k=3, etc. gives the result stated above.

Here is what doesn't make sense to me. If we argue that there are N ways that a man can choose first, that implies order of choosing is important. If order is important, then the order of choosing 2nd, 3rd, etc. is also important, which isn't accounted for in the above argument.

What am I missing?

You are confusing yourself by supposing a particular order for choosing. The probability that man i chooses his own hat is $P(E_i) = 1/N$ for all $i = 1,2 \cdots, N.$ The easiest and surest way to see this is similar to what you did: among all the $N!$ permutations, hat number $i$ falls in position $i$ in $(N-1)!$ of the cases, so $P(E_i) = (N-1)!/N! = 1/N.$ Of course we have that that $\sum_{i=1}^N P(E_i) = 1$, but that is only a small first step towards the probability that at least one man gets his own hat. Note that the occurrence of event $E_i$ says nothing at all about whether some other men also get their own hats; it just looks at what happens to man $i$.

Next, for any fixed pair $i < j$, the number of permutations in which hat $i$ falls in position $i$ and hat $j$ in position $j$ is $(N-2)!$, so $P(E_i, E_j) = (N-2)!/N! = 1/[N(N-1)].$ Thus, $\sum_{i < j} P(E_i,E_j) = {N \choose 2}/[N(N-1)] = 1/2! .$ (Here I use the notation $P(A,B)$ instead of $P(A \cap B) .$) Similarly, $\sum_{i < j < k} P(E_i, E_j, E_k) = 1/3!$, etc.

Now use the general inclusion-exclusion principle to get $P_{\geq 1}$ =probability that at least one man gets his own hat:
$$P_{\geq 1} \equiv P(E_1 \cup E_2 \cup \cdots \cup E_N) = S_1 - S_2 + S_3 - \cdots \pm S_N, $$
where
$$S_1 = \sum_{i} P(E_i)=1,\\
S_2 = \sum_{i < j} P(E_i, E_j)=1/2!, \\
S_3 = \sum_{i < j < k} P(E_i,E_j,E_k)= 1/3!\\
\vdots\\
S_N = P(E_1,E_2, \ldots, E_N) = 1/N!
$$
Of course, the probability that 0 men get their own hats is $P_0 = 1 - P_{\geq 1} .$

All of this stuff is presented beautifully in Feller, "An Introduction to Probability Theory and its Applications", Vol. I, Wiley (1968). That treatment is now considered old-fashioned, but in my opinion is still the clearest and most direct.