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 |