# What's the 'extra man' in the matching problem in Ross?

Below is the beginning of an example in Ross' First Course in Probability (p.97):

EXAMPLE 5d

At a party, n men take off their hats. The hats are then mixed up, and each man randomly selects one. We say that a match occurs if a man selects his own hat. What is the probability of no matches?

Solution.

Let E denote the event that no matches occur, and to make explicit the dependence on n, write $P_n$ = P(E). We start by conditioning on whether or not first man selects his own hat—call these events M and $M^c$, respectively. Then $P_n$ = P(E) = P(E|M)P(M) + P(E|$M^c$)P($M^c$)

Clearly, P(E|M) = 0, so $P_n$ = P(E|$M^c$)$\frac{n − 1}{n}$

I understand that first part perfectly, now the next part confuses me.

Now, P(E|$M^c$) is the probability of no matches when n − 1 men select from a set of n − 1 hats that does not contain the hat of one of these men. This can happen in either of two mutually exclusive ways: Either there are no matches and the extra man does not select the extra hat (this being the hat of the man who chose first), or there are no matches and the extra man does select the extra hat. The probability of the first of these events is just $P_{n−1}$, which is seen by regarding the extra hat as “belonging” to the extra man. Because the second event has probability $\frac{1}{n − 1} P_{n−2}$, we have P(E|$M^c$) = $P_{n−1} + \frac{1}{n − 1}P_{n−2}$.

I'm not sure what Ross is referring to when he says the extra man. It seems like the extra hat is the hat of the man who chose first. If someone could please clarify how Ross obtained this last equation, I would be grateful. Thanks.

Suppose there are four men $A,B,C,D$ with their hats $a,b,c,d$.
The first part considered two cases: $A$ chooses $a$ or else.

When $A$ chooses $a$, $p(E|M)=0$.
So $P_n = p(E|M^c)p(M^c) = p(E|M^c)\frac{n-1}{n}$.

For the second part, we are concerning only the case when $A$ has not chosen hat $a$. Suppose $A$ has chosen $b$, then there are three men and three hats remaining, namely $B,C,D$ and $a,c,d$.
Since there are only two matching pairs left ($C,c$ and $D,d$), so I guess the extra man refers to $B$ and the extra hat refers to $a$.

The second case is straight forward, if

the extra man does select the extra hat


that is, $B$ selects $a$ (which is of probability $\frac{1}{n-1}$), then there are $n-2$ matching pairs left ($C,c$ and $D,d$ in this case). So the probability of this case is $\frac{1}{n-1}P_{n-2}$.

If

the extra man does not select the extra hat


that is, $B$ does not select $a$ (which is of probability $\frac{n-2}{n-1}$), considering

regarding the extra hat as “belonging” to the extra man


the probability of this case is $p(\hat{E}|M^c)\frac{n-2}{n-1}=P_{n-1}$.

Therefore we have $p(E|M^c)=P_{n-1}+\frac{1}{n-1}P_{n-2}$.

A permutation with no matches is also known as a derangement.

Simply put, whenever Ross uses the term "extra," he is referring to either a man or a hat that has not yet been paired up, but any pairing that remains possible is guaranteed to not result in that man receiving his own hat.

So, up to the first part that you say you understand, if the first man does not choose his own hat, then he has chosen someone else's hat. In that case, his own hat remains among the $n-1$ left over hats, and his hat is "extra"--no matter who chooses it, it will not result in a pairing of a hat and its owner, because its owner already chose a different hat.

Similarly, after the first man's choice of a hat that is not his, there must be an "extra" man, who, for any remaining hat that he receives, is guaranteed to not receive his own. Who is this man? He is the man whose hat the first man received.

I am only explaining the second part which is not clear from other answers.Hope this is clear.

Extra is referred to man or hat whose pair is not present in the selection, once first man has made the selection. This leads to two cases :-

1. Extra man doesn't choose the extra hat- Here he is having same choices compared other men where he can't choose this extra hat and for other men, they can't choose their own hat which is leading to similar situation having n-1 men having no man can choose their hat.

2. Extra man does choose the extra hat - Probability of choosing the extra hat is 1/(n-1) for extra man and having done that we are now left with n-2 men leading to similar situation having n-2 men situation.