Intereting Posts

An Alternative Definition of Reductive Lie Algebra?
Proof of the Sherman-Morrison Formula
Calculate coordinate of any point on triangle in 3D plane
What are the Laws of Rational Exponents?
constructing a genus 2 surface from 8-gon
Continuity of the inverse matrix function
How can I find $\lim_{n\to \infty} a_n$
Maximum value of the modulus of a holomorphic function
Divisor of meromorphic section of point bundle over a Riemann surface
In a finite field product of non-square elements is a square
Showing the square of a Markov process is or isn't Markov
Aftermath of the incompletness theorem proof
help me understand derivatives and their purpose
Ring of analytic functions
Unique Stationary Distribution for Reducible Markov Chain

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.

- How many tries to get at least k successes?
- How many solutions are there to the equation $x + y + z + w = 17$?
- Sum of the series $\binom{n}{0}-\binom{n-1}{1}+\binom{n-2}{2}-\binom{n-3}{3}+…$
- Deriving the formula for the Möbius function?
- Count the number of n-bit strings with an even number of zeros.
- (Olympiad) Minimum number of pairs of friends.

-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?

- Transforming a latin square into a sudoku
- What is the expected value of the number of anchors of $S$?
- How many of all cube's edges 3-colorings have exactly 4 edges for each color?
- What is the probability of randomly selecting $ n $ natural numbers, all pairwise coprime?
- Maximum number of edges in a simple graph?
- Sum of Cauchy distributed random variables
- Number of inversions
- Jointly continuous random variables
- Ordered set partitions
- Edge coloring of the cube

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.

- Finding the remainder of $11^{2013}$ divided by $61$
- A pathological example of a differentiable function whose derivative is not integrable
- How do I get the existence of a set in ZFC following Jech?
- Action of $G/H$ on $H_n(H;M)$
- Lebesgue measure, Borel sets and Axiom of choice
- Is composition of covering maps covering map?
- 6/2*(1+2) is 1 or 9?
- A valid proof for the invariance of domain theorem?
- Finding $\binom{999}{0}-\binom{999}{2}+\binom{999}{4}-\binom{999}{6}+\cdots +\binom{999}{996}-\binom{999}{998}$
- Binary matrices and probability
- Computing: $\lim\limits_{n\to\infty}\left(\prod\limits_{k=1}^{n} \binom{n}{k}\right)^\frac{1}{n}$
- Solve the following differential equation: $ty' + 2y = \sin(t)$
- Hartshorne Exercise II. 3.19 (b)
- Need help finding limit $\lim \limits_{x\to \infty}\left(\frac{x}{x-1}\right)^{2x+1}$
- “Probability” of a map being surjective