We initiate the study of the Careless Coupon Collector’s Problem (CCCP), a novel variation of the classical coupon collector, that we envision as a model for information systems such as web crawlers, dynamic caches, and fault-resilient networks. In CCCP, a collector attempts to gather n distinct coupon types by obtaining one coupon type uniformly at random in each discrete round, however the collector is careless: at the end of each round, each collected coupon type is independently lost with probability p. We analyze the number of rounds required to complete the collection as a function of n and p. In particular, we show that it transitions from Θ (n ln n) when p = o ( (ln n) /n²) up to Θ ( ( (np) / (1-p) ) ⁿ) when p = ω (1/n) in multiple distinct phases. Interestingly, when p = c/n, the process remains in a metastable phase, where the fraction of collected coupon types is concentrated around 1/ (1+c) with probability 1-o (1), for a time window of length e^Θ (n). Finally, we give an algorithm that computes the expected completion time of CCCP in O (n²) time.
Cruciani et al. (Thu,) studied this question.