Rényi Divergence and Kullback-Leibler Divergence

I Introduction

Shannon entropy and Kullback-Leibler divergence (also known as information divergence or relative entropy) are perhaps the two most fundamental quantities in information theory and its applications. Because of their success, there have been many attempts to generalize these concepts, and in the literature one will find numerous entropy and divergence measures. Most of these quantities have never found any applications, and almost none of them have found an interpretation in terms of coding. The most important exceptions are the Rényi entropy and Rényi divergence . Harremoës and Grünwald [3, p. 649] provide an operational characterization of Rényi divergence as the number of bits by which a mixture of two codes can be compressed; and Csiszár gives an operational characterization of Rényi divergence as the cut-off rate in block coding and hypothesis testing.

Rényi divergence appears as a crucial tool in proofs of convergence of minimum description length and Bayesian estimators, both in parametric and nonparametric models , [7, Chapter 5], and one may recognize it implicitly in many computations throughout information theory. It is also closely related to Hellinger distance, which is commonly used in the analysis of nonparametric density estimation . Rényi himself used his divergence to prove the convergence of state probabilities in a stationary Markov chain to the stationary distribution , and still other applications of Rényi divergence can be found, for instance, in hypothesis testing , in multiple source adaptation and in ranking of images .

Although the closely related Rényi entropy is well studied , the properties of Rényi divergence are scattered throughout the literature and have often only been established for finite alphabets. This paper is intended as a reference document, which treats the most important properties of Rényi divergence in detail, including Kullback-Leibler divergence as a special case. Preliminary versions of the results presented here can be found in and . During the preparation of this paper, Shayevitz has independently published closely related work .

For finite alphabets, the Rényi divergence of positive order $\alpha\neq 1$ of a probability distribution $P=(p_{1},\ldots,p_{n})$ from another distribution $Q=(q_{1},\ldots,q_{n})$ is

where, for $\alpha>1$, we read $p_{i}^{\alpha}q_{i}^{1-\alpha}$ as $p_{i}^{\alpha}/q_{i}^{(\alpha-1)}$ and adopt the conventions that $\nicefrac{{0}}{{0}}=0$ and $\nicefrac{{x}}{{0}}=\infty$ for $x>0$. As described in Section II, this definition generalizes to continuous spaces by replacing the probabilities by densities and the sum by an integral. If $P$ and $Q$ are members of the same exponential family, then their Rényi divergence can be computed using a formula by Huzurbazar and Liese and Vajda [20, p. 43], . Gil provides a long list of examples .

Let $Q$ be a probability distribution and $A$ a set with positive probability. Let $P$ be the conditional distribution of $Q$ given $A$. Then

We observe that in this important special case the factor $\frac{1}{\alpha-1}$ in the definition of Rényi divergence has the effect that the value of $D_{\alpha}(P\|Q)$ does not depend on $\alpha$.

can be expressed in terms of the Rényi divergence of $P$ from the uniform distribution $U=(\nicefrac{{1}}{{n}},\ldots,\nicefrac{{1}}{{n}})$:

As $\alpha$ tends to $1$, the Rényi entropy tends to the Shannon entropy and the Rényi divergence tends to the Kullback-Leibler divergence, so we recover a well-known relation. The differential Rényi entropy of a distribution $P$ with density $p$ is given by

whenever this integral is defined. If $P$ has support in an interval $I$ of length $n$ then

where $U_{I}$ denotes the uniform distribution on $I$, and $D_{\alpha}$ is the generalization of Rényi divergence to densities, which will be defined formally in Section II. Thus the properties of both the Rényi entropy and the differential Rényi entropy can be deduced from the properties of Rényi divergence as long as $P$ has compact support.

There is another way of relating Rényi entropy and Rényi divergence, in which entropy is considered as self-information. Let $X$ denote a discrete random variable with distribution $P$, and let $P_{\text{diag}}$ be the distribution of $(X,X)$. Then

For $\alpha$ tending to $1$, the right-hand side tends to the mutual information between $X$ and itself, and again a well-known formula is recovered.

I-B Special Orders

Although one can define the Rényi divergence of any order, certain values have wider application than others. Of particular interest are the values , $\nicefrac{{1}}{{2}}$, $1$, $2$, and $\infty$.

The values $0,$ $1,$ and $\infty$ are extended orders in the sense that Rényi divergence of these orders cannot be calculated by plugging into (1). Instead, their definitions are determined by continuity in $\alpha$ (see Figure 1). This leads to defining Rényi divergence of order $1$ as the Kullback-Leibler divergence. For order it becomes $-\ln Q(\{i\mid p_{i}>0\}),$ which is closely related to absolute continuity and contiguity of the distributions $P$ and $Q$ (see Section III-F). For order $\infty$, Rényi divergence is defined as $\ln\max_{i}\frac{p_{i}}{q_{i}}$. In the literature on the minimum description length principle in statistics, this is called the worst-case regret of coding with $Q$ rather than with $P$ . The Rényi divergence of order $\infty$ is also related to the separation distance, used by Aldous and Diaconis to bound the rate of convergence to the stationary distribution for certain Markov chains.

Only for $\alpha=\nicefrac{{1}}{{2}}$ is Rényi divergence symmetric in its arguments. Although not itself a metric, it is a function of the squared Hellinger distance \operatorname{Hel}^{2}(P,Q)=\sum_{i=1}^{n}\big{(}p_{i}^{\nicefrac{{1}}{{2}}}-q_{i}^{\nicefrac{{1}}{{2}}}\big{)}^{2} :

where $\chi^{2}(P,Q)=\sum_{i=1}^{n}\frac{(p_{i}-q_{i})^{2}}{q_{i}}$ denotes the $\chi^{2}$-divergence . It will be shown that Rényi divergence is nondecreasing in its order. Therefore, by $\ln t\leq t-1,$ (5) and (6) imply that

Finally, Gilardoni shows that Rényi divergence is related to the total variation distanceN.B. It is also common to define the total variation distance as $\frac{1}{2}V(P,Q)$. See the discussion by Pollard [26, p. 60]. Our definition is consistent with the literature on Pinsker’s inequality. $V(P,Q)=\sum_{i=1}^{n}\lvert p_{i}-q_{i}\rvert$ by a generalization of Pinsker’s inequality:

(See Theorem 31 below.) For $\alpha=1$ this is the normal version of Pinsker’s inequality, which bounds total variation distance in terms of the square root of the Kullback-Leibler divergence.

I-C Outline

The rest of the paper is organized as follows. First, in Section II, we extend the definition of Rényi divergence from formula (1) to continuous spaces. One can either define Rényi divergence via an integral or via discretizations. We demonstrate that these definitions are equivalent. Then we show that Rényi divergence extends to the extended orders , $1$ and $\infty$ in the same way as for finite spaces. Along the way, we also study its behaviour as a function of $\alpha$. By contrast, in Section III we study various convexity and continuity properties of Rényi divergence as a function of $P$ and $Q$, while $\alpha$ is kept fixed. We also generalize the Pythagorean inequality to any order $\alpha\in(0,\infty)$. Section IV contains several minimax results, and treats the connection to Chernoff information in hypothesis testing, to which many applications of Rényi divergence are related. We also discuss the equivalence of channel capacity and the minimax redundancy for all orders $\alpha$. Then, in Section V, we show how Rényi divergence extends to negative orders. These are related to the orders $\alpha>1$ by a negative scaling factor and a reversal of the arguments $P$ and $Q$. Finally, Section VI contains a number of counterexamples, showing that properties that hold for certain other divergences are violated by Rényi divergence.

For fixed $\alpha$, Rényi divergence is related to various forms of power divergences, which are in the well-studied class of $f$-divergences . Consequently, several of the results we are presenting for fixed $\alpha$ in Section III are equivalent to known results about power divergences. To make this presentation self-contained we avoid the use of such connections and only use general results from measure theory.

II Definition of Rényi divergence

We will often need to distinguish between the orders for which Rényi divergence can be defined by a generalization of formula (1) to an integral over densities, and the other orders. This motivates the following definitions.

We call a (finite) real number $\alpha$ a simple order if $\alpha>0$ and $\alpha\neq 1$. The values , $1$, and $\infty$ are called extended orders.

Let $P$ and $Q$ be two arbitrary distributions on $(\mathcal{X},\mathcal{F})$. The formula in (1), which defines Rényi divergence for simple orders on finite sample spaces, generalizes to arbitrary spaces as follows:

For any simple order $\alpha,$ the Rényi divergence of order $\alpha$ of $P$ from $Q$ is defined as

where, for $\alpha>1,$ we read $p^{\alpha}q^{1-\alpha}$ as $\frac{p^{\alpha}}{q^{\alpha-1}}$ and adopt the conventions that $\nicefrac{{0}}{{0}}=0$ and $\nicefrac{{x}}{{0}}=\infty$ for $x>0$.

For example, for any simple order $\alpha$, the Rényi divergence of a normal distribution (with mean $\mu_{0}$ and positive variance $\sigma_{0}^{2}$) from another normal distribution (with mean $\mu_{1}$ and positive variance $\sigma_{1}^{2}$) is

provided that $\sigma_{\alpha}^{2}=(1-\alpha)\sigma_{0}^{2}+\alpha\sigma_{1}^{2}>0$ [20, p. 45].

For simple orders, we may always change to integration with respect to $P$:

which shows that our definition does not depend on the choice of dominating measure $\mu$. In most cases it is also equivalent to integrate with respect to $Q$:

However, if $\alpha>1$ and $P\not\ll Q,$ then $D_{\alpha}(P\|Q)=\infty,$ whereas the integral with respect to $Q$ may be finite. This is a subtle consequence of our conventions. For example, if $P=(\nicefrac{{1}}{{2}},\nicefrac{{1}}{{2}})$, $Q=(1,0)$ and $\mu$ is the counting measure, then for $\alpha>1$

II-B Definition via Discretization for Simple Orders

We shall repeatedly use the following result, which is a direct consequence of the Radon-Nikodým theorem :

Suppose $\lambda\ll\mu$ is a probability distribution, or any countably additive measure such that $\lambda(\mathcal{X})\leq 1$. Then for any sub-$\sigma$-algebra $\mathcal{G}\subseteq\mathcal{F}$

It has been argued that grouping observations together (by considering a coarser $\sigma$-algebra), should not increase our ability to distinguish between $P$ and $Q$ under any measure of divergence . This is expressed by the data processing inequality, which Rényi divergence satisfies:

For any simple order $\alpha$ and any sub-$\sigma$-algebra $\mathcal{G}\subseteq\mathcal{F}$

Theorem 9 below shows that the data processing inequality also holds for the extended orders.

The name “data processing inequality” stems from the following application of Theorem 1. Let $X$ and $Y$ be two random variables that form a Markov chain

where the conditional distribution of $Y$ given $X$ is $A(Y|X)$. Then if $Y=f(X)$ is a deterministic function of $X$, we may view $Y$ as the result of “processing” $X$ according to the function $f$. In general, we may also process $X$ using a nondeterministic function, such that $A(Y|X)$ is not a point-mass.

Suppose $P_{X}$ and $Q_{X}$ are distributions for $X$. Let $P_{X}\circ A$ and $Q_{X}\circ A$ denote the corresponding joint distributions, and let $P_{Y}$ and $Q_{Y}$ be the induced marginal distributions for $Y$. Then the reader may verify that $D_{\alpha}(P_{X}\circ A\|Q_{X}\circ A)=D_{\alpha}(P_{X}\|Q_{X})$, and consequently the data processing inequality implies that processing $X$ to obtain $Y$ reduces Rényi divergence:

The next theorem shows that if $\mathcal{X}$ is a continuous space, then the Rényi divergence on $\mathcal{X}$ can be arbitrarily well approximated by the Rényi divergence on finite partitions of $\mathcal{X}$. For any finite or countable partition $\mathcal{P}=\left\{A_{1},A_{2},\ldots\right\}$ of $\mathcal{X}$, let $P_{\lvert\mathcal{P}}\equiv P_{\lvert\sigma(\mathcal{P})}$ and $Q_{\lvert\mathcal{P}}\equiv Q_{\lvert\sigma(\mathcal{P})}$ denote the restrictions of $P$ and $Q$ to the $\sigma$-algebra generated by $\mathcal{P}$.

where the supremum is over all finite partitions $\mathcal{P}\subseteq\mathcal{F}$.

It follows that it would be equivalent to first define Rényi divergence for finite sample spaces and then extend the definition to arbitrary sample spaces using (15).

The identity (15) also holds for the extended orders $1$ and $\infty$. (See Theorem 10 below.)

To show the converse inequality, consider for any $\varepsilon>0$ a discretization of the densities $p$ and $q$ into a countable number of bins

and hence the supremum over all countable partitions is large enough:

It remains to show that the supremum over finite partitions is at least as large. To this end, suppose $\mathcal{Q}=\{B_{1},B_{2},\ldots\}$ is any countable partition and let $\mathcal{P}_{n}=\{B_{1},\ldots,B_{n-1},\bigcup_{i\geq n}B_{i}\}$. Then by

where the inequality holds with equality if $0<\alpha<1$. ∎

II-C Extended Orders: Varying the Order

As for finite alphabets, continuity considerations lead to the following extensions of Rényi divergence to orders for which it cannot be defined using the formula in (9).

The Rényi divergences of orders and $1$ are defined as

and the Rényi divergence of order $\infty$ is defined as

Our definition of $D_{0}$ follows Csiszár . It differs from Rényi’s original definition , which uses (9) with $\alpha=0$ plugged in and is therefore always zero. As illustrated by Section III-F, the present definition is more interesting.

The limits in Definition 3 always exist, because Rényi divergence is nondecreasing in its order:

For $\alpha\in[0,\infty]$ the Rényi divergence $D_{\alpha}(P\|Q)$ is nondecreasing in $\alpha$. On $\mathcal{A}=\{\alpha\in[0,\infty]\mid 0\leq\alpha\leq 1\text{ or }D_{\alpha}(P\|Q)<\infty\}$ it is constant if and only if $P$ is the conditional distribution $Q(\cdot\mid A)$ for some event $A\in\mathcal{F}$.

Let $\alpha<\beta$ be simple orders. Then for $x\geq 0$ the function $x\mapsto x^{\frac{(\alpha-1)}{(\beta-1)}}$ is strictly convex if $\alpha<1$ and strictly concave if $\alpha>1$. Therefore by Jensen’s inequality

From the simple orders, the result extends to the extended orders by the following observations:

Let us verify that the limits in Definition 3 can be expressed in closed form, just like for finite alphabets. We require the following lemma:

Let $\mathcal{A}=\{\alpha\text{ a simple order}\mid 0<\alpha<1$ or $D_{\alpha}(P\|Q)<\infty\}$. Then, for any sequence $\alpha_{1},\alpha_{2},\ldots\in\mathcal{A}$ such that $\alpha_{n}\rightarrow\beta\in\mathcal{A}\operatorname{\cup}\{0,1\}$,

Our proof extends a proof by Shiryaev [28, pp. 366–367].

The closed-form expression for $\alpha=0$ follows immediately:

By Lemma 1 and the fact that $\lim_{\alpha\downarrow 0}p^{\alpha}q^{1-\alpha}=\text{{1}}_{\{p>0\}}q$. ∎

For $\alpha=1$, the limit in Definition 3 equals the Kullback-Leibler divergence of $P$ from $Q$, which is defined as

with the conventions that $0\ln(\nicefrac{{0}}{{q}})=0$ and $p\ln(\nicefrac{{p}}{{0}})=\infty$ if $p>0$. Consequently, $D(P\|Q)=\infty$ if $P\not\ll Q$.

Moreover, if $D(P\|Q)=\infty$ or there exists a $\beta>1$ such that $D_{\beta}(P\|Q)<\infty$, then also

For example, by letting $\alpha\uparrow 1$ in (10) or by direct computation, it can be derived that the Kullback-Leibler divergence between two normal distributions with positive variance is

The proof of Theorem 5 requires an intermediate lemma:

By Taylor’s theorem with Cauchy’s remainder term we have for any positive $x$ that

for some $\xi$ between $x$ and $1$. As $\frac{\xi-x}{2\xi^{2}}$ is increasing in $\xi$ for $x>\nicefrac{{1}}{{2}}$, the lemma follows. ∎

Alternatively, suppose $P\ll Q$. Then $\lim_{\alpha\uparrow 1}x_{\alpha}=1$ and therefore Lemma 2 implies that

where the restriction of the domain of integration is allowed because $q=0$ implies $p=0$ ($\mu$-a.s.) by $P\ll Q$. Convexity of $p^{\alpha}q^{1-\alpha}$ in $\alpha$ implies that its derivative, $p^{\alpha}q^{1-\alpha}\ln\frac{p}{q}$, is nondecreasing and therefore for $p,q>0$

is nondecreasing in $\alpha$, and $\frac{p-p^{\alpha}q^{1-\alpha}}{1-\alpha}\geq\frac{p-p^{0}q^{1-0}}{1-0}=p-q$. As $\int_{p,q>0}(p-q)$ d$\mu>-\infty$, it follows by the monotone convergence theorem that

which together with (19) proves (17). If $D(P\|Q)=\infty$, then $D_{\beta}(P\|Q)\geq D(P\|Q)=\infty$ for all $\beta>1$ and (18) holds. It remains to prove (18) if there exists a $\beta>1$ such that $D_{\beta}(P\|Q)<\infty$. In this case, arguments similar to the ones above imply that

and $\frac{p^{\alpha}q^{1-\alpha}-p}{\alpha-1}$ is nondecreasing in $\alpha$. Therefore $\frac{p^{\alpha}q^{1-\alpha}-p}{\alpha-1}\leq\frac{p^{\beta}q^{1-\beta}-p}{\beta-1}\leq\frac{p^{\beta}q^{1-\beta}}{\beta-1}$ and, as $\int_{p,q>0}\frac{p^{\beta}q^{1-\beta}}{\beta-1}$ d$\mu<\infty$ is implied by $D_{\beta}(P\|Q)<\infty$, it follows by the monotone convergence theorem that

which together with (20) completes the proof. ∎

For any random variable $X$, the essential supremum of $X$ with respect to $P$ is $\operatorname*{ess\,sup}_{P}X=\sup\{c\mid P(X>c)>0\}$.

with the conventions that $\nicefrac{{0}}{{0}}=0$ and $\nicefrac{{x}}{{0}}=\infty$ if $x>0$.

If the sample space $\mathcal{X}$ is countable, then with the notational conventions of this theorem the essential supremum reduces to an ordinary supremum, and we have $D_{\infty}(P\|Q)=\ln\sup_{x}\frac{P(x)}{Q(x)}$.

If $\mathcal{X}$ contains a finite number of elements $n$, then

This extends to arbitrary measurable spaces $(\mathcal{X},\mathcal{F})$ by Theorem 2:

where $\mathcal{P}$ ranges over all finite partitions in $\mathcal{F}$.

Now if $P\not\ll Q$, then there exists an event $B\in\mathcal{F}$ such that $P(B)>0$ but $Q(B)=0$, and

implies that $\operatorname*{ess\,sup}\nicefrac{{p}}{{q}}=\infty=\sup_{A}\frac{P(A)}{Q(A)}$. Alternatively, suppose that $P\ll Q$. Then

for all $A\in\mathcal{F}$ and it follows that

Let $a<\operatorname*{ess\,sup}\nicefrac{{p}}{{q}}$ be arbitrary. Then there exists a set $A\in\mathcal{F}$ with $P\left(A\right)>0$ such that $\nicefrac{{p}}{{q}}\geq a$ on $A$ and therefore

Thus $\sup_{A\in\mathcal{F}}\frac{P(A)}{Q(A)}\geq a$ for any $a<\operatorname*{ess\,sup}\nicefrac{{p}}{{q}}$, which implies that

In combination with (21) this completes the proof. ∎

Taken together, the previous results imply that Rényi divergence is a continuous function of its order $\alpha$ (under suitable conditions):

The Rényi divergence $D_{\alpha}(P\|Q)$ is continuous in $\alpha$ on $\mathcal{A}=\{\alpha\in[0,\infty]\mid 0\leq\alpha\leq 1\text{ or }D_{\alpha}(P\|Q)<\infty\}$.

Continuity at any simple order $\beta$ follows by Lemma 1. It extends to the extended orders and $\infty$ by the definition of Rényi divergence at these orders. And it extends to $\alpha=1$ by Theorem 5. ∎

III Fixed Nonnegative Orders

In this section we fix the order $\alpha$ and study properties of Rényi divergence as $P$ and $Q$ are varied. First we prove nonnegativity and extend the data processing inequality and the relation to a supremum over finite partitions to the extended orders. Then we study convexity, we prove a generalization of the Pythagorean inequality to general orders, and finally we consider various types of continuity.

For $\alpha>0$, $D_{\alpha}(P\|Q)=0$ if and only if $P=Q$. For $\alpha=0$, $D_{\alpha}(P\|Q)=0$ if and only if $Q\ll P$.

Suppose first that $\alpha$ is a simple order. Then by Jensen’s inequality

Equality holds if and only if $q/p$ is constant $P$-a.s. (first inequality) and $Q\ll P$ (second inequality), which together is equivalent to $P=Q$.

The result extends to $\alpha\in\{1,\infty\}$ by $D_{\alpha}(P\|Q)=\sup_{\beta<\alpha}D_{\beta}(P\|Q)$. For $\alpha=0$ it can be verified directly that $-\ln Q(p>0)\geq 0$, with equality if and only if $Q\ll P$. ∎

For any order $\alpha\in[0,\infty]$ and any sub-$\sigma$-algebra $\mathcal{G}\subseteq\mathcal{F}$

Example 2 also applies to the extended orders without modification.

By Theorem 1, (22) holds for the simple orders. Let $\beta$ be any extended order and let $\alpha_{n}\to\beta$ be an arbitrary sequence of simple orders that converges to $\beta$, from above if $\beta=0$ and from below if $\beta\in\{1,\infty\}$. Then

where the supremum is over all finite partitions $\mathcal{P}\subseteq\mathcal{F}$.

For simple orders $\alpha$, the result holds by Theorem 2. This extends to $\alpha\in\{1,\infty\}$ by monotonicity and left-continuity in $\alpha$:

For $\alpha=0$, the data processing inequality implies that

and equality is achieved for the partition $\mathcal{P}=\{p>0,p=0\}$.

III-B Convexity

Consider Figures 2 and 3. They show $D_{\alpha}(P\|Q)$ as a function of $P$ for sample spaces containing two or three elements. These figures suggest that Rényi divergence is convex in its first argument for small $\alpha$, but not for large $\alpha$. This is in agreement with the well-known fact that it is jointly convex in the pair $(P,Q)$ for $\alpha=1$. It turns out that joint convexity extends to $\alpha<1$, but not to $\alpha>1$, as noted by Csiszár . Our proof generalizes the proof for $\alpha=1$ by Cover and Thomas .

For any order $\alpha\in$ Rényi divergence is jointly convex in its arguments. That is, for any two pairs of probability distributions $(P_{0},Q_{0})$ and $(P_{1},Q_{1})$, and any $0<\lambda<1$

Suppose first that $\alpha=0$, and let $P_{\lambda}=(1-\lambda)P_{0}+\lambda P_{1}$ and $Q_{\lambda}=(1-\lambda)Q_{0}+\lambda Q_{1}$. Then

Equality holds if and only if, for the first inequality, $Q_{0}(p_{0}>0)=Q_{1}(p_{1}>0)$ and, for the second inequality, $p_{1}>0\Rightarrow p_{0}>0$ ($Q_{0}$-a.s.) and $p_{0}>0\Rightarrow p_{1}>0$ ($Q_{1}$-a.s.) These conditions are equivalent to the equality conditions of the theorem.

Alternatively, suppose $\alpha>0$. We will show that point-wise

where $p_{\lambda}=(1-\lambda)p_{0}+\lambda p_{1}$ and $q_{\lambda}=(1-\lambda)q_{0}+\lambda q_{1}$. For $\alpha=1$, (23) then follows directly; for $0<\alpha<1$, (23) follows from (24) by Jensen’s inequality:

If one of $p_{0},p_{1},q_{0}$ and $q_{1}$ is zero, then (24) can be verified directly. So assume that they are all positive. Then for $0<\alpha<1$ let $f(x)=-x^{\alpha}$ and for $\alpha=1$ let $f(x)=x\ln x$, such that (24) can be written as

Joint convexity in $P$ and $Q$ breaks down for $\alpha>1$ (see Section VI-A), but some partial convexity properties can still be salvaged. First, convexity in the second argument does hold for all $\alpha$ :

For any order $\alpha\in[0,\infty]$ Rényi divergence is convex in its second argument. That is, for any probability distributions $P$, $Q_{0}$ and $Q_{1}$

for any $0<\lambda<1$. For finite $\alpha$, equality holds if and only if

For $\alpha\in$ this follows from the previous theorem. (For $P_{0}=P_{1}$ the equality conditions reduce to the ones given here.) For $\alpha\in(1,\infty)$, let $Q_{\lambda}=(1-\lambda)Q_{0}+\lambda Q_{1}$ and define $f(x,Q_{\lambda})=(p(x)/q_{\lambda}(x))^{\alpha-1}$. It is sufficient to show that

Noting that, for every $x\in\mathcal{X}$, $f(x,Q)$ is log-convex in $Q$, this is a consequence of the general fact that an expectation over log-convex functions is itself log-convex, which can be shown using Hölder’s inequality:

Taking logarithms completes the proof of (26). Equality holds in the first inequality if and only if $q_{0}=q_{1}$ ($P$-a.s.), which is also sufficient for equality in the second inequality. Finally, (26) extends to $\alpha=\infty$ by letting $\alpha$ tend to $\infty$. ∎

And secondly, Rényi divergence is jointly quasi-convex in both arguments for all $\alpha$:

For any order $\alpha\in[0,\infty]$ Rényi divergence is jointly quasi-convex in its arguments. That is, for any two pairs of probability distributions $(P_{0},Q_{0})$ and $(P_{1},Q_{1})$, and any $\lambda\in(0,1)$

which holds by essentially the same argument as for (24) in the proof of Theorem 11, with the convex function $f(x)=x^{\alpha}$.

Finally, the case $\alpha=\infty$ follows by letting $\alpha$ tend to $\infty$:

III-C A Generalized Pythagorean Inequality

An important result in statistical applications of information theory is the Pythagorean inequality for Kullback-Leibler divergence . It states that, if $\mathcal{P}$ is a convex set of distributions, $Q$ is any distribution not in $\mathcal{P}$, and $D_{\text{min}}=\inf_{P\in\mathcal{P}}D(P\|Q)$, then there exists a distribution $P^{\ast}$ such that

The main use of the Pythagorean inequality lies in its implication that if $P_{1},P_{2},\ldots$ is a sequence of distributions in $\mathcal{P}$ such that $D(P_{n}\|Q)\rightarrow D_{\text{min}}$, then $P_{n}$ converges to $P^{\ast}$ in the strong sense that $D(P_{n}\|P^{\ast})\rightarrow 0$.

For $\alpha\neq 1$ Rényi divergence does not satisfy the ordinary Pythagorean inequality, but there does exist a generalization if we replace convexity of $\mathcal{P}$ by the following alternative notion of convexity:

For $\alpha\in(0,\infty)$, we will call a set of distributions $\mathcal{P}$ $\alpha$-convex if, for any probability distribution $\lambda=(\lambda_{1},\lambda_{2})$ and any two distributions $P_{1},P_{2}\in\mathcal{P}$, we also have $P_{\lambda}\in\mathcal{P}$, where $P_{\lambda}$ is the $(\alpha,\lambda)$-mixture of $P_{1}$ and $P_{2}$, which will be defined below.

For $\alpha=1$, the $(\alpha,\lambda)$-mixture is simply the ordinary mixture $\lambda_{1}P_{1}+\lambda_{2}P_{2}$, so that $1$-convexity is equivalent to ordinary convexity. We generalize this to other $\alpha$ as follows:

Let $\alpha\in(0,\infty)$ and let $P_{1},\ldots,P_{m}$ be any probability distributions. Then for any probability distribution $\lambda=(\lambda_{1},\ldots,\lambda_{m})$ we define the $(\alpha,\lambda)$-mixture $P_{\lambda}$ of $P_{1},\ldots,P_{m}$ as the distribution with density

The normalizing constant $Z$ is always well defined:

The normalizing constant $Z$ in (29) is bounded by

Since every $p_{\theta}$ integrates to $1$, it follows that

The left-hand side is minimized at $\lambda=\nicefrac{{1}}{{m}}$, where it equals $m^{-(1-\alpha)/\alpha}$, which completes the proof for $\alpha\in(0,1)$. The proof for $\alpha\in(1,\infty)$ goes the same way, except that all inequalities are reversed because $f$ is concave. ∎

And, like for $\alpha=1$, the set of $(\alpha,\lambda)$-mixtures is closed under taking further mixtures of its elements:

Let $\alpha\in(0,\infty)$, let $P_{1},\ldots,P_{m}$ be arbitrary probability distributions and let $P_{\lambda_{1}}$ and $P_{\lambda_{2}}$ be their $(\alpha,\lambda_{1})$- and $(\alpha,\lambda_{2})$-mixtures for some distributions $\lambda_{1},\lambda_{2}$. Then, for any distribution $\gamma=(\gamma_{1},\gamma_{2})$, the $(\alpha,\gamma)$-mixture of $P_{\lambda_{1}}$ and $P_{\lambda_{2}}$ is an $(\alpha,\nu)$-mixture of $P_{1},\ldots,P_{m}$ for the distribution $\nu$ such that

where $C=\frac{\gamma_{1}}{Z_{1}^{\alpha}}+\frac{\gamma_{2}}{Z_{2}^{\alpha}}$, and $Z_{1}$ and $Z_{2}$ are the normalizing constants of $P_{\lambda_{1}}$ and $P_{\lambda_{2}}$ as defined in (29).

Let $M_{\gamma}$ be the $(\alpha,\gamma)$-mixture of $P_{\lambda_{1}}$ and $P_{\lambda_{2}}$, and take $\lambda_{i}=(\lambda_{i,1,},\ldots,\lambda_{i,m})$. Then

We are now ready to generalize the Pythagorean inequality to any $\alpha\in(0,\infty)$:

Let $\alpha\in(0,\infty)$. Suppose that $\mathcal{P}$ is an $\alpha$-convex set of distributions. Let $Q$ be an arbitrary distribution and suppose that the $\alpha$-information projection

exists. Then we have the Pythagorean inequality

This result is new, although the work of Sundaresan on a generalization of Rényi divergence might be related . Our proof follows the same approach as the proof for $\alpha=1$ by Cover and Thomas .

For $\alpha=1$, this is just the standard Pythagorean inequality for Kullback-Leibler divergence. See, for example, the proof by Topsøe . It remains to prove the theorem when $\alpha$ is a simple order.

Putting everything together, we therefore find

and if $\alpha<1$ we have the converse of this inequality. In both cases, the Pythagorean inequality (33) follows upon taking logarithms and dividing by $\alpha-1$ (which flips the inequality sign for $\alpha<1$). ∎

III-D Continuity

In this section we study continuity properties of the Rényi divergence $D_{\alpha}(P\|Q)$ of different orders in the pair of probability distributions $(P,Q)$. It turns out that continuity depends on the order $\alpha$ and the topology on the set of all probability distributions.

The set of probability distributions on $(\mathcal{X},\mathcal{F})$ may be equipped with the topology of setwise convergence, which is the coarsest topology such that, for any event $A\in\mathcal{F}$, the function $P\mapsto P(A)$ that maps a distribution to its probability on $A$, is continuous. In this topology, convergence of a sequence of probability distributions $P_{1},P_{2},\ldots$ to a probability distribution $P$ means that $P_{n}(A)\rightarrow P(A)$ for any $A\in\mathcal{F}$.

Alternatively, one might consider the topology defined by the total variation distance

in which $P_{n}\rightarrow P$ means that $V(P_{n},P)\rightarrow 0$. The total variation topology is stronger than the topology of setwise convergence in the sense that convergence in total variation distance implies convergence on any $A\in\mathcal{F}$. The two topologies coincide if the sample space $\mathcal{X}$ is countable.

In general, Rényi divergence is lower semi-continuous for positive orders:

For any order $\alpha\in(0,\infty]$, $D_{\alpha}(P\|Q)$ is a lower semi-continuous function of the pair $(P,Q)$ in the topology of setwise convergence.

Suppose $\mathcal{X}=\{x_{1},\ldots,x_{k}\}$ is finite. Then for any simple order $\alpha$

where $p_{i}=P(x_{i})$ and $q_{i}=Q(x_{i})$. If $0<\alpha<1$, then $p_{i}^{\alpha}q_{i}^{1-\alpha}$ is continuous in $(P,Q)$. For $1<\alpha<\infty$, it is only discontinuous at $p_{i}=q_{i}=0$, but there $p_{i}^{\alpha}q_{i}^{1-\alpha}=0=\min_{(P,Q)}p_{i}^{\alpha}q_{i}^{1-\alpha}$, so then $p_{i}^{\alpha}q_{i}^{1-\alpha}$ is still lower semi-continuous. These properties carry over to $\sum_{i=1}^{k}p_{i}^{\alpha}q_{i}^{1-\alpha}$ and thus $D_{\alpha}(P\|Q)$ is continuous for $0<\alpha<1$ and lower semi-continuous for $\alpha>1$. A supremum over (lower semi-)continuous functions is itself lower semi-continuous. Therefore, for simple orders $\alpha$, Theorem 2 implies that $D_{\alpha}(P\|Q)$ is lower semi-continuous for arbitrary $\mathcal{X}$. This property extends to the extended orders $1$ and $\infty$ by $D_{\beta}(P\|Q)=\sup_{\alpha<\beta}D_{\alpha}(P\|Q)$ for $\beta\in\{1,\infty\}$. ∎

Moreover, if $\alpha\in(0,1)$ and the total variation topology is assumed, then Theorem 17 below shows that Rényi divergence is uniformly continuous.

First we prove that the topologies induced by Rényi divergences of orders $\alpha\in(0,1)$ are all equivalent:

This follows from the following symmetry-like property, which may be verified directly.

Note that, in particular, Rényi divergence is symmetric for $\alpha=\nicefrac{{1}}{{2}}$, but that skew symmetry does not hold for $\alpha=0$ and $\alpha=1$.

We have already established the second inequality in Theorem 3, so it remains to prove the first one. Skew symmetry implies that

By (5), these results show that, for $\alpha\in(0,1)$, $D_{\alpha}(P_{n}\|Q)\rightarrow 0$ is equivalent to convergence of $P_{n}$ to $Q$ in Hellinger distance, which is equivalent to convergence of $P_{n}$ to $Q$ in total variation [28, p. 364].

Next we shall prove a stronger result on the relation between Rényi divergence and total variation.

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

Let $0<\alpha<1$. Then for all $x,y\geq 0$ and $\varepsilon>0$

If $x,y\leq\varepsilon$ or $x=y$ the inequality $\lvert x^{\alpha}-y^{\alpha}\rvert\leq\varepsilon^{\alpha}$ is obvious. So assume that $x>y$ and $x\geq\varepsilon$. Then

Since $x\mapsto\frac{1}{\alpha-1}\ln(1-x)$ is continuous, it is sufficient to prove that $d_{\alpha}(P,Q)$ is a uniformly continuous function of $(P,Q)$. For any $\varepsilon>0$ and distributions $P_{1},P_{2}$ and $Q$, Lemma 5 implies that

As $d_{\alpha}(P,Q)=d_{1-\alpha}(Q,P)$, it also follows that $\left|d_{\alpha}(P,Q_{1})-d_{\alpha}(P,Q_{2})\right|\leq\varepsilon^{1-\alpha}+\varepsilon^{-\alpha}V(Q_{1},Q_{2})$ for any $Q_{1},Q_{2}$ and $P$. Therefore

A partial extension to $\alpha=0$ follows:

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

This follows from Theorem 17 because $D_{0}(P\|Q)$ is the infimum of the continuous functions $(P,Q)\mapsto D_{\alpha}(P\|Q)$ for $\alpha\in(0,1)$. ∎

If we consider continuity in $Q$ only, then for any finite sample space we obtain:

Suppose $\mathcal{X}$ is finite, and let $\alpha\in[0,\infty]$. Then for any $P$ the Rényi divergence $D_{\alpha}(P\|Q)$ is continuous in $Q$ in the topology of setwise convergence.

Directly from the closed-form expressions for Rényi divergence. ∎

Finally, we will also consider the weak topology, which is weaker than the two topologies discussed above. In the weak topology, convergence of $P_{1},P_{2},\ldots$ to $P$ means that

Suppose that $\mathcal{X}$ is a Polish space. Then for any order $\alpha\in(0,\infty]$, $D_{\alpha}(P\|Q)$ is a lower semi-continuous function of the pair $(P,Q)$ in the weak topology.

The proof is essentially the same as the proof for $\alpha=1$ by Posner .

Let $P_{1},P_{2},\ldots$ and $Q_{1},Q_{2},\ldots$ be sequences of distributions that weakly converge to $P$ and $Q$, respectively. We need to show that

For any set $A\in\mathcal{F}$, let $\partial A$ denote its boundary, which is its closure minus its interior, and let $\mathcal{F}_{0}\subseteq\mathcal{F}$ consist of the sets $A\in\mathcal{F}$ such that $P(\partial A)=Q(\partial A)=0$. Then $\mathcal{F}_{0}$ is an algebra by Lemma 1.1 of Prokhorov , applied to the measure $P+Q$, and the Portmanteau theorem implies that $P_{n}(A)\to P(A)$ and $Q_{n}(A)\to Q(A)$ for any $A\in\mathcal{F}_{0}$ .

Posner [36, proof of Theorem 1] shows that $\mathcal{F}_{0}$ generates $\mathcal{F}$ (that is, $\sigma(\mathcal{F}_{0})=\mathcal{F}$). By the translator’s proof of Theorem 2.4.1 in Pinsker’s book , this implies that, for any finite partition $\{A_{1},\ldots,A_{k}\}\subseteq\mathcal{F}$ and any $\gamma>0$, there exists a finite partition $\{A^{\prime}_{1},\ldots,A^{\prime}_{k}\}\subseteq\mathcal{F}_{0}$ such that $P(A_{i}\triangle A^{\prime}_{i})\leq\gamma$ and $Q(A_{i}\triangle A^{\prime}_{i})\leq\gamma$ for all $i$, where $A_{i}\triangle A^{\prime}_{i}=(A_{i}\setminus A^{\prime}_{i})\operatorname{\cup}(A^{\prime}_{i}\setminus A_{i})$ denotes the symmetric set difference. By the data processing inequality and lower semi-continuity in the topology of setwise convergence, this implies that (15) still holds when the supremum is restricted to finite partitions $\mathcal{P}$ in $\mathcal{F}_{0}$ instead of $\mathcal{F}$.

Thus, for any $\varepsilon>0$, we can find a finite partition $\mathcal{P}\subseteq\mathcal{F}_{0}$ such that

The data processing inequality and the fact that $P_{n}(A)\to P(A)$ and $Q_{n}(A)\to Q(A)$ for all $A\in\mathcal{P}$, together with lower semi-continuity in the topology of setwise convergence, then imply that

for all sufficiently large $n$. Consequently,

for any $\varepsilon>0$, and (36) follows by letting $\varepsilon$ tend to . ∎

Suppose $\mathcal{X}$ is a Polish space, let $Q$ be arbitrary, and let $c\in[0,\infty)$ be a constant. Then the sublevel set

is convex and compact in the topology of weak convergence for any order $\alpha\in[1,\infty]$.

Convexity follows from quasi-convexity of Rényi divergence in its first argument.

Suppose that $P_{1},P_{2},\ldots\in\mathcal{S}$ converges to a finite measure $P$. Then (35), applied to the constant function $f(x)=1$, implies that $P(\mathcal{X})=1$, so that $P$ is also a probability distribution. Hence by lower semi-continuity (Theorem 19) $\mathcal{S}$ is closed. It is therefore sufficient to show that $\mathcal{S}$ is relatively compact.

For any event $A\in\mathcal{F}$, let $A^{\textnormal{c}}=\mathcal{X}\setminus A$ denote its complement. Prokhorov [35, Theorem 1.12] shows that $\mathcal{S}$ is relatively compact if, for any $\varepsilon>0$, there exists a compact set $A\subseteq\mathcal{X}$ such that $P(A^{\textnormal{c}})<\varepsilon$ for all $P\in\mathcal{S}$.

Since $\mathcal{X}$ is a Polish space, for any $\delta>0$ there exists a compact set $B_{\delta}\subseteq\mathcal{X}$ such that $Q(B_{\delta})\geq 1-\delta$ [37, Lemma 1.3.2]. For any distribution $P$, let $P_{\lvert B_{\delta}}$ denote the restriction of $P$ to the binary partition $\{B_{\delta},B^{\textnormal{c}}_{\delta}\}$. Then, by monotonicity in $\alpha$ and the data processing inequality, we have, for any $P\in\mathcal{S}$,

where the last inequality follows from $x\ln x\geq-1/\textnormal{e}$. Consequently,

and since $Q(B^{\textnormal{c}}_{\delta})\to 0$ as $\delta$ tends to we can satisfy the condition of Prokhorov’s theorem by taking $A$ equal to $B_{\delta}$ for any sufficiently small $\delta$ depending on $\varepsilon$. ∎

III-E Limits of σ𝜎\sigma-Algebras

As shown by Theorem 2, there exists a sequence of finite partitions $\mathcal{P}_{1},\mathcal{P}_{2},\ldots$ such that

Theorem 21 below elaborates on this result. It implies that (38) holds for any increasing sequence of partitions $\mathcal{P}_{1}\subseteq\mathcal{P}_{2}\subseteq\cdots$ that generate $\sigma$-algebras converging to $\mathcal{F}$, in the sense that $\mathcal{F}=\sigma\left(\bigcup_{n=1}^{\infty}\mathcal{P}_{n}\right)$. An analogous result holds for infinite sequences of increasingly coarse partitions, which is shown by Theorem 22. For the special case $\alpha=1$, information-theoretic proofs of Theorems 21 and 22 are given by Barron and Harremoës and Holst . Theorem 21 may also be derived from general properties of $f$-divergences .

Let $\mathcal{F}_{1}\subseteq\mathcal{F}_{2}\subseteq\cdots\subseteq\mathcal{F}$ be an increasing family of $\sigma$-algebras, and let $\mathcal{F}_{\infty}=\sigma\left(\bigcup_{n=1}^{\infty}\mathcal{F}_{n}\right)$ be the smallest $\sigma$-algebra containing them. Then for any order $\alpha\in(0,\infty]$

For $\alpha=0$, (39) does not hold. A counterexample is given after Example 3 below.

Let $\mathcal{F}_{1}\subseteq\mathcal{F}_{2}\subseteq\cdots\subseteq\mathcal{F}$ be an increasing family of $\sigma$-algebras, and suppose that $\mu$ is a probability distribution. Then the family of random variables $\{p_{n}\}_{n\geq 1}$ with members $p_{n}=\operatorname{\mathbf{E}}\left[\left.p\right|\mathcal{F}_{n}\right]$ is uniformly integrable (with respect to $\mu$).

The proof of this lemma is a special case of part of the proof of Lévy’s upward convergence theorem in Shiryaev’s textbook [28, p. 510]. We repeat it here for completeness.

in which the inequality marked by $(*)$ is Markov’s. Consequently

Let $\mathcal{F}\supseteq\mathcal{F}_{1}\supseteq\mathcal{F}_{2}\supseteq\cdots$ be a decreasing family of $\sigma$-algebras, and let $\mathcal{F}_{\infty}=\bigcap_{n=1}^{\infty}\mathcal{F}_{n}$ be the largest $\sigma$-algebra contained in all of them. Let $\alpha\in[0,\infty)$. If $\alpha\in[0,1)$ or there exists an $m$ such that $D_{\alpha}(P_{\lvert\mathcal{F}_{m}}\|Q_{\lvert\mathcal{F}_{m}})<\infty$, then

The theorem cannot be extended to the case $\alpha=\infty$.

Suppose first that $\alpha\in(0,1)$. Then for any $b>0$

($Q$-a.s.) As $\min_{x}\,x\ln x=-\textnormal{e}^{-1}$, it follows that $X_{n}\geq 0$ and for any $b,c>0$

where $\operatorname{\mathbf{E}}_{Q}[X_{n}]\leq\operatorname{\mathbf{E}}_{Q}[X_{1}]$ in the last inequality follows from the data processing inequality. Consequently,

By Proposition 1, $p_{n}=\operatorname{\mathbf{E}}_{\mu}\left[\left.p\right|\mathcal{F}_{n}\right]$ and $q_{n}=\operatorname{\mathbf{E}}_{\mu}\left[\left.q\right|\mathcal{F}_{n}\right]$. Therefore by a version of Lévy’s theorem for decreasing sequences of $\sigma$-algebras [41, Theorem 6.23],

and hence $X_{n}\rightarrow X_{\infty}$ ($\mu$-a.s. and therefore $Q$-a.s.) If $0<\alpha<1$, then

And if $\alpha\geq 1$, then by the data processing inequality $D_{\alpha}(P_{\lvert\mathcal{F}_{n}}\|Q_{\lvert\mathcal{F}_{n}})<\infty$ for all $n$, which implies that also in this case $\operatorname{\mathbf{E}}_{Q}[X_{n}]<\infty$. Hence uniform integrability (by Lemma 7) of the family of nonnegative random variables $\{X_{n}\}$ implies (40) [28, Thm. 5, p. 189], and the theorem follows for $\alpha>0$. The remaining case, $\alpha=0$, is proved by

III-F Absolute Continuity and Mutual Singularity

Shiryaev [28, pp. 366, 370] relates Hellinger integrals to absolute continuity and mutual singularity of probability distributions. His results may more elegantly be expressed in terms of Rényi divergence. They then follow from the observations that $D_{0}(P\|Q)=0$ if and only if $Q$ is absolutely continuous with respect to $P$ and that $D_{0}(P\|Q)=\infty$ if and only if $P$ and $Q$ are mutually singular, together with right-continuity of $D_{\alpha}(P\|Q)$ in $\alpha$ at $\alpha=0$. As illustrated in the next section, these properties give a convenient mathematical tool to establish absolute continuity or mutual singularity of infinite product distributions.

$\lim_{\alpha\downarrow 0}D_{\alpha}(P\|Q)=0$.

Clearly (ii) is equivalent to $Q(p=0)=0$, which is equivalent to (i). The other cases follow by $\lim_{\alpha\downarrow 0}D_{\alpha}(P\|Q)=D_{0}(P\|Q)=-\ln Q(p>0)$. ∎

$D_{\alpha}(P\|Q)=\infty$ for some $\alpha\in[0,1)$,

$D_{\alpha}(P\|Q)=\infty$ for all $\alpha\in[0,\infty]$.