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

$$H_\alpha(A,B) \leq H_\alpha(A) + H_\alpha(B) ?$$

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, $$H_\alpha(X)=\frac{1}{1-\alpha}\log\sum_i^n p_i^\alpha,$$ and $H_\alpha(A,B)$ is the Renyi entropy of the joint probability distribuition of the random variables A and B.

-
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

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.

-

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

-

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

-