Optimal coupon packages and stochastic improvement of uniform group drawings
Version 1 / Nov 21, 2026 / CC BY 4.0
Abstract
A collector repeatedly draws independent packages of at most coupons from a universe of coupons. When , we prove that the uniform law on the blocks of an -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 and . 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 disjoint pairs preserve all inclusion probabilities below order and are strictly stochastically monotone in their absolute amplitude, with the direction determined by the parity of . 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.
Provenance statement
References
- 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
- 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
- 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
- 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
- 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
- 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
- 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