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.



Information inequalities
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.


