Extremizers of the expected missing mass under an entropy constraint

A mix of human-written and AI-generated textHuman understanding: some partsmath.PR — Probabilitymath.IT — Information Theory

Contributed by Christopher D. Long ↗

Version 1 / Nov 20, 2026 / CC BY 4.0

Abstract

For a discrete probability distribution p=(pi)p=(p_i), the expected mass of symbols absent from tt independent samples is Φt(p)=∑ipi(1−pi)t\Phi_t(p)=\sum_i p_i(1-p_i)^t. For every positive integer tt and finite entropy budget h≥0h\ge0, we prove that every ℓ1\ell^1-local maximizer under H(p)≤hH(p)\le h has at most two distinct positive coordinate values, and all but at most one positive coordinate are equal. This holds on finite and countably infinite alphabets and improves the four-size bound of Berend, Kontorovich, and Zagdanski (2017). On a countably infinite alphabet, we give an exact finite classification of all global maximizers: a unique one-light or uniform candidate is compared with an explicitly bounded family of one-heavy candidates, whose masses are uniquely specified by entropy equations. The one-light or uniform candidate is uniquely optimal for t=1,2t=1,2. For fixed h>0h>0, the optimal value Bt(h)B_t(h) satisfies \[ \frac{h}{B_t(h)}=\log t+\log\log t+2 +O_h\!\left(\frac{\log\log t}{\log t}\right). \] Every optimizer is eventually one-heavy, with mt∼htm_t\sim ht equal light atoms of size qt∼1/(tlog⁡t)q_t\sim1/(t\log t). The two-size proof combines a three-coordinate entropy-curvature estimate with a finite coefficient comparison. Crossing theorems describe the winning intervals of the candidate distributions, and the classification gives exact extrema for singleton counts, discovery increments, and expected coverage.

Author comments: Lean 4 formalization, manuscript correspondence, and final audit: https://github.com/long-mathematics/entropy-constrained-missing-mass/tree/cfc6f0e70596b36c2309cccbb931a1c84f63ad7f

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 proof discovery, simplification, and editorial suggestions. All 18 named results and their proof-critical dependencies are formalized in Lean 4; the repository provides the manuscript-correspondence ledger and final formalization audit. The build, axiom/source/ledger audits, and exact rational certificates passed in CI for commit cfc6f0e70596b36c2309cccbb931a1c84f63ad7f.

References

  1. D. Berend and A. Kontorovich, The missing mass problem , Statistics & Probability Letters 82 (2012), no. 6, 1102--1110. doi:10.1016/j.spl.2012.02.014 (https://doi.org/10.1016/j.spl.2012.02.014).DOI
  2. D. Berend, A. Kontorovich, and G. Zagdanski, The expected missing mass under an entropy constraint , Entropy 19 (2017), no. 7, article 315, 13 pp. doi:10.3390/e19070315 (https://doi.org/10.3390/e19070315).DOI

Version history

  1. v1 · 19 pagesSubmitted by Christopher LongLean 4 formalization, manuscript correspondence, and final audit: https://github.com/long-mathematics/entropy-constrained-missing-mass/tree/cfc6f0e70596b36c2309cccbb931a1c84f63ad7fCurrentNov 20, 2026