0
$\begingroup$

This question already has an answer here:

Let $x_1,x_2,\dots,x_n$ be independent identically distributed random variables uniform on $\{1,2,\dots,N\}$, and let: $Y_n:=\text{the number of different elements in } \{x_1,x_2,\dots,x_n\}$.

Let $T:=\inf\{n:Y_n=N\}$.

What is $E\left[T\right]$?

$\endgroup$

marked as duplicate by joriki probability Jun 18 '16 at 0:48

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ What do you mean by $\inf\{n:Y_n=N\}$? $\endgroup$ – enthdegree Feb 10 '14 at 3:42
  • 1
    $\begingroup$ The question is asking for the expected value of the random minimum sample size $T$ needed to be observed from a discrete uniform variable on $[1, N]$ such that every value in the support is observed. Clearly, ${\rm E}[T] \ge N$. $\endgroup$ – heropup Feb 10 '14 at 3:48
  • 1
    $\begingroup$ @enthdegree the smallest n s.t. Yn=N.i.e. the first time we have N different elements in {x1,x2,...,xn}. $\endgroup$ – user98619 Feb 10 '14 at 3:50
  • $\begingroup$ Get it now, thanks! $\endgroup$ – enthdegree Feb 10 '14 at 3:50
  • $\begingroup$ @heropup You are right!Thank you for the explanation $\endgroup$ – user98619 Feb 10 '14 at 3:51
0
$\begingroup$

This question is commonly known as the coupon collector's problem. See here: http://en.wikipedia.org/wiki/Coupon_collector%27s_problem

$\endgroup$
  • $\begingroup$ It is a good answer! $\endgroup$ – user98619 Feb 10 '14 at 4:18

Not the answer you're looking for? Browse other questions tagged or ask your own question.