# The n-person hat matching problem in probability for n=3, doesn't match derangement formula

Suppose all $$n$$ people at a party throw their hats in the center of the room. Each person then randomly selects a hat. The probability that none of the $$n$$ people selects their own hat is

$$1/2! - 1/3! + 1/4! - ... + (-1)^n/n!$$

The formula aligns with what one could derive by using derangements.

I try to compute it for $$n = 3$$.

Let $$E_i$$ be the event that the $$i$$th person picks the wrong hat and $$E_{ij}$$ be the event that the $$i$$th person picks the wrong hat by picking the $$j$$th person's hat.

We are looking for $$P(E_1 \cap E_2 \cap E_3)$$.

We know $$P(E_1 \cap E_2 \cap E_3)$$ = $$P(E_1) * P(E_2|E_1) * P(E_3|E_1 \cap E_2)$$.

We have:

$$P(E_1) = 2/3$$

$$P(E_2|E_1) = P(E_2 \cap E_1)/P(E_1)$$

[Letting P(E_ij) be the probability that the ith person wrongly picks the jth person's hat.]

Then, $$P(E_2 \cap E_1) = P(E_2 \cap (E_{12} \cup E_{13}))$$ $$= P((E_2 \cap E_{12}) \cup (E_2 \cap E_{13}))$$ $$= P((E_2 \cap E_{12})) + P((E_2 \cap E_{13})) - P((E_2 \cap E_{12}) \cap (E_2 \cap E_{13}))$$ $$= P((E_2 \cap E_{12})) + P((E_2 \cap E_{13}))$$ $$= P(E_{12}) * P(E_2) + P(E_{13}) *P(E_2)$$ $$= 1/3 * 1 + 1/3 *1/2$$ $$= 1/3 + 1/6$$ $$= 1/2$$

As a result, $$P(E_2 | E_1) = P(E_2 \cap E_1)/P(E_1) = 1/2 * 3/2 = 3/4$$.

Of course, $$P(E_3|E_1 \cap E_2) = 1$$.

Finally, this leads to $$P(E_1 \cap E_2 \cap E_3) = 2/3 * 3/4 * 1 = 1/2$$.

But according to the formula, $$P(E_1 \cap E_2 \cap E_3) = 1/3$$, which is right and can be arrived at via going to complement route, i.e. by finding the probability that at least 1 person picks the right hat and subtracting that from 1.

Can someone help in pointing out where I am going wrong in the derivation above?

EDIT:

As pointed out by the comment, the issue is in computing $$P(E_3|E_1 \cap E_2)$$.

Here, person 1 can pick 2's hat and 2 picks 1's hat, then 3 gets their hat for sure.

Then, $$P(E_3|E_1 \cap E_2) = 1 - P(E_{33}|E_{12} \cap E_{21})$$.

Note that $$P(E_{33}|E_{12} \cap E_{21}) = (1/3 * 1/3 * 1/3)/(1/3 * 1/3)$$.

As a result, $$P(E_3|E_1 \cap E_2) = 1 - 1/3 = 2/3$$.

Then, we match the formula perfectly.

$$P(E_3\mid E_1\cap E_2)$$ is not $$1$$. If people $$1$$ and $$2$$ both get the wrong hat, one possibility is that they got each other's: in which case, person $$3$$ does not get the wrong hat.

Of course, $$P(E_3|E_1 \cap E_2) = 1$$.

This is not true.

Suppose $$E_{12}$$ and $$E_{21}$$. Then $$E_1 \cap E_2$$ has occurred, but person $$3$$ must pick their own hat and therefore $$E_3$$ does not occur.

In fact, the probabilities of the subcases of $$E_1 \cap E_2$$ are:

$$P(E_{12} \cap E_{21}) = \frac16$$

$$P(E_{12} \cap E_{23}) = \frac16$$

$$P(E_{13} \cap E_{21}) = \frac16$$

$$E_3$$ occurs only in the last two cases, so $$P(E_3|E_1 \cap E_2) = \dfrac23$$ and therefore

$$P(E_1 \cap E_2 \cap E_3) = \frac23\cdot\frac34\cdot\frac23 = \frac13.$$