---
title: "Rényi entropy"
sort_title: "Renyi entropy" # sic
date: 2021-04-11
categories:
- Cryptography
layout: "concept"
---

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{\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":

$$\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](https://www.researchgate.net/publication/253537416_Shannon_Entropy_Renyi_Entropy_and_Information),
    2010, University of Manchester.
2.  J.B. Brask,
    *Quantum information: lecture notes*,
    2021, unpublished.