Desigualtat de Gibbs

En teoria de la informació, la desigualtat de Gibbs és una declaració sobre l'entropia de la informació d'una distribució de probabilitat discreta. Moltes altres cotes en l'entropia de les distribucions de probabilitat deriven de la desigualtat de Gibbs, inclosa la desigualtat de Fano. Va ser presentada per primer cop per J. Willard Gibbs en el segle XIX.

Desigualtat de Gibbs

Sigui

P=\{p_{1},\ldots ,p_{n}\}

una distribució de probabilitat discreta. Llavors per qualsevol altra distribució de probabilitat

Q=\{q_{1},\ldots ,q_{n}\}

La desigualtat següent entre quant_itats positives (des de pi i qi és entre zero i un) controls:^[1]^:68

-\sum _{i=1}^{n}p_{i}\log p_{i}\leq -\sum _{i=1}^{n}p_{i}\log q_{i}

amb igualtat si i només si

p_{i}=q_{i}

per tot i. En paraules, l'entropia de Shannon d'una distribució P és menor o igual a la seva entropia creuada amb qualsevol altra distribució Q.

La diferència entre dues quantitats és la divergència de Kullback-Leibler o l'entropia relativa, així doncs també es pot escriure la desigualtat com:^[2]^:34

D_{\mathrm {KL} }(P\|Q)\equiv \sum _{i=1}^{n}p_{i}\log {\frac {p_{i}}{q_{i}}}\geq 0.

Noti's que l'ús de logaritmes de base 2 és opcional i que permet referir-se a la quantitat en cada costat de la desigualtat com la quantitat d'informació en bits.

Demostració

Per simplicitat, s'utilitza el logaritme natural (ln), ja que

\log a={\frac {\ln a}{\ln 2}},

El logaritme en particular que s'utilitzi només escala la relació.

Sigui $I$ el conjunt de tots els índexs $i$ pels quals p_i és diferent a zero. Llavors, com que $\ln x\leq x-1$ per tot x > 0, amb igualtat si i només si x=1, es té:

-\sum _{i\in I}p_{i}\ln {\frac {q_{i}}{p_{i}}}\geq -\sum _{i\in I}p_{i}\left({\frac {q_{i}}{p_{i}}}-1\right)

=-\sum _{i\in I}q_{i}+\sum _{i\in I}p_{i}=-\sum _{i\in I}q_{i}+1\geq 0

L'última desigultat és una conseqüència del fet que p_i i q_i formen part d'una distribució de probabilitat. En particular, la suma de tots els valors diferents de zero és 1. Alguns termes no-zeros q_i, tanmateix, poden haver estat exclosos ja que la tria d'índexs depèn dels termes p_i diferents a zero. Per tant, la suma dels q_i pot ser inferior a 1.

Fins aquí, en el conjunt d'índexs $I$ , es té:

-\sum _{i\in I}p_{i}\ln {\frac {q_{i}}{p_{i}}}\geq 0

,

o equivalentment

-\sum _{i\in I}p_{i}\ln q_{i}\geq -\sum _{i\in I}p_{i}\ln p_{i}

.

Tots dos sumatoris poden ser estesos a tots els índexs $i=1,\ldots ,n$ , és a dir, incloent $p_{i}=0$ , recordant que l'expressió $p\ln p$ tendeix a 0 a mesura que $p$ tendeix a 0, i $(-\ln q)$ tendeix a $\infty$ a mesura que $q$ tendeix a 0. S'arriba a

$-\sum _{i=1}^{n}p_{i}\ln q_{i}\geq -\sum _{i=1}^{n}p_{i}\ln p_{i}$

Per tal que hi hagi igualtat, cal que

${\frac {q_{i}}{p_{i}}}=1$ per tot $i\in I$ perquè apliqui l'igualtat $\ln {\frac {q_{i}}{p_{i}}}={\frac {q_{i}}{p_{i}}}-1$ ,
i $\sum _{i\in I}q_{i}=1$ que significa que $q_{i}=0$ si $i\notin I$ , és a dir, $q_{i}=0$ si $p_{i}=0$ .

Això pot passar si i només si $p_{i}=q_{i}$ per $i=1,\ldots ,n$ .

Demostracions alternatives

Alternativament, el resultat pot ser demostrat usant la desigualtat de Jensen, la desigualtat de la suma de logaritmes, o el fet que la divergència de Kullback-Leibler és una forma de divergència de Bregman. A continuació es mostra una demostració basada en la desigualtat de Jensen:

Com que el logaritme és una funció còncava, es té que:

\sum _{i}p_{i}\log {\frac {q_{i}}{p_{i}}}\leq \log \sum _{i}p_{i}{\frac {q_{i}}{p_{i}}}=\log \sum _{i}q_{i}\leq 0

On la primera desigualtat és deguda a la desigualtat de Jensen, i la darrera igualtat és deguda a la mateixa raó que es dona en la demostració principal, més amunt.

A més, com que $\log$ és estrictament còncava, per la condició d'igualtat de la desigualtat de Jensen es té igualtat com

{\frac {q_{1}}{p_{1}}}={\frac {q_{2}}{p_{2}}}=\cdots ={\frac {q_{n}}{p_{n}}}

i

\sum _{i}q_{i}=1

Suposi's que aquest ràtio és $\sigma$ , llavors es té que

1=\sum _{i}q_{i}=\sum _{i}\sigma p_{i}=\sigma

On s'ha usat el fet que $p,q$ són distribucions de probabilitat. Per tant, la igualtat es dona quan $p=q$ .

Corol·lari

L'entropia de $P$ és fitada per:^[1]^:68

H(p_{1},\ldots ,p_{n})\leq \log n.

La demostració és trivial - agafi's $q_{i}=1/n$ per tot i.

Vegeu també

Entropia d'informació

Referències

↑ ^1,0 ^1,1 Pierre Bremaud. An Introduction to Probabilistic Modeling. Springer Science & Business Media, 6 December 2012. ISBN 978-1-4612-1046-7.
↑ David J. C. MacKay. Information Theory, Inference and Learning Algorithms. Cambridge University Press, 2003. ISBN 978-0-521-64298-9.

[Bremaud2012-1] 1,0 ^1,1 Pierre Bremaud. An Introduction to Probabilistic Modeling. Springer Science & Business Media, 6 December 2012. ISBN 978-1-4612-1046-7.

[MacKay2003-2] David J. C. MacKay. Information Theory, Inference and Learning Algorithms. Cambridge University Press, 2003. ISBN 978-0-521-64298-9.

[1]

[2]