# 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.

## 1 Answer

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.

• This is very interesting. What aspect of it suggests undecidability? Commented Aug 2 at 20:39