Exact threshold found for entropy concavity in Bernoulli sums
The Sharp Rényi and Tsallis Threshold in the Shepp--Olkin Concavity Problem
Information Theory
Summary
This paper studies how a certain measure of randomness, called entropy, behaves when you combine many simple yes/no random events, like coin flips with different probabilities. The authors find the precise range of parameters where the measure stays nicely curved downwards, meaning it's mathematically concave, which is important for understanding and analyzing randomness. They prove that this property holds exactly when a shape-related parameter q is between zero and one, and fails for larger values. Their work settles previous guesses by giving exact answers and explains the math behind why the property holds or fails.
What this means in practice
- •For data compression engineers: Use exact entropy concavity thresholds to optimize coding schemes based on sums of independent binary sources within known parameter ranges.
- •For statistical signal processors: Design algorithms that rely on concave entropy functions for parameter estimation from binary random mixtures knowing exactly when concavity holds.
A theory result. No direct application yet.
Authors
Haoran Wang
Abstract
Let $B_1,\ldots,B_n$ be independent Bernoulli random variables with parameters $p_1,\ldots,p_n$, and let $S=\sum_i B_i$. Hillion and Johnson proved that the Shannon entropy of $S$ is jointly concave in the parameter vector and proposed corresponding critical-order conjectures for R'enyi and Tsallis entropies, with predicted thresholds $2$ and approximately $3.65986$, respectively. We determine both thresholds exactly. For every $0<q<1$, the power sum $\sum_k \mathbb P(S=k)^q$ is jointly concave in $(p_1,\ldots,p_n)$, and strictly concave on the open parameter cube. Consequently, the R'enyi and Tsallis entropies of order $q$ are jointly concave. At $q=1$ this agrees with the Shannon theorem. For every $q>1$, joint concavity fails already for the sum of two Bernoulli variables: a transverse interpolation in which the two parameters move in opposite directions gives strict local convexity for both entropies. Hence the universal joint-concavity range for both families is exactly $0<q\leq 1$. Below order one, the proof combines the Hillion--Johnson transport inequality with an explicit nonlinear telescoping correction. The corrected local curvature reduces to a two-dimensional quadratic form. An exact Riccati identity, together with a one-sided zero-crossing argument, proves positivity of its determinant throughout the full range $0<q<1$.