Coupon collector targeting a collection among many

Question

I am interested in the following problem:
We are given a universe $U$ of $n$ coupons, partitioned into $k$ collections, $C_1,\dots C_k$.
At each time step $t$, a coupon $X_t$ is selected uniformly at random in $U$.

I am interested in the expectation (and other properties) of the random variable $T$ which models the completion of at least one collection: $$T = \min \{t > 0: \exists i, C_i\subseteq\{X_1,\dots,X_t\}\}$$

There are a few cases which have already been studied:

• If $k = 1$, this is just the usual coupon collector
• If $|C_i| = 1$, this is a geometric random variable of parameter $k/n$

Question: Has this problem been studied in the litterature ? (I haven't found any references)
Are there similar problems which might give insights on how to tackle this problem ?

Finally, I am also interested in an extension of the above problem where the $C_i$ are pairwise disjoint but do not necessarily cover $U$.
This version of the problem is somewhat easier to tackle since there is a recursive formula for $T$, considered as a function of $|C_1|,\dots,|C_k|$ (we move coupons that we have already collected to the part of $U$ that is not covered by the collection).

Answer 1

Let us obtain an explicit expression for the distribution of $T$. This will be done for any family $(C_1,\dots,C_k)$ of subsets of $[n]:=\{1,\dots,n\}$. However, the formula will be rather complicated, expressed in terms of the Stirling numbers $S_t^{(j)}$ of the second kind, with $S_t^{(j)}$ defined as the number of ways to partition a set, say $A$, of cardinality $|A|=t$ into $j$ non-empty subsets. There is an explicit expression for $S_t^{(j)}$.

Consider the random set \begin{equation*} S_t:=\{X_1,\dots, X_t\}. \end{equation*} Let \begin{equation*} p_{t,j}:=p_{n;t,j}:=P(|S_t|=j). \end{equation*} Then for all integers $t\ge0$ and $j\ge0$ \begin{equation*} p_{0,j}=1(j=0),\quad p_{t,0}=1(t=0),\tag{1} \end{equation*} and, by conditioning on $|S_{t-1}|$, we get \begin{equation*} p_{t,j}=p_{t-1,j}\,\frac jn+p_{t-1,j-1}\,\frac{n-j+1}n \tag{2} \end{equation*} if $t,j\ge1$. Using the substitution \begin{equation*} p_{t,j}=\frac{s_{t,j}}{n^t}\,\binom nj j!, \end{equation*} we rewrite (1)--(2) in an $n$-free way:
\begin{equation*} s_{0,j}=1(j=0),\quad s_{t,0}=1(t=0),\tag{1s} \end{equation*} for all integers $t\ge0$ and $j\ge0$ and \begin{equation*} s_{t,j}=s_{t-1,j}\,j+s_{t-1,j-1} \tag{2s} \end{equation*} if $t,j\ge1$. Relations (1s) and (2s) are satisfied by, and hence determine, the Stirling numbers $S_t^{(j)}$ of the second kind. So, for all integers $t\ge0$ and $j\ge0$ we have $s_{t,j}=S_t^{(j)}$ and hence \begin{equation*} p_{t,j}=\frac{S_t^{(j)}}{n^t}\,\binom nj j!. \tag{3} \end{equation*}

Let now $R_j$ denote a set selected at random from the set $\binom{[n]}j$ of all subsets of $[n]$ of cardinality $j$. Then for any $C\subseteq[n]$ \begin{equation*} P(R_j\supseteq C)=\pi_{n,j,|C|}:=\binom{n-|C|}{j-|C|}\Big/\binom nj. \tag{4} \end{equation*} So, by conditioning on $|S_t|$ and then recalling (3) and using the mentioned explicit expression for $S_t^{(j)}$, we get \begin{align*} P(S_t\supseteq C)&=\sum_{j=0}^n p_{t,j}\,\pi_{n,j,|C|} \\ &=\frac1{n^t}\sum_{j=0}^n \binom{n-|C|}{j-|C|}\, j!\, S_t^{(j)} \\ &=\frac1{n^t}\sum_{j=0}^n \binom{n-|C|}{j-|C|}\, \sum_{i=0}^j(-1)^{j-i}\binom ji i^t \\ &=\frac1{n^t} \sum_{i=0}^n i^t \sum_{j=i}^n (-1)^{j-i}\binom{n-|C|}{j-|C|}\,\binom ji \\ &=\frac1{n^t} \sum_{i=0}^n i^t \binom{n-|C|}{i-|C|} \, _2F_1(i+1,i-n;i-|C|+1;1). \tag{5} \end{align*}

Finally, by the inclusion--exclusion formula, \begin{align*} P(T\le t)&=P\Big(\bigcup_{i\in[k]}\{S_t\supseteq C_i\}\Big) \\ &=\sum_{r\in[k]}(-1)^{r-1}\sum_{J\subseteq[k],\,|J|=r}P(S_t\supseteq C_J), \end{align*} where $C_J:=\bigcup_{i\in J}C_i$, with $P(S_t\supseteq C_J)$ computed according to (5).

Answer 2

There a well known generating function methods (the ''symbolic method'' and ''Poissonization'') which can be used to deal with this kind of question. However, I am unable to point to a reference for this specific question (but it may well be out there).

Here is a self contained answer to get you started.

I rephrase your general question as an urn problem. Denote the cardinality of $C_i$ by $c_i$ and collect the useless coupons in class $C_{k+1}=U\setminus\bigcup_{i=1}^k C_i$, of cardinality $c_{k+1}=n-\sum_{i=1}^k c_i$.

Consider an urn which for $i\in\{1,\ldots k\}$ contains $c_i\geq 1$ distinguishable coupons of type $i$, and $c_{k+1}\geq 0$ further distinguishable coupons, altogether $n:=c_1+\ldots+c_{k+1}$ coupons.

Coupons are drawn with replacement from this urn until for the first (random) time $T$ for an $i\in\{1,\ldots,k\}$ all different coupons of type $i$ have been drawn at least once. Let $Y_1(\ell),\ldots,Y_{k+1}(\ell)$ be the random variables $Y_i(\ell):=$ "number of different coupons of type $i$'' that have been drawn at "time" $\ell$.

I use generating functions and start from the following basic

Proposition

The generating function of (the joint distribution of) $Y_1(\ell),\ldots,Y_{k+1}(\ell)$ is given by: \begin{equation*} \mathbb{E}\, t_1^{Y_1(\ell)}\ldots t_n^{Y_{k+1}(\ell)}=\frac{\ell!} {n^\ell}[t^\ell] (1+(e^t-1)\,t_1)^{c_1}\cdot\ldots\cdot(1+(e^t-1)\,t_{k+1})^{c_{k+1}} \end{equation*} Proof Let $j_1+\ldots +j_{k+1}\leq\ell$. Clearly $$\mathbb{P}(Y_1(\ell)=j_1,\ldots,Y_{k+1}(\ell)=j_{k+1})=\frac{1}{n^\ell}\cdot {c_1 \choose j_1}\cdots {c_{k+1} \choose j_{k+1}}\cdot \mathrm{Sur}(\ell, j_1+\ldots+j_{k+1})$$ where $\mathrm{Sur}(\ell,r)$ denotes the number of surjective mappings from $\{1,\ldots,\ell\}$ onto $\{1,\ldots,r\}$. (Namely, once the (possibly empty) sets $J_i\subset C_i$ of cardinality $j_i$ of appearing coupons from class $C_i$ are chosen, the sequence of draws may be viewed as the value table of a surjective mapping from $\{1,\ldots,\ell\}$ to $\bigcup_{i=1}^{k+1} J_i$. ) It is known that $\mathrm{Sur}(\ell,r)=\ell!\,[t^\ell]\,(e^t-1)^r$ (since a such a surjective mapping corresponds uniquely to an ordered partition of $\{1,\ldots,\ell\}$ in $r$ into non-empty subsets, and $e^t-1$ is the exponential generating function for non-empty sets). The assertion about the g.f. follows. End of proof

(I) The distribution of $T$

Since $\{\,T > \ell\}=\{\,Y_1(\ell) < c_1,\ldots,Y_{k}(\ell)<c_k\,\}$ the above gives \begin{equation*} \mathbb{P}(T>\ell) =\frac{\ell!} {n^\ell}[t^\ell]\, e^{c_{k+1}t} \prod_{i=1}^k \big(e^{tc_i} -(e^t-1)^{c_i})\big) \end{equation*}

(II) The expectation of $T$

Finally, using $\mathbb{E} T=\sum_{\ell\geq 0} \mathbb{P}(T>\ell)$ and writing $\frac{\ell!}{n^\ell} =n\,\int_0^\infty\,s^\ell e^{-ns}\,ds$ leads to

$$\mathbb{E}(T)=n\int_0^\infty \prod_{i=1}^k\big(1-(1-e^{-s})^{c_i}\big)\,ds$$

ADDED Similar formulas for the expectation of related waiting times can be found here (Theorem 3.1) https://www.sciencedirect.com/science/article/pii/0166218X9290177C

Answer 3

You can modify a little the problem replacing the deterministe $t$ by a random Poisson variable $\hat{t}$ of expectation $t$. For large $t$, because $|\hat{t}-t|\lesssim\sqrt{t}$ (Central Limit Theorem), this new problem is (almost) equivalent to the initial one.

The good news is that now everything is completly explicite: Indeed the familly $$Y_u =\sum_{s\leq \hat{t}}1_{X_s=u} $$ (ie: the number of tickets of $u\in U$ after $\hat{t}$ drawing) are iid Poisson variable of parameter $\frac{t}{n}$. And then $$\{C_i\subset\{X_1,\cdots,X_{\hat{t}}\}\}=\{\forall u\in C_i:Y_u\geq 1\}$$ are independant (because $C_i$ are disjoint) Bernoulli of parameter $(1-\exp(-\frac{t}{n}))^{|C_i|}$.