1
$\begingroup$

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).

$\endgroup$
6
  • 1
    $\begingroup$ Computationally speaking, getting the expectation is a fairly straightforward task with renewal theory that ultimately boils down to an inhomogeneous linear system. Doing this on some cases for the vector $(|C_1|,\dots,|C_n|)$ might give you some insight into e.g. scaling relationships. $\endgroup$
    – Ian
    Dec 10, 2020 at 18:29
  • $\begingroup$ @Ian Can you expand a bit on what you mean ? This is something I am not familiar with. $\endgroup$
    – GBathie
    Dec 10, 2020 at 18:31
  • 1
    $\begingroup$ One can treat this process as a Markov chain on the power set of $U$ where at each time you go from $s$ to $s \cup \{ x \}$ where $x$ is chosen uniformly at random. Of course you don't care about duplicates, so in some cases $s \cup \{ x \} = s$. By conditioning on one step, you can calculate $u(s):=E[T \mid S_0=s]=1+\frac{1}{n} \sum_{x \in U} E[T \mid S_0=s \cup \{ x \}]$ if $s$ does not contain a collection, and $u(s)=0$ if $s$ does contain a collection. This is a system of $2^n$ linear equations in $2^n$ unknowns which you can solve. $\endgroup$
    – Ian
    Dec 10, 2020 at 19:01
  • 1
    $\begingroup$ Now this particular problem has some structure that you can exploit. In particular, you can write a version of the system without self-loops Once you prune the self-loops by replacing that $1$ with $\frac{n}{n-|s|}$ and replacing $x \in U$ with $x \in U \setminus s$. Now the graph that you are moving on is a tree, leaving some more hope of an analytical solution of some kind. $\endgroup$
    – Ian
    Dec 10, 2020 at 19:05
  • $\begingroup$ (You also need to replace $\frac{1}{n}$ with $\frac{1}{n-|s|}$, my bad.) $\endgroup$
    – Ian
    Dec 10, 2020 at 19:18

3 Answers 3

2
$\begingroup$

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).

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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|}$.

$\endgroup$
1
  • $\begingroup$ Could you add details to your answer ? I don't understand what $Y_u$ is here. $\endgroup$
    – GBathie
    Dec 17, 2020 at 11:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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