# The Classic Matching Problem in Probability

I have some questions about the solution to this problem for $n=3$. The problem goes:

"Suppose that each of three men at a party throws his hat into the center of the room. The hats are first mixed up and then each man randomly selects a hat. What is the probability that none of the three men selects his own hat?"

One of the solutions reads Equation 1

$P($no man selects his hat$) = 1 - P($at least one man selects his own hat$) = 1 - P(E1∪E2∪E3)$

I am having a hard time understanding why

$P($at least one man selects his own hat$) = P(E1∪E2∪E3)$

I can understand the complement, basically if $E_i$ is the event that man $i$ picks his own hat, then we are looking for the complement of $\cap E_i$ which equals $\cup E_i^c$. However is the union of events to be used when we answer the question of at least one event occurring?

My second question is this:

while I was trying to solve this problem for $n=3$, I used the following reasoning:

$P($no man selects his hat $) = 1 - P(E_1) - P(E_1E_2) - P(E_1E_2E_3)$

where $E_1$ is the event that only one man picks his own hat $E_1E_2$ is the event that two men pick their own hat, and $E_1E_2E_3$ the event that all did.

In my computations, I ended up with $1/3$, which is the same probability we get if we use $\$ Equation 1. Is my reasoning correct?

• That looks like the number of derangement divided by all permutations. To put into a formula $$\frac{!n}{n!}~=~\sum_{k=0}^n \frac{(-1)^k}{k!}$$ In your case $n=3$. Derangements are permutations without fixed points (See en.wikipedia.org/wiki/Derangement). Commented Jul 23, 2018 at 23:16
• For your first question: Yes, when you consider the union of two elements $x,y$ as another way to say $x$ or $y$. In a context of probability this equals to that the union of events denotes that at least on event is occurring. For your second I want to clarify something: Do you want to verify the equation $P(E_1\cup E_2 \cup E_3)~=~P(E_1)+P(E_1\cap E_2)+P(E_1\cap E_2 \cap E_3)$? Commented Jul 23, 2018 at 23:49
• @mrtaurho, yes. Does the equation make sense?
– user529632
Commented Jul 24, 2018 at 0:28

You have to think about what kind of outcomes are possible when we say "at least one man selects his own hat." If $E_i$ represents the outcome that man $i$ selects his own hat, then $E_1 \cup E_2 \cup E_3$ includes the outcome where all three select their own hat; it also includes the outcome where exactly one man selects his own hat. Note it is impossible for exactly two men to select their own hat--since if this happens, the remaining hat is necessarily selected by its owner. So it just so happens in this case that \begin{align*} \Pr[E_1 \cup E_2 \cup E_3] &= \Pr[E_1 \cap \bar E_2 \cap \bar E_3] + \Pr[\bar E_1 \cap E_2 \cap \bar E_3] + \Pr[\bar E_1 \cap \bar E_2 \cap E_3] \\ &\quad + \Pr[E_1 \cap E_2 \cap E_3]. \end{align*} I recommend that you draw a Venn diagram to understand this.
In regard to your second question, you are being sloppy with your notation, and as a result, you are not enumerating all of the relevant outcomes. Your calculation worked only because of coincidence. A correct calculation requires you to consider the outcomes of all three men's selections, so if you write $\Pr[E_1]$, this is just the unconditional probability of the first man selecting his own hat, which is $1/3$. But this probability also counts the event where all three men select their own hat, since $$E_1 \cap E_2 \cap E_3 \subset E_1.$$