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?


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

  • $\begingroup$ 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 ?? $\endgroup$ – John Smith Jan 22 '14 at 16:31
  • $\begingroup$ That is correct for at least one. You have $!n=\frac {n!}e$, rounded to the nearest integer. $\endgroup$ – Ross Millikan Jan 22 '14 at 16:36
  • $\begingroup$ Hmm ok thanks. I have to read derangements carefuly then. I was hoping there'd be a way using inclusion-exclusion or something. $\endgroup$ – John Smith Jan 22 '14 at 16:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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