Desigualdad de Pinsker

En teoría de la información , la desigualdad de Pinsker , llamada así por su inventor Mark Semenovich Pinsker , es una desigualdad que limita la distancia de variación total (o distancia estadística) en términos de la divergencia de Kullback-Leibler . La desigualdad es estricta hasta factores constantes. ^[1]

Declaración formal

La desigualdad de Pinsker establece que, si y son dos distribuciones de probabilidad en un espacio medible , entonces ${\displaystyle P}$ ${\displaystyle Q}$ ${\displaystyle (X,\Sigma )}$

${\displaystyle \delta (P,Q)\leq {\sqrt {{\frac {1}{2}}D_{\mathrm {KL} }(P\parallel Q)}},}$

dónde

${\displaystyle \delta (P,Q)=\sup {\bigl \{}|P(A)-Q(A)|\mid \quad A\in \Sigma {\text{ is a measurable event}}{\bigr \}}}$

es la distancia de variación total (o distancia estadística) entre y y ${\displaystyle P}$ ${\displaystyle Q}$

${\displaystyle D_{\mathrm {KL} }(P\parallel Q)=\operatorname {E} _{P}\left(\log {\frac {\mathrm {d} P}{\mathrm {d} Q}}\right)=\int _{X}\left(\log {\frac {\mathrm {d} P}{\mathrm {d} Q}}\right)\,\mathrm {d} P}$

es la divergencia de Kullback–Leibler en nats . Cuando el espacio muestral es un conjunto finito, la divergencia de Kullback–Leibler está dada por ${\displaystyle X}$

${\displaystyle D_{\mathrm {KL} }(P\parallel Q)=\sum _{i\in X}\left(\log {\frac {P(i)}{Q(i)}}\right)P(i)\!}$

Nótese que en términos de la norma de variación total de la medida con signo , la desigualdad de Pinsker difiere de la dada anteriormente en un factor de dos: ${\displaystyle \|P-Q\|}$ ${\displaystyle P-Q}$

${\displaystyle \|P-Q\|\leq {\sqrt {2D_{\mathrm {KL} }(P\parallel Q)}}.}$

Una prueba de la desigualdad de Pinsker utiliza la desigualdad de partición para f -divergencias .

Versión alternativa

Nótese que la expresión de la desigualdad de Pinsker depende de qué base de logaritmo se utiliza en la definición de divergencia KL. se define utilizando (logaritmo en base ), mientras que se define típicamente con (logaritmo en base 2). Entonces, ${\displaystyle D_{KL}}$ ${\displaystyle \ln }$ ${\displaystyle e}$ ${\displaystyle D}$ ${\displaystyle \log _{2}}$

${\displaystyle D(P\parallel Q)={\frac {D_{KL}(P\parallel Q)}{\ln 2}}.}$

Dados los comentarios anteriores, existe una declaración alternativa de la desigualdad de Pinsker en alguna literatura que relaciona la divergencia de información con la distancia de variación:

${\displaystyle D(P\parallel Q)={\frac {D_{KL}(P\parallel Q)}{\ln 2}}\geq {\frac {1}{2\ln 2}}V^{2}(p,q),}$

es decir,

${\displaystyle {\sqrt {\frac {D_{KL}(P\parallel Q)}{2}}}\geq {\frac {V(p,q)}{2}},}$

En el cual

${\displaystyle V(p,q)=\sum _{x\in {\mathcal {X}}}|p(x)-q(x)|}$

es la distancia de variación (no normalizada) entre dos funciones de densidad de probabilidad y en el mismo alfabeto . ^[2] ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle {\mathcal {X}}}$

Esta forma de la desigualdad de Pinsker muestra que "convergencia en divergencia" es una noción más fuerte que "convergencia en distancia de variación".

John Pollard muestra una prueba sencilla al dejar : ${\displaystyle r(x)=P(x)/Q(x)-1\geq -1}$

${\displaystyle {\begin{aligned}D_{KL}(P\parallel Q)&=E_{Q}[(1+r(x))\log(1+r(x))-r(x)]\\&\geq {\frac {1}{2}}E_{Q}\left[{\frac {r(x)^{2}}{1+r(x)/3}}\right]\\&\geq {\frac {1}{2}}{\frac {E_{Q}[|r(x)|]^{2}}{E_{Q}[1+r(x)/3]}}&{\text{(from Titu's lemma)}}\\&={\frac {1}{2}}E_{Q}[|r(x)|]^{2}&{\text{(As }}E_{Q}[1+r(x)/3]=1{\text{ )}}\\&={\frac {1}{2}}V(p,q)^{2}.\end{aligned}}}$

Aquí el lema de Titu también se conoce como desigualdad de Sedrakyan .

Obsérvese que el límite inferior de la desigualdad de Pinsker es nulo para cualquier distribución donde , ya que la distancia de variación total es como máximo . Para tales distribuciones, se puede utilizar un límite alternativo, debido a Bretagnolle y Huber ^[3] (véase también Tsybakov ^[4] ): ${\displaystyle D_{\mathrm {KL} }(P\parallel Q)>2}$ ${\displaystyle 1}$

${\displaystyle \delta (P,Q)\leq {\sqrt {1-e^{-D_{\mathrm {KL} }(P\parallel Q)}}}.}$

Historia

Pinsker fue el primero en demostrar la desigualdad con una constante mayor. La desigualdad en la forma anterior fue demostrada independientemente por Kullback , Csiszár y Kemperman . ^[5]

Problema inverso

No puede cumplirse una inversa precisa de la desigualdad: para cada , existen distribuciones con pero . Un ejemplo sencillo lo da el espacio de dos puntos con y . ^[6] ${\displaystyle \varepsilon >0}$ ${\displaystyle P_{\varepsilon },Q}$ ${\displaystyle \delta (P_{\varepsilon },Q)\leq \varepsilon }$ ${\displaystyle D_{\mathrm {KL} }(P_{\varepsilon }\parallel Q)=\infty }$ ${\displaystyle \{0,1\}}$ ${\displaystyle Q(0)=0,Q(1)=1}$ ${\displaystyle P_{\varepsilon }(0)=\varepsilon ,P_{\varepsilon }(1)=1-\varepsilon }$

Sin embargo, una desigualdad inversa se cumple en espacios finitos con una constante que depende de . ^[7] Más específicamente, se puede demostrar que con la definición que tenemos para cualquier medida que sea absolutamente continua a ${\displaystyle X}$ ${\displaystyle Q}$ ${\displaystyle \alpha _{Q}:=\min _{x\in X:Q(x)>0}Q(x)}$ ${\displaystyle P}$ ${\displaystyle Q}$

${\displaystyle {\frac {1}{2}}D_{\mathrm {KL} }(P\parallel Q)\leq {\frac {1}{\alpha _{Q}}}\delta (P,Q)^{2}.}$

En consecuencia, si tiene soporte completo (es decir, para todos ), entonces ${\displaystyle Q}$ ${\displaystyle Q(x)>0}$ ${\displaystyle x\in X}$

${\displaystyle \delta (P,Q)^{2}\leq {\frac {1}{2}}D(P\parallel Q)\leq {\frac {1}{\alpha _{Q}}}\delta (P,Q)^{2}.}$

Referencias

1. Csiszár, Imre; Körner, János (2011). Teoría de la información: teoremas de codificación para sistemas discretos sin memoria. Prensa de la Universidad de Cambridge. pag. 44.ISBN​ 9781139499989.
2. Raymond W., Yeung (2008). Teoría de la información y codificación de redes . Hong Kong: Springer. pág. 26. ISBN. 978-0-387-79233-0.
3. Bretagnolle, J.; Huber, C, Estimation des densités: risque minimax , Séminaire de Probabilités, XII (Univ. Estrasburgo, Estrasburgo, 1976/1977), págs. 342–363, Lecture Notes in Math., 649, Springer, Berlín, 1978, Lema 2.1 (Francés).
4. Tsybakov, Alexandre B., Introducción a la estimación no paramétrica , Revisado y ampliado a partir del original en francés de 2004. Traducido por Vladimir Zaiats. Springer Series in Statistics. Springer, Nueva York, 2009. xii+214 pp. ISBN 978-0-387-79051-0 , Ecuación 2.25. 
5. Tsybakov, Alexandre (2009). Introducción a la estimación no paramétrica . Springer. pág. 132. ISBN. 9780387790527.
6. La divergencia se vuelve infinita siempre que una de las dos distribuciones asigna probabilidad cero a un evento mientras que la otra le asigna una probabilidad distinta de cero (sin importar cuán pequeña sea); véase, por ejemplo, Basu, Mitra; Ho, Tin Kam (2006). Complejidad de datos en el reconocimiento de patrones. Springer. p. 161. ISBN. 9781846281723..
7. Véase el Lema 4.1 en Götze, Friedrich; Sambale, Holger; Sinulis, Arthur (2019). "Concentración de orden superior para funciones de variables aleatorias débilmente dependientes". Revista electrónica de probabilidad . 24 . arXiv : 1801.06348 . doi :10.1214/19-EJP338. S2CID  52200238.

Lectura adicional

• Thomas M. Cover y Joy A. Thomas: Elementos de la teoría de la información , 2.ª edición, Willey-Interscience, 2006
• Nicolo Cesa-Bianchi y Gábor Lugosi: Predicción, aprendizaje y juegos , Cambridge University Press, 2006