4
$\begingroup$

Shannon entropy $H(f)\triangleq \sum_x -f(x)\log f(x)$ is sub-additive. That is, if $f,g$ are pmfs:

$$H(f\star g)\leq H(f)+H(g).$$

Equality is attained when $f$ and $g$'s distributions are separated after convolution. For example if $x_0\sim\operatorname{B}(.5),\ x_1=1000x_1$ and $x_2\sim \operatorname{B}(.5)$, imagine the distribution of: $y=x_1 + x_2$ over $\{0,1,1000,1001\}$.

I cannot think of a case where this sort of preservation happens when $f=g$, which makes me suspicious there is a much better upper bound for $H(f\star f)$ than $2H(f)$.

Does anyone know of one?

$\endgroup$
1
  • $\begingroup$ equivalently, if $X,\tilde{X}$ are iid, what is a lower bound on $H(X|X+\tilde{X})$? $\endgroup$ Jul 20, 2017 at 18:26

1 Answer 1

2
$\begingroup$

The entropy of $X+Y$, or in fact any symmetric function of two variables $X$ and $Y$, is bounded by the entropy of the set-valued random variable $\{X,Y\}$. Hence

$$ \begin{align*} H(f\star f) &\leq \sum_x -f(x)^2\log(f(x)^2) + \sum_{\{x,y\}}-2f(x)f(y)\log(2f(x)f(y))\\ &=\sum_x -f(x)^2\log(f(x)^2) + \sum_{x\neq y}-f(x)f(y)\log(2f(x)f(y))\\ &=\sum_{x,y}-f(x)f(y)\log(2f(x)f(y)) - \sum_x -f(x)^2\log(2) \\ &=2H(f) - 1 + \sum_x f(x)^2. \end{align*} $$

$\sum_x f(x)^2$ has the interpretation $\mathbb P[X=Y]$ where $X,Y$ are independent variables with p.m.f $f$.

The inequality is sharp when the sum is determined by the pair, in particular when $f$ is supported on a set $R$ such that the sumset $R+R$ has cardinality $\binom{|R|}2$. For example for powers of three.

$\endgroup$
2
  • $\begingroup$ If $X$ and $Y$ are independent and identically distributed then $H( X,Y)=2H(X)$ which is the bound OP already presented above. Moreover how did $2f(x)f(y)$ come into the logarithm? Could you explain how did you write the first line? $\endgroup$
    – Arash
    Aug 27, 2017 at 20:09
  • $\begingroup$ @Arash: the probability of a particular set $\{X,Y\}=\{a,b\}$ (with $a\neq b$) is the probability of $(X,Y)=(a,b)$ plus the probability of $(X,Y)=(b,a)$. $\endgroup$
    – Dap
    Aug 28, 2017 at 1:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .