Information inequalities

Question

What are the feasible $2^n$-tuples of entropies $h(S) := H(X_{i_1},\dots,X_{i_{|S|}})$ where $X_1,\dots,X_n$ are discrete random variables with some (unknown) joint probability distribution as $S=\{i_1,\dots,i_{|S|}\}$ ranges over the subsets of $\{1,\dots,n\}$? Here $X_{i_1},\dots,X_{i_{|S|}}$ denotes the compound random variable that in classic information theory texts might be written as $XY$, $XYZ$, etc. and $H(\cdot)$ is the standard entropy $\sum p \log 1/p$.

Of course $h(\{\,\}) = 0$ and $S_1 \subseteq S_2$ implies $h(S_1) \leq h(S_2)$; furthermore, nonnegativity of conditional mutual information gives $$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).$$ Are there other constraints, linear or otherwise?

Assuming the answer is “no”, I’d be interested in knowing a combinatorial characterization of the extreme rays of the convex polyhedral cone of achievable $2^n$-tuples.

Answer 1

Yes. The set of $2^n$ (or $2^n-1$ excluding the empty set) dimensional vectors formed by entropies is called the entropic region [1]. Inequalities on the entropic region not implied by the nonnegativity of conditional mutual information are called non-Shannon-type inequalities. The first such inequality for $n=4$ was given in:

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

Since then, many more non-Shannon-type inequalities were discovered. Remarkably, there are infinitely many such inequalities even for $n=4$, as shown in:

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

Characterizing the entropic region is still a major open problem in information theory (even for $n=4$). The problem might even be undecidable depending on how you formulate it.