Rényi entropy

Template:Short description In information theory, the Rényi entropy is a quantity that generalizes various notions of entropy, including Hartley entropy, Shannon entropy, collision entropy, and min-entropy. The Rényi entropy is named after Alfréd Rényi, who looked for the most general way to quantify information while preserving additivity for independent events. In the context of fractal dimension estimation, the Rényi entropy forms the basis of the concept of generalized dimensions.

The Rényi entropy is important in ecology and statistics as index of diversity. The Rényi entropy is also important in quantum information, where it can be used as a measure of entanglement. In the Heisenberg XY spin chain model, the Rényi entropy as a function of Template:Mvar can be calculated explicitly because it is an automorphic function with respect to a particular subgroup of the modular group. In theoretical computer science, the min-entropy is used in the context of randomness extractors.

Definition

The Rényi entropy of order Template:Tmath, where $0<\alpha <\mathrm{\infty }$ and Template:Tmath, is defined as

${\mathrm{H}}_{\alpha }(X)=\frac{1}{1-\alpha }\log \left(\sum _{i=1}^n{p}_i^{\alpha }\right).$

It is further defined at $\alpha =0,1,\mathrm{\infty }$ as

${\mathrm{H}}_{\alpha }(X)=\underset{\gamma \to \alpha }{\lim }{\mathrm{H}}_{\gamma }(X).$

Here, $X$ is a discrete random variable with possible outcomes in the set $𝒜=\{x_1,x_2,...,x_n\}$ and corresponding probabilities $p_i\doteq \mathrm{Pr}(X=x_i)$ for Template:Tmath. The resulting unit of information is determined by the base of the logarithm, e.g. shannon for base 2, or nat for base e. If the probabilities are $p_i=1/n$ for all Template:Tmath, then all the Rényi entropies of the distribution are equal: Template:Tmath. In general, for all discrete random variables Template:Tmath, ${\mathrm{H}}_{\alpha }(X)$ is a non-increasing function in Template:Tmath.

Applications often exploit the following relation between the Rényi entropy and the α-norm of the vector of probabilities:

${\mathrm{H}}_{\alpha }(X)=\frac{\alpha }{1-\alpha }\log (\Vert P{\Vert }_{\alpha }).$

Here, the discrete probability distribution $P=(p_1,\dots ,p_n)$ is interpreted as a vector in ${ℝ}^n$ with $p_i\ge 0$ and Template:Tmath.

The Rényi entropy for any $\alpha \ge 0$ is Schur concave. Proven by the Schur–Ostrowski criterion.

Special cases

Rényi entropy of a random variable with two possible outcomes against Template:Math, where Template:Math. Shown are Template:Math₀, Template:Math₁, Template:Math₂ and Template:Math_∞, with the unit on the vertical axis being the shannon.

As $\alpha$ approaches zero, the Rényi entropy increasingly weighs all events with nonzero probability more equally, regardless of their probabilities. In the limit for Template:Tmath, the Rényi entropy is just the logarithm of the size of the support of Template:Mvar. The limit for $\alpha \to 1$ is the Shannon entropy. As $\alpha$ approaches infinity, the Rényi entropy is increasingly determined by the events of highest probability.

Hartley or max-entropy

${\mathrm{H}}_0(X)$ is $\log n$ where $n$ is the number of non-zero probabilities. If the probabilities are all nonzero, it is simply the logarithm of the cardinality of the alphabet (Template:Tmath) of Template:Tmath, sometimes called the Hartley entropy of Template:Tmath,

${\mathrm{H}}_0(X)=\log n=\log |𝒜|$

Shannon entropy

The limiting value of ${\mathrm{H}}_{\alpha }$ as $\alpha \to 1$ is the Shannon entropy:

${\mathrm{H}}_1(X)\equiv \underset{\alpha \to 1}{\lim }{\mathrm{H}}_{\alpha }(X)=-\sum _{i=1}^n{p}_i\log p_i$

Collision entropy

Collision entropy, sometimes just called "Rényi entropy", refers to the case Template:Tmath,

${\mathrm{H}}_2(X)=-\log \sum _{i=1}^n{p}_i^2=-\log P(X=Y),$

where $X$ and $Y$ are independent and identically distributed. The collision entropy is related to the index of coincidence. It is the negative logarithm of the Simpson diversity index.

Min-entropy

Template:Main In the limit as Template:Tmath, the Rényi entropy ${\mathrm{H}}_{\alpha }$ converges to the min-entropy Template:Tmath:

${\mathrm{H}}_{\mathrm{\infty }}(X)\doteq \underset{i}{\min }(-\log p_i)=-(\underset{i}{\max }\log p_i)=-\log \underset{i}{\max }{p}_i.$

Equivalently, the min-entropy ${\mathrm{H}}_{\mathrm{\infty }}(X)$ is the largest real number Template:Mvar such that all events occur with probability at most Template:Tmath.

The name min-entropy stems from the fact that it is the smallest entropy measure in the family of Rényi entropies. In this sense, it is the strongest way to measure the information content of a discrete random variable. In particular, the min-entropy is never larger than the Shannon entropy.

The min-entropy has important applications for randomness extractors in theoretical computer science: Extractors are able to extract randomness from random sources that have a large min-entropy; merely having a large Shannon entropy does not suffice for this task.

Inequalities for different orders α

That ${\mathrm{H}}_{\alpha }$ is non-increasing in $\alpha$ for any given distribution of probabilities Template:Tmath, which can be proven by differentiation, as

$-\frac{d{\mathrm{H}}_{\alpha }}{d\alpha }=\frac{1}{(1-\alpha {)}^2}\sum _{i=1}^n{z}_i\log (z_i/p_i)=\frac{1}{(1-\alpha {)}^2}{D}_{KL}(z\Vert p)$

which is proportional to Kullback–Leibler divergence (which is always non-negative), where Template:Tmath. In particular, it is strictly positive except when the distribution is uniform.

At the $\alpha \to 1$ limit, we have Template:Tmath.

In particular cases inequalities can be proven also by Jensen's inequality:

$\log n={\mathrm{H}}_0\ge {\mathrm{H}}_1\ge {\mathrm{H}}_2\ge {\mathrm{H}}_{\mathrm{\infty }}.$

For values of Template:Tmath, inequalities in the other direction also hold. In particular, we have

${\mathrm{H}}_2\le 2{\mathrm{H}}_{\mathrm{\infty }}.$

On the other hand, the Shannon entropy ${\mathrm{H}}_1$ can be arbitrarily high for a random variable $X$ that has a given min-entropy. An example of this is given by the sequence of random variables $X_n\sim \{0,\dots ,n\}$ for $n\ge 1$ such that $P(X_n=0)=1/2$ and $P(X_n=x)=1/(2n)$ since ${\mathrm{H}}_{\mathrm{\infty }}(X_n)=\log 2$ but Template:Tmath.

Rényi divergence

As well as the absolute Rényi entropies, Rényi also defined a spectrum of divergence measures generalising the Kullback–Leibler divergence.

The Rényi divergence of order Template:Tmath or alpha-divergence of a distribution Template:Math from a distribution Template:Math is defined to be

$D_{\alpha }(P\Vert Q)=\frac{1}{\alpha -1}\log \left(\sum _{i=1}^n\frac{p_i^{\alpha }}{q_i^{\alpha -1}}\right)=\frac{1}{\alpha -1}\log {𝔼}_{i\sim p}[(p_i/q_i{)}^{\alpha -1}]$

when Template:Tmath and Template:Tmath. We can define the Rényi divergence for the special values Template:Math by taking a limit, and in particular the limit Template:Math gives the Kullback–Leibler divergence.

Some special cases:

Template:Tmath: minus the log probability under Template:Math that Template:Math;

Template:Tmath: minus twice the logarithm of the Bhattacharyya coefficient; (Template:Harvtxt)

Template:Tmath: the Kullback–Leibler divergence;

Template:Tmath: the log of the expected ratio of the probabilities;

Template:Tmath: the log of the maximum ratio of the probabilities.

The Rényi divergence is indeed a divergence, meaning simply that $D_{\alpha }(P\Vert Q)$ is greater than or equal to zero, and zero only when Template:Math. For any fixed distributions Template:Math and Template:Math, the Rényi divergence is nondecreasing as a function of its order Template:Math, and it is continuous on the set of Template:Math for which it is finite, or for the sake of brevity, the information of order Template:Math obtained if the distribution Template:Math is replaced by the distribution Template:Math.

Financial interpretation

A pair of probability distributions can be viewed as a game of chance in which one of the distributions defines official odds and the other contains the actual probabilities. Knowledge of the actual probabilities allows a player to profit from the game. The expected profit rate is connected to the Rényi divergence as follows

$\mathrm{E}\mathrm{x}\mathrm{p}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{e}\mathrm{d}\mathrm{R}\mathrm{a}\mathrm{t}\mathrm{e}=\frac{1}{R}{D}_1(b\Vert m)+\frac{R-1}{R}{D}_{1/R}(b\Vert m),$

where $m$ is the distribution defining the official odds (i.e. the "market") for the game, $b$ is the investor-believed distribution and $R$ is the investor's risk aversion (the Arrow–Pratt relative risk aversion).

If the true distribution is $p$ (not necessarily coinciding with the investor's belief Template:Tmath), the long-term realized rate converges to the true expectation which has a similar mathematical structure

$\mathrm{R}\mathrm{e}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{z}\mathrm{e}\mathrm{d}\mathrm{R}\mathrm{a}\mathrm{t}\mathrm{e}=\frac{1}{R}(D_1(p\Vert m)-D_1(p\Vert b))+\frac{R-1}{R}{D}_{1/R}(b\Vert m).$

Properties specific to α = 1

The value Template:Tmath, which gives the Shannon entropy and the Kullback–Leibler divergence, is the only value at which the chain rule of conditional probability holds exactly:

$\mathrm{H}(A,X)=\mathrm{H}(A)+{𝔼}_{a\sim A}[\mathrm{H}(X|A=a)]$

for the absolute entropies, and

$D_{\mathrm{K}\mathrm{L}}(p(x|a)p(a)\Vert m(x,a))=D_{\mathrm{K}\mathrm{L}}(p(a)\Vert m(a))+{𝔼}_{p(a)}\{D_{\mathrm{K}\mathrm{L}}(p(x|a)\Vert m(x|a))\},$

for the relative entropies.

The latter in particular means that if we seek a distribution Template:Math which minimizes the divergence from some underlying prior measure Template:Math, and we acquire new information which only affects the distribution of Template:Math, then the distribution of Template:Math remains Template:Math, unchanged.

The other Rényi divergences satisfy the criteria of being positive and continuous, being invariant under 1-to-1 co-ordinate transformations, and of combining additively when Template:Math and Template:Math are independent, so that if Template:Math, then

${\mathrm{H}}_{\alpha }(A,X)={\mathrm{H}}_{\alpha }(A)+{\mathrm{H}}_{\alpha }(X)$

and

$D_{\alpha }(P(A)P(X)\Vert Q(A)Q(X))=D_{\alpha }(P(A)\Vert Q(A))+D_{\alpha }(P(X)\Vert Q(X)).$

The stronger properties of the $\alpha =1$ quantities allow the definition of conditional information and mutual information from communication theory.

Exponential families

The Rényi entropies and divergences for an exponential family admit simple expressions

${\mathrm{H}}_{\alpha }(p_F(x;\theta ))=\frac{1}{1-\alpha }(F(\alpha \theta )-\alpha F(\theta )+\log E_p[e^{(\alpha -1)k(x)}])$

and

$D_{\alpha }(p:q)=\frac{J_{F,\alpha }(\theta :{\theta }^{\prime })}{1-\alpha }$

where

$J_{F,\alpha }(\theta :{\theta }^{\prime })=\alpha F(\theta )+(1-\alpha )F({\theta }^{\prime })-F(\alpha \theta +(1-\alpha ){\theta }^{\prime })$

is a Jensen difference divergence.

Physical meaning

The Rényi entropy in quantum physics is not considered to be an observable, due to its nonlinear dependence on the density matrix. (This nonlinear dependence applies even in the special case of the Shannon entropy.) It can, however, be given an operational meaning through the two-time measurements (also known as full counting statistics) of energy transfersTemplate:Citation needed.

The limit of the quantum mechanical Rényi entropy as $\alpha \to 1$ is the von Neumann entropy.

See also

• Diversity indices
• Tsallis entropy
• Generalized entropy index

References

• Template:Cite book
• Template:Cite journal
• Template:Cite journal
• Template:Citation
• Template:Cite journal
• Template:Springer
• Template:Cite report
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite conference
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite book