# Information inequalities

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.

Yes. The set of $$2^n$$ (or $$2^n-1$$ excluding the empty set) dimensional vectors formed by entropies is called the entropic region . 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:
Since then, many more non-Shannon-type inequalities were discovered. Remarkably, there are infinitely many such inequalities even for $$n=4$$, as shown in:
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.