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:

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:

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{\displaystyle \dv{}{\alpha}\log\!\left( \sum_i p_i^\alpha \right)}{\displaystyle \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”:

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:

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:

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

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