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.

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

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

Le cas ${\displaystyle \alpha =0}$ donne :

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

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

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

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

Cette expression correspond à l'entropie de Shannon.

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

${\displaystyle 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.

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

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

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

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

${\displaystyle {\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 {p_{i}}{q_{i}}})\\&=-{\frac {1}{1-\alpha ^{2}}}D_{KL}(Q||P)\end{aligned}}}$

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

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

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

${\displaystyle {\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 à ${\displaystyle \mathbb {E} [x^{c}]}$, en notant ${\displaystyle c={\frac {\beta -1}{\alpha -1}}}$ :

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

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

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

De plus, on remarque que ${\displaystyle H_{2}\leq 2H_{\infty }}$ puisque ${\displaystyle 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 }}$.

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

${\displaystyle 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 ${\displaystyle D_{1}(P\|Q)}$existe et correspond à la Divergence de Kullback-Leibler.

• Entropie de Shannon

• (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])

• Portail des probabilités et de la statistique