Rényi Divergence and Majorization

I Introduction

Since Shannon’s introduction of his entropy function various other similar measures of uncertainty or information have been introduced. Most of these have found no applications and some have found applications only in quite special cases. An exception is formed by Rényi entropy and Rényi divergence, which pop up again and again. They are far from being as well understood as Shannon entropy and Shannon divergence, and do not have as simple an interpretation. Erdal Arikan observed that the discrete version of Rényi entropy is related to so-called guessing moments .

In this short note we shall first review the most important properties of Rényi divergence in Section II. In Section III we give a very brief introduction to Markov ordering and its relation to majorization. Then in Sections IV, and V we relate Rényi divergence to the theory of majorization. And finally, in Section VI we will show that, like its entropy counterpart, Rényi divergence is related to guessing moments.

II Rényi Divergence

Let $P$ and $Q$ be probability measures on a measurable space $(\mathcal{X},\mathcal{F})$, and let $p$ and $q$ be their densities with respect to a common $\sigma$-finite dominating measure $\mu$. Then for any $0<\alpha<\infty$ except $\alpha=1$, the Rényi divergence $D_{\alpha}$ of order $\alpha$ of $P$ from $Q$ is defined as

with the conventions that $p^{\alpha}q^{1-\alpha}=0$ if $p=q=0$, even for $\alpha<0$ and $\alpha>1$, and that $x/0=\infty$ for $x>0$. Continuity considerations lead to the following extensions for $\alpha\in\{0,1\}$:

We will first review some of the basic properties of $D_{\alpha}$. Whenever these properties can easily be derived from known results, we will point to the relevant literature. For other properties, space requirements limit us to only hint at their proofs. A longer version of this paper with full proofs will be published elsewhere, and will include results for negative values of the order $\alpha$.

Let us start by noting that, for finite orders $0<\alpha\neq 1$, $D_{\alpha}$ is a continuous, strictly increasing function of the power divergence

As $d_{\alpha}$ are $f$-divergences, we may derive properties for $D_{\alpha}$ from general properties of $f$-divergences .

In particular, Rényi divergence satisfies the data processing inequality

for any $\sigma$-subalgebra $\mathcal{G}\subseteq\mathcal{F}$, where $P_{\lvert\mathcal{G}}$ and $Q_{\lvert\mathcal{G}}$ denote the restrictions of $P$ and $Q$ to $\mathcal{G}$. As a special case, taking $\mathcal{G}=\{0,\mathcal{X}\}$ to be the trivial algebra, we find that

$D_{\alpha}(P\|Q)=0$ if and only if $P=Q.$ Taking $\mathcal{G}=\sigma(\mathcal{P})$ to be the $\sigma$-algebra generated by a finite partition $\mathcal{P}$ of $\mathcal{X}$, the data processing inequality implies that discretizing $\mathcal{X}$ can only decrease $D_{\alpha}$. However, because of the following property, which carries over from $f$-divergences, $D_{\alpha}$ may be approximated arbitrarily well by such finite partitions:

where the supremum is over all finite partitions $\mathcal{P}$ of $\mathcal{X}$. This characterization also shows that we have found the right generalization of Rényi’s definition for finite $\mathcal{X}$.

Using the dominated convergence theorem it can be shown that:

$D_{\alpha}$ is continuous in $\alpha$ on

$D_{\alpha}$ is also nondecreasing in $\alpha$, and on $A$ it is constant if and only if $q/p$ is constant $P$-a.s.

The fact that $D_{\alpha}$ is nondecreasing, together with Equation (2), implies that $\lim_{\alpha\uparrow 1}D_{\alpha}=D$, as asserted in our definition of $D_{1}$: for finite $\mathcal{X}$, this can be verified directly using l’Hôpital’s rule. Therefore

The assertion that $\lim_{\alpha\downarrow 0}D_{\alpha}=-\log Q(p>0)$ is verified differently, using the dominated convergence theorem and the observation that $\lim_{\alpha\downarrow 0}p^{\alpha}q^{1-\alpha}$ equals $q$ if $p>0$ and otherwise. Rényi divergence may be extended to $\alpha=\infty$ by letting $\alpha$ tend to $\infty$. Then, for finite $\mathcal{X}$,

and by an interchanging of suprema similar to (3) we find that

in general. Consequently, $D_{\infty}(Q\|P)$ (note the reversal of $P$ and $Q$) is a one-to-one function of the separation distance $s(P,Q)=\max_{x}(1-P(x)/Q(x))$, defined only for countable $\mathcal{X}$, which has been used to obtain bounds on the rate of convergence to the stationary distribution for certain Markov chains .

Equation 2 implies that there exists a sequence $\mathcal{F}_{1},\mathcal{F}_{2},\ldots$ of $\sigma$-algebras generated by finite partitions such that

By the connection to $f$-divergences, such a convergence result holds for any increasing sequence of $\sigma$-algebras $\mathcal{F}_{1}\subseteq\mathcal{F}_{2}\subseteq\cdots\subseteq\mathcal{F}_{\infty}=\sigma\left(\bigcup_{n=1}^{\infty}\mathcal{F}_{n}\right)\subseteq\mathcal{F}$:

[4, Theorem 15]. By a suitable choice of $\mathcal{F}_{n}$ this result extends additivity for any distributions $P_{1},P_{2},\ldots$ and $Q_{1},Q_{2},\ldots$,

from any finite $N$ (for which it is easy to prove) to $N=\infty$ (if $\alpha>0$). For $\alpha=0$ additivity only holds for finite $N$. By a direct proof we can also prove the counterpart to (4) for decreasing sequences of $\sigma$-algebras $\mathcal{F}\supseteq\mathcal{F}_{1}\supseteq\mathcal{F}_{2}\supseteq\cdots\supseteq\mathcal{F}_{\infty}=\bigcap_{n=1}^{\infty}\mathcal{F}_{n}$ (for finite $\alpha$) under the condition that the divergence is finite.

denote the squared Hellinger distance, and let

denote the $\chi^{2}$-distance . We see that

and $D_{2}(P\|Q)=\log(1+\chi^{2}(P,Q))$. Hence by $\log x\leq x-1$

III Majorization, Markov ordering and Lorenz diagrams

The general theory of majorization is now a well established mathematical discipline . The majorization lattice and its relation to discrete entropy was studied in and later generalized in . Recently a long article on this subject by Gorban, Gorban, and Judge has been accepted for publication . We refer to these papers for a more complete discussion and further references. Here we shall relate the relative majorization lattice to Rényi divergence.

Let $P$ and $Q$ be measures on the same measurable set. The Lorenz diagram of $\left(P,Q\right)$ is the range of

where $f$ is any measurable function with values in $\left[0,1\right].$

If $Q$ is the uniform distribution then the Lorenz diagram of $\left(P_{1},Q\right)$ is a subset of the Lorenz diagram of $\left(P_{2},Q\right)$ if and only if $P_{2}$ majorizes $P_{1}.$

The Lorenz diagram of $\left(P_{1},Q\right)$ is a subset of the Lorenz diagram of $\left(P_{2},Q\right)$ if and only if there exists a Markov operator that transforms $P_{2}$ into $P_{1}$ and leaves $Q$ invariant.

Let $P_{1},P_{2}$ and $Q$ be measures on the same measurable set $\mathcal{X}$. We write $P_{2}\succeq_{Q}P_{1}$ if the Lorenz diagram of $\left(P_{1},Q\right)$ is a subset of the Lorenz diagram of $\left(P_{2},Q\right).$ If the Lorenz diagrams of $(P_{1},Q)$ and $(P_{2},Q)$ are equal, then we write $P_{1}\simeq_{Q}P_{2}$.

This ordering that generalizes majorization will be celled the Markov ordering In this ordering was called relative majorization..

Let $Q$ be a measure on a measurable set $\mathcal{X}.$ If $Q$ is a uniform distribution on a finite set or if $Q$ has no atoms, then $M_{+}^{1}\left(\mathcal{X}\right)/\simeq_{Q}$ is a lattice, where $M_{+}^{1}\left(\mathcal{X}\right)$ denotes the set of probability measures on $\mathcal{X}.$

The Lorenz diagram is characterized by a lower bound curve that is convex and an upper bounding curve that is concave. Because of the symmetry around $\left(1/2,1/2\right)$ the Lorenz diagram is completely determined by the lower bounding curve.

The Lorenz curve of $\left(P,Q\right)$ is the convex envelope of the Lorenz diagram, i.e. the largest convex function such that all the points in the Lorenz diagram are at or above the curve.

so $\left(P\left(A_{t}\right),Q\left(A_{t}\right)\right)$ gives a parametrization of the Lorenz curve in terms of its slope if it is differentiable.

Suppose $Q$ is the counting measure on a finite set $\mathcal{X}$ of size $n$, and let $P_{1}=(v_{1},\ldots,v_{n})$ be a discrete measure on $\mathcal{X}$. Then $A_{t}$ is simply $\left\{i\mid v_{i}\leq t\right\}.$ Let $P_{2}=(w_{1},\ldots,w_{n})$ be another measure and let $B_{t}=\left\{i\mid w_{i}\leq t\right\}$. Then $P_{1}\preceq P_{2}$ if and only if $P_{1}\left(A_{t_{1}}\right)\geq P_{2}\left(B_{t_{2}}\right)$ whenever $Q\left(A_{t_{1}}\right)=Q\left(B_{t_{2}}\right)$. Thus $P_{1}\preceq P_{2}$ if and only if the Lorenz curve of $\left(P_{1},Q\right)$ is above the Lorenz curve of $\left(P_{2},Q\right)$.

If one of the conditions of Theorem 5 is fulfilled, then for each convex function $f$ there exists a measure $P$ such that $f$ is the Lorenz curve of $P$. Thus $M_{+}^{1}\left(\mathcal{X}\right)/\simeq_{Q}$ can be identified with the set of Lorenz curves. Let $P_{1}$ and $P_{2}$ be measures and let $L_{1}$ and $L_{2}$ be their Lorenz curves. Then $P_{1}\wedge P_{2}$ can be identified with the Lorenz curve $\max\left\{L_{1},L_{2}\right\}$ and $P_{1}\vee P_{2}$ can be identified with the Lorenz curve that is the convex envelop of $\min\left\{L_{1},L_{2}\right\}$. In general this lattice is neither modular nor distributive .

IV Divergence, Convexity and Ordering

We will now consider properties of $D_{\alpha}(P\|Q)$ as we vary $P$ and $Q$ while keeping $\alpha$ fixed. Information divergence $D(P\|Q)$ is known to be jointly convex in the pair $(P,Q)$ . By an argument similar to the proof for $D_{1}$ in , this property generalizes to $D_{\alpha}$ for arbitrary order $0\leq\alpha\leq 1$:

For $0\leq\alpha\leq 1$, $D_{\alpha}(P,Q)$ is jointly convex in the pair $(P,Q)$.

Even though joint convexity does not generalize to $\alpha>1$, we still have:

For all $\alpha$, $D_{\alpha}(P\|Q)$ is convex in $Q.$

The key step in proving the latter result for $\alpha>1$ relies on Hölder’s inequality.

Let $P$ be absolutely continuous with respect to $Q$. If $F$ denotes the curve that upper bounds the Lorenz diagram, then the Rényi divergence is given by

Note that we can replace the upper bounding function by the lower bounding function (the Lorenz curve) without changing the integral.

For $\alpha>0$ the Rényi divergence $D_{\alpha}\left(P\|Q\right)$ is a increasing function of $P$ on the lattice corresponding to $Q$.

Theorem 10 is essentially a noisy data processing inequality because the Markov kernel $\Phi_{x}$ in the proof essentially maps the measure corresponding to $G$ into the measure corresponding to $P.$ By adapting a proof from is possible to prove the following theorem:

Let $P_{1}$ and $P_{2}$ denote distributions that are absolutely continuous with respect to $Q$. If Markov ordering is taken with respect to $Q$ then power divergence is sub-modular and super-additive, i.e.

Since power divergence is a function of Rényi divergence one can reformulate Theorem 11 in terms of Rényi divergence. Like Rényi divergence, the power divergence $d_{\alpha}(P,Q)$ tends to the information divergence $D(P\|Q)$ as $\alpha\uparrow 1$. This implies:

Let $P_{1}$ and $P_{2}$ be distributions that are absolutely continuous with respect to $Q$. If the Markov ordering is taken with respect to $Q$ then information divergence is sub-modular and super-additive, i.e.

V Continuity of Rényi divergence

The type of continuity of $D_{\alpha}$ in the pair $(P,Q)$ turns out to depend on the topology and on $\alpha$. We consider the $\tau$-topology, in which convergence of $P_{n}$ to $P$ means that $P_{n}(A)\rightarrow P(A)$ for all $A\in\mathcal{F}$, and the total variation topology in which $P_{n}\rightarrow P$ if the variation distance between $P_{n}$ and $P$ goes to zero. In general the total variation topology is stronger than the $\tau$-topology, but if $\mathcal{X}$ is countable, then the two topologies coincide.

For any $\alpha>0$, $D_{\alpha}(P\|Q)$ is a lower semi-continuous function of $(P,Q)$ in the $\tau$-topology.

For $0<\alpha<1$, $D_{\alpha}(P\|Q)$ is a (uniformly) continuous function of $(P,Q)$ in the total variation topology.

It remains to consider $\alpha=0$. In this case:

$D_{0}(P\|Q)$ is an upper semi-continuous function of $(P,Q)$ in the total variation topology.

Using the Markov ordering we get more insight.

This holds for all $\varepsilon>0$ and, since the right-hand side tends to $\frac{1}{\alpha-1}\log\int_{0}^{1}\left(\frac{d}{dt}F\left(t\right)\right)^{\alpha}~{}dt=D_{\alpha}\left(P\|Q\right)$ for $\varepsilon\rightarrow 0$, the result follows. ∎

VI Guessing moments

Erdal Arikan observed that the discrete version of Rényi entropy is related to so-called guessing moments . In this short note we shall see that Rényi divergences are also related to guessing moments.

Let $P_{1}$ and $P_{2}$ denote probability measures on $\mathcal{X}.$ We say that $P_{1}$ is a rearrangement of $P_{2}$ if

The ranking function is the guessing function that minimizes the $\rho$-th moment if $\rho>0$ and maximizes the $\rho$-th moment if $\rho<0$.

Guessing and ranking are closely related to majorization and the Markov ordering via the following proposition.

Assume that $P_{1},P_{2}$ and $Q$ are probability measures on $\mathcal{X}$ and $P_{1}\preceq_{Q}P_{2}.$ Let $r_{1}$ and $r_{2}$ denote the ranking functions of $P_{1}$ and $P_{2}.$ Then

If $\alpha=\frac{1}{1+\rho}>0$ then, for any probability measures $P$ and $Q$,

We raise to the power $1/\rho$ and take minus the logarithm and get

Using additivity of Rényi divergence and Lemma 22 we get the following theorem.

If $\alpha=\frac{1}{1+\rho}>0$ then for any i.i.d. sequence $X_{1}^{n}=\left(X_{1},X_{2},\ldots,X_{n}\right)\in\mathcal{X}^{n}$ we have

This bound is asymptotically tight as stated in the following theorem.

If $\alpha=\frac{1}{1+\rho}>0$ then for any i.i.d. sequence $X_{1}^{n}=\left(X_{1},X_{2},\ldots,X_{n}\right)\in\mathcal{X}^{n}$ we have

The result gives a new interpretation of Rényi divergence.

VII Discussion

The results in this short paper are formulated under the assumption that the second argument $Q$ in $D_{\alpha}\left(P\|Q\right)$ is a probability measure. Nevertheless many of the results still hold if $Q$ is a more general positive measure. For instance many results on Rényi entropy are obtained when $Q$ denotes the counting measure. Most of these results for Rényi entropy are well-known. Results for differential Rényi entropy are obtained when $Q$ is the Lebesgue measure. For both Rényi entropy and differential Rényi entropy many results should first be formulated and proved for subsets of finite measure and then one should take a limit for an increasing sequence of subsets. In this sense our results on Rényi divergence are often more general than the results one will find in the literature.

We have related Rényi divergence to majorization and Markov ordering. An interesting related concept is catalytic majorization. It has been proved by M. Klimesh that one discrete distribution majorizes another distribution if and only if certain inequalities hold between their Rényi entropies . A similar result is still to be proved for Rényi divergence.

VIII Acknowledgments

We thank Christophe Vignat, Matthew Klimesh, and Erdal Arikan for useful discussions.

This work was supported in part by the IST Programme of the European Community, under the PASCAL Network of Excellence, IST-2002-506778.

References