arxiv: 2604.26298 · v1 · submitted 2026-04-29 · 🧮 math.PR · math.CO

Recognition: unknown

The Expiring Coupon Collector: Sliding-Window Surjection Flux and Rare-Entry Laws

Christopher D. Long

Authors on Pith no claims yet

Pith reviewed 2026-05-07 13:03 UTC · model grok-4.3

classification 🧮 math.PR math.CO

keywords coupon collectorsliding windowsurjective sequencesStirling numberswaiting time asymptoticsrare-event limitsexponential convergence

0 comments

The pith

The exact flux of new surjective sliding windows equals (n-1)(n-1)!S(M-1,n-1)/n^M and normalizes the waiting time to Exp(1) when M grows like α n log n for α<1.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper computes the stationary rate at which a random sequence first produces an M-window containing every one of n coupon types. It shows that this rate, when multiplied by the waiting time until the first such window appears, converges in distribution to a standard exponential under a subcritical growth condition on M. A reader would care because the result turns an intuitive scaling guess into an exact normalization that works throughout the regime M = floor(α n log n) for any fixed α between 0 and 1.

Core claim

The paper computes the stationary probability flux μ_{n,M} into the set of surjective M-windows exactly as (n-1)(n-1)! S(M-1,n-1) / n^M. Under the quantitative subcritical separation condition on M relative to n, satisfied in particular by every fixed integer scale M = floor(α n log n) for 0<α<1, it proves local declumping and obtains μ_{n,M} T_{n,M} ⇒ Exp(1). This yields the logarithmic scale log T_{n,M} = n^{1-α} + o_P(n^{1-α}) and, when α>1/2, the sharper normalization n^{-α} e^{-n^{1-α}} T_{n,M} ⇒ Exp(1).

What carries the argument

The stationary flux of new entries into the onto-window set, computed exactly via Stirling numbers of the second kind as the probability that a non-onto window is immediately followed by an onto window.

If this is right

When M equals floor(α n log n) for fixed α in (0,1), the waiting time satisfies log T_{n,M} = n^{1-α} plus a term that is o_p of that scale.
The expectation E[T_{n,M}] obeys the same leading asymptotic n^{1-α}.
For α greater than 1/2 the sharper scaled version n^{-α} exp(-n^{1-α}) T converges in distribution to Exp(1) with expectation asymptotic to n^α exp(n^{1-α}).
The exact finite-n flux supplies the canonical normalization for the waiting time throughout the entire subcritical range.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same flux calculation may supply normalizations for waiting times in other sliding-window versions of classic covering problems.
Numerical checks of the exponential limit could be performed for α values close to the boundary 1 to test the sharpness of the separation condition.
The approach offers a template for deriving entry rates in non-monotone or window-constrained random processes where direct hitting probabilities are intractable.

Load-bearing premise

A quantitative subcritical separation condition must hold between the window length M and the number of types n so that successive entries into the surjective state remain locally separated in time.

What would settle it

For concrete n=200 and α=0.6, generate many independent realizations of the process, compute the empirical distribution of μ_{n,M} T, and check whether it matches the cdf of a standard exponential to within sampling error.

read the original abstract

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: \[ \mu_{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{\alpha n\log n}$, $0<\alpha<1$, we prove local declumping and obtain \[ \mu_{n,M}T_{n,M}\Rightarrow \Exp(1). \] For the fixed subcritical scale $M=\floor{\alpha n\log n}$, $0<\alpha<1$, this gives the logarithmic scale \[ \log T_{n,M}=n^{1-\alpha}+o_{\mathbb P}(n^{1-\alpha}), \qquad \log \Ebb T_{n,M}=n^{1-\alpha}+o(n^{1-\alpha}), \] and, when $\alpha>1/2$, the sharper normalization \[ n^{-\alpha}e^{-n^{1-\alpha}}T_{n,M}\Rightarrow \Exp(1), \qquad \Ebb T_{n,M}\sim n^\alpha e^{n^{1-\alpha}}. \] 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper delivers a clean exact formula for the stationary flux into surjective windows and a rigorous exponential limit for the waiting time under subcritical expiration.

read the letter

The standout piece is the closed-form expression for the flux μ_{n,M} = (n-1)(n-1)! S(M-1,n-1)/n^M, obtained by direct counting of the transitions where the prior window misses exactly one type. This is new relative to standard coupon-collector results and gives an explicit rate without approximation. The stress-test confirms it matches small cases like n=2,M=2 and n=3,M=2, so the combinatorics checks out. They then prove local declumping under the quantitative subcritical condition on M, yielding μ T ⇒ Exp(1) and the logarithmic asymptotics log T = n^{1-α} + o_P(n^{1-α}) for M = floor(α n log n), α<1. The sharper normalization when α>1/2 follows naturally once the leading scale is fixed. These steps align with the usual Poisson approximation for the number of missing types in a window, and the declumping condition is the standard one that isolates the rare entries. No internal contradictions appear. The only minor soft spot is that the o terms in the asymptotics will need careful error control in the full proof, but nothing load-bearing looks shaky. This is for specialists in discrete probability who work on coupon-collector variants or sliding-window rare events; a reader wanting explicit rates or justification of StackExchange heuristics will find it useful. It deserves peer review because the claims are specific, the combinatorial step is verifiable, and the limiting argument rests on established rare-event techniques.

Referee Report

0 major / 3 minor

Summary. The paper examines the coupon collector process with deterministic expiration after M steps, equivalent to requiring that every length-M sliding window of draws is a surjection onto n types. The central contribution is an exact closed-form expression for the stationary flux μ_{n,M} = P(W_{t-1} not onto and W_t onto) = (n-1)(n-1)! S(M-1,n-1)/n^M. Under an explicit quantitative subcritical separation condition on M relative to n (satisfied by M = ⌊α n log n⌋ for fixed α ∈ (0,1)), the authors establish local declumping of entry events and prove that μ_{n,M} T_{n,M} converges in distribution to Exp(1). They further derive the logarithmic scale log T_{n,M} = n^{1-α} + o_P(n^{1-α}), the expectation asymptotics, and a sharper normalization n^{-α} exp(-n^{1-α}) T_{n,M} ⇒ Exp(1) when α > 1/2.

Significance. If the exact flux formula and the declumping argument hold, the work supplies a parameter-free combinatorial expression together with rigorous rare-event limits for sliding-window surjection waiting times. This furnishes a direct companion to existing flux-based analyses of non-monotone coupon collectors and confirms the leading scale proposed in earlier heuristic discussions. The explicit verification for small (n,M) pairs and the matching with Poisson approximation for the number of missing types constitute concrete strengths.

minor comments (3)

The notation Pbb and Ebb (and the corresponding blackboard-bold symbols) should be defined at first use or replaced by standard mathbb{P} and mathbb{E} for consistency with the target journal's style.
The reference to the Math StackExchange discussion in the abstract and introduction should be supplemented by a precise URL or arXiv-style citation so that readers can locate the heuristic being rigorized.
In the statement of the sharper normalization for α > 1/2, the precise meaning of the o_P term (with respect to which probability measure) could be stated explicitly in the theorem.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading and positive assessment of the manuscript. The recommendation for minor revision is appreciated, and we will address any editorial or minor points in the revised version. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The central flux formula is obtained by direct combinatorial enumeration of the probability that a length-M window transitions from non-surjective to surjective, using the explicit expression involving Stirling numbers of the second kind. This matches independent small-case verification (n=2,M=2 yields 1/4; etc.) and is not defined in terms of the target waiting time T_{n,M}. The convergence μ_{n,M} T_{n,M} ⇒ Exp(1) and the logarithmic asymptotics are obtained via standard rare-event Poisson approximation and local declumping under the stated quantitative subcritical separation condition on M relative to n; these steps invoke no fitted parameters, no self-citation chains, and no renaming of known results as new derivations. The argument remains independent of the claimed limits throughout the subcritical range.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper introduces no free parameters or invented entities; it relies on standard probabilistic assumptions and combinatorial identities.

axioms (2)

domain assumption Draws are i.i.d. uniform over the n coupon types
Fundamental modeling assumption used to define the process and derive the flux probability.
domain assumption Existence of a stationary distribution for the sliding-window process
Invoked to define the stationary flux μ_{n,M} as a time-independent probability.

pith-pipeline@v0.9.0 · 5709 in / 1361 out tokens · 98611 ms · 2026-05-07T13:03:37.547405+00:00 · methodology

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Clumsy and Careless: Stationary-Entry Flux in Non-monotone Coupon Collectors
math.PR 2026-05 unverdicted novelty 6.0

Stationary-entry flux yields exponential hitting laws for clumsy and careless non-monotone coupon collectors, with explicit asymptotic flux formulas replacing the usual Gumbel scale.

Reference graph

Works this paper leans on

8 extracted references · cited by 1 Pith paper

[1]

Expiring coupon collector’s problem

mjqxxxx. Expiring coupon collector’s problem. Mathematics Stack Exchange, question posted August 30, 2012. Available online

2012
[2]

Expiring coupon collector’s problem

Joriki. Answer to “Expiring coupon collector’s problem.” Mathematics Stack Exchange, answered October 11, 2012; edited April 13, 2017. Available online

2012
[3]

Erd˝ os and A

P. Erd˝ os and A. R´ enyi. On a classical problem of probability theory.Magyar Tud. Akad. Mat. Kutat´ o Int. K¨ ozl.6 (1961), 215–220

1961
[4]

Feller.An Introduction to Probability Theory and Its Applications, Vol

W. Feller.An Introduction to Probability Theory and Its Applications, Vol. I. Third edition. John Wiley & Sons, New York, 1968

1968
[5]

Dubhashi and D

D. Dubhashi and D. Ranjan. Balls and bins: a study in negative dependence.Random Structures & Algorithms13(2) (1998), 99–124

1998
[6]

V. V. Petrov.Sums of Independent Random Variables. Translated from the Russian by A. A. Brown. Ergebnisse der Mathematik und ihrer Grenzgebiete, Vol. 82. Springer-Verlag, Berlin–Heidelberg–New York, 1975

1975
[7]

N. M. Temme. Asymptotic estimates of Stirling numbers.Studies in Applied Mathematics89(3) (1993), 233–243

1993
[8]

Christopher D. Long. Clumsy and careless: rare-void hitting in nonmonotone coupon collectors. Manuscript in preparation, 2026. 27

2026