12
$\begingroup$

I have a set of $n$ integers $\{1, . . . , n\}$, and I select three values with replacement. How can I find the expected number of distinct values?

Note each value is chosen uniformly and independently.

  • 0
    This might help http://math.stackexchange.com/questions/5775/how-many-bins-do-random-numbers-fill2011-10-13
  • 0
    See also [Expected number of unique items when drawing with replacement](http://math.stackexchange.com/questions/41519/expected-number-of-unique-items-when-drawing-with-replacement).2011-10-13
  • 0
    @Mike Thanks for the additional reference. Looks like this problem is an *evergreen*, or a *chestnut*!2011-10-13
  • 0
    @Byron: I give links to some other examples of using indicator variables in my answer to that question. And the more complicated problem of the expected number of distinct items when drawing $k$ *pairs* at random [was asked](http://math.stackexchange.com/questions/10124/how-to-calculate-the-expected-number-of-distinct-items-when-drawing-pairs) a while back. Both the "with replacement" and "without replacement" answers are given.2011-10-13

3 Answers 3