tenant mailbox problem

Question

In your appartment building, there are n tenants, each having a mailbox. The mailboxes are numbered from 1 to n. An insurance company wants to send a letter to each tenant. However, due to a software error, each of the n letters is sent to a random mailbox (i.e. chosen independently and uniformly at random among the n mailboxes.) So some mailboxes may receive several letters, and some may not receive any letter|we call these boxes empty mailboxes. Let f(n) be the expected number of empty mailboxes. Determine f(n) for all integer n > 1, and justify your answer.

Answer 1

For $n \gt 1$, the probability for a given mailbox to stay empty for the next incoming letter is

$$P_{\text{empty next}} = \frac{n-1}{n}$$

There are $n-1$ of $n$ potential cases which leave the mailbox empty.

Performing this experiment independently $n$ times results in a probability to stay empty until letter $n$ is eventually delivered:

$$P_{\text{empty final}} = \left(\frac{n-1}{n}\right)^n$$

To get the expected number of empty mailboxes, simply add the expectation values of all $n$ mailboxes:

$$E(\#_{\text{empty}}) = n\left(\frac{n-1}{n}\right)^n$$

As commented by lulu, this summation of expected values is known as Linearity of Expectation.