Wasserstein continuity of entropy and outer bounds for interference channels

Introduction

One motivation comes from multi-user information theory, where frequently one user causes interference to the other and in proving the converse one wants to replace the complicated non-i.i.d. interference by a simpler i.i.d. approximation. As a concrete example, we consider the so-called “missing corner point” problem in the capacity region of the two-user Gaussian interference channels (GIC) [Cos85a]. Perhaps due to the explosion in the number of interfering radio devices, this problem has attracted renewed attention recently [Cos11, BPS14, CR15, RC15]. For further information on capacity region of GIC and especially the problem of corner points, we refer to a comprehensive account just published by Igal Sason [Sas15].

Mathematically, the key question for settling “missing corner point” is the following: Given independent $n$-dimensional random vectors $X_{1},X_{2},G_{2},Z$ with the latter two being Gaussian, is it true that

The rationale of the above discussion is two-fold: a) Certain regularity conditions of the distributions must be imposed; b) Distances other than KL divergence might be more suited for bounding the entropy difference. Correspondingly, the main contribution of this paper is the following: Under suitable regularity conditions, the difference in entropy (in both continuous and discrete cases) can in fact be bounded by the Wasserstein distance, a notion originating from optimal transportation theory which turns out to be the main tool of this paper.

where $\|\cdot\|$ denotes the Euclidean distance and the infimum is taken over all couplings of $P$ and $Q$, i.e., joint distributions $P_{XY}$ whose marginals satisfy $P_{X}=P$ and $P_{Y}=Q$. The following dual representation of the $W_{1}$ distance is useful:

Furthermore, transportation-information inequalities, such as those due to Marton [Mar86] and Talagrand [Tal96], allow us to bound the Wasserstein distance by the KL divergence (see, e.g., [RS13] for a review). For example, Talagrand’s inequality states that if $Q={\mathcal{N}}(0,\Sigma)$, then

where $\sigma_{\max}(\Sigma)$ denotes the maximal singular value of $\Sigma$. Invoking (5) in conjunction with the Wasserstein continuity of the differential entropy, we establish (2) and prove a new outer bound for the capacity region of the two-user GIC, finally settling the missing corner point in [Cos85a]. See Section 3 for details.

One interesting by-product is an estimate that goes in the reverse direction of (5). Namely, under regularity conditions on $P$ and $Q$ we haveFor positive $a,b$, denote $a\lesssim b$ if $a/b$ is at most some universal constant.

Wasserstein-continuity of information quantities

Notice that in particular, regular density is never zero and furthermore

Therefore, if $X$ has a regular density and finite second moment then

Let $U$ and $V$ be random vectors with finite second moments. If $V$ has a $(c_{1},c_{2})$-regular density $p_{V}$, then there exists a coupling $P_{UV}$, such that

If both $U$ and $V$ are $(c_{1},c_{2})$-regular, then

where (12) follows from Cauchy-Schwartz inequality and the $(c_{1},c_{2})$-regularity of $p_{V}$. Taking expectation of (13) with respect to $(u,v)$ distributed according to the optimal $W_{2}$-coupling of $P_{U}$ and $P_{V}$ and then applying Cauchy-Schwartz and triangle inequality for $L_{2}$-norm, we obtain (7).

To show (8) notice that by finiteness of second moment $h(U)<\infty$. If $h(U)=-\infty$ then there is nothing to prove. So assume otherwise, then in identity

all terms are finite and hence (8) follows. Clearly, (8) implies (9) (when applied with $U$ and $V$ interchanged).

Finally, for (10) just add the identity (14) to itself with $U$ and $V$ interchanged to obtain

The key question now is what densities are regular. It turns out that convolution with sufficiently smooth density, such as Gaussians, produces a regular density.

First notice that whenever density $p_{Z}$ of $Z$ is differentiable and non-vanishing, we have:

For this, we mirror the proof in [WV12, Lemma 4]. Indeed, we have

Another useful criterion for regularity is the following:

If $W$ has $(c_{1},c_{2})$-regular density and B\mathchoice{\mathrel{\hbox to0.0pt{\displaystyle\perp\hss}\mkern 2.0mu{\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{\textstyle\perp\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptstyle\perp\hss}\mkern 2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptscriptstyle\perp\hss}\mkern 2.0mu{\scriptscriptstyle\perp}}}W satisfies

then $V=B+W$ has $(c_{1},c_{2}+c_{1}\sqrt{nP})$-regular density.

As a consequence of regularity, we show that when smoothed by Gaussian noise, mutual information, differential entropy and divergence are Lipschitz with respect to the $W_{2}$-distance under average power constraints:

In fact, to get the best constants for applications to interference channels it is best to forgo the notion of regular density and deal directly with (15). Indeed, when the inputs has bounded norms, the next result gives a sharpened version of what can be obtained by combining Proposition 1 with 2.

Let $B$ satisfying (21) and $G\sim\mathcal{N}(0,\sigma_{G}^{2}I_{n})$ be independent. Let $V=B+G$. Then for any $U$,

Plugging Gaussian density $p_{G}(z)=\frac{1}{\sqrt{2\pi}\sigma_{G}}e^{-z^{2}/(2\sigma_{G}^{2})}$ into (15) we get

since $\|B\|\leq\sqrt{nP}$ almost surely. Next we use

Taking expectation of the last equation under the $W_{1}$-optimal coupling and in view of (14), we obtain (24). ∎

To get slightly better constants in one-sided version of (22) we apply Proposition 5:

Let $A,B,G,Z$ be independent, with $G\sim{\mathcal{N}}(0,\sigma_{G}^{2}I_{n})$, $Z\sim{\mathcal{N}}(0,\sigma_{Z}^{2}I_{n})$ and $B$ satisfying (21). Then for every $c\in$ we have:

First, notice that by definition Wasserstein distance is non-increasing under convolutions, i.e., $W_{2}(P_{1}*Q,P_{2}*Q)\leq W_{2}(P_{1},P_{2})$. Since $c\leq 1$ and Gaussian distribution is stable, we have

which, in turn, can be bounded via Talagrand’s inequality (5) by

From here we apply Proposition 5 with $G$ replaced by $G+Z$ (and $\sigma_{G}^{2}$ by $\sigma_{Z}^{2}+\sigma_{G}^{2}$). ∎

Applications to Gaussian interference channels

Consider the two-user Gaussian interference channel (GIC):

with $a,b\geq 0$, $Z_{i}\sim\mathcal{N}(0,I_{n})$ and a power constraint on the $n$-letter codebooks: either

Denote by ${\mathcal{R}}(a,b)$ the capacity region of the GIC (30). As an application of the results developed in Section 2, we prove an outer bound for the capacity region.

Assume the average power constraint (32). Then (33) holds with $\delta$ replaced by

Consequently, in both cases, $R_{2}\geq C_{2}-\epsilon$ implies that $R_{1}\leq\frac{1}{2}\log(1+\frac{a^{2}P_{1}}{1+P_{2}})-\epsilon^{\prime}$ where $\epsilon^{\prime}=O(\sqrt{\epsilon})$ as $\epsilon\to 0$.

Without loss of generality, assume that all random variables have zero mean. First of all, setting $b=0$ (which is equivalent to granting the first user access to $X_{2}$) will not shrink the capacity region of the interference channel (30). Therefore to prove the desired outer bound it suffices to focus on the following Z-interference channel henceforth:

Let $(X_{1},X_{2})$ be $n$-dimensional random variables corresponding to the encoder output of the first and second user, which are uniformly distributed on the respective codebook. For $i=1,2$ define

By Fano’s inequality there is no difference asymptotically between this definition of rate and the operational one. Define the entropy-power function of the $X_{1}$-codebook:

We know the following general properties of $N_{1}(t)$:

$N_{1}(0)=0$ (since $X_{1}$ is uniform over the codebook).

$N_{1}^{\prime}(t)\geq 2\pi e$ (since $N_{1}(t+\delta)\geq N_{1}(t)+2\pi e\delta$ by entropy power inequality).

$N_{1}(t)$ is concave (Costa’s entropy power inequality [Cos85a]).

$N_{1}(t)\leq 2\pi e(P_{1}+t)$ (Gaussian maximizes differential entropy).

We can then express $R_{1}$ in terms of the entropy power function as

It remains to upper bound $N_{1}(1)$. Note that

where $A$ is defined in (34). This in conjunction with the slope property $N_{1}^{\prime}(t)\geq 2\pi e$ yields

which, in view of (38), yields the first part of the bound (33).

Note that the second term (43) is precisely $\frac{n}{2}\log\frac{N_{1}(\frac{1}{a^{2}})}{N_{1}(\frac{1+P_{2}}{a^{2}})}$. The first term (42) can be bounded by applying Corollary 6 and (41) with $B=aX_{1}$, $A=X_{2}$, $G=G_{2}$ and $c=1$:

where $\delta$ is defined in (35). From the concavity of $N_{1}(t)$ and (45)

where $\gamma=1+{1-a^{2}\over P_{2}}>1$. In view of (38), upper bounding $N_{1}\left({1/a^{2}}\right)$ in (47) via (39) we get after some simplifications the second part of (33).

The outer bound for average power constraint (32) follows analogously with (44) replaced by (48) below: By Proposition 2, the density of $aX_{1}+G_{2}+Z_{2}$ is $(\frac{3\log e}{1+P2},\frac{4a\log e\sqrt{nP_{1}}}{1+P2})$-regular. Applying Proposition 1 to (44), we have $h(aX_{1}+X_{2}+Z_{2})-h(aX_{1}+G_{2}+Z_{2})\leq\Delta$, where

Again using the fact that $W_{2}$ distance is non-decreasing under convolutions and invoking Talagrand’s inequality, we have

This yields the outer bound with $\delta^{\prime}$ defined in (36).

Finally, in both cases, when $R_{2}\to C_{2}$, we have $\delta\to 0$ and $A\to\frac{1}{a^{2}}+\frac{P_{2}}{1+P_{1}}$ and hence from (33) $R_{1}\leq C_{1}^{\prime}$. ∎

The first part of the bound (33) coincides with Sato’s outer bound [Sat78] and [Kra04, Theorem 2] by Kramer, which [Kra04, Theorem 2] was obtained by reducing the Z-interference channel to the degraded broadcast channel; the second part of (33) is new, which settles the missing corner point of the capacity region (see Section 3.2 for discussions). Note that our estimates on $N_{1}(1)$ in the proof of Theorem 7 are tight in the sense that there exists a concave function $N_{1}(t)$ satisfying the listed general properties, estimates (45) and (39) as well as attaining the minimum of (40) and (47) at $N_{1}(1)$. Hence, tightening the bound via this method would require inferring more information about $N_{1}(t)$.

The outer bound (33) relies on Costa’s EPI. To establish the second statement about corner point, it is sufficient to invoke the concavity of $\gamma\mapsto I(X_{2};\sqrt{\gamma}X_{2}+Z_{2})$ [GSSV05, Corollary 1], which is strictly weaker than Costa’s EPI.

The outer bound (33) is evaluated on Fig. 1 for the case of $b=0$ (Z-interference), where we also plot (just for reference) the simple Han-Kobayashi inner bound for the Z-GIC (37) attained by choosing $X_{1}=U+V$ with U\mathchoice{\mathrel{\hbox to0.0pt{\displaystyle\perp\hss}\mkern 2.0mu{\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{\textstyle\perp\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptstyle\perp\hss}\mkern 2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptscriptstyle\perp\hss}\mkern 2.0mu{\scriptscriptstyle\perp}}}V jointly Gaussian. This achieves rates:

For more sophisticated Han-Kobayashi bounds see [Sas04, Cos11].

2 Corner points of the capacity region

The two corner points of the capacity region are defined as follows:

Below we present a brief account of the corner points in various cases; for an extensive discussion see [Sas15]. We start with a few simple observations about the capacity region $\mathcal{R}(a,b)$:

Any rate pair satisfying the following belongs to $\mathcal{R}(a,b)$:

which corresponds to the intersection of two Gaussian multiple-access (MAC) capacity regions, namely, $(X_{1},X_{2})\to Y_{1}$ and $(X_{1},X_{2})\to Y_{2}$. These rate pairs correspond to the case when each receiver decodes both messages.

For $a>1$ and $b>1$ (strong interference) the capacity region is known to coincide with (52) [Car75, Sat81]. So, without loss of generality we assume $a\leq 1$ henceforth.

Replacing either $a$ or $b$ with zero can only enlarge the region (genie argument).

If $b\geq 1$ then for any $(R_{1},R_{2})\in\mathcal{R}(a,b)$ we have [Sat81]

This follows from the observation that in this case $I(X_{1},X_{2};Y_{1})=H(X_{1},X_{2})-o(n)$, since conditioned on $X_{1}$, $Y_{2}$ is a noisier observation of $X_{2}$ than $Y_{1}$.

For the top corner, we have the following:

Note that for any $b\geq 0$, $a\mapsto C_{1}^{\prime}(a,b)$ is discontinuous as $a\downarrow 0$. To verify (54) we consider each case separately:

For $a>0$ the converse bound follows from Theorem 7. For achievability, we consider two cases. When $b\leq 1$, we have ${a^{2}P_{1}\over 1+P_{2}}\leq\frac{P_{1}}{1+b^{2}P_{2}}$ and therefore treating interference $X_{2}$ as noise at the first receiver and using a Gaussian MAC-code for $(X_{1},X_{2})\to Y_{2}$ works. For $b>1$, the achievability follows from the MAC inner bound (52). Note that since ${1\over 2}\log\left(1+{P_{1}+b^{2}P_{2}}\right)\geq{1\over 2}\log\left(1+{P_{2}+a^{2}P_{1}}\right)$, a Gaussian MAC-code that works for $(X_{1},X_{2})\to Y_{2}$ will also work for $(X_{1},X_{2})\to Y_{1}$. Alternatively, the achievability also follows from Han-Kobayashi inner bound (see, e.g., [EGK11, Theorem 6.4] with $(U_{1},U_{2})=(X_{1},X_{2})$ for $b\geq 1$ and $(U_{1},U_{2})=(X_{1},0)$ for $b\leq 1$).

For $a=0$ and $b\geq\sqrt{1+P_{1}}$ the converse is obvious, while for achievability we have that ${b^{2}P_{2}\over 1+P_{1}}\leq P_{2}$ and therefore $X_{2}$ is decodable at $Y_{1}$.

For $a=0$ and $1<b<\sqrt{1+P_{1}}$ the converse is (53) and the achievability is just the MAC code $(X_{1},X_{2})\to Y_{1}$ with rate $R_{2}=C_{2}$.

For $a=0$ and $0<b\leq 1$ the result follows from the treatment of $C_{2}^{\prime}(a,b)$ below by interchanging $a\leftrightarrow b$ and $P_{1}\leftrightarrow P_{2}$.

The bottom corner point is given by the following:

which is discontinuous as $b\downarrow 0$ for any fixed $a\in$. We treat each case separately:

The case of $C_{2}^{\prime}(a,0)$ is due to Sato [Sat78] (see also [Kra04, Theorem 2]). The converse part also follows from Theorem 7 (for $a=0$ there is nothing to prove). For the achievability, we notice that under $b\geq\sqrt{1+P_{1}\over 1+a^{2}P_{1}}$ we have ${b^{2}P_{2}\over 1+P_{1}}>{P_{2}\over 1+a^{2}P_{1}}$ and thus $X_{2}$ at rate $C_{2}^{\prime}(a,0)$ can be decoded and canceled from $Y_{1}$ by simply treating $X_{1}$ as Gaussian noise (as usual, we assume Gaussian random codebooks). Thus the problem reduces to that of $b=0$. For $b=0$, the Gaussian random coding achieves the claimed result if the second receiver treats $X_{1}$ as Gaussian noise.

The converse follows from (53) and for the achievability we use the Gaussian MAC-code $(X_{1},X_{2})\to Y_{1}$ and treat $X_{1}$ as Gaussian interference at $Y_{2}$.

If $b\in(0,1]$, we apply results on $C_{1}^{\prime}(a,b)$ in (54) by interchanging $a\leftrightarrow b$ and $P_{1}\leftrightarrow P_{2}$.

Discrete version

Fix a finite alphabet $\mathcal{X}$ and an integer $n$. On the product space $\mathcal{X}^{n}$ we define the Hamming distance

and consider the corresponding Wasserstein distance $W_{1}$. In fact, $\frac{1}{n}W_{1}(P,Q)$ is known as Ornstein’s $\bar{d}$-distance [GNS75, Mar86], namely,

where the infimum is taken over all couplings $P_{XY}$ of $P$ and $Q$. For $n=1$, this coincides with the total variation, which is also expressible as $d_{\rm TV}(P,Q)=\frac{1}{2}\int|dP-dQ|$ for $P,Q$ on ${\mathcal{X}}$.

For a pair of distributions $P,Q$ on $\mathcal{X}^{n}$ we may ask the following questions:

Does $D(P\|Q)$ control the entropy difference $H(P)-H(Q)$?

Does $\bar{d}(P,Q)$ control the entropy difference $H(P)-H(Q)$?

Recall that in the Euclidean space the answer to both questions was negative unless the distributions satisfy certain regularity conditions. For discrete alphabets the answer to the first question is still negative in general (see Section 1 for a counterexample); nevertheless, the answer to the second one turns out to be positive:

Let $P$ and $Q$ be distributions on $\mathcal{X}^{n}$ and let

In fact, the statement holds for any translation-invariant distance $d(\cdot,\cdot)$ on ${\mathcal{X}}$ extended additively to ${\mathcal{X}}^{n}$, i.e., $d(x,x^{\prime})=\sum_{i=1}^{n}d(x_{i},x^{\prime}_{i})$ for any $x,x^{\prime}\in{\mathcal{X}}^{n}$. Indeed, define

where $x_{0}\in\mathcal{X}^{n}$ is an arbitrary fixed string. It is easy to see that $s\mapsto f_{n}(s)$ is concave since $P\mapsto H(P)$ is. Furthermore, writing $X=(X_{1},\ldots,X_{n})$ and applying chain-rule for entropy we get

Thus, letting $X,Y$ be distributed according to the $\bar{d}$-optimal coupling of $P$ and $Q$, we get

where (59) is by definition of $f_{n}(\cdot)$ and (60) is by Jensen’s inequality. Finally, for the Hamming distance we have $f_{1}(s)=F_{\mathcal{X}}(s)$ by Fano’s inequality. ∎

Notice that the right-hand side of (57) behaves like $n\bar{d}\log\frac{1}{\bar{d}}$ when $\bar{d}(P,Q)$ is small. This super-linear dependence is in fact sharp.To see this, consider $Q=\text{Bern}(p)^{\otimes n}$ and choose $P$ to be the output distribution of the optimal lossy compressor for $Q$ at average distortion $\delta n$. By definition, $\bar{d}(P,Q)\leq\delta$. On the other hand, $H(P)=n(h(p)-h(\delta)+o(1))$ as $n\to\infty$ and hence $|H(P)-H(Q)|=n(h(\delta)+o(1))$, which asymptotically meets the upper bound (57) with equality. Nevertheless, if certain regularity of distributions is assumed, the estimate (57) can be improved to be linear in $\bar{d}(P,Q)$. The next result is the analog of Proposition 1 in the discrete space. We formulate it in a form convenient for applications in multi-user information theory.

Let $P_{Y|X,A}$ be a two-input blocklength-$n$ memoryless channel, namely

Applying (66) and (67) to $Y$ and $(X,A)$ gives (61) and (62) with $L=c$ defined in (64).

To bound the mutual information, we first notice

Applying (66) conditioned on $X=x$ we get

where $c_{x}=\max_{j\in[n]}\max_{y,y^{\prime},a}\log\frac{W(y|x_{j},a)}{W(y^{\prime}|x_{j},a)}$. Note that $c_{x}\leq c$ for any $x$, averaging over $P_{X}$ gives

2 Marton’s transportation inequality

In this section we discuss how previous bounds (Proposition 8 and 9) in terms of the $\bar{d}$-distance can be converted to bounds in terms of KL divergence. This is possible when $Q$ is a product distribution, thanks to Marton’s transportation inequality [Mar86, Lemma 1]. We formulate this together with a few other properties of the ${\bar{d}}$-distance in the following lemma proved in Appendix A.

(Marton’s transportation inequality [Mar86]): For any pair of distributions $P$ and $Q=\prod_{i=1}^{n}Q_{i}$ on $\mathcal{X}^{n}$,

(Tensorization) $\bar{d}(\prod_{i=1}^{n}P_{i},\prod_{i=1}^{n}Q_{i})\leq\frac{1}{n}\sum_{i=1}^{n}d_{\rm TV}(P_{i},Q_{i})$.

(Contraction) For $P_{XY}$ and $Q_{XY}$ such that $P_{Y|X}=Q_{Y|X}=\prod_{i=1}^{n}P_{Y_{i}|X_{i}}$,

where $\eta_{\rm TV}(W)$ is Dobrushin’s contraction coefficient of a Markov kernel $W$ defined as $\eta_{\rm TV}(W)=\sup_{x,x^{\prime}}d_{\rm TV}(W(\cdot|x),W(\cdot|x^{\prime}))$.

If we assume that $D(P\|Q)=\epsilon n$ for some small $\epsilon$, then combining (57) and (69) gives

where the right-hand side behaves as $n\sqrt{\epsilon}\log\frac{1}{\epsilon}$ when $\epsilon\to 0$. This estimate has a one-sided improvement (here again $Q$ must be a product distribution):

(see [CS07] for $n=1$ and [WV10, Appendix H] for the general case).

which is the maximal Dobrushin contraction coefficients among all channels $W(\cdot|\cdot,x)$ indexed by $x\in{\mathcal{X}}$. Then

where the left inequality is by convexity of the $\bar{d}$-distance as a Wasserstein distance, the middle inequality is by Lemma 10, and the right inequality is via (69). An alternative to the estimate (73) is the following:

3 Application: corner points for discrete interference channels

In order to apply Proposition 9 to determine corner points of capacity regions of discrete memoryless interference channels (DMIC) we will need an auxiliary tensorization result. This result appears to be a rather standard exercise for degraded channels and so we defer the proof to Appendix B.

Given channels $P_{A|X}$ and $P_{B|A}$ on finite alphabets, define

(Tensorization) For any blocklength-$n$ Markov chain $X^{n}\to A^{n}\to B^{n}$, where $P_{A^{n}|X^{n}}=P_{A|X}^{\otimes n}$ and $P_{B^{n}|A^{n}}=P_{B|A}^{\otimes n}$ are $n$-letter memoryless channels, we have

Neither of the sufficient condition (80) and (81) for strict inequality is superfluous, as can be seen from the example $B=A$ and A\mathchoice{\mathrel{\hbox to0.0pt{\displaystyle\perp\hss}\mkern 2.0mu{\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{\textstyle\perp\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptstyle\perp\hss}\mkern 2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptscriptstyle\perp\hss}\mkern 2.0mu{\scriptscriptstyle\perp}}}X, respectively; in both cases $F_{c}(t)=t$.

The important consequence of Proposition 11 is the following implication:This is the analog of the following property of Gaussian channels, exploited in Theorem 7 in the form of Costa’s EPI: For i.i.d. Gaussian $Z$ and $t_{1}<t_{2}<t_{3}$ we have $I(X;X+t_{2}Z)=I(X;X+t_{3}Z)+o(n)\implies I(X;X+t_{1}Z)=I(X;X+t_{3}Z)+o(n)\,.$ This also follows from the concavity of $\gamma\mapsto I(X;\sqrt{\gamma}X+Z)$.

By Proposition 11, we have $F_{c}(t)<t$ for all $t>0$. This together with the concavity of $F_{c}$ implies that $t\mapsto t-F_{c}(t)$ is convex, strictly increasing and strictly positive on $(0,\infty)$. Define $g$ as the inverse of $t\mapsto t-F_{c}(t)$, which is increasing and concave and satisfies $g(0)=0$. Since $I(X^{n};A^{n})\leq I(X^{n};B^{n})+\epsilon n$, the tensorization result (79) yields

i.e., $t\leq F_{c}(t)+\epsilon$, where $t\triangleq{1\over n}H(X^{n}|B^{n})$. Then $t\leq g(\epsilon)$ by definition, completing the proof. ∎

We are now ready to state a non-trivial example of corner points for the capacity region of DMIC. The proof strategy mirrors that of Theorem 7, with Corollary 6 and Costa’s EPI replaced by Proposition 9 and Corollary 12, respectively.

where $X_{1}\in\{0,1,2\}^{n}$, $X_{2}\in\{0,1\}^{n},Z_{2}\in\{0,1,2\}^{n}$ are independent and $Z_{2}\sim P_{2}^{\otimes n}$ is i.i.d. for some non-uniform $P_{2}$ containing no zeros. The maximal rate achievable by user 2 is

At this rate the maximal rate of user 1 is

As an example, consider $P_{2}=\left[{1-\delta},{\delta\over 2},{\delta\over 2}\right]$ where $\delta\neq 0,1,\frac{1}{3}$. Then the maximum in (86) is achieved by $Q=[\frac{1}{2},\frac{1}{2}]$. Therefore $C_{2}=H(P_{3})-H(P_{2})$ and $C_{1}^{\prime}=\log 3-H(P_{3})$, where $P_{3}=\left[{2-\delta\over 4},{2-\delta\over 4},{\delta\over 2}\right]$. Note that in the case of $\delta=\frac{1}{3}$, where Theorem 13 is not applicable, we simply have $C_{2}=0$ and $C_{1}^{\prime}=\log 2$ since X_{2}\mathchoice{\mathrel{\hbox to0.0pt{\displaystyle\perp\hss}\mkern 2.0mu{\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{\textstyle\perp\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptstyle\perp\hss}\mkern 2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptscriptstyle\perp\hss}\mkern 2.0mu{\scriptscriptstyle\perp}}}Y_{2}. Therefore the corner point is discontinuous in $\delta$.

Theorem 13 continues to hold even if cost constraints are imposed. Indeed, if $X_{2}\in\{0,1,2\}^{n}$ is required to satisfy

Applying (63) in Proposition 9 and in view of the translation invariance of the $\bar{d}$-distance, we obtain

where $c=\max_{z,z^{\prime}\in\{0,1,2\}}\log\frac{P_{2}(z)}{P_{2}(z^{\prime})}$ and $\alpha=\frac{2c}{\sqrt{2\log e}}$ are finite since $P_{2}$ contains no zeros by assumption. On the other hand,

where $I(X_{1};X_{2}|Y_{2})\leq H(X_{2}|Y_{2})=o(n)$ by Fano’s inequality. Combining the last two displays, we have

Finally, note that the rate pair $(C_{1}^{\prime},C_{2})$ is achievable by a random MAC-code for $(X_{1},X_{2})\to Y_{2}$, with $X_{1}$ uniform on $\{0,1,2\}^{n}$ and $X_{2}\sim Q_{2}^{\otimes n}$. ∎

Acknowledgment

Explaining that the “missing corner point” requires proving of (2), as well as the majority of our knowledge on interference channels were provided by Prof. Chandra Nair. We acknowledge his scholarship and patience deeply.

The research of Y.P. has been supported in part by the Center for Science of Information (CSoI), an NSF Science and Technology Center, under grant agreement CCF-09-39370 and by the NSF CAREER award under grant agreement CCF-12-53205. The research of Y.W. has been supported in part by NSF grants IIS-14-47879, CCF-14-23088 and CCF-15-27105. This work would not be possible without the generous support of the Simons Institute for the Theory of Computing and California SB-420.

Appendix A Proof of Lemma 10

Appendix B Proof of Proposition 11

Basic properties of $F_{c}$ follow from standard arguments. To show the strict inequality $F_{c}(t)<t$ under the conditions (80) and (81), we first notice that $F_{c}$ is simply the concave envelope of the set of achievable pairs $(H(X|A),H(X|B))$ obtained by iterating over all $P_{X}$. By Caratheodory’s theorem, it is sufficient to consider a ternary-valued $U$ in the optimization defining $F_{c}(t)$. Then the set of achievable pairs $(H(X|A,U),H(X|B,U))$ is convex and compact (as the continuous image of the compact set of distributions $P_{U,X}$). Consequently, to have $F_{c}(t)=t$ there must exist a distribution $P_{U,X}$, such that

We next show that under the extra conditions on $P_{B|A}$ and $P_{A|X}$ we must have $t=0$. Indeed, (80) guarantees the channel $P_{B|A}$ satisfies the strong data processing inequality (see, e.g., [CK11, Exercise 15.12 (b)] and [PW16, Section 1.2] for a survey) that there exists $\eta<1$ such that

From (90) and (91) we infer that $I(X;A|U)=0$, or equivalently

On the other hand, the condition (81) ensures that then we must have $H(X|U)=0$. Clearly, this implies $t=0$ in (90).

To show the single-letterization statement (82), we only consider the case of $n=2$ since the generalization is straightforward by induction. Let $X^{2}\to A^{2}\to B^{2}$ be a Markov chain with blocklength-$2$ memoryless channel in between. We have

where (93) is because $B_{2}\to X_{2}\to X_{1}\to B_{1}$ and hence $I(X_{2};B_{1}|X_{2}B_{2})=0$, and (94) is because $B_{1}\to X_{1}\to A_{2}\to B_{2}$. Next consider the chain

where (96) is by $A_{2}\to X_{2}\to X_{1}\to A_{1}$ and hence $I(X_{2};A_{1}|X_{1},A_{2})=0$, (97) is by the definition of $F_{c}$ and since we have both $A_{2}\to X_{1}\to A_{1}\to B_{1}$ and $X_{1}\to X_{2}\to A_{2}\to B_{2}$, (98) is by the concavity of $F_{c}$, and finally (99) is by the monotonicity of $F_{c}$ and (94). ∎

References