# Drunk Mail Man N letters to N Addresses

Suppose that $n$ different letters are sent to $n$ different addresses on the same street, one to each address. A drunk mailman randomly delivers the letters to the $n$ addresses on the street, one to each address. What is the expected number of letters that were received at correct addresses? Find the probability that at least one letter is put in a correctly addressed envelope.

I have no clue for the expected value but I know the answer for the second question is approaching $\frac{e-1}{e}$ as $n \to \infty$ by using inclusion exclusion.

The number of correctly delivered letters is $X = \sum_{i=1}^n X_i$, where $X_i = 1$ if letter number $i$ is delivered correctly, $0$ otherwise. Then $\mathbb E[X_i] = \mathbb P(X_i = 1) = 1/n$, and $\mathbb E[X] = \sum_{i=1}^n \mathbb E[X_i] = 1$.

The expected value is 1 for any $n$. We use induction on $n$ to prove this.

The base cases are straightforward. Now suppose the assertion is true for $n \leq k$, and we need to see the case $n = k+1$.

Case 1: The first letter is correctly sent. The chance is $\frac{1}{k+1}$. For the rest $k$ letters, in average there are 1 letter being correctly sent, so in this case, there are $1+1=2$ letters sent correctly in average.

Case 2: The first letter is sent incorrectly. Then we start to tract the relations. Suppose letter 1 is sent to address $a_1$, and letter $a_1$ is sent to address $a_2$, and we continue the process until we find a loop, that is, until we get to the address 1. We separate into two cases by the size of the loop, $\ell$.

Case 2-1: $\ell < k+1$. In this case the $\ell$ letters in the loop are messed up, while in the rest $k+1 - \ell$ letters, in average there is 1 letter being sent correctly.

Case 2-2: $\ell = k+1$. The chance that this happens is $\frac{1}{k+1}$. And if this happens, none of the letters is sent correctly.

By combining all cases, the expected value of letters sent correctly is $$\frac{1}{k+1}\times 2 + \frac{k-1}{k+1}\times 1 + \frac{1}{k+1}\times 0 = 1.$$ This ends our induction process.