6
$\begingroup$

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.

Improve this question
$\endgroup$
1

4 Answers 4

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

Let us have n men corresponding to which there exist n hats. A match is said to occur if a man wears his own hat.

A Match occurs if $Man_{i}$ wears $Hat_{i}$ , $Man_{j}$ wears $Hat_{j}$. Let us denote this event as $E_{i}$ .

A NO Match occurs if $Man_{i}$ wears $Hat_{j}$ , $Man_{j}$ wears $Hat_{i}$. Let us denote this event as $\overline{E_{i}}$ .

$E_{i}$ : Denote the Event where that the ith object occupies the ith position corresponding to its number. Then, the probability 'p' that P(None of the objects occupies the place corresponding to its number) = P( No man wears his own Hat) is given by : $ p = P(\overline{E1} \cap \overline{E2} \cap \overline{E3}.... \cap \overline{En} ) = 1 - P(\text{Atleast one of the objects occupies the place corresponding to its number})= 1 - P(\text{Atleast one Man is wearing his own Hat})= 1 - P(E1 \cup E2\cup E3.... \cup En) = 1 - [\sum_{i=1 }^{n}P(E_{i}) - \sum_{i=1 }^{n}\sum_{j=1 }^{n}P(E_{i} \cap E_{j})....+(-1)^{n-1}P(E_{1} \cap E_{2}\cap E_{3}....... \cap E_{n}) ]= 1 - [\frac{\binom{n}{1}}{n} - \frac{\binom{n}{2}}{n(n-1)} + \frac{\binom{n}{3}}{n(n-1)(n-2)} - ..... + \frac{(-1)^{n-1}}{n(n-1)(n-2)...3.2.1} ] = 1- [ 1- \frac{1}{2!} + \frac{1}{3!}-...+\frac{^{(-1)^{(n-1)}}}{n!}]= \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - ........ + \frac{(-1)^{(n)}}{n!} = \sum_{k = 0 }^{n}\frac{(-1)^{k}}{k!}$ ......................................................................

But for large n :

p = $1-1 + \frac{1}{2!} + \frac{1}{3!} + \frac{1}{4!} - ........... = e^{-1}$

And, the Probability of Atleast One match : $1 - p = (1-e^{-1})$

.........................................................................

Therefore, P(None of the Men are wearing their own Hat ) = P(No Matches) = $\sum_{k = 0 }^{n}\frac{(-1)^{k}}{k!}$

This problem is a University level question and This is the verified answer.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.