On the entropy of a sum

Question

I am looking for a bound on the entropy $H(X+Y)$ of the sum of two independent discrete random variables $X$ and $Y$. Naturally, $$H(X+Y) \leq H(X) + H(Y) ~~~~~~(*)$$ However, applied to the sum of $n$ independent Bernoulli random variables $Z_1, \ldots, Z_n$, this gives $$ H(Z_1 + Z_2 + \cdots + Z_n) \leq n H(Z_1) $$ In other words, the bound grows linearly with $n$ when applied repeatedly. However, $Z_1 + \cdots Z_n$ is supported on a set of size $n$, so its entropy is at most $\log n$. In fact, by the central limit theorem, I'm guessing that $H(Z_1 + \cdots + Z_n) \approx (1/2) \log n$ since it is essentially supported on a set of size $\sqrt{n}$.

In short, the bound $(*)$ overshoots by quite a bit in this situation. From perusing this blog post, I gather all sorts of bounds on $H(X+Y)$ are possible; is there a bound that gives the right asymptotics (or, at least, more reasonable asymptotics) when applied repeatedly to the sum of Bernoulli random variables?

Answer 1

For such questions, you often get the right intuition by thinking of "flat" random variables. That is, think of $X$ as the uniform distribution over a set $A$ of size $2^{H(X)}$ and of $Y$ as the uniform distribution over a set $B$ of size $2^{H(Y)}$.

So, the question you're asking is (roughly speaking) what can you say about the size $|A+B|$ compared to $|A|$ and $|B|$. Generically (e.g., if they were random sets) then indeed you'll have $|A+B| \sim |A|\cdot |B|$ which corresponds to $H(X+Y) \sim H(X)+H(Y)$.

There are some special cases when $|A+B| \ll |A|\cdot |B|$, most notably when $A$ and $B$ are intervals (or more generally arithmetic progressions). There are some results that say that (at least under some conditions and if $|A+B|$ is almost as small as it can be) this is the only case. The area that studies such questions is known as "additive combinatorics", and some results have the flavor that in a group $(G,+)$ if $|A+B|=O(|A|+|B|)$ then $A,B$ are approximately subgroups of $G$ (as you mention in your question, Terence Tao's blog discusses some such results, generally speaking set size results can be transferred to the entropy setting).

The case you describe roughly corresponds to the case where $A$ is an integer interval $[a..b]$ and $B$ is an integer interval of the form $[0..c]$ (in fact, if don't try to take advantage of concentration and shoot for a $(1/2)\log n$ entropy bound, one would have $c=1$ and $a=0$ and $b=k$ for $k=1,...,n-1$ as you apply this repeatedly, however actually this will be more like $a \sim k-\sqrt{k}$ , $b \sim k+ \sqrt{k}$). Obviously in this case $|A+B| \leq |A|+c$, but I'm not sure if there is a more general bound this falls from as a special case.

Answer 2

I believe this paper by Harremoes proves that if you take a sum of $n$ Bernoulli random variables $Z_1,Z_2,...,Z_n$, each with parameter $p$ then then entropy of $Z_1+Z_2+...+Z_n$ is less that the entropy of a Poisson distribution with the mean $np$. From a quick look at Wikipedia, it seems that for large values of $np$ the entropy of a Poisson is $\frac{1}{2}\log n + O(\log n)$, which is what you expect.

Answer 3

Maybe you could use the Equation:

$$ H(Z_1+Z_2+\cdots+Z_n)=H(Z_1)+H(Z_2)+\cdots+H(Z_n)-H(Z_1|Z_1+Z_2+\cdots+Z_n)-H(Z_2|Z_2+Z_3+\cdots+Z_n)-\cdots-H(Z_{n-1}|Z_{n-1}+Z_n) $$

This would look like a term you mentioned in the comments, unfortunately i don't know of results about the cardinality of the negative terms or insightful bounds on them.