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.

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.