Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
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... –  Suvrit Dec 20 '12 at 13:46

3 Answers 3

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.

share|improve this answer

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.