We know $H(f\star g)\leq H(f)+H(g)$. Is there a better bound for $H(f\star f)$?

103 Views Asked by At

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?

1

There are 1 best solutions below

2
On BEST ANSWER

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.