<p>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)}$.</p>

<p>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)$.</p>

<p>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).</p>

<p>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. </p>

CC BY-SA 3.0
2012-09-08T04:15:14.847Z
2012-09-08T04:38:38.050Z
2012-09-08T04:38:38.050Z
Boaz Barak
<p>I believe <a href="http://www.harremoes.dk/Peter/poisson.pdf">this paper</a> 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.</p>

CC BY-SA 3.0
2012-09-13T19:13:06.317Z
2012-09-13T19:18:46.920Z
2012-09-13T19:18:46.920Z
VSJ
<p>Maybe you could use the Equation:</p>

<p>$$
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)
$$</p>

<p>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.</p>

CC BY-SA 3.0
2013-05-16T10:15:59.747Z
2013-05-16T10:15:59.747Z
Rick
<p>I am looking for a bound on the entropy <span class="math-container">$H(X+Y)$</span> of the sum of two independent discrete random variables <span class="math-container">$X$</span> and <span class="math-container">$Y$</span>. Naturally, <span class="math-container">$$H(X+Y) \leq H(X) + H(Y) ~~~~~~(*)$$</span> However, applied to the sum of <span class="math-container">$n$</span> independent Bernoulli random variables <span class="math-container">$Z_1, \ldots, Z_n$</span>, this gives
<span class="math-container">$$ H(Z_1 + Z_2 + \cdots + Z_n) \leq n H(Z_1)  $$</span> In other words, the bound grows linearly with <span class="math-container">$n$</span> when applied repeatedly. However, <span class="math-container">$Z_1 + \cdots Z_n$</span> is supported on a set of size <span class="math-container">$n$</span>, so its entropy is at most <span class="math-container">$\log n$</span>. In fact, by the central limit theorem, I'm guessing that <span class="math-container">$H(Z_1 + \cdots + Z_n) \approx (1/2) \log n$</span> since it is essentially supported on a set of size <span class="math-container">$\sqrt{n}$</span>.</p>
<p>In short, the bound <span class="math-container">$(*)$</span> overshoots by quite a bit in this situation. From perusing <a href="http://terrytao.wordpress.com/2009/06/25/sumset-and-inverse-sumset-theorems-for-shannon-entropy/" rel="noreferrer">this blog post</a>, I gather all sorts of bounds on <span class="math-container">$H(X+Y)$</span> 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?</p>

CC BY-SA 3.0
2012-09-01T20:26:33.647Z
I am not sure what you are really asking.  If you want an upper bound on H(X+Y) in terms of H(X) and H(Y) which is applicable to any two independent discrete random variables X and Y, then H(X+Y)≤H(X)+H(Y) is clearly the best you can get; consider the case where the sums x+y are all distinct when x ranges over the support of X and y ranges over the support of Y.  If you apply this general bound to a very special case, then it is natural that you get a very loose bound.
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-01T22:03:31.977Z
@TsuyoshiIto - well, one possibility for an answer that would be great is an inequality like $H(X+Y) \leq H(X) + H(Y) - \ldots$ where the terms after the minus are zero in the case you describe and add up to give a better scaling with $n$ in the case of a sum of Bernoulli random variables...
robinson
CC BY-SA 3.0
2012-09-01T22:06:07.727Z
...it seems to me that the existence of inequalities like $H(X+Y) \leq 3 H(X-Y) - H(X) - H(Y)$ makes it at least plausible that the answer I am looking for exists.
robinson
CC BY-SA 3.0
2012-09-01T22:17:13.497Z
That means that what you are looking for is not an upper bound on H(X+Y) _in terms of H(X) and H(Y)_.  Please edit the question.
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-01T22:26:36.430Z
@TsuyoshiIto - Done.
robinson
CC BY-SA 3.0
2012-09-02T02:06:32.267Z
i think in the case where the variance of each $Z_i$ is small compared to $n$ your guess is the right answer, and is not hard to make precise using the Berry-Esseen theorem
Sasho Nikolov
CC BY-SA 3.0
2013-05-17T03:39:08.557Z
Not a general formula, but a general approach could be to use a Chernoff bound first. For the Bernoulli case, you could split the range of the sum into a set of size $O(\sqrt{n})$ and into the remainder; then you can suppose as a worst case that is is piecewise uniform, uniform on the $O(\sqrt{n})$ set with relatively high probability and on the remainder with low probability. For Bernoullis, this gives me a bound of $\left(\frac{1}{2} + \frac{1}{e^{k}}\right) \log n + \log(k)$ for any constant $k$ bigger than $4$ or so. Anyway, I wonder if this approach gives a more general bound.
usul
<it.information-theory><shannon-entropy>
On the entropy of a sum
robinson
# On the entropy of a sum

(Asked by: username_0 on 2012-09-01)

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](http://terrytao.wordpress.com/2009/06/25/sumset-and-inverse-sumset-theorems-for-shannon-entropy/), 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?

**Tags:** it.information-theory, shannon-entropy

> **Comments:**
> **username_1**: I am not sure what you are really asking.  If you want an upper bound on H(X+Y) in terms of H(X) and H(Y) which is applicable to any two independent discrete random variables X and Y, then H(X+Y)≤H(X)+H(Y) is clearly the best you can get; consider the case where the sums x+y are all distinct when x ranges over the support of X and y ranges over the support of Y.  If you apply this general bound to a very special case, then it is natural that you get a very loose bound.  
> **username_0**: @TsuyoshiIto - well, one possibility for an answer that would be great is an inequality like $H(X+Y) \leq H(X) + H(Y) - \ldots$ where the terms after the minus are zero in the case you describe and add up to give a better scaling with $n$ in the case of a sum of Bernoulli random variables...  
> **username_0**: ...it seems to me that the existence of inequalities like $H(X+Y) \leq 3 H(X-Y) - H(X) - H(Y)$ makes it at least plausible that the answer I am looking for exists.  
> **username_1**: That means that what you are looking for is not an upper bound on H(X+Y) _in terms of H(X) and H(Y)_.  Please edit the question.  
> **username_0**: @TsuyoshiIto - Done.  
> **username_2**: i think in the case where the variance of each $Z_i$ is small compared to $n$ your guess is the right answer, and is not hard to make precise using the Berry-Esseen theorem  
> **username_3**: Not a general formula, but a general approach could be to use a Chernoff bound first. For the Bernoulli case, you could split the range of the sum into a set of size $O(\sqrt{n})$ and into the remainder; then you can suppose as a worst case that is is piecewise uniform, uniform on the $O(\sqrt{n})$ set with relatively high probability and on the remainder with low probability. For Bernoullis, this gives me a bound of $\left(\frac{1}{2} + \frac{1}{e^{k}}\right) \log n + \log(k)$ for any constant $k$ bigger than $4$ or so. Anyway, I wonder if this approach gives a more general bound.  

---

## 3 answers

### Answer by username_4 on 2012-09-08. Score: 19

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 by username_5 on 2012-09-13. Score: 5

I believe [this paper](http://www.harremoes.dk/Peter/poisson.pdf) 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 by username_6 on 2013-05-16. Score: 0

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.


---

