# Probability matching problem

Arriving at party n guests throw their hats into pile. When they leave they each take a hat that is chosen randomly from the pile. We want to compute the probability of the event $A$ that at least one guest leaves with their own hat.

1. Describe a sample space that can be used to model this experiment. How many sample points belong to it? For $k= 1;2;:::n,$ let $A_k$ be the event that the $k$th guest goes home with their own hat. Which sample points belong to $Ak$, and how many are of them are there?
2. Write $A$ in terms of the events $A_k$ and hence compute its probability ( assuming outcomes are equally likely).
3. What is the probability that exactly r guests leave with their own hat.

For (1) I simply said let $X =\{ 1,2,3....n \}$ where each element is the guest numebered from $1$ to $n$ uniquely and define $f:X\rightarrow X$ where $f(i)=j$ would mean $i$'th person got $j$'s hat for $i,j \in X$.

The sample space will be the set of all bijections from $X$ to $X$ and it will have $n!$ sample points.

$k$th person goes home with his own hat would be sample points s.t. $f(k)=k$ for $k\in X$ . There are n sample points ( best case everyone gets his own hat).

(2) I said $A= \bigcup_{k=1}^{n} A_k$ but I don't know how to calculate the probability. Any help please with this and third part?

## 1 Answer

Hint: For ii, look up derangements. For iii, choose $r$ guests to get their own hat, then you need a derangement of the rest.

• It gives the formula $!n$ for derangements, the derivation of which I don't quite understand. Is it the only way to solve? we have not covered derangements yet. If so $!n$ gives the probability that no one gets his/her hat. What should I do for at least one getting it? Is it 1-!n ?? – John Smith Jan 22 '14 at 16:31
• That is correct for at least one. You have $!n=\frac {n!}e$, rounded to the nearest integer. – Ross Millikan Jan 22 '14 at 16:36
• Hmm ok thanks. I have to read derangements carefuly then. I was hoping there'd be a way using inclusion-exclusion or something. – John Smith Jan 22 '14 at 16:40