| Hard | Probability |
There are n letters and n envelopes. Your servant puts the letters randomly in the envelopes so that each letter is in one envelope and all envelopes have exactly one letter. (Effectively a random permutation of n numbers chosen uniformly). Calculate the expected number of envelopes with correct letter inside them.
Hint
Linearity of expectation
Solution
Let I_i be a indicator random variable which takes
1) value 1 if ith letter ends up in ith envelope.
2) value 0, otherwise
let I be r.v which indicates the number of letters which ended up in their respective envelopes.
Now, I= I_1 +I_2+....+I_n
E[I_i] = 1/n. for all i
Using Linearity of Expectations E[I]= 1/n + 1/n +...+1/n = 1.
1) value 1 if ith letter ends up in ith envelope.
2) value 0, otherwise
let I be r.v which indicates the number of letters which ended up in their respective envelopes.
Now, I= I_1 +I_2+....+I_n
E[I_i] = 1/n. for all i
Using Linearity of Expectations E[I]= 1/n + 1/n +...+1/n = 1.
Source: CSEblog
Enable Like and Comment Latest solved Puzzles
Color Switches Weird Sequences Intersecting Pillars Consecutive sums Scaling a Square Difficulty Level
| © BRAINSTELLAR |