4
$\begingroup$

Is there a distribution that describes the number of trials before all the events of a random variable with a discrete uniform distribution occurs?

Examples:

  • The number of rolls before getting all the numbers on a die.

  • The number of randomly chosen people needed to get a birthday every day of the year (excluding February 29th and assuming a discrete uniform distribution in birthdays)

Also, is there a generalized distribution to describe the number of times needed for all events to occur at least $K$ times?

$\endgroup$
  • 3
    $\begingroup$ You might want to start by looking into the Coupon Collector problem. There are several posts here on the topic, and there's a wikipedia page on it. $\endgroup$ – Glen_b Mar 5 '15 at 13:57
  • 1
    $\begingroup$ This question is practically the same as stats.stackexchange.com/questions/136714 (which is unanswered: I believe that's because a general answer would be messy). $\endgroup$ – whuber Mar 5 '15 at 19:25
1
$\begingroup$

Is there a distribution that describes the number of trials before all the events of a random variable with a discrete uniform distribution occurs?

Yes, there is. I call this distribution the coupon collector's distribution, since it describes the behaviour of the number of trials in the solution to the coupon collector's problem. The general form of the distribution and some of its properties are given here.

Let $X_1, X_2, X_3, ... \sim \text{IID U} \{ 1,...,m \}$ be uniformly distributed over $m \in \mathbb{N}$ categories and let $T$ be the smallest number of values in this series required to cover all the categories. This random variable follows the coupon collector's distribution, which has mass function:

$$\mathbb{P}(T=t) = \frac{m!}{m^t} \cdot S(t-1, m-1) \quad \quad \quad \text{for all } t \geqslant m,$$

where the function $S$ denotes the Stirling numbers of the second kind. It can be shown that this distribution has cumulant generating function:

$$K_T(s) = \ln((m+1)!) + sm + \sum_{r=0}^{m-1} \ln (m-re^s) \quad \quad \quad \text{for all } s \in \mathbb{R}.$$

Its mean and variance are given by:

$$\mathbb{E}(T) = m H_{1,m} \quad \quad \quad \mathbb{V}(T) = m^2 H_{2,m} - m H_{1,m} \quad \quad \quad H_{k,m} \equiv \sum_{i=1}^\infty \frac{1}{i^k},$$

where the values $H_{k,m}$ are the generalised harmonic numbers. For large $m$ the harmonic numbers in the expression for the mean are often approximated by their asymptotic form to give $\mathbb{E}(T) \approx m (\gamma + \ln m)$ where $\gamma$ is the Euler-Mascheroni constant. (The latter expression is sometimes incorrectly given as an exact expression for the mean.)

Also, is there a generalized distribution to describe the number of times needed for all events to occur at least $K$ times.

Such a distribution certainly exists, but its form is quite complicated and cumbersome. For this latter distribution it is usually simplest to deal with it by simulation (see e.g., this answer to a related question).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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