On a Generalisation of the Coupon Collector Problem

We consider a generalisation of the classical coupon collector problem. We define a super-coupon to be any s-subset of a universe of n coupons. In each round, a random r-subset from the universe is drawn and all its s-subsets are marked as collected. We show that the time to collect all super-coupons is $$\left( {\begin{array}{c}r\\ s\end{array}}\right) ^{-1}\left( {\begin{array}{c}n\\ s\end{array}}\right) \log \left( {\begin{array}{c}n\\ s\end{array}}\right) [(1 + o(1))]$$ on average and has a Gumbel limit after a suitable normalisation. In a similar vein, we show that for any $$\alpha \in (0, 1)$$ , the expected time to collect $$(1 - \alpha )$$ -proportion of all super-coupons is $$\left( {\begin{array}{c}r\\ s\end{array}}\right) ^{-1}\left( {\begin{array}{c}n\\ s\end{array}}\right) \log \big (\frac{1}{\alpha }\big )[(1 + o(1))]$$ . The $$r = s$$ case of this model is equivalent to the classical coupon collector model. We also consider a temporally dependent model where the r-subsets are drawn according to the following Markovian dynamics: the r-subset at round $$k + 1$$ is formed by replacing a random coupon from the r-subset drawn at round k with another random coupon from outside this r-subset. We link the time it takes to collect all super-coupons in the $$r = s$$ case of this model to the cover time of random walk on a certain finite regular graph and conjecture that in general, it takes $$\frac{r}{s} \left( {\begin{array}{c}r\\ s\end{array}}\right) ^{-1}\left( {\begin{array}{c}n\\ s\end{array}}\right) \log \left( {\begin{array}{c}n\\ s\end{array}}\right) [(1 + o(1))]$$ time on average to collect all super-coupons.