The exact Poisson–binomial comparison in every dimension

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

Contributed by Christopher D. Long ↗

Version 1 / Nov 20, 2026 / CC BY 4.0

Abstract

For coordinatewise ordered Bernoulli parameters with a prescribed total mean gap, the maximum difference of count tails is minimized by homogeneous parameters. For a nondegenerate gap 0<Δ<n0<\Delta<n, in odd dimension n=2m+1≥3n=2m+1\ge3 the two minimizers are the homogeneous pairs whose likelihood ratios equal one at count mm or m+1m+1; in even dimension n≥4n\ge4 the unique minimizer is the complementary homogeneous pair. We prove the comparison and these equality statements by a global stationary-point reduction, with all boundary faces included. A normalized switch-mass identity orders the homogeneous switching values. The same extremizers give the exact product total-variation minimum. The exceptional two-dimensional equality families are classified in the appendix.

Author comments: Lean 4 formalization and verification ledger: https://github.com/long-mathematics/poisson-binomial-comparison/tree/b34cde620016c85e5c7d5461630c0fde3f098d4b

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. The contributor relies on the Lean formalization as evidence of correctness. The manuscript acknowledges GPT-6 Astra and Claude Opus 5 for assistance with proof discovery, auditing, and editorial suggestions. The repository contains the Lean 4 formalization and a manuscript-correspondence ledger; Lean CI passed for commit b34cde620016c85e5c7d5461630c0fde3f098d4b.

References

  1. W. Hoeffding, On the distribution of the number of successes in independent trials , Ann. Math. Statist. 27 (1956), no. 3, 713--721. doi:10.1214/aoms/1177728178 (https://doi.org/10.1214/aoms/1177728178).DOI
  2. A. Kontorovich, Minimizing total variation under constraint , MathOverflow, question 476847, August 13, 2024. https://mathoverflow.net/q/476847.link
  3. A. Kontorovich, Poisson binomial conjecture , MathOverflow, question 477402, August 22, 2024, with answers by T. Steinke (August 22, 2024) and W. Sawin (September 24, 2024). https://mathoverflow.net/q/477402.link
  4. A. Kontorovich, On the tensorization of the variational distance , Electron. Commun. Probab. 30 (2025), paper no. 32, 10 pp. doi:10.1214/25-ECP680 (https://doi.org/10.1214/25-ECP680).DOI
  5. A. Kontorovich, TV homogenization inequalities , preprint (2026), arXiv:2601.04079v3 (https://arxiv.org/abs/2601.04079v3) [math.PR].arXiv
  6. J. Pitman, Probabilistic bounds on the coefficients of polynomials with only real zeros , J. Combin. Theory Ser. A 77 (1997), no. 2, 279--303. doi:10.1006/jcta.1997.2747 (https://doi.org/10.1006/jcta.1997.2747).DOI

Version history

  1. v1 · 14 pagesSubmitted by Christopher LongLean 4 formalization and verification ledger: https://github.com/long-mathematics/poisson-binomial-comparison/tree/b34cde620016c85e5c7d5461630c0fde3f098d4bCurrentNov 20, 2026