# Check my answer: A slight modification to the 'hat-check' problem.

Suppose $n$ (hat wearing) people attended a meeting. Afterwards, everyone took a hat at random. On the way home, there is a probability $p$ that a person loses their hat (independent of whether other people did). What’s the probability that nobody got home with their own hat?

First of all, I’m not sure if I got the question right. The way I understand it, we’re interested in all of the following outcomes:

-Nobody got their own hat from the meeting. Then whether they lost it or not is irrelevant.

-Exactly one person got their own hat from the meeting but lost it on the way home.

-Exactly two people got their own hats from the meeting but lost it on the way home.

-…

-Everyone got their own hat from the meeting but they all lost it.

These events are disjoint so to get the probability of their union, I can just sum them up, right? So $P(A)=\sum_{i=0}^{n} P(B_i)p^i$, where $B_i$ is the event that exactly $i$ people got their hat from the meeting.

Therefore all that is left is to calculate $P(B_i)$. This is the amount of permutations with $i$ fixed points divided by total amount of permutations of an $n$-element set, so

$$P(B_i)=\frac{D_{n,i}}{n!}$$

where $D_{n,i}$ is the Rencontres number, $D_{n,i} = {n \choose i}D_{n-i,0}$, so

$$P(B_i)=\frac{D_{n,i}}{n!} = \frac{{n \choose i}(n-i)!\sum_{k=0}^{n-i}\frac{(-1)^k}{k!}}{n!} = \frac{1}{i!} \sum_{k=0}^{n-i}\frac{(-1)^k}{k!}.$$

Therefore,
$$P(A)=\sum_{i=0}^{n} P(B_i)p^i = \sum_{i=0}^{n} \left( \frac{1}{i!} \sum_{k=0}^{n-i}\frac{(-1)^k}{k!} \right) p^i = \sum_{i=0}^{n} \left( \frac{p^i}{i!} \left( \sum_{k=0}^{n-i}\frac{(-1)^k}{k!} \right) \right)$$

Now, is there any further way to simplify this? The answer I have says it’s supposed to approach $e^{-(1-p)}$, but I don’t really see it what with all the nested sums. In fact, is any of this even remotely correct?

#### Solutions Collecting From Web of "Check my answer: A slight modification to the 'hat-check' problem."

Well you are looking at the limit $$\lim_{n \to \infty} \sum_{i=0}^{n} \left( \frac{p^i}{i!} \left( \sum_{k=0}^{n-i}\frac{(-1)^k}{k!} \right) \right) \tag{1}$$

EDIT: As we know the limit of sums is the sum of limits and $(1)$ can be re-written as an infinite sum of limits $$\frac{p}{1!} \lim_{n \to \infty} \left( \sum_{k=0}^{n-1} \frac{-1^k}{k!} \right) + \frac{p^2}{2!} \lim_{n \to \infty} \left( \sum_{k=0}^{n-2} \frac{-1^k}{k!} \right) + \cdots \tag{2}$$

$(2)$ can be reduced by applying the limit and the infinite sum and can further be reduced

The inner sum converges to $e^{-1}$, according to $$e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \dots$$ with x = -1

The outer sum becomes $$\lim_{n \to \infty} \sum_{i=0}^{n} \left( \frac{p^i}{i!} e^{-1}\right) \tag{2}$$

and eventually as @vonbrand pointed out $e^{p-1}$

P.S. Im rather new to calculus, please do point out if any technical error.

The inner sum converges rapìdly to $e^{-1}$, if you substitute it by that constant, you are left with the outer sum, i.e. $e^p$, in all $e^{p – 1}$

The exponential generating function of permutations by fixed points is given by
$$G(z, u) = \exp \left(uz – z + \log \frac{1}{1-z} \right).$$
It follows that the probability generating function of the distribution of fixed points for $n$ fixed is given by
$$[z^n] G(z, u) = [z^n] \frac{1}{1-z} \exp((u-1)z).$$
Then the answer to the problem can be computed by calculating
$$[z^n] G(z, p) = [z^n] \frac{1}{1-z} \exp((p-1)z) = \sum_{k=0}^n \frac{(p-1)^k}{k!} \sim e^{(p-1)} = e^{-(1-p)}.$$
This is because $P[\mu = k|n] = [u^k z^n] G(z, u),$ where $\mu$ is the number of fixed points. Hence substituting $p$ for $u$ yields the probability that all the guests that had their hats in a permutation with $k$ fixed points (matching hats) subsequently lose them. Under this construction permutations with no fixed points in the first place contribute all of their probabilities, which is how it ought to be.