5

This is a textbook example and I am confused about the explanation. This question was asked by different people in stack-exchange already but I couldn't find the solution to my question.

Here's the problem:

At a party $n$ man take 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? What is the probability of exactly $k$ matches?

Solution (summarized):

$P_n = P(E) =$ the event that no matches occur, dependence on $n$,

$M =$ first man selects his own hat

$M^c=$ first man does not select his own hat

So, $P_n = P(E) = P(E|M)P(M) + P(E|M^c)P(M^c)$

Since $P(E|M) = 0$, we get $P(E)=P(E|M^c)* \frac{n-1}{n}$

Here's my question:

the solution says $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 that chose first), or there are no matches and the extra man does select the extra hat. Therefore, we get $P(E|M^c)= P(E|M^c)=P_{n−1}+ \frac{1}{n-1}*P_{n−2}$

What does the bolded part exactly mean?

  1. Who is the extra man? Is he the last person to choose the hat?

  2. If so, if the extra man does select the extra hat, shouldn't the probability of no matches be $0$.

  3. Can we do this question in a different way? like setting $X_i=$ the $i^{th}$ person selecting his hat, and the probability of no matches will be $P(\sum_{i=1}^n X_i = 0)$

N. F. Taussig
  • 76,571
Johnny Ton
  • 59

1 Answers1

3

After the first man takes a hat that is not his, here is what remains:

  • $n - 2$ hats belonging to men still in the room.
  • $n - 2$ men whose hats are still in the room.
  • One hat (the "extra" hat) that belonged to the first man (who is not in the room).
  • One man (the "extra" man) whose hat is no longer in the room because the first man took it.

The "extra" man is guaranteed not to get his own hat, since that hat is already taken. But we distinguish the case of where the "extra" man takes the first man's hat from the case where he takes one of the hats belonging to someone else still in the room.

For part 3, yes, that is exactly what you are evaluating when you solve this problem; the question is how to evaluate the sum. The best way to evaluate a sum is sometimes to find something else it is equal to and evaluate that thing instead.

For the formula that comes after the bold-font part of the solution, you probably already got the most obvious part, which is the event where the "extra" man gets the "extra" hat (probability $\frac{1}{n-1}$) and none of the other $n-2$ men get their own hats even though all the other $n-2$ hats belong to one of them ($P_{n-2}$).

Now for all the other ways every man could leave with someone else's hat, consider a case in which the "extra" man's hat is still in the room instead of the first man's hat. You can map every way of distributing the $n-1$ hats in that case to a way of distributing the $n-2$ "own" hats plus the "extra" hat: just replace the "extra" man's hat with the "extra" hat. This is a perfect one-to-one correspondence, so the probability that the "extra" man doesn't pick his own hat and that none of the other men pick their own hats in the $(n-2)$-"own"-plus-one-"extra" case is the same as the probability that nobody (including the "extra" man) picks his own hat in the $(n-1)$-"own" case, which is $P_{n-1}$.

There is nothing else to multiply by $P_{n-1}$ here because it's already exactly the probability of the event we're looking for. One of the events already accounted for in $P_{n-1}$ is the event that the "extra" man gets one of the $n-2$ hats belonging to the other $n-2$ men in the room.

You might think that you should consider separately each hat that the "extra" man might pick up and add the $n-2$ cases in which that hat is not the "extra" hat, but I think that is a more difficult way to solve the problem. It's simpler to use just two cases, either it's the "extra" hat or it's any of the hats that belong to someone still in the room.

David K
  • 98,388