Source-linked AI summary
Multiplicative comparisons of Rényi entropies for weighted Bernoulli sums
Jiange Li
TL;DR
The paper studies when the monotonicity of Rényi entropies can be reversed multiplicatively, focusing on weighted sums of independent Bernoulli variables and anti-concentration. It develops structural and inductive arguments yielding explicit nonzero-order comparisons and a logarithmic zeroth-to-infinity-order bound, improving a prior square-root bound.
Problem
Rényi entropy is monotone in its order, but universal multiplicative reversals fail for orders between 0 and 1, motivating sharper bounds in anti-concentrated weighted Bernoulli sums.
Method
The paper selects an independent core of weights with distinct subset sums, represents remaining weights through signed core combinations, and also uses induction on partial sums.
Results
A logarithmic bound between zeroth- and infinity-order Rényi entropies gives a polynomial improvement over the square-root bound, alongside explicit order-dependent bounds including 1−α for α ∈ (0, 1/2) and 2 for α ∈ [1/2, 1).
Takeaways & Limitations
The results improve multiplicative comparisons among Rényi entropies for weighted sums of independent Bernoulli random variables, especially between orders zero and infinity.
Takeaways & Limitations
The multiplicative factor (2n/|B|)^k in a related likelihood-ratio argument is not sharp under certain expansion properties and may be improvable to subexponential in k.
Abstract
from arXiv · showhide
We establish improved multiplicative bounds relating the Rényi entropies of different orders for weighted sums of independent Bernoulli random variables. In particular, we prove a logarithmic bound between the zeroth-order and infinity-order Rényi entropies, which yields a polynomial improvement over the square-root bound of Jain, Sah, and Sawhney. Additionally, we obtain explicit constant-factor bounds for comparisons among Rényi entropies of nonzero orders.
1. Introduction
The paper studies when multiplicative comparisons between Rényi entropies can be reversed, focusing on weighted sums of independent Bernoulli variables. It proves dimension-free nonzero-order bounds and a logarithmic zeroth-to-infinity-order bound, improving earlier estimates.
- 1.1. Background.: For 1 < α < β ≤∞, Rényi-entropy monotonicity can be reversed for any discrete random variable using a multiplicative constant depending only on α and β.No universal multiplicative constant exists for 0 ≤α < β ≤1, as geometric random variables demonstrate.
- 1.1. Background.: Weighted sums of independent Bernoulli variables provide a natural anti-concentration setting connected to the Littlewood–Offord problem.The endpoint comparison α = 0, β = ∞ concerns the relationship between support size and maximal atom size.
- 1.2. Main results.: Theorem 1.5 gives a dimension-free comparison among Rényi entropies of nonzero orders, with the factor 1−α for α ∈(0, 1/2) and 2 for α ∈[1/2, 1).The theorem is stated for weighted Bernoulli sums under the notation of Conjecture 1.1.
- 1.2. Main results.: Theorem 1.6 establishes a logarithmic bound between zeroth-order and infinity-order Rényi entropies, yielding a polynomial improvement over the earlier square-root bound.For a weight vector w, the parameter m counts its nonzero coordinates, and the displayed bound includes log2(m + 1).
- 1.3. Comparison with related work.: Theorem 1.5 couples a uniform Bernoulli vector with a largest fiber; conditioning on their XOR factors the weighted sum into independent partial sums, enabling Cauchy–Schwarz and dyadic induction.The comparison with prior work also highlights an injective map between fiber sums and combined sums, while a likelihood-ratio factor in an earlier probabilistic argument may be improvable to subexponential size.
- 1.3. Comparison with related work.: The proof strategy selects an independent core of weights, bounding the number of possible weighted sums while retaining 2^|J| distinct equally likely sums from the core.The argument also uses interpolation from the lower bound 2^-m on every nonzero probability and invokes Theorem 1.5 at a suitable order.
2. Proof of Theorem 1.5
The proof of Theorem 1.5 uses a coupling that decomposes conditional weighted sums into independent partial sums, then bootstraps bounds across Rényi orders.
- Coupling construction: The coupling lemma makes Z uniform and independent of Y, where Y is uniform on a largest level set B of the weighted sum.This coupling represents X as z ⊕ Y and preserves the relevant conditional structure.
- Coupling construction: Conditioned on Z = z, the conditional law of Sw is an injective affine image of U conditioned on U + V = τ.The partial sums U and V are independent, enabling the factorization used in the entropy argument.
- Rényi-order bootstrap: For γ = 1/2, the proof obtains the base estimate by combining the conditional moment identity with the coupling inequalities.The two relevant sums equal one at γ = 1/2, which yields the initial bound.
- Rényi-order bootstrap: For 0 < γ < 1/2, a doubling argument relates the best constant Dγ to D2γ through ˜Dγ ≤ 1 + ˜D2γ.Repeating the argument kα = ⌈log2(1/2α)⌉ times reaches an order in [1/2, 1).
- Conclusion: The proof concludes after iterating the doubling argument and applying the resulting estimate to the entropy comparison.The theorem relies crucially on the conditional factorization, which fails for non-uniform X on {0, 1}n.
3. Proof of Theorem 1.6
The proof of Theorem 1.6 combines structural bounds on weighted Bernoulli sums with entropy estimates based on the number of nonzero weights.
- Proof strategy: Theorem 1.6 combines bounds from Theorems 3.1 and 3.3.The proof explicitly derives its main inequality by combining inequality (3.2) with the preceding theorem-specific bound.
- Structural decomposition: Theorem 3.1 selects a largest subset of weights whose subset sums are distinct, then represents the remaining weights using {−1, 0, 1}-relations.Maximal independence supplies the representation used to count possible values of Sw.
- Structural decomposition: The representation bounds the support of Sw by (m + 1)^|J| possible values, where m is the number of nonzero weights.Each auxiliary integer-valued sum takes at most m + 1 distinct values.
- Entropy comparison: The independent coordinates indexed by J produce 2^|J| distinct equiprobable values, yielding an entropy contribution of |J| log 2.This supplies the complementary lower-structure estimate used in the theorem combination.
- Extension: The structural bound extends to independent non-identical Bernoulli variables when every parameter satisfies p ≤ pi ≤ 1 − p.The extension follows because inequality (3.2) does not depend on the individual probabilities.