Inégalité log somme

L'inégalité log somme (ou log sum inequality) est fréquemment utilisée en théorie de l'information.

Énoncé

Soient ${\displaystyle a_{1},\ldots ,a_{n}}$ et ${\displaystyle b_{1},\ldots ,b_{n}}$ des réels strictement positifs, avec ${\displaystyle a=\sum _{i=1}^{n}a_{i}}$ et ${\displaystyle b=\sum _{i=1}^{n}b_{i}}$, alors :

${\displaystyle \sum _{i=1}^{n}a_{i}\log {\frac {a_{i}}{b_{i}}}\geq a\log {\frac {a}{b}},}$

avec égalité si et seulement si ${\displaystyle \forall i,j\in \{1,...,n\}^{2},{\frac {a_{i}}{b_{i}}}={\frac {a_{j}}{b_{j}}}}$, c'est-à-dire qu'il existe une constante ${\displaystyle c}$ telle que ${\displaystyle \forall i\in \{1,...,n\},a_{i}=c~b_{i}}$.^[1]

(On prendra ${\displaystyle a_{i}\log {\frac {a_{i}}{b_{i}}}=0}$ si ${\displaystyle a_{i}=0}$ et ${\displaystyle a_{i}\log {\frac {a_{i}}{b_{i}}}=\infty }$ si ${\displaystyle a_{i}>0}$ et ${\displaystyle b_{i}=0}$. Ces valeurs sont obtenues par prolongement par continuité en ${\displaystyle 0}$.)^[1]

Preuve

En posant ${\displaystyle f(x)=x\log x}$, nous avons

${\displaystyle {\begin{aligned}\sum _{i=1}^{n}a_{i}\log {\frac {a_{i}}{b_{i}}}&{}=\sum _{i=1}^{n}b_{i}f\left({\frac {a_{i}}{b_{i}}}\right)=b\sum _{i=1}^{n}{\frac {b_{i}}{b}}f\left({\frac {a_{i}}{b_{i}}}\right)\\&{}\geq bf\left(\sum _{i=1}^{n}{\frac {b_{i}}{b}}{\frac {a_{i}}{b_{i}}}\right)=bf\left({\frac {1}{b}}\sum _{i=1}^{n}a_{i}\right)=bf\left({\frac {a}{b}}\right)\\&{}=a\log {\frac {a}{b}},\end{aligned}}}$

où l'inégalité vient de l'inégalité de Jensen puisque ${\displaystyle {\frac {b_{i}}{b}}\geq 0}$, ${\displaystyle \sum _{i=1}^{n}{\frac {b_{i}}{b}}=1}$ et ${\displaystyle f}$ est une fonction convexe.^[1]

Généralisations

Cette inégalité reste valide pour ${\displaystyle n=\infty }$, puisque ${\displaystyle a<\infty }$ et ${\displaystyle b<\infty }$.^{[citation nécessaire]} La preuve ci-dessus reste vraie pour toute fonction ${\displaystyle g}$ telle que ${\displaystyle f(x)=xg(x)}$ soit convexe, comme toute fonction croissante continue. La généralisation aux fonctions croissantes autres que le logarithme est donné dans Csiszár, 2004.

Applications

L'inégalité log-somme peut être utilisée pour prouver des inégalités en théorie de l'information. L'inégalité de Gibbs affirme que la divergence de Kullback-Leibler est positive, et égale à zéro si ses arguments sont égaux.^[2] Une preuve utilise l'inégalité log-somme.

Preuve^[1]

Soient ${\displaystyle P=(p_{i})_{i\in \mathbb {N} }}$ et ${\displaystyle Q=(q_{i})_{i\in \mathbb {N} }}$ des fonctions de masses. Dans l'inégalité log-somme, on change ${\displaystyle n=\infty }$, ${\displaystyle a_{i}=p_{i}}$ et ${\displaystyle b_{i}=q_{i}}$ pour obtenir

${\displaystyle \mathbb {D} _{\mathrm {KL} }(P\|Q)\equiv \sum _{i}p_{i}\log _{2}{\frac {p_{i}}{q_{i}}}\geq 1\log {\frac {1}{1}}=0}$

avec égalité si et seulement si ${\displaystyle \forall i\in \{1,...,n\},p_{i}=q_{i}}$ (puisque les sommes des ${\displaystyle P}$ et ${\displaystyle Q}$ valent 1).

Cette inégalité peut aussi prouver la convexité de la divergence de Kullback-Leibler. ^[3]

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Log sum inequality » (voir la liste des auteurs).

1. Cover et Thomas (1991), p. 29.
2. MacKay (2003), p. 34.
3. Cover et Thomas (1991), p. 30.

Bibliographie

• Thomas M. Cover et Joy A. Thomas, Elements of Information Theory, Hoboken (New Jersey), Wiley, 1991 (ISBN 978-0-471-24195-9)
• I. Csiszár et P. Shields, « Information Theory and Statistics: A Tutorial », Foundations and Trends in Communications and Information Theory, vol. 1, n^o 4,‎ 2004, p. 417–528 (DOI 10.1561/0100000004, lire en ligne, consulté le 14 juin 2009)
• T.S. Han, K. Kobayashi, Mathematics of information and coding. American Mathematical Society, 2001. (ISBN 0-8218-0534-7).
• Information Theory course materials, Utah State University [1]. Retrieved on 2009-06-14.
• David J.C. MacKay, Information Theory, Inference, and Learning Algorithms, Cambridge University Press, 2003 (ISBN 0-521-64298-1, lire en ligne)