Desigualdades informativas

Question

¿Cuáles son las $2^n$ -tuplas de entropías $h(S) := H(X_{i_1},\dots,X_{i_{|S|}})$ donde $X_1,\dots,X_n$ son variables aleatorias discretas con una distribución de probabilidad conjunta (desconocida) como $S=\{i_1,\dots,i_{|S|}\}$ abarca los subconjuntos de $\{1,\dots,n\}$ ? Aquí $X_{i_1},\dots,X_{i_{|S|}}$ denota la variable aleatoria compuesta que en los textos clásicos de teoría de la información podría escribirse como $XY$ , $XYZ$ etc. y $H(\cdot)$ es la entropía estándar $\sum p \log 1/p$ .

Por supuesto $h(\{\,\}) = 0$ y $S_1 \subseteq S_2$ implica $h(S_1) \leq h(S_2)$ ; además, la no negatividad de la información mutua condicional da $$h(S_1 \cup S_2 \cup S_3) + h(S_3) \leq h(S_1 \cup S_3) + h(S_2 \cup S_3).$$ ¿Existen otras limitaciones, lineales o de otro tipo?

Suponiendo que la respuesta sea "no", me interesaría conocer una caracterización combinatoria de los rayos extremos del cono poliédrico convexo de alcanzables $2^n$ -tuplas.

Answer 1

Sí. El conjunto de $2^n$ (o $2^n-1$ excluyendo el conjunto vacío) vectores dimensionales formados por entropías se llama el región entrópica [1]. Las desigualdades en la región entrópica no implicadas por la no negatividad de la información mutua condicional se denominan desigualdades no tipo Shannon . La primera desigualdad de este tipo para $n=4$ se dio en:

[1] Zhen Zhang y Raymond W Yeung, "On characterization of entropy function via information inequalities", IEEE Trans. Inf. Theory 44, 4 (1998), pp. 1440-1452.

Desde entonces, se han descubierto muchas más desigualdades que no son del tipo Shannon. Sorprendentemente, existen infinitas desigualdades de este tipo incluso para $n=4$ como se muestra en:

[2] Frantisek Matúš, "Infinitely many information inequalities", en 2007 IEEE ISIT (2007), pp. 41-44.

Caracterizar la región entrópica sigue siendo un importante problema abierto en la teoría de la información (incluso para $n=4$ ). El problema podría ser incluso indecidible dependiendo de cómo se formule.