You're mad! Lunatic! Deranged!

Probability Level 3

Let $P(n)$ be the probability that a random permutation of $n$ distinct elements have no element in their original position.

Find $\lim_{n \rightarrow \infty} P(n)$

The answer is 0.36787944.

1 solution

Jake Lai
Dec 23, 2014

It is known that there are $\displaystyle \sum_{k=0}^{n} \frac{n!(-1)^{k}}{k!}$ derangements of a set of $n$ elements out of a total of $n!$ permutations.

Hence,

$\displaystyle P(n) = \frac{1}{n!} \sum_{k=0}^{n} \frac{n!(-1)^{k}}{k!} = \sum_{k=0}^{n} \frac{(-1)^{k}}{k!}$

Using the fact that $\displaystyle \sum_{k=0}^{\infty} \frac{x^{k}}{k!} = e^{x}$ ,

$\lim_{n \rightarrow \infty} P(n) = \sum_{k=0}^{\infty} \frac{(-1)^{k}}{k!} = \boxed{e^{-1} \approx 0.3678}$

Very nice problem! It's amazing how often $e$ appears in probability.

Michael Ng - 6 years, 5 months ago

Indeed! I was doing a maths project recently on the secretary problem and there it was, appearing from simple probabilistic settings. I should post a problem on stopping at the nth best candidate, actually - that'll be soon.

Jake Lai - 6 years, 5 months ago

A rather quick approach to the problem would be to use the identity $!n=\left \lfloor \dfrac{n!}{e}+\dfrac{1}{2} \right \rfloor~,~n\geq1$ and neglect the floor function and the value $\dfrac{1}{2}$ while evaluating the limit since, in the limit , we have $n\to \infty$ and neglecting those considerations in the identity won't affect the limit much and we can get an approximation quicker this way. So,

$\displaystyle \lim_{n\to \infty}P(n)= \lim_{n\to \infty}\dfrac{!n}{n!}\approx \lim_{n\to \infty} \dfrac{n!}{n!\cdot e} \approx e^{-1} \approx \boxed{0.3678}$

Prasun Biswas - 6 years, 5 months ago

You're mad! Lunatic! Deranged!

The answer is 0.36787944.

1 solution

0 pending reports