The hat-matching problem, probability of at least $k$ matches

533 Views Asked by At

the setup: $N$ people arrive at a party all of whom are wearing hats. We collect all the hats and then redistribute them. What is the probability that at least $k$ of the party members receive their own hats back?

There are a total of $\binom{N}{k}$ number of ways to make a subset of $k$ people out of these $N$ people. let's label each of these $\binom{N}{k}$ subsets with a unique number between $1$ to $\binom{N}{k}$, arbitrarily. let $\space T_i \space$ be the event that all people in the subset labeled $i$ have received their own hats back.

Then, the probability that at least $k$ people receive their own hats back is $$P(\bigcup\limits_{i=1}^{\binom{N}{k}} T_{i}) = \sum_{i=1}^{\binom{N}{k}} P(T_{i}) - \sum_{i_1 < i_2}P(T_{i_1}T_{i_2}) + \dots + (-1)^{n+1}\sum_{i_1 < i_2<\dots<i_n}P(T_{i_1}T_{i_2}\dots T_{i_n}) + \dots + (-1)^{\binom{N}{k}+1}P(T_{1}T_{2}\dots T_{\binom{N}{k}})$$

question1: is this correct? is there any way to take this calculation forward?

question2: is there a simpler way to find the probability that at least $k$ people receive their own hats back
(other than $\sum_{i=k}^N\text{probability that at exactly k people receive their own hats back}$,
where the probability that exactly k people receive their own hats back is $\frac{\binom{N}{k} D_{N - k}}{N!}$, where $D_n = n! \cdot \sum_{i=0}^{n}\frac{(-1)^i}{i!}$)

1

There are 1 best solutions below

3
On

I think you can get a pretty straightforward answer by modifying @Brian M. Scott 's answer in your other question(the one linked to this post) for exactly $k$ people.

Suppose that we’ve put aside a set $S$ of $k$ men who are to get their own hats back; there are $(N-k)$! permutations that return their own hats to all $k$ of the men in $S$ (and possibly others as well). Let $T$ be the set consisting of the remaining $N-k$ men, and for each $i\in T$ let $A_i$ be the set of permutations also giving $i$ his own hat back. To get the number of permutations that return their own hats only to the $k$ men in $S$, we need to subtract $∣\cup_{i\in T} A_i∣$, and that’s exactly what we’ve done.

Since we don't care for only but for at least there's no need to subtract. So, there $(N-k)!$ permutations for at least $k$ in a given set of size $k$, $N\choose k$ ways to pick such a set and we need to divide by the total number of permutations, that is $N!$ to find the propability. Putting all together,

$$ p = \frac{(N-k)! {{N}\choose k}}{N!} = \frac{1}{k!}$$

Edit: Apparently, that is wrong since for $k=1$ the probability can't always be equal to 1. I think the correct answer is $ p = \frac{(N-k)!} {N!}$ because we don't care about defining the set since we don't subtract but this is not a solid proof.