Entropic vector

For a tuple of random variables ${\displaystyle X_{1},X_{2},\ldots ,X_{n}}$, their entropies satisfy:

${\displaystyle 1)\quad H(X_{\emptyset })=0}$

${\displaystyle 2)\quad H(X_{I})\leq H(X_{J})}$,     for any ${\displaystyle I\subseteq J\subseteq \{1,\dots ,n\}}$

In particular, ${\displaystyle H(X_{I})\geq 0}$, for any ${\displaystyle I\subseteq \{1,\dots ,n\}}$.

The Shannon inequality says that an entropic vector is submodular:

${\displaystyle 3)\quad H(X_{I})+H(X_{J})\geq H(X_{I\cup J})+H(X_{I\cap J})}$,     for any ${\displaystyle I,J\subseteq \{1,\dots ,n\}}$

It is equivalent to the inequality stating that the conditional mutual information is non-negative:

${\displaystyle {\begin{aligned}I(X;Y\mid Z)&=H(X\mid Z)-H(X\mid Y,Z)\\&=H(X\mid Z)+H(Y\mid Z)-H(X,Y\mid Z)\\&=H(X,Z)+H(Y,Z)-H(X,Y,Z)-H(Z)\\&\geq 0\end{aligned}}}$

(For one direction, observe this the last form expresses Shannon's inequality for subsets ${\displaystyle X,Z}$ and ${\displaystyle Y,Z}$ of the tuple ${\displaystyle X,Y,Z}$; for the other direction, substitute ${\displaystyle X=X_{I}}$, ${\displaystyle Y=X_{J}}$, ${\displaystyle Z=X_{I\cap J}}$).

Many inequalities can be derived as linear combinations of Shannon inequalities; they are called Shannon-type inequalities or basic information inequalities of Shannon's information measures.[2] The set of vectors that satisfies them is called ${\displaystyle \Gamma _{n}}$; it contains ${\displaystyle \Gamma _{n}^{*}}$.

Software has been developed to automate the task of proving Shannon-type inequalities.[3][4] Given an inequality, such software is able to determine whether the given inequality is a valid Shannon-type inequality (i.e., whether it contains the cone ${\displaystyle \Gamma _{n}}$).

The question of whether Shannon-type inequalities are the only ones, that is, whether they completely characterize the region ${\displaystyle \Gamma _{n}^{*}}$, was first asked by Te Su Han in 1981[2] and more precisely by Nicholas Pippenger in 1986.[5] It is not hard to show that this is true for two variables, that is, ${\displaystyle \Gamma _{2}^{*}=\Gamma _{2}}$. For three variables, Zhang and Yeung[1] proved that ${\displaystyle \Gamma _{3}^{*}\neq \Gamma _{3}}$; however, it is still asymptotically true, meaning that the closure is equal: ${\displaystyle {\overline {\Gamma _{3}^{*}}}=\Gamma _{3}}$. In 1998, Zhang and Yeung[2][6] showed that ${\displaystyle {\overline {\Gamma _{n}^{*}}}\neq \Gamma _{n}}$ for all ${\displaystyle n\geq 4}$, by proving that the following inequality on four random variables (in terms of conditional mutual information) is true for any entropic vector, but is not Shannon-type:

${\displaystyle 2I(X_{3};X_{4})\leq I(X_{1};X_{2})+I(X_{1};X_{3},X_{4})+3I(X_{3};X_{4}|X_{1})+I(X_{3};X_{4}|X_{2})}$

Further inequalities and infinite families of inequalities have been found.[7][8][9][10] These inequalities provide outer bounds for ${\displaystyle {\overline {\Gamma _{n}^{*}}}}$ better than the Shannon-type bound ${\displaystyle \Gamma _{n}}$. In 2007, Matus proved that no finite set of linear inequalities is sufficient (to deduce all as linear combinations), for ${\displaystyle n\geq 4}$ variables. In other words, the region ${\displaystyle {\overline {\Gamma _{4}^{*}}}}$ is not polyhedral.[11] Whether they can be characterized in some other way (allowing to effectively decide whether a vector is entropic or not) remains an open problem.

Analogous questions for von Neumann entropy in quantum information theory have been considered.[12]

Some inner bounds of ${\displaystyle {\overline {\Gamma _{n}^{*}}}}$ are also known. One example is that ${\displaystyle {\overline {\Gamma _{4}^{*}}}}$ contains all vectors in ${\displaystyle \Gamma _{4}}$ which additionally satisfy the following inequality (and those obtained by permuting variables), known as Ingleton's inequality for entropy:[13]

${\displaystyle I(X_{1};X_{2})+I(X_{3};X_{4}\mid X_{1})+I(X_{3};X_{4}\mid X_{2})-I(X_{3};X_{4})\geq 0}$[2]

Consider a group ${\displaystyle G}$ and subgroups ${\displaystyle G_{1},G_{2},\dots ,G_{n}}$ of ${\displaystyle G}$. Let ${\displaystyle G_{I}}$ denote ${\displaystyle \bigcap _{i\in I}G_{i}}$ for ${\displaystyle I\subseteq \{1,\dots ,n\}}$; this is also a subgroup of ${\displaystyle G}$. It is possible to construct a probability distribution for ${\displaystyle n}$ random variables ${\displaystyle X_{1},\dots ,X_{n}}$ such that

${\displaystyle H(X_{I})=\log {\frac {|G|}{|G_{I}|}}}$.[14]

(The construction essentially takes an element ${\displaystyle a}$ of ${\displaystyle G}$ uniformly at random and lets ${\displaystyle X_{i}}$ be the corresponding coset ${\displaystyle aG_{i}}$). Thus any information-theoretic inequality implies a group-theoretic one. For example, the basic inequality ${\displaystyle H(X,Y)\leq H(X)+H(Y)}$ implies that

${\displaystyle |G|\cdot |G_{1}\cap G_{2}|\geq |G_{1}|\cdot |G_{2}|.}$

It turns out the converse is essentially true. More precisely, a vector is said to be group-characterizable if it can be obtained from a tuple of subgroups as above. The set of group-characterizable vectors is denoted ${\displaystyle \Upsilon ^{n}}$. As said above, ${\displaystyle \Upsilon ^{n}\subseteq \Gamma _{n}^{*}}$. On the other hand, ${\displaystyle \Gamma _{n}^{*}}$ (and thus ${\displaystyle {\overline {\Gamma _{n}^{*}}}}$) is contained in the topological closure of the convex closure of ${\displaystyle \Upsilon ^{n}}$.[15] In other words, a linear inequality holds for all entropic vectors if and only if it holds for all vectors ${\displaystyle h}$ of the form ${\displaystyle h_{I}=\log {\frac {|G|}{|G_{I}|}}}$, where ${\displaystyle I}$ goes over subsets of some tuple of subgroups ${\displaystyle G_{1},G_{2},\dots ,G_{n}}$ in a group ${\displaystyle G}$.

Group-characterizable vectors that come from an abelian group satisfy Ingleton's inequality.