4
$\begingroup$

I am looking for a proof of the following fact

Let $X$ and$ X'$ be i.i.d on $\{0,1,2\}$ (not necessarily uniform). Prove that

$$H((X + X') \mod3) \leq H((X - X') \mod3)$$

where $H()$ is the standard Shannon entropy.

A short (or long) proof or any pointers would be very helpful.

$\endgroup$
4
  • $\begingroup$ As Tom Lin points out (+1), this is not true. What is true is that the inequality universally holds for the conditional random variables $X\pm X^\prime \mod 3 | X\pm X^\prime \ne 0$. $\endgroup$
    – whuber
    Nov 11 '14 at 15:57
  • $\begingroup$ I had actually made a mistake in writing the inequality unfortunately. Does this direction hold? $\endgroup$ Nov 11 '14 at 16:18
  • $\begingroup$ Yes, the inequality is now correct. (+1) $\endgroup$
    – whuber
    Nov 11 '14 at 17:52
  • $\begingroup$ Can you give me a proof of it? $\endgroup$ Nov 11 '14 at 17:58
3
$\begingroup$

I found this suprisingly hard to prove, because the expressions for the entropies are messy. One successful idea is to modify the distribution in a way that (a) fixes the entropy of $X-X^\prime$ while (b) increasing the entropy of $X+X^\prime$ (where the sum and difference will always be taken modulo $3$). In this fashion the distribution of $X+X^\prime$ can be made the same as that of $X-X^\prime$, implying the original entropy of $X+X^\prime$ was no greater than that of $X-X^\prime$.


Let us designate the distribution of any random variable $X$ attaining the values $0,1,2$ by the vector of its probabilities $(\Pr(X=0), \Pr(X=1), \Pr(X=2))$. Letting the common distribution of $X$ and $X^\prime$ be $(p,q,r)$, which I will write $X\sim (p,q,r)$, we may directly compute that

$$X+X^\prime \sim (p^2 + 2qr, r^2 + 2pq, q^2 + 2pr)$$

and

$$X-X^\prime \sim (p^2+q^2+r^2, pr + qp + rq, pq + qr + rp).$$

Note that the last two coefficients are equal and observe that the value of the first (different) coefficient $t = p^2 + q^2 + r^2$ must lie between $1/3$ and $1$. Thus we may alternatively parameterize the distribution of the difference in terms of $t$ as

$$X-X^\prime \sim \left(t, \frac{1-t}{2}, \frac{1-t}{2}\right)$$

for $t\in [1/3,1]$.

Now fix $t$ and adjust $(p,q,r)$ to make the entropy of $X+X^\prime$ as large as possible (so that the entropy of $X-X^\prime$ remains the same). That is, modify $p, q, r$ without changing the equalities

$$t = p^2 + q^2 + r^2;\quad p+q+r=1.$$

If we temporarily fix one of the coefficients of $X+X^\prime$ then the entropy (which is proportional to the entropy of the random variable $X+X^\prime$ conditioned on not being equal to the corresponding value) increases as the remaining two coefficients move closer together; therefore, we may as well assume this has been done as much as possible and that two of the coefficients are actually equal. This can be accomplished within the foregoing restrctictions by setting

$$p=\frac{1}{3}\left(1 \pm \sqrt{6t-2}\right);\quad q=r=\frac{1}{3}\left(1\mp \frac{1}{2}\sqrt{6t-2}\right).$$

In so doing we will have increased the entropy of $X+X^\prime$ while fixing the entropy of $X-X^\prime$. However, as a result the distributions of $X+X^\prime$ and $X-X^\prime$ have become the same (that's an easy calculation based on these formulas for $p,q,$ and $r$) and so the resulting entropy is the same as that of $X-X^\prime$, QED.

$\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.