The Careless Coupon Collector's Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910031409053696 |
|---|---|
| author | Cruciani, Emilio Dudeja, Aditi |
| author_facet | Cruciani, Emilio Dudeja, Aditi |
| contents | 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 \textit{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\big(\frac{\ln n}{n^2}\big)$ up to $Θ\big((\frac{np}{1-p})^n\big)$ when $p=ω\big(\frac{1}{n}\big)$ in multiple distinct phases. Interestingly, when $p=\frac{c}{n}$, the process remains in a metastable phase, where the fraction of collected coupon types is concentrated around $\frac{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^2)$ time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_20705 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Careless Coupon Collector's Problem Cruciani, Emilio Dudeja, Aditi Discrete Mathematics Probability 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 \textit{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\big(\frac{\ln n}{n^2}\big)$ up to $Θ\big((\frac{np}{1-p})^n\big)$ when $p=ω\big(\frac{1}{n}\big)$ in multiple distinct phases. Interestingly, when $p=\frac{c}{n}$, the process remains in a metastable phase, where the fraction of collected coupon types is concentrated around $\frac{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^2)$ time. |
| title | The Careless Coupon Collector's Problem |
| topic | Discrete Mathematics Probability |
| url | https://arxiv.org/abs/2602.20705 |