The Fragile Coupon Collector: Random Deadlines, Critical Fragility, and Optimal Sampling
- 1Department of Data Science, HIT—Holon Institute of Technology, Holon 5810201, Israel
- 2University of Haifa, Haifa 3498838, Israel
Abstract
We study coupon collection when each type is at risk of disappearing until its first observation, after which it becomes permanently safe. Sampling follows a fixed independent and identically distributed law. For uniform sampling and common fragility, the success probability is the probability-generating function of a pre-discovery exposure statistic. An independent weighted-geometric decomposition gives an exact product, a critical disappearance scale of n−2, and a central limit theorem with a Berry–Esseen bound. For common fragility 0<q<1, the deadline-success probability is strictly Schur-concave on the open probability simplex. For heterogeneous fragilities qi=ci/n2 and sampling probabilities pi=ai/n, we prove a uniform O(n−1) approximation to the actual success probability on a bounded-profile class. For positive fragility profiles uniformly bounded away from zero, this yields an O(n−1) optimality gap for square-root allocation whenever that allocation belongs to the same admissible class. We distinguish this conclusion from exact finite-size optimality and treat zero fragility separately. An independent-exponential continuous-time model provides a benchmark, with a quantified discrepancy from the discrete model.
Related
- Online Packet Scheduling with Deadlines and Learning
- Nested Sampling: A Critical and Comprehensive Theoretical Guide
- A Critical Look at Power Sampling when Test Time Sharpening LLMs
- Overcoming critical slowing down in frustrated spin systems by learned multiscale sampling
- Sampling Uncertainty is Critical for Setting Forecast-Based Anticipatory Action Triggers
BibTeX
@article{kleiner2026fragile,
title = {{The Fragile Coupon Collector: Random Deadlines, Critical Fragility, and Optimal Sampling}},
author = {Igor Kleiner},
journal = {Mathematics},
year = {2026},
month = oct,
doi = {10.3390/math14203729},
url = {https://www.mdpi.com/2227-7390/14/20/3729},
note = {CC BY 4.0},
}
RIS
TY - JOUR
TI - The Fragile Coupon Collector: Random Deadlines, Critical Fragility, and Optimal Sampling
AU - Igor Kleiner
PY - 2026
DA - 2026/10/14
JO - Mathematics
DO - 10.3390/math14203729
UR - https://www.mdpi.com/2227-7390/14/20/3729
AB - We study coupon collection when each type is at risk of disappearing until its first observation, after which it becomes permanently safe. Sampling follows a fixed independent and identically distributed law. For uniform sampling and common fragility, the success probability is the probability-generating function of a pre-discovery exposure statistic. An independent weighted-geometric decomposition gives an exact product, a critical disappearance scale of n−2, and a central limit theorem with a Berry–Esseen bound. For common fragility 0<q<1, the deadline-success probability is strictly Schur-concave on the open probability simplex. For heterogeneous fragilities qi=ci/n2 and sampling probabilities pi=ai/n, we prove a uniform O(n−1) approximation to the actual success probability on a bounded-profile class. For positive fragility profiles uniformly bounded away from zero, this yields an O(n−1) optimality gap for square-root allocation whenever that allocation belongs to the same admissible class. We distinguish this conclusion from exact finite-size optimality and treat zero fragility separately. An independent-exponential continuous-time model provides a benchmark, with a quantified discrepancy from the discrete model.
SN - 2227-7390
ER -