Entropie de Rényi

L'entropie de Rényi, due à Alfréd Rényi, est une fonction mathématique qui correspond à la quantité d'information contenue dans la probabilité de collision d'une variable aléatoire.

Définition

Étant donnés une variable aléatoire discrète $X$ à $n$ valeurs possibles $(x_{1},x_{2},\ldots x_{n})$, ainsi qu'un paramètre réel $\alpha$ strictement positif et différent de 1, l' entropie de Rényi d'ordre $\alpha$ de $X$ est définie par la formule :

$H_{\alpha }(X)={\frac {1}{1-\alpha }}\log \sum _{i=1}^{n}P(X=x_{i})^{\alpha }$

Cas particuliers

L'entropie de Rényi généralise d'autres acceptions de la notion d'entropie, qui correspondent chacune à des valeurs particulières de $\alpha$.

Entropie de Hartley

Le cas $\alpha =0$ donne :

$H_{0}(X)=\log n=\log |X|$

ce qui correspond au logarithme du cardinal de $X$, qui correspond à l'entropie de Hartley.

Entropie de Shannon

D'après la règle de L'Hôpital, on peut trouver une limite à $H_{\alpha }(X)$ quand $\alpha$ tend vers 1 :

$\lim _{\alpha \rightarrow 1}H_{\alpha }(X)=-\sum _{i=1}^{n}p_{i}\log p_{i}$

Cette expression correspond à l'entropie de Shannon.

Entropie de collision

Dans le cas où $\alpha =2$, on trouve l'entropie dite de collision, appelée parfois simplement « entropie de Rényi » :

$H_{2}(X)=-\log \sum _{i=1}^{n}p_{i}^{2}=-\log P(X=Y)$

où Y est une variable aléatoire indépendante et identiquement distribuée par rapport à X.

Entropie min

En faisant tendre $\alpha$ vers l'infini, on trouve l'entropie min :

$H_{\infty }(X)=-\log \sup _{i=1..n}p_{i}$

Propriétés

Décroissance selon α

$H_{\alpha }$ est une fonction décroissante de $\alpha$.

Preuve

Soit $P=\{p_{1},p_{2},...,p_{n}\}$ une distribution de probabilité

${\begin{aligned}{\frac {dH_{\alpha }}{d\alpha }}&={\frac {d}{d\alpha }}({\frac {1}{1-\alpha }}\log \sum _{i=1}^{n}P(X=x_{i})^{\alpha })\\&={\frac {1}{1-\alpha ^{2}}}\sum _{i=1}^{n}q_{i}\log({\frac {q_{i}}{p_{i}}})\\&=-{\frac {1}{1-\alpha ^{2}}}D_{KL}(P||Q)\end{aligned}}$

avec $Q$ la distribution de probabilité des $q_{i}={\frac {p_{i}^{\alpha }}{\sum _{j=1}^{n}p_{j}^{\alpha }}}$ et $D_{KL}$ la Divergence de Kullback-Leibler de $Q$ par rapport $P$.

Puisque cette divergence est positive, la dérivée de l'entropie de Rényi en devient négative et donc $H_{\alpha }$ est bien décroissante en $\alpha$.

Preuve alternative

Soit $P=\{p_{1},p_{2},...,p_{n}\}$ une distribution de probabilité,

${\begin{aligned}H_{\alpha }(X)&={\frac {1}{1-\alpha }}\log \sum _{i=1}^{n}P_{X}(x_{i})^{\alpha }\\&=-\log \mathbb {E} [P_{X}(X)^{\alpha -1}]^{\frac {1}{\alpha -1}}\\&=-\log \mathbb {E} [P_{X}(X)^{\alpha -1}]^{{\frac {\beta -1}{\alpha -1}}{\frac {1}{\beta -1}}}\\&\geq -\log \mathbb {E} [P_{X}(X)^{{\alpha -1}{\frac {\beta -1}{\alpha -1}}}]^{\frac {1}{\beta -1}}\\&=-\log \mathbb {E} [P_{X}(X)^{\beta -1}]^{\frac {1}{\beta -1}}\\&={\frac {1}{1-\beta }}\log \sum _{i=1}^{n}P_{X}(x_{i})^{\beta }\\&=H_{\beta }(X)\end{aligned}}$

L'inégalité provient de l'Inégalité de Jensen appliquée dans les cas suivants à $\mathbb {E} [x^{c}]$, en notant $c={\frac {\beta -1}{\alpha -1}}$ :

• Si, $c>1$ et donc $x^{c}$ est convexe et ${\frac {1}{\beta -1}}>0$.
• Si, $c<0$ donc $x^{c}$ est convexe et ${\frac {1}{\beta -1}}>0$.
• Si, $c>0$ donc $x^{c}$ est concave ${\frac {1}{\beta -1}}<0$.
• Si $(\alpha =1)\lor (\beta =1)$l'application de l'inégalité est immédiate.

Ce qui donne la croissance de $\alpha \rightarrow H_{\alpha }$.

Relations entre les entropies de différents ordres

L'entropie de Rényi est donc une fonction décroissante de son ordre.

De plus, on remarque que $H_{2}\leq 2H_{\infty }$ puisque $H_{2}=-\log(\sum _{i=1}^{n}p_{i}^{2})\leq -\log(\sup _{i}(p_{i}^{2}))=-2\log(\sup _{i}(p_{i}))=2H_{\infty }$.

Divergence de Rényi

Pour deux distributions de probabilités $P=\{p_{1},p_{2},...,p_{n}\}$ et $Q=\{q_{1},q_{2},...,q_{n}\}$, la divergence de Rényi de $P$ selon $Q$ est définie comme :

$D_{\alpha }(P\|Q)={\frac {1}{\alpha -1}}\log {\Bigg (}\sum _{i=1}^{n}{\frac {p_{i}^{\alpha }}{q_{i}^{\alpha -1}}}{\Bigg )}$

La limite $D_{1}(P\|Q)$existe et correspond à la Divergence de Kullback-Leibler.

Voir aussi

Article connexe

• Entropie de Shannon

Bibliographie

• (en) A. Rényi, « On measures of entropy and information », dans Proc. 4th Berkeley Symposium on Mathematical Statistics and Probability', vol. 1, 1960, p. 547-561.
• (en) Christian Cachin, Entropy Measures and Unconditional Security in Cryptography, 1997 (lire en ligne [PDF])