Hard | Probability |

Given the set of numbers from 1 to n: { 1, 2, 3 .. n } We draw n numbers randomly (with uniform distribution) from this set (with replacement). What is the expected number of distinct values that we would draw?

Hint

Linearity of expectation

Answer

E(n) = n[1-(1-1/n)^n]

Solution

Notice that number of distinct points in the produced set is same as number of distinct points selected from the given set {1..n} . For that we denote indicator function Si, that is, Si = 1 if the interger i is taken into produced set.

Let S denote the number of distinct points selected, S = S1+..+Sn

E(S) = E(S1) +...+ E(Sn)

and E(Si) = 1*P(Si) = 1 - (Probability that 'i' is not chosen in any draw)

= 1 - ( Prob that is i is not chosen in one 1st draw)^n = 1 - ( 1 - 1/n )^n

Thus E(S) = n * ( 1 - ( (n-1) / n)^n )

Let S denote the number of distinct points selected, S = S1+..+Sn

E(S) = E(S1) +...+ E(Sn)

and E(Si) = 1*P(Si) = 1 - (Probability that 'i' is not chosen in any draw)

= 1 - ( Prob that is i is not chosen in one 1st draw)^n = 1 - ( 1 - 1/n )^n

Thus E(S) = n * ( 1 - ( (n-1) / n)^n )

Source: CSEblog

Enable Like and Comment Latest solved Puzzles

Color Switches Weird Sequences Intersecting Pillars Consecutive sums Scaling a Square Difficulty Level

© BRAINSTELLAR |