The Careless Coupon Collector’s Problem

Emilio Cruciani, Aditi Dudeja · 2026

Read The Careless Coupon Collector’s Problem by Emilio Cruciani, Aditi Dudeja (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-20705.txt.

Description

Emilio Cruciani and Aditi Dudeja introduce a careless twist on the classic coupon collector, aimed at systems like web crawlers, dynamic caches, and fault-tolerant networks. In their version, a collector gathers n distinct types one random draw at a time, but loses each collected type with chance p at the end of each round.

They analyze how many rounds completion takes in terms of n and p. Completion time shifts across phases, from near-linearithmic growth at tiny loss chances to exponential growth at larger ones. When loss chance equals a constant divided by n, the process stays in a metastable phase. The collected share stays near one over one plus that constant for an exponentially long window. They also give an algorithm computing expected completion time in quadratic steps.

Catalog record

CREATOREmilio Cruciani, Aditi Dudeja
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE51 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-20705

Browse the full library · About the Tower of Babel