Alfred Renyi 1921-1970

The definition of Renyi Divergence

If $P=(P_n)_n$, $Q=(Q_n)_n$ are two discrete probability distributions, and $\alpha \in (0,1) \cup (1, \infty)$, then the Renyi divergence from $P$ to $Q$ is defined by

$$ D_\alpha (P||Q)= \left\{ \begin{array}{ll} \frac{1}{\alpha -1} \log_2 \sum_n P_n^\alpha Q_n^{1-\alpha}, & \begin{array}{l} \alpha \in (0,1) \text{ or } \\(\alpha \in (1, \infty)\text{ and } P\ll Q ) \end{array} \\ \infty & \text{otherwise} \end{array} \right. . $$

The Renyi divergence was invented by Alfred Renyi in 1961 who intended to use it in order to give an information theoretic proof of the Central Limit Theorem. The project was never completed because of his early death in 1970 at the age of 49.

Properties of the Renyi divergence:

• $D_\alpha (P||Q) \geq 0$ for all $\alpha \in (0,1)\cup (1, \infty)$.
• $D_\alpha (P||Q)=0 \Leftrightarrow P=Q$ for all $\alpha \in (0,1)\cup (1, \infty)$.
• $\lim_{\alpha \to 1} D_\alpha (P||Q)= D(P||Q)=\sum_n P_n \log_2 \frac{P_n}{Q_n}$ (the Kullback-Leibler Divergence).
• If $\alpha \leq \beta$ then $D_\alpha (P|| Q) \leq D_\beta (P||Q)$.

An operational meaning of the Renyi divergence:

Uniquely decodable binary codes:

Alphabet $n \in A$

a

b

c

d

Codewords $C(n)$

0

01

011

0111

Lengths $\ell (C(n))$

1

2

3

4

Encoding-decoding process

$$ \text{baadbcb} \xrightarrow[]{\text{encoding}} 01 0 0 0111 01 011 01 \xrightarrow[]{\text{decoding}} \text{baadbcb}. $$

The Kraft-McMillan Inequality

If a code is uniquely decodable, then

$$ \sum_{n \in A} 2^{-\ell (C(n))} \leq 1. $$

If equality occurs in the Kraft-McMillan inequality, then the code is called compact code. Every compact binary code $C$ gives rise to a probability distribution

$$ P=(P_n)_n=(2^{-\ell (C(n))})_n. $$