10
$\begingroup$

Do the Renyi entropies satisfy the standard subadditivity of Shannon entropy? That is,

\begin{equation} H_\alpha(A,B) \leq H_\alpha(A) + H_\alpha(B) ? \end{equation}

for $\alpha \ne 1$. If they do, for which $\alpha$?

Here $H_\alpha(X)$ is the standard Renyi $\alpha$-entropy of the random variable X, \begin{equation} H_\alpha(X)=\frac{1}{1-\alpha}\log\sum_i^n p_i^\alpha, \end{equation} and $H_\alpha(A,B)$ is the Renyi entropy of the joint probability distribuition of the random variables A and B.

$\endgroup$
1
  • 2
    $\begingroup$ Please expand the definitions that you are using, example by linking en.wikipedia.org/wiki/R%C3%A9nyi_entropy and also, by telling us what does $R_\alpha(A,B)$ mean... $\endgroup$
    – Suvrit
    Dec 20, 2012 at 13:46

3 Answers 3

8
$\begingroup$

No, the Renyi entropy is not subadditive. It also lacks several other "natural" properties of entropies.

See this paper on "Additive entropies of degree-$q$ and the Tsallis Entropy by B. H. Lavenda and J. Dunning-Davies for more details, references, and versions of entropy, which possess many desired Shannon-entropy-like properties, while generalizing it.

$\endgroup$
8
$\begingroup$

Suvrit has answered it completely, but let me suggest how you might go about finding counterexamples.

It's often useful to work with not the Rényi entropies but their exponentials, $$ D_\alpha(X) = \exp(H_\alpha(X)) = \Bigl( \sum_{i=1}^n p_i^\alpha \Bigr)^{1/(1-\alpha)} $$ (where, as in your question, $X$ is a random variable with distribution $p_1, \ldots, p_n$). One advantage of working with $D$ rather than $H$ is that there's a useful limit as $\alpha \to \infty$, namely $$ D_\infty(X) = 1/\max_i p_i. $$ Since this is such a simple formula, $\alpha = \infty$ is a good case to try when testing conjectures.

In terms of $D$, subadditivity becomes $D_\alpha(A, B) \leq D_\alpha(A) D_\alpha(B)$. It's easy to find counterexamples when $\alpha = \infty$: for instance, $$ \begin{pmatrix} 1/2 &1/4 \\\ 1/4 &0 \end{pmatrix} $$ is a counterexample since $$ \frac{1}{\max\{1/2, 1/4, 1/4, 0\}} = 2 > \frac{16}{9} = \frac{1}{\max\{3/4,1/4\}}\frac{1}{\max\{3/4,1/4\}}. $$ It follows that this is a counterexample for all sufficiently large finite $\alpha$. If you graph it, you see that it is in fact a counterexample for all $\alpha$ greater than about $1.6$. Tweaking it gives you counterexamples for all $\alpha > 1$.

$\endgroup$
2
$\begingroup$

In fact, to find a violation of any linear inequality you could form using the Renyi entropies of order $\alpha \in (0,1) \cup (1,\infty)$, please consult the following paper:

http://arxiv.org/abs/1212.0248

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