Categories: Cryptography.

Rényi entropy

In information theory, the Rényi entropy is a measure (or family of measures) of the “suprise” or “information” contained in a random variable \(X\). It is defined as follows:

\[\begin{aligned} \boxed{ H_\alpha(X) = \frac{1}{1 - \alpha} \log\!\bigg( \sum_{i = 1}^N p_i^\alpha \bigg) } \end{aligned}\]

Where \(\alpha \ge 0\) is a free parameter. The logarithm is usually base-2, but variations exist.

The case \(\alpha = 0\) is known as the Hartley entropy or max-entropy, and quantifies the “surprise” of an event from \(X\), if \(X\) is uniformly distributed:

\[\begin{aligned} \boxed{ H_0(X) = \log N } \end{aligned}\]

Where \(N\) is the cardinality of \(X\); the number of different possible events. The most famous case, however, is \(\alpha = 1\). Since \(H_\alpha\) is problematic for \(\alpha \to 1\), we must take the limit:

\[\begin{aligned} H_1(X) = \lim_{\alpha \to 1} H_\alpha(X) = \lim_{\alpha \to 1} \frac{\log\!\left( \sum_i p_i^\alpha \right)}{1 - \alpha} \end{aligned}\]

We then apply L’Hôpital’s rule to evaluate this limit, and use the fact that all \(p_i\) sum to \(1\):

\[\begin{aligned} H_1(X) = \lim_{\alpha \to 1} \frac{\dv{\alpha} \log\!\left( \sum_i p_i^\alpha \right)}{\dv{\alpha} (1 - \alpha)} = \lim_{\alpha \to 1} \frac{\sum_i p_i^\alpha \log p_i}{- \sum_i p_i^\alpha} = - \sum_{i = 1}^N p_i \log p_i \end{aligned}\]

This quantity is the Shannon entropy, which is the most general measure of “surprise”:

\[\begin{aligned} \boxed{ H_1(X) = \lim_{\alpha \to 1} H_\alpha(X) = - \sum_{i = 1}^N p_i \log p_i } \end{aligned}\]

Next, for \(\alpha = 2\), we get the collision entropy, which describes the surprise of two independent and identically distributed variables \(X\) and \(Y\) yielding the same event:

\[\begin{aligned} \boxed{ H_2(X) = - \log\!\bigg( \sum_{i = 1}^N p_i^2 \bigg) = - \log P(X = Y) } \end{aligned}\]

Finally, in the limit \(\alpha \to \infty\), the largest probability dominates the sum, leading to the definition of the min-entropy \(H_\infty\), describing the surprise of the most likely event:

\[\begin{aligned} \boxed{ H_\infty(X) = \lim_{\alpha \to \infty} H_\alpha(x) = - \log\!\big( \max_{i} p_i \big) } \end{aligned}\]

It is straightforward to convince yourself that these entropies are ordered in the following way:

\[\begin{aligned} H_0 \ge H_1 \ge H_2 \ge H_\infty \end{aligned}\]

In other words, from left to right, they go from permissive to conservative, roughly speaking.

References

  1. P.A. Bromiley, N.A. Thacker, E. Bouhova-Thacker, Shannon entropy, Rényi entropy, and information, 2010, University of Manchester.
  2. J.B. Brask, Quantum information: lecture notes, 2021, unpublished.

© "Prefetch". Licensed under CC BY-SA 4.0.
uses