On a Generalisation of the Coupon Collector Problem

Siva Athreya (), Satyaki Mukherjee () and Soumendu Sundar Mukherjee ()
Additional contact information
Siva Athreya: International Centre for Theoretical Sciences
Satyaki Mukherjee: National University of Singapore
Soumendu Sundar Mukherjee: Indian Statistical Institute

Journal of Theoretical Probability, 2025, vol. 38, issue 3, 1-20

Abstract: Abstract 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))]$$ r s - 1 n s log n s [ ( 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)$$ α ∈ ( 0 , 1 ) , the expected time to collect $$(1 - \alpha )$$ ( 1 - α ) -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))]$$ r s - 1 n s log ( 1 α ) [ ( 1 + o ( 1 ) ) ] . The $$r = s$$ 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$$ 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$$ 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))]$$ r s r s - 1 n s log n s [ ( 1 + o ( 1 ) ) ] time on average to collect all super-coupons.

Keywords: Generalised coupon collector; Combinatorial probability; Randomly chosen subset; 60C05; 65C05 (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10959-025-01417-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jotpro:v:38:y:2025:i:3:d:10.1007_s10959-025-01417-w

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10959

DOI: 10.1007/s10959-025-01417-w

Access Statistics for this article

Journal of Theoretical Probability is currently edited by Andrea Monica

More articles in Journal of Theoretical Probability from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().