Rényi entropy

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 α 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

Let X be a discrete random variable with possible outcomes in the set 𝒜={x1,x2,...,xn} and corresponding probabilities pi≐Pr⁡(X=xi) for ⁠i=1,…,n⁠. Then, the Rényi entropy of order ⁠α⁠, where 0<α<∞ and ⁠α≠1⁠, is defined as Hα(X)=11−αlog⁡(∑i=1npiα). It is further defined at α=0,1,∞ as Hα(X)=limγ→αHγ(X).

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 pi=1/n for all ⁠i=1,…,n⁠, then all the Rényi entropies of the distribution are equal: ⁠Hα(X)=log⁡n⁠. In general, for all discrete random variables ⁠X⁠, Hα(X) is a non-increasing function in ⁠α⁠.

Applications often exploit the following relation between the Rényi entropy and the α-norm of the vector of probabilities: Hα(X)=α1−αlog⁡(‖P‖α). Here, the discrete probability distribution P=(p1,…,pn) is interpreted as a vector in ℝn with pi≥0 and ∑i=1npi=1.

The Rényi entropy for any α≥0 is Schur concave, a property that can be proven by the Schur–Ostrowski criterion.

Special cases

Rényi entropy of a random variable with two possible outcomes against p1, where P = (p1, 1 − p1). Shown are Η0, Η1, Η2 and Η∞, with the unit on the vertical axis being the shannon.

As α approaches zero, the Rényi entropy increasingly weighs all events with nonzero probability more equally, regardless of their probabilities. In the limit for ⁠α→0⁠, the Rényi entropy is just the logarithm of the size of the support of X. The limit for α→1 is the Shannon entropy. For α=2, the Rényi entropy is related to the collision probability, and the quantity 2H2=1/∑pi2 is known as the participation ratio, widely used in condensed matter physics and random matrix theory to measure the effective number of states contributing to a distribution. As α approaches infinity, the Rényi entropy is increasingly determined by the events of highest probability.

Hartley or max-entropy

H0(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 (⁠𝒜⁠) of ⁠X⁠, sometimes called the Hartley entropy of ⁠X⁠, H0(X)=log⁡n=log⁡|𝒜|

Shannon entropy

The limiting value of Hα as α→1 is the Shannon entropy: H1(X)≡limα→1Hα(X)=−∑i=1npilog⁡pi

Collision entropy

Collision entropy, sometimes just called "Rényi entropy", refers to the case ⁠α=2⁠, H2(X)=−log⁡∑i=1npi2=−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. The quantity 2H2=1/∑pi2 is also known in random matrix theory as the participation ratio, where it measures the effective number of eigenstates contributing to a quantum state or, more generally, the effective number of eigenvalues contributing to a matrix spectrum.

Min-entropy

In the limit as ⁠α→∞⁠, the Rényi entropy Hα converges to the min-entropy ⁠H∞⁠: H∞(X)≐mini(−log⁡pi)=−(maxilog⁡pi)=−log⁡maxipi.

Equivalently, the min-entropy H∞(X) is the largest real number b such that all events occur with probability at most ⁠2−b⁠.

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 Hα is non-increasing in α for any given distribution of probabilities ⁠pi⁠, which can be proven by differentiation, as −dHαdα=1(1−α)2∑i=1nzilog⁡(zi/pi)=1(1−α)2DKL(z‖p) which is proportional to Kullback–Leibler divergence (which is always non-negative), where zi=piα/∑j=1npjα. In particular, it is strictly positive except when the distribution is uniform.

At the α→1 limit, we have −dHαdα→12∑ipi(ln⁡pi+H(p))2.

In particular cases inequalities can be proven also by Jensen's inequality: log⁡n=H0≥H1≥H2≥H∞.

For values of ⁠α>1⁠, inequalities in the other direction also hold. In particular, we have H2≤2H∞.

On the other hand, the Shannon entropy H1 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 Xn∼{0,…,n} for n≥1 such that P(Xn=0)=1/2 and P(Xn=x)=1/(2n) since H∞(Xn)=log⁡2 but ⁠H1(Xn)=(log⁡2+log⁡2n)/2⁠.

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 ⁠α⁠ or alpha-divergence of a distribution P from a distribution Q is defined to be Dα(P‖Q)=1α−1log⁡(∑i=1npiαqi1−α)=1α−1log⁡𝔼i∼p[(pi/qi)α−1] when ⁠0<α<∞⁠ and ⁠α≠1⁠. We can define the Rényi divergence for the special values α = 0, 1, ∞ by taking a limit, and in particular the limit α → 1 gives the Kullback–Leibler divergence.

Some special cases:

The Rényi divergence is indeed a divergence, meaning simply that Dα(P‖Q) is greater than or equal to zero, and zero only when P = Q. For any fixed distributions P and Q, the Rényi divergence is nondecreasing as a function of its order α, and it is continuous on the set of α for which it is finite, or for the sake of brevity, the information of order α obtained if the distribution P is replaced by the distribution Q.

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 ExpectedRate=1RD1(b‖m)+R−1RD1/R(b‖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 ⁠b⁠), the long-term realized rate converges to the true expectation which has a similar mathematical structure RealizedRate=1R(D1(p‖m)−D1(p‖b))+R−1RD1/R(b‖m).

Properties specific to α = 1

The value ⁠α=1⁠, which gives the Shannon entropy and the Kullback–Leibler divergence, is the only value at which the chain rule of conditional probability holds exactly: H(A,X)=H(A)+𝔼a∼A[H(X|A=a)] for the absolute entropies, and DKL(p(x|a)p(a)‖m(x,a))=DKL(p(a)‖m(a))+𝔼p(a){DKL(p(x|a)‖m(x|a))}, for the relative entropies.

The latter in particular means that if we seek a distribution p(x, a) which minimizes the divergence from some underlying prior measure m(x, a), and we acquire new information which only affects the distribution of a, then the distribution of p(x|a) remains m(x|a), 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 A and X are independent, so that if p(A, X) = p(A)p(X), then Hα(A,X)=Hα(A)+Hα(X) and Dα(P(A)P(X)‖Q(A)Q(X))=Dα(P(A)‖Q(A))+Dα(P(X)‖Q(X)).

The stronger properties of the α=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 Hα(pF(x;θ))=11−α(F(αθ)−αF(θ)+log⁡Ep[e(α−1)k(x)]) and Dα(p:q)=JF,α(θ:θ′)1−α where JF,α(θ:θ′)=αF(θ)+(1−α)F(θ′)−F(αθ+(1−α)θ′) is a Jensen difference divergence.

Quantum information

The Rényi entropy can be generalized to the quantum case as

Hα(ρ):=11−αlog⁡tr⁡(ρα)

where ρ is normalized density matrix. Its limit as α→1 is the von Neumann entropy.

The Rényi relative entropy (or divergence) can be generalized in two possible ways: the straightforward quantum Rényi relative entropy

Dα(ρ‖σ)=1α−1log⁡tr⁡(ρασ1−α)

and the sandwiched Rényi relative entropy

D~α(ρ‖σ)=1α−1log⁡tr⁡[(σ1−α2αρσ1−α2α)α]

Both converge to the quantum relative entropy in the limit α→1. However, the sandwiched Rényi relative entropy has more convenient properties when used to defined conditional entropies, and has found applications in quantum key distribution.

Stabilizer Rényi entropy

One measure of quantum magic is the stabilizer Rényi entropy of order α:

Mα=11−αlog⁡[12N∑P̂∈ℙN⟨P̂⟩2α]

with P̂ being the multi-qubit Pauli group and ⟨P̂⟩=⟨ψ|P̂|ψ⟩ is an expectation value (quantum mechanics) for an N-qubit system.

Ecology

Hill (1973) showed that the exponential of the Rényi entropy of order α defines a one-parameter family of diversity indices, now known as Hill numbers: αD = exp(Hα). For α = 0, this gives the species richness (total count of species present); for α = 1, the exponential of the Shannon entropy; and for α = 2, the inverse Simpson index, which counts the effective number of equally common species. Hill's framework unifies several previously disparate diversity measures as members of a single parametric family, differing only in how much weight is given to rare versus common species.

See also

Notes

  1. 1 2 3 Rényi (1961)
  2. ↑ Rioul (2021)
  3. ↑ Barros, Vanessa; Rousseau, Jérôme (2021-06-01). "Shortest Distance Between Multiple Orbits and Generalized Fractal Dimensions". Annales Henri Poincaré. 22 (6): 1853–1885. arXiv:1912.07516. Bibcode:2021AnHP...22.1853B. doi:10.1007/s00023-021-01039-y. ISSN 1424-0661. S2CID 209376774.
  4. ↑ Franchini, Its & Korepin (2008)
  5. ↑ Its & Korepin (2010)
  6. ↑ RFC 4086, page 6
  7. ↑ Bromiley, Thacker & Bouhova-Thacker (2004)
  8. ↑ Bell, R. J.; Dean, P. (1970). "Atomic vibrations in vitreous silica". Discussions of the Faraday Society. 50: 55–61. doi:10.1039/df9705000055.
  9. ↑ Beck & Schlögl (1993)
  10. ↑ H1≥H2 holds because ⁠∑i=1Mpilog⁡pi≤log⁡∑i=1Mpi2⁠.
  11. ↑ H∞≤H2 holds because ⁠log⁡∑i=1npi2≤log⁡supipi(∑i=1npi)=log⁡supipi⁠.
  12. ↑ H2≤2H∞ holds because log⁡∑i=1npi2≥log⁡supipi2=2log⁡supipi
  13. ↑ Devroye, Luc; Györfi, Laszlo; Lugosi, Gabor (1996-04-04). A Probabilistic Theory of Pattern Recognition (Corrected ed.). New York, NY: Springer. ISBN 978-0-387-94618-4.
  14. 1 2 Van Erven, Tim; Harremoës, Peter (2014). "Rényi Divergence and Kullback–Leibler Divergence". IEEE Transactions on Information Theory. 60 (7): 3797–3820. arXiv:1206.2459. Bibcode:2014ITIT...60.3797V. doi:10.1109/TIT.2014.2320500. S2CID 17522805.
  15. 1 2 Soklakov (2018)
  16. ↑ Nielsen & Nock (2011)
  17. 1 2 Müller-Lennert, Martin; Dupuis, Frédéric; Szehr, Oleg; Fehr, Serge; Tomamichel, Marco (1 December 2013). "On quantum Rényi entropies: A new generalization and some properties". Journal of Mathematical Physics. 54 (12) 122203. arXiv:1306.3142. Bibcode:2013JMP....54l2203M. doi:10.1063/1.4838856.
  18. ↑ Arqand, Amir; A. Hahn, Thomas; Y. -Z. Tan, Ernest (2024). "Generalized Rényi entropy accumulation theorem and generalized quantum probability estimation". Physical Review X. 15 (4): 041013. arXiv:2405.05912. Bibcode:2025PhRvX..15d1013A. doi:10.1103/pgrn-mz9j.
  19. ↑ Chung, Rebecca R. B.; Ng, Nelly H. Y.; Cai, Yu (14 July 2025). "Generalized numerical framework for improved finite-sized key rates with Rényi entropy". Physical Review A. 112 (1) 012612. arXiv:2502.02319. Bibcode:2025PhRvA.112a2612C. doi:10.1103/tyts-8v8j.
  20. ↑ Leone, L.; Oliviero, S. F. E.; Hamma, A. (2022). "Stabilizer Rényi Entropy". Physical Review Letters. 128 (5) 050402. arXiv:2106.12587. Bibcode:2022PhRvL.128e0402L. doi:10.1103/PhysRevLett.128.050402. S2CID 235670417.
  21. ↑ Hill, M. O. (1973). "Diversity and evenness: a unifying notation and its consequences". Ecology. 54 (2): 427–432. doi:10.2307/1934352.

References