Optimal coupon packages and stochastic improvement of uniform group drawings

A mix of human-written and AI-generated textHuman understanding: some partsmath.PR — Probabilitymath.CO — Combinatorics

Contributed by Christopher D. Long ↗

Version 1 / Nov 21, 2026 / CC BY 4.0

Abstract

A collector repeatedly draws independent packages of at most ss coupons from a universe of nn coupons. When s∣ns\mid n, we prove that the uniform law on the blocks of an ss-set partition uniquely minimizes the expected completion time, resolving the Fang–Chang optimal-package conjecture. The partition law is stochastically optimal in Poissonized time, also for every common collection multiplicity. The proof combines independent package clocks, Finner's inequality, and strict concavity; an incidence-class tail argument characterizes equality. The same bound proves the lower-bound conjecture of Grunbaum and Yaakobi without their regularity assumptions. A separate elementary discrete-time bound identifies the unique optimal complementary-partition laws whenever s<ns<n and n−s∣nn-s\mid n. For fixed-size packages, a four-coupon perturbation preserves singleton marginals and strictly increases the completion probability at every feasible draw count. This gives an alternative proof and a stochastic strengthening of Schilling's conjecture, previously proved in expectation by Berend and Sher. More generally, perturbations formed from dd disjoint pairs preserve all inclusion probabilities below order dd and are strictly stochastically monotone in their absolute amplitude, with the direction determined by the parity of dd. Their inclusion–exclusion coefficients count covering families. Combined with the Johnson-scheme decomposition, this yields the complete alternating signature of the expectation Hessian at the uniform law. The general fixed-draw partition comparison is left as a conjecture; its first feasible draw count follows from the Poissonized bound.

Author comments: 17 pages. Resolves the Fang–Chang expected-time optimum; the general fixed-draw partition comparison remains open. Internal audit and exact finite checks, without proof-assistant formalization or independent refereeing. Source and reproducibility records: https://github.com/long-mathematics/optimal-coupon-packages/tree/f11c52cc42b82575fff5ed1c699717976c8546d0

Provenance statement

The submitting contributor understands the problem statement, the flow of the main arguments, and the conclusions, but has not personally verified every detail. ChatGPT assisted with exploration, drafting, symbolic checking, and review. The human author takes responsibility for the mathematical claims and their attribution. The repository provides an internal mathematical and citation audit and finite exact computational checks; these are not independent peer review or proof-assistant formalization. The expected-time optimum and Poissonized stochastic comparison are proved in the manuscript; the general fixed-draw partition comparison remains open.

References

  1. D. Berend and T. Sher, On a conjecture on uniform group drawings in the coupon collector problem , Stochastic Models (2026), published online May 27, 2026. doi:10.1080/15326349.2026.2671340 (https://doi.org/10.1080/15326349.2026.2671340). Preprint: arXiv:2509.17201 (https://arxiv.org/abs/2509.17201); version 2, May 11, 2026.arXivDOI
  2. C. Fang and E.-C. Chang, Optimal strategy of coupon subset collection when each package contains half of the coupons , Information Processing Letters 114 (2014), no. 12, 703--705. doi:10.1016/j.ipl.2014.06.012 (https://doi.org/10.1016/j.ipl.2014.06.012).DOI
  3. Y. Filmus, An orthogonal basis for functions over a slice of the Boolean hypercube , The Electronic Journal of Combinatorics 23 (2016), no. 1, paper P1.23, 27 pp. doi:10.37236/4567 (https://doi.org/10.37236/4567).DOI
  4. H. Finner, A generalization of Hölder's inequality and some probability inequalities , The Annals of Probability 20 (1992), no. 4, 1893--1901. doi:10.1214/aop/1176989534 (https://doi.org/10.1214/aop/1176989534).DOI
  5. Y. Grunbaum and E. Yaakobi, General coverage models: Structure, monotonicity, and shotgun sequencing , preprint, arXiv:2510.25305v1 (https://arxiv.org/abs/2510.25305v1) (2025). The references here to Remark 2 and Conjecture 3 use this version.arXiv
  6. J. Schilling, Results and conjectures on the role of the uniform distribution in the coupon collector's problem with group drawings , Information Processing Letters 169 (2021), article 106112. doi:10.1016/j.ipl.2021.106112 (https://doi.org/10.1016/j.ipl.2021.106112).DOI

Version history

  1. v1 · 17 pagesSubmitted by Christopher Long17 pages. Resolves the Fang–Chang expected-time optimum; the general fixed-draw partition comparison remains open. Internal audit and exact finite checks, without proof-assistant formalization or independent refereeing. Source and reproducibility records: https://github.com/long-mathematics/optimal-coupon-packages/tree/f11c52cc42b82575fff5ed1c699717976c8546d0CurrentNov 21, 2026