hard | probability |
There are letters and envelopes. You put the letters randomly in the envelopes so that each letter is in one envelope. (Effectively a random permutation of 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 be the indicator random variable such that:
- if the th letter ends up in the th envelope.
- otherwise
for any
let be the number of letters that ended up in their respective envelopes.
Now, =
(Using Linearity of Expectations)
Therefore, we expect on average one letter to be in the correct envelope.