inequalities in information theory

{{main|Entropic vector}}

Consider a tuple $X\_1,X\_2,\backslash dots,X\_n$ of $n$ 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 $H(X\_1),$ $H(X\_2),$ and $H(X\_1,\; X\_2)$. They satisfy the following inequalities (which together characterize the range of the marginal and joint entropies of two random variables):

• $H(X\_1)\; \backslash ge\; 0$
• $H(X\_2)\; \backslash ge\; 0$
• $H(X\_1)\; \backslash le\; H(X\_1,\; X\_2)$
• $H(X\_2)\; \backslash le\; H(X\_1,\; X\_2)$
• $H(X\_1,\; X\_2)\; \backslash le\; H(X\_1)\; +\; H(X\_2).$

In fact, these can all be expressed as special cases of a single inequality involving the conditional mutual information, namely

:$I(A;B|C)\; \backslash ge\; 0,$

where $A$, $B$, and $C$ 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 $n$ there are further restrictions on possible values of entropy.

To make this precise, a vector $h$ in $\backslash mathbb\{R\}^\{2^n\}$ indexed by subsets of $\backslash \{1,\backslash dots,n\backslash \}$ is said to be entropic if there is a joint, discrete distribution of n random variables $X\_1,\backslash dots,X\_n$ such that $h\_I\; =\; H(X\_i\; \backslash colon\; i\; \backslash in\; I)$ is their joint entropy, for each subset $I$.

The set of entropic vectors is denoted $\backslash Gamma^*\_n$, following the notation of Yeung.{{cite journal|last=Yeung|first=R.W.|year=1997|title=A framework for linear information inequalities|journal=IEEE Transactions on Information Theory|volume=43|issue=6|pages=1924–1934|doi=10.1109/18.641556}})

It is not closed nor convex for $n\; \backslash geq\; 3$, but its topological closure $\backslash overline\{\backslash Gamma^*\_n\}$ 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 $\backslash overline\{\backslash Gamma^*\_n\}$.

This containment is strict for $n\; \backslash geq\; 4$ and further inequalities are known as non-Shannon type inequalities.

Zhang and Yeung reported the first non-Shannon-type inequality,{{cite journal |first1=Z. |last1=Zhang |first2=R. W. |last2=Yeung |title=On characterization of entropy function via information inequalities |journal=IEEE Transactions on Information Theory |year=1998 |volume=44 |issue=4 |pages=1440–1452 |doi=10.1109/18.681320 }} often referred to as the Zhang-Yeung inequality.

Matus{{cite conference |first=F. |last=Matus |title=Infinitely many information inequalities |conference=2007 IEEE International Symposium on Information Theory | year=2007 }} proved that no finite set of inequalities can characterize (by linear combinations) all entropic inequalities. In other words, the region $\backslash overline\{\backslash Gamma^*\_n\}$ is not a polytope.

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_KL(P||Q) depends very sensitively on events that are very rare in the reference distribution Q. D_KL(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_KL(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.)

{{main|Gibbs' inequality}}

This fundamental inequality states that the Kullback–Leibler divergence is non-negative.

{{main|Kullback's inequality}}

Another inequality concerning the Kullback–Leibler divergence is known as Kullback's inequality.{{cite book |first1=Aimé |last1=Fuchs |first2=Giorgio |last2=Letta |title=Séminaire de Probabilités IV Université de Strasbourg |chapter=L'Inégalité de KULLBACK. Application à la théorie de l'estimation |location=Strasbourg |volume=124 |pages=108–131 |year=1970 |mr=267669 |doi=10.1007/bfb0059338|series=Lecture Notes in Mathematics |isbn=978-3-540-04913-5 |url=http://www.numdam.org/item/SPS_1970__4__108_0/ }} 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

:$D\_\{KL\}(P\backslash parallel\; Q)\; \backslash ge\; \backslash Psi\_Q^*(\backslash mu\text{'}\_1(P)),$

where $\backslash Psi\_Q^*$ is the large deviations rate function, i.e. the convex conjugate of the cumulant-generating function, of Q, and $\backslash mu\text{'}\_1(P)$ is the first moment of P.

The Cramér–Rao bound is a corollary of this result.

{{main|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

: $\backslash sqrt\{\backslash frac\{1\}\{2\}D\_\{KL\}^\{(e)\}(P\backslash parallel\; Q)\}\; \backslash ge\; \backslash sup\; \backslash \{\; |P(A)\; -\; Q(A)|\; :\; A\backslash text\{\; is\; an\; event\; to\; which\; probabilities\; are\; assigned.\}\; \backslash \}.$

where

: $D\_\{KL\}^\{(e)\}(P\backslash parallel\; Q)$

is the Kullback–Leibler divergence in nats and

: $\backslash sup\_A\; |P(A)\; -\; Q(A)|$

is the total variation distance.

{{main|Hirschman uncertainty}}

In 1957,{{cite journal |first=I. I. |last=Hirschman |title=A Note on Entropy |journal=American Journal of Mathematics |year=1957 |volume=79 |issue=1 |pages=152–156 |jstor=2372390 |doi=10.2307/2372390}} Hirschman showed that for a (reasonably well-behaved) function $f:\backslash mathbb\; R\; \backslash rightarrow\; \backslash mathbb\; C$ such that $\backslash int\_\{-\backslash infty\}^\backslash infty\; |f(x)|^2\backslash ,dx\; =\; 1,$ and its Fourier transform $g(y)=\backslash int\_\{-\backslash infty\}^\backslash infty\; f(x)\; e^\{-2\; \backslash pi\; i\; x\; y\}\backslash ,dx,$ the sum of the differential entropies of $|f|^2$ and $|g|^2$ is non-negative, i.e.

:$-\backslash int\_\{-\backslash infty\}^\backslash infty\; |f(x)|^2\; \backslash log\; |f(x)|^2\; \backslash ,dx\; -\backslash int\_\{-\backslash infty\}^\backslash infty\; |g(y)|^2\; \backslash log\; |g(y)|^2\; \backslash ,dy\; \backslash ge\; 0.$

Hirschman conjectured, and it was later proved,{{cite journal |first=W. |last=Beckner |title=Inequalities in Fourier Analysis |journal=Annals of Mathematics |volume=102 |issue=6 |pages=159–182 |year=1975 |jstor=1970980 |doi=10.2307/1970980}} that a sharper bound of $\backslash log(e/2),$ 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.

Given discrete random variables $X$, $Y$, and $Y\text{'}$, such that $X$ takes values only in the interval [−1, 1] and $Y\text{'}$ is determined by $Y$ (such that $H(Y\text{'}|Y)=0$), we have{{cite journal |author-link=Terence Tao |first=T. |last=Tao |title=Szemerédi's regularity lemma revisited |journal=Contrib. Discrete Math. |volume=1 |year=2006 |pages=8–28 |arxiv=math/0504472 |bibcode=2005math......4472T }}{{cite journal |author-link=Rudolf Ahlswede |first=Rudolf |last=Ahlswede |title=The final form of Tao's inequality relating conditional expectation and conditional mutual information |journal=Advances in Mathematics of Communications |volume=1 |issue=2 |year=2007 |pages=239–242 |doi=10.3934/amc.2007.1.239 |doi-access=free }}

:$\backslash operatorname\; E\; \backslash big(\; \backslash big|\; \backslash operatorname\; E(X|Y\text{'})\; -\; \backslash operatorname\; E(X\backslash mid\; Y)\; \backslash big|\; \backslash big)$

\le \sqrt {I(X;Y\mid Y') \, 2 \log 2 },

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.)

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.{{cite journal|first1=S.W.|last1=Ho|first2=L.|last2=Ling|first3=C.W.|last3=Tan|first4=R.W.|last4=Yeung|year=2020|title=Proving and Disproving Information Inequalities: Theory and Scalable Algorithms|journal=IEEE Transactions on Information Theory|volume=66|issue=9|pages=5525–5536|doi=10.1109/TIT.2020.2982642|s2cid=216530139 }}[http://user-www.ie.cuhk.edu.hk/~ITIP/ ITIP] is a Matlab based proof checker for all Shannon type Inequalities. [http://xitip.epfl.ch 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. [https://aitip.org AITIP] and [http://www.oxitip.com oXitip] are cloud based implementations for validating the Shannon type inequalities. [http://www.oxitip.com oXitip] uses GLPK optimizer and has a C++ backend based on Xitip with a web based user interface. [https://aitip.org 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.Quantum information-theoretic inequalities can be checked by the contraction map proof method.Bao, N; Naskar, J;, "Properties of the contraction map for holographic entanglement entropy inequalities"

, J. High Energ. Phys. 06(2024), 3,

DOI: https://doi.org/10.1007/JHEP06(2024)039, 07 June 2024.

• Data processing inequality
• Cramér–Rao bound
• Entropy power inequality
• Entropic vector
• Fano's inequality
• Jensen's inequality
• Kraft inequality
• Pinsker's inequality

• Thomas M. Cover, Joy A. Thomas. Elements of Information Theory, Chapter 16, "Inequalities in Information Theory" John Wiley & Sons, Inc. 1991 Print {{ISBN|0-471-06259-6}} Online {{ISBN|0-471-20061-1}}
• Amir Dembo, Thomas M. Cover, Joy A. Thomas. Information Theoretic Inequalities. IEEE Transactions on Information Theory, Vol. 37, No. 6, November 1991. [https://web.archive.org/web/20100703052423/http://www.stanford.edu/~cover/papers/dembo_cover_thomas_91.pdf pdf]
• ITIP: http://user-www.ie.cuhk.edu.hk/~ITIP/
• XITIP: http://xitip.epfl.ch
• N. R. Pai, Suhas Diggavi, T. Gläßle, E. Perron, R.Pulikkoonattu, R. W. Yeung, Y. Yan, oXitip: An Online Information Theoretic Inequalities Prover http://www.oxitip.com
• Siu Wai Ho, Lin Ling, Chee Wei Tan and Raymond W. Yeung, AITIP (Information Theoretic Inequality Prover): https://aitip.org
• Nivedita Rethnakar, Suhas Diggavi, Raymond. W. Yeung, InformationInequalities.jl: Exploring Information-Theoretic Inequalities, Julia Package, 2021 [https://nivupai.github.io/InformationInequalities.jl/]

{{DEFAULTSORT:Inequalities In Information Theory}}

Category:Entropy and information

Category:Information theory