On characterization of entropy function via information inequalities

Given n discrete random variables Ω={X₁, ···, X_n}, associated with any subset α of (1, 2, ···, n), there is a joint entropy H(X_α) where X_α={X_i:iεα}. This can be viewed as a function defined on 2/sup {1, 2, ···, n}/ taking values in (0, +∞). We call this function the entropy function of Ω. The nonnegativity of the joint entropies implies that this function is nonnegative; the nonnegativity of the conditional joint entropies implies that this function is nondecreasing; and the nonnegativity of the conditional mutual information implies that this function has the following property: for any two subsets α and β of {1, 2, ···, n} H_Ω(α)+H_Ω(β)⩾H _Ω(α∪β)+H_Ω (α∩β). These properties are the so-called basic information inequalities of Shannon´s information measures. Do these properties fully characterize the entropy function? To make this question more precise, we view an entropy function as a 2ⁿ-1-dimensional vector where the coordinates are indexed by the nonempty subsets of the ground set {1, 2, ···, n}. Let Γ_n be the cone in R^2n-1 consisting of all vectors which have these three properties when they are viewed as functions defined on 2/sup {1, 2, ···, n}/. Let Γ_n* be the set of all 2ⁿ-1-dimensional vectors which correspond to the entropy functions of some sets of n discrete random variables. The question can be restated as: is it true that for any n, Γ¯_n*=Γ_n? Here Γ¯_n* stands for the closure of the set Γ_n*. The answer is “yes” when n=2 and 3 as proved in our previous work. Based on intuition, one may tend to believe that the answer should be “yes” for any n. The main discovery of this paper is a new information-theoretic inequality involving four discrete random variables which gives a negative answer to this fundamental problem in information theory: Γ¯*_n is strictly smaller than Γ_n whenever n>3. While this new inequality gives a nontrivial outer bound to the cone Γ¯₄*, an inner bound for Γ¯*₄ is also given. The inequality is also extended to any number of random variables