# Answer: Probability No Man Gets His Own Hat in Hat Matching Problem

• hotvette
In summary, the probability that no man gets his own hat, is$$P_0 = \frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \cdots + (-1)^N \frac{1}{N!},$$which is what you already have.
hotvette
Homework Helper

## Homework Statement

N men throw their hats on to the floor, mix them up, and draw at random. What is the probability that no man gets his own hat

## Homework Equations

$$P(E_1^c E_2^c \dots E_N^c) = 1-P(E_1 \cup E_2 \dots \cup E_N)$$
$$P(\text{n-tuple}) = \frac{1}{n!}$$

## The Attempt at a Solution

The way I've seen this explained appears to me to have an inconsistency that I don't know how to resolve.

1). Total # arrangements of N hats among N men is $N!$ This is the denominator in the probability expression.

2). Define $E_i$ as the event that n=1 man chooses his own hat. Imagine man #1 choosing a hat first. There is only 1 way he can choose his own hat. The remaining $(N-1)$ hats can be arranged $(N-1)!$ ways. But, since each man can choose first, we must multiply by $C_1^N = N$. Thus $P(E_1) = P(E_2) \dots = P_N) = N (N-1)!/N! = 1 = \frac{1}{n!}$

3) Same argument for k=2, k=3, etc. gives the result stated above.

Here is what doesn't make sense to me. If we argue that there are N ways that a man can choose first, that implies order of choosing is important. If order is important, then the order of choosing 2nd, 3rd, etc. is also important, which isn't accounted for in the above argument.

What am I missing?

hotvette said:

## Homework Statement

N men throw their hats on to the floor, mix them up, and draw at random. What is the probability that no man gets his own hat

## Homework Equations

$$P(E_1^c E_2^c \dots E_N^c) = 1-P(E_1 \cup E_2 \dots \cup E_N)$$
$$P(\text{n-tuple}) = \frac{1}{n!}$$

## The Attempt at a Solution

The way I've seen this explained appears to me to have an inconsistency that I don't know how to resolve.

1). Total # arrangements of N hats among N men is $N!$ This is the denominator in the probability expression.

2). Define $E_i$ as the event that n=1 man chooses his own hat. Imagine man #1 choosing a hat first. There is only 1 way he can choose his own hat. The remaining $(N-1)$ hats can be arranged $(N-1)!$ ways. But, since each man can choose first, we must multiply by $C_1^N = N$. Thus $P(E_1) = P(E_2) \dots = P_N) = N (N-1)!/N! = 1 = \frac{1}{n!}$

3) Same argument for k=2, k=3, etc. gives the result stated above.

Here is what doesn't make sense to me. If we argue that there are N ways that a man can choose first, that implies order of choosing is important. If order is important, then the order of choosing 2nd, 3rd, etc. is also important, which isn't accounted for in the above argument.

What am I missing?

You are confusing yourself by supposing a particular order for choosing. The probability that man i chooses his own hat is ##P(E_i) = 1/N## for all ##i = 1,2 \cdots, N.## The easiest and surest way to see this is similar to what you did: among all the ##N!## permutations, hat number ##i## falls in position ##i## in ##(N-1)!## of the cases, so ##P(E_i) = (N-1)!/N! = 1/N.## Of course we have that that ##\sum_{i=1}^N P(E_i) = 1##, but that is only a small first step towards the probability that at least one man gets his own hat. Note that the occurrence of event ##E_i## says nothing at all about whether some other men also get their own hats; it just looks at what happens to man ##i##.

Next, for any fixed pair ##i < j##, the number of permutations in which hat ##i## falls in position ##i## and hat ##j## in position ##j## is ##(N-2)!##, so ##P(E_i, E_j) = (N-2)!/N! = 1/[N(N-1)].## Thus, ##\sum_{i < j} P(E_i,E_j) = {N \choose 2}/[N(N-1)] = 1/2! .## (Here I use the notation ##P(A,B)## instead of ##P(A \cap B) .##) Similarly, ##\sum_{i < j < k} P(E_i, E_j, E_k) = 1/3!##, etc.

Now use the general inclusion-exclusion principle to get ##P_{\geq 1}## =probability that at least one man gets his own hat:
$$P_{\geq 1} \equiv P(E_1 \cup E_2 \cup \cdots \cup E_N) = S_1 - S_2 + S_3 - \cdots \pm S_N,$$
where
$$S_1 = \sum_{i} P(E_i)=1,\\ S_2 = \sum_{i < j} P(E_i, E_j)=1/2!, \\ S_3 = \sum_{i < j < k} P(E_i,E_j,E_k)= 1/3!\\ \vdots\\ S_N = P(E_1,E_2, \ldots, E_N) = 1/N!$$
Of course, the probability that 0 men get their own hats is ##P_0 = 1 - P_{\geq 1} .##

All of this stuff is presented beautifully in Feller, "An Introduction to Probability Theory and its Applications", Vol. I, Wiley (1968). That treatment is now considered old-fashioned, but in my opinion is still the clearest and most direct.

Last edited:

## 1. What is the "Hat Matching Problem" in probability?

The Hat Matching Problem is a probability problem in which a group of people each randomly select a hat from a pile of hats. The goal is for each person to get their own hat back. However, the hats are identical and there is no way to tell them apart, making it a challenging probability problem.

## 2. What is the probability that no one gets their own hat back in the Hat Matching Problem?

The probability of no one getting their own hat back in the Hat Matching Problem is 1/n, where n is the number of people in the group. This means that as the number of people increases, the probability of no one getting their own hat back decreases.

## 3. How does the number of people in the group affect the probability in the Hat Matching Problem?

The number of people in the group directly affects the probability in the Hat Matching Problem. As the number of people increases, the probability of no one getting their own hat back decreases. This is because there are more possible combinations of hats for the people to choose from, increasing the likelihood that at least one person will get their own hat back.

## 4. Is the Hat Matching Problem a real-life scenario?

The Hat Matching Problem is a hypothetical scenario used to demonstrate the concept of probability. While it may not occur in real life with hats, it can be applied to other situations where there is a random selection and matching process, such as drawing names for a gift exchange.

## 5. What are some strategies for solving the Hat Matching Problem?

There are a few strategies that can be used to solve the Hat Matching Problem, including assigning numbers to the hats and having each person choose a specific number, or having each person select a hat at random and then trading with others until they have their own hat. However, these strategies may not guarantee a solution and the best approach is to understand the probability and likelihood of success in the problem.

• Calculus and Beyond Homework Help
Replies
3
Views
891
• Quantum Interpretations and Foundations
Replies
47
Views
2K
Replies
2
Views
447
• Calculus and Beyond Homework Help
Replies
5
Views
2K
• Quantum Physics
Replies
2
Views
1K
• Calculus and Beyond Homework Help
Replies
5
Views
2K
• Atomic and Condensed Matter
Replies
1
Views
1K
Replies
24
Views
2K
• Calculus and Beyond Homework Help
Replies
1
Views
2K