Entropic vector

The entropic vector or entropic function is a concept arising in information theory. It represents the possible values of Shannon's information entropy that subsets of one set of random variables may take. Understanding which vectors are entropic is a way to represent all possible inequalities between entropies of various subsets. For example, for any two random variables X 1 , X 2 {\displaystyle X_{1},X_{2}} , their joint entropy (the entropy of the random variable representing the pair X 1 , X 2 {\displaystyle X_{1},X_{2}} ) is at most the sum of the entropies of X 1 {\displaystyle X_{1}} and of X 2 {\displaystyle X_{2}} :

H ( X 1 , X 2 ) ≤ H ( X 1 ) + H ( X 2 ) {\displaystyle H(X_{1},X_{2})\leq H(X_{1})+H(X_{2})}

Other information-theoretic measures such as conditional information, mutual information, or total correlation can be expressed in terms of joint entropy and are thus related by the corresponding inequalities. Many inequalities satisfied by entropic vectors can be derived as linear combinations of a few basic ones, called Shannon-type inequalities. However, it has been proven that already for n = 4 {\displaystyle n=4} variables, no finite set of linear inequalities is sufficient to characterize all entropic vectors.

Shannon's information entropy of a random variable X {\displaystyle X} is denoted H ( X ) {\displaystyle H(X)} . For a tuple of random variables X 1 , X 2 , … , X n {\displaystyle X_{1},X_{2},\ldots ,X_{n}} , we denote the joint entropy of a subset X i 1 , X i 2 , … , X i k {\displaystyle X_{i_{1}},X_{i_{2}},\dots ,X_{i_{k}}} as H ( X i 1 , X i 2 , … , X i k ) {\displaystyle H(X_{i_{1}},X_{i_{2}},\dots ,X_{i_{k}})} , or more concisely as H ( X I ) {\displaystyle H(X_{I})} , where I = { i 1 , i 2 , … , i k } {\displaystyle I=\{i_{1},i_{2},\dots ,i_{k}\}} . Here X I {\displaystyle X_{I}} can be understood as the random variable representing the tuple ( X i 1 , X i 2 , … , X i k ) {\displaystyle (X_{i_{1}},X_{i_{2}},\dots ,X_{i_{k}})} . For the empty subset I = ∅ {\displaystyle I=\emptyset } , X I {\displaystyle X_{I}} denotes a deterministic variable with entropy 0.

A vector h in R 2 n {\displaystyle \mathbb {R} ^{2^{n}}} indexed by subsets of { 1 , 2 , … , n } {\displaystyle \{1,2,\dots ,n\}} is called an entropic vector of order n {\displaystyle n} if there exists a tuple of random variables X 1 , X 2 , … , X n {\displaystyle X_{1},X_{2},\ldots ,X_{n}} such that h ( I ) = H ( X I ) {\displaystyle h(I)=H(X_{I})} for each subset I ⊆ { 1 , 2 , … , n } {\displaystyle I\subseteq \{1,2,\dots ,n\}} .

The set of all entropic vectors of order n {\displaystyle n} is denoted by Γ n ∗ {\displaystyle \Gamma _{n}^{*}} . Zhang and Yeung^[1] proved that it is not closed (for n ≥ 3 {\displaystyle n\geq 3} ), but its closure, Γ n ∗ ¯ {\displaystyle {\bar {\Gamma _{n}^{*}}}} , is a convex cone and hence characterized by the (infinitely many) linear inequalities it satisfies. Describing the region Γ n ∗ ¯ {\displaystyle {\bar {\Gamma _{n}^{*}}}} is thus equivalent to characterizing all possible inequalities on joint entropies.

Let X,Y be two independent random variables with discrete uniform distribution over the set { 0 , 1 } {\displaystyle \{0,1\}} . Then

H ( X ) = H ( Y ) = 1 {\displaystyle H(X)=H(Y)=1}

(since each is uniformly distributed over a two-element set), and

H ( X , Y ) = H ( X ) + H ( Y ) = 2 {\displaystyle H(X,Y)=H(X)+H(Y)=2}

(since the two variables are independent, which means the pair ( X 1 , X 2 ) {\displaystyle (X_{1},X_{2})} is uniformly distributed over ( 0 , 0 ) , ( 0 , 1 ) , ( 1 , 0 ) , ( 1 , 1 ) {\displaystyle (0,0),(0,1),(1,0),(1,1)} .) The corresponding entropic vector is thus:

v = ( 0 , 1 , 1 , 2 ) T ∈ Γ 2 ∗ {\displaystyle v=(0,1,1,2)^{\mathsf {T}}\in \Gamma _{2}^{*}}

On the other hand, the vector ( 0 , 1 , 1 , 3 ) T {\displaystyle (0,1,1,3)^{\mathsf {T}}} is not entropic (that is, ( 0 , 1 , 1 , 3 ) T ∉ Γ 2 ∗ {\displaystyle (0,1,1,3)^{\mathsf {T}}\not \in \Gamma _{2}^{*}} ), because any pair of random variables (independent or not) should satisfy H ( X , Y ) ≤ H ( X ) + H ( Y ) {\displaystyle H(X,Y)\leq H(X)+H(Y)} .

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

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

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

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

The Shannon inequality says that an entropic vector is submodular:

3 ) H ( X I ) + H ( X J ) ≥ H ( X I ∪ J ) + H ( X I ∩ J ) {\displaystyle 3)\quad H(X_{I})+H(X_{J})\geq H(X_{I\cup J})+H(X_{I\cap J})} ,     for any I , J ⊆ { 1 , … , n } {\displaystyle I,J\subseteq \{1,\dots ,n\}}

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

I ( X ; Y ∣ Z ) = H ( X ∣ Z ) − H ( X ∣ Y , Z ) = H ( X ∣ Z ) + H ( Y ∣ Z ) − H ( X , Y ∣ Z ) = H ( X , Z ) + H ( Y , Z ) − H ( X , Y , Z ) − H ( Z ) ≥ 0 {\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 X , Z {\displaystyle X,Z} and Y , Z {\displaystyle Y,Z} of the tuple X , Y , Z {\displaystyle X,Y,Z} ; for the other direction, substitute X = X I {\displaystyle X=X_{I}} , Y = X J {\displaystyle Y=X_{J}} , Z = X I ∩ 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 Γ n {\displaystyle \Gamma _{n}} ; it contains Γ n ∗ {\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 Γ n {\displaystyle \Gamma _{n}} ).

The question of whether Shannon-type inequalities are the only ones, that is, whether they completely characterize the region Γ n ∗ {\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, Γ 2 ∗ = Γ 2 {\displaystyle \Gamma _{2}^{*}=\Gamma _{2}} . For three variables, Zhang and Yeung^[1] proved that Γ 3 ∗ ≠ Γ 3 {\displaystyle \Gamma _{3}^{*}\neq \Gamma _{3}} ; however, it is still asymptotically true, meaning that the closure is equal: Γ 3 ∗ ¯ = Γ 3 {\displaystyle {\overline {\Gamma _{3}^{*}}}=\Gamma _{3}} . In 1998, Zhang and Yeung^[2][6] showed that Γ n ∗ ¯ ≠ Γ n {\displaystyle {\overline {\Gamma _{n}^{*}}}\neq \Gamma _{n}} for all n ≥ 4 {\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:

2 I ( X 3 ; X 4 ) ≤ I ( X 1 ; X 2 ) + I ( X 1 ; X 3 , X 4 ) + 3 I ( X 3 ; X 4 | X 1 ) + I ( X 3 ; X 4 | X 2 ) {\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 Γ n ∗ ¯ {\displaystyle {\overline {\Gamma _{n}^{*}}}} better than the Shannon-type bound Γ n {\displaystyle \Gamma _{n}} . In 2007, Matus proved that no finite set of linear inequalities is sufficient (to deduce all as linear combinations), for n ≥ 4 {\displaystyle n\geq 4} variables. In other words, the region Γ 4 ∗ ¯ {\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 Γ n ∗ ¯ {\displaystyle {\overline {\Gamma _{n}^{*}}}} are also known. One example is that Γ 4 ∗ ¯ {\displaystyle {\overline {\Gamma _{4}^{*}}}} contains all vectors in Γ 4 {\displaystyle \Gamma _{4}} which additionally satisfy the following inequality (and those obtained by permuting variables), known as Ingleton's inequality for entropy:^[13]

I ( X 1 ; X 2 ) + I ( X 3 ; X 4 ∣ X 1 ) + I ( X 3 ; X 4 ∣ X 2 ) − I ( X 3 ; X 4 ) ≥ 0 {\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 G {\displaystyle G} and subgroups G 1 , G 2 , … , G n {\displaystyle G_{1},G_{2},\dots ,G_{n}} of G {\displaystyle G} . Let G I {\displaystyle G_{I}} denote ⋂ i ∈ I G i {\displaystyle \bigcap _{i\in I}G_{i}} for I ⊆ { 1 , … , n } {\displaystyle I\subseteq \{1,\dots ,n\}} ; this is also a subgroup of G {\displaystyle G} . It is possible to construct a probability distribution for n {\displaystyle n} random variables X 1 , … , X n {\displaystyle X_{1},\dots ,X_{n}} such that

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

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

| G | ⋅ | G 1 ∩ G 2 | ≥ | G 1 | ⋅ | G 2 | . {\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 Υ n {\displaystyle \Upsilon ^{n}} . As said above, Υ n ⊆ Γ n ∗ {\displaystyle \Upsilon ^{n}\subseteq \Gamma _{n}^{*}} . On the other hand, Γ n ∗ {\displaystyle \Gamma _{n}^{*}} (and thus Γ n ∗ ¯ {\displaystyle {\overline {\Gamma _{n}^{*}}}} ) is contained in the topological closure of the convex closure of Υ n {\displaystyle \Upsilon ^{n}} .^[15] In other words, a linear inequality holds for all entropic vectors if and only if it holds for all vectors h {\displaystyle h} of the form h I = log ⁡ | G | | G I | {\displaystyle h_{I}=\log {\frac {|G|}{|G_{I}|}}} , where I {\displaystyle I} goes over subsets of some tuple of subgroups G 1 , G 2 , … , G n {\displaystyle G_{1},G_{2},\dots ,G_{n}} in a group G {\displaystyle G} .

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

Kolmogorov complexity satisfies essentially the same inequalities as entropy. Namely, denote the Kolmogorov complexity of a finite string x {\displaystyle x} as K ( x ) {\displaystyle K(x)} (that is, the length of the shortest program that outputs x {\displaystyle x} ). The joint complexity of two strings x , y {\displaystyle x,y} , defined as the complexity of an encoding of the pair ⟨ x , y ⟩ {\displaystyle \langle x,y\rangle } , can be denoted K ( x , y ) {\displaystyle K(x,y)} . Similarly, the conditional complexity can be denoted K ( x | y ) {\displaystyle K(x|y)} (the length of the shortest program that outputs x {\displaystyle x} given y {\displaystyle y} ). Andrey Kolmogorov noticed these notions behave similarly to Shannon entropy, for example:

K ( a ) + K ( b ) ≥ K ( a , b ) − O ( log ⁡ | a | + log ⁡ | b | ) {\displaystyle K(a)+K(b)\geq K(a,b)-O(\log |a|+\log |b|)}

In 2000, Hammer et al.^[16] proved that indeed an inequality holds for entropic vectors if and only if the corresponding inequality in terms of Kolmogorov complexity holds up to logarithmic terms for all tuples of strings.

• Inequalities in information theory

• Thomas M. Cover, Joy A. Thomas. Elements of information theory New York: Wiley, 1991. ISBN 0-471-06259-6
• Raymond Yeung. A First Course in Information Theory, Chapter 12, Information Inequalities, 2002, Print ISBN 0-306-46791-7