[Math] Probability matching problem

combinatoricsprobability

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?

Best 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.

Related Question