Approximate Discrete Entropy Monotonicity for Log-Concave Sums

Abstract

It is proven that a conjecture of Tao (2010) holds true for log-concave random variables on the integers: For every $n\ge 1$, if $X_1,\dots ,X_n$ are i.i.d. integer-valued, log-concave random variables, then $$H(X_1+\cdots +X_{n+1})\ge H(X_1+\cdots +X_n)+\frac{1}{2}\log \left(\frac{n+1}{n}\right)-o(1)$$ as $H(X_1)\to \infty$, where $H$ denotes the (discrete) Shannon entropy. The problem is reduced to the continuous setting by showing that if $U_1,\dots ,U_n$ are independent continuous uniforms on $(0,1)$, then $$h(X_1+\cdots +X_n+U_1+\cdots +U_n)=H(X_1+\cdots +X_n)+o(1)$$ as $H(X_1)\to \infty$, where $h$ stands for the differential entropy. Explicit bounds for the $o(1)$-terms are provided.

arXiv comment15 pages, no figures. A number of typos have been fixed and reviewers' comments have been incorporated. More details have been added in most of the proofs. To appear in Combinatorics, Probability and Computing