7
$\begingroup$

The differential Renyi entropy for a probability distribution is given by $H_q(P(X))=\frac{1}{1-q}\log\int p^q(x)dx$. In the limit of $q\to 1$, it reduces to the usual Shannon entropy. We can write down the mutual information between two variables X and Y simply by $I(X;Y)=H_q(P(X))+H_q(P(Y))-H_q(P(X,Y))$. Is this always a non-negative quantity? Again, in the case $q=1$ it is very easy to show it, but what about in general?

$\endgroup$
3
  • $\begingroup$ Hint: In the Shannon case you need to consider the Kullback Leibner divergence $D_{\pm 1}$ to prove that the mutual information is non negative. In the Renyi case you need to consider the $f$-divergence $D_f$ associated to it. Can you do it? $\endgroup$
    – Avitus
    Jun 27, 2013 at 17:25
  • $\begingroup$ Thanks, but I really don't see it :-(. In the Shannon case I can prove it with a simple application of Jensen's to xln(x), but in Renyi's case I seem to come up short... $\endgroup$
    – Ivan
    Jun 27, 2013 at 17:46
  • $\begingroup$ Ok, I wrote an answer, but I will add some more details, if you need them $\endgroup$
    – Avitus
    Jun 27, 2013 at 17:57

3 Answers 3

5
$\begingroup$

EDIT. I justify the positivity of the Renyi mutual information using its interpretation as Renyi divergence. I follow the expositions in

T. Cover, J. A. Thomas "Elements of Information Theory" (chapter 2)

and

D. Xu, D. Erdogmuns "Renyi's Entropy, Divergence and their Nonparametric Estimators"

  • Shannon entropy and mutual information

In the setting of "classical" information theory the mutual information $I(X,Y)$ of the random variables $X$ and $Y$ is defined as

$$I(X,Y):=D_{KL}(p_{XY}||p_Xq_Y),$$

where $D_{KL}(p_{XY}||p_Xq_Y),$ denotes the Kullback Leibler divergence (KL divergence) between the joint probability $p_{XY}$ and the product $p_Xq_Y$ of the prob. distribution of $X$ and $Y$.

Using the Jensen inequality on the KL divergence it follows that $I(X,Y)$ is always non negative. I refer to the first reference for the computation in the discrete case.

Introducing the Shannon entropies $H(X)$ $H(Y)$ of $X$ resp. $Y$ and the conditional entropy $H(X|Y)$ we arrive at the equivalent formulation

$$I(X,Y)=H(X)+H(Y)-H(X|Y).$$

  • Renyi Entropy and mutual information

Let us consider the Renyi $\alpha$-setting , now. With

$$H_{\alpha}(X)=\frac{1}{1-\alpha}\log\int p^{\alpha}_X(x)dx$$

we denote the Renyi entropy of the r.v. $X$. The Renyi divergence of the distribution $g(x)$ from the distribution $f(x)$ is

$$D_{\alpha}(f||g):=\frac{1}{\alpha-1}\log\int f(x)\left(\frac{f(x)}{g(x)}\right)^{\alpha-1}dx.$$

It can be proved that (please see the second reference at pag.81)

$$D_{\alpha}(f||g)\geq 0 \forall ~f, g, \text{and}~\alpha>0,~~(*)$$ $$\lim_{\alpha\rightarrow 1}D_{\alpha}(f||g)=D_{1}(f||g)=D_{KL}(f||g).~~(*)$$

The Renyi mutual information $I_{\alpha}(X,Y)$ is defined naturally as the Renyi divergence between the joint distribution $p_{XY}$ of $X$ and $Y$ and the product of the marginal distributions $p_X$, $q_Y$, i.e.

$$I_{\alpha}(X,Y):=D_{\alpha}(p_{XY}||p_Xq_Y).$$

This is a definition; you can find it, for example, at pag. 83 in the second reference. You can justify it through the overall $\alpha$-setting and the limit

$$\lim_{\alpha\rightarrow 1}I_{\alpha}(X,Y)=I(X,Y),$$

which follows from property $(**)$ of the Renyi divergence. This limit is parallel to the fundamental $\lim_{\alpha\rightarrow 1}H_{\alpha}(X)=H(X):$

From property $(*)$ one derives nonnegativity of the Renyi mutual information.

For these reasons, I would prove non negativity of the Renyi mutual information through the above definition. At the present stage I haven't been able to prove that

$$I_{\alpha}(X,Y)=H_{\alpha}(X)+H_{\alpha}(Y)-H_{\alpha}(X|Y),$$

or to find such characterization in the literature. Even in the discrete case I got blocked because of the coefficient $\frac{1}{1-\alpha}$ in front of the entropies. The cases $0<\alpha<1$ and $\alpha>1$ must be studied separately and it seems that a straightforward application of Jensen's inequality is not possible.

$\endgroup$
9
  • $\begingroup$ I don't think that the Renyi mutual information is given by the integral on the R.H.S. In Renyi's case, the logarithm is outside the integral. $\endgroup$
    – Ivan
    Jun 27, 2013 at 18:05
  • $\begingroup$ @Ivan you are right, that is a typo. To apply Jensen one starts with the $ln$ outside. I edit it now. $\endgroup$
    – Avitus
    Jun 27, 2013 at 18:10
  • $\begingroup$ Sorry, but I really don't see how you end up with a single integral and not a ratio of integrals. If I follow the definition that I have in the question, I get $I(X;Y)=1/(q-1)log(\int p^q(x,y)/(\int p^q(x) \int p^q(y))$ which cannot be reduced as far as I can see $\endgroup$
    – Ivan
    Jun 27, 2013 at 18:18
  • $\begingroup$ I seem to have found a literature reference that suggests that Renyi mutual informations don't have to be positive definite: maths.nottingham.ac.uk/personal/ga/papers/12PRL_109_190502.pdf $\endgroup$
    – Ivan
    Jun 27, 2013 at 18:24
  • 1
    $\begingroup$ That is how the Renyi entropy is defined. Without the logarithm (and with a -1), it is called the Tsallis entropy. They are generally easier to calculate than Shannon, but don't satisfy the same properties. I was wondering about Renyi in particular. $\endgroup$
    – Ivan
    Jun 27, 2013 at 18:50
3
$\begingroup$

Unfortunately the quantity $I_q(X,Y) = H_q(X) + H_q(Y) - H_q(X,Y)$ is not always positive. This is particularly annoying given that this quantity has the useful property of being $0$ when $X$ and $Y$ are independent.

This is due to the fact that this definition implicitly states that the conditional Renyi entropy is: $$H_q(X|Y) = H_q(X,Y) - H_q(Y),$$ and with this definition it is not always true that conditioning a random variable decreases its Renyi entropy. That is: $$ H_q(X|Y) \leq H_q(X) \text{ is false}$$

From Conditional Renyi Entropies [Teixeira2012], we can find a joint probability distribution $(X,Y)$ for which the inequality above does not hold: $$P(X = x_1, Y = y_1) = 0.2, P(X = x_2, Y = y_1) = 0.4$$ $$P(X = x_1, Y = y_2) = 0, P(X = x_2, Y = y_2) = 0.4$$ In this case, $$I_q(X,Y) = \frac{1}{1-q} \log{\Big(\frac{\int \int p(x)^q p(y)^q}{\int \int p(x,y)^q}\Big)}$$ for $q = 3$ is equal to: $$ \frac{1}{1-3}\log(\frac{(0.2 \cdot 0.4)^3 + (0.2 \cdot 0.6)^3 + (0.6\ \cdot 0.8)^3 + (0.4 \cdot 0.8)^3}{0.2^3 + 0.4^3 + 0.4^3}) = -\frac{1}{2} \log(\frac{0.1456}{0.136}) = - 0.015 $$ which is negative.

$\endgroup$
2
  • $\begingroup$ so this is an argument to just use classical mutual information, as opposed to Renyi mutual information, because the first is always positive? $\endgroup$
    – develarist
    Aug 14, 2020 at 17:46
  • 1
    $\begingroup$ I guess it is if you always want positive values. There might be cases where you do not need this though. $\endgroup$
    – Simone
    Aug 14, 2020 at 17:53
2
$\begingroup$

The following paper elaborates on a few different possible definitions of "Rényi mutual information". It points out the negativity issue raised on Simone's answer and observes the nonnegativity of the proposal in Avitus' answer.

α-Mutual Information

Sergio Verdú

http://www.ita.ucsd.edu/workshop/15/files/paper/paper_374.pdf

Verdú comes down in favor of a slight variant of Avitus' definition (attributed to Sibson): $$I_\alpha(X;Y) = \min_{q_Y} D_\alpha(p_{XY} \| p_X q_Y)$$ where $p_X$ is the marginal of $X$ under $p_XY$ and $q_Y$ ranges over all possible distributions for $Y$ (not necessarily the marginal corresponding to $p_{XY}$).

Perhaps the simplest takeaway here is that there is no single clear "Rényi mutual information". Which version you need will vary based on context.

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