You are given N addressed letters and N addressed envelopes. If you randomly put one letter in each envelope, what is the probability that no letter ends up in the correct envelope?

In other words, what is the probability that at least one letter is in the correct envelope? The order of placement is significant, as it affects the availability of subsequent positions; however, all letters are equally likely to be assigned. This process can be thought of as a loop or a circle. Therefore,

The overall probability of a given letter (for instance, the first letter) being correctly matched with its corresponding envelope is \(P=\frac{1}{N}\)

Consequently, the probability that no letter is placed in the correct envelope is \(P'=(1-\frac{1}{N})^N \approx \frac{1}{e}\)

when N is large the correlation between the letters can be negelected.

Let L(i) and E(i) denote the i th letter and corresponding i th envelope

The letter L(a1) will in some envelope E(a2), etc.Eventually, one of the envelopes must be E(a1), let it be E(a1’). We can say that L(a1) in a “loop” of length n. If L(a1) ends up in its own envelope, then n=1. If no letter ends up in the correct envelope, then the n could take on any values from 2 to N.

The probability that L(a1) belongs to a loop of length n is

\[\frac{N-1}{N}\frac{N-2}{N-1}...\frac{N-(n-1)}{N-(n-2)}\frac{1}{N-(n-1)}=\frac{1}{N}\]

When n=1, the probability is 1/N. For n>1, L(a1) is not in E(a1) but in a random envelope E(a2), where L(a2) is also not in E(a1), and so forth. Ultimately, L(an) must be in E(a1). To derive P(N), we can manipulate the previous values of P(N-?). For L(a1) to be part of the case P(N-2), it must increase the loop length by 2. In the case of P(N-1), the loop length increases by only 1, which does not yield a logical outcome.

\[P_N=\frac{1}{N}(P_{N-2}+P_{N-3}+...+P_1+P_0)\]

This provides us with the recurrence relation: \(NP_N-(N-1)P_{N-1}=P_{N-2}\)

Let B(N) denote the number of “bad” arrangements where non of the N letters end up in the correct envelop. One step to get all the possible outcomes. \(B_{N+1}=N(B_N+B_{N-1})\)

Since there are N! possible arrangements involving N letters \(B_N=N!P_N\) \((N+1)!P_{N+1}=N(N!P_{N}+(N-1)!P_{N-1})\) \((N+1)P_{N+1}=NP_N+P_{N-1}\)

\[P_{N+1}-P_N=-\frac{1}{N+1}(P_N-P_{N-1})\]

Since, P(1)=0, P(2)=1/2, easy to get \(P_k-P_{k-1}=(-1)^k/k!\) \(P_N=P_1+\sum_{k=2}^N (P_k-P_{k-1})=\sum_{k=0}^N \frac{(-1)^k}{k!}\) This is the partial series expansion for 1/e

What is the probability that exactly m out of N letters end up in the correct envelopes?

  • Select m letters to be placed in the correct envelopes.
  • Consider the remaining N-m letters being placed in incorrect envelopes.
\[P_N^m=(C_N^m \frac{1}{N}\frac{1}{N-1}\frac{1}{N-2}...\frac{1}{N-m+1})P_{N-m}^0=\frac{1}{m!}P_{N-m}\approx \frac{1}{m! e}\]

check the probability properly sum to 1 \(\sum_{m=0}^N P_N^m=\sum_{m=0}^N \sum_{k=0}^{N-m}\frac{1}{m!}\frac{(-1)^k}{k!}\)

binary distribution \(\sum_{m=0}^{m+k}\frac{1^{m}}{m!}\frac{(-1)^k}{k!}\times (m+k)!=(1-1)^{m+k}\)