Inequality of entropies under convolution on groups

74 Views Asked by At

Let $P_1$, $P_2$, $P_3$ be probability distributions on a finite group $G$, and let $H(P_i)$ be their respective entropy functions $H(P_i) = -\sum_{g\in G}P_i(g)\log(P_i(g))$, where we set $0\cdot \log(0) = 0$. Let $P_i \ast P_j$ be the convolution between $P_i$ and $P_j$ with respect to $G$.

Assume that $H(P_2)\leq H(P_3)$. Is it then in general true that $H(P_1 \ast P_2)\leq H(P_1 \ast P_3)$? If not, are there are any mild conditions for when this holds? In my particular case I have that $G$ is abelian, and that all the probability distributions have full support on $G$.

1

There are 1 best solutions below

0
On BEST ANSWER

In general, it is possible that

$$ H(P_2)<H(P_3) \qquad\text{but}\qquad H(P_1\star P_2)>H(P_1\star P_3).$$

This is because entropy function is invariant under permuting variable values but the convolution is not. So, there is some room to play with. (A more structured distribution can sometimes mix things faster than a less structured one does.)

For example, let $G=\mathbb{Z}/6\mathbb{Z}$ and consider the distributions

\begin{align*} P_1 &= \frac{1}{9}(\delta_0 + \delta_2 + \delta_4) + \frac{2}{9}(\delta_1 + \delta_3 + \delta_5), \\ P_2 &= \frac{1}{3}(\delta_0 + \delta_1) + \frac{1}{12}(\delta_2 + \delta_3 + \delta_4 + \delta_5), \\ P_3 &= \frac{1}{4}(\delta_0 + \delta_1 + \delta_2) + \frac{1}{12}(\delta_3 + \delta_4 + \delta_5). \end{align*}

Then a direct computation confirms that $H(P_2) < H(P_3)$ holds. However, $P_1 \star P_2$ is uniform over $G$ whereas $P_1 \star P_3$ is not, hence $H(P_1 \star P_2) > H(P_1 \star P_3)$.