$\frac{1}{e}=$"Probability that every chocolate goes into a wrong spot".

Question

While watching a video by Po Shen Loh I found something strange. In the video, he said that:

Suppose I have a box of chocolates having $100$ chocolates, and I drop them all on the ground, and then I try to put them all back in. What is the probability that every chocolate went back in a wrong spot?

According to him, the probability is $\frac{1}{e}$. Now the question is that how can we get that? To me, It is as interesting as Buffon's Needle problem, that is why I am eager to know the method to reach at $\frac{1}{e}$. I shall be thankful if you guys can provide me idea about what is happening.

Thanks

Answer 1

It is not exactly $\dfrac{1}{e}$. However the probability approaches $\dfrac{1}{e}$ as the number of chocolates tends to infinity.

What we are counting are the permutations over $\{1,..,n\}$ which do not a have a fixed point that is $\sigma(i)\not=i$ for every $i$. These are called derangements. The usual method for counting derangements is by using the inclusion-exclusion principle which gives that there are $$n!\sum_{i=0}^n\dfrac{(-1)^i}{i!}$$ derangements over $\{1,..,n\}$. Since there are a total of $n!$ permutations it means the probability for random permutation to be a derangement is $$\sum_{i=0}^n\dfrac{(-1)^i}{i!}$$ which tends to $\dfrac{1}{e}$ as $n\rightarrow\infty$ according to the formula $$e^x=\sum_{i=0}^{\infty}\dfrac{x^i}{i!}$$

Answer 2

You are interested in the number of Derangements of the set of $100$ chocolates.

In this answer, the number of Derangements of $n$ items is shown to be $$ \sum_{k=0}^n(-1)^k\frac{n!}{k!} $$ which is the closest integer to $\frac{n!}e$ for $n\ge1$. Since there are $n!$ ways to arrange the $n$ items, the probability of getting all objects into the wrong spot is $$ \sum_{k=0}^n(-1)^k\frac1{k!}\approx\frac1e $$ Note that this is approximate, it is not exactly $\frac1e$. By the Alternating Series Theorem, the error is less than $\frac1{(n+1)!}$ which is very small, but not $0$. For $n=100$, the error is less than $\frac1{101!}\approx1.06\times10^{-160}$. In particular:

$$ \begin{array}{r} \begin{array}{r}\scriptsize{p =0.3678794411714423215955237701614608674458111310317678345078368016974614957448998}\\ \scriptsize{03357147274345919643746627325276843995208246975792790129008626653589494098783092\color{#C00}{299}}\end{array}\\[12pt] \begin{array}{r}\scriptsize{\frac1e =0.3678794411714423215955237701614608674458111310317678345078368016974614957448998}\\ \scriptsize{03357147274345919643746627325276843995208246975792790129008626653589494098783092\color{#C00}{194}}\end{array} \end{array} $$