Pith. sign in

REVIEW 4 minor 37 references

When discovery rates and weights share a Zipf law, the time to accumulate a fixed weight threshold splits into three asymptotic regimes controlled by the exponent.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-10 05:30 UTC pith:4VPVOTUV

load-bearing objection Clean three-regime Zipf analysis for weighted-threshold coupon collection; solid math, limited but honest scope.

arxiv 2607.08551 v1 pith:4VPVOTUV submitted 2026-07-09 math.PR

Weighted-threshold Coupon Collection

Sebastian M\"uller , Stjepan \v{S}ebek This is my paper
classification math.PR MSC 68M1494A2091A20
keywords generalized coupon collectorweighted quorumquorum formationZipf lawmissing massconcentration inequalitiesdistributed systems
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper studies a continuous-time coupon collector that stops not when every type is seen, but when the total weight of distinct discovered types first exceeds a fixed threshold. Under equal discovery rates and vanishing maximum weight, that quorum time is asymptotically universal: it grows linearly with the number of types and depends only on the threshold and the common rate, not on how the weights are shaped. When rates and weights are aligned in a Zipf (power-law) family, the picture changes with the exponent. Mild concentration keeps a deterministic linear scale; a critical exponent produces the scale H_N N^θ with an explicit constant involving Euler’s constant; strong concentration leaves a non-degenerate random hitting time of an infinite weighted process. Expected waiting time need not be monotone in the Zipf exponent, already for two types. The results matter for any system that forms a quorum by accumulating stake, reputation, or voting weight rather than counting participants equally.

Core claim

Concentration of the discovered-mass process around its mean yields a law of large numbers for the quorum time whenever weights are diffuse. Homogeneous clocks give the universal limit −log(1−θ)/λ independent of the weight vector. For the aligned Zipf family p_i = w_i ∝ i^{−s} the first-order asymptotics split into three regimes: deterministic linear scale for 0 ≤ s < 1, critical scale H_N N^θ with leading constant e^{(θ−2)γ}/λ at s = 1, and almost-sure (and L^1) convergence to a non-degenerate random hitting time for s > 1. Expected quorum time is not monotone in s even for N = 2.

What carries the argument

The discovered-mass process M_N(t) = ∑ w_i 1_{T_i ≤ t} and its mean profile m_N(t). Bernstein concentration of M_N around m_N converts mean-profile convergence into a law of large numbers for the quorum time τ_{N,θ}; in the atomic Zipf regime the same process converges to an infinite weighted Bernoulli sum whose closed hitting time is the limit.

Load-bearing premise

The sharp three-regime analysis and the non-monotonicity example are proved only when discovery rates and weights are exactly the same Zipf sequence; the paper does not establish analogous scales when the two profiles differ.

What would settle it

Simulate the aligned Zipf model for large N at s = 1 and check whether τ_N,θ/(H_N N^θ) concentrates near e^{(θ−2)γ}/λ; a systematic deviation for moderate θ would refute the critical-regime claim.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Under homogeneous activity and vanishing max weight, weight heterogeneity has no first-order effect on quorum time.
  • Aligning activity with Zipf weights changes both the scale and the randomness of confirmation times.
  • Sufficient weight concentration leaves the discovery times of a few heavy types visible in the limit, so growing the number of participants does not remove intrinsic randomness.
  • Expected quorum time can rise then fall with the Zipf exponent, so more heterogeneous systems are not always slower or faster.
  • At the critical exponent the leading scale is H_N N^θ with explicit constant e^{(θ−2)γ}/λ.

Where Pith is reading between the lines

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

  • Misaligned profiles (heavy weight on rarely active types) would likely produce larger delays and different critical scales than the aligned Zipf case.
  • The N = 2 non-monotonicity suggests intermediate Zipf exponents may extremize expected quorum time in larger systems, which is directly checkable by simulation.
  • The same mean-profile-plus-concentration method should extend to regularly varying weights beyond pure Zipf.
  • In weighted-voting or stake systems, the atomic regime implies confirmation latency stays random as the network grows if weight is sufficiently concentrated.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The paper studies a continuous-time weighted-threshold coupon collector in which type i is discovered at rate λ p_i and contributes weight w_i; the quorum time τ_{N,θ} is the first time the discovered weight exceeds a fixed θ ∈ (0,1). After Bernstein concentration and comparison of τ_{N,θ} to the inverse of the mean profile m_N(t), it proves a universal first-order limit τ_{N,θ}/N o -log(1-θ)/λ under homogeneous clocks and diffuse weights. For the aligned Zipf family p_i = w_i ∝ i^{-s} it establishes three regimes: deterministic linear scale with explicit integral equation for 0 ≤ s < 1, critical scale H_N N^θ with leading constant e^{(θ-2)γ}/λ at s = 1, and almost-sure (and L^1) convergence to the random hitting time of an infinite weighted Bernoulli process for s > 1. An exact N = 2 calculation shows that expected quorum time need not be monotone in the Zipf exponent.

Significance. The work cleanly extends classical coupon-collector analysis to a weighted-threshold stopping rule that arises in quorum systems, weighted voting and missing-mass problems. The three-regime classification for aligned Zipf is sharp, self-contained and fully rigorous: Riemann-sum convergence of the mean profile plus Bernstein comparison (Theorems 3.6 and 5.3), harmonic expansions with explicit Euler-constant corrections and Chebyshev (Lemmas 6.1–6.2, Theorem 6.3), and pathwise continuity-point transfer under coupling for the atomic limit (Proposition 7.1, Theorem 7.4, Corollary 7.5). The N = 2 non-monotonicity example is exact and elementary. These results supply concrete scales, constants and a diffuse/atomic dichotomy that are immediately usable for modelling and for further asymptotic work; the proofs rely only on standard tools and are free of circular fitting.

minor comments (4)
  1. In the statement of Theorem 5.5 the critical threshold is written θ_c := 1 - e^{-2}; it would help the reader to recall immediately that this is the point where α_{0,θ} = 2, so the sign of the second-order correction changes.
  2. Section 7 introduces the common coupling via i.i.d. Exp(1) variables E_i; a one-sentence reminder that the same sequence is used for both the finite-N and infinite processes would make the almost-sure statement of Theorem 7.4 even more transparent.
  3. Several recent arXiv preprints appear in the related-work list with 2026 dates; if any have since been published, updating the bibliographic data would be useful, though this is purely cosmetic.
  4. In the display after (6.1) the o(1) terms are controlled carefully, but a brief remark that the same argument yields a full asymptotic expansion of m_N^{(1)}(t_N) to any order in 1/H_N would be a low-cost addition for readers interested in finer asymptotics.

Circularity Check

0 steps flagged

No circularity: self-contained probabilistic derivations from independent Exp clocks, Bernstein concentration, and classical harmonic/zeta expansions; no fitted parameters or load-bearing self-citations.

full rationale

The paper derives all claimed limits from the model definition (independent Exp(λ p_i) discovery times, discovered-mass process M_N(t) as weighted sum of Bernoullis) via standard tools: Bernstein inequality for concentration (Thm 3.3), comparison of τ_{N, heta} to the mean-profile root t_{N, heta} (Thm 3.4), and a general diffuse LLN (Thm 3.6). Homogeneous-clock universality follows because m_N(t)=1-e^{-λ t/N} is independent of w under diffuseness. Aligned Zipf regimes use Riemann-sum convergence of the mean profile to an explicit integral (s<1), harmonic expansions yielding SN=log A_N+2γ+o(1) plus O(1/(H_N^{2} N^ heta)) variance (s=1), and a.s./L^{1} coupling of finite-N processes to the infinite atomic process with continuity-point transfer of hitting times (s>1). The N=2 non-monotonicity is an exact closed-form calculation. Euler’s γ and ζ(s) enter as classical constants forced by the expansions, not free parameters. No data fitting, no prediction-equals-fit structure, and no load-bearing self-citation or uniqueness import; related-work citations are background only. The derivation chain is independent of its outputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 2 invented entities

The paper is a pure-probability asymptotic analysis. It imports standard concentration and Poissonization tools and defines model objects (quorum time, diffuse/atomic weights) without free fitted constants. No new physical entities are postulated; Zipf alignment is a modeling choice, not a free parameter fit.

axioms (5)
  • domain assumption Independent Poisson discovery clocks of rates λ p_i (equivalently independent Exp(λ p_i) discovery times).
    Section 2 model definition; continuous-time Poissonization of coupon collection.
  • standard math Bernstein’s inequality for bounded independent centered summands (Boucheron–Lugosi–Massart Thm 2.10).
    Invoked in Theorem 3.3 to control M_N(t) − m_N(t).
  • standard math Harmonic-number expansion H_m = log m + γ + O(1/m) and integrability of e^{−u} log u.
    Used in Lemma 6.1 for the critical s = 1 mean asymptotics.
  • domain assumption Diffuse weights: max_i w_i → 0 as N → ∞ (Definition 3.1).
    Load-bearing for the law of large numbers in Theorems 3.6 and 4.1; without it the limit need not be deterministic.
  • ad hoc to paper Aligned Zipf: p_i = w_i ∝ i^{−s} for the three-regime analysis.
    Sections 5–7 specialize to this one-parameter family to exhibit the diffuse/critical/atomic transition; not forced by the general model.
invented entities (2)
  • Weighted quorum time τ_{N,θ} no independent evidence
    purpose: Stopping time when discovered weight first exceeds θ; the main object of asymptotic study.
    Naming of a natural stopping time; not a new physical entity. Independent evidence is not applicable beyond the mathematical definition.
  • Diffuse vs atomic weight regimes (Definition 3.1) no independent evidence
    purpose: Classify when max weight vanishes versus when fixed types keep positive limiting weight.
    Taxonomy introduced to organize LLN vs random-limit behavior; standard asymptotic language rather than a new ontological claim.

pith-pipeline@v1.1.0-grok45 · 22769 in / 3019 out tokens · 32888 ms · 2026-07-10T05:30:37.066362+00:00 · methodology

0 comments
read the original abstract

We study a weighted-threshold version of the coupon collector problem in continuous time. Each type $i$ is discovered at rate $\lambda p_i$ and, once discovered, contributes weight $w_i$, where $p$ and $w$ are probability vectors. The stopping time when the total weight of the discovered types first exceeds a fixed threshold $\theta\in (0,1)$ is called the quorum time. We first prove concentration estimates and compare the quorum time with the corresponding deterministic threshold time obtained from the mean discovered weight. When all discovery rates are equal and the largest individual weight tends to zero, the first-order asymptotics are universal and do not depend on the weight vector. We then analyze the aligned Zipf family $p_i = w_i \propto i^{-s}$. This model has three regimes: a deterministic linear scale for $0\le s < 1$, a critical scale $H_NN^\theta$ at $s=1$, with an explicit leading constant, and a non-degenerate random hitting-time limit for $s>1$. Finally, we show that the expected quorum time need not be monotone in the Zipf exponent.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

37 extracted references · 37 canonical work pages · 9 internal anchors

  1. [1]

    Ilan Adler and Sheldon M. Ross. The coupon subset collection problem.J. Appl. Probab., 38(3):737– 746, 2001

    work page 2001

  2. [2]

    EmmanuelleAnceaume, YannBusnel, ErnstSchulte-Geers, andBrunoSericola.Optimizationresults for a generalized coupon collector problem.J. Appl. Probab., 53(2):622–629, 2016

    work page 2016

  3. [3]

    New results on a generalized coupon collector problem using Markov chains.J

    Emmanuelle Anceaume, Yann Busnel, and Bruno Sericola. New results on a generalized coupon collector problem using Markov chains.J. Appl. Probab., 52(2):405–418, 2015

    work page 2015

  4. [4]

    The clumsy coupon collector's problem

    Luke J. Attrill and Timothy M. Garoni. The clumsy coupon collector’s problem.arXiv:2605.14206, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  5. [5]

    A multiple coupon collection process and its Markov embedding structure.Monatsh

    Ellen Baake and Michael Baake. A multiple coupon collection process and its Markov embedding structure.Monatsh. Math., 209(3):357–381, 2026

    work page 2026

  6. [6]

    Ohannessian

    Anna Ben-Hamou, Stéphane Boucheron, and Mesrob I. Ohannessian. Concentration inequalities in the infinite urn scheme for occupancy counts and the missing mass, with applications.Bernoulli, 23(1):249–287, 2017

    work page 2017

  7. [7]

    InComputing and combinatorics, volume 5609 ofLecture Notes in Comput

    PetraBerenbrinkandThomasSauerwald.Theweightedcouponcollector’sproblemandapplications. InComputing and combinatorics, volume 5609 ofLecture Notes in Comput. Sci., pages 449–458. Springer, Berlin, 2009

    work page 2009

  8. [8]

    On the concentration of the missing mass.Electron

    Daniel Berend and Aryeh Kontorovich. On the concentration of the missing mass.Electron. Com- mun. Probab., 18:no. 3, 7, 2013

    work page 2013

  9. [9]

    Asymptotic Results for Uniform Group Drawing in the Coupon Collector's Problem

    Daniel Berend and Tomer Sher. Asymptotic results for uniform group drawing in the coupon col- lector’s problem.arXiv:2605.06953, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  10. [10]

    The coupon-collector problem revisited—a survey of engineering problems and computational methods.Comm

    Arnon Boneh and Micha Hofri. The coupon-collector problem revisited—a survey of engineering problems and computational methods.Comm. Statist. Stochastic Models, 13(1):39–66, 1997

    work page 1997

  11. [11]

    Oxford Uni- versity Press, Oxford, 2013

    Stéphane Boucheron, Gábor Lugosi, and Pascal Massart.Concentration inequalities. Oxford Uni- versity Press, Oxford, 2013. A nonasymptotic theory of independence, With a foreword by Michel Ledoux

    work page 2013

  12. [12]

    Peköz, and Sheldon M

    Mark Brown, Erol A. Peköz, and Sheldon M. Ross. Coupon collecting.Probab. Engrg. Inform. Sci., 22(2):221–229, 2008

    work page 2008

  13. [13]

    Practical byzantine fault tolerance

    Miguel Castro, Barbara Liskov, et al. Practical byzantine fault tolerance. InOsDI, volume 99, pages 173–186, 1999

    work page 1999

  14. [14]

    Kuang-Chao Chang and Sheldon M. Ross. The multiple subset coupon collecting problem.Probab. Engrg. Inform. Sci., 21(3):435–440, 2007

    work page 2007

  15. [15]

    Barak-Pelleg D. and D. Berend. Fano geometry and slow coupon collecting.arXiv:2606.28216, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  16. [16]

    AristidesV.DoumasandVassilisG.Papanicolaou.Thecouponcollector’sproblemrevisited: asymp- totics of the variance.Adv. in Appl. Probab., 44(1):166–195, 2012

    work page 2012

  17. [17]

    Doumas and Vassilis G

    Aristides V. Doumas and Vassilis G. Papanicolaou. Uniform versus Zipf distribution in a mixing collection process.Statist. Probab. Lett., 155:108559, 7, 2019

    work page 2019

  18. [18]

    AristidesV.DoumasandS.Spektor.Equalprobabilitiesmaximizetheexpecteddeficitinthesiblings of the coupon collector.arXiv:2606.21591, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  19. [19]

    Two Multi--Draw Coupon Collector models with different retention rules

    Aristides V. Doumas and S. Spektor. Two multi–draw coupon collector models with different reten- tion rules.arXiv:2607.01463, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  20. [20]

    Birthday paradox, coupon collectors, caching algorithms and self-organizing search.Discrete Appl

    Philippe Flajolet, Danièle Gardy, and Loÿs Thimonier. Birthday paradox, coupon collectors, caching algorithms and self-organizing search.Discrete Appl. Math., 39(3):207–229, 1992

    work page 1992

  21. [21]

    Weighted voting for replicated data

    David K Gifford. Weighted voting for replicated data. InProceedings of the seventh ACM symposium on Operating systems principles, pages 150–162, 1979

    work page 1979

  22. [22]

    Notes on the occupancy problem with infinitely many boxes: general asymptotics and power laws.Probab

    Alexander Gnedin, Ben Hansen, and Jim Pitman. Notes on the occupancy problem with infinitely many boxes: general asymptotics and power laws.Probab. Surv., 4:146–171, 2007

    work page 2007

  23. [23]

    Central limit theorems for certain infinite urn schemes.J

    Samuel Karlin. Central limit theorems for certain infinite urn schemes.J. Math. Mech., 17:373–401, 1967

    work page 1967

  24. [24]

    Ouroboros: A provably secure proof-of-stake blockchain protocol

    Aggelos Kiayias, Alexander Russell, Bernardo David, and Roman Oliynykov. Ouroboros: A provably secure proof-of-stake blockchain protocol. InAnnual international cryptology conference, pages 357–

    work page

  25. [25]

    WEIGHTED-THRESHOLD COUPON COLLECTION 23

    Springer, 2017. WEIGHTED-THRESHOLD COUPON COLLECTION 23

    work page 2017

  26. [26]

    Christopher D. Long. The ballot event for two-player coupon collection: A renewal–catalan asymp- totic.arXiv:2605.09641, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  27. [27]

    Clumsy and Careless: Stationary-Entry Flux in Non-monotone Coupon Collectors

    ChristopherD.Long.Clumsyandcareless: Stationary-entryfluxinnon-monotonecouponcollectors. arXiv:2605.14511, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  28. [28]

    Christopher D. Long. Extremality and limit laws for the siblings of the coupon collector. arXiv:2606.29635, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  29. [29]

    Christopher D. Long. Radial transform extremality for the siblings of the coupon collector. arXiv:2606.31391, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  30. [30]

    Byzantine quorum systems.Distributed computing, 11(4):203– 213, 1998

    Dahlia Malkhi and Michael Reiter. Byzantine quorum systems.Distributed computing, 11(4):203– 213, 1998

    work page 1998

  31. [31]

    Coupon collecting with quotas.Electron

    Russell May. Coupon collecting with quotas.Electron. J. Combin., 15(1):Note 31, 7, 2008

    work page 2008

  32. [32]

    Buchanan

    Sebastian Müller, Andreas Penzkofer, Bartosz Kuśmierz, Darcy Camargo, and William J. Buchanan. Fast probabilistic consensus with weighted votes. In Kohei Arai, Supriya Kapoor, and Rahul Bhatia, editors,Proceedings of the Future Technologies Conference (FTC) 2020, Volume 2, volume 1289 of Advances in Intelligent Systems and Computing, pages 360–378. Spring...

    work page 2020

  33. [33]

    Tangle 2.0 Leaderless Nakamoto Consensus on the Heaviest DAG.IEEE Access, 10:105807– 105842, 2022

    Sebastian Müller, Andreas Penzkofer, Nikita Polyanskii, Jonas Theis, William Sanders, and Hans Moog. Tangle 2.0 Leaderless Nakamoto Consensus on the Heaviest DAG.IEEE Access, 10:105807– 105842, 2022

    work page 2022

  34. [34]

    The generalised coupon collector problem.J

    Peter Neal. The generalised coupon collector problem.J. Appl. Probab., 45(3):621–629, 2008

    work page 2008

  35. [35]

    Newman and Lawrence Shepp

    Donald J. Newman and Lawrence Shepp. The double dixie cup problem.Amer. Math. Monthly, 67:58–61, 1960

    work page 1960

  36. [36]

    RafaelPassandElaineShi.Thesleepymodelofconsensus.InAdvances in cryptology—ASIACRYPT

    work page

  37. [37]

    Sci., pages 380–409

    Part II, volume 10625 ofLecture Notes in Comput. Sci., pages 380–409. Springer, Cham, 2017. Sebastian Müller, Aix Marseille Université, CNRS, Centrale Marseille, I2M - UMR 7373, 13453 Marseille, France Email address:sebastian.muller@univ-amu.fr Stjepan Šebek, University of Zagreb F aculty of Electrical Engineering and Comput- ing, 10000 Zagreb, Croatia Em...

    work page 2017