Modern Stochastics: Theory and Applications

The coupon collector’s problem is undoubtedly one of the most popular classical problems in combinatorial probability. It is not only of purely theoretical interest, but also finds numerous applications (see, e.g., [8, 25, 1, 4, 5]). More recently, an extended version of this problem, known in the literature as the collector’s brotherhood problem, has attracted considerable attention; see, e.g., [15, 14, 2, 11].

Following [14], we give its statement as follows. A person collects coupons, each of which belongs to one of $n\in \mathbb{N}$ different types. The coupons arrive one by one at discrete times, the type of each coupon being equiprobable and independent of types of preceding ones. Each time the person receives a coupon which he does not yet have, he puts it in his album. Otherwise, he gives it to his younger brother. In his turn, the latter puts it in his own album, if the coupon is new for him. Otherwise, he gives it to the next younger brother, and so on. All the brothers try to complete their own collections, using the same policy. The main collector is labeled 0, the younger brother 1, the next younger brother 2, etc.

For $r\in {\mathbb{N}_{0}}=\mathbb{N}\cup \{0\}$, let ${T_{r}^{(n)}}$ stand for the time the rth person completes his collection. By a classical result due to Erdős and Rényi [12], with $\gamma =-{\Gamma ^{\prime }}(1)$ standing for the Euler–Mascheroni constant. So, the limiting distribution is of Gumbel type.

Denote by ${U_{r}^{(n)}}$, $r\in \mathbb{N}$, the number of empty spots in the album of the rth brother at time ${T_{0}^{(n)}}$, that is, when the main collector completed his album. In [26], by using the optional stopping theorem for a specially constructed martingale, it was shown that $\mathbb{E}{U_{1}^{(n)}}={\mathcal{H}_{1}^{(n)}}$, where ${\mathcal{H}_{1}^{(n)}}={\textstyle\sum _{k=1}^{n}}\frac{1}{k}$ stands for the nth harmonic number. Subsequently, it turned out that this can be further generalized to where ${\mathcal{H}_{r}^{(n)}}$ are hyperharmonic numbers defined by the recursive formula This was proved in [15] and [14] by using a non-elementary generating function argument, and in [2] by a simpler and more direct probabilistic reasoning. Moreover, the latter argument made it possible to obtain another, more explicit representation: By (10.1) in [15], for the above hyperharmonic numbers the following asymptotic formula holds: It should be noted that the term “hyperharmonic numbers” often refers to a different numerical sequence (see, e.g., the corresponding article in Wikipedia).

Note that this problem allows for different, though equivalent, formulations. For instance, we give another one in terms of a balls-into-bins model. Suppose we have an infinite sequence of balls and n bins of unlimited capacity. Each time a single ball is placed into one of the bins, which is chosen equiprobably and independently of the previous history. In this setting, ${T_{r}^{(n)}}$ means the first time when each bin contains at least $r+1$ balls. Similarly, ${U_{r}^{(n)}}$ stands for the number of bins containing at most r balls at time ${T_{0}^{(n)}}$, that is, when each bin first contains at least one ball.

Until now, the question of limiting distributions for ${U_{r}^{(n)}}$ as $n\to \infty $ remained open. This problem was explicitly stated on p. 446 in [11]. In order to determine these limiting distributions it would be natural to use the generating function of ${U_{r}^{(n)}}$. The latter can be easily deduced from Proposition 4.1 in [15]: It is, however, clear that the generating function of such an ominous form can hardly be used for this purpose. Therefore, as in our previous papers [19, 20], we take a different approach based on the use of point processes. This allows not only to determine the limiting distributions for ${U_{r}^{(n)}}$ (looking ahead, they will turn out to be exponential) but also to obtain the limit theorem in an ultimate infinite-dimensional form. In other words, we will prove the distributional convergence of the sequence $\big({U_{r}^{(n)}},r\in \mathbb{N}\big)$, normalized in a proper way, to a random element $(E,E,\dots )$ of ${\mathbb{R}^{\infty }}$ as $n\to \infty $, where the same $\mathsf{Exp}(1)$-distributed random variable E appears in every coordinate. This means that ${U_{r}^{(n)}}$ exhibit a remarkable asymptotic stability. The precise statement is given in Theorem 1 below.

Note that in the proof of this limit theorem we use a rather unusual trick which, hopefully, can be applied elsewhere. Namely, appealing to a certain analogy between normalization and thinning, we prove the distributional convergence for thinned random variables rather than for normalized ones. This convergence can be deduced from that of specially constructed point processes. The way we then return to normalized random variables is described in Section 4.

We also prove another limit theorem which can be called delayed one. The idea behind is as follows. Due to their definition, the random variables ${U_{r}^{(n)}}$ increase unboundedly as $n\to \infty $. Thus, in order to obtain a distributional limit, we had to use some normalization. If one still wants to obtain a limit result without any normalization, one should, instead of ${U_{r}^{(n)}}$, consider the number of empty spots in the album of the rth brother not at time ${T_{0}^{(n)}}$ but after some delay, that is, at time ${T_{0}^{(n)}}+{d_{r}^{(n)}}$ with some non-random ${d_{r}^{(n)}}\to \infty $ as $n\to \infty $. With the right choice of ${d_{r}^{(n)}}$, the corresponding numbers of empty spots will not go to infinity as n does, but will instead converge in distribution to some limit law. In Theorem 2, we find this right form of ${d_{r}^{(n)}}$ and establish convergence to a geometric distribution. Like the previous result, we state and prove this one in an infinite-dimensional form, that is, in the sense of distributional convergence in ${\mathbb{R}^{\infty }}$.

Our third main result, Theorem 3 below, describes the asymptotic behavior of the sequence of completion times, that is, of the (centered and normalized in a proper way) random elements $\big({T_{r}^{(n)}},r\in {\mathbb{N}_{0}}\big)$ in ${\mathbb{R}^{\infty }}$. Actually, this is an infinite-dimensional extension of (1), the limit theorem due to Erdős and Rényi. Surprisingly, the limiting random element turns out to consist of independent entries, which means that the completion times ${T_{r}^{(n)}}$, after appropriate centering and normalizing, become asymptotically independent. This may seem all the more unexpected since ${T_{r}^{(n)}}$ increase in r, which excludes any kind of independence for non-centered completion times. So, this asymptotic independence is achieved only at the expense of centering and normalizing. As a direct application of the latter result, we derive a limit theorem for inter-completion times with limiting logistic distribution.

Denote by ${Y_{i,r}^{(n)}}$, $n\in \mathbb{N}$, $i\le n$, $r\in {\mathbb{N}_{0}}$, the arrival time of the $(r+1)$th coupon of type i. So, at time ${Y_{i,r}^{(n)}}$ the collector labeled r receives such a coupon into his collection. Hence, which is one version of the negative binomial distribution, namely, the one that counts trials up to the $(r+1)$th success. Note that

For different i, the random variables ${Y_{i,r}^{(n)}}$ are identically distributed but not independent. There is a standard way to get rid of this dependence, namely, poissonization. This technique goes back at least to Karlin and was systematically exploited by Holst in the context of random allocations (see [18] or [19] for details). Consider a poissonized scheme, that is, assume that coupons arrive at random times with independent $\mathsf{Exp}(1)$-distributed intervals ${E_{j}}$, $j\in \mathbb{N}$. Similarly to the above, denote by ${Z_{i,r}^{(n)}}$ the arrival time of the $(r+1)$th coupon of type i in the poissonized scheme. Then, for different i, ${Z_{i,r}^{(n)}}$ are independent gamma-distributed random variables, ${Z_{i,r}^{(n)}}\sim \Gamma \big(r+1,\frac{1}{n}\big)$, which is a consequence of the thinning theorem for Poisson point processes (see, e.g., Theorem 5.8 in [24]). For any fixed n, the sequences $\big({Y_{i,r}^{(n)}}\big)$ and $\big({Z_{i,r}^{(n)}}\big)$ can be given on a common probability space and coupled by Moreover, $\big({Y_{i,r}^{(n)}},i\le n,r\in {\mathbb{N}_{0}}\big)$ is independent of $({E_{j}},j\in \mathbb{N})$, because the inter-arrival times ${E_{j}}$ do not affect the order in which the coupons of different types arrive. Finally, note that, along with (5), a similar formula in terms of ${Z_{i,r}^{(n)}}$ holds:

We now state our first main result, an infinite-dimensional distributional limit theorem for $\big({U_{r}^{(n)}},r\in \mathbb{N}\big)$ in the space ${\mathbb{R}^{\infty }}$ equipped with the product topology.

Let us now turn to the delayed limit theorem. By analogy with ${U_{r}^{(n)}}$, for fixed ${d_{r}^{(n)}}\in \mathbb{N}$ denote by ${\hat{U}_{r}^{(n)}}$ the number of empty spots in the album of the rth brother at time ${T_{0}^{(n)}}+{d_{r}^{(n)}}$: The following result asserts that, with the right choice of ${d_{r}^{(n)}}$, the random elements $\big({\hat{U}_{r}^{(n)}},r\in \mathbb{N}\big)$ of ${\mathbb{R}^{\infty }}$ converge in distribution to some limiting random element with geometrically distributed marginals.

As our final result, we give an infinite-dimensional extension of (1), the limit theorem by Erdős and Rényi.

In particular, this result allows obtaining limit distributions for times between completions of different collections. Denote by ${\Delta _{{r_{1}},{r_{2}}}^{(n)}}={T_{{r_{2}}}^{(n)}}-{T_{{r_{1}}}^{(n)}}$, ${r_{2}}\gt {r_{1}}$, such an inter-completion time.

It is well known (and may be easily checked by means of characteristic functions) that the difference of two independent Gumbel-distributed random variables has a logistic distribution. Particularly, ${B_{{r_{2}}}}-{B_{{r_{1}}}}\stackrel{d}{=}{L_{{r_{1}},{r_{2}}}}$. Thus, (17) follows from (16).

One of the key points in the proof of Theorem 1 is convergence of specially constructed point processes to a Poisson one. We now proceed to the corresponding construction.

For fixed $n\in \mathbb{N}$ and $r\in {\mathbb{N}_{0}}$, let where ${\delta _{u}}$ stands for the Dirac measure $𝟙\{u\in \cdot \}$. The processes ${\eta _{r}^{(n)}}$ describe $(r+1)$th arrivals of different coupon types in the poissonized scheme. Note that in a similar case in [19], in order to provide the necessary convergence, we used an r-dependent centering/normalizing function In our case, however, we want to consider the numbers of empty spots in different albums at the same point in time, namely when the 0th album is completed. Hence, we have to deal with the same centering for different r. So, we will achieve the desired convergence in a different way — by means of thinnings.

For a proper point process η, let us denote by ${T_{p}}\eta $, $p\in [0,1]$, its p-thinning, i.e. the point process which independently keeps the points of η with probability p and removes otherwise (see, e.g., [24], Section 5.3 for details). On the space endowed with some relevant metric, say, consider the point processes ${H^{(n)}}$, $n\ge 3$, given as follows: for ${B_{r}}\in \mathfrak{B}\big(\mathbb{R}\cup \{+\infty \}\big)$, $r\in {\mathbb{N}_{0}}$, define where all thinnings are performed independently across levels and of the underlying coupon process. (We require $n\ge 3$ in order to have ${\ln ^{-r}}n\in [0,1]$ for all $r\in {\mathbb{N}_{0}}$.) In other words, we are thinning out the processes ${\eta _{r}^{(n)}}$ and glue them into one “multilevel” point process ${H^{(n)}}$. Note that, by construction in (19), anyway. The reason we, nevertheless, consider the semi-compactified real axis $\mathbb{R}\cup \{+\infty \}$ instead of just $\mathbb{R}$ will become clear from what follows (see Section 5).

Before stating the main theorem of this section, we reformulate the basic definitions related to convergence of point processes as applied to our problem (for a detailed exposition in the abstract setting, see [28, 29], or [22]). Let ${M_{p}}(\mathbb{X})$ denote the space of all locally finite (with respect to d in (22)) point measures on $\mathbb{X}$ given by (21). For $\mu ,{\mu _{1}},{\mu _{2}},\dots \in {M_{p}}(\mathbb{X})$, ${\mu _{n}}$ are said to converge vaguely to μ (denoted by ${\mu _{n}}\xrightarrow{v}\mu $) if ${\textstyle\int _{\mathbb{X}}}f\hspace{0.1667em}\mathrm{d}{\mu _{n}}\to {\textstyle\int _{\mathbb{X}}}f\hspace{0.1667em}\mathrm{d}\mu $ for each continuous compactly supported non-negative test function f defined on $\mathbb{X}$. In our case, this means that for each $r\in {\mathbb{N}_{0}}$ and each continuous compactly supported $g:\mathbb{R}\cup \{+\infty \}\to [0,+\infty )$. As usual, the set ${M_{p}}(\mathbb{X})$, equipped with the topology of the above convergence, can be metrized as a complete separable metric space. This setting allows us to consider the distributional convergence of point processes ${H^{(3)}},{H^{(4)}}\dots \hspace{0.1667em}$, denoted as ${H^{(n)}}\xrightarrow{vd}H$. The main result of this section, Theorem 4 below, asserts that the point processes ${H^{(n)}}$ converge in this sense toward a non-homogeneous Poisson process.

In this section, we consider a somewhat unusual approach to proving limit theorems, which is the basic tool in the proof of Theorem 1. This approach does not seem to have been used in this context before, and may prove useful elsewhere as well.

For an ${\mathbb{N}_{0}}$-valued random variable X, define its p-thinning, $p\in [0,1]$, by where ${\varepsilon _{i}}$ are $\mathsf{Bin}(1,p)$-distributed and independent of each other and of X. Note that, in the notation of the previous section, $({T_{p}}\eta )(B)\stackrel{d}{=}p\odot \eta (B)$ for a proper point process η and a Borel set B. This operation, going back to [27], was then used in [32] to introduce the concepts of discrete self-decomposability and stability.

The idea behind the proposed technique is to replace the normalization by thinning. In other words, instead of proving that ${p^{(n)}}{X^{(n)}}\xrightarrow{d}Y$ with some constants ${p^{(n)}}\to 0$ and a limiting random variable Y, we will prove that ${p^{(n)}}\odot {X^{(n)}}\xrightarrow{d}Z$ with some new limiting random variable Z. The connection between the distributions of Y and Z can be guessed from the following examples. For ${X^{(n)}}=n$ a.s., we have $\frac{1}{n}{X^{(n)}}=1\xrightarrow{d}1$ and $\frac{1}{n}\odot {X^{(n)}}\xrightarrow{d}Z\sim \mathsf{Pois}(1)$ by the Poisson limit theorem. More generally, consider an i.i.d. sequence $({\xi _{i}},i\in \mathbb{N})$ with $\mathbb{E}{\xi _{i}}=\lambda $, and denote ${X^{(n)}}={\textstyle\sum _{i=1}^{n}}{\xi _{i}}$. Due to the law of large numbers, $\frac{1}{n}{X^{(n)}}\xrightarrow{d}\lambda $, and, by Theorem 3.1 in [17], $\frac{1}{n}\odot {X^{(n)}}\xrightarrow{d}Z\sim \mathsf{Pois}(\lambda )$. All this suggests that, in general, Z must have the mixed Poisson distribution with mixing distribution of Y (see, e.g., Chapter 2 in [16]). This means that where ${F_{Y}}$ stands for the distribution function of Y.

The main result of this section, Theorem 5 below, justifies this approach. With an eye to the future, we will state and prove it in multidimensional form. Let $\mathbf{Y}=({Y_{1}},\dots ,{Y_{s}})$ be a random vector with a.s. non-negative components. By analogy with (35), the random vector $\mathbf{Z}=({Z_{1}},\dots ,{Z_{s}})$ is said to have a multivariate mixed Poisson distribution with mixing distribution of Y (see [13] or [23]) if

In this short section, we apply Theorems 4 and 5 to the proof of Theorem 1. Let for $r\in \mathbb{N}$. In the notation of Section 2, ${\tilde{T}_{0}^{(n)}}={\max _{i\le n}}{\psi ^{(n)}}\big({Z_{i,0}^{(n)}}\big)$, and thus means the (centered and normalized) time when the main collector completes his album in the poissonized scheme. Next, ${V_{r}^{(n)}}$ is the number of points of the thinned process ${T_{{\ln ^{-r}}n}}{\eta _{r}^{(n)}}$ to the right of ${\tilde{T}_{0}^{(n)}}$. So, according to (7), it is easily seen to be equal in distribution to ${\ln ^{-r}}n\odot {U_{r}^{(n)}}$, where the operation ⊙ is defined in (34).

By Theorem 4 and the Skorokhod coupling (see, e.g., [29], p. 41), we may assume that ${H^{(n)}}\xrightarrow{v}H$ a.s. as $n\to \infty $. Define ${\tilde{T}_{0}}$ and ${V_{r}}$ similarly to (45) but with H instead of ${H^{(n)}}$. Proposition 3.13 in [28], together with the simplicity of H and the independence of its levels, implies that the mappings corresponding to ${\tilde{T}_{0}}$ and ${V_{r}}$ are continuous at H a.s. Hence, ${\lim \nolimits_{n\to \infty }}{\tilde{T}_{0}^{(n)}}={\tilde{T}_{0}}$ and ${\lim \nolimits_{n\to \infty }}{V_{r}^{(n)}}={V_{r}}$ a.s. It is here that we use the fact that ${H^{(n)}}(\{r\}\times \cdot )$ are given on the semi-compactified space $\mathbb{R}\cup \{+\infty \}$, because we need $(x,+\infty )$ to be relatively compact.

Let $({N_{r}}(t),t\ge 0)$, $r\in {\mathbb{N}_{0}}$, be independent unit-rate Poisson counting processes. Denote by E the first jump time of ${N_{0}}$, and note that $E\sim \mathsf{Exp}(1)$. Due to Remarks 3 and 4, ${\tilde{T}_{0}}\stackrel{d}{=}-\ln E$, and $({V_{1}},\dots ,{V_{s}})\stackrel{d}{=}({N_{r}}(E/r!),r=1,\dots ,s)$ for any $s\in \mathbb{N}$. Summarizing all the above, we have

Then, applying Theorem 5 and taking into account Remark 5, we obtain condition (38) being satisfied due to (2) and (3). Thus, the convergence in (8) holds in the sense of finite-dimensional distributions. To complete the proof, it only remains to note that in ${\mathbb{R}^{\infty }}$ the notions of finite-dimensional convergence and convergence in distribution are equivalent (see, e.g., [29], pp. 53–54).  □

For the proofs of Theorems 2 and 3, we will also use a specially constructed sequence of point processes. This time, however, their convergence will be achieved not at the expense of thinning, as in Section 3, but due to an r-dependent centering.

On the metric space $(\mathbb{X},d)$ given by (21) and (22), consider the point processes ${\hat{H}^{(n)}}$, $n\in \mathbb{N}$, defined as follows: for ${B_{r}}\in \mathfrak{B}\big(\mathbb{R}\cup \{+\infty \}\big)$, $r\in {\mathbb{N}_{0}}$, let where and the centering/normalizing functions ${\hat{\psi }_{r}^{(n)}}$, slightly generalizing ${\psi _{r}^{(n)}}$ in (20), are defined as follows: Here, for each $r\in {\mathbb{N}_{0}}$, ${\varkappa _{r}^{(n)}}$ is a fixed numerical sequence such that ${\lim \nolimits_{n\to \infty }}{\varkappa _{r}^{(n)}}=0$. We will also use counterparts of ${\hat{H}^{(n)}}$ in the original, non-poissonized scheme: where and ${Y_{i,r}^{(n)}}$ are defined at the beginning of Section 2.

The following result is an analogue of Theorem 4 but differs in two significant aspects. Firstly, we now use the r-dependent centering (47) instead of thinning, and secondly, the original scheme instead of the poissonized one. The latter will require a special depoissonization procedure based on the coupling formula (6) and similar to that used in [19]. Unlike Theorem 4, we need to consider this result in the original setting rather than in the poissonized one due to the lack of any counterpart to (7) for ${\hat{U}_{r}^{(n)}}$.

In this section, we apply Theorem 6 to the proof of Theorems 2 and 3. As in Section 5, it suffices only to prove the convergence of finite-dimensional distributions.

Similarly to (45), let for $r\in {\mathbb{N}_{0}}$. Particularly, ${\hat{V}_{0}^{(n)}}=0$ a.s. By definition of ${\hat{\Xi }^{(n)}}$ and ${\hat{\xi }_{r}^{(n)}}$, and according to (4), it holds that Thus, ${\hat{T}_{r}^{(n)}}$ means the (centered and normalized) time when the rth collector completes his album in the original, non-poissonized scheme. Next, ${\hat{V}_{r}^{(n)}}$ is the number of points of the single-level process ${\hat{\xi }_{r}^{(n)}}$ to the right of ${\hat{T}_{0}^{(n)}}$. By definition of ${\hat{\xi }_{r}^{(n)}}$ and according to (47), (54), we have Comparing this with (9), we can see that, with any choice of $\mathcal{O}(n)$ in (10), one may choose ${\varkappa _{r}^{(n)}}$, $r\in {\mathbb{N}_{0}}$, in such a way that ${\hat{V}_{r}^{(n)}}={\hat{U}_{r}^{(n)}}$.

Just as it was done in Section 5, Theorem 6 and the Skorokhod coupling imply that, for any $s\in \mathbb{N}$, where $E\sim \mathsf{Exp}(1)$, and ${N_{r}}$ are unit-rate Poisson counting processes, independent of each other and of E. This completes the proof of (12). The generating function of the random vector on the right-hand side can be easily calculated by means of conditioning with respect to E: Letting here $s\to \infty $ yields (11).

Finally, again Theorem 6 and the Skorokhod coupling, combined with (54), (53), and Remarks 3, 4 imply that, for any $s\in {\mathbb{N}_{0}}$, where ${E_{r}}$ are independent $\mathsf{Exp}(1)$-distributed random variables. Here ${E_{r}}$ actually means the first jump time of ${N_{r}}$. Thus, $-\ln r!-\ln {E_{r}}$ on the right-hand side, by Remark 4, is the rightmost point of $H\big(\{r\}\times \cdot \big)$, the rth level of the limiting process H. To complete the proof of (16), it suffices to note that $-\ln r!-\ln {E_{r}}\stackrel{d}{=}{B_{r}}$ from (15), and to put in (47) ${\varkappa _{r}^{(n)}}=0$.  □

In Theorems 1 and 2, the reference point is ${T_{0}^{(n)}}$, the time when the main collector completed his album. That is, we studied the number of empty spots in the album of the rth brother at time ${T_{0}^{(n)}}$ in Theorem 1 and at time ${T_{0}^{(n)}}+{d_{r}^{(n)}}$ in Theorem 2. Similarly, we could fix some ${r_{0}}\in {\mathbb{N}_{0}}$ and consider the number of empty spots in the collection of the rth brother at times ${T_{{r_{0}}}^{(n)}}$ and ${T_{{r_{0}}}^{(n)}}+{d_{r,{r_{0}}}^{(n)}}$ with some ${d_{r,{r_{0}}}^{(n)}}\to +\infty $ as $n\to \infty $. The former makes sense only for $r\gt {r_{0}}$, while, in the latter case, we may consider $r\lt {r_{0}}$ with ${d_{r,{r_{0}}}^{(n)}}\lt 0$, replacing ${d_{r,{r_{0}}}^{(n)}}\to +\infty $ by ${d_{r,{r_{0}}}^{(n)}}\to -\infty $. Repeating the above proofs with minimal changes, we can derive analogous results with similar limiting distributions (exponential and geometric, respectively).

Another possible reference point is ${T_{0}^{(n)}}(m)$, $m\in {\mathbb{N}_{0}}$, the time when the main collector first assembled some $n-m$ (unspecified) of n coupons, or ${T_{{r_{0}}}^{(n)}}(m)$, the similar value for the ${r_{0}^{\hspace{0.1667em}\hspace{0.1667em}th}}$ collector. In this notation, ${T_{{r_{0}}}^{(n)}}(0)={T_{{r_{0}}}^{(n)}}$. In this case, we come to more general limiting distributions — gamma and negative binomial, respectively. This can be proved along the above lines.

Let us now dwell on some possible directions for further research. Computer simulations show that the rate of convergence in Theorems 1 and 2 is rather slow. It would be interesting to obtain, for each fixed $r\in \mathbb{N}$, upper bounds on the rates of convergence of the rth coordinates in the Wasserstein distance for Theorem 1 and in the total variation distance for Theorem 2, similarly to the recent work [9] on the Erdős–Rényi limit theorem (1), which is the one-dimensional version of Theorem 3. The most natural tool for this is Stein’s method. The relevant techniques for exponential and geometric approximation are summarized, for example, in Sections 5 and 6 of [30]. Some applications of Stein–Chen Poisson approximation to the coupon collector’s problem are given in Chapter 6 of [6] and in Examples 4.34 and 4.35 of [30].

The extended coupon collector’s problem with unequal probabilities provides a natural direction for future research. Some steps in this direction were taken in [11]. Finally, related questions can also be posed for variants of the coupon collector’s problem with group drawings, as considered, e.g., in [31] and in the recent work [3].