Shannon's problem on the monotonicity of entropy and a Conjecture of Tao

Abstract

Let $X_1,X_2,\dots$ be i.i.d. finitely supported random variables in a torsion-free abelian group, and write $S_k=X_1+\cdots +X_k$, and $H(S_k)$ is the Shannon entropy $S_k$, for all $k\ge 1$. We prove that, for every fixed $n\ge 1$, \[ H(S_{n+1})-H(S_n) \geq \frac12\log\frac{n+1}{n} -o_{H(X_1)\to\infty}(1), \] uniformly over the ambient group and the input law. This proves a conjecture of Tao [29] in 2010.

62 pages