7
$\begingroup$

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.

$\endgroup$

2 Answers 2

12
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .