Desigualdad de Gibbs

Afirmación sobre la teoría de la información

Josiah Willard Gibbs

En teoría de la información , la desigualdad de Gibbs es una afirmación sobre la entropía de la información de una distribución de probabilidad discreta . Varios otros límites de la entropía de las distribuciones de probabilidad se derivan de la desigualdad de Gibbs, incluida la desigualdad de Fano . Fue presentada por primera vez por J. Willard Gibbs en el siglo XIX.

Desigualdad de Gibbs

Supongamos que y son distribuciones de probabilidad discretas . Entonces ${\displaystyle P=\{p_{1},\ldots ,p_{n}\}}$ ${\displaystyle Q=\{q_{1},\ldots ,q_{n}\}}$

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

con igualdad si y sólo si para . ^{[1] : 68} Dicho en palabras, la entropía de información de una distribución es menor o igual a su entropía cruzada con cualquier otra distribución . ${\displaystyle p_{i}=q_{i}}$ ${\displaystyle i=1,\dots n}$ ${\displaystyle P}$ ${\displaystyle Q}$

La diferencia entre las dos cantidades es la divergencia de Kullback-Leibler o entropía relativa, por lo que la desigualdad también se puede escribir: ^{[2] : 34}

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

Tenga en cuenta que el uso de logaritmos de base 2 es opcional y permite referirse a la cantidad en cada lado de la desigualdad como una " sorpresa promedio " medida en bits .

Prueba

Para simplificar, demostramos la afirmación utilizando el logaritmo natural, denotado por ln , ya que

${\displaystyle \log _{b}a={\frac {\ln a}{\ln b}},}$

Por lo tanto, el logaritmo base particular b > 1 que elegimos solo escala la relación por el factor 1 / ln b .

Sea el conjunto de todos aquellos para los que p _i es distinto de cero. Entonces, como para todo x > 0 , con igualdad si y solo si x=1 , tenemos: ${\displaystyle I}$ ${\displaystyle i}$ ${\displaystyle \ln x\leq x-1}$

${\displaystyle -\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)}$ ${\displaystyle =-\sum _{i\in I}q_{i}+\sum _{i\in I}p_{i}=-\sum _{i\in I}q_{i}+1\geq 0}$

La última desigualdad es consecuencia de que p _i y q _i formen parte de una distribución de probabilidad. En concreto, la suma de todos los valores distintos de cero es 1. Sin embargo, es posible que se hayan excluido algunos valores q _i distintos de cero, ya que la elección de los índices está condicionada a que p _i sea distinto de cero. Por tanto, la suma de los valores q _i puede ser inferior a 1.

Hasta ahora, sobre el conjunto de índices , tenemos: ${\displaystyle I}$

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

o equivalentemente

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

Ambas sumas se pueden extender a todos los , es decir, incluyendo , recordando que la expresión tiende a 0 cuando tiende a 0, y tiende a cuando tiende a 0. Llegamos a ${\displaystyle i=1,\ldots ,n}$ ${\displaystyle p_{i}=0}$ ${\displaystyle p\ln p}$ ${\displaystyle p}$ ${\displaystyle (-\ln q)}$ ${\displaystyle \infty }$ ${\displaystyle q}$

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

Para que la igualdad se mantenga, es necesario

1. ${\displaystyle {\frac {q_{i}}{p_{i}}}=1}$para todos para que la igualdad se mantenga, ${\displaystyle i\in I}$ ${\displaystyle \ln {\frac {q_{i}}{p_{i}}}={\frac {q_{i}}{p_{i}}}-1}$
2. y que significa si , es decir, si . ${\displaystyle \sum _{i\in I}q_{i}=1}$ ${\displaystyle q_{i}=0}$ ${\displaystyle i\notin I}$ ${\displaystyle q_{i}=0}$ ${\displaystyle p_{i}=0}$

Esto puede suceder si y sólo si para . ${\displaystyle p_{i}=q_{i}}$ ${\displaystyle i=1,\ldots ,n}$

Pruebas alternativas

El resultado se puede demostrar alternativamente utilizando la desigualdad de Jensen , la desigualdad de suma logarítmica o el hecho de que la divergencia de Kullback-Leibler es una forma de divergencia de Bregman .

Demostración mediante la desigualdad de Jensen

Como log es una función cóncava, tenemos que:

${\displaystyle \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}=0}$

donde la primera desigualdad se debe a la desigualdad de Jensen, y al ser una distribución de probabilidad implica la última igualdad. ${\displaystyle q}$

Además, dado que es estrictamente cóncava, por la condición de igualdad de la desigualdad de Jensen obtenemos igualdad cuando ${\displaystyle \log }$

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

y

${\displaystyle \sum _{i}q_{i}=1}$.

Supongamos que esta relación es , entonces tenemos que ${\displaystyle \sigma }$

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

donde utilizamos el hecho de que son distribuciones de probabilidad. Por lo tanto, la igualdad ocurre cuando . ${\displaystyle p,q}$ ${\displaystyle p=q}$

Demostración por divergencia de Bregman

Alternativamente, se puede demostrar notando que para todos , con igualdad mantenida si y solo si . Luego, sumando sobre los estados, tenemos con igualdad mantenida si y solo si . $${\displaystyle q-p-p\ln {\frac {q}{p}}\geq 0}$$ ${\displaystyle p,q>0}$ ${\displaystyle p=q}$ $${\displaystyle \sum _{i}q_{i}-p_{i}-p_{i}\ln {\frac {q_{i}}{p_{i}}}\geq 0}$$ ${\displaystyle p=q}$

Esto se debe a que la divergencia KL es la divergencia de Bregman generada por la función . ${\displaystyle t\mapsto \ln t}$

Corolario

La entropía de está limitada por: ^{[1] : 68} ${\displaystyle P}$

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

La prueba es trivial: simplemente se establece para todo i . ${\displaystyle q_{i}=1/n}$

Véase también

• Entropía de la información
• Divergencia de Bregman
• Desigualdad de suma logarítmica

Referencias

1. Pierre Bremaud (6 de diciembre de 2012). Introducción al modelado probabilístico . Springer Science & Business Media. ISBN 978-1-4612-1046-7.
2. David JC MacKay (25 de septiembre de 2003). Teoría de la información, inferencia y algoritmos de aprendizaje . Cambridge University Press. ISBN 978-0-521-64298-9.