WorksMathematics
The exact Poisson–binomial comparison in every dimension
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 , in odd dimension the two minimizers are the homogeneous pairs whose likelihood ratios equal one at count or ; in even dimension 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.
Statement
For , let be a sum of independent Bernoulli variables with parameters . Put
For probability measures on a finite set, we use . We assume coordinatewise. For , , and , there is a unique pair satisfying
Define
Set and .
Theorem 1.1. For every and every with ,
For and , equality forces both vectors to be homogeneous. More precisely:
If is even, equality holds exactly when and for all .
If is odd, let solve (1.1) with and . Equality holds exactly for
The exact minimum of under the same constraint is also , with the same equality cases for and .
The exceptional equality cases for are classified in Proposition A.1 of Appendix § 7. For odd , the benchmark can also be written
where is the switch with . Equivalently, let be the unique solution of
Then
These formulas follow directly from the equal-height equation.
The even-dimensional comparison and related product optimization were posed by Kontorovich [3, 2]. The discussion of [3] includes Steinke’s randomized symmetrization and Sawin’s fixed-mean tail-extremization approach. General lower bounds for product total variation in terms of marginal distances are developed in [4]. More directly, [5 Theorem 1.5] compares Bernoulli products with their mean-preserving homogenizations up to a universal constant. Here only the total gap is fixed, and we determine the exact minimum and all equality cases. The proof combines the deletion-mixture bound in Lemma 2.2, the switch identities in Lemma 3.1, and a global extremizer argument. The even-dimensional benchmark is recovered as
For , (1.3) becomes
The proof proceeds by induction from .
Bernoulli facts and the randomized test
We use the likelihood-ratio order only for Bernoulli sums. Their mass functions have interval support and are strictly log-concave at positive interior triples. A deterministic shift preserves these facts. To see strict log-concavity, remove the deterministic variables and write the remaining probability generating polynomial as , where . Its zeros are real and negative. If its coefficients are , Newton’s inequality (see [6]) gives, for ,
Here and below a comparison of ratios is understood by cross multiplication when an endpoint mass is zero.
Lemma 2.1 (Increasing a parameter). Increasing Bernoulli parameters, or adjoining a Bernoulli variable, increases the law in likelihood-ratio order. If at least one parameter increases strictly, the adjacent likelihood-ratio comparison is strict when both adjacent masses are positive in both laws. In particular, if , and is obtained by a strict parameter increase, then
If the mass at disappears because the lower endpoint of the support moves past , both displayed masses of are zero instead. On a parameter interval where both adjacent masses remain positive, their difference can cross zero only from positive to negative.
Proof. With all other variables summed into , changing a parameter from to changes the mass at from to . Their ratio increases with , which increases strictly in on the positive support by strict log-concavity. Equivalently, the relevant adjacent determinant is a positive multiple of . Successive coordinate changes prove the assertion. Adjoining a variable is the change of an appended parameter from zero to its new value.
For ordered with and , Lemma 2.1 shows that the maximizing thresholds consist of one threshold or two adjacent thresholds. Indeed the mass difference changes sign once, and can vanish at at most one count in the overlapping support. Disjoint supports would give . For and , define
An independent gives . Write and . Direct differentiation gives
A pure threshold is included by taking or . For fixed other coordinates, splitting two equal coordinates into changes by exactly .
Lemma 2.2 (A maximal-atom bound). Put
Every -trial Bernoulli sum has a mass at least . If at most two of the gaps are positive, then
Proof. First, an -trial Bernoulli sum of integer mean has probability at that integer at least . To prove this, minimize that probability at fixed mean. The fixed-mean reduction to equal interior parameters is classical; see Hoeffding [1]. Here is the two-coordinate argument needed in this case. Among the minimizers choose one with least sum of squared parameters. If two interior parameters occur, then, with the others fixed, the objective has the form . The transfer is feasible for both signs of sufficiently small , so minimality gives . Thus , and replacing by their average preserves the objective while strictly decreasing the sum of squares, a contradiction. Consequently an extremizer is a deterministic shift plus with integer and . For
ratio calculations give
The increasing function shows that the least -trial integer-mean mass is , and that increasing with fixed can only decrease the mass. Deterministic cases give mass one.
If with , adjoin . Its mass at the integer mean is , proving the first assertion. This extra Bernoulli variable explains the index in the bound for an -trial sum.
For the second assertion, the case is immediate; assume . Put , and . When at most two are nonzero, symmetric expansion of the generating polynomials gives exactly
This deletion mixture is an -trial Bernoulli law. For completeness, its generating polynomial is . For distinct interior and positive weights, factor out the full product: the remaining rational function has positive residues at its negative poles and therefore one zero between each successive pair of poles. Thus has only negative real zeros, and factors it into Bernoulli generating factors. Continuity covers all degeneracies. The first assertion now proves (7).
We will repeatedly use one more elementary consequence of Lemma 2.1. If is a fixed Bernoulli sum and
then
The derivative formula is used for ; is simply a constant. On the support is fixed. Thus the derivative changes sign at most once, from positive to negative. An interior critical point of positive height is its maximum; it is strict when . For an interior critical point means that is constant.
We also need the following adjoining rule, with its positivity condition explicit: if a Bernoulli sum satisfies
then adjoining further independent Bernoulli variables cannot increase its mass at . Indeed, write , and . Log-concavity and interval support give . After adjoining the relevant masses are and , so their order persists and the mass at does not increase. If that mass becomes zero, the support has moved strictly above , and further adjoining cannot recreate it. If and , strict log-concavity gives ; the first addition makes the adjacent difference strictly negative, and a second addition with positive parameter strictly decreases the mass at . All uses of this rule below start with a positive mass at .
Corollary 2.3 (Derivative criterion for adjoining). Let be as in (2.5), with and . If and , then
Consequently adjoining further independent Bernoulli variables cannot increase the mass at .
Proof. Write and . The derivative condition gives , and then implies . Log-concavity and interval support give . For , it follows that
The adjoining rule applies. □
The homogeneous problem in both parities
Suppress the first index in , and write . Let satisfy (1.1), and set
Here , and
The binomial masses at count agree, so thresholds tie and both equal .
Lemma 3.1 (Switch identities). Primes denote differentiation in . Then
Consequently,
For fixed , is strictly decreasing in on . Also .
Proof. The equation defining has derivative
in , with opposite infinite endpoint limits. This proves existence and uniqueness of the switch. Differentiating the equal-height equation and , and using (3.1), gives
Differentiation of the binomial tail proves (3.2). In particular . Integration, followed by and , proves (3.3).
We give the geometric monotonicity explicitly. Suppose , and put and . Let , , , , and . The equal-height equation says
Thus . The identity
shows that the paired average increases with . Hence , strictly if . The first inequality is equivalent to
and the second gives .
Now keep fixed and differentiate in the continuous parameter . The derivative is positive, since the derivative of the switch equation in is whereas its derivative in is negative. Therefore
Finally set . Differentiation gives , and gives . Since , its derivative is nonpositive. Reflection covers and proves the last assertion. □
Proposition 3.2 (Strict ordering of switches). For and ,
Consequently the homogeneous minimum is , with exactly the central switch when is even and the two reflected central switches when is odd. For , is strictly concave on and
Proof. By (3.4), . Thus
The equal integrals in (3.3) imply that changes sign exactly once, from positive to negative. Where , writing gives . Before the crossing, , and afterwards . In both cases
Reflection gives .
It remains to justify that switches exhaust the homogeneous minima. Define
At fixed , each threshold difference has the form
Its derivative has the sign of the ratio of the two endpoint densities minus one. Strict log-concavity makes that ratio strictly decreasing in , so the individual threshold difference has no interior local minimum. Suppose that is a local minimum of . If exactly one threshold is active at , its strict separation from the other finitely many thresholds persists in a neighborhood. There equals that threshold difference, a contradiction. Thus at least two thresholds are active. Here , so both count laws have full support and . The active-threshold property in Section 2 therefore shows that they are exactly two adjacent thresholds . Their equality is equivalent to
so is a switch. The homogeneous minimum is therefore attained at a switch or at . At an endpoint its value is , strictly larger than a central switch value: in the coordinatewise uniform coupling of a central homogeneous pair, the event of at least one discrepancy has this probability, and the positive-probability event of exactly one discrepancy with all other coordinates zero does not cross threshold .
Finally (10) and give
For the central index , as we have and . Since ,
Strict concavity, together with and , proves (13).
Removing a common deterministic coordinate
The following strict dimension improvement supplies the boundary step in the induction.
Lemma 4.1. Let . For every , there is an ordered -dimensional pair of gap with tail objective strictly less than .
Proof. For , any strictly interior ordered pair of that gap has . Suppose and take a homogeneous central switch pair in dimension , with switch index , common mass , and geometric quantity from Lemma 3.1. Set
The density
satisfies, by substitution,
Adjoin the common parameter . To identify the active threshold, write for the old tail differences and set . The new differences satisfy
Exactly the old thresholds attain . Since , the new threshold still has this value, whereas every other new threshold has a strictly smaller value: its convex combination includes at least one old value below the maximum. Thus is the unique maximizing threshold. For small replace the parameters by
Here a superscript on a coordinate denotes repetition. The gap remains and the pair is feasible. By (14), the unique active tail has derivative at zero
It remains the maximizing tail for sufficiently small . This proves the strict improvement.
The global minimizer
We prove Theorem 1.1 by induction. For , , so , attained by the complementary homogeneous pair. Fix , assume the theorem’s minimum-value assertion in dimension , and let be a global minimizer at a fixed gap . Compactness gives its existence. Its value is at most the homogeneous candidate .
By Lemma 2.2 and (13), at least three gaps are positive. By Lemma 4.1, no coordinate can be common deterministic. Such a coordinate requires ; deleting it would give , whereas a strict improvement is available. Thus and for every . Also cannot be identically one, nor identically zero. For example, if , then
where the strict endpoint comparison was proved above.
Write
All common parameters, when present, are strictly interior.
Stationarity and common coordinates
There are one or two adjacent active thresholds. Choose their convex combination as in (4) so that the first-order optimality conditions hold. Existence follows from the separating hyperplane theorem applied to the feasible tangent cone of the linear constraints and the active gradients. With a multiplier for the total gap, these conditions read, for ,
and, for ,
The signs follow, for example, by using as the Lagrangian, together with the endpoint constraints.
We first establish, without any nonconstancy assumption, that
Write the supports of as and . Since , we have . For every changing coordinate , the derivative of the pure threshold at is positive whenever , and its derivative at is positive whenever . This follows from the deletion supports and includes and . Every threshold belongs to at least one of these two ranges. Therefore their active convex combination satisfies
where the upper bound follows from (5.1)–(5.2). This proves (17).
If there is only one active threshold and a common coordinate , stationarity in gives . These are positive masses. Indeed, write the original supports as and . Deleting the common interior coordinate gives supports and . Both masses at could vanish only if and , forcing and hence . Likelihood-ratio ordering then says that the two deletion tails at both maximize their difference. Adjoining any common Bernoulli parameter preserves this maximum. Taking that parameter to zero creates a common deterministic coordinate at the same minimum, a contradiction.
Consequently, if , there are two active thresholds . For a common coordinate , put . The active tie and (16) give
The tied count lies in the overlap, so . The deletion supports are and ; the upper deletion mass at and the lower deletion mass at are positive. If , equality would make both adjacent masses positive in both deletion laws. At least one changing coordinate remains, so strict likelihood-ratio ordering would contradict the two equalities. Thus the two adjacent differences cannot both vanish, and hence
In particular all common coordinates agree. Their derivative is exactly the original mass at the tied count. That mass is positive because has support and . Thus
One changing vector is homogeneous
indeed distinct interior entries have equal gradients, and a larger entry equal to one has no larger gradient. Likewise
Suppose that both and . The laws in (5) are ordered in likelihood ratio, and at least one of the other changing coordinates increases strictly because . The upper deletion law has positive mass at : this follows from a free gradient equal to and its nonnegative adjacent difference. Similarly the lower deletion law has positive mass at . Their ordered interval supports therefore make both adjacent masses positive in both laws. If denote the upper deletion masses at , and the corresponding lower deletion masses, then the coefficient signs and Lemma 2.1 would give
a contradiction. Thus every pair satisfies or . The elementary consequence is that one of is constant: two different values in one vector force all entries of the other to agree. Reflection lets us assume
Here reflection means ; it preserves and , with sent to .
If , then , since the all-one vector was excluded. By (19) and (15), for a common coordinate and a changing coordinate ,
Consider . Its partial derivatives at equal . Along the path from to , the deletion laws are strictly smaller in likelihood ratio than the endpoint deletion law . Its two relevant masses are positive because , so and both lie in . All partial derivatives are therefore positive in the interior of this path. It follows that , contradicting the active mass equality. Hence
The other changing vector is homogeneous
Fix the common coordinates and set
This notation includes deterministic when and is an endpoint. By (20), (21), and (15),
Every positive , , is less than and is a free coordinate. Its gradient is .
There are at most two distinct positive values among these . Indeed, suppose three such coordinates have distinct values , and let be the masses of the law with those three coordinates deleted and adjoined. Put and . The pair coefficients vanish by (6), giving for . Subtracting two equations yields , and then . Thus . Their common value equals a free gradient, which is a convex combination of these three masses, and hence equals . This contradicts strict log-concavity.
If two positive values occur, the smaller value occurs only once. Otherwise split two coordinates. The coefficient for a pair is zero, so its deletion law , with adjoined, has equal masses at . The free-gradient identity
shows that both equal masses are . The deletion law for two coordinates replaces the remaining by . Since $0 < u < v < a < 1$, this replacement preserves the support and both adjacent masses stay positive. Strict likelihood-ratio ordering therefore gives . The objective then has negative second variation along the split. For a single active threshold this is an immediate contradiction. For two active thresholds keep their tie exactly: an unequal transfer has nonzero first derivative of , whereas the equal-coordinate split has zero first derivative. To check nonvanishing, write the coefficient as , where
and excludes those two coordinates, without . If , then , so the three consecutive masses of are equal. Their common value is for the coordinate with value : adjoining and takes a convex combination of those three masses. Strict log-concavity gives a contradiction. In fact, along the transfer that increases a coordinate and decreases a coordinate,
Let denote the equal-coordinate split direction and this unequal transfer direction, both acting on alone. For , we have and . The implicit-function theorem gives with . Both directions have coordinate sum zero. Moreover, for , the free-gradient equalities give . Consequently
for sufficiently small nonzero . All other thresholds remain strictly below the two tied active thresholds by continuity. On this curve , so this is a genuine feasible decrease of the original maximum, not merely of a supporting test. All moves stay strictly between zero and , contradicting minimality.
Suppose now that the positive entries are one and copies of , with zero entries; thus . Deleting gives , while the zero coefficient gives . Consequently is its maximum. If , then gives and . The mass is positive because the support is fixed on and . Corollary 2.3 therefore gives
contradicting (22). If , the function is constant and because . The law has equal positive masses at . Adding one preserves the mass at but makes the adjacent difference strictly negative. The second addition therefore gives , and further additions cannot increase the mass. Thus there cannot be two positive values.
Finally suppose that there are copies of a single positive value and zeros, so . A positive-coordinate derivative and a zero-coordinate derivative give
For , the identity
shows that , since . Adjoin Bernoulli variables with parameter and then raise the original parameters from to . Every step can only decrease the mass at . For the raising steps, its deletion law dominates : one appended replaces the deleted , and any remaining appended variables are extra. The decrease is strict. If the initial adjacent masses are unequal, the first addition is strict. If they tie, two additions are strict in aggregate; when , there is a parameter to raise because , and that raising step is strict. Hence again , a contradiction.
We have proved that for some . The case is excluded either by the all-zero-vector endpoint comparison when , or by reflection of the argument when . Therefore
No unchanged coordinate remains
Suppose . Recalling (18) and (23), we have
Set
The free gradients and common-coordinate gradients give
Since , has a unique mode . At that point the law has equal positive masses at . All laws compared below have strictly interior Bernoulli parameters, including those obtained by intermediate replacements. They therefore have positive masses at both and .
If , then . Replacing one parameter by increases this deletion law strictly in likelihood ratio, so and hence . This makes . If , the reflected argument gives and . In the remaining case , nonnegativity in (24) would force , impossible because increasing crosses the adjacent-mass equality only from positive to negative, strictly. Every case contradicts (24). Thus .
The global minimizer is therefore fully homogeneous, with strictly interior parameters. Proposition 3.2 identifies it as precisely the central switch or the two reflected central switches. This proves (2) and all equality cases for , and completes the induction.
Product total variation and endpoints
For the threshold event ,
At a homogeneous pair the product likelihood ratio depends only on the count and increases strictly with it, so product total variation equals the maximizing tail difference. The sharp minimum is therefore , and equality for forces equality in the tail comparison, giving the same classification. At , ordering forces , and every such pair minimizes. At , feasibility forces . The nonunique two-dimensional equality families are proved in Appendix A.
Two-dimensional equality families
For , write .
Proposition A.1. Let satisfy , and put , , and . Then
For , both minima are . Tail equality holds exactly when . Product equality holds exactly for
The product-minimizing family is a proper subset of the tail-minimizing family for every .
Proof. Ordering gives . The two tail differences are and , proving (A.1). The signed product mass differences at 00, 10, 01, 11 are
Taking half the sum of their absolute values proves (A.2). The lower bound in both formulas is attained by the complementary homogeneous pair. The tail equality condition follows immediately. Product equality is equivalent to . Since and
this is equivalent to . Writing gives (A.3), with the displayed interval exactly expressing feasibility. Conversely every member of that family attains equality; its homogeneous member is .
For strict containment, choose , set , , and take , . Then , so but . At , ordering forces , and every such pair minimizes both objectives. At , the only feasible pair is , .
:::`
AI assistance
GPT-6 Astra and Claude Opus 5 assisted with proof discovery, auditing, and editorial suggestions. The author takes full responsibility for the correctness of this work.
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.DOI
- [2]A. Kontorovich, Minimizing total variation under constraint, MathOverflow, question 476847, August 13, 2024. https://mathoverflow.net/q/476847.
- [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.
- [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.DOI
- [5]A. Kontorovich, TV homogenization inequalities, preprint (2026), arXiv:2601.04079v3 [math.PR].arxiv.org/abs/2601.04079
- [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.DOI