A generalization of negative binomial distribution

Question

Assume we have a set of $n$ balls. For each step, we uniformly pick one ball and label it if it is not labeled. Or otherwise move on to next step. I am wondering what is the distribution of number of steps till $m$ balls are labeled in the set.

This r.v. could be expressed as $G_1+G_2+\dots+G_m$, where $G_k$ is a geometric distribution with parameter $\frac{(n-k+1)}n$. It's conditional on $(k-1)$ balls have been labeled and how many step we need to reach one of those unlabeled balls.

Do we have a specific name for this r.v.? I am curious about its concentration around the mean and if it is unimodal discrete distribution.

Intuitively it is like a generalization of negative binomial distribution.

Answer 1

This is related to the coupon-collector problem. These random variables have been studied by many people, although I don't recall a particular name for them. See, for example, Anna Pósfai's thesis (abstract), which mentions the following limits in section 1.2:

Let $W_{n,m}$ be the number of draws to collect all but $m$ out of $n$ coupons. $\frac{W_{n,0} - EW_{n,0}}{n} \overset{D}\longrightarrow \textrm{Gumbel}(0)$. If $\frac{n-m(n)}{\sqrt{n}} \to \infty$ and $m(n) \to \infty$ then $\frac{W_{n,m} - EW_{n,m}}{\sigma(W_{n,m})} \overset{D}\longrightarrow \textrm{N}(0,1).$

Since geometric distributions are log-convex, their convolution is log-convex, hence unimodal.

Baum, L.E. and Billingsley, P., "Asymptotic distributions for the coupon collector’s problem," Ann. Math. Statist. 36 (1965), 1835–1839.

Erdős, P. and Rényi, A., On a classical problem of probability theory, Magyar Tud. Akad. Mat. Kutató Int. Közl. 6 (1961), 215–220.