Vector entrópico

Para una tupla de variables aleatorias${\displaystyle X_{1},X_{2},\ldots ,X_{n}}$, sus entropías satisfacen:

${\displaystyle 1)\quad H(X_{\emptyset })=0}$

${\displaystyle 2)\quad H(X_{I})\leq H(X_{J})}$, para cualquier  ${\displaystyle I\subseteq J\subseteq \{1,\dots ,n\}}$

En particular,${\displaystyle H(X_{I})\geq 0}$, para cualquier ${\displaystyle I\subseteq \{1,\dots ,n\}}$.

La desigualdad de Shannon dice que un vector entrópico es submodular :

${\displaystyle 3)\quad H(X_{I})+H(X_{J})\geq H(X_{I\cup J})+H(X_{I\cap J})}$, para cualquier   ${\displaystyle I,J\subseteq \{1,\dots ,n\}}$

Es equivalente a la desigualdad que establece que la información mutua condicional es no negativa:

${\displaystyle {\begin{aligned}I(X;Y\mid Z)&=H(X\mid Z)-H(X\mid Y,Z)\\&=H(X\mid Z)+H(Y\mid Z)-H(X,Y\mid Z)\\&=H(X,Z)+H(Y,Z)-H(X,Y,Z)-H(Z)\\&\geq 0\end{aligned}}}$

(Para una dirección, observe que la última forma expresa la desigualdad de Shannon para subconjuntos)${\displaystyle X,Z}$y${\displaystyle Y,Z}$de la tupla${\displaystyle X,Y,Z}$; para la otra dirección, sustituir${\displaystyle X=X_{I}}$,${\displaystyle Y=X_{J}}$,${\displaystyle Z=X_{I\cap J}}$).

Muchas desigualdades pueden derivarse como combinaciones lineales de desigualdades de Shannon; se denominan desigualdades de tipo Shannon o desigualdades de información básica de las medidas de información de Shannon. ^{[ 2 ]} El conjunto de vectores que las satisface se denomina${\displaystyle \Gamma _{n}}$; contiene${\displaystyle \Gamma _{n}^{*}}$.

Se ha desarrollado software para automatizar la tarea de demostrar desigualdades de tipo Shannon. ^{[ 3 ] [ 4 ]} Dada una desigualdad, dicho software es capaz de determinar si la desigualdad dada es una desigualdad válida de tipo Shannon (es decir, si contiene el cono${\displaystyle \Gamma _{n}}$).

La cuestión de si las desigualdades de tipo Shannon son las únicas, es decir, si caracterizan completamente la región.${\displaystyle \Gamma _{n}^{*}}$, fue preguntado por primera vez por Te Su Han en 1981 ^{[ 2 ]} y más precisamente por Nicholas Pippenger en 1986. ^{[ 5 ]} No es difícil demostrar que esto es cierto para dos variables, es decir,${\displaystyle \Gamma _{2}^{*}=\Gamma _{2}}$Para tres variables, Zhang y Yeung ^{[ 1 ]} demostraron que${\displaystyle \Gamma _{3}^{*}\neq \Gamma _{3}}$; sin embargo, sigue siendo asintóticamente cierto, lo que significa que el cierre es igual:${\displaystyle {\overline {\Gamma _{3}^{*}}}=\Gamma _{3}}$En 1998, Zhang y Yeung ^{[ 2 ] [ 6 ]} demostraron que${\displaystyle {\overline {\Gamma _{n}^{*}}}\neq \Gamma _{n}}$a pesar de${\displaystyle n\geq 4}$, demostrando que la siguiente desigualdad sobre cuatro variables aleatorias (en términos de información mutua condicional) es verdadera para cualquier vector entrópico, pero no es de tipo Shannon:

${\displaystyle 2I(X_{3};X_{4})\leq I(X_{1};X_{2})+I(X_{1};X_{3},X_{4})+3I(X_{3};X_{4}|X_{1})+I(X_{3};X_{4}|X_{2})}$

Se han encontrado más desigualdades y familias infinitas de desigualdades. ^{[ 7 ] [ 8 ] [ 9 ] [ 10 ]} Estas desigualdades proporcionan límites exteriores para${\displaystyle {\overline {\Gamma _{n}^{*}}}}$mejor que el límite de tipo Shannon${\displaystyle \Gamma _{n}}$En 2007, Matus demostró que ningún conjunto finito de desigualdades lineales es suficiente (para deducir todas como combinaciones lineales), para${\displaystyle n\geq 4}$variables. En otras palabras, la región${\displaystyle {\overline {\Gamma _{4}^{*}}}}$no es poliédrico. ^{[ 11 ]} Si se pueden caracterizar de alguna otra manera (que permita decidir efectivamente si un vector es entrópico o no) sigue siendo un problema abierto .

Se han considerado cuestiones análogas para la entropía de von Neumann en la teoría de la información cuántica . ^{[ 12 ]}

Algunos límites internos de${\displaystyle {\overline {\Gamma _{n}^{*}}}}$También se conocen. Un ejemplo es que${\displaystyle {\overline {\Gamma _{4}^{*}}}}$contiene todos los vectores en${\displaystyle \Gamma _{4}}$que además satisfacen la siguiente desigualdad (y las obtenidas al permutar variables), conocida como la desigualdad de Ingleton para la entropía : ^{[ 13 ]}

${\displaystyle I(X_{1};X_{2})+I(X_{3};X_{4}\mid X_{1})+I(X_{3};X_{4}\mid X_{2})-I(X_{3};X_{4})\geq 0}$^{[ 2 ]}

Consideremos un grupo${\displaystyle G}$y subgrupos${\displaystyle G_{1},G_{2},\dots ,G_{n}}$de${\displaystyle G}$. Dejar${\displaystyle G_{I}}$denotar${\displaystyle \bigcap _{i\in I}G_{i}}$para${\displaystyle I\subseteq \{1,\dots ,n\}}$; este también es un subgrupo de${\displaystyle G}$. Es posible construir una distribución de probabilidad para${\displaystyle n}$variables aleatorias${\displaystyle X_{1},\dots ,X_{n}}$de tal manera que

${\displaystyle H(X_{I})=\log {\frac {|G|}{|G_{I}|}}}$. ^{[ 14 ]}

(La construcción esencialmente toma un elemento${\displaystyle a}$de${\displaystyle G}$uniformemente al azar y deja${\displaystyle X_{i}}$sea ​​la clase lateral correspondiente${\displaystyle aG_{i}}$). Por lo tanto, cualquier desigualdad de la teoría de la información implica una desigualdad de la teoría de grupos. Por ejemplo, la desigualdad básica${\displaystyle H(X,Y)\leq H(X)+H(Y)}$implica que

${\displaystyle |G|\cdot |G_{1}\cap G_{2}|\geq |G_{1}|\cdot |G_{2}|.}$

Resulta que lo contrario es esencialmente cierto. Más precisamente, se dice que un vector es caracterizable por grupos si se puede obtener a partir de una tupla de subgrupos como se indicó anteriormente. El conjunto de vectores caracterizables por grupos se denota${\displaystyle \Upsilon ^{n}}$Como se mencionó anteriormente, ${\displaystyle \Upsilon ^{n}\subseteq \Gamma _{n}^{*}}$. Por otro lado,${\displaystyle \Gamma _{n}^{*}}$(y por lo tanto${\displaystyle {\overline {\Gamma _{n}^{*}}}}$) está contenido en el cierre topológico del cierre convexo de${\displaystyle \Upsilon ^{n}}$. ^{[ 15 ]} En otras palabras, una desigualdad lineal se cumple para todos los vectores entrópicos si y solo si se cumple para todos los vectores${\displaystyle h}$de la forma${\displaystyle h_{I}=\log {\frac {|G|}{|G_{I}|}}}$, dónde${\displaystyle I}$recorre subconjuntos de alguna tupla de subgrupos.${\displaystyle G_{1},G_{2},\dots ,G_{n}}$en un grupo${\displaystyle G}$.

Los vectores caracterizables por grupos que provienen de un grupo abeliano satisfacen la desigualdad de Ingleton.