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 $a_{1},\ldots ,a_{n}$ et $b_{1},\ldots ,b_{n}$ des réels strictement positifs, avec $a=\sum _{i=1}^{n}a_{i}$ et $b=\sum _{i=1}^{n}b_{i}$, alors :

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

avec égalité si et seulement si $\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 $c$ telle que $\forall i\in \{1,...,n\},a_{i}=c~b_{i}$.

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

Preuve

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

${\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 ${\frac {b_{i}}{b}}\geq 0$, $\sum _{i=1}^{n}{\frac {b_{i}}{b}}=1$ et $f$ est une fonction convexe.

Généralisations

Cette inégalité reste valide pour $n=\infty$, puisque $a<\infty$ et $b<\infty$.^{[citation nécessaire]} La preuve ci-dessus reste vraie pour toute fonction $g$ telle que $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. Une preuve utilise l'inégalité log-somme.

Preuve

Soient $P=(p_{i})_{i\in \mathbb {N} }$ et $Q=(q_{i})_{i\in \mathbb {N} }$ des fonctions de masses. Dans l'inégalité log-somme, on change $n=\infty$, $a_{i}=p_{i}$ et $b_{i}=q_{i}$ pour obtenir $\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 $\forall i\in \{1,...,n\},p_{i}=q_{i}$ (puisque les sommes des $P$ et $Q$ valent 1).

Cette inégalité peut aussi prouver la convexité de la divergence de Kullback-Leibler.

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).

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)