On the Entropy of Couplings

Introduction

Distributions with fixed marginals have been studied extensively in the probability literature (see for example and the references therein). They are closely related to (and sometimes identified with, as will be the case in this paper) the concept of coupling, which has proven to be a very useful proof technique in probability theory , and in particular in the theory of Markov chains . In statistics, a related notion of contingency tables is of considerable importance . There is also rich literature on the geometrical and combinatorial properties of sets of distributions with given marginals, which are known as transportation polytopes in this context (see, e.g., ). We investigate here these objects from a certain information-theoretic perspective. Our results and the general outline of the paper are briefly described below.

In Section 2 we recall the definitions and elementary properties of the quantities under study, namely, information-theoretic functionals and couplings. Notational conventions are also introduced here.

In Section 3 we discuss properties of Shannon information measures under constraints on the marginal distributions. In particular, certain optimization problems associated with these functionals are studied. Most of them are, in a sense, the reverses of the well-known optimization problems, such as the maximum entropy principle, channel capacity, and information projections. The general problems of entropy minimization, maximization of mutual information, and maximization of information divergence are all shown to be intractable. Since mutual information is a good measure of dependence of two random variables, this will also lead to a similar result for all measures of dependence satisfying Rényi’s axioms, and to a statistical scenario where this result might be of interest. Furthermore, these problems are found to be basically information-theoretic restatements of some well-known problems in complexity theory. The infinite-alphabet case is also discussed in this section, in particular the questions of continuity and existence of extrema.

In Section 4 we define a family of (pseudo)metrics on the space of probability distributions, that is based on the so-called minimum entropy coupling in the same way as the total variation distance is based on the maximal coupling. The relation between these distances is derived from Fano’s inequality. Other properties of the new metrics are also discussed, in particular an interesting characterization of the conditional entropy that they yield.

Preliminaries

Shannon entropy of a random variable $X$ with probability distribution $P=(p_{i})$ is defined as

with the usual convention $0\log 0=0$ being understood. $H$ is a strictly concave functional in $P$ . Further, for a pair of random variables $(X,Y)$ with joint distribution $S=(s_{i,j})$ and respective marginal distributions $P=(p_{i})$ and $Q=(q_{j})$, the following defines their joint entropy

again with appropriate conventions. The above quantities, usually referred to as the Shannon information measures , are all related by simple identities

The equalities on the right-hand sides of (6)–(8) are attained if and only if $X$ and $Y$ are independent. The equalities on the left-hand sides of (6) and (7) are attained if and only if $X$ deterministically depends on $Y$ (i.e., iff $X$ is a function of $Y$), or vice versa. The equality on the left-hand side of (8) holds if and only if $X$ deterministically depends on $Y$. We will use some of these properties in our proofs; for their demonstration we point the reader to the standard reference .

From identities (5) one immediately observes the following: Over a set of bivariate probability distributions with fixed marginals (and hence fixed marginal entropies $H(X)$ and $H(Y)$), all the above functionals differ up to an additive constant (and a minus sign in the case of mutual information), and hence one can focus on studying only one of them and easily translate the results for the others. This fact will also be exploited later.

Relative entropy (information divergence, Kullback-Leibler divergence) of the distribution $P$ with respect to the distribution $Q$ is the following functional

where $0\log\frac{0}{q}=0$ and $p\log\frac{p}{0}=\infty$ for every $q\geq 0$, $p>0$.

2 Couplings of probability distributions

Let $\Gamma_{n}^{(1)}$ and $\Gamma_{n\times m}^{(2)}$ denote the sets of one- and two-dimensional probability distributions with alphabets of size $n$ and $n\times m$, respectively

and let $\mathcal{C}(P,Q)$ denote the set of all couplings of $P\in\Gamma_{n}^{(1)}$ and $Q\in\Gamma_{m}^{(1)}$

The set of distributions with fixed marginals is basically the set of matrices with nonnegative entries and prescribed row and column sums. Such sets are special cases of the so-called transportation polytopes .

We will also find it interesting to study information measures over the sets of distributions whose one marginal and the support of the other are fixed

These sets are also convex polytopes and form a partition of $\Gamma_{n\times m}^{(2)}$ when $P$ varies through $\Gamma_{n}^{(1)}$.

Information measures and couplings

In the following we analyze some general properties of Shannon information measures, as well as natural optimization problems associated with these functionals, over domains of the form ${\mathcal{C}}(P,Q)$ and ${\mathcal{C}}(P,m)$. The proofs presented are not difficult, but they have a number of important consequences, as discussed in Section 3.3. Some closely related problems over ${\mathcal{C}}(P,Q)$, in the context of computing the metric $\underline{\Delta}_{1}(P,Q)$ (defined in Section 4), are also studied in .

Due to (5), we can focus on the optimization of $H_{X,Y}$ only. In regard to this, we introduce the following definition, whose relevance will be demonstrated throughout this and the following section.

Minimum entropy coupling of probability distributions $P$ and $Q$ is a bivariate distribution $S^{*}\in{\mathcal{C}}(P,Q)$ that minimizes the entropy functional $H\equiv H_{X,Y}$, i.e.,

Note that the maximization of entropy over ${\mathcal{C}}(P,Q)$ is trivial – the maximizer is always $P\times Q=(p_{i}q_{j})$.

Minimum entropy couplings exist for any $P\in\Gamma_{n}^{(1)}$ and $Q\in\Gamma_{m}^{(1)}$ because sets ${\mathcal{C}}(P,Q)$ are compact (closed and bounded) and entropy is continuous over $\Gamma_{n\times m}^{(2)}$ and hence attains its extrema. Note, however, that they need not be unique. From the strict concavity of entropy one concludes that the minimum entropy couplings must be vertices of the polytope ${\mathcal{C}}(P,Q)$ (i.e., they cannot be expressed as $\lambda S+(1-\lambda)T$, with $S,T\in{\mathcal{C}}(P,Q)$, $\lambda\in(0,1)$). Finally, from identities (5) it follows that the minimizers of $H_{X,Y}$ over ${\mathcal{C}}(P,Q)$ are simultaneously the minimizers of $H_{X|Y}$ and $H_{Y|X}$ and the maximizers of $I_{X;Y}$, and hence could also be called maximum mutual information couplings for example.

From the last observation we see that minimum entropy couplings express the largest dependence (measured by $I_{X;Y}$) of random variables having particular marginal distributions; this is further discussed in Section 3.3.4.

The problem at hand is a constrained optimization problem, and we will use a standard result in the field – the Berge’s maximum theorem [40, Thm 9.14]. To see that the conditions of the theorem are satisfied, observe that entropy is continuous over $\Gamma_{n\times m}^{(2)}$, and that the mapping $(P,Q)\mapsto{\mathcal{C}}(P,Q)$, viewed as a correspondence The term correspondence denotes a set-valued map (i.e., multi-valued map). Much of the study of such maps was motivated by their applications in mathematical economics. For a definition of continuity of correspondences, as well as the related notions of lower and upper hemi-continuity, see ., is compact-valued and continuous . $\blacksquare$

Berge’s maximum theorem also implies that the mapping $(P,Q)\mapsto\operatorname{arg\,inf}_{S\in{\mathcal{C}}(P,Q)}H(S)$, which maps distributions $P,Q$ to the set of minimum entropy couplings in ${\mathcal{C}}(P,Q)$, is a compact-valued upper hemi-continuous correspondence on $\Gamma_{n}^{(1)}\times\Gamma_{m}^{(1)}$. It is in fact finite-valued because minimum entropy couplings are necessarily vertices of ${\mathcal{C}}(P,Q)$, as commented above. In the following we analyze the computational complexity of finding an element of the set $\operatorname{arg\,inf}_{S\in{\mathcal{C}}(P,Q)}H(S)$.

Positive integers $d_{1},\ldots,d_{n}$ and $s$.

Is there a $J\subseteq\{1,\ldots,n\}$ such that $\sum_{j\in J}d_{j}=s$ ?

We demonstrate a reduction from the Subset sum to the Minimum entropy coupling. Let there be given an instance of the Subset sum, i.e., a set of positive integers $s;d_{1},\ldots,d_{n}$, $n\geq 2$. Let $D=\sum_{i=1}^{n}d_{i}$, and let $p_{i}=d_{i}/D$, $q=s/D$ (assume that $s<D$, the problem otherwise being trivial). Denote $P=(p_{1},\ldots,p_{n})$ and $Q=(q,1-q)$. The question we are trying to answer is whether there is a $J\subseteq\{1,\ldots,n\}$ such that $\sum_{j\in J}d_{j}=s$, i.e., such that $\sum_{j\in J}p_{j}=q$. Observe that this happens if and only if there is a matrix $S$ with row sums $P=(p_{1},\ldots,p_{n})$ and column sums $Q=(q,1-q)$, which has exactly one nonzero entry in every row (or, in probabilistic language, a distribution $S\in{\mathcal{C}}(P,Q)$ such that $Y$ deterministically depends on $X$). We know that in this case, and only in this case, the entropy of $S$ would be equal to $H(P)$ , which is by (6) a lower bound on entropy over ${\mathcal{C}}(P,Q)$. In other words, if such a distribution exists, it must be the minimum entropy coupling. Therefore, if we could find the minimum entropy coupling, we could easily decide whether it has one nonzero entry in every row, thereby solving the given instance of the Subset sum. $\blacksquare$

We have shown that the problem of deciding whether there is a distribution $S\in{\mathcal{C}}(P,Q)$ with $H(S)=H(P)$ is NP-complete even when the distribution $Q$ is allowed to have only two masses. In this case it is equivalent to the Subset sum problem and represents its information theoretic analogue (and it implies the hardness of the Minimum entropy coupling). When this restriction on $Q$ is removed, the problem is equivalent to deciding whether there exist subsets with prescribed sums $s_{1},\ldots,s_{m}$. This problem is NP-complete in the strong sense because it is a generalization of the 3-Partition problem which we recall below. Since the reduction in the proof of the previous theorem is clearly pseudo-polynomial (it is just a division of all numbers by $D$), it follows that Minimum entropy coupling is strongly NP-hard.

It would be interesting to determine whether the Minimum entropy coupling belongs to FNP , but this appears to be quite difficult. Namely, given the optimal solution, it is not obvious how to verify (in polynomial time) that it is indeed optimal. A similar situation arises with the decision version of this problem: Given $P$ and $Q$ and a threshold $h$, is there a distribution $S\in{\mathcal{C}}(P,Q)$ with entropy $H(S)\leq h$? Whether this problem belongs to NP is another interesting question (which we will not be able to answer here). We will not go into these details further; we mention instead one closely related problem which has been studied in the literature:

Positive integers $d_{1},\ldots,d_{n}$, and $k$.

Decide whether $\sum_{i=1}^{n}\sqrt{d_{i}}\leq k$ ?

This problem, though “conceptually simple” and bearing certain resemblance with the above decision version of the entropy minimization problem, is not known to be solvable in NP (it is solvable in PSPACE).

2 Optimization over 𝒞​(P,m)𝒞𝑃𝑚{\mathcal{C}}(P,m)

Optimal channel with $m$ outputs and input distribution $P$ is a bivariate distribution $S^{*}\in{\mathcal{C}}(P,m)$ that maximizes the mutual information functional, i.e.,

Since $H(X)$ is fixed, maximizing $I_{X;Y}$ over ${\mathcal{C}}(P,m)$ is equivalent to minimizing the conditional entropy $H(X|Y)$, and is the only interesting optimization problem over domains of this form. Namely, the minimizer of $H(X,Y)$ and $H(Y|X)$ over ${\mathcal{C}}(P,m)$ is any joint distribution having at most one nonzero entry in each row (i.e., such that $Y$ deterministically depends on $X$), and the maximizer is $P\times U_{m}$, where $U_{m}$ is the uniform distribution over $\{1,\ldots,m\}$.

By the Berge’s maximum theorem we have the following claim.

We will use the well-known Partition (or Number partitioning) problem .

Is there a partition of $\{d_{1},\ldots,d_{n}\}$ into two subsets with equal sums?

This is clearly a special case of the Subset sum. It can be solved in pseudo-polynomial time by dynamic programming methods . But the following closely related problem is much harder.

Positive integers $d_{1},\ldots,d_{3m}$ with $s/4<d_{j}<s/2$, where $s=\sum_{j}d_{j}/m$.

Is there a partition of $\{1,\ldots,3m\}$ into $m$ subsets $J_{1},\ldots,J_{m}$ (disjoint and covering $\{1,\ldots,3m\}$) such that $\sum_{j\in J_{i}}d_{j}$ are all equal? (The sums are necessarily $s$ and every $J_{i}$ has $3$ elements.)

This problem is NP-complete in the strong sense , i.e., no pseudo-polynomial time algorithm for it exists unless P=NP.

We prove the claim by reducing 3-Partition to Optimal channel. Let there be given an instance of the 3-Partition as described above, and let $p_{i}=d_{i}/D$, where $D=\sum_{i}d_{i}$. Observe that a partition with desired properties exists if and only if there is a matrix $C\in\mathcal{C}(P,m)$, $P=(p_{i})$, having column sums $s/D=1/m$ and having exactly one nonzero entry in every row (i.e., if and only if a bivariate distribution $C\in\mathcal{C}(P,m)$ exists with the uniform second marginal $\left(\frac{1}{m},\ldots,\frac{1}{m}\right)$, and such that $Y$ deterministically depends on $X$). Furthermore, a distribution $C\in\mathcal{C}(P,m)$ has such properties if and only if it satisfies $I_{X;Y}(C)=\log m$ (to see this, observe that (i) $I_{X;Y}(S)\leq H(S_{Y})$, where $S_{Y}$ is the second marginal of $S$, with equality if and only if $S$ has at most one nonzero entry in every row, and (ii) $H(S_{Y})\leq\log m$, whenever $S\in\mathcal{C}(P,m)$, with equality if and only if $S_{Y}$ is uniform). Since $\log m$ is an upper bound on $I_{X;Y}$ over $\mathcal{C}(P,m)$, such a distribution $C$ would necessarily be the maximizer of $I_{X;Y}$. To conclude, if we could solve the Optimal channel with instance $(p_{1},\ldots,p_{3m});m$, we could easily decide whether the maximizer has column sums $1/m$ and exactly one nonzero entry in every row, thereby solving the original instance of the 3-Partition.xxxxx $\blacksquare$

Note that the problem remains NP-hard even when the number of channel outputs ($m$) is fixed in advance and is not a part of the input instance. For example, maximization of $I_{X;Y}$ over ${\mathcal{C}}(P,2)$ is essentially equivalent to the Partition problem. Furthermore, since the transformation in the proof of Theorem 3.8 is pseudo-polynomial , Optimal channel is strongly NP-hard and, unless P=NP, has no pseudo-polynomial time algorithm.

3 Comments and generalizations

In this subsection we put the above optimization problems in a more general context, and discuss their relevance and certain generalizations.

Entropy minimization, taken in the broadest sense, is a very important problem. Watanabe has shown, for example, that many algorithms for clustering and pattern recognition can be characterized as suitably defined entropy minimization problems. In theoretical computer science, a class of combinatorial optimization problems based on entropy minimization has been studied extensively (see and the references therein). These include minimum entropy set cover, minimum entropy graph coloring, minimum entropy orientation, etc.

A much more familiar problem in information theory is that of entropy maximization. The so-called Maximum entropy principle formulated by Jaynes states that, among all probability distributions satisfying certain constraints (expressing our knowledge about the system), one should pick the one with maximum entropy. It has been recognized by Jaynes, as well as many other researchers, that this choice gives the least biased, the most objective distribution consistent with the information one possesses about the system. Consequently, the problem of maximizing entropy under constraints has been thoroughly studied (see, e.g., ). It has been argued, however, that minimum entropy distributions can also be of interest in many contexts. The MinMax information measure, for example, has been introduced as a measure of the amount of information contained in a given set of constraints, and it is based both on maximum and minimum entropy distributions.

One could formalize the problem of entropy minimization as follows: Given a polytope (by a system of inequalities with rational coefficients, say) in the set of probability distributions, find the distribution $S^{*}$ which minimizes the entropy functional $H$. (If the coefficients are rational, then all the vertices are rational, i.e., have rational coordinates. Therefore, the minimum entropy distribution has finite description and is well-defined as an output of a computational problem.) This problem is strongly NP-hard and remains such over transportation polytopes, as established above.

3.2 Rényi entropy minimization

Rényi entropy of order $\alpha\geq 0$ of a random variable $X$ with distribution $P$ is defined as

It was introduced by Rényi on axiomatic grounds as a generalization of the Shannon entropy, and represents an important functional in information theory. Joint Rényi entropy of the pair $(X,Y)$ having distribution $S=(s_{i,j})$ is naturally defined as

Due to subadditivity (for $\alpha<1$) and superadditivity (for $\alpha>1$) properties of the function $x^{\alpha}$ for $x\geq 0$, it follows that

Hence, as we have seen throughout this section, various problems from computational complexity theory can be reformulated as information-theoretic optimization problems. (Observe also the similarity of the Sqrt sum and the minimization of Rényi entropy of order $1/2$.)

3.3 Other information measures

Maximization of mutual information is also a problem of great importance in information theory. The so-called Maximum mutual information criterion has found many applications, e.g., for feature selection and the design of classifiers . Another familiar example is that of the capacity of a communication channel which is defined precisely as the maximum of the mutual information between the input and the output of a channel.

We have illustrated the general intractability of the problem of maximization of $I_{X;Y}$ by exhibiting two simple classes of polytopes over which the problem is strongly NP-hard. We also mention here one possible generalization of this problem – maximization of information divergence. Namely, since for $S\in{\mathcal{C}}(P,Q)$

one can naturally consider the more general problem of maximizing $D(S||T)$ when $S$ belongs to some convex region and $T$ is fixed. Related problems of finding maximizers of information divergence from exponential families have been studied in .

Formally, let Information divergence maximization be the following computational problem: Given a rational convex polytope $\mathcal{S}$ in the set of probability distributions, and a distribution $T$, find the distribution $S\in{\mathcal{S}}$ which maximizes $D(\cdot||T)$. This is again a convex maximization problem because $D(S||T)$ is convex in the pair $(S,T)$ .

Information divergence maximization is NP-hard. $\blacksquare$

Note that the reverse problem, namely the minimization of information divergence, defines an information projection of $T$ onto the region $\mathcal{S}$ .

3.4 Measures of statistical dependence

We conclude this subsection with one more generalization of the problem of maximization of mutual information. Namely, this problem can also be seen as a statistical problem of expressing the largest possible dependence between two given random variables.

Suppose we have two correlated information sources obtained by independent drawings from a discrete bivariate probability distribution, and suppose we only have access to individual streams of symbols (i.e., streams of symbols from either one of the sources, but not from both simultaneously) and can observe the relative frequencies of the symbols in each of the streams. We therefore “know” probability distributions of both sources (say $P$ and $Q$), but we don’t know how correlated they are. Then the “model” for this joint source would be ${\mathcal{C}}(P,Q)$. In the absence of any additional information, we must assume that some $S\in{\mathcal{C}}(P,Q)$ is the “true” distribution of the source.

Given such a model, we may ask the following question: What is the largest possible dependence of the two random variables? How correlated can they possibly be? This question can be made precise once a dependence measure is specified, and this is done next.

A. Rényi has formalized the notion of probabilistic dependence by presenting axioms which a “good” dependence measure $\rho$ should satisfy. These axioms, adapted for discrete random variables, are listed below.

$\rho(X,Y)$ is defined for any two random variables $X$, $Y$, neither of which is constant with probability $1$.

$\rho(X,Y)=0$ iff $X$ and $Y$ are independent.

If $f$ and $g$ are injective functions, then $\rho(f(X),g(Y))=\rho(X,Y)$.

Actually, Rényi considered axiom (E) to be too restrictive and demanded only the “if part”. It has been argued subsequently , however, that this is a substantial weakening. We will find it convenient to consider the stronger axiom given above. As an example of a good measure of dependence, one could take precisely the mutual information; its normalized variant $I(X;Y)/\min\{H(X),H(Y)\}$ satisfies all the above axioms.

Let $\rho$ be a measure of dependence satisfying axioms (A)–(F). Then maximal $\rho$–dependence is NP-hard. $\blacksquare$

The intractability of the problem over more general statistical models is now a simple consequence.

4 Infinite alphabets

We conclude this section with a discussion on the properties of information measures over domains of the form ${\mathcal{C}}(P,Q)$ and ${\mathcal{C}}(P,m)$ in the case when the distributions $P$ and $Q$ have possibly infinite supports. The notation is similar to the finite alphabet case, for example

A metric space is compact if and only if it is complete and totally bounded ; these facts are demonstrated below. $\blacksquare$

${\mathcal{C}}(P,Q)$ and ${\mathcal{C}}(P,m)$ are complete metric spaces.

and hence could not decrease to zero. The case of ${\mathcal{C}}(P,m)$ is similar. $\blacksquare$

For our next claim, recall that a set $E$ is said to be totally bounded if it has a finite covering by $\epsilon$-balls, for any $\epsilon>0$. In other words, for any $\epsilon>0$, there exist $x_{1},\ldots,x_{K}\in E$ such that $E\subseteq\bigcup_{k}{\mathcal{B}}(x_{k},\epsilon)$, where ${\mathcal{B}}(x_{k},\epsilon)$ denotes the open ball around $x_{k}$ of radius $\epsilon$. The points $x_{1},\ldots,x_{K}$ are then called an $\epsilon$-net for $E$.

${\mathcal{C}}(P,Q)$ and ${\mathcal{C}}(P,m)$ are totally bounded.

Understanding that $T_{k}(i,j)=0$ for $i>N$ or $j>N+1$, we have

Note that $S^{\prime}$ is not a distribution, but that does not affect the proof. Note also that the marginals of $S^{\prime}$ are bounded from above by the marginals of $S$, namely $q_{j}^{\prime}=\sum_{i}S^{\prime}(i,j)\leq q_{j}$ and $p_{i}^{\prime}=\sum_{j}S^{\prime}(i,j)\leq p_{i}$. Finally, we have ${\lVert S-S^{\prime}\rVert}_{1}<\frac{\epsilon}{3}$ because the total mass of $S$ on the coordinates where $i>N$ or $j>N$ is at most $\frac{\epsilon}{3}$. The next step is to create $S^{\prime\prime}\in{\mathcal{C}}(P^{(N)},Q^{(N,r)})$ by adding masses to $S^{\prime}$ on the $N\times(N+1)$ rectangle. One way to do this is as follows. Let

and let $U=(u_{i})$, and $V=(v_{j})$, and $c=\sum_{i}u_{i}=\sum_{j}v_{j}$ (to see that these two sums are equal write $\sum_{i}u_{i}-\sum_{j}v_{j}=\sum_{i=1}^{N}(p_{i}-p_{i}^{\prime})-\sum_{j=1}^{N}(q_{j}-q_{j}^{\prime})-r$ which is equal to zero by the definition of $r$ and due to the fact that $\sum_{i=1}^{N}p_{i}^{\prime}=\sum_{j=1}^{N}q_{j}^{\prime}=\sum_{i=1}^{N}\sum_{j=1}^{N}S(i,j)$). Now define $S^{\prime\prime}$ by

It is easy to verify that $S^{\prime\prime}\in{\mathcal{C}}(P^{(N)},Q^{(N,r)})$ and that ${\lVert S^{\prime}-S^{\prime\prime}\rVert}_{1}<\frac{\epsilon}{6}$ because the total mass added is

which completes the proof. $\blacksquare$

The following claim shows that imposing certain restrictions on the marginal distributions ensures the continuity of Shannon information measures and existence of their extrema. In contrast, without any restrictions, these functionals are known to be discontinuous at every point of $\Gamma^{(2)}$. (Entropy is, however, sequentially continuous at any power bounded distribution in the topology of information divergence [18, Thm 21]; this weaker notion of continuity is useful for many applications in probability theory.)

Continuity over ${\mathcal{C}}(P,Q)$ and ${\mathcal{C}}(P,m)$ is a special case of [19, Thm 4.3] and can thus be established by exhibiting cost-stable codes for these statistical models. We also give here a more direct proof (which can be extended to prove Theorem 3.16). Write

The functional $H_{Y|X}(S)=\sum_{i,j}s_{i,j}\log\frac{p_{i}}{s_{i,j}}$ is lower semi-continuous because it is a sum of nonnegative continuous functions. The functional $I_{X;Y}$ is also lower semi-continuous since

and information divergence $D(S||T)$ is known to be jointly lower semi-continuous in the distributions $S$ and $T$ [42, Thm 3.1]. But since the sum of these two functionals is a constant $H_{Y}(S)=H(Q)<\infty$, both of them must be continuous. The continuity of $H_{X|Y}$ and $H_{X,Y}$ follows from (5).

Now consider ${\mathcal{C}}(P,m)$. In it is shown that $H(Y|X)$ and $I(X;Y)$ are continuous when the alphabet of $Y$ is finite and fixed, which is what we have here. And since $H(X)=H(P)$ is fixed, $H(X|Y)$ and $H(X,Y)$ are also continuous (if $H(P)=\infty$ then they are infinite over the entire ${\mathcal{C}}(P,m)$, but we also take this to mean that they are continuous).

Uniform continuity and the fact that the above functionals attain their extrema over ${\mathcal{C}}(P,Q)$ and ${\mathcal{C}}(P,m)$ now follow from the compactness of these domains. $\blacksquare$

Regarding the extrema of information measures, we note that Proposition 3.2 fails in the case of unbounded alphabets (when $(P,Q)\in\Gamma^{(1)}\times\Gamma^{(1)}$). Namely, the functional $H_{\min}(P,Q)$ is discontinuous at every $(P,Q)$ with $H(P),H(Q)<\infty$. This follows easily from the discontinuity of entropy. However, Proposition 3.7 remains valid because $I_{X;Y}$ is continuous when one of the alphabets is finite .

The argument in the proof of Theorem 3.15 can easily be adapted to prove the following more general claim which gives necessary and sufficient conditions for the convergence of entropy in terms of other information measures.

Let $S\in\Gamma^{(2)}$ be a bivariate probability distribution with finite entropy, $H_{X,Y}(S)<\infty$. Then the following statements are equivalent:

$H_{X}$ and $H_{Y}$ are continuous at $S$,

$I_{X;Y}$, $H_{X|Y}$, and $H_{Y|X}$ are continuous at $S$.

Note first that when $S_{n}\to S$, then also $P_{n}\to P$, $Q_{n}\to Q$, and $P_{n}\times Q_{n}\to P\times Q$, where $P_{n},Q_{n}$, and $P,Q$ are the marginals of $S_{n}$ and $S$, respectively. Now all implications follow from (5) and the fact that the functionals in question are lower semi-continuous. $\blacksquare$

Metrics from couplings

Apart from many of their other uses, couplings are very convenient for defining metrics on the space of probability distributions. There are many interesting metrics defined via so-called “optimal” couplings. We illustrate this point below using one familiar example, and then define new information-theoretic metrics based on the minimum entropy coupling. Similar approaches are also used in the literature for defining measures of distortion (that are not necessarily metrics) between random objects; see, e.g., for the corresponding definitions and their applications in rate distortion theory.

We next define information-theoretic distances in a similar manner.

Let $(X,Y)$ be a random pair with joint distribution $S$ and marginal distributions $P$ and $Q$. The total information contained in these random variables is $H(X,Y)$, while the information contained simultaneously in both of them (or the information they contain about each other) is measured by $I(X;Y)$. One is then tempted to take as a measure of their dissimilarity Drawing a familiar information-theoretic Venn diagram makes it clear that this is a measure of “dissimilarity” of two random variables.

Indeed, this quantity (introduced by Shannon , and usually referred to as the entropy metric ) satisfies the properties of a pseudometric . In a similar way one can show that the following is also a pseudometric

as are the normalized variants of $\Delta_{1}$ and $\Delta_{\infty}$ . These pseudometrics have found numerous applications (see for example ) and have also been considered in an algorithmic setting .

for $p\geq 1$. Observe that $\lim_{p\to\infty}\Delta_{p}(X,Y)=\Delta_{\infty}(X,Y)$, justifying the notation.

$\Delta_{p}(X,Y)$ satisfies the properties of a pseudometric, for all $p\in[1,\infty]$.

Nonnegativity and symmetry are clear, as is the fact that $\Delta_{p}(X,Y)=0$ if (but not only if) $X=Y$ with probability one. The triangle inequality remains. Following the proof for $\Delta_{1}$ from [12, Lemma 3.7], we first observe that $H(X|Y)\leq H(X|Z)+H(Z|Y)$, wherefrom

Now apply the Minkowski inequality (${\lVert a+b\rVert}_{p}\leq{\lVert a\rVert}_{p}+{\lVert b\rVert}_{p}$) to the vectors $a=(H(X|Z),H(Z|X))$ and $b=(H(Z|Y),H(Y|Z))$ to get

$\Delta_{p}$ are pseudometrics on the space of random variables over the same probability space. Namely, for $\Delta_{p}$ to be defined, the joint distribution of $(X,Y)$ must be given because joint entropy and mutual information are not defined otherwise. Equation (43) below defines the distance between random variables (more precisely, between their distributions) that does not depend on the joint distribution.

Having defined measures of dissimilarity, we can now define the corresponding distances

The case $p=1$ has also been analyzed in some detail in , motivated by the problem of optimal order reduction for stochastic processes.

$\underline{\Delta}_{p}$ is a pseudometric on $\Gamma^{(1)}$, for any $p\in[1,\infty]$.

Since ${\Delta}_{p}$ satisfies the properties of a pseudometric, we only need to show that these properties are preserved under the infimum. Nonnegativity and symmetry are clearly preserved. Also, if $P=Q$ then $\underline{\Delta}_{p}(P,Q)=0$. This is because $S=\text{diag}(P)$ (distribution with masses $p_{i}=q_{i}$ on the diagonal and zeros elsewhere) belongs to ${\mathcal{C}}(P,Q)$ in this case, and for this distribution we have $H_{X|Y}(S)=H_{Y|X}(S)=0$. The triangle inequality is left. Let $X$, $Y$ and $Z$ be random variables with distributions $P$, $Q$ and $R$, respectively, and let their joint distribution be specified. We know that $\Delta_{p}(X,Y)\leq\Delta_{p}(X,Z)+\Delta_{p}(Z,Y)$, and we have to prove that

(${\mathcal{C}}(P,Q,R)$ denotes the set of all three-dimensional distributions with one-dimensional marginals $P$, $Q$, and $R$, as the notation suggests.) Let $T\in{\mathcal{C}}(P,R)$ and $U\in{\mathcal{C}}(R,Q)$ be the optimizing distributions on the right-hand side (rhs) of (46). Observe that there must exist a joint distribution $W\in{\mathcal{C}}(P,Q,R)$ consistent with $T$ and $U$ (for example, take $w_{i,j,k}=t_{i,k}u_{k,j}/r_{k}$). Since the optimal value of the lhs is less than or equal to the value at $W$, we have shown that the lhs of (46) is less than or equal to the rhs. For the opposite inequality observe that the optimizing distribution on the lhs of (46) defines some two-dimensional marginals $T\in{\mathcal{C}}(P,R)$ and $U\in{\mathcal{C}}(R,Q)$, and the optimal value of the rhs must be less than or equal to its value at $(T,U)$. $\blacksquare$

If $\underline{\Delta}_{p}(P,Q)=0$, then $P$ and $Q$ are permutations of each other. This is easy to see because only in that case can one have $H_{X|Y}(S)=H_{Y|X}(S)=0$, for some $S\in\mathcal{C}(P,Q)$. Therefore, if distributions are identified up to a permutation, then $\underline{\Delta}_{p}$ is a metric. In other words, if we think of distributions as unordered multisets of nonnegative numbers summing up to one, then $\underline{\Delta}_{p}$ is a metric on such a space.

Observe that the distribution defining $\underline{\Delta}_{p}(P,Q)$ is in fact the minimum entropy coupling. Thus minimum entropy couplings define the distances $\underline{\Delta}_{p}$ on the space of probability distributions in the same way as the maximal coupling defines the total variation distance. However, there is a sharp difference in the computational complexity of finding these two couplings, as illustrated in the previous section.

2 Some properties of entropy metrics

Note that $\underline{\Delta}_{p}$ is a monotonically nonincreasing function of $p$. In the following, we will mostly deal with $\underline{\Delta}_{1}$ and $\underline{\Delta}_{\infty}$, but most results concerning bounds and convergence can be extended to all $\underline{\Delta}_{p}$ based on this monotonicity property.

The metric $\underline{\Delta}_{1}$ gives an upper bound on the entropy difference $|H(P)-H(Q)|$. Namely, since

Therefore, entropy is continuous with respect to this pseudometric, i.e., $\underline{\Delta}_{1}(P_{n},P)\to 0$ implies $H(P_{n})\to H(P)$. Bounding the entropy difference is an important problem in various contexts and it has been studied extensively, see for example . In particular, studies bounds on the entropy difference via maximal couplings, whereas (48) is obtained via minimum entropy couplings.

Another useful property, relating the entropy metric $\underline{\Delta}_{1}$ and the total variation distance, follows from Fano’s inequality

This relation makes sense only when the alphabets (supports of $P$ and $Q$) are finite. When the supports are also fixed it shows that $\underline{\Delta}_{1}$ is continuous with respect to $d_{\textsc{tv}}$, i.e., that $d_{\textsc{tv}}(P_{n},P)\to 0$ implies $\underline{\Delta}_{1}(P_{n},P)\to 0$. By the Pinsker-Csiszár-Kemperman inequality

it follows that $\underline{\Delta}_{1}$ is also continuous with respect to information divergence, i.e., $D(P_{n}||P)\to 0$ implies $\underline{\Delta}_{1}(P_{n},P)\to 0$.

The continuity of $\underline{\Delta}_{1}$ with respect to $d_{\textsc{tv}}$ fails in the case of infinite (or even finite, but unbounded) supports, which follows from (48) and the fact that entropy is a discontinuous functional with respect to the total variation distance. One can, however, claim the following.

If $P_{n}\to P$ in the total variation distance, and $H(P_{n})\to H(P)<\infty$, then $\underline{\Delta}_{1}(P_{n},P)\to 0$.

It should be pointed out that sharper bounds than the above can be obtained by using $\underline{\Delta}_{\infty}$ instead of $\underline{\Delta}_{1}$. For example

(with equality whenever the minimum entropy coupling of $P$ and $Q$ is such that $Y$ is a function of $X$, or vice versa), and

We conclude this section with an interesting remark on the conditional entropy. First observe that the pseudometric $\Delta_{p}$ ($\underline{\Delta}_{p}$) can also be defined for random vectors (multivariate distributions). For example, $\Delta_{1}((X,Y),(Z))$ is well-defined by $H(X,Y|Z)+H(Z|X,Y)$. If the distributions of $(X,Y)$ and $Z$ are $S$ and $R$, respectively, then minimizing the above expression over all tri-variate distributions with the corresponding marginals $S$ and $R$ would give $\underline{\Delta}_{1}(S,R)$. Furthermore, random vectors can even overlap. For example, we have

because the first summand is equal to zero. Therefore, the conditional entropy $H(Y|X)$ can be seen as the distance between the pair $(X,Y)$ and the conditioning random variable $X$. If the distribution of $(X,Y)$ is $S$, and the marginal distribution of $X$ is $P$, then

because $S$ is the only distribution consistent with these constraints. In fact, we have $\underline{\Delta}_{p}(P,S)=H_{Y|X}(S)$ for all $p\in[1,\infty]$. Therefore, the conditional entropy $H(Y|X)$ represents the distance between the joint distribution of $(X,Y)$ and the marginal distribution of the conditioning random variable $X$.

Conclusions

We have presented an information-theoretic view on probability distributions with fixed marginals. This well-studied topic still provides many interesting research problems and enables an interplay of several different fields. Various optimization problems associated with information measures over such sets of distributions were analyzed and shown to be intractable. Continuity questions and the existence of extrema of these functionals were also addressed (in the case of countably infinite alphabets). A family of information-theoretic pseudometrics was defined and their properties and relations to other metrics investigated. A central notion that was introduced in the paper and that represents a connecting point of the above-mentioned results is the minimum entropy coupling; the relevance of this notion was demonstrated in several respects.

Acknowledgments

The authors would like to thank the reviewers for carefully reading the manuscript and for providing many suggestions on how to improve it.

References