hard | probability |

There are $n$ letters and $n$ envelopes. You put the letters randomly in the envelopes so that each letter is in one envelope. (Effectively a random permutation of $n$ numbers chosen uniformly). Calculate the expected number of envelopes with the correct letter inside them.

Use Indicator variables and the Linearity of Expectation

1

Let $X_i$ be the indicator random variable such that:

- $1$ if the $i$th letter ends up in the $i$th envelope.
- $0$ otherwise

$E[X_i] = P(X_i = 1) = 1/n$ for any $i$

let $X$ be the number of letters that ended up in their respective envelopes.

Now, $X$= $X_1 + X_2+ \ldots +X_n$

$E[X] = E[\sum_{i=1}^{n} X_i]$

$= \sum_{i=1}^{n} E[X_i]$ (Using Linearity of Expectations)

$=\sum_{i=1}^{n} (1/n) = 1$

Therefore, we expect on average **one** letter to be in the correct envelope.