On characterization of entropy function via information inequalities
On characterization of entropy function via information inequalities
复制标题
DOI：
10.1109/18.681320
复制
发表时间：
1998-07-01
影响因子：
2.5
通讯作者：
Yeung, RW
中科院分区：
文献类型：
--
作者：
Zhang, Z;Yeung, RW
Given n discrete random variables Omega = {X-1, ..., X-n}, associated with any subset alpha of {1, 2, ..., n}, there is a joint entropy H(X-alpha) where X-alpha = {X-i:i is an element of alpha), This can be viewed as a function defined on 2({1,2,...,n}) faking values in [0, +infinity). We call this function the entropy function of i, 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 informations implies that this function has the following property: for any two subsets alpha and beta of {1, 2, ..., n}H-Omega(alpha) + H-Omega(beta) greater than or equal to H-Omega(alpha boolean OR beta) + H-Omega(alpha boolean AND beta).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(n) - 1-dimensional vector where the coordinates are indexed by the nonempty subsets of the ground set {1, 2, ..., n}. Let Gamma(n) be the cone in R2n-1 consisting of all vectors which have these three properties when they are viewed as functions defined on 2{(1, 2, ..., n}). Let Gamma(n)* be the set of all 2(n) - 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)* = Gamma(n)? Here (n)* stands for the closure of the set Gamma(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 Gamma(n) whenever n > 3, While this new inequality gives a nontrivial outer bound to the cone (4)*, an inner bound for (4)* is also given, The inequality is also extended to any number of random variables.
Given n discrete random variables Omega = {X-1, ..., X-n}, associated with any subset alpha of {1, 2, ..., n}, there is a joint entropy H(X-alpha) where X-alpha = {X-i:i is an element of alpha), This can be viewed as a function defined on 2({1,2,...,n}) faking values in [0, +infinity). We call this function the entropy function of i, 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 informations implies that this function has the following property: for any two subsets alpha and beta of {1, 2, ..., n}H-Omega(alpha) + H-Omega(beta) greater than or equal to H-Omega(alpha boolean OR beta) + H-Omega(alpha boolean AND beta).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(n) - 1-dimensional vector where the coordinates are indexed by the nonempty subsets of the ground set {1, 2, ..., n}. Let Gamma(n) be the cone in R2n-1 consisting of all vectors which have these three properties when they are viewed as functions defined on 2{(1, 2, ..., n}). Let Gamma(n)* be the set of all 2(n) - 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)* = Gamma(n)? Here (n)* stands for the closure of the set Gamma(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 Gamma(n) whenever n > 3, While this new inequality gives a nontrivial outer bound to the cone (4)*, an inner bound for (4)* is also given, The inequality is also extended to any number of random variables.