Why is the Derangement Probability so Close to $\frac{1}{e}$?

A derangement is a permutation $\sigma$ of $\{1,2,3,\dots,n\}$ such that $\sigma(i) \neq i$ for every $i$. A common application of inclusion/exclusion in undergraduate combinatorics and probability classes is to compute the number of derangements, and in the process show that the probability a random permutation is a derangement approaches $\frac{1}{e}$ for large $n$.

There's also a "standard" intuition for this probability, which goes roughly as follows: Let $E_i$ be the event that $\sigma(i)=i$.

1) For a given $i$, the probability of $E_i$ is exactly $\frac{1}{n}$.

2) If $n$ is large, than these events should be "nearly" independent ($E_i$ occurring means that $\sigma(i) \neq j$, making it a tiny bit more likely that $\sigma(j)=j$, but this shouldn't have much of an effect for large $n$), so we'd expect the probability none of the $E_i$ occur to be roughly $\left(1-\frac{1}{n}\right)^n$.

3) For large $n$, $\left(1-\frac{1}{n} \right)^n \approx \frac{1}{e}$.

Now the last approximation alone already has an error proportional to $\frac{1}{n}$. What's suprising then is that, after working through the inclusion/exclusion, you find that the probability is not just approximately $\frac{1}{e}$, but incredibly close -- the error is less than $\frac{1}{(n+1)!}$.

Is there some alternative intuitive explanation for the $\frac{1}{e}$ asymptotic probability that gives a sense of why the convergence is so fast?

Solution 1:

In fact a much stronger $e$-related statement is true: let $X_i$ denote the number of $i$-cycles in a random permutation on $n$ elements. Then for fixed $k$, as $n \to \infty$ the random variables $X_1, X_2, ... X_k$ are asymptotically independently Poisson with rates $1, \frac{1}{2}, ... \frac{1}{k}$. This observation about derangements is a special case applied to $X_1$. See this blog post for details, which proves this fact as a corollary of the exponential formula. The convergence rate is presumably also controlled by the exponential formula but I haven't worked out the details.

Solution 2:

Note: The convergence is so fast, because the derangement number $D_n$ and the Taylor series expansion of $e^x$ are closely related.

The intuition behind it is (for me) trying to develop a better feeling for the mechanism of the inclusion/exclusion principle, which encodes this relationship.

According to OPs referenced paper we know the derangement number $D_n$ is

\begin{align*} D_n=n!\sum_{j=0}^n(-1)^j\frac{1}{j!} \end{align*} Let's compare it with the Taylor expansion series of $e^x$ at $x=-1$ \begin{align*} \frac{1}{e}=\sum_{j=0}^\infty(-1)^j\frac{1}{j!} \end{align*}

Observe, that $\frac{D_n}{n!}$ is the $n$-th Taylor polynom of $\frac{1}{e}$.

We also note, that the series for $e^{-1}$ satifies the requirement of the alternating series test.

• The terms alternate in sign.

• They are decreasing in absolute value.

• They approach $0$.

Therefore applying the alternating series error test we obtain if we stop at the $n$-th term an absolute error less than the $(n+1)$-st term. So, the error is

\begin{align*} \left|\frac{D_n}{n!}-\frac{1}{e}\right|<\frac{1}{(n+1)!} \end{align*}

Note: This and the nice fact that $D_n$ is the nearest integer to $\frac{n!}{e}$ can be found e.g. in Stirling’s Approximation and Derangement Numbers by T. Zaslavsky

Solution 3:

I'm not sure this is really better than the inclusion exclusion, but it is different:

Let $d_n$ be the number of derangements. Then we have $$d_n = (n-1) (d_{n-1} + d_{n-2})$$ (see here). Let $p_n = d_n/n!$ be the probability of a derangement. Then $$p_n = \frac{n-1}{n} p_{n-1} + \frac{1}{n} p_{n-2} \ \mbox{which implies} \ p_{n} - p_{n-1} = - \frac{p_{n-1} - p_{n-2}}{n} .$$

So $p_{n} - p_{n-1}$ decays factorially fast, and thus $p_n = \sum_{m=2}^n (p_m - p_{m-1})$ is factorially close to $\sum_{m=2}^{\infty} (p_m - p_{m-1}) = \lim_{n \to \infty} p_n$.