The entropic vector or entropic function is a concept arising in
information theory
Information theory is the scientific study of the quantification (science), quantification, computer data storage, storage, and telecommunication, communication of information. The field was originally established by the works of Harry Nyquist a ...
. 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
, their joint entropy (the entropy of the random variable representing the pair
) is at most the sum of the entropies of
and of
:
:
Other information-theoretic measures such as
conditional information
In information theory, the conditional entropy quantifies the amount of information needed to describe the outcome of a random variable Y given that the value of another random variable X is known. Here, information is measured in shannons, na ...
,
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
variables, no finite set of linear inequalities is sufficient to characterize all entropic vectors.
Definition
Shannon's
information entropy of a random variable
is denoted
.
For a tuple of random variables
, we denote the
joint entropy of a subset
as
, or more concisely as
, where
.
Here
can be understood as the random variable representing the tuple
.
For the empty subset
,
denotes a deterministic variable with entropy 0.
A vector ''h'' in
indexed by subsets of
is called an ''entropic vector'' of order
if there exists a tuple of random variables
such that
for each subset
.
The set of all entropic vectors of order
is denoted by
.
Zhang and Yeung
proved that it is not closed (for
), but its
closure,
, is a
convex cone and hence characterized by the (infinitely many) linear inequalities it satisfies.
Describing the region
is thus equivalent to characterizing all possible inequalities on joint entropies.
Example
Let ''X'',''Y'' be two independent random variables with
discrete uniform distribution
In probability theory and statistics, the discrete uniform distribution is a symmetric probability distribution wherein a finite number of values are equally likely to be observed; every one of ''n'' values has equal probability 1/''n''. Anothe ...
over the set
. Then
:
(since each is uniformly distributed over a two-element set), and
:
(since the two variables are independent, which means the pair
is uniformly distributed over
.)
The corresponding entropic vector is thus:
On the other hand, the vector
is not entropic (that is,
), because any pair of random variables (independent or not) should satisfy
.
Characterizing entropic vectors: the region Γ''n''*
Shannon-type inequalities and Γ''n''
For a tuple of random variables
, their entropies satisfy:
:
:
, for any
In particular,
, for any
.
The Shannon inequality says that an entropic vector is
submodular
In mathematics, a submodular set function (also known as a submodular function) is a set function whose value, informally, has the property that the difference in the incremental value of the function that a single element makes when added to an ...
:
:
, for any
It is equivalent to the inequality stating that the
conditional mutual information
In probability theory, particularly information theory, the conditional mutual information is, in its most basic form, the expected value of the mutual information of two random variables given the value of a third.
Definition
For random var ...
is non-negative:
:
(For one direction, observe this the last form expresses Shannon's inequality for subsets
and
of the tuple
; for the other direction, substitute
,
,
).
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.
The set of vectors that satisfies them is called
; it contains
.
Software has been developed to automate the task of proving Shannon-type inequalities.
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
).
Non-Shannon-type inequalities
The question of whether Shannon-type inequalities are the only ones, that is, whether they completely characterize the region
, was first asked by Te Su Han in 1981
and more precisely by
Nicholas Pippenger
Nicholas John Pippenger is a researcher in computer science. He has produced a number of fundamental results many of which are being widely used in the field of theoretical computer science, database processing and compiler optimization. He has ...
in 1986.
It is not hard to show that this is true for two variables, that is,
.
For three variables, Zhang and Yeung
proved that
; however, it is still asymptotically true, meaning that the closure is equal:
.
In 1998, Zhang and Yeung
showed that
for all
, 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:
:
Further inequalities and infinite families of inequalities have been found.
These inequalities provide outer bounds for
better than the Shannon-type bound
.
In 2007, Matus proved that no finite set of linear inequalities is sufficient (to deduce all as linear combinations), for
variables. In other words, the region
is not polyhedral.
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.
Inner bounds
Some inner bounds of
are also known.
One example is that
contains all vectors in
which additionally satisfy the following inequality (and those obtained by permuting variables), known as
Ingleton's inequality
In mathematics, Ingleton's inequality is an inequality that is satisfied by the rank function of any representable matroid. In this sense it is a necessary condition for representability of a matroid over a finite field. Let ''M'' be a matroid an ...
for entropy:
:
Entropy and groups
Group-characterizable vectors and quasi-uniform distributions
Consider a
group and subgroups
of
.
Let
denote
for
; this is also a subgroup of
.
It is possible to construct a probability distribution for
random variables
such that
:
.
(The construction essentially takes an element
of
uniformly at random and lets
be the corresponding
coset ). Thus any information-theoretic inequality implies a group-theoretic one. For example, the basic inequality
implies that
:
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
.
As said above,
.
On the other hand,
(and thus
) is contained in the topological closure of the convex closure of
.
In other words, a linear inequality holds for all entropic vectors if and only if it holds for all vectors
of the form
, where
goes over subsets of some tuple of subgroups
in a group
.
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
as
(that is, the length of the shortest program that outputs
).
The joint complexity of two strings
, defined as the complexity of an encoding of the pair
, can be denoted
.
Similarly, the
conditional complexity can be denoted
(the length of the shortest program that outputs
given
).
Andrey Kolmogorov noticed these notions behave similarly to Shannon entropy, for example:
:
In 2000, Hammer et al.
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.
See also
*
Inequalities in information theory
References
* Thomas M. Cover, Joy A. Thomas. ''Elements of information theory'' New York: Wiley, 1991.
* Raymond Yeung. ''A First Course in Information Theory'', Chapter 12, ''Information Inequalities'', 2002, Print {{ISBN, 0-306-46791-7
Information theory