12
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Sep 1 '12 at 20:26
  • 1
    $\begingroup$ @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... $\endgroup$ – robinson Sep 1 '12 at 22:03
  • 1
    $\begingroup$ ...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. $\endgroup$ – robinson Sep 1 '12 at 22:06
  • 2
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Sep 1 '12 at 22:17
  • 1
    $\begingroup$ 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 $\endgroup$ – Sasho Nikolov Sep 2 '12 at 2:06
19
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.