The Expiring Coupon Collector: Sliding-Window Surjection Flux and Rare-Entry Laws
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910176419774464 |
|---|---|
| author | Long, Christopher D. |
| author_facet | Long, Christopher D. |
| contents | We study the coupon collector with deterministic expiration: one coupon is drawn at each time, and each coupon remains active for exactly $M$ draws. Completion occurs when all $n$ coupon types are simultaneously active. Equivalently, the current length-$M$ sliding window of draws must contain all $n$ types.
The central object is not the one-time probability that a random window is onto, but the stationary flux of new entries into the onto-window set. We compute this flux exactly: \[
μ_{n,M}
=\Pbb(W_{t-1}\text{ is not onto},\ W_t\text{ is onto})
=\frac{(n-1)(n-1)!S(M-1,n-1)}{n^M}, \] where $S(\cdot,\cdot)$ denotes a Stirling number of the second kind. Under a quantitative subcritical separation condition, satisfied in particular by every fixed integer scale $M=\floor{αn\log n}$, $0<α<1$, we prove local declumping and obtain \[
μ_{n,M}T_{n,M}\Rightarrow \Exp(1). \] For the fixed subcritical scale $M=\floor{αn\log n}$, $0<α<1$, this gives the logarithmic scale \[
\log T_{n,M}=n^{1-α}+o_{\mathbb P}(n^{1-α}),
\qquad
\log \Ebb T_{n,M}=n^{1-α}+o(n^{1-α}), \] and, when $α>1/2$, the sharper normalization \[
n^{-α}e^{-n^{1-α}}T_{n,M}\Rightarrow \Exp(1),
\qquad
\Ebb T_{n,M}\sim n^αe^{n^{1-α}}. \] Thus the leading scale proposed in the Math StackExchange discussion is made rigorous; the exact finite-$n$ flux gives the canonical normalization throughout the subcritical range. The result is a sliding-window companion to rare-void entry-flux methods for nonmonotone coupon collectors. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_26298 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Expiring Coupon Collector: Sliding-Window Surjection Flux and Rare-Entry Laws Long, Christopher D. Probability Combinatorics 60C05, 60F05, 60G70, 60E15 We study the coupon collector with deterministic expiration: one coupon is drawn at each time, and each coupon remains active for exactly $M$ draws. Completion occurs when all $n$ coupon types are simultaneously active. Equivalently, the current length-$M$ sliding window of draws must contain all $n$ types. The central object is not the one-time probability that a random window is onto, but the stationary flux of new entries into the onto-window set. We compute this flux exactly: \[ μ_{n,M} =\Pbb(W_{t-1}\text{ is not onto},\ W_t\text{ is onto}) =\frac{(n-1)(n-1)!S(M-1,n-1)}{n^M}, \] where $S(\cdot,\cdot)$ denotes a Stirling number of the second kind. Under a quantitative subcritical separation condition, satisfied in particular by every fixed integer scale $M=\floor{αn\log n}$, $0<α<1$, we prove local declumping and obtain \[ μ_{n,M}T_{n,M}\Rightarrow \Exp(1). \] For the fixed subcritical scale $M=\floor{αn\log n}$, $0<α<1$, this gives the logarithmic scale \[ \log T_{n,M}=n^{1-α}+o_{\mathbb P}(n^{1-α}), \qquad \log \Ebb T_{n,M}=n^{1-α}+o(n^{1-α}), \] and, when $α>1/2$, the sharper normalization \[ n^{-α}e^{-n^{1-α}}T_{n,M}\Rightarrow \Exp(1), \qquad \Ebb T_{n,M}\sim n^αe^{n^{1-α}}. \] Thus the leading scale proposed in the Math StackExchange discussion is made rigorous; the exact finite-$n$ flux gives the canonical normalization throughout the subcritical range. The result is a sliding-window companion to rare-void entry-flux methods for nonmonotone coupon collectors. |
| title | The Expiring Coupon Collector: Sliding-Window Surjection Flux and Rare-Entry Laws |
| topic | Probability Combinatorics 60C05, 60F05, 60G70, 60E15 |
| url | https://arxiv.org/abs/2604.26298 |