| 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 )