2026-09-22T03:57:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25733 2026-09-05T19:25:28Z ddc:004 open_access

The Careless Coupon Collector’s Problem Cruciani, Emilio Dudeja, Aditi Coupon Collector Markov Chains Metastability 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Emilio Cruciani and Aditi Dudeja 2026 Is Part Of LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2026.14 urn:nbn:de:0030-drops-257333 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.14 eng https://creativecommons.org/licenses/by/4.0/legalcode