A non-Shannon-type conditional inequality of information quantities

Given n discrete random variables /spl Omega/=X/sub 1/,. . . , X/sub n/, associated with any subset /spl alpha/ of 1, 2,. . . , n, there is a joint entropy H (X/sub /spl alpha//) where X/sub /spl alpha//=X/sub i/: i/spl isin//spl alpha/. This can be viewed as a function defined on 2/sup 1, 2,. . . , n/ taking values in [0, +/spl infin/). We call this function the entropy function of /spl Omega/. 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 is two-alternative. These properties are the so-called basic information inequalities of Shannon's information measures. An entropy function can be viewed as a 2/sup n/-1-dimensional vector where the coordinates are indexed by the subsets of the ground set 1, 2,. . . , n. As introduced by Yeng (see ibid. , vol. 43, no. 6, p. 1923-34, 1997) /spl Gamma//sub n/ stands for the cone in IR (2/sup n/-1) consisting of all vectors which have all these properties. Let /spl Gamma//sub n/* be the set of all 2/sup n/-1-dimensional vectors which correspond to the entropy functions of some sets of n discrete random variables. A fundamental information-theoretic problem is whether or not /spl Gamma/~/sub n/*=/spl Gamma//sub n/. Here /spl Gamma/~/sub n/* stands for the closure of the set /spl Gamma//sub n/*. We show that /spl Gamma/~/sub n/* is a convex cone, /spl Gamma//sub 2/*=/spl Gamma//sub 2/, /spl Gamma//sub 3/*/spl ne//spl Gamma//sub 3/, but /spl Gamma/~/sub 3/*=/spl Gamma//sub 3/. For four random variables, we have discovered a conditional inequality which is not implied by the basic information inequalities of the same set of random variables. This lends an evidence to the plausible conjecture that /spl Gamma/~/sub n/*/spl ne//spl Gamma//sub n/ for n>3.