Basic Probability Question Conditional Probability

Question

There are three men at a party, and each throws their hat in the middle. The hats are mixed up, and then each man randomly selects a hat. What is the probability that none of the three men winds up with his own hat?

I have solved this question by first finding the probability that at least one of three of the men wind up with their own hat, and then subtracting the value from 1.

Let $E_1$, $E_2$, $E_3$ denote the events that each man finds his own hat. $P(E_1E_2E_3)$ is total probability of each man finding his own hat

$$P(E_i) = \frac{1}{3}, \quad i=1,2,3$$ $$P(E_iE_j) = \frac{1}{6}, \quad i \neq j$$ $$P(E_1E_2E_3) = \frac{1}{6}$$

$$P(E_1 \cup E_2 \cup E_3) = P(E_1) + P(E_2) + P(E_3) - P(E_1E_2) - P(E_1E_3) - P(E_2E_3) + P(E_1E_2E_3)$$ $$\therefore P(E_1 \cup E_2 \cup E_3) = 1 - \frac{1}{2} + \frac{1}{6} = \frac{2}{3}$$ $$1 - \frac{2}{3} = \frac{1}{3}$$

This makes sense, however I wanted to see if I could find the same answer by letting $E_1$, $E_2$, $E_3$ denote the events that each man does not find his own hat.

$$P(E_i) = \frac{2}{3}, \quad i=1,2,3$$ $$P(E_iE_j) = \frac{2}{6}, \quad i \neq j$$ $$P(E_1E_2E_3) = \frac{2}{6}$$

$$P(E_1 \cup E_2 \cup E_3) = 2 - 1 + \frac{2}{6} = 1\frac{2}{6}$$

This is obviously wrong, so what am I missing?

Edit: I think I got my problem. The first man may select the second man's hat, so the probability of $P(E_iE_j)$ is not necessarily equal to $\frac{2}{6}$

Edit: I know what the mistake was, I will add it here to help anyone else who may want to see.

The first man has a $\frac{2}{3}$ probability of choosing a hat that is not his, hat 2 or hat 3.

Case 1 If he chooses hat 2, then the second man will have to choose between hat 1 and hat 3. In order to ensure that all 3 men get the wrong hat, he only has a $\frac{1}{2}$ probability. The third man will have a probability of 1 since he has only one choice. This means that the probability for case 1 is $\frac{1}{3}\frac{1}{2}=\frac{1}{6}$

Case 2 Similarly, if the first man chooses hat 3, the second man will have a choice between hat 2 and hat 1, and to ensure all three men get the wrong hat, he again has a probability of $\frac{1}{2}$. Man 3 has no choice and has a probability of 1. So the probability is $\frac{1}{3}\frac{1}{2}=\frac{1}{6}$

Adding these two probabilities together, we get a total probability of $\frac{1}{3}$.

Answer 1

Your edit seems like a valid solution. For larger values of $n$, the computation gets much trickier.

In general, if we have $n$ hats, the probability that no one gets their own hat can be obtained in many ways. Two such methods are to take

$$\sum_{i=0}^{n} {(-1)^i}\cdot{\frac{1}{i!}}$$

In our case, $n$ is $3$ so we get

$$\sum_{i=0}^{3} {(-1)^i}\cdot{\frac{1}{i!}}=1-1+{\frac{1}{2}}-{\frac{1}{6}}={\frac{1}{3}}$$

Alternatively, this probability can be obtained by

$$\frac{[\frac{n!}{e}]}{n!}$$

where $[\frac{n!}{e}]$ is the closest integer to $\frac{n!}{e}$

In our case, $n$ is $3$ so we get

$$\frac{[\frac{3!}{e}]}{3!} = {\frac{[2.207]}{6}}={\frac{1}{3}}$$

Finally, as $n \rightarrow \infty$ the probability that no one gets their own hat approaches $\frac{1}{e}$ and it approaches this quite quickly.

Consider $n=9$. Then $$\frac{[\frac{9!}{e}]}{9!} \approx .3678792 \approx \frac{1}{e} \approx .3678794$$