betaFeedback

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 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.

Statement

For p∈[0,1]np \in[0,1]^n, let SpS_p be a sum of independent Bernoulli variables with parameters pip_i. Put

Dk(p,q)=P(Sp≥k)−P(Sq≥k),T(p,q)=max⁡1≤k≤nDk(p,q),Δ=∑i(pi−qi).D_k(p,q) = \mathbb{P}(S_p \ge k) - \mathbb{P}(S_q \ge k), \qquad T(p,q) = \max_{1 \le k \le n} D_k(p,q), \qquad\Delta= \sum_i (p_i-q_i).

For probability measures on a finite set, we use TV⁡(P,Q)=12∑x∣P(x)−Q(x)∣\operatorname{TV}(P,Q) = \frac{1}{2}\sum_x \lvert P(x) - Q(x)\rvert. We assume p≥qp \ge q coordinatewise. For n≥2n \ge2, 1≤j≤n−11 \le j \le n - 1, and 0<γ<10 < \gamma< 1, there is a unique pair 0<b<a<10 < b < a < 1 satisfying

a−b=γ,aj(1−a)n−j=bj(1−b)n−j.(1)a-b=\gamma,\qquad a^j(1-a)^{n-j}=b^j(1-b)^{n-j}. \tag*{(1)}

Define

Fn,j(γ)=P(Bin⁡(n,a)≥j)−P(Bin⁡(n,b)≥j),Bn(Δ)=Fn,⌊n/2⌋(Δ/n).F_{n,j}(\gamma)=\mathbb{P}(\operatorname{Bin}(n,a)\ge j)-\mathbb{P}(\operatorname{Bin}(n,b)\ge j),\qquad B_n(\Delta)=F_{n,\lfloor n/2\rfloor}(\Delta/n).

Set Bn(0)=0B_n(0)=0 and Bn(n)=1B_n(n)=1.

Theorem 1.1. For every n≥2n \ge2 and every p,q∈[0,1]np,q \in[0,1]^n with p≥qp \ge q,

T(p,q)≥Bn(Δ).(2)T(p,q) \ge B_n(\Delta). \tag*{(2)}

For n≥3n \ge3 and 0<Δ<n0 < \Delta< n, equality forces both vectors to be homogeneous. More precisely:

  1. If nn is even, equality holds exactly when pi=(1+Δ/n)/2p_i=(1+\Delta/n)/2 and qi=(1−Δ/n)/2q_i=(1-\Delta/n)/2 for all ii.

  1. If n=2m+1n=2m+1 is odd, let (a,b)(a,b) solve (1.1) with j=mj=m and γ=Δ/n\gamma=\Delta/n. Equality holds exactly for

(p,q)=(a1,b1)or(p,q)=((1−b)1,(1−a)1).(p,q)=(a\mathbf{1},b\mathbf{1})\quad\text{or}\quad(p,q)=((1-b)\mathbf{1},(1-a)\mathbf{1}).

The exact minimum of TV⁡(⨂iBer⁡(pi),⨂iBer⁡(qi))\operatorname{TV}(\bigotimes_i \operatorname{Ber}(p_i),\bigotimes_i \operatorname{Ber}(q_i)) under the same constraint is also Bn(Δ)B_n(\Delta), with the same equality cases for n≥3n \ge3 and 0<Δ<n0 < \Delta< n.

The exceptional equality cases for n=2n = 2 are classified in Proposition A.1 of Appendix § 7. For odd n=2m+1n = 2m + 1, the benchmark can also be written

B2m+1(Δ)=(2m+1)(2mm)∫ba[u(1−u)]m du.(3)B_{2m+1}(\Delta) = (2m+1)\binom{2m}{m}\int_b^a [u(1-u)]^m\,\mathrm{d}u. \tag*{(3)}

where (a,b)(a,b) is the switch with j=mj = m. Equivalently, let z>1z > 1 be the unique solution of

(zm−1)(zm+1−1)z2m+1−1=Δ2m+1.\frac{(z^m-1)(z^{m+1}-1)}{z^{2m+1}-1} = \frac{\Delta}{2m+1}.

Then

b=zm−1z2m+1−1,a=zm+1(zm−1)z2m+1−1.b = \frac{z^m-1}{z^{2m+1}-1}, \qquad a = \frac{z^{m+1}(z^m-1)}{z^{2m+1}-1}.

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

Bn(Δ)=2−n(nn/2)∫0Δ(1−u2/n2)n/2−1 du.B_n(\Delta) = 2^{-n}\binom{n}{n/2}\int_0^\Delta\left(1-u^2/n^2\right)^{n/2-1}\,\mathrm{d}u.

For n=3n = 3, (1.3) becomes

B3(Δ)=2Δ9(1+1−Δ2/12).B_3(\Delta) = \frac{2\Delta}{9}\left(1+\sqrt{1-\Delta^2/12}\right).

The proof proceeds by induction from n=2n = 2.

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 ∏i=1M(1−ti+tiz)\prod_{i=1}^{M}(1-t_i+t_i z), where 0<ti<10 < t_i < 1. Its zeros are real and negative. If its coefficients are a0,…,aMa_0,\ldots,a_M, Newton’s inequality (see [6]) gives, for 1≤j≤M−11 \le j \le M-1,

aj2≥aj−1aj+1(j+1)(M−j+1)j(M−j)>aj−1aj+1.a_j^2 \ge a_{j-1}a_{j+1}\frac{(j+1)(M-j+1)}{j(M-j)} > a_{j-1}a_{j+1}.

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 P(Z=k−1)=P(Z=k)>0\mathbb{P}(Z=k-1)=\mathbb{P}(Z=k)>0, and Z′Z' is obtained by a strict parameter increase, then

P(Z′=k)>0⟹P(Z′=k−1)<P(Z′=k).\mathbb{P}(Z'=k)>0 \quad\Longrightarrow\quad\mathbb{P}(Z'=k-1)<\mathbb{P}(Z'=k).

If the mass at kk disappears because the lower endpoint of the support moves past kk, both displayed masses of Z′Z' 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 RR, changing a parameter from uu to v>uv>u changes the mass at jj from (1−u)rj+urj−1(1-u)r_j+ur_{j-1} to (1−v)rj+vrj−1(1-v)r_j+vr_{j-1}. Their ratio increases with rj−1/rjr_{j-1}/r_j, which increases strictly in jj on the positive support by strict log-concavity. Equivalently, the relevant adjacent determinant is a positive multiple of rj−12−rj−2rjr_{j-1}^{2}-r_{j-2}r_j. Successive coordinate changes prove the assertion. Adjoining a variable is the change of an appended parameter from zero to its new value.

For ordered p,qp,q with Δ>0\Delta>0 and T(p,q)<1T(p,q)<1, 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 T=1T=1. For 1≤k≤n−11\le k\le n-1 and 0≤λ≤10\le\lambda\le1, define

H(x)=λP(Sx≥k)+(1−λ)P(Sx≥k+1).H(x)=\lambda\mathbb{P}(S_x\ge k)+(1-\lambda)\mathbb{P}(S_x\ge k+1).

An independent E∼Ber⁡(λ)E\sim\operatorname{Ber}(\lambda) gives H(x)=P(Sx+E≥k+1)H(x)=\mathbb{P}(S_x+E\ge k+1). Write Hi=∂iHH_i=\partial_iH and Cij=∂i∂jHC_{ij}=\partial_i\partial_jH. Direct differentiation gives

Hi(x)=P(Sx,−i+E=k),(4)H_i(x)=\mathbb{P}(S_{x,-i}+E=k), \tag*{(4)}
Cij(x)=P(Sx,−ij+E=k−1)−P(Sx,−ij+E=k),(5)C_{ij}(x)=\mathbb{P}(S_{x,-ij}+E=k-1)-\mathbb{P}(S_{x,-ij}+E=k), \tag*{(5)}
Hi(x)−Hj(x)=(xj−xi)Cij(x).(6)H_i(x)-H_j(x)=(x_j-x_i)C_{ij}(x). \tag*{(6)}

A pure threshold is included by taking λ=0\lambda=0 or 11. For fixed other coordinates, splitting two equal coordinates u,uu,u into u+t,u−tu+t,u-t changes HH by exactly −Cijt2-C_{ij}t^2.

Lemma 2.2 (A maximal-atom bound). Put

κn=(n⌊n/2⌋)(⌊n/2⌋n)⌊n/2⌋(⌈n/2⌉n)⌈n/2⌉.\kappa_n=\binom{n}{\lfloor n/2\rfloor} \left(\frac{\lfloor n/2\rfloor}{n}\right)^{\lfloor n/2\rfloor} \left(\frac{\lceil n/2\rceil}{n}\right)^{\lceil n/2\rceil}.

Every (n−1)(n-1)-trial Bernoulli sum has a mass at least κn\kappa_n. If at most two of the gaps pi−qip_i-q_i are positive, then

T(p,q)≥κnΔ.(7)T(p,q)\ge\kappa_n\Delta. \tag*{(7)}

Proof. First, an nn-trial Bernoulli sum of integer mean has probability at that integer at least κn\kappa_n. 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 u≠vu\ne v occur, then, with the others fixed, the objective has the form A+B(u+v)+CuvA+B(u+v)+Cuv. The transfer (u,v)↦(u+t,v−t)(u,v)\mapsto(u+t,v-t) is feasible for both signs of sufficiently small tt, so minimality gives C(v−u)=0C(v-u)=0. Thus C=0C=0, and replacing u,vu,v by their average preserves the objective while strictly decreasing the sum of squares, a contradiction. Consequently an extremizer is a deterministic shift plus Bin⁡(M,ℓ/M)\operatorname{Bin}(M,\ell/M) with integer ℓ\ell and M≤nM \le n. For

bM,ℓ=(Mℓ)(ℓ/M)ℓ(1−ℓ/M)M−ℓ,h(x)=xlog⁡(1+1/x),h(0)=0,b_{M,\ell}=\binom{M}{\ell}(\ell/M)^\ell(1-\ell/M)^{M-\ell},\qquad h(x)=x\log(1+1/x),\qquad h(0)=0,

ratio calculations give

log⁡bM,ℓbM,ℓ+1=h(M−ℓ−1)−h(ℓ),log⁡bM+1,ℓbM,ℓ=h(M−ℓ)−h(M).\log\frac{b_{M,\ell}}{b_{M,\ell+1}}=h(M-\ell-1)-h(\ell),\qquad\log\frac{b_{M+1,\ell}}{b_{M,\ell}}=h(M-\ell)-h(M).

The increasing function hh shows that the least nn-trial integer-mean mass is κn\kappa_n, and that increasing MM with ℓ\ell fixed can only decrease the mass. Deterministic cases give mass one.

If EZ=k+f\mathbb{E}Z=k+f with 0≤f≤10\le f\le1, adjoin Ber⁡(1−f)\operatorname{Ber}(1-f). Its mass at the integer mean k+1k+1 is (1−f)P(Z=k)+fP(Z=k+1)≥κn(1-f)\mathbb{P}(Z=k)+f\mathbb{P}(Z=k+1)\ge\kappa_n, proving the first assertion. This extra Bernoulli variable explains the index nn in the bound for an (n−1)(n-1)-trial sum.

For the second assertion, the case Δ=0\Delta=0 is immediate; assume Δ>0\Delta>0. Put ri=(pi+qi)/2r_i=(p_i+q_i)/2, di=pi−qid_i=p_i-q_i and wi=di/Δw_i=d_i/\Delta. When at most two did_i are nonzero, symmetric expansion of the generating polynomials gives exactly

Dj+1Δ=∑iwiP(Sr,−i=j).\frac{D_{j+1}}{\Delta}=\sum_i w_i\mathbb{P}(S_{r,-i}=j).

This deletion mixture is an (n−1)(n-1)-trial Bernoulli law. For completeness, its generating polynomial is G(z)=∑iwi∏ℓ≠i(1−rℓ+rℓz)G(z)=\sum_i w_i\prod_{\ell\ne i}(1-r_\ell+r_\ell z). For distinct interior rir_i 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 GG has only negative real zeros, and G(1)=1G(1)=1 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 WW is a fixed Bernoulli sum and

gM(t)=P(Bin⁡(M,t)+W=k),(8)g_M(t)=\mathbb{P}(\operatorname{Bin}(M,t)+W=k), \tag*{(8)}

then

gM′(t)=M{P(Bin⁡(M−1,t)+W=k−1)−P(Bin⁡(M−1,t)+W=k)}.g'_M(t)=M\{\mathbb{P}(\operatorname{Bin}(M-1,t)+W=k-1)-\mathbb{P}(\operatorname{Bin}(M-1,t)+W=k)\}.

The derivative formula is used for M≥1M\ge1; g0g_0 is simply a constant. On 0<t<10<t<1 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 M≥2M\ge2. For M=1M=1 an interior critical point means that g1g_1 is constant.

We also need the following adjoining rule, with its positivity condition explicit: if a Bernoulli sum ZZ satisfies

P(Z=k−1)≤P(Z=k),P(Z=k)>0,\mathbb{P}(Z=k-1)\le\mathbb{P}(Z=k),\qquad\mathbb{P}(Z=k)>0,

then adjoining further independent Bernoulli variables cannot increase its mass at kk. Indeed, write a=P(Z=k−2)a=\mathbb{P}(Z=k-2), b=P(Z=k−1)b=\mathbb{P}(Z=k-1) and c=P(Z=k)>0c=\mathbb{P}(Z=k)>0. Log-concavity and interval support give a≤b≤ca\le b\le c. After adjoining Ber⁡(t)\operatorname{Ber}(t) the relevant masses are (1−t)b+ta(1-t)b+ta and (1−t)c+tb(1-t)c+tb, so their order persists and the mass at kk does not increase. If that mass becomes zero, the support has moved strictly above kk, and further adjoining cannot recreate it. If b=c>0b=c>0 and t>0t>0, strict log-concavity gives a<ba<b; the first addition makes the adjacent difference strictly negative, and a second addition with positive parameter strictly decreases the mass at kk. All uses of this rule below start with a positive mass at kk.

Corollary 2.3 (Derivative criterion for adjoining). Let gMg_M be as in (2.5), with M≥1M \ge1 and 0<t<10 < t < 1. If gM(t)>0g_M(t) > 0 and gM′(t)≤0g'_M(t) \le0, then

P(Bin⁡(M,t)+W=k−1)≤P(Bin⁡(M,t)+W=k).\mathbb{P}(\operatorname{Bin}(M,t)+W=k-1) \le\mathbb{P}(\operatorname{Bin}(M,t)+W=k).

Consequently adjoining further independent Bernoulli variables cannot increase the mass at kk.

Proof. Write Y=Bin⁡(M−1,t)+WY=\operatorname{Bin}(M-1,t)+W and yj=P(Y=j)y_j=\mathbb{P}(Y=j). The derivative condition gives yk−1≤yky_{k-1}\le y_k, and gM(t)>0g_M(t)>0 then implies yk>0y_k>0. Log-concavity and interval support give yk−2≤yk−1≤yky_{k-2}\le y_{k-1}\le y_k. For Z=Y+Ber⁡(t)Z=Y+\operatorname{Ber}(t), it follows that

P(Z=k−1)=(1−t)yk−1+tyk−2≤(1−t)yk+tyk−1=P(Z=k).\mathbb{P}(Z=k-1)=(1-t)y_{k-1}+ty_{k-2}\le(1-t)y_k+ty_{k-1}=\mathbb{P}(Z=k).

The adjoining rule applies. □

The homogeneous problem in both parities

Suppress the first index in Fn,jF_{n,j}, and write c=j/nc=j/n. Let (a,b)(a,b) satisfy (1.1), and set

v=c(1−c),x=a−c,y=c−b,R=xyv,fj(γ)=(nj)aj(1−a)n−j.v=c(1-c), \qquad x=a-c, \qquad y=c-b, \qquad R=\frac{xy}{v}, \qquad f_j(\gamma)=\binom{n}{j}a^j(1-a)^{n-j}.

Here x,y>0x,y>0, and

v(1−R)=c(1−a)(1−b)+(1−c)ab>0.(9)v(1-R)=c(1-a)(1-b)+(1-c)ab>0. \tag*{(9)}

The binomial masses at count jj agree, so thresholds j,j+1j,j+1 tie and both equal Fj(γ)F_j(\gamma).

Lemma 3.1 (Switch identities). Primes denote differentiation in γ\gamma. Then

Fj′=nfj1−R,fj′fj=−nRγ(1−R).(10)F'_j=\frac{nf_j}{1-R}, \qquad\frac{f'_j}{f_j}=-\frac{nR}{\gamma(1-R)}. \tag*{(10)}

Consequently,

Fj(γ)=(n+1)∫0γfj(u) du−γfj(γ),∫01fj(u) du=1n+1.(11)F_j(\gamma)=(n+1)\int_0^\gamma f_j(u)\,\mathrm{d}u-\gamma f_j(\gamma), \qquad\int_0^1 f_j(u)\,\mathrm{d}u=\frac{1}{n+1}. \tag*{(11)}

For fixed γ∈(0,1)\gamma\in(0,1), RR is strictly decreasing in cc on (0,1/2)(0,1/2). Also R′≤2R/γR'\le2R/\gamma.

Proof. The equation defining bb has derivative

−γ{cab+1−c(1−a)(1−b)}<0-\gamma\left\{\frac{c}{ab}+\frac{1-c}{(1-a)(1-b)}\right\}<0

in bb, with opposite infinite endpoint limits. This proves existence and uniqueness of the switch. Differentiating the equal-height equation and a−b=γa-b=\gamma, and using (3.1), gives

a′=ya(1−a)γv(1−R),b′=−xb(1−b)γv(1−R).a'=\frac{ya(1-a)}{\gamma v(1-R)}, \qquad b'=-\frac{xb(1-b)}{\gamma v(1-R)}.

Differentiation of the binomial tail proves (3.2). In particular Fj′=nfj−γfj′F'_j=nf_j-\gamma f'_j. Integration, followed by Fj(1)=1F_j(1)=1 and fj(1)=0f_j(1)=0, proves (3.3).

We give the geometric monotonicity explicitly. Suppose c≤1/2c \le1/2, and put z=1−2cz = 1 - 2c and e=a+b−2c=x−ye = a + b - 2c = x - y. Let A=logit⁡(a)A = \operatorname{logit}(a), B=logit⁡(b)B = \operatorname{logit}(b), M=(A+B)/2M = (A + B)/2, s=(A−B)/2s = (A - B)/2, and σ(t)=et/(1+et)\sigma(t) = e^t/(1 + e^t). The equal-height equation says

c=12s∫M−sM+sσ(t) dt.c = \frac{1}{2s}\int_{M-s}^{M+s} \sigma(t)\,\mathrm{d}t.

Thus M≤0M \le0. The identity

σ(M+u)+σ(M−u)=1+sinh⁡Mcosh⁡M+cosh⁡u\sigma(M + u) + \sigma(M - u) = 1 + \frac{\sinh M}{\cosh M + \cosh u}

shows that the paired average increases with u≥0u \ge0. Hence σ(M)≤c≤(a+b)/2\sigma(M) \le c \le(a + b)/2, strictly if c<1/2c < 1/2. The first inequality is equivalent to

c2(1−a)(1−b)−(1−c)2ab=v(zR−e)≥0,c^2(1-a)(1-b) - (1-c)^2ab = v(zR-e) \ge0,

and the second gives e≥0e \ge0.

Now keep γ\gamma fixed and differentiate in the continuous parameter cc. The derivative t=∂ca=∂cbt = \partial_c a = \partial_c b is positive, since the derivative of the switch equation in cc is A−B>0A - B > 0 whereas its derivative in bb is negative. Therefore

∂cR=−(zR−e)+etv<0(0<c<1/2).(12)\partial_c R = -\frac{(zR-e)+et}{v} < 0 \qquad(0 < c < 1/2). \tag*{(12)}

Finally set θ=x/γ\theta= x/\gamma. Differentiation gives θ′=(zR−e)/[γ2(1−R)]≥0\theta' = (zR-e)/[\gamma^2(1-R)] \ge0, and e≥0e \ge0 gives θ≥1/2\theta\ge1/2. Since R/γ2=θ(1−θ)/vR/\gamma^2 = \theta(1-\theta)/v, its derivative is nonpositive. Reflection covers c>1/2c > 1/2 and proves the last assertion. □

Proposition 3.2 (Strict ordering of switches). For 1≤i<j≤n/21 \le i < j \le n/2 and 0<γ<10 < \gamma< 1,

Fn,i(γ)>Fn,j(γ).F_{n,i}(\gamma) > F_{n,j}(\gamma).

Consequently the homogeneous minimum is Bn(Δ)B_n(\Delta), with exactly the central switch when nn is even and the two reflected central switches when nn is odd. For n≥3n \ge3, BnB_n is strictly concave on (0,n)(0,n) and

0<Bn(Δ)<min⁡{κnΔ,1}(0<Δ<n).(13)0 < B_n(\Delta) < \min\{\kappa_n\Delta,1\} \qquad(0 < \Delta< n). \tag*{(13)}

Proof. By (3.4), Ri>RjR_i > R_j. Thus

(log⁡fifj)′=−nγ(Ri1−Ri−Rj1−Rj)<0.\left(\log\frac{f_i}{f_j}\right)' = -\frac{n}{\gamma}\left(\frac{R_i}{1-R_i} - \frac{R_j}{1-R_j}\right) < 0.

The equal integrals in (3.3) imply that h=fi−fjh = f_i - f_j changes sign exactly once, from positive to negative. Where h>0h > 0, writing Aℓ=nRℓ/[γ(1−Rℓ)]A_\ell= nR_\ell/[\gamma(1-R_\ell)] gives h′=−Aih−(Ai−Aj)fj<0h' = -A_i h - (A_i-A_j)f_j < 0. Before the crossing, ∫0γh≥γh(γ)>0\int_0^\gamma h \ge\gamma h(\gamma) > 0, and afterwards ∫γ1h=−∫0γh>0\int_\gamma^1 h = -\int_0^\gamma h > 0. In both cases

Fi−Fj=(n+1)∫0γh−γh(γ)>0.F_i - F_j = (n+1)\int_0^\gamma h - \gamma h(\gamma) > 0.

Reflection gives Fn,j=Fn,n−jF_{n,j} = F_{n,n-j}.

It remains to justify that switches exhaust the homogeneous minima. Define

Dh(a,b)=Dh(a1,b1),Mγ(b)=max⁡1≤h≤nDh(b+γ,b).D_h(a,b) = D_h(a_1,b_1), \qquad M_\gamma(b) = \max_{1\le h\le n} D_h(b+\gamma,b).

At fixed γ\gamma, each threshold difference has the form

Dh(b+γ,b)=n∫bb+γ(n−1h−1)uh−1(1−u)n−h du.\mathcal{D}_h(b+\gamma,b)=n\int_b^{b+\gamma}\binom{n-1}{h-1}u^{h-1}(1-u)^{n-h}\,\mathrm{d}u.

Its derivative has the sign of the ratio of the two endpoint densities minus one. Strict log-concavity makes that ratio strictly decreasing in bb, so the individual threshold difference has no interior local minimum. Suppose that b0∈(0,1−γ)b_0\in(0,1-\gamma) is a local minimum of MγM_\gamma. If exactly one threshold is active at b0b_0, its strict separation from the other finitely many thresholds persists in a neighborhood. There MγM_\gamma equals that threshold difference, a contradiction. Thus at least two thresholds are active. Here 0<b0<b0+γ<10<b_0<b_0+\gamma<1, so both count laws have full support and T<1T<1. The active-threshold property in Section 2 therefore shows that they are exactly two adjacent thresholds k,k+1k,k+1. Their equality is equivalent to

P(Bin⁡(n,b0+γ)=k)=P(Bin⁡(n,b0)=k),\mathbb{P}(\operatorname{Bin}(n,b_0+\gamma)=k)=\mathbb{P}(\operatorname{Bin}(n,b_0)=k),

so b0b_0 is a switch. The homogeneous minimum is therefore attained at a switch or at b=0,1−γb=0,1-\gamma. At an endpoint its value is 1−(1−γ)n1-(1-\gamma)^n, 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 ⌊n/2⌋+1\lfloor n/2\rfloor+1.

Finally (10) and R′≤2R/γR'\le2R/\gamma give

(log⁡Fj′)′≤−(n−2)Rγ(1−R)<0(n≥3).(\log F'_j)'\le-\frac{(n-2)R}{\gamma(1-R)}<0\qquad(n\ge3).

For the central index j=⌊n/2⌋j=\lfloor n/2\rfloor, as γ↓0\gamma\downarrow0 we have a,b→j/na,b\to j/n and R→0R\to0. Since Δ=nγ\Delta=n\gamma,

Bn′(0+)=lim⁡γ↓01nFn,j′(γ)=lim⁡γ↓0fj(γ)1−R(γ)=(nj)(jn)j(1−jn)n−j=κn.B_n'(0+)=\lim_{\gamma\downarrow0}\frac{1}{n}F'_{n,j}(\gamma)=\lim_{\gamma\downarrow0}\frac{f_j(\gamma)}{1-R(\gamma)}=\binom{n}{j}\left(\frac{j}{n}\right)^j\left(1-\frac{j}{n}\right)^{n-j}=\kappa_n.

Strict concavity, together with Bn(0)=0B_n(0)=0 and Bn(n)=1B_n(n)=1, proves (13).

Removing a common deterministic coordinate

The following strict dimension improvement supplies the boundary step in the induction.

Lemma 4.1. Let N≥2N\ge2. For every 0<Δ≤N0<\Delta\le N, there is an ordered (N+1)(N+1)-dimensional pair of gap Δ\Delta with tail objective strictly less than BN(Δ)B_N(\Delta).

Proof. For Δ=N\Delta=N, any strictly interior ordered pair of that gap has T<1=BN(N)T<1=B_N(N). Suppose 0<Δ<N0<\Delta<N and take a homogeneous central switch pair (a1,b1)(a_1,b_1) in dimension NN, with switch index jj, common mass f>0f>0, and geometric quantity R>0R>0 from Lemma 3.1. Set

ρ=(N−j)ab(N−j)ab+j(1−a)(1−b)∈(0,1).\rho=\frac{(N-j)ab}{(N-j)ab+j(1-a)(1-b)}\in(0,1).

The density

g(u)=ρP(Bin⁡(N−1,u)=j−1)+(1−ρ)P(Bin⁡(N−1,u)=j)g(u)=\rho\mathbb{P}(\operatorname{Bin}(N-1,u)=j-1)+(1-\rho)\mathbb{P}(\operatorname{Bin}(N-1,u)=j)

satisfies, by substitution,

g(a)=g(b)=f1−R.(14)g(a)=g(b)=\frac{f}{1-R}. \tag*{(14)}

Adjoin the common parameter ρ\rho. To identify the active threshold, write DhD_h for the old tail differences and set D0=DN+1=0D_0 = D_{N+1} = 0. The new differences satisfy

D~h=(1−ρ)Dh+ρDh−1,1≤h≤N+1.\widetilde{D}_h = (1-\rho)D_h + \rho D_{h-1}, \qquad1 \le h \le N+1.

Exactly the old thresholds j,j+1j, j+1 attain BN(Δ)B_N(\Delta). Since 0<ρ<10 < \rho< 1, the new threshold j+1j+1 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 j+1j+1 is the unique maximizing threshold. For small ε>0\varepsilon> 0 replace the parameters by

pε=((a−ε2N)N,ρ+ε2),qε=((b+ε2N)N,ρ−ε2).p_\varepsilon= \left(\left(a-\frac{\varepsilon}{2N}\right)^N,\rho+\frac{\varepsilon}{2}\right), \qquad q_\varepsilon= \left(\left(b+\frac{\varepsilon}{2N}\right)^N,\rho-\frac{\varepsilon}{2}\right).

Here a superscript on a coordinate denotes repetition. The gap remains Δ\Delta and the pair is feasible. By (14), the unique active tail has derivative at zero

f−g(a)+g(b)2=f−f1−R<0.f-\frac{g(a)+g(b)}{2}=f-\frac{f}{1-R}<0.

It remains the maximizing tail for sufficiently small ε\varepsilon. This proves the strict improvement.

The global minimizer

We prove Theorem 1.1 by induction. For n=2n=2, D1+D2=ΔD_1+D_2=\Delta, so T≥Δ/2=B2(Δ)T\ge\Delta/2=B_2(\Delta), attained by the complementary homogeneous pair. Fix n≥3n\ge3, assume the theorem’s minimum-value assertion in dimension n−1n-1, and let (p,q)(p,q) be a global minimizer at a fixed gap 0<Δ<n0<\Delta<n. Compactness gives its existence. Its value is at most the homogeneous candidate Bn(Δ)B_n(\Delta).

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 Δ≤n−1\Delta\le n-1; deleting it would give T≥Bn−1(Δ)T\ge B_{n-1}(\Delta), whereas a strict improvement is available. Thus pi>0p_i>0 and qi<1q_i<1 for every ii. Also pp cannot be identically one, nor qq identically zero. For example, if p=1p=1, then

T=1−∏iqi≥1−(1−Δn)n>Bn(Δ),T=1-\prod_i q_i\ge1-\left(1-\frac{\Delta}{n}\right)^n>B_n(\Delta),

where the strict endpoint comparison was proved above.

Write

I={i:pi>qi},C={i:pi=qi},r=∣I∣≥3,s=∣C∣.I=\{i:p_i>q_i\}, \qquad C=\{i:p_i=q_i\}, \qquad r=|I|\ge3,\qquad s=|C|.

All common parameters, when present, are strictly interior.

Stationarity and common coordinates

There are one or two adjacent active thresholds. Choose their convex combination HH 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 cc for the total gap, these conditions read, for i∈Ii\in I,

pi<1⟹Hi(p)=c,pi=1⟹Hi(p)≤c,qi>0⟹Hi(q)=c,qi=0⟹Hi(q)≤c.(15)\begin{aligned} p_i<1 &\Longrightarrow H_i(p)=c, &\qquad p_i=1 &\Longrightarrow H_i(p)\le c, \\ q_i>0 &\Longrightarrow H_i(q)=c, &\qquad q_i=0 &\Longrightarrow H_i(q)\le c. \tag*{(15)} \end{aligned}

and, for i∈Ci\in C,

Hi(p)=Hi(q)=c+νi,νi≥0.(16)H_i(p)=H_i(q)=c+\nu_i,\qquad\nu_i\ge0. \tag*{(16)}

The signs follow, for example, by using H(p)−H(q)−c(∑i(pi−qi)−Δ)−∑i∈Cνi(pi−qi)H(p)-H(q)-c(\sum_i(p_i-q_i)-\Delta)-\sum_{i\in C}\nu_i(p_i-q_i) as the Lagrangian, together with the endpoint constraints.

We first establish, without any nonconstancy assumption, that

c>0.(17)c>0. \tag*{(17)}

Write the supports of Sp,SqS_p,S_q as [L,n][L,n] and [0,U][0,U]. Since T<1T<1, we have L≤UL\le U. For every changing coordinate ii, the derivative of the pure threshold hh at pp is positive whenever L+1≤h≤nL+1\le h\le n, and its derivative at qq is positive whenever 1≤h≤U1\le h\le U. This follows from the deletion supports and includes pi=1p_i=1 and qi=0q_i=0. Every threshold belongs to at least one of these two ranges. Therefore their active convex combination satisfies

0<Hi(p)+Hi(q)≤2c(i∈I),0<H_i(p)+H_i(q)\le2c \qquad(i\in I),

where the upper bound follows from (5.1)–(5.2). This proves (17).

If there is only one active threshold hh and a common coordinate tt, stationarity in tt gives P(Sp,−i=h−1)=P(Sq,−i=h−1)\mathbb{P}(S_{p,-i}=h-1)=\mathbb{P}(S_{q,-i}=h-1). These are positive masses. Indeed, write the original supports as [L,n][L,n] and [0,U][0,U]. Deleting the common interior coordinate gives supports [L,n−1][L,n-1] and [0,U−1][0,U-1]. Both masses at h−1h-1 could vanish only if h≤Lh\le L and h≥U+1h\ge U+1, forcing L>UL>U and hence T=1T=1. Likelihood-ratio ordering then says that the two deletion tails at h−1,hh-1,h 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 C≠∅C\ne\varnothing, there are two active thresholds k,k+1k,k+1. For a common coordinate tt, put uj=P(Sp,−i=j)−P(Sq,−i=j)u_j=\mathbb{P}(S_{p,-i}=j)-\mathbb{P}(S_{q,-i}=j). The active tie and (16) give

tuk−1+(1−t)uk=0,λuk−1+(1−λ)uk=0.tu_{k-1}+(1-t)u_k=0,\qquad\lambda u_{k-1}+(1-\lambda)u_k=0.

The tied count lies in the overlap, so L≤k≤UL\le k\le U. The deletion supports are [L,n−1][L,n-1] and [0,U−1][0,U-1]; the upper deletion mass at kk and the lower deletion mass at k−1k-1 are positive. If uk−1=uk=0u_{k-1}=u_k=0, 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

t=λ∈(0,1)for every common coordinate.(18)t=\lambda\in(0,1)\quad\text{for every common coordinate.} \tag*{(18)}

In particular all common coordinates agree. Their derivative is exactly the original mass at the tied count. That mass is positive because SpS_p has support [L,n][L,n] and L≤k≤n−1L\le k\le n-1. Thus

Hi(p)=Hi(q)=f:=P(Sp=k)=P(Sq=k)>0(i∈C),f=c+ν,ν≥0.(19)H_i(p)=H_i(q)=f:=\mathbb{P}(S_p=k)=\mathbb{P}(S_q=k)>0\quad(i\in C),\qquad f=c+\nu,\quad\nu\ge0. \tag*{(19)}

One changing vector is homogeneous

For i,j∈Ii,j\in I, (15) and (6) show

pi≠pj⟹Cij(p)≥0;p_i\ne p_j\quad\Longrightarrow\quad C_{ij}(p)\ge0;

indeed distinct interior entries have equal gradients, and a larger entry equal to one has no larger gradient. Likewise

qi≠qj⟹Cij(q)≤0.q_i\ne q_j\quad\Longrightarrow\quad C_{ij}(q)\le0.

Suppose that both pi≠pjp_i\ne p_j and qi≠qjq_i\ne q_j. The laws in (5) are ordered in likelihood ratio, and at least one of the other changing coordinates increases strictly because r≥3r\ge3. The upper deletion law has positive mass at k−1k-1: this follows from a free gradient equal to c>0c>0 and its nonnegative adjacent difference. Similarly the lower deletion law has positive mass at kk. Their ordered interval supports therefore make both adjacent masses positive in both laws. If Ap,BpA_p,B_p denote the upper deletion masses at k−1,kk-1,k, and Aq,BqA_q,B_q the corresponding lower deletion masses, then the coefficient signs and Lemma 2.1 would give

1≤ApBp<AqBq≤1,1 \le\frac{A_p}{B_p} < \frac{A_q}{B_q} \le1,

a contradiction. Thus every pair satisfies pi=pjp_i=p_j or qi=qjq_i=q_j. The elementary consequence is that one of pI,qIp_I,q_I is constant: two different values in one vector force all entries of the other to agree. Reflection lets us assume

pi=a(i∈I).(20)p_i=a \quad(i\in I). \tag*{(20)}

Here reflection means (p,q)↦(1−q,1−p)(p,q)\mapsto(1-q,1-p); it preserves Δ\Delta and TT, with DhD_h sent to Dn−h+1D_{n-h+1}.

If a=1a=1, then s>0s>0, since the all-one vector was excluded. By (19) and (15), for a common coordinate ii and a changing coordinate jj,

(1−λ)Cij(p)=Hi(p)−Hj(p)≥0.(1-\lambda)C_{ij}(p)=H_i(p)-H_j(p)\ge0.

Consider h(t1,…,tr)=P(∑j=1rBer⁡(tj)+Bin⁡(s,λ)=k)h(t_1,\ldots,t_r)=\mathbb{P}\left(\sum_{j=1}^{r}\operatorname{Ber}(t_j)+\operatorname{Bin}(s,\lambda)=k\right). Its partial derivatives at t=1t=1 equal Cij(p)≥0C_{ij}(p)\ge0. Along the path from qIq_I to 11, the deletion laws are strictly smaller in likelihood ratio than the endpoint deletion law (r−1)+Bin⁡(s,λ)(r-1)+\operatorname{Bin}(s,\lambda). Its two relevant masses are positive because r≤k≤n−1r\le k\le n-1, so k−rk-r and k−r+1k-r+1 both lie in {0,…,s}\{0,\ldots,s\}. All partial derivatives are therefore positive in the interior of this path. It follows that h(1)>h(qI)h(1)>h(q_I), contradicting the active mass equality. Hence

0<a<1.(21)0<a<1. \tag*{(21)}

The other changing vector is homogeneous

Fix the common coordinates and set

W∼Bin⁡(s+1,λ),gM(t)=P(Bin⁡(M,t)+W=k).W\sim\operatorname{Bin}(s+1,\lambda),\qquad g_M(t)=\mathbb{P}(\operatorname{Bin}(M,t)+W=k).

This notation includes deterministic WW when s=0s=0 and λ\lambda is an endpoint. By (20), (21), and (15),

c=gr−1(a)>0.(22)c=g_{r-1}(a)>0. \tag*{(22)}

Every positive qiq_i, i∈Ii\in I, is less than aa and is a free coordinate. Its gradient is cc.

There are at most two distinct positive values among these qiq_i. Indeed, suppose three such coordinates have distinct values t1,t2,t3t_1,t_2,t_3, and let rjr_j be the masses of the law with those three coordinates deleted and EE adjoined. Put A=rk−2−rk−1A=r_{k-2}-r_{k-1} and B=rk−1−rkB=r_{k-1}-r_k. The pair coefficients vanish by (6), giving (1−tℓ)B+tℓA=0(1-t_\ell)B+t_\ell A=0 for ℓ=1,2,3\ell=1,2,3. Subtracting two equations yields A=BA=B, and then A=B=0A=B=0. Thus rk−2=rk−1=rkr_{k-2}=r_{k-1}=r_k. Their common value equals a free gradient, which is a convex combination of these three masses, and hence equals c>0c>0. This contradicts strict log-concavity.

If two positive values u<vu<v occur, the smaller value occurs only once. Otherwise split two uu coordinates. The coefficient for a pair u,vu,v is zero, so its deletion law ZuvZ_{uv}, with EE adjoined, has equal masses at k−1,kk-1,k. The free-gradient identity

c=(1−v)P(Zuv=k)+vP(Zuv=k−1)c=(1-v)\mathbb{P}(Z_{uv}=k)+v\mathbb{P}(Z_{uv}=k-1)

shows that both equal masses are c>0c > 0. The deletion law for two uu coordinates replaces the remaining uu by vv. Since $0 < u < v < a < 1$, this replacement preserves the support and both adjacent masses stay positive. Strict likelihood-ratio ordering therefore gives Cuv<0C_{uv} < 0. The objective H(p)−H(q)H(p) - H(q) then has negative second variation Cuut2C_{uu}t^2 along the split. For a single active threshold this is an immediate contradiction. For two active thresholds keep their tie exactly: an unequal u,vu,v transfer has nonzero first derivative of G=P(Sp=k)−P(Sq=k)G = \mathbb{P}(S_p = k) - \mathbb{P}(S_q = k), whereas the equal-coordinate split has zero first derivative. To check nonvanishing, write the coefficient as λA+(1−λ)B=0\lambda A + (1 - \lambda)B = 0, where

A=P(R=k−2)−P(R=k−1),B=P(R=k−1)−P(R=k)A = \mathbb{P}(R = k - 2) - \mathbb{P}(R = k - 1), \qquad B = \mathbb{P}(R = k - 1) - \mathbb{P}(R = k)

and RR excludes those two coordinates, without EE. If A−B=0A - B = 0, then A=B=0A = B = 0, so the three consecutive masses of RR are equal. Their common value is Hi(q)=c>0H_i(q) = c > 0 for the coordinate with value uu: adjoining Ber⁡(v)\operatorname{Ber}(v) and EE takes a convex combination of those three masses. Strict log-concavity gives a contradiction. In fact, along the transfer that increases a uu coordinate and decreases a vv coordinate,

dGds=−(v−u)(A−B)≠0.\frac{\mathrm{d}G}{\mathrm{d}s} = -(v-u)(A-B) \ne0.

Let v0v_0 denote the equal-coordinate split direction and w0w_0 this unequal transfer direction, both acting on qq alone. For q(t,s)=q+tv0+sw0q(t,s) = q + tv_0 + sw_0, we have Gt(0,0)=0G_t(0,0) = 0 and Gs(0,0)≠0G_s(0,0) \ne0. The implicit-function theorem gives s(t)=O(t2)s(t) = O(t^2) with G(t,s(t))=0G(t,s(t)) = 0. Both directions have coordinate sum zero. Moreover, for J(t,s)=H(p)−H(q(t,s))J(t,s) = H(p) - H(q(t,s)), the free-gradient equalities give Jt(0,0)=Js(0,0)=0J_t(0,0) = J_s(0,0) = 0. Consequently

J(t,s(t))=J(0,0)+Cuut2+O(t3)<J(0,0)J(t,s(t)) = J(0,0) + C_{uu}t^2 + O(t^3) < J(0,0)

for sufficiently small nonzero tt. All other thresholds remain strictly below the two tied active thresholds by continuity. On this curve T=JT = J, so this is a genuine feasible decrease of the original maximum, not merely of a supporting test. All moves stay strictly between zero and aa, contradicting minimality.

Suppose now that the positive entries are one u<vu < v and MM copies of vv, with bb zero entries; thus r=M+b+1r = M + b + 1. Deleting uu gives c=gM(v)c = g_M(v), while the zero u,vu,v coefficient gives gM′(v)=0g'_M(v) = 0. Consequently gM(v)g_M(v) is its maximum. If M≥2M \ge2, then a>va > v gives gM(a)<gM(v)g_M(a) < g_M(v) and gM′(a)<0g'_M(a) < 0. The mass gM(a)g_M(a) is positive because the support is fixed on 0<t<10 < t < 1 and gM(v)=c>0g_M(v) = c > 0. Corollary 2.3 therefore gives

gM+b(a)≤gM(a)<gM(v)=c,g_{M+b}(a) \le g_M(a) < g_M(v) = c,

contradicting (22). If M=1M = 1, the function is constant and b≥1b \ge1 because r≥3r \ge3. The law WW has equal positive masses at k−1,kk-1,k. Adding one Ber⁡(a)\operatorname{Ber}(a) preserves the mass cc at kk but makes the adjacent difference strictly negative. The second addition therefore gives g2(a)<g1(a)=cg_2(a) < g_1(a) = c, and further additions cannot increase the mass. Thus there cannot be two positive values.

Finally suppose that there are MM copies of a single positive value vv and b≥1b \ge1 zeros, so r=M+br = M + b. A positive-coordinate derivative and a zero-coordinate derivative give

c=gM−1(v),gM(v)≤c.c = g_{M-1}(v), \qquad g_M(v) \le c.

For R0=Bin⁡(M−1,v)+WR_0 = \operatorname{Bin}(M - 1,v) + W, the identity

gM(v)−gM−1(v)=v{P(R0=k−1)−P(R0=k)}≤0g_M(v) - g_{M-1}(v) = v\{\mathbb{P}(R_0 = k - 1) - \mathbb{P}(R_0 = k)\} \le0

shows that P(R0=k−1)≤P(R0=k)=c>0\mathbb{P}(R_0 = k - 1) \le\mathbb{P}(R_0 = k) = c > 0, since v>0v > 0. Adjoin bb Bernoulli variables with parameter aa and then raise the original M−1M-1 parameters from vv to aa. Every step can only decrease the mass at kk. For the raising steps, its deletion law dominates R0R_0: one appended a>va>v replaces the deleted vv, 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 b=1b=1, there is a parameter to raise because r≥3r\ge3, and that raising step is strict. Hence again gr−1(a)<cg_{r-1}(a)<c, a contradiction.

We have proved that qI=b1q_I=b1 for some 0≤b<a0\le b<a. The case b=0b=0 is excluded either by the all-zero-vector endpoint comparison when s=0s=0, or by reflection of the a=1a=1 argument when s>0s>0. Therefore

0<b<a<1.(23)0<b<a<1. \tag*{(23)}

No unchanged coordinate remains

Suppose s>0s>0. Recalling (18) and (23), we have

p=(ar,λs),q=(br,λs),0<b<a<1.p=(a^r,\lambda^s),\qquad q=(b^r,\lambda^s),\qquad0<b<a<1.

Set

g(t)=P(Bin⁡(r−1,t)+Bin⁡(s+1,λ)=k),g(t)=\mathbb{P}(\operatorname{Bin}(r-1,t)+\operatorname{Bin}(s+1,\lambda)=k),
h(t)=P(Bin⁡(r−1,t)+Bin⁡(s,λ)=k−1)−P(Bin⁡(r−1,t)+Bin⁡(s,λ)=k).h(t)=\mathbb{P}(\operatorname{Bin}(r-1,t)+\operatorname{Bin}(s,\lambda)=k-1)-\mathbb{P}(\operatorname{Bin}(r-1,t)+\operatorname{Bin}(s,\lambda)=k).

The free gradients and common-coordinate gradients give

g(a)=g(b)=c,ν=(a−λ)h(a)=(b−λ)h(b)≥0.(24)g(a)=g(b)=c,\qquad\nu=(a-\lambda)h(a)=(b-\lambda)h(b)\ge0. \tag*{(24)}

Since r−1≥2r-1\ge2, gg has a unique mode u∈(b,a)u\in(b,a). At that point the law Bin⁡(r−2,u)+Bin⁡(s+1,λ)\operatorname{Bin}(r-2,u)+\operatorname{Bin}(s+1,\lambda) has equal positive masses at k−1,kk-1,k. All laws compared below have n−1n-1 strictly interior Bernoulli parameters, including those obtained by intermediate replacements. They therefore have positive masses at both k−1k-1 and kk.

If λ≤b\lambda\le b, then u>λu>\lambda. Replacing one λ\lambda parameter by uu increases this deletion law strictly in likelihood ratio, so h(u)<0h(u)<0 and hence h(a)<0h(a)<0. This makes (a−λ)h(a)<0(a-\lambda)h(a)<0. If λ≥a\lambda\ge a, the reflected argument gives h(b)>0h(b)>0 and (b−λ)h(b)<0(b-\lambda)h(b)<0. In the remaining case b<λ<ab<\lambda<a, nonnegativity in (24) would force h(b)≤0≤h(a)h(b)\le0\le h(a), impossible because increasing tt crosses the adjacent-mass equality only from positive to negative, strictly. Every case contradicts (24). Thus s=0s=0.

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 n≥3n\ge3, and completes the induction.

Product total variation and endpoints

For the threshold event Ek={x:∑ixi≥k}E_k=\{x:\sum_i x_i\ge k\},

TV⁡(⨂iBer⁡(pi),⨂iBer⁡(qi))≥Dk(p,q).\operatorname{TV}\left(\bigotimes_i\operatorname{Ber}(p_i),\bigotimes_i\operatorname{Ber}(q_i)\right)\ge D_k(p,q).

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 Bn(Δ)B_n(\Delta), and equality for n≥3n\ge3 forces equality in the tail comparison, giving the same classification. At Δ=0\Delta=0, ordering forces p=qp=q, and every such pair minimizes. At Δ=n\Delta=n, feasibility forces p=1,q=0p=1,q=0. The nonunique two-dimensional equality families are proved in Appendix A.

Two-dimensional equality families

For x∈[0,1]2x \in[0,1]^2, write Px=Ber⁡(x1)⊗Ber⁡(x2)P_x = \operatorname{Ber}(x_1) \otimes\operatorname{Ber}(x_2).

Proposition A.1. Let p,q∈[0,1]2p,q \in[0,1]^2 satisfy p≥qp \ge q, and put di=pi−qid_i = p_i-q_i, Δ=d1+d2\Delta= d_1+d_2, and A=p1p2−q1q2A = p_1p_2-q_1q_2. Then

T(p,q)=Δ2+∣A−Δ2∣,(25)T(p,q)=\frac{\Delta}{2}+\left|A-\frac{\Delta}{2}\right|, \tag*{(25)}
TV(Pp,Pq)=Δ2+12(∣d1−A∣+∣d2−A∣).(26)\mathrm{TV}(P_p,P_q)=\frac{\Delta}{2}+\frac{1}{2}\left(\lvert d_1-A\rvert+\lvert d_2-A\rvert\right). \tag*{(26)}

For 0<Δ<20<\Delta<2, both minima are Δ/2\Delta/2. Tail equality holds exactly when A=Δ/2A=\Delta/2. Product equality holds exactly for

p=(r+d,1−r),q=(r,1−d−r),d=Δ/2,0≤r≤1−d.(27)p=(r+d,1-r),\qquad q=(r,1-d-r),\qquad d=\Delta/2,\qquad0\le r\le1-d. \tag*{(27)}

The product-minimizing family is a proper subset of the tail-minimizing family for every 0<Δ<20<\Delta<2.

Proof. Ordering gives 0≤A=d1p2+d2q1≤Δ0\le A=d_1p_2+d_2q_1\le\Delta. The two tail differences are D1=Δ−AD_1=\Delta-A and D2=AD_2=A, proving (A.1). The signed product mass differences at 00, 10, 01, 11 are

A−Δ,d1−A,d2−A,A.A-\Delta,\qquad d_1-A,\qquad d_2-A,\qquad A.

Taking half the sum of their absolute values proves (A.2). The lower bound Δ/2\Delta/2 in both formulas is attained by the complementary homogeneous pair. The tail equality condition follows immediately. Product equality is equivalent to d1=d2=A=dd_1=d_2=A=d. Since d>0d>0 and

A=(q1+d)(q2+d)−q1q2=d(q1+q2+d),A=(q_1+d)(q_2+d)-q_1q_2=d(q_1+q_2+d),

this is equivalent to q1+q2=1−dq_1+q_2=1-d. Writing q1=rq_1=r gives (A.3), with the displayed interval exactly expressing feasibility. Conversely every member of that family attains equality; its homogeneous member is r=(1−d)/2r=(1-d)/2.

For strict containment, choose 0<ε<min⁡{d,1−d}0<\varepsilon<\min\{d,1-d\}, set d1=d+εd_1=d+\varepsilon, d2=d−εd_2=d-\varepsilon, and take pi=(1+di)/2p_i=(1+d_i)/2, qi=(1−di)/2q_i=(1-d_i)/2. Then A=dA=d, so T(p,q)=dT(p,q)=d but TV(Pp,Pq)=d+ε>d\mathrm{TV}(P_p,P_q)=d+\varepsilon>d. At Δ=0\Delta=0, ordering forces p=qp=q, and every such pair minimizes both objectives. At Δ=2\Delta=2, the only feasible pair is p=(1,1)p=(1,1), q=(0,0)q=(0,0).

:::`

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. [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. [2]A. Kontorovich, Minimizing total variation under constraint, MathOverflow, question 476847, August 13, 2024. https://mathoverflow.net/q/476847.
  3. [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. [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. [5]A. Kontorovich, TV homogenization inequalities, preprint (2026), arXiv:2601.04079v3 [math.PR].arxiv.org/abs/2601.04079
  6. [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

Paper details

vlnc:W_crph9xtu
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 11

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents