Inequalities in information theory

Inequalities are very important in the study of information theory. There are a number of different contexts in which these inequalities appear. Entropic vector Consider a tuple of finitely (or at most countably) supported random variables on the same probability space. There are 2n subsets, for which (joint) entropies can be computed. For example, when n = 2, we may consider the entropies and . They satisfy the following inequalities (which together characterize the range of the marginal and joint entropies of two random variables): In fact, these can all be expressed as special cases of a single inequality involving the conditional mutual information, namely where , , and each denote the joint distribution of some arbitrary (possibly empty) subset of our collection of random variables. Inequalities that can be derived as linear combinations of this are known as Shannon-type inequalities. For larger there are further restrictions on possible values of entropy. To make this precise, a vector in indexed by subsets of is said to be entropic if there is a joint, discrete distribution of n random variables such that is their joint entropy, for each subset . The set of entropic vectors is denoted , following the notation of Yeung. It is not closed nor convex for , but its topological closure is known to be convex and hence it can be characterized by the (infinitely many) linear inequalities satisfied by all entropic vectors, called entropic inequalities. The set of all vectors that satisfy Shannon-type inequalities (but not necessarily other entropic inequalities) contains . This containment is strict for and further inequalities are known as non-Shannon type inequalities. Zhang and Yeung reported the first non-Shannon-type inequality, often referred to as the Zhang-Yeung inequality. Matus proved that no finite set of inequalities can characterize (by linear combinations) all entropic inequalities. In other words, the region is not a polytope. A great many important inequalities in information theory are actually lower bounds for the Kullback–Leibler divergence.