La desigualdad de Gibbs - Gibbs' inequality

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

La desigualdad de Gibbs

Suponer que

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

es una distribución de probabilidad . Luego, para cualquier otra distribución de probabilidad

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

la siguiente desigualdad entre cantidades positivas (ya que p _i y q _i están entre cero y uno) se cumple:

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

con igualdad si y solo si

${\ Displaystyle p_ {i} = q_ {i}}$

por todo i . Dicho en palabras, la entropía de información de una distribución P es menor o igual que su entropía cruzada con cualquier otra distribución Q.

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

${\ 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 en 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, probamos el enunciado usando el logaritmo natural (ln), ya que

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

el logaritmo particular que elegimos solo escala la relación.

Dejar que denotan el conjunto de todos para los que p _i es distinto de cero. Entonces, dado que 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 una consecuencia de que p _i y q _i son parte de una distribución de probabilidad. Específicamente, la suma de todos los valores distintos de cero es 1. Sin embargo, algunos q _i distintos de cero pueden haberse excluido ya que la elección de índices está condicionada a que p _i sea ​​distinto de cero. Por tanto, la suma de q _i puede ser menor que 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 equivalente

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

Ambas sumas pueden extenderse a todos , es decir, incluidos , 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, necesitamos

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 lo 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 probar alternativamente utilizando la desigualdad de Jensen, la desigualdad de la suma logarítmica o el hecho de que la divergencia de Kullback-Leibler es una forma de divergencia de Bregman . A continuación damos una prueba basada en la desigualdad de Jensen:

Debido a que 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} \ leq 0}$

Donde la primera desigualdad se debe a la desigualdad de Jensen, y la última igualdad se debe a la misma razón dada en la prueba anterior.

Además, dado que es estrictamente cóncavo, 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 razón es , entonces tenemos que ${\ Displaystyle \ sigma}$

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

Donde usamos el hecho de que son distribuciones de probabilidad. Por tanto la igualdad ocurre cuando . ${\ Displaystyle p, q}$${\ Displaystyle p = q}$

Corolario

La entropía de está limitada por: ${\ 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}$

Ver también

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

Referencias