Answers are grounded in this paper and cite their sources.
Randomized model shows average time to collect super-coupons, suggesting new insights into coupon dynamics.
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 ( arraycr\\ sarray) ⁻¹( arraycn\\ sarray) log ( arraycn\\ sarray) [(1 + o(1))] on average and has a Gumbel limit after a suitable normalisation. In a similar vein, we show that for any α ∈ (0, 1) , the expected time to collect (1 - α ) -proportion of all super-coupons is ( arraycr\\ sarray) ⁻¹( arraycn\\ sarray) log (1/α )[(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 r/s ( arraycr\\ sarray) ⁻¹( arraycn\\ sarray) log ( arraycn\\ sarray) [(1 + o(1))] time on average to collect all super-coupons.
No takes yet. Share an insight, caveat, or question.
Athreya et al. (2025) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: