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?

Linearity of expectation

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

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 )