arxiv: 2605.09641 · v1 · submitted 2026-05-10 · 🧮 math.PR · math.CO

Recognition: 2 theorem links

· Lean Theorem

The Ballot Event for Two-Player Coupon Collection: A Renewal--Catalan Asymptotic

Christopher D. Long

Pith reviewed 2026-05-12 04:13 UTC · model grok-4.3

classification 🧮 math.PR math.CO

keywords coupon collectorballot problemrenewal theoryCatalan numbersgambler's ruinasymptoticstwo-player competitionprobability

0 comments

The pith

The probability that the eventual winner in two-player coupon collection was never behind is asymptotically 2/d as d grows large.

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

This paper examines the ballot-type event in a two-player coupon collector game where each player draws one coupon per round from a set of d types. It establishes that the probability b_d of the eventual winner having never trailed satisfies b_d ∼ 2/d as d tends to infinity. The proof decomposes the process via renewal at tie boundaries, shows that the first one-sided lead has an entrance law whose sqrt(d)-scaled height converges to a Rayleigh distribution, and approximates the subsequent survival probability by a Catalan or gambler's-ruin harmonic whose defect in the exact simultaneous chain is negligible. A sympathetic reader would care because this resolves an open question on the asymptotic frequency of a never-trailing path in a classic discrete competition model.

Core claim

The probability b_d that the ultimate winner in the two-player coupon collector was never behind satisfies b_d ∼ 2/d as d → ∞. This follows from a renewal decomposition at the tie boundary: the first one-sided tie-break admits an explicit entrance distribution whose level scaled by d^{1/2} converges to a Rayleigh law, after which the leader's survival is governed by a Catalan or gambler's-ruin harmonic, with the accumulated defect of this comparison in the exact chain shown to be negligible.

What carries the argument

Renewal decomposition at the tie boundary, using the explicit entrance distribution of the first one-sided tie-break whose scaled height converges to a Rayleigh law and the Catalan/gambler's-ruin harmonic that governs subsequent survival with negligible defect.

If this is right

The ballot probability decays exactly as 2/d for large d.
The height of the first lead after a tie, when scaled by sqrt(d), converges in distribution to a Rayleigh law.
After the first break the leader's survival probability is asymptotically given by the gambler's-ruin harmonic with an error small enough to preserve the overall 2/d asymptotic.

Where Pith is reading between the lines

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

The same renewal-plus-Rayleigh-plus-Catalan structure may apply to ballot events in other simultaneous random-walk or urn models with symmetric steps.
The 2/d rate supplies a concrete benchmark for testing fairness or dominance in discrete competitive collection processes used in algorithms or game design.
Numerical verification of the convergence rate for moderate d would be straightforward and could quantify the approach to the asymptotic.

Load-bearing premise

The accumulated defect between the Catalan/gambler's-ruin harmonic and the exact discrete simultaneous-round chain remains negligible after the first one-sided tie-break.

What would settle it

Direct computation or Monte Carlo simulation of b_d for a sequence of large d values (for example d = 500 and d = 2000) to check whether b_d multiplied by d converges to 2 within a bounded error.

read the original abstract

We study the two-player coupon-collector competition in which two independent collectors draw one coupon each per round from a set of $d$ equally likely coupon types. Myers and Wilf gave finite formulae for several two-player events and explicitly left open the ballot-type problem of finding the probability that the ultimate winner was never behind. We prove that this probability satisfies $$ b_d \sim \frac{2}{d}, \qquad d\to\infty .$$ The proof uses a renewal decomposition at the tie boundary. The first one-sided tie-break has an explicit entrance distribution; its level, scaled by $d^{1/2}$, converges to a Rayleigh law; and, after the break, the leader's survival probability is governed by a Catalan, or gambler's-ruin, harmonic. The main estimate shows that the accumulated defect of this comparison harmonic in the exact simultaneous-round chain is negligible.

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

Long closes the Myers-Wilf ballot asymptotic with a renewal-Rayleigh-Catalan argument that pins down the constant 2/d.

read the letter

Long has settled the open ballot question from Myers and Wilf. In the two-player coupon collector with d types, the probability that the eventual winner was never behind is asymptotically 2/d as d grows large. The proof decomposes the process at ties, tracks the first one-sided break with an explicit entrance distribution whose scaled height converges to Rayleigh, and then uses the Catalan harmonic to bound the leader's survival probability afterward. The main technical step is showing that the total defect from replacing the exact chain with the harmonic stays small enough to preserve the leading term. This approach is new for the simultaneous-draw setting and avoids extra parameters or fitted constants. The renewal decomposition fits the tie structure naturally, and the standard limits are applied without circularity. The argument is self-contained once the defect estimate is in place. The load-bearing piece is precisely that negligibility claim after the Rayleigh-scaled break. If the paper's bound on the accumulated error is rigorous and of the right order, the asymptotic follows directly; any larger error would change the constant. The abstract states they establish this, so the result stands or falls on those calculations rather than on any hidden assumption. This work is for people already working in probabilistic combinatorics or coupon-collector variants. A reader who cares about ballot problems, renewal methods on discrete chains, or Catalan-type harmonics will find the strategy useful and worth checking in detail. It is narrow in scope but cleanly targeted at a specific open question. It deserves a serious referee. The explicit resolution of a stated open problem plus the coherent use of external tools makes it worth the time to verify the defect estimate. Recommendation: send it to review rather than desk reject.

Referee Report

1 major / 3 minor

Summary. The manuscript proves that the ballot probability b_d in the two-player coupon-collector process (two independent collectors drawing one coupon each per round from d types) satisfies b_d ∼ 2/d as d → ∞. The argument decomposes the process via renewal at ties, derives an explicit entrance distribution for the first one-sided tie-break whose d^{1/2}-scaled height converges to a Rayleigh law, and shows that the leader's survival probability equals the Catalan/gambler's-ruin harmonic plus a defect whose accumulated contribution is negligible.

Significance. If the central estimates hold, the result resolves an open ballot-type question left by Myers and Wilf with a clean, parameter-free asymptotic. The proof combines renewal theory, Rayleigh convergence, and Catalan harmonics in a self-contained manner without circular definitions or fitted parameters; the explicit entrance law and negligibility estimate are technically substantive and could extend to related competition models.

major comments (1)

[§5] §5 (Main defect estimate): the claim that the accumulated defect between the exact simultaneous-draw chain and the Catalan harmonic is o(1) after the Rayleigh-scaled tie-break is load-bearing for the constant 2/d. The current argument bounds the per-step discrepancy but does not explicitly control the total variation over the random number of post-break steps (which can be order d); an explicit rate such as O(d^{-1/2+ε}) integrated against the Rayleigh density is needed to confirm the error remains o(1) and does not alter the leading term.

minor comments (3)

[§2] §2, notation for the tie-break entrance law: the transition probabilities are written with an implicit conditioning on the first tie; adding a displayed equation for the exact entrance measure would improve readability.
[Figure 1] Figure 1 (Rayleigh convergence plot): the x-axis scaling is not labeled with the precise d^{1/2} factor; this makes visual comparison to the limiting density harder.
[Introduction] References: Myers and Wilf (2003) is cited in the introduction but the precise statement of their open problem is not quoted; including the exact quote would clarify the contribution.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for identifying the load-bearing nature of the defect estimate in §5. We agree that an explicit rate for the accumulated error is needed to fully substantiate the o(1) claim and the leading 2/d asymptotic. We will strengthen this section accordingly.

read point-by-point responses

Referee: [§5] §5 (Main defect estimate): the claim that the accumulated defect between the exact simultaneous-draw chain and the Catalan harmonic is o(1) after the Rayleigh-scaled tie-break is load-bearing for the constant 2/d. The current argument bounds the per-step discrepancy but does not explicitly control the total variation over the random number of post-break steps (which can be order d); an explicit rate such as O(d^{-1/2+ε}) integrated against the Rayleigh density is needed to confirm the error remains o(1) and does not alter the leading term.

Authors: We agree that the current per-step bound alone is insufficient to control the accumulated defect over a random number of steps of order d. We will revise §5 to supply an explicit rate: the per-step discrepancy is O(d^{-1}) in expectation (arising from the 1/d probability of simultaneous draws and the renewal structure), and we will apply a concentration argument (or direct integration against the Rayleigh density, which has finite moments) to show that the total accumulated error is O(d^{-1/2} log d) with high probability and hence o(1) uniformly. This will be added as a new lemma or proposition without changing the main result or the 2/d asymptotic. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation uses independent renewal theory, Rayleigh convergence, and Catalan harmonics with a proved negligibility estimate.

full rationale

The paper decomposes the ballot probability via renewal at ties, derives an explicit entrance law whose scaled height converges to Rayleigh (external), applies the Catalan/gambler's-ruin harmonic (standard), and proves the accumulated defect between this harmonic and the exact chain is negligible as d→∞. None of these steps reduce the target asymptotic 2/d to a fitted parameter, self-definition, or self-citation chain; the negligibility is established by direct estimate rather than by construction. The argument is self-contained against external benchmarks (renewal theory, diffusion limits, discrete harmonic functions) with no load-bearing reduction to the paper's own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The proof rests on standard renewal theory, convergence to Rayleigh distribution, and properties of Catalan/gambler's-ruin harmonics. No free parameters are fitted to data and no new entities are postulated.

axioms (2)

standard math Standard properties of renewal processes at tie boundaries and convergence of the scaled first one-sided tie-break level to a Rayleigh law.
Invoked to obtain the entrance distribution after the first tie.
domain assumption The leader's survival probability after the tie-break is governed by the Catalan (gambler's-ruin) harmonic function.
Used to control the probability that the leader stays ahead until absorption.

pith-pipeline@v0.9.0 · 5446 in / 1507 out tokens · 53527 ms · 2026-05-12T04:13:58.568926+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

3 extracted references · 3 canonical work pages

[1]

I, 3rd ed., John Wiley & Sons, New York, 1968

William Feller,An Introduction to Probability Theory and Its Applications, Vol. I, 3rd ed., John Wiley & Sons, New York, 1968

work page 1968
[2]

3, 300–321

Ira Gessel and G´ erard Viennot, Binomial determinants, paths, and hook length formulae, Advances in Mathematics58(1985), no. 3, 300–321. DOI: 10.1016/0001-8708(85)90121-5. 20

work page doi:10.1016/0001-8708(85)90121-5 1985
[3]

Myers and Herbert S

Amy N. Myers and Herbert S. Wilf, Some new aspects of the coupon-collector’s problem,SIAM Journal on Discrete Mathematics17(2003), no. 1, 1–17. DOI: 10.1137/S0895480102403076; arXiv:math/0304229. 21

work page doi:10.1137/s0895480102403076 2003