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 inequalities. Consider a tuple formula_1 of formula_2 finitely (or at most countably) supported random variables on the same probability space. There are 2 subsets, for which (joint) entropies can be computed. For example, when "n" = 2, we may consider the entropies formula_3 formula_4 and formula_5. 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 formula_12, formula_13, and formula_14 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 formula_2 there are further restrictions on possible values of entropy. To make this precise, a vector formula_16 in formula_17 indexed by subsets of formula_18 is said to be "entropic" if there is a joint, discrete distribution of "n" random variables formula_19 such that formula_20 is their joint  entropy, for each subset formula_21. The set of entropic vectors is denoted formula_22, following the notation of Yeung. It is not closed nor convex for formula_23, but its topological closure formula_24 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 formula_24. This containment is strict for formula_26 and further inequalities are known as "non-Shannon type" inequalities. Zhang and Yeung reported the first non-Shannon-type inequality . Matus proved that no finite set of inequalities can characterize (by linear combinations) all entropic inequalities. In other words, the region formula_24 is not a polytope. Lower bounds for the Kullback–Leibler divergence. A great many important inequalities in information theory are actually lower bounds for the Kullback–Leibler divergence. Even the Shannon-type inequalities can be considered part of this category, since the interaction information can be expressed as the Kullback–Leibler divergence of the joint distribution with respect to the product of the marginals, and thus these inequalities can be seen as a special case of Gibbs' inequality . On the other hand, it seems to be much more difficult to derive useful upper bounds for the Kullback–Leibler divergence. This is because the Kullback–Leibler divergence "D"("P"||"Q") depends very sensitively on events that are very rare in the reference distribution "Q". "D"("P"||"Q") increases without bound as an event of finite non-zero probability in the distribution "P" becomes exceedingly rare in the reference distribution "Q", and in fact "D"("P"||"Q") is not even defined if an event of non-zero probability in "P" has zero probability in "Q". (Hence the requirement that "P" be absolutely continuous with respect to  Q.) Gibbs' inequality. This fundamental inequality states that the Kullback–Leibler divergence is non-negative. Kullback's inequality. Another inequality concerning the Kullback–Leibler divergence is known as Kullback's inequality. If "P" and "Q" are probability distributions on the real line with "P" absolutely continuous with respect to "Q," and whose first moments exist, then where formula_29 is the large deviations rate function, i.e. the convex conjugate of the cumulant-generating function, of "Q", and formula_30 is the first moment of "P". The Cramér–Rao bound is a corollary of this result. Pinsker's inequality. Pinsker's inequality relates  Kullback–Leibler divergence and total variation distance. It states that if "P", "Q" are two probability distributions, then where is the Kullback–Leibler divergence in nats and is the total variation distance. Other inequalities. Hirschman uncertainty. In 1957, Hirschman showed that for a (reasonably well-behaved) function formula_34 such that formula_35 and its Fourier transform formula_36 the sum of the differential entropies of formula_37 and formula_38 is non-negative, i.e. Hirschman conjectured, and it was later proved, that a sharper bound of formula_40 which is attained in the case of a Gaussian distribution, could replace the right-hand side of  this inequality. This is especially significant since it implies, and is stronger than, Weyl's formulation of Heisenberg's uncertainty principle. Tao's inequality. Given discrete random variables formula_41, formula_42, and formula_43, such that formula_41 takes values only in the interval [−1, 1] and formula_43 is determined by formula_42 (such that formula_47), we have relating the conditional expectation to the conditional mutual information. This is a simple consequence of Pinsker's inequality. (Note: the correction factor log 2 inside the radical arises because we are measuring the conditional mutual information in bits rather than nats.) Machine based proof checker of  information-theoretic inequalities. Several machine based proof checker algorithms are now available. Proof checker algorithms typically verify the inequalities as either true or false. More advanced proof checker algorithms can produce proof or counterexamples.ITIP is a Matlab based proof checker for all Shannon type Inequalities. Xitip is an open source, faster version of the same algorithm implemented in C with a graphical front end. Xitip also has a built in language parsing feature which support a broader range of random variable descriptions as input. AITIP and oXitip are cloud based implementations for validating the Shannon type inequalities. oXitip uses  GLPK optimizer and has a C++ backend based on Xitip with a web based user interface. AITIP uses Gurobi solver for optimization and a mix of python and C++ in the backend implementation. It can also provide the canonical break down of the inequalities in terms of basic Information measures.