Entropic vector

Last updated October 03, 2023

The entropic vector or entropic function is a concept arising in information theory. It represents the possible values of Shannon's information entropy that subsets of one set of random variables may take. Understanding which vectors are entropic is a way to represent all possible inequalities between entropies of various subsets. For example, for any two random variables $X_{1},X_{2}$ , their joint entropy (the entropy of the random variable representing the pair $X_{1},X_{2}$ ) is at most the sum of the entropies of $X_{1}$ and of $X_{2}$ :

Other information-theoretic measures such as conditional information, mutual information, or total correlation can be expressed in terms of joint entropy and are thus related by the corresponding inequalities. Many inequalities satisfied by entropic vectors can be derived as linear combinations of a few basic ones, called Shannon-type inequalities. However, it has been proven that already for $n=4$ variables, no finite set of linear inequalities is sufficient to characterize all entropic vectors.

Definition

Shannon's information entropy of a random variable $X$ is denoted $H(X)$ . For a tuple of random variables $X_{1},X_{2},\ldots ,X_{n}$ , we denote the joint entropy of a subset $X_{i_{1}},X_{i_{2}},\dots ,X_{i_{k}}$ as $H(X_{i_{1}},X_{i_{2}},\dots ,X_{i_{k}})$ , or more concisely as $H(X_{I})$ , where $I=\{i_{1},i_{2},\dots ,i_{k}\}$ . Here $X_{I}$ can be understood as the random variable representing the tuple $(X_{i_{1}},X_{i_{2}},\dots ,X_{i_{k}})$ . For the empty subset $I=\emptyset$ , $X_{I}$ denotes a deterministic variable with entropy 0.

A vector h in $\mathbb {R} ^{2^{n}}$ indexed by subsets of $\{1,2,\dots ,n\}$ is called an entropic vector of order $n$ if there exists a tuple of random variables $X_{1},X_{2},\ldots ,X_{n}$ such that $h(I)=H(X_{I})$ for each subset $I\subseteq \{1,2,\dots ,n\}$ .

The set of all entropic vectors of order $n$ is denoted by $\Gamma _{n}^{*}$ . Zhang and Yeung^[1] proved that it is not closed (for $n\geq 3$ ), but its closure, ${\bar {\Gamma _{n}^{*}}}$ , is a convex cone and hence characterized by the (infinitely many) linear inequalities it satisfies. Describing the region ${\bar {\Gamma _{n}^{*}}}$ is thus equivalent to characterizing all possible inequalities on joint entropies.

Example

Let X,Y be two independent random variables with discrete uniform distribution over the set $\{0,1\}$ . Then

H(X)=H(Y)=1

(since each is uniformly distributed over a two-element set), and

H(X,Y)=H(X)+H(Y)=2

(since the two variables are independent, which means the pair $(X_{1},X_{2})$ is uniformly distributed over $(0,0),(0,1),(1,0),(1,1)$ .) The corresponding entropic vector is thus:

$v=(0,1,1,2)^{\mathsf {T}}\in \Gamma _{2}^{*}$

On the other hand, the vector $(0,1,1,3)^{\mathsf {T}}$ is not entropic (that is, $(0,1,1,3)^{\mathsf {T}}\not \in \Gamma _{2}^{*}$ ), because any pair of random variables (independent or not) should satisfy $H(X,Y)\leq H(X)+H(Y)$ .

Characterizing entropic vectors: the region Γ_n^*

Shannon-type inequalities and Γ_n

For a tuple of random variables $X_{1},X_{2},\ldots ,X_{n}$ , their entropies satisfy:

1)\quad H(X_{\emptyset })=0

2)\quad H(X_{I})\leq H(X_{J})

, for any

I\subseteq J\subseteq \{1,\dots ,n\}

In particular, $H(X_{I})\geq 0$ , for any $I\subseteq \{1,\dots ,n\}$ .

The Shannon inequality says that an entropic vector is submodular:

3)\quad H(X_{I})+H(X_{J})\geq H(X_{I\cup J})+H(X_{I\cap J})

, for any

I,J\subseteq \{1,\dots ,n\}

It is equivalent to the inequality stating that the conditional mutual information is non-negative:

{\begin{aligned}I(X;Y\mid Z)&=H(X\mid Z)-H(X\mid Y,Z)\\&=H(X\mid Z)+H(Y\mid Z)-H(X,Y\mid Z)\\&=H(X,Z)+H(Y,Z)-H(X,Y,Z)-H(Z)\\&\geq 0\end{aligned}}

(For one direction, observe this the last form expresses Shannon's inequality for subsets $X,Z$ and $Y,Z$ of the tuple $X,Y,Z$ ; for the other direction, substitute $X=X_{I}$ , $Y=X_{J}$ , $Z=X_{I\cap J}$ ).

Many inequalities can be derived as linear combinations of Shannon inequalities; they are called Shannon-type inequalities or basic information inequalities of Shannon's information measures.^[2] The set of vectors that satisfies them is called $\Gamma _{n}$ ; it contains $\Gamma _{n}^{*}$ .

Software has been developed to automate the task of proving Shannon-type inequalities.^[3]^[4] Given an inequality, such software is able to determine whether the given inequality is a valid Shannon-type inequality (i.e., whether it contains the cone $\Gamma _{n}$ ).

Non-Shannon-type inequalities

The question of whether Shannon-type inequalities are the only ones, that is, whether they completely characterize the region $\Gamma _{n}^{*}$ , was first asked by Te Su Han in 1981^[2] and more precisely by Nicholas Pippenger in 1986.^[5] It is not hard to show that this is true for two variables, that is, $\Gamma _{2}^{*}=\Gamma _{2}$ . For three variables, Zhang and Yeung^[1] proved that $\Gamma _{3}^{*}\neq \Gamma _{3}$ ; however, it is still asymptotically true, meaning that the closure is equal: ${\overline {\Gamma _{3}^{*}}}=\Gamma _{3}$ . In 1998, Zhang and Yeung^[2]^[6] showed that ${\overline {\Gamma _{n}^{*}}}\neq \Gamma _{n}$ for all $n\geq 4$ , by proving that the following inequality on four random variables (in terms of conditional mutual information) is true for any entropic vector, but is not Shannon-type:

2I(X_{3};X_{4})\leq I(X_{1};X_{2})+I(X_{1};X_{3},X_{4})+3I(X_{3};X_{4}|X_{1})+I(X_{3};X_{4}|X_{2})

Further inequalities and infinite families of inequalities have been found.^[7]^[8]^[9]^[10] These inequalities provide outer bounds for ${\overline {\Gamma _{n}^{*}}}$ better than the Shannon-type bound $\Gamma _{n}$ . In 2007, Matus proved that no finite set of linear inequalities is sufficient (to deduce all as linear combinations), for $n\geq 4$ variables. In other words, the region ${\overline {\Gamma _{4}^{*}}}$ is not polyhedral.^[11] Whether they can be characterized in some other way (allowing to effectively decide whether a vector is entropic or not) remains an open problem.

Analogous questions for von Neumann entropy in quantum information theory have been considered.^[12]

Inner bounds

Some inner bounds of ${\overline {\Gamma _{n}^{*}}}$ are also known. One example is that ${\overline {\Gamma _{4}^{*}}}$ contains all vectors in $\Gamma _{4}$ which additionally satisfy the following inequality (and those obtained by permuting variables), known as Ingleton's inequality for entropy:^[13]

I(X_{1};X_{2})+I(X_{3};X_{4}\mid X_{1})+I(X_{3};X_{4}\mid X_{2})-I(X_{3};X_{4})\geq 0

^[2]

Entropy and groups

Group-characterizable vectors and quasi-uniform distributions

Consider a group $G$ and subgroups $G_{1},G_{2},\dots ,G_{n}$ of $G$ . Let $G_{I}$ denote $\bigcap _{i\in I}G_{i}$ for $I\subseteq \{1,\dots ,n\}$ ; this is also a subgroup of $G$ . It is possible to construct a probability distribution for $n$ random variables $X_{1},\dots ,X_{n}$ such that

H(X_{I})=\log {\frac {|G|}{|G_{I}|}}

.^[14]

(The construction essentially takes an element $a$ of $G$ uniformly at random and lets $X_{i}$ be the corresponding coset $aG_{i}$ ). Thus any information-theoretic inequality implies a group-theoretic one. For example, the basic inequality $H(X,Y)\leq H(X)+H(Y)$ implies that

|G|\cdot |G_{1}\cap G_{2}|\geq |G_{1}|\cdot |G_{2}|.

It turns out the converse is essentially true. More precisely, a vector is said to be group-characterizable if it can be obtained from a tuple of subgroups as above. The set of group-characterizable vectors is denoted $\Upsilon ^{n}$ . As said above, $\Upsilon ^{n}\subseteq \Gamma _{n}^{*}$ . On the other hand, $\Gamma _{n}^{*}$ (and thus ${\overline {\Gamma _{n}^{*}}}$ ) is contained in the topological closure of the convex closure of $\Upsilon ^{n}$ .^[15] In other words, a linear inequality holds for all entropic vectors if and only if it holds for all vectors $h$ of the form $h_{I}=\log {\frac {|G|}{|G_{I}|}}$ , where $I$ goes over subsets of some tuple of subgroups $G_{1},G_{2},\dots ,G_{n}$ in a group $G$ .

Group-characterizable vectors that come from an abelian group satisfy Ingleton's inequality.

Kolmogorov complexity

Kolmogorov complexity satisfies essentially the same inequalities as entropy. Namely, denote the Kolmogorov complexity of a finite string $x$ as $K(x)$ (that is, the length of the shortest program that outputs $x$ ). The joint complexity of two strings $x,y$ , defined as the complexity of an encoding of the pair $\langle x,y\rangle$ , can be denoted $K(x,y)$ . Similarly, the conditional complexity can be denoted $K(x|y)$ (the length of the shortest program that outputs $x$ given $y$ ). Andrey Kolmogorov noticed these notions behave similarly to Shannon entropy, for example:

K(a)+K(b)\geq K(a,b)-O(\log |a|+\log |b|)

In 2000, Hammer et al.^[16] proved that indeed an inequality holds for entropic vectors if and only if the corresponding inequality in terms of Kolmogorov complexity holds up to logarithmic terms for all tuples of strings.

Related Research Articles

In information theory, the entropy of a random variable is the average level of "information", "surprise", or "uncertainty" inherent to the variable's possible outcomes. Given a discrete random variable $, which takes values in the alphabet and is distributed according to :$

In probability theory and statistics, the chi-squared distribution with $degrees of freedom is the distribution of a sum of the squares of independent standard normal random variables. The chi-squared distribution is a special case of the gamma distribution and is one of the most widely used probability distributions in inferential statistics, notably in hypothesis testing and in construction of confidence intervals. This distribution is sometimes called the central chi-squared distribution, a special case of the more general noncentral chi-squared distribution.$

In probability theory, Chebyshev's inequality guarantees that, for a wide class of probability distributions, no more than a certain fraction of values can be more than a certain distance from the mean. Specifically, no more than 1/k² of the distribution's values can be k or more standard deviations away from the mean. The rule is often called Chebyshev's theorem, about the range of standard deviations around the mean, in statistics. The inequality has great utility because it can be applied to any probability distribution in which the mean and variance are defined. For example, it can be used to prove the weak law of large numbers.

In probability theory and statistics, the moment-generating function of a real-valued random variable is an alternative specification of its probability distribution. Thus, it provides the basis of an alternative route to analytical results compared with working directly with probability density functions or cumulative distribution functions. There are particularly simple results for the moment-generating functions of distributions defined by the weighted sums of random variables. However, not all random variables have moment-generating functions.

In vector calculus, Green's theorem relates a line integral around a simple closed curve $C$ to a double integral over the plane region $D$ bounded by $C$ . It is the two-dimensional special case of Stokes' theorem.

In probability theory and statistics, the Rayleigh distribution is a continuous probability distribution for nonnegative-valued random variables. Up to rescaling, it coincides with the chi distribution with two degrees of freedom. The distribution is named after Lord Rayleigh.

<span class="mw-page-title-main">Joint entropy</span> Measure of information in probability and information theory

In information theory, joint entropy is a measure of the uncertainty associated with a set of variables.

<span class="mw-page-title-main">Dirichlet distribution</span> Probability distribution

In probability and statistics, the Dirichlet distribution (after Peter Gustav Lejeune Dirichlet), often denoted $, is a family of continuous multivariate probability distributions parameterized by a vector of positive reals. It is a multivariate generalization of the beta distribution, hence its alternative name of multivariate beta distribution (MBD) . Dirichlet distributions are commonly used as prior distributions in Bayesian statistics, and in fact, the Dirichlet distribution is the conjugate prior of the categorical distribution and multinomial distribution.$

In information theory, the Rényi entropy is a quantity that generalizes various notions of entropy, including Hartley entropy, Shannon entropy, collision entropy, and min-entropy. The Rényi entropy is named after Alfréd Rényi, who looked for the most general way to quantify information while preserving additivity for independent events. In the context of fractal dimension estimation, the Rényi entropy forms the basis of the concept of generalized dimensions.

In statistics and information theory, a maximum entropy probability distribution has entropy that is at least as great as that of all other members of a specified class of probability distributions. According to the principle of maximum entropy, if nothing is known about a distribution except that it belongs to a certain class, then the distribution with the largest entropy should be chosen as the least-informative default. The motivation is twofold: first, maximizing entropy minimizes the amount of prior information built into the distribution; second, many physical systems tend to move towards maximal entropy configurations over time.

Differential entropy is a concept in information theory that began as an attempt by Claude Shannon to extend the idea of (Shannon) entropy, a measure of average (surprisal) of a random variable, to continuous probability distributions. Unfortunately, Shannon did not derive this formula, and rather just assumed it was the correct continuous analogue of discrete entropy, but it is not. The actual continuous version of discrete entropy is the limiting density of discrete points (LDDP). Differential entropy is commonly encountered in the literature, but it is a limiting case of the LDDP, and one that loses its fundamental association with discrete entropy.

In information theory, information dimension is an information measure for random vectors in Euclidean space, based on the normalized entropy of finely quantized versions of the random vectors. This concept was first introduced by Alfréd Rényi in 1959.

Fourier–Motzkin elimination, also known as the FME method, is a mathematical algorithm for eliminating variables from a system of linear inequalities. It can output real solutions.

In information theory, the entropy power inequality (EPI) is a result that relates to so-called "entropy power" of random variables. It shows that the entropy power of suitably well-behaved random variables is a superadditive function. The entropy power inequality was proved in 1948 by Claude Shannon in his seminal paper "A Mathematical Theory of Communication". Shannon also provided a sufficient condition for equality to hold; Stam (1959) showed that the condition is in fact necessary.

Inequalities are very important in the study of information theory. There are a number of different contexts in which these inequalities appear.

In probability theory, the family of complex normal distributions, denoted $or, characterizes complex random variables whose real and imaginary parts are jointly normal. The complex normal family has three parameters: location parameter μ, covariance matrix, and the relation matrix . The standard complex normal is the univariate distribution with,, and .$

In probability theory, concentration inequalities provide bounds on how a random variable deviates from some value. The law of large numbers of classical probability theory states that sums of independent random variables are, under very mild conditions, close to their expectation with a large probability. Such sums are the most basic examples of random variables concentrated around their mean. Recent results show that such behavior is shared by other functions of independent random variables.

In mathematics, a submodular set function is a set function that, informally, describes the relationship between a set of inputs and an output, where adding more of one input has a decreasing additional benefit. The natural diminishing returns property which makes them suitable for many applications, including approximation algorithms, game theory and electrical networks. Recently, submodular functions have also found immense utility in several real world problems in machine learning and artificial intelligence, including automatic summarization, multi-document summarization, feature selection, active learning, sensor placement, image collection summarization and many other domains.

In mathematics and physics, Lieb–Thirring inequalities provide an upper bound on the sums of powers of the negative eigenvalues of a Schrödinger operator in terms of integrals of the potential. They are named after E. H. Lieb and W. E. Thirring.

The hyperbolastic functions, also known as hyperbolastic growth models, are mathematical functions that are used in medical statistical modeling. These models were originally developed to capture the growth dynamics of multicellular tumor spheres, and were introduced in 2005 by Mohammad Tabatabai, David Williams, and Zoran Bursac. The precision of hyperbolastic functions in modeling real world problems is somewhat due to their flexibility in their point of inflection. These functions can be used in a wide variety of modeling problems such as tumor growth, stem cell proliferation, pharma kinetics, cancer growth, sigmoid activation function in neural networks, and epidemiological disease progression or regression.

References

1 2 Zhang, Z.; Yeung, R.W. (1997). "A Non-Shannon-Type Conditional Inequality of Information Quantities". IEEE Trans. Inf. Theory. 43 (6): 1982–1986. doi:10.1109/18.641561.
1 2 3 4 Zhang, Z.; Yeung, R.W. (1998). "On Characterization of Entropy Function via Information Inequalities". IEEE Trans. Inf. Theory. 44 (4): 1440–1452. doi:10.1109/18.681320.
↑ Yeung, R.W.; Yan, Y.O. (1996). "ITIP - Information Theoretic Inequality Prover".{{cite journal}}: Cite journal requires |journal= (help)
↑ Pulikkoonattu, R.; E.Perron, E.; S.Diggavi, S. (2007). "Xitip - Information Theoretic Inequalities Prover".{{cite journal}}: Cite journal requires |journal= (help)
↑ Kaced, Tarik (2013). Equivalence of Two Proof Techniques for Non-Shannon-type Inequalities. 2013 IEEE International Symposium on Information Theory. arXiv: 1302.2994 .
↑ Yeung. A First Course in Information Theory, Theorem 14.7
↑ Dougherty, R.; Freiling, C.; Zeger, K. (2006). Six New Non-Shannon Information Inequalities. 2006 IEEE International Symposium on Information Theory.
↑ Matus, F. (1999). "Conditional independences among four random variables III: Final conclusion". Combinatorics, Probability and Computing . 8 (3): 269–276. doi:10.1017/s0963548399003740. S2CID 121634597.
↑ Makarychev, K.; et al. (2002). "A new class of non-Shannon-type inequalities for entropies". Communications in Information and Systems. 2 (2): 147–166. doi: 10.4310/cis.2002.v2.n2.a3 .
↑ Zhang, Z. (2003). "On a new non-Shannon-type information inequality". Communications in Information and Systems. 3 (1): 47–60. doi: 10.4310/cis.2003.v3.n1.a4 .
↑ Matus, F. (2007). Infinitely many information inequalities. 2007 IEEE International Symposium on Information Theory.
↑ Linden; Winter (2005). "A New Inequality for the von Neumann Entropy". Commun. Math. Phys. 259 (1): 129–138. arXiv: quant-ph/0406162 . Bibcode:2005CMaPh.259..129L. doi:10.1007/s00220-005-1361-2. S2CID 13279358.
↑ Yeung. A First Course in Information Theory, p. 386
↑ Yeung. A First Course in Information Theory, Theorem 16.16
↑ Yeung. A First Course in Information Theory, Theorem 16.22
↑ Hammer; Romashchenko; Shen; Vereshchagin (2000). "Inequalities for Shannon Entropy and Kolmogorov Complexity". Journal of Computer and System Sciences. 60 (2): 442–464. doi: 10.1006/jcss.1999.1677 .

Thomas M. Cover, Joy A. Thomas. Elements of information theory New York: Wiley, 1991. ISBN 0-471-06259-6
Raymond Yeung. A First Course in Information Theory, Chapter 12, Information Inequalities, 2002, Print ISBN 0-306-46791-7

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[ZhangYeung95-1] 1 2 Zhang, Z.; Yeung, R.W. (1997). "A Non-Shannon-Type Conditional Inequality of Information Quantities". IEEE Trans. Inf. Theory. 43 (6): 1982–1986. doi:10.1109/18.641561.

[ZhangYeung-2] 1 2 3 4 Zhang, Z.; Yeung, R.W. (1998). "On Characterization of Entropy Function via Information Inequalities". IEEE Trans. Inf. Theory. 44 (4): 1440–1452. doi:10.1109/18.681320.

[3] Yeung, R.W.; Yan, Y.O. (1996). "ITIP - Information Theoretic Inequality Prover".{{cite journal}}: Cite journal requires |journal= (help)

[4] Pulikkoonattu, R.; E.Perron, E.; S.Diggavi, S. (2007). "Xitip - Information Theoretic Inequalities Prover".{{cite journal}}: Cite journal requires |journal= (help)

[5] Kaced, Tarik (2013). Equivalence of Two Proof Techniques for Non-Shannon-type Inequalities. 2013 IEEE International Symposium on Information Theory. arXiv: 1302.2994 .

[6] Yeung. A First Course in Information Theory, Theorem 14.7

[7] Dougherty, R.; Freiling, C.; Zeger, K. (2006). Six New Non-Shannon Information Inequalities. 2006 IEEE International Symposium on Information Theory.

[8] Matus, F. (1999). "Conditional independences among four random variables III: Final conclusion". Combinatorics, Probability and Computing . 8 (3): 269–276. doi:10.1017/s0963548399003740. S2CID 121634597.

[9] Makarychev, K.; et al. (2002). "A new class of non-Shannon-type inequalities for entropies". Communications in Information and Systems. 2 (2): 147–166. doi: 10.4310/cis.2002.v2.n2.a3 .

[10] Zhang, Z. (2003). "On a new non-Shannon-type information inequality". Communications in Information and Systems. 3 (1): 47–60. doi: 10.4310/cis.2003.v3.n1.a4 .

[matus2007-11] Matus, F. (2007). Infinitely many information inequalities. 2007 IEEE International Symposium on Information Theory.

[12] Linden; Winter (2005). "A New Inequality for the von Neumann Entropy". Commun. Math. Phys. 259 (1): 129–138. arXiv: quant-ph/0406162 . Bibcode:2005CMaPh.259..129L. doi:10.1007/s00220-005-1361-2. S2CID 13279358.

[13] Yeung. A First Course in Information Theory, p. 386

[14] Yeung. A First Course in Information Theory, Theorem 16.16

[15] Yeung. A First Course in Information Theory, Theorem 16.22

[16] Hammer; Romashchenko; Shen; Vereshchagin (2000). "Inequalities for Shannon Entropy and Kolmogorov Complexity". Journal of Computer and System Sciences. 60 (2): 442–464. doi: 10.1006/jcss.1999.1677 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

Entropic vector

Contents

Definition

Example