1

Random Coding Error Exponents for the Two-User
Interference Channel

arXiv:1503.02389v2 [cs.IT] 20 Jun 2017

Wasim Huleihel and Neri Merhav
The Andrew & Erna Viterbi Faculty of Electrical Engineering
Technion - Israel Institute of Technology
Haifa 3200003, ISRAEL
E-mail: {wh@campus, merhav@ee}.technion.ac.il

Abstract—This paper is about deriving lower bounds on the
error exponents for the two-user interference channel under
the random coding regime for several ensembles. Specifically,
we first analyze the standard random coding ensemble, where
the codebooks are comprised of independently and identically
distributed (i.i.d.) codewords. For this ensemble, we focus on
optimum decoding, which is in contrast to other, suboptimal
decoding rules that have been used in the literature (e.g., joint
typicality decoding, treating interference as noise, etc.). The
fact that the interfering signal is a codeword, rather than an
i.i.d. noise process, complicates the application of conventional
techniques of performance analysis of the optimum decoder.
Also, unfortunately, these conventional techniques result in loose
bounds. Using analytical tools rooted in statistical physics, as well
as advanced union bounds, we derive single-letter formulas for
the random coding error exponents. We compare our results with
the best known lower bound on the error exponent, and show
that our exponents can be strictly better. Then, in the second part
of this paper, we consider more complicated coding ensembles,
and find a lower bound on the error exponent associated with
the celebrated Han-Kobayashi (HK) random coding ensemble,
which is based on superposition coding.
Index Terms—Random coding, error exponent, interference
channels, superposition coding, Han-Kobayashi scheme, statistical physics, optimal decoding, multiuser communication.

I. I NTRODUCTION

T

HE two-user interference channel (IFC) models a general
scenario of communication between two transmitters and
two receivers (with no cooperation at either side), where each
receiver decodes its intended message from an observed signal,
which is interfered by the other user, and corrupted by channel
noise. The information-theoretic analysis of this model has
begun over more than four decades ago and has recently
witnessed a resurgence of interest. Most of the previous
work on multiuser communication, and specifically on the
IFC, has focused on obtaining inner and outer bounds to
the capacity region (see, for example, [1, Ch. II.7]). In a
nutshell, the study of this kind of channel started in [2] and
continued in [3], where simple inner and outer bounds to
the capacity region were given. Then, in [4], by using the
well-known superposition coding technique, the inner bound
of [3] was strictly improved. In [5], various inner and outer
bounds were obtained by transforming the IFC model into
∗ This research was partially supported by The Israeli Science Foundation
(ISF), grant no. 412/12. This paper was presented in part at the 2016
International Zurich Seminar on Communications.

some multiple-access or broadcast channel. Unfortunately, the
capacity region for the general interference channel is still
unknown, although it has been solved for some special cases
[6, 7]. The best known inner bound is the Han-Kobayashi (HK)
region, established in [8], and which will also be considered
in this paper.
To our knowledge, [9, 10] are the only previous works
which treat the error exponents for the IFC under optimal
decoding. Specifically, [9] derives lower bounds on error
exponents of random codebooks comprised of i.i.d. codewords
uniformly distributed over a given type class, under maximum
likelihood (ML) decoding at each user, that is, optimal decoding. Contrary to the error exponent analysis of other multiuser
communication systems, such as the multiple access channel
[11], the difficulty in analyzing the error probability of the
optimal decoder for the IFC is due to statistical dependencies
induced by the interfering signal. Indeed, for the IFC, the
marginal channel determining each receiver’s ML decoding
rule is induced also by the codebook of the interfering user.
This extremely complicates the analysis, mostly because the
interfering signal is a codeword and not an i.i.d. process.
Another important observation, which was noticed in [9], is
that the usual bounding techniques (e.g., Gallager’s bounding
technique) on the error probability fail to give tight results.
To alleviate this problem, the authors of [9] combined some
of the ideas from Gallager’s bounding technique [12] to get
an upper bound on the average probability of decoding error
under ML decoding, the method of types [13], and used the
method of type class enumerators, in the spirit of [14], which
allows to avoid the use of Jensen’s inequality in some steps.
The main purpose of this paper is to extend the study of
achievability schemes to the more refined analysis of error
exponents achieved by the two users, similarly as in [9].
Specifically, we derive single-letter expressions for the error
exponents associated with the average error probability, for
the finite-alphabet two-user IFC, under several random coding
ensembles. The main contributions of this paper are as follows:
• Similarly as in recent works (see, e.g., [11, 15-18] and
references therein) on the analysis of error exponents, we
derive single-letter lower bounds for the random coding error
exponents. For the standard random coding ensemble, considered in Subsection III-B, we analyze the optimal decoder
for each receiver, which is interested solely in its intended
message. This is in contrast to usual decoding techniques

2

analyzed for the IFC, in which each receiver decodes, in
addition to its intended message, also part of (or all) the
interfering codeword (that is, the other user’s message), or
other conventional achievability arguments [1, Ch. II.7], which
are based on joint-typicality decoding, with restrictions on the
decoder (such as, “treat interference as noise” or to “decode
the interference”). This enables us to understand whether there
is any significant degradation in performance due to the suboptimality of the decoder. Also, since [9] analyzed the optimal
decoder as well, we compare our formulas with those of [9],
and show that our error exponent can be strictly better, which
implies that the bounding technique in [9] is not tight. It is
worthwhile to mention that the analytical formulas of our error
exponents are simpler than the lower bound of [9].
• As was mentioned earlier, in [9] only random codebooks
comprised of i.i.d. codewords (uniformly distributed over a
type class) were considered. These ensembles are much simpler than the superposition codebooks of [8]. Unfortunately,
it is very tedious to analyze superposition codebooks using
the methods of [9]. In this paper, however, the new tools
that we have derived enable us to analyze more involved
random coding ensembles. Indeed, we can consider the coding
ensemble used in the HK achievability scheme [8] and derive
the respective error exponents. We also discuss an ensemble
of hierarchical/tree codes [19].
• The analysis of the error exponents, carried out in this paper,
turns out to be much more difficult than in previous works
on point-to-point and multiuser communication problems, see,
e.g., [11, 15-18]. Specifically, we encounter two main difficulties in our analysis: First, typically, when analyzing the
probability of error, the first step is to apply the union bound.
Usually, for point-to-point systems, under the random coding
regime, the average error probability can be written as a
union of pairwise independent error events. Accordingly, in
this case, it is well known that the truncated union bound is
exponentially tight [20, Lemma A.2]. This is no longer the
case, however, when considering multiuser systems, and in
particular, the IFC. For the IFC, the events comprising the
union are strongly dependent, especially due to the fact that we
are considering the optimal decoder. To alleviate this difficulty,
following the ideas of [11], we derived new upper bounds on
the probability of a union of events, which take into account
the dependencies among the events. The second difficulty that
we have encountered in our analysis is that in contrast to
previous works, applying the type class enumerator method
[14] is not simple, due to the reason mentioned above. Using
some methods from large deviations theory, we were able to
tackle this difficulty.
• Recently, in [21, 22], the authors independently suggested
lower bounds on the error exponents of both standard and cognitive multiple-access channels (MACs), assuming suboptimal
successive decoding scheme, and using the standard random
coding ensemble (considered in Subsection III-B). Although
the motivation in [21] is different, the codebook construction
and the decoding rule are the same as in the first part of
this paper, and thus, essentially, their results apply also for
the IFC. It is important to emphasize that while we believe
that our error exponent analysis is somewhat simpler, at least

conceptually, there is strong resemblance between our analysis
and [21], as they both based on type enumeration techniques.
Note, however, that while in [21] the standard union bound
was used, here, the new upper bounds mentioned above,
provide some potential gain over [21], even for the ordinary
ensemble. Also, as was mentioned above, we consider also
the more complicated ensemble pertaining to the HK scheme.
The derivation of the lower bound on the error exponent of this
ensemble is built upon the derivation of the lower bound on the
error exponent of the standard random coding ensemble, and
thus it makes useful and convenient to start with the analysis
of the latter ensemble. We emphasize that the extension of [21]
to the HK ensemble is non-trivial. Finally, we mention that the
focus in [21] was on achievable rate region, rather than error
exponents, and thus no comparison to [9] was provided.
• We believe that by using the techniques and tools derived
in this paper, other multiuser systems, such as the IFC with
mismatched decoding, the MAC [11], the broadcast channel,
the relay channel, etc., and accordingly, other coding schemes,
such as binning [15], and hierarchical codes [19], can be
analyzed.
The paper is organized as follows. In Section II, we establish
notation conventions. In Section III, we formalize the problem
and assert the main theorems. Specifically, in Subsections
III-B and III-C, we give the resulting error exponents under
the standard random coding ensemble and the HK coding
ensemble, respectively. Finally, Section IV is devoted to the
proofs of our main results.
II. N OTATION C ONVENTIONS
Throughout this paper, scalar random variables (RVs) will
be denoted by capital letters, their sample values will be
denoted by the respective lower case letters, and their alphabets
will be denoted by the respective calligraphic letters, e.g. X, x,
and X , respectively. A similar convention will apply to random
vectors of dimension n and their sample values, which will be
denoted with the same symbols in the boldface font. We also
use the notation Xij (j > i) to designate the sequence of RVs
(Xi , Xi+1 , . . . , Xj ). The set of all n-vectors with components
taking values in a certain finite alphabet, will be denoted by the
same alphabet superscripted by n, e.g., X n . Generic channels
will be usually denoted by the letters P , Q, or W . We shall
mainly consider joint distributions of two RVs (X, Y ) over
the Cartesian product of two finite alphabets X and Y. For
brevity, we will denote any joint distribution, e.g. QXY , simply
by Q, the marginals will be denoted by QX and QY , and
the conditional distributions will be denoted by QX|Y and
QY |X . The joint distribution induced by QX and QY |X will
be denoted by QX × QY |X , and a similar notation will be
used when the roles of X and Y are switched.
The expectation operator will be denoted by E {·}, and when
we wish to make the dependence on the underlying distribution
Q clear, we denote it by EQ {·}. Information measures induced
by the generic joint distribution QXY , will be subscripted
by Q, for example, IQ (X; Y ) will denote the corresponding
mutual information, etc. The divergence (or, Kullback-Liebler
distance) between two probability measures Q and P will be

3

denoted by D(Q||P ). The weighted divergence between two
channels, QY |X and PY |X , with weight PX , is defined as
X
D(QY |X ||PY |X |PX ) ,
PX (x)

We assume that the message pair (m1 , m2 ) is uniformly
distributed over M1 ×M2 . It is clear that the optimal decoder
of the first user, for this problem, is given by
m̂1 = arg max P (y 1 |x1,i )

x∈X

X

y∈Y

i∈M1

QY |X (y|x)
QY |X (y|x) log
. (1)
PY |X (y|x)

For a given vector x, let Q̂x denote the empirical distribution,
that is, the vector {Q̂x (x), x ∈ X }, where Q̂x (x) is the
relative frequency of the letter x in the vector x. Let T (PX )
denote the type class associated with PX , that is, the set of
all sequences x for which Q̂x = PX . Similarly, for a pair of
vectors (x, y), the empirical joint distribution will be denoted
by Q̂xy , or simply by Q̂, for short. All previously defined
notation rules for regular distributions will also be used for
empirical distributions.
The cardinality of a finite set A will be denoted by |A|,
its complement will be denoted by Ac . The probability of an
event E will be denoted by Pr {E}. The indicator function of
an event E will be denoted by I {E}. For two sequences of
·
positive numbers, {an } and {bn }, the notation an = bn means
that {an } and {bn } are of the same exponential order, i.e.,
n−1 log an /bn → 0 as n → ∞, where logarithms are defined
with respect to (w.r.t.) the natural basis, that is, log (·) = ln (·).
Finally, for a real number x, we denote [x]+ , max {0, x}.
III. P ROBLEM F ORMULATION

AND

M AIN R ESULTS

We divide this section into three subsections. In the first, we
present the model and formulate the problem. In the second,
we present a lower bound on the IFC error exponent, assuming
a simple random coding ensemble where random codebooks
comprised of i.i.d. codewords are uniformly distributed over a
type class. It is well-known [10] that this coding scheme can
be improved by using superposition coding and introducing the
notion of “private” and “common” messages (to be defined in
the sequel). Accordingly, in the third subsection, we consider
the HK coding scheme [8], and derive lower bounds on the
error exponents. Finally, we discuss other ensembles that can
be analyzed using the same methods.
A. The IFC Model
Consider a two-user interference channel of two senders,
two receivers, and a discrete memoryless channel (DMC),
defined by a set of single-letter transition probabilities, WY1 Y2 |X1 X2 (y1 , y2 |x1 , x2 ), with finite input alphabets,
X1 , X2 , and finite output alphabets, Y1 , Y2 . Here, each sender,
k ∈ {1, 2}, communicates an independent message mk ∈
{1, 2, . . . , Mk , 2nRk } at rate Rk , and each receiver,
l ∈ {1, 2}, decodes its respective message. Specifically, a
(2nR1 , 2nR2 , n) code Cn consists of:

sets M1 , 0, . . . , 2nR1 − 1 and M2 ,
• Two message
0, . . . , 2nR2 − 1 for the first and second users, respectively.
• Two encoders, where for each k ∈ {1, 2}, the k-th encoder
assigns a codeword xk,i to each message i ∈ Mk .
• Two decoders, where each decoder l ∈ {1, 2} assigns an
estimate m̂l to ml .

= arg max

i∈M1

M2 −1
1 X
P (y 1 |x1,i , x2,j )
M2 j=1

(2)
(3)

where P (y 1 |x1,i , x2,j ) is the marginal channel defined as
P (y 1 |x1,i , x2,j ) ,

n
Y

WY1 |X1 X2 (y1k |x1,i,k , x2,j,k ),

(4)

k=1

and

WY1 |X1 X2 (y1,k |x1,i,k , x2,j,k )
X
,
WY1 Y2 |X1 X2 (y1,k , y2,k |x1,i,k , x2,j,k ).

(5)

y2,k ∈Y2

The optimal decoder of the second user is defined similarly.
Since there is no cooperation between the two receivers, the
error probabilities for the code Cn , are defined as
Pe,i (Cn ) , 2−n(R1 +R2 )
X
·
Pr {m̂i (Yin ) 6= m̃i |m1 = m̃1 , m2 = m̃2 } ,
m̃1 ,m̃2

(6)

for i = 1, 2.
B. The Ordinary Random Coding Ensemble
In this subsection, we consider the ordinary random coding
ensemble: For each k ∈ {1, 2}, we select independently Mk
codewords {xk,i }, for i ∈ Mk , under the uniform distribution
across the type class T (PXk ), for a given distribution PXk
(n)
on Xk . Our goal is to assess the exponential rate of P̄e,1 ,
E {Pe,1 (Cn )}, where the average is over the code ensemble,
that is,
1
(n)
(7)
E1∗ (R1 , R2 ) , lim inf − log P̄e,1 ,
n→∞
n
and similarly for the second user. Before stating the main
result, we define some quantities. Given a joint distribution
QX1 X2 Y1 over X1 × X2 × Y1 , consider the definitions in (8),
shown at the top of the next page. We devote Appendix C for
a discussion on aspects of the computation of (8j). We have
the following result.
Theorem 1 Let R1 and R2 be given, and let E ∗ (R1 , R2 ) be
defined as in (7). Consider the ensemble of fixed composition
codes of types PX1 and PX2 , for the first and second users,
respectively. For a discrete memoryless two-user IFC, we have
E1∗ (R1 , R2 ) ≥ Ẽ1 (R1 , R2 ),

(9)

for any R1 , R2 ≥ 0.
Several remarks on Theorem 1 are in order.
Due to symmetry, the error exponent for the second user,
that is, Ẽ2 (R1 , R2 ) is simply obtained from Theorem 1 by
•

4



f (QX1 X2 Y1 ) , EQ log WY1 |X1 X2 (Y1 |X1 , X2 ) ,
h
i
f (Q̂) − IQ̂ (X2 ; X1 , Y1 ) ,
max
t0 (QX1 Y1 ) , R2 +

(8a)
(8b)

Q̂: Q̂X2 =PX2 , Q̂X1 Y1 =QX1 Y1
IQ̂ (X2 ;X1 ,Y1 )≤R2

E1 (Q̃X1 X2 Y1 , QX1 X2 Y1 ) ,
E2 (Q̃X1 X2 Y1 , QX1 X2 Y1 ) ,

min
Q̂: Q̂X2 =PX2 , Q̂X1 Y1 =Q̃X1 Y1
Q̂∈L(Q̃X1 X2 Y1 ,QX1 X2 Y1 )

min
Q̂: Q̂X2 =PX2 , Q̂X1 Y1 =Q̃X1 Y1
Q̂∈L̂(Q̃X1 X2 Y1 ,QX1 X2 Y1 )

i
h
IQ̂ (X2 ; X1 , Y1 ) − R2 ,

(8c)

i
h
IQ̂ (X2 ; Y1 ) − R2 ,

(8d)

+

+


L(Q̃X1 X2 Y1 , QX1 X2 Y1 ) , Q̂ : max [t0 (QX1 X2 Y1 ), f (QX1 X2 Y1 )]

h
i 
,
≤ max f (Q̃X1 X2 Y1 ), f (Q̂) + R2 − IQ̂ (X2 ; X1 , Y1 )
+

L̂(Q̃X1 X2 Y1 , QX1 X2 Y1 ) , Q̂ : max [t0 (QX1 X2 Y1 ), f (QX1 X2 Y1 )]

h
i 
,
≤ max f (Q̃X1 X2 Y1 ), f (Q̂) + R2 − IQ̂ (X2 ; Y1 )
+
i
h
IQ̃ (X1 ; X2 , Y1 ) + E1 (Q̃X1 X2 Y1 , QX1 X2 Y1 ) ,
min
Ê1 (QX1 X2 Y1 , R2 ) ,

(8e)

(8f)
(8g)

Q̃: Q̃X1 =PX1 , Q̃X2 Y1 =QX2 Y1

Ê2 (QX1 X2 Y1 , R2 ) ,

min

Q̃: Q̃X1 =PX1 , Q̃X2 Y1 =QX2 Y1

E(QX1 X2 Y1 , R1 , R2 ) , max
Ẽ1 (R1 , R2 ) ,

min

E2 (Q̃X1 X2 Y1 , QX1 X2 Y1 ),


h
i
Ê1 (QX1 X2 Y1 , R2 ) − R1 , Ê2 (QX1 X2 Y1 , R2 ) ,
+


D(QY1 |X1 X2 ||WY1 |X1 X2 |PX1 × PX2 ) + E(QX1 X2 Y1 , R1 , R2 ) .

QY1 |X1 X2 :
QX1 =PX1 ,QX2 =PX2

swapping the roles of X1 , Y1 , and R1 , with those of X2 , Y2 ,
and R2 , respectively.
• An immediate byproduct of Theorem 1 is finding the set of
rates (R1 , R2 ) for which Ẽ1 (R1 , R2 ) > 0, namely, the rates
for which the probability of error vanishes exponentially as
n → ∞. We show in Appendix D, that this set is given by:

(8i)
(8j)

R2

I(X2 ; Y1 |X1 )

Rordinary,1

Rordinary,1 = {R1 < I (X1 ; Y1 )} ∪
{{R1 + R2 < I (X1 , X2 ; Y1 )} ∩ {R1 < I (X1 ; Y1 |X2 )}}
(10)
evaluated with PX1 X2 Y1 = PX1 × PX2 × WY1 |X1 X2 . Note
that this region can be obtained also by using standard
typicality-based achievability arguments (see, e.g., [23]).
Fig. 1 demonstrates a qualitative description of this region. The interpretation is as follows: The corner point
(I (X1 ; Y1 |X2 ) , I (X2 ; Y1 )) is achieved by first decoding the
interference (the second user), canceling it, and then decoding
the first user. The sum-rate constraint can be achieved by
joint decoding the two users (similarly to MAC), and thus,
obviously, also by our optimal decoder. Finally, the region
R1 < I (X1 ; Y1 ) and R2 ≥ I (X2 ; Y1 |X1 ) means that we
decode the first user while treating the interference as noise.
Evidently, from the perspective of the first decoder, which is
interested only in the message transmitted by the first sender,
the second sender can use any rate, and thus there is no bound
on R2 whenever R1 < I (X1 ; Y1 ). Now, it was shown in [10]

(8h)

I(X2 ; Y1 )
I(X1 ; Y1 )
Fig. 1.

I(X1 ; Y1 |X2 )

R1

Rate region Rordinary,1 for which Ẽ1 (R1 , R2 ) > 0.

that the error exponent achievable for the first user under the
ordinary random coding regime is zero outside the closure
of Rordinary,1 . Whence, this fact and the above conclusion,
characterize the rate region where the attainable exponent with
ordinary random coding is positive. Notice that Rordinary,1 is
well-known to be contained in the HK region [10, 23].
• Existence of a single code: our result holds true on the
average, where the averaging is done over the random choice
of codebooks. It can be shown (see, for example, [24, p. 2924])
that there exists deterministic sequence of fixed composition
codebooks of increasing block length n for which the same

5

asymptotic error performance can be achieved for both users
simultaneously.
• About the proof: it is instructive to discuss (in some more
detail than earlier) one of the main difficulties in proving
Theorem 1, which is customary to multiuser systems, such
as the IFC. Without loss of generality, we assume throughout,
that the transmitted codewords are x1,0 and x2,0 . Accordingly,
the average probability of error associated with the decoder
(3) is given by (11), shown at the top of the next page, where
F0 , (X 1,0 , X 2,0 , Y 1 ). In contrast to previous works, applying the type class enumerator1 method [14], is not a simple
task. Since we are interested in the optimal decoder, each
event of the union in (11), depends on the whole codebook
of the second user. One may speculate that this problem can
be tackled by conditioning on the codebook of the second
user, and then (12). However, the cost of this conditioning is a
very complicated (if not intractable) large deviations analysis
of some quantities. The consequence of this situation is that
in order to analyze the probability of error, it is required to
analyze the joint distribution of type class enumerators, and
not just rely on their marginal distributions, as is usually done,
e.g., [15-18].
Another difficulty is handling the union in (11). By the
union bound and Shulman’s inequality [20, Lemma A.2], we
know that for a sequence of pairwise independent events,
N
{Ai }i=1 , the following holds
)
)
(N
( N
[
X
1
Ai
Pr {Ai } ≤ Pr
min 1,
2
i=1
i=1
)
( N
X
Pr {Ai } , (12)
≤ min 1,
i=1

which is a useful result when assessing the exponential behavior of such probabilities. Equation (12) is one of the
building blocks of tight exponential analysis of previously
considered point-to-point systems (see, e.g., [15-18], and many
references therein). However, in our case the various events are
not pairwise independent, and therefore this result cannot be
applied. To alleviate this problem, following the techniques of
[11], we derive new upper bounds on the probability of a union
of events, which takes into account such dependencies among
the events.
• As was mentioned in the Introduction, in [21], lower
bounds on the error exponents of both standard and cognitive
multiple-access channels (MACs) were suggested. Although
the motivation in [21] is different, their results apply also
for the IFC. Now, while in [21] the standard truncated union
bound was used, here our new upper bound on the probability
of a union of events, provides some potential gain over
[21]. Specifically, the lower bound in [21] is the same as
1 For a given y n ∈ Y n , and a given joint probability distribution Q
XY
on
X
 n × Y, the type class enumerator, N (QXY ), is the number ofncodewords
xi in Cn whose conditional empirical joint distribution with y is QXY ,

namely, N (QXY ) = xn ∈ Cn : Q̂xn y n = QXY , where Q̂xn y n is the
empirical joint distribution of xn and y n , and |A| designates the cardinality
of a finite set A. Type class enumeration method refers to the process of
converting a sum of exponentially many terms (usually likelihood functions)
into polynomial number of type class enumerators, which are easier to analyze.

(8j) but
i.e., it is given by

 without the
 Ê2 (Q, R2 ) term,
minQ D(Q||W )+ Ê1 (Q, R2 )−R1 + , and thus, in general,
our result may be tighter. It should be stressed, however, that
we have not identified specific examples where the new term,
namely, Ê2 (Q, R2 ), dominated the maximum in (8i).
• The lower bound in [9] is extremely complicated, and it is
very difficult to compare it analytically to the lower bound in
Theorem 1. Nonetheless, we can still claim (in general) that
our lower bound is at least as good as the lower bound in [9].
Indeed, the first step in the analysis of the error exponent in
both our paper and in [9] is applying the union bound (actually,
here, we employ a tighter union bound). However, it will be
seen that every other passage in our analysis is exponentially
exact, while in [9], some steps are associated with inequalities
that may cause gaps in the exponential scale, and thus in
general, Ẽ(R1 , R2 ) ≥ E[9] (R1 , R2 ), for any (R1 , R2 ) ∈ R2+ ,
where E[9] (R1 , R2 ) is the lower bound in [9].
• Comparison with [9]: Similarly to [9], we present results for
the following channel: Y1 = X1 · X2 ⊕ Z and Y2 = X2 , where
X1 , X2 , Y1 , Y2 ∈ {0, 1}, Z ∼ Bern(p), “·” is multiplication,
and “⊕” is modulo-2 addition. In the numerical calculations,
we fix p = 0.01. Fig. 2 presents the lower bound on the
error exponent under optimal decoding, derived in this paper,
compared to the lower bound E[9] (R1 , R2 ) of [9], as a function
of R1 , for different values of PX1 , PX2 , and R2 . It can be seen
that our exponents are strictly better than those of [9].
C. The Han-Kobayashi Coding Scheme
Consider the channel model of Subsection III-B. The best
known inner bound on the capacity region is achieved by the
HK coding scheme [8]. The idea of this scheme is to split
the message m1 into “private” and “common” messages, m11
and m12 at rates R11 and R12 , respectively, such that R1 =
R11 + R12 . Similarly, m2 is split into m21 and m22 at rates
R21 and R22 , with R2 = R21 + R22 . The intuition behind
this splitting is based on the receiver behavior at low and high
signal-to-noise-ratio (SNR). Specifically, it is well-known [1]
that: (1) when the SNR is low, treating the interference as
noise is an optimal strategy, and (2) when the SNR is high,
decoding and then canceling the interference is the optimal
strategy. Accordingly, the above splitting captures the general
intermediate situation where the first decoder, for example, is
interested only in partial information from the second user, in
addition to its own intended message.
Next, we describe explicitly the coding strategy of [8]. Fix a
distribution PZ11 PZ12 PZ21 PZ22 PX1 |Z11 Z12 PX2 |Z21 Z22 , where
the latter two conditional distributions represent deterministic
mappings. For each k, k ′ ∈ {1, 2}, randomly and conditionally
independently generate a sequence z k,k′ (mk,k′ ) under the
uniform distribution across the type class T (PZkk′ ) for a given
PZk,k′ . To communicate a message pair (m11 , m12 ), sender 1
transmits x1 (z 11 , z 12 ), and analogously for sender 2. All our
results can be extended to the setting in which the codewords
are generated conditionally on a time-sharing sequence q.
However, this leads to more complicated notation. Thus, we
focus primarily on the case without time-sharing.
Let us now describe the operation of each receiver. Receiver
k = 1, 2, recovers its intended message mk and the common

6



(n)

P̄e,1 = Pr 
=E







M[
2 −1
1 −1 M
X
i=1





P (Y 1 |X 1,i , X 2,j ) ≥

j=0

j=0



M[
2 −1
1 −1 M
X

Pr 

i=1



P (Y 1 |X 1,i , X 2,j ) ≥



P (Y 1 |X 1,0 , X 2,j ) 


M
2 −1
X
j=0

j=0





P (Y 1 |X 1,0 , X 2,j ) F0 



(11)

M11 7→ Z11

0.45

X1

M12 7→ Z12

0.4

Ẽ1 for R2 = 0.139, PX1 (1) = 0.6, PX2 (1) = 0.9
Ẽ1 for R2 = 0.277, PX1 (1) = 0.6, PX2 (1) = 0.7

Y2 → (M̂12 , M̂21 , M̂22 )

M21 7→ Z21

E[9] for R2 = 0.277, PX1 (1) = 0.6, PX2 (1) = 0.7

0.3

Y1 → (M̂11 , M̂12 , M̂21 )
P (Y12 |X12 )

E[9] for R2 = 0.139, PX1 (1) = 0.6, PX2 (1) = 0.9

0.35

Error Exponents

M
2 −1
X

X2

M22 7→ Z22
0.25
0.2

Fig. 3.

Han-Kobayashi coding scheme.

0.15

arg

0.1
0.05

= arg

0
0

max

(i,j,k)∈M11 ×M12 ×M21

0.1

0.2

0.3

0.4

0.5

0.6

R1 [nats/channel use]

P (y 1 |z 11,i , z 12,j , z 21,k )

(13)

max

(i,j,k)∈M11 ×M12 ×M21
M22 −1
1 X
P (y 1 |z 11,i , z 12,j , z 21,k , z 22,l ) . (14)
M22
l=0

Fig. 2. Comparison between Ẽ1 (R1 , R2 ) and E[9] (R1 , R2 ) of [9], as a
function of R1 for two different values of R2 and fixed choices of PX1 and
P X2 .

Accordingly, the probability of error for the code Cn and for
the first user, is defined as
Pe,1 (Cn ) , Pr {(m̂11 , m̂12 ) 6= (m11 , m12 )} ,

message from the other sender (although it is not required to).
This scheme is illustrated in Fig. 3. Note that this decoding
operation is the one that was used in [8], but there, the suboptimal non-unique simultaneous joint typical decoder [1, Ch.
II.7] was used. Here, by contrast, we use sub-optimal ML
decoding (the sub-optimality is due to the fact that our decoder
recovers also the common message from the other sender).
As will be explained in the sequel, analyzing the optimal ML
decoder is a challenging task, and therefore we will focus on
sub-optimal ML decoding.
We wish to find a lower bound on the error exponent,
achieved by the HK encoding functions, in conjunction with
the above described decoding functions. To this end, note
that by combining the channel and the deterministic mappings as indicated by the dashed box in Fig. 3, the channel (Z11 , Z12 , Z21 , Z22 ) 7→ (Y1 , Y2 ) is just a four-sender,
two-receiver, DMC interference channel, with virtual inputs.
Note that this formulation induces the Markovian structure
(Z11 , Z12 , Z21 , Z22 )−
◦ (X1 , X2 )−
◦ (Y1 , Y2 ), where the (virtual) input distributions, i.e., PZk,k′ for k, k ′ ∈ {1, 2},
can be optimized. We assume that the message quadruple
(m11 , m12 , m21 , m22 ) is uniformly distributed over M11 ×
M12 × M21 × M22 . Following the above descriptions, our
decoder for this problem is given by
(m̂11 , m̂12 , m̂21 ) =

(15)

and similarly for the second user. Our goal is to assess the
(n)
exponential rate of P̄e,1 , E {Pe,1 (Cn )}, where the average
is over the code ensemble, namely,
∗
EHK
(R1 , R2 ) , lim inf −
n→∞

1
(n)
log P̄e,1 ,
n

(16)

and similarly for the second user. In order to facilitate the
presentation of the following result, we move the technical
definitions to Appendix A. Our second main result is the
following.
∗
Theorem 2 Let EHK
(R1 , R2 ) be defined as in (16). Consider
the HK encoding scheme described above. For a discrete
memoryless two-user IFC, we have:
∗
EHK
(R1 , R2 ) ≥

max

(R11 ,R12 ,R21 ,R22 ):
R11 +R12 =R1
R21 +R22 =R2

ẼHK (R11 , R12 , R21 , R22 ),
(17)

for any R1 , R2 ≥ 0, where ẼHK (R11 , R12 , R21 , R22 ) is given
in (A.30).
Several remarks on Theorem 2 are in order.
• As before, an immediate byproduct of Theorem 2 is
finding the set of rates (R11 , R12 , R21 , R22 ) for which

7

ẼHK (R11 , R12 , R21 , R22 ) > 0, namely, for which the probability of error vanishes exponentially as n → ∞. It can be
shown that this set is given by the HK region, that is,
R11 ≤ I(Z1 ; Y1 |Z2 , Z3 ),
R12 ≤ I(Z2 ; Y1 |Z1 , Z3 ),

(18a)
(18b)

R21 ≤ I(Z3 ; Y1 |Z1 , Z2 ),

(18c)

R11 + R12 ≤ I(Z1 , Z2 ; Y1 |Z3 ),
R11 + R21 ≤ I(Z1 , Z3 ; Y1 |Z2 ),

(18d)
(18e)

R12 + R21 ≤ I(Z2 , Z3 ; Y1 |Z1 ),
R11 + R12 + R21 ≤ I(Z1 , Z2 , Z3 ; Y1 ),

(18f)
(18g)

evaluated with
PZ14 Y1 = PZ1 PZ2 PZ3 PZ4 PX1 |Z1 Z2 PX2 |Z3 Z4 WY1 |X1 X2
and similarly for the second user, where PX1 |Z1 Z2 and
PX2 |Z3 Z4 represent deterministic mappings. As was mentioned
earlier, it is possible to introduce a time-sharing sequence
q, and accordingly, (18) remains almost the same, but with
a time-sharing RV Q (with alphabet size bounded by eight
[8]), appearing at the conditioning of each the above mutual
information terms. Finally, we mention that in [23] it was
shown that by using the optimal ML decoder (given in (20))
instead of the non-unique simultaneous joint typical decoder
[8], we cannot improve the achievable region. This observation
do not for the error exponent.
2
• It can be shown that the error exponent in Theorem 2
is no worse than the error exponent in Theorem 1, namely,
ẼHK (R11 , R12 , R21 , R22 ) ≥ Ẽ1 (R1 , R2 ) for any (R1 , R2 )
such that R1 = R11 +R12 and R2 = R21 +R22 . Moreover, it is
well-known that upon optimizing the auxiliary RVs, {Zij }, the
HK region in (18) is strictly better than Rordinary,1 . Therefore,
this necessarily implies that for a certain region of high rates,
the HK error exponent in Theorem 2 will be positive while
the standard random coding error exponent in Theorem 1 will
be zero. On the other extreme, it is easy to show that for
(R1 , R2 ) = (0, 0) the error exponent in Theorem 2 equals to
the error exponent in Theorem 1, so for small rates there is
no improvement in the error exponents.
• Contrary to the ordinary ensemble, described in Subsection
III-B, the HK ensemble depends on some auxiliary RVs which
should be optimized. For a give pair of rates (R1 , R2 ), our
error exponent formula provides a criterion for the choice of
the optimal auxiliary RVs: maximize the lower bound on the
error exponent in Theorem 2, w.r.t. the auxiliaries, subject to
some relevant constraints. As a matter of fact, for a given pair
of rates (R1 , R2 ), it is very likely that the optimal choice of
these auxiliaries will be different from the optimal choice for
the same pair in the achievable region. Indeed, even in the
single-user case, the capacity achieving distribution is usually
different from the optimal distribution in the error exponent
sense.
2 By definition, the ordinary ensemble is a simple instance of the HK
ensemble, and thus the latter is indeed better upon optimization of the auxiliary
RVs {Zij }. To see that the ordinary ensemble is a special case of the HK
ensemble, we take Z11 = X1 , Z12 = Z21 = ∅, and Z22 = X2 .

• Using the same techniques and tools derived in this paper, we can consider other random coding ensembles. For
example, we can analyze the error exponents resulting from
the hierarchical code ensemble. Specifically, in this ensemble,
the message m1 is split into common and private messages
m11 , m12 at rates R11 and R12 , respectively, such that
R1 = R11 + R12 . Similarly m2 is split into m21 , m22 at
rates R21 and R22 , respectively, such that R2 = R21 + R22 .
Then, we first randomly draw a rate R11 codebook of block
length n according to a given distribution. Then, for each such
codeword, we randomly and conditionally independently generate a rate R12 codebook of block length n. In other words,
the code has a tree structure with two levels, where the first
serves for “cloud centers”, and the second for the “satellites”.
We do the same for the second user. Under this ensemble,
we can analyze the optimal decoder. Note, however, that this
ensemble is different from the product ensemble considered
in Theorem 2. Indeed, while for the former for each first
stage codeword (cloud center) we independently draw a new
codebook (satellites), for the latter, for each cloud center we
have the same satellite codebook. Loosely speaking, this means
that the product ensemble is “less random”. From the point of
view of achievable region, however, the hierarchical ensemble
is equivalent to the product ensemble used in HK scheme
[1, Ch. II.7]. Nonetheless, the error exponents associated with
these ensembles could be different.
• In Theorem 2 we assumed the sub-optimal decoder given
in (14). Indeed, the optimal decoder for our problem is given
by:

(m̂11 , m̂12 ) = arg max P (y 1 |z 11,i , z 12,j )
i,j

(19)

= arg max
i,j

1
M21 M22

MX
21 −1 MX
22 −1
k=0

P (y 1 |z 11,i , z 12,j , z 21,k , z 22,l ) . (20)

l=0

Unfortunately, it turns out that analyzing the HK scheme (in
conjunction with (20)) is much more difficult, and requires
some more delicate tools from large deviations theory. Specifically, the main difficulty in the derivations, is to analyze the
large deviations behavior of a two-dimensional sum (due to the
double summation in (20)) involving binomial RVs which are
strongly dependent (contrary to the standard one-dimensional
version, see, e.g., [15, p. 6027-6028]). Nonetheless, we note
that for the hierarchical code ensemble described above, the
optimal decoder can be analyzed. Indeed, for this ensemble, it
is clear that the optimal decoder is given by
(m̂11 , m̂12 ) = arg max P (y 1 |x1 (i, j))
i,j

= arg max
i,j

(21)

MX
21 −1 MX
22 −1
1
P (y 1 |x1 (i, j), x2 (k, l))
M21 M22
k=0
l=0
(22)

where x1 (i, j) , f1 (x′1 (i), x′′1 (i, j)) and x2 (i, j) ,
f2 (x′2 (i), x′′2 (i, j)) due to the hierarchical structure. Now,
while here too, we will deal with two-dimensional summation,
the summands will be independent, given the cloud centers
codebook, and the proof can be carried out smoothly.

8

IV. P ROOFS OF M AIN R ESULTS
A. Proof of Theorem 1
Without loss of generality, we assume throughout, that the
transmitted codewords are x1,0 and x2,0 , and due to the fact
that we analyze the first decoder, for convenience, we use y
instead of y 1 . Accordingly, the average probability of error associated with the optimal decoder (3), is given by (24), shown
at the top of the next page, where F0 , (X 1,0 , X 2,0 , Y ). In
the following, we propose new upper bound on the probability
of a union of events, which are suitable for some structured
dependency between the events, as above.
In order to give some motivation for this new bound, we
first rewrite (23) in another (equivalent) form. Specifically, we
express (24) in terms of the joint types of (X 1,0 , X 2,0 , Y )
and {(Y , X 1,i , X 2,j )}i,j . First, for a given joint distribution
QX1 X2 Y of (x1 , x2 , y), let
1
f (QX1 X2 Y ) , log P (y|x1 , x2 )
(25)
n 

(26)
= EQ log WY |X1 X2 (Y |X1 X2 ) .

For a given joint type QX1,0 X2,0 Y of the random
 vectors (X 1,0 , X 2,0 , Y ), define the set TI QX1,0 X2,0 Y , given
in (27), shown at the top of the next page. The set
TI (QX1,0 X2,0 Y ) is the set of all possible types of (X 1,i , C2 ),
where C2 denotes the codebook of the second user, which lead
to a decoding error when (X 1,0 , X 2,0 , Y ) ∈ T (QX1,0 X2,0 Y )
is transmitted. The various marginal constraints in (28) and
(29) arise from the fact that we are assuming constantcomposition random coding and, of course, fixed marginals
due to the given fixed joint distribution QX1,0 X2,0 Y . Finally,
the constraint
M
2 −1 h
i
X
k
k
nf (Q̃0X1 X2,0 Y )
e
+
enf (Q̃X1 X2 Y ) − enf (Q̂X1 X2 Y )
k=1

≥ enf (QX1,0 X2,0 Y )

(30)

in (27), represents a decoding error event, that is, it holds if
and only if
M
2 −1
X

P (y|x1,i , x2,j ) ≥

M
2 −1
X

P (y|x1,0 , x2,j ) ,

(31)

j=0

j=0

or, equivalently,
P (y|x1,i , x2,0 ) +

M
2 −1
X

[P (y|x1,i , x2,j ) − P (y|x1,0 , x2,j )]

j=1

≥ P (y|x1,0 , x2,0 ) ,

(32)

for (x1,0 , x2,0 , y) ∈ T (QX1,0 X2,0 Y ), (x1,i , x2,0 , y) ∈
T (Q̃0X1 X2,0 Y ), (x1,i , x2,j , y)
∈
T (Q̃jX1 X2 Y ), and
(x1,0 , x2,j , y) ∈ T (Q̂jX1,0 X2 Y ), for j = 1, 2, . . . , M2 − 1.
Now, with these definitions, fixing QX1,0 X2,0 Y , and letting
(x1,0 , x2,0 , y) be an arbitrary triplet of sequences such that
(x1,0 , x2,0 , y) ∈ T (QX1,0 X2,0 Y ), it follows, by definition,
that the error event


M
M[
2 −1
2 −1
1 −1 M

X
X
P (Y |X 1,0 , X 2,j )
P (Y |X 1,i , X 2,j ) ≥


i=1

j=0

j=0

(33)

can be rewritten, in terms of types, as follows
M[
1 −1
i=1

n

Q̃jX

1 X2 Y

,Q̂jX

[

1 X2 Y

o

j

∈TI (QX1,0 X2,0 Y )



(X 1,i , x2,0 , y) ∈ T (Q̃0X1 X2,0 Y ),



oM2 −1
 n
(X 1,i , X 2,j , y) ∈ T (Q̃jX1 X2 Y )
,
j=1

n
o

M2 −1


 (x1,0 , X 2,j , y) ∈ T (Q̂jX1,0 X2 Y )
j=1








.

(34)







We wish to analyze the probability of the event in (34),
conditioned on F0 . Note that the inner union in (34) is over
vectors of types (an exponential number of them). Finally, for
the sake of convenience, we simplify the notations of (34),
and write it equivalently as


X 1,i ∈ Al,0 ,


M[
1 −1 [ 

(X 1,i , X 2,j ) ∈ Al,j , for j = 1, . . . , M2 − 1,



i=1 l 
X 2,j ∈ Ãl,j , for j = 1, . . . , M2 − 1
(35)

where, again, the index “l” in the inner union runs over the
combinations of types (namely, l = {Q̃jX1 X2 Y , Q̂jX1 X2 Y }j )
that belong to TI (QX1,0 X2,0 Y ), and the various sets
{Al,j , Ãl,j }l,j correspond to the typical sets in (34) (recall
that (x1,0 , x2,0 , y) are given at this stage). Next, following
the ideas of [11], we provide a new upper bound on a generic
probability which has the form of (35). The proof of this
lemma is relegated to Appendix B.
L

1
Lemma 1 Let {V1 (i)}i=1
, V2 , V3 , . . . , VK be independent sequences of independently and identically distributed (i.i.d.)
RVs on the alphabets V1 × V2 × . . . × VK , respectively, with
V1 (i) ∼ PV1 , V2 ∼ PV2 , . . . , VK ∼ PVK . Fix a sequence of
N
N
N
sets {Ai,1 }i=1 , {Ai,2 }i=1 , . . . , {Ai,K−1 }i=1 , where Ai,j ⊆
V1 ×Vj+1 , for 1 ≤ j ≤ K−1 and for all 1 ≤ i ≤ N . Also, fix a
N
set {Ai,0 }i=1 where Ai,0 ⊆ V1 for all 1 ≤ i ≤ N , and another
N
N
N
sequence of sets {Gi,2 }i=1 , {Gi,3 }i=1 , . . . , {Gi,K }i=1 , where
Gi,j ⊆ Vj , for 2 ≤ j ≤ K and for all 1 ≤ i ≤ N . Define

K−1

\
(v1 , vj+1 ) ∈ Am,j ,
Bm,1 , v1 : v1 ∈ Am,0 ,

j=1

K

\
(36)
vj ∈ Gm,j for some {vj }K
j=2  ,

j=2

and

Bm,2 ,




K

{vj }j=2 : v1 ∈ Am,0 ,



K
\

j=2

K−1
\

(v1 , vj+1 ) ∈ Am,j ,

j=1

vj ∈ Gm,j for some v1





,

(37)

for m = 1, 2, . . . , N . Then, a general upper bound is given in
(38), shown at the top of the next page, with (V1 , . . . , VK ) ∼
PV1 · · · × PVK .

9



(n)

P̄e,1 = Pr 
=E







M[
2 −1
1 −1 M
X
i=1





P (Y |X 1,i , X 2,j ) ≥

j=0

j=0



M[
2 −1
1 −1 M
X

Pr 



i=1

M
2 −1
X

P (Y |X 1,i , X 2,j ) ≥



P (Y |X 1,0 , X 2,j ) 


M
2 −1
X
j=0

j=0

(23)





P (Y |X 1,0 , X 2,j ) F0 




n
oM2 −1 n
oM2 −1 

TI QX1,0 X2,0 Y , Q̃0X1 X2,0 Y ∈ S0 ,
Q̃kX1 X2 Y
, Q̂kX1,0 X2 Y
∈ S1 :
k=1

e

nf (Q̃0X1 X2,0 Y )

+

M
2 −1 h
X

e

k=1

nf (Q̃k
X1 X2 Y )

−e

nf (Q̂k
X1 X2 Y )

k=1

i

≥e

nf (QX1,0 X2,0 Y )

o
n
S0 (QX1,0 X2,0 Y ) , Q̃0X1 X2,0 Y : Q̃0X1 = PX1 , Q̃0X2 = PX2 , Q̃0X2,0 Y = QX2,0 Y ,
n
oM2 −1
oM2 −1 n
: Q̃kX1 = PX1 , Q̃kX2 = PX2 , Q̃kY = QY ,
, Q̂kX1,0 X2 Y
S1 (QX1,0 X2,0 Y ) ,
Q̃kX1 X2 Y
=

Pr

[
i

(

N
[

m=1

(

V1 (i) ∈ Am,0 ,
(

K−1
\

≤ min 1, L1 Pr
L1 Pr

(

,

(27)
(28)

= PX2 , Q̂kX1,0 Y = QX1,0 Y , ∀1 ≤ k ≤ M2 − 1

PX1 , Q̂kX2

Q̃kX2 Y

(

)

k=1

k=1

Q̂kX1,0

(24)

m=1

(

, Q̃kX1 Y

(V1 (i), Vk+1 ) ∈ Am,k ,

k=1
( N
[

)

{V1 ∈ Bm,1 } , Pr

m=1

N
[

=

Q̂kX2 Y

V1 ∈ Am,0 ,

K−1
\
k=1

K
\

k=2
( N
[

=

Q̃m
X1 Y

Vk ∈ Gm,k

m=1



, ∀k, m .

(29)

)))

)
o
n
K
{Vj }k=2 ∈ Bm,2
,

(V1 , Vk+1 ) ∈ Am,k ,

K
\

k=2

Vk ∈ Gm,k

)))

(38)

Next, we apply Lemma 1 to the problem at hand. To this types. Accordingly, we have:
end, we choose the following parameters in accordance to the 1) Am,i = Al,i , for 0 ≤ i ≤ M2 − 1,
notations used in Lemma 1. Recall that we deal with

 2) Gm,i = Ãl,i−1 , for 2 ≤ i ≤ M2 .
0
X
∈
A
,


1,i
l,0
M[
1 −1 [ 
 These sets correspond to each of the typical sets T (Q̃X1 X2,0 Y ),
M
−1
M
−1
2
2
(X 1,i , X 2,j ) ∈ Al,j , for j = 1, . . . , M2 − 1,
.
, and {T (Q̂kX1,0 X2 Y )}k=1
{T (Q̃kX1 X2 Y )}k=1


 • According
i=1 l 
to
(36)
and
(37)
we
need
to define
X 2,j ∈ Ãl,j , for j = 1, . . . , M2 − 1
j
j
0
,
{
Q̃
,
Q̂
and
B
=
B
(
Q̃
m,1
1
(39)
X1 X2,0 Y
X1 X2 Y
X1 X2 Y }j )
j
j
0
Bm,2
=
B2 (Q̃X1 X2,0 Y , {Q̃X1 X2 Y , Q̂X1 X2 Y }j ). Using
and in Lemma 1 we have considered:


(36) and (37), we get (41) and (42), given at the top of the
V1 (i) ∈ Am,0 ,

L1 [
N 


next page.
[
(V1 (i), Vj+1 ) ∈ Am,j , for j = 1, . . . , K − 1
.



Thus, invoking Lemma 1, we have (44), where each of
i=1 m=1 
V2 ∈ Gm,2 , . . . , VK ∈ Gm,K
the probabilities at the r.h.s. of (44) are conditioned on F0 .
(40)
Therefore, we were able to simplify the problematic union
Thus, comparing (39) and (40), we readily notice the following over the codebook of the first user. Note, however, that we
parallels:
cannot (directly) apply here the method of types due to the
fact that the union is over an exponential number of types, and
• The numbers of events in the unions over i is L1 = M1 − 1.
Also, we have K = M2 independent random vectors V1 (i) = thus a more refined analysis is needed. We start by analyzing
X 1,i and Vl+1 = X 2,l , for 1 ≤ i ≤ M1 − 1 and 1 ≤ l ≤ the last term at the r.h.s. of (44). To this end, we will invoke
the type enumeration method, but first, the main observation
M2 − 1.
here is that similarly to the passage from (33) to (34), the last
• The union over m corresponds to a union over l, which as
was mentioned before, is actually a union over a vector of term at the r.h.s. of (44) can be rewritten as (46), shown at the

10








(x1 , x2,0 , y) ∈ T (Q̃0X1 X2,0 Y ),
n
oM2 −1
j
x
:
(x
,
x
,
y)
∈
T
(
Q̃
)
,
1
1
2,j
X1 X2 Y
Bm,1 =
j=1

n
o

M
−1
2



(x1,0 , x2,j , y) ∈ T (Q̂jX1,0 X2 Y )
for some {x2,j }j
j=1


(x1 , x2,0 , y) ∈ T (Q̃0X1 X2,0 Y ),



n
oM2 −1

{x2,j }j≥1 :
(x1 , x2,j , y) ∈ T (Q̃jX1 X2 Y )
,
Bm,2 =

n
oM2 −1j=1




(x1,0 , x2,j , y) ∈ T (Q̂jX1,0 X2 Y )
for some x1
j=1

(n)
P̃e,1





M[
2 −1
1 −1 M
X

, Pr 
≤ min



i=1











Pr 


P (Y |X 1,i , X 2,j ) ≥

j=0

j=0




1, M1 · Pr 


n

n

Q̃jX

1 X2 Y

,Q̂jX

Q̃jX

1 X2 Y

[

1 X2 Y

o

j

Q̃jX X Y
1 2

[

,Q̂jX

1 X2 Y

o

j

∈TI (QX1,0 X2,0 Y )

∈TI (QX1,0 X2,0 Y )






 n

[

,Q̂jX X Y
1 2

o



∈TI (QX1,0 X2,0 Y ) 


j

(47)

1
log P (y|x1,1 , x2,0 ) .
n

(48)

For a given (y, x1,0 , x1,1 , x2,0 ), and a given joint probability
distribution QX1 X2 Y on X1 × X2 × Y, let N1 (QX1 X2 Y )
designate the number of codewords {X 2,j }j (excluding x2,0 )
whose conditional empirical distribution with y and x1,1 is
QX1 X2 Y , that is,
N1 (QX1 X2 Y ) ,





{X 2,j }j≥1 ∈ B2 Q̃0X1 X2,0 Y , (Q̃jX1 X2 Y , Q̂jX1 X2 Y )j ) 
,

1
log P (y|x1,0 , x2,0 ) ,
n

M
2 −1
X

(43)



X 1,1 ∈ B1 Q̃0X1 X2,0 Y , (Q̃jX1 X2 Y , Q̂jX1 X2 Y )j ) 
,

(X 1,1 , x2,0 , y) ∈ T (Q̃0X1 X2,0 Y ),
oM2 −1
(X 1,1 , X 2,j , y) ∈ T (Q̃jX1 X2 Y )
,
n
oj=1
M2 −1
(x1,0 , X 2,j , y) ∈ T (Q̂jX1,0 X2 Y )
j=1

I {(x1,1 , X 2,j , y) ∈ T (QX1 X2 Y )} ,

j=1

(49)




















 


(44)

and let N2 (QX1 X2 Y ) designate the number of codewords
{X 2,j }j (excluding x2,0 ) whose conditional empirical distribution with y and x1,0 is QX1 X2 Y , that is
N2 (QX1 X2 Y ) ,

M
2 −1
X

I {(x1,0 , X 2,j , y) ∈ T (QX1 X2 Y )} .

j=1

(50)

Also, recall that
1
log P (y|x1 , x2 )
n 

= EQ log WY |X1 X2 (Y |X1 , X2 )

f (QX1 X2 Y ) =

and
r,

(42)










P (Y |X 1,0 , X 2,j ) F0 


next page. That is, we returned back to the structure of the
original probability in (24), but now, without the union over
the codebook of the first user. Note that the conditioning on
the random vector X 1,1 in (46), is due to the fact that X 1,1 is
common to all the summands in the inner summation over the
codebook of the second user. We next evaluate the exponential
behavior of the probability in (46). For a given realization of
Y = y, X 1,0 = x1,0 , X 1,1 = x1,1 , and X 2,0 = x2,0 , let us
define
s,

(41)



















M1 · Pr 
n


M
2 −1
X








(51)
(52)

where QX1 X2 Y is understood to be the joint empirical distribution of (x1 , x2 , y) ∈ X1n × X2n × Y n . Thus, in terms of the
above notations, we may write:
M
2 −1
X

P (y|x1,1 , X 2,j ) = enr

j=0

+

X

N1 (QX1 X2 Y ) enf (QX1 X2 Y )

(53)

QX2 |X1 Y ∈S(QX1 Y )

, enr + N1 (QX1 Y ).

(54)

where for a given QX1 Y , S(Q
 X1 Y ) is defined as
the set of all distributions
QX2 |X1 Y , such that

11



(X 1,1 , x2,0 , y) ∈ T (Q̃0X1 X2,0 Y ),



oM2 −1 

[


j
(X
,
X
,
y)
∈
T
(
Q̃
)
,


1,1
2,j
X1 X2 Y
Pr 

j=1


o
n
o



n j
M
−1
2

j
∈TI (QX1,0 X2,0 Y ) 
Q̃X X Y ,Q̂jX X Y



 (x1,0 , X 2,j , y) ∈ T (Q̂X1,0 X2 Y )
1 2
1 2
j
j=1



M
−1
2
2 −1

MX
X
P (Y |X 1,0 , X 2,j ) F0 
P (Y |X 1,1 , X 2,j ) ≥
= Pr 


j=0
j=0


 

M
2 −1
2 −1



MX
X
P (Y |X 1,0 , X 2,j ) F0 , X 1,1  F0 .
P (Y |X 1,1 , X 2,j ) ≥
= E Pr 









 n



(x1 ,y)∈X1 ×Y QX1 Y (x1 , y) QX2 |X1 Y
for all x2 ∈ X2 , namely,

Similarly,
P (y|x1,0 , X 2,j ) = ens

j=0

X

+

QX2 |X1,0 Y ∈S(QX1,0 Y )


N2 QX1,0 X2 Y enf (QX1,0 X2 Y ) (56)

, ens + N2 (QX1,0 Y ).

(57)

where for a given QX1,0 Y , S(Q
 X1,0 Y ) is defined as
the
set
of
all
distributions
QX2 |X1,0 Y , such that
P
=
(x1 ,y)∈X1 ×Y QX1,0 Y (x1 , y) QX2 |X1,0 Y (x2 |x1 , y)
PX2 (x2 ) for all x2 ∈ X2 (similarly as in (55)). For simplicity
of notation, in the following, we use Q and Q̃ to denote
QX1 X2 Y and QX1,0 X2 Y , respectively. Therefore, with these
definitions in mind, we wish to calculate (given (F0 , X 1,1 ))


M
M
2 −1
2 −1
X
X
P (Y |x1,0 , X 2,j )
Pr 
P (Y |x1,1 , X 2,j ) ≥
j=0

j=0

= Pr N1 (QX1 Y ) − N2 (QX1,0 Y ) ≥ ens − enr




(58)

where s, r, N1 (Q) and N2 (Q) are given in (47), (48), (54),
and (57), respectively.
Let ε > 0 be arbitrarily small, and
1
define i1 , nǫ
log P (y|x1,0 , x2,0 ) . Then,


Pr N1 (QX1 Y ) − N2 (QX1,0 Y ) ≥ ens − enr
⌈R2 /ε⌉

=

X

i=i1

⌈R2 /ε⌉

≤

X

i=i1

n
Pr eniε ≤ N2 (QX1,0 Y ) ≤ en(i+1)ε ,

N1 (QX1 Y ) − N2 (QX1,0 Y ) ≥ ens − enr
n
Pr eniε ≤ N2 (QX1,0 Y ) ≤ en(i+1)ε ,
N1 (QX1 Y ) ≥ e

⌈R2 /ε⌉

=

X

i=i1

n

niε


× Pr N1 (QX1 Y ) ≥ eniε + ens − enr

(x2 |x1 , y) = PX2 (x2 )


S(QX1 Y ) = Q′X1 X2 Y : Q′X1 Y = QX1 Y , Q′X2 = PX2 .
(55)
M
2 −1
X

+e

ns

−e

(46)

j=0

j=0

P

(45)

nr

Pr eniε ≤ N2 (QX1,0 Y ) ≤ en(i+1)ε

o

o

o

o
| eniε ≤ N2 (QX1,0 Y ) ≤ en(i+1)ε .

(60)

It is not difficult to show that (see, e.g., [15, p. 6028])
o
n
Pr ent ≤ N2 (QX1,0 Y ) ≤ en(t+ε)


t < t0 (QX1,0 Y ) − ε
0

·
= 1
t0 (QX1,0 Y ) − ε ≤ t ≤ t0 (QX1,0 Y )





exp −nE(t, QX1,0 Y )
t > t0 (QX1,0 Y )
(61)
where
t0 (QX1,0 Y ) , R2 +
max
Q̃∈S(QX1,0 Y ): IQ̃ (X2 ;X1,0 ,Y )≤R2

i
h
f (Q̃) − IQ̃ (X2 ; X1,0 , Y ) ,

(62)

in which S(Q) is defined in (55), f (Q) is given in (52), and
h
i
E(t, QX1,0 Y ) , min IQ̃ (X2 ; X1,0 , Y ) − R2 :
+

h
i
f (Q̃) + R2 − IQ̃ (X2 ; X1,0 , Y ) ≥ t . (63)
+

Now, in the exponential scale, the term at the r.h.s. of
(60) is dominated by one of the summands, and we
claim that the dominant contribution to the sum over i
is due to the
first term3 , i = t0 (QX1,0 Y )/ε. Indeed,
 nkε
let Ak , e
≤ N2 (QX1,0 Y ) ≤ en(k+1)ε and Bk ,

nkε
N1 (QX1 Y ) ≥ e
+ ens − enr , and notice that the summands in (60) correspond to Pr {Ak ∩ Bk }. According to
(61), Pr {At0 } → 1 (the exponent E(kε, QX1,0 Y ) vanishes),
and note that Pr {Bk } is monotonically decreasing with k.
Therefore,
Pr {At0 ∩ Bt0 } ≤ max Pr {Ak ∩ Bk }
k≥t0

≤ max Pr {Bk } = Pr {Bt0 } .
k≥t0

(64)

(59)
3 Note that according to (61), Pr{eniε ≤ N (Q
n(i+1)ε }
2
X1,0 Y ) ≤ e
vanishes (in the exponential scale) for i < t0 (QX1,0 Y )/ε. Thus, to asses
the exponential scale of (60) we consider only the indices correspond to i ≥
t0 (QX1,0 Y )/ε.

12

We claim that (79) can be rewritten as4

On the other hand,

·


Pr {At0 ∩ Bt0 } = Pr {Bt0 } − Pr Atc0 ∩ Bt0

≥ Pr {Bt0 } − Pr Atc0 .

Pe,3 =

max

QX1 |X2,0 Y ∈Ŝ(QX2,0 Y ) Q∈S(QX1 Y )

(80)

which
follows
from
the
fact
that
the
set
{x2 : (x1,1 , x2 , y) ∈ T (QX1 X2 Y ), for some x1,1 }
equals
T (QX2 Y ) (see, e.g., [11, eqs. (24)-(25)]). Thus, by using
standard large deviations techniques (see, e.g., [15, p. 6027])
·

Pr {At0 ∩ Bt0 } = Pr {Bt0 } .

(66)

Combining (60), (64) and (66), and the fact that ε is arbitrarily
small, we get (68) (shown at the top of the next page) by
using standard large deviations techniques (see, e.g., [15, p.
6027]), where N1 (Q) and S(Q) are defined in (49) and (55),
respectively, and
o
n
L̃ , Q : max [t0 , s] − f (Q) ≤ [R2 − IQ (X2 ; X1 , Y )]+ .
(69)
Thus,


Pr N1 (QX1 Y ) − N2 (QX1,0 Y ) ≥ ens − enr

·
= exp −nE1 (QX1 X2,0 Y , QX1,0 X2,0 Y )

o
n
Pr Ñ1 (Q) ≥ enγ ,

(65)

Thus, due to the fact that Pr {At0 } → 1 super-exponentially
fast [15, p. 6028], we may conclude that
·

max

(70)

where E1 (·, ·) is defined in (8c). Note that when r >
max [t0 , s], the r.h.s. term of the inequality in the probability
in (67) is negative, and due to the fact that the enumerator
is nonnegative, the overall probability is unity. Finally, we
average over X 1,1 given F0 . Using the method of types, we
readily obtain (73), given at the top of the next page, where

Ŝ(QX2 Y ) , Q′X1 X2 Y : Q′X2 Y = QX2 Y , Q′X1 = PX1 ,
(74)
and Ê1 (·, ·) is defined in (8g). This completes the analysis of
the last term at the r.h.s. of (44).
Next, we analyze the second and third terms at the r.h.s.
of (44). Recall that the latter is given by (75). Accordingly,
in the spirit of (46), we note that Pe,3 can be equivalently
rewritten as (78), shown at the top of the next page, where
s, r, N1 (Q), N2 (Q), and Ŝ(Q), are given in (47), (48),
(54), (57), and (74), respectively, and the second passage
follows by using the method of types. Now, due to the fact
that only N1 (and not N2 ) in (78) depends on x1,1 , and
since the analysis in (58)-(67) is independent of x1,1 , it can
be repeated here, and we obtain (79), shown at the top of
page 14, where N1 (Q) is given in (49), and we have defined
] + en[s−f (Q)] − en[r−f (Q)] . Recall
enγ , en[t0 (QX1,0 Y )−f (Q)P
M2 −1
(49), and let Ñ1 (Q) ,
j=1 I {(X 2,j , y) ∈ T (QX2 Y )}.

Pe,3 =

where

max

max

(81)

QX1 |X2,0 Y ∈Ŝ(QX2,0 Y ) Q∈S(QX1 Y )



1


e−n[IQ (X2 ;Y )−R2 ]+



0

r > max [t0 , s]
r ≤ max [t0 , s] , Q ∈ L̂

(82)

c

r ≤ max [t0 , s] , Q ∈ L̂

o
n
L̂ , Q : max [t0 , s] − f (Q) ≤ [R2 − IQ (X2 ; Y )]+ .
(83)
Therefore,
n
o
·
Pe,3 = exp −nÊ2 (QX1,0 X2,0 Y , R2 )

(84)

where Ê2 (QX1,0 X2,0 Y , R2 ) is defined in (8h). This completes
the analysis of the third term at the r.h.s. of (44). Finally, recall
that the second term at the r.h.s. of (44) is given by

[
A , M1 · Pr 
TI (QX1,0 X2,0 Y )

X 1,1




∈ B1 Q̃0X1 X2,0 Y , (Q̃jX1 X2 Y , Q̂jX1 X2 Y )j )  (85)

and is equivalent to (86), given at the top of page 14. This
term can be analyzed as before, but, we claim that it is
actually larger than the fourth term at the r.h.s. of (44), and
thus, essentially, does not affect the minimum in (44). Indeed,
recall that the fourth term is given by (87), shown at the top
of page 14, and since the factor M1 is common to both A
and B, we just need to compare the probabilities in these
terms. However, it is obvious that the probability term in
B is smaller than the probability in A, due to the fact that
events in the former are contained in the events in the latter.
Indeed, this is equivalent to comparing Pr {(Z1 , Z2 ) ∈ Z}
and Pr {(Z1 , z2 ) ∈ Z, for some z2 ∈ Z2 }, where Z1 and Z2
4 It is easy to see that (80) is an upper bound on (79). The other direction
follows from:
o
n
o
n
∗
max Pr Ñ1 (Q̂) ≥ enγ(Q) = max Pr Ñ1 (Q̂) ≥ enγ(Q )
Q̂∈S(Q∗ )

Q,Q̂∈S(Q)

=

max

Q̂∈S(Q∗ )

n

∗

o
Pr N1 (Q̂) ≥ enγ(Q ) , for some x1,1 ∈ T (Q∗ )

n
o
≤ max max Pr N1 (Q̂) ≥ enγ(Q) , for some x1,1 ∈ T (Q) ,
Q

Q̂∈S(Q)

where in the first equality we designate Q∗ as the maximizer,
and
the second equality follows from the fact that T (QX2 Y ) =

x2 : (x1,1 , x2 , y) ∈ T (QX1 X2 Y ), for some x1,1 .

13

 ·

Pr N1 (QX1 Y ) − N2 (QX1,0 Y ) ≥ ens − enr = Pr {Bt0 }
o
n
= Pr N1 (QX1 Y ) ≥ ent0 (QX1,0 Y ) + ens − enr
o
n
·
=
max Pr N1 (Q) ≥ en[t0 (QX1,0 Y )−f (Q)] + en[s−f (Q)] − en[r−f (Q)]
Q∈S(QX1 Y )

(67)



1


·
=
max
e−n[IQ (X2 ;X1 ,Y )−R2 ]+
Q∈S(QX1 Y ) 


0

r > max [t0 , s]
r ≤ max [t0 , s] , Q ∈ L̃

(68)

r ≤ max [t0 , s] , Q ∈ L̃c





M
2 −1
2 −1


MX
X
P (Y |X 1,0 , X 2,j ) F0 , X 1,1  F0
P (Y |X 1,1 , X 2,j ) ≥
E Pr 




j=0
j=0
)
(


·
= exp −n
min
IQ (X1 ; X2,0 , Y ) + E1 (QX1 X2,0 Y , QX1,0 X2,0 Y )



(71)

(72)

QX1 |X2,0 Y ∈Ŝ(QX2,0 Y )

n
o
, exp −nÊ1 (QX1,0 X2,0 Y , R2 )



Pe,3 , Pr 


n



Pe,3 = Pr 

Q̃jX X Y
1 2

[

[

,Q̂jX X Y
1 2

o

{X 2,j }j≥1 ∈ B2

j

∈TI (QX1,0 X2,0 Y )

P (y|x1,1 , x2,0 ) +
M
2 −1
X
j=1

·

=

max





Pr P (y|x1,1 , x2,0 ) +
+

M
2 −1
X
j=1

max
QX1 |X2,0 Y ∈Ŝ(QX2,0 Y )

M
2 −1
X

(88)

=

X

P (z1 ) = Pr {(Z1 , z2 ) ∈ Z, for some z2 } .

(77)
(78)

(91)

z1 ∈Ṽ

Wrapping up, using (24), (44), and the last results, after
averaging w.r.t. F0 , we get (96), shown at the top of the next
page, as required.

(89)
B. Proof of Theorem 2

(z1 ,z2 )∈Z

P (z1 , z2 )





Pr N1 (QX1 Y ) − N2 (QX1,0 Y ) ≥ ens − enr , for some x1,1 ∈ T (QX1 X2,0 Y )|F0

Then, it is obvious that Z ⊆ V, and thus
X
P (z1 , z2 )
Pr {(Z1 , Z2 ) ∈ Z} =
(z1 ,z2 )∈V

P (y|x1,1 , X 2,j ) ≥ P (y|x1,0 , x2,0 )

P (y|x1,0 , X 2,j ) , for some x1,1 ∈ T (QX1 X2,0 Y ) F0 

Ṽ , {z1 ∈ Z1 : (z1 , z2 ) ∈ Z, for some z2 ∈ Z2 } .

≤

(76)

j=1

are RVs that are defined over the alphabets Z1 and Z2 ,
respectively, and Z ⊆ Z1 × Z2 . Let V , Ṽ × Z2 , in which

X

(75)

P (y|x1,1 , X 2,j ) ≥ P (y|x1,0 , x2,0 )

P (y|x1,0 , X 2,j ) , for some x1,1 ∈ T (QX1 X2,0 Y ) F0  ,

QX1 |X2,0 Y ∈Ŝ(QX2,0 Y )

=




Q̃0X1 X2,0 Y , (Q̃jX1 X2 Y , Q̂jX1 X2 Y )j ) 
.

j=1

QX1 |X2,0 Y

+

M
2 −1
X



(73)

(90)

Without loss of generality, we assume throughout, that the
transmitted codewords are x1,0 and x2,0 which correspond

14

⌈R2 /ε⌉
·

Pe,3 =

X

max

QX1 |X2,0 Y ∈Ŝ(QX2,0 Y ) i=i
1

× Pr
·

=

max
QX1 |X2,0 Y ∈Ŝ(QX2,0 Y )

·

=

max

o
n
Pr eniε ≤ N2 (QX1,0 Y ) ≤ en(i+1)ε


[




x1,1

o
n
Pr N1 (QX1 Y ) ≥ ent0 (QX1,0 Y ) + ens − enr , for some x1,1
max

QX1 |X2,0 Y ∈Ŝ(QX2,0 Y ) Q∈S(QX1 Y )






 n



N1 (QX1 Y ) ≥ eniε + ens − enr eniε ≤ N2 (QX1,0 Y ) ≤ en(i+1)ε


[

A = M1 · Pr 


TI (QX1,0 X2,0 Y ) 







Pr {N1 (Q) ≥ enγ , for some x1,1 } ,

(79)

(X 1,1 , x2,0 , y) ∈ T (Q̃0X1 X2,0 Y ),
oM2 −1
(X 1,1 , x2,j , y) ∈ T (Q̃jX1 X2 Y )
, for some {x2,j }
j=1
n
oM2 −1
(x1,0 , x2,j , y) ∈ T (Q̂jX1,0 X2 Y )
j=1



(X 1,1 , x2,0 , y) ∈ T (Q̃0X1 X2,0 Y ),




n
oM2 −1

[

j
(X
,
X
,
y)
∈
T
(
Q̃
)
,

1,1
2,j
X1 X2 Y
B , M1 · Pr 
j=1
n
o

TI (QX1,0 X2,0 Y ) 
M
−1
2


 (x1,0 , X 2,j , y) ∈ T (Q̂jX1,0 X2 Y )


j=1








.















,








n
n
oo
(n) ·
P̄e,1 ≤ E min 1, e−n(Ê1 (QX1,0 X2,0 Y ,R2 )−R1 ) , e−nÊ2 (QX1,0 X2,0 Y ,R2 )



−n[Ê1 (QX1,0 X2,0 Y ,R2 )−R1 ]
−nÊ2 (QX1,0 X2,0 Y ,R2 )
+, e
= E min e


h

i
= E exp −n max Ê1 (QX1,0 X2,0 Y , R2 ) − R1 , Ê2 (QX1,0 X2,0 Y , R2 )
+
#)
(
"


·
D(QY |X1,0 X2,0 ||WY |X1,0 X2,0 |PX1,0 × PX2,0 ) + E(Q, R1 , R2 )
= exp −n
min
QY |X1,0 X2,0

h

i
E(Q, R1 , R2 ) , max Ê1 (QX1,0 X2,0 Y , R2 ) − R1 , Ê2 (QX1,0 X2,0 Y , R2 ) .
+

to z 11,0 , z 12,0 , z 21,0 and z 22,0 . Here, we distinguish between
several types of errors. Recall that the overall error probability
is given by
(n)

P̄e,1 = Pr {(m̂11 , m̂12 ) 6= (0, 0)} ,

(98)

which can be divided into six possible types of errors: (m̂11 6=
0, m̂12 = 0, m̂21 = 0), (m̂11 = 0, m̂12 6= 0, m̂21 = 0),
(m̂11 6= 0, m̂12 6= 0, m̂21 = 0), (m̂11 6= 0, m̂12 = 0, m̂21 6=
0), (m̂11 = 0, m̂12 6= 0, m̂21 6= 0), and (m̂11 6= 0, m̂12 6=
0, m̂21 6= 0). Note that the event (m̂11 = 0, m̂12 = 0, m̂21 6=
0) will not result in an error, and thus ignored. Obviously,
the exponent of the overall error probability in (98) is given
by the minimum between the error exponents corresponding to
each type of error individually. We start with analyzing the last
error event, which is also the most involved one. For this event,

(86)

(87)

(93)
(94)
(95)
(96)
(97)

the average probability of error, associated with the decoder in
(14), is given by (100), given at the top of the next page, where
Z̃ ijk , (Z 11,i , Z 12,j , Z 21,k ), Z̃ 0 , (Z 11,0 , Z 12,0 , Z 21,0 ),
and F0 , (Z̃ 0 , Z 22,0 , Y ). We will assess the exponential
behavior of (100) in the same manner as we did for (24).
Specifically, we start with expressing (100) in terms of types.
First, for a given joint distribution QZ14 Y , we let
f (QZ14 Y ) ,

1
log P (y|x1 (z 1 , z 2 ), x2 (z 3 , z 4 )) .
n

(101)

4 Y of the random vectors
Now, for a given joint type QZ1,0
4 Y ) in
(Z 1,0 , Z 2,0 , Z 3,0 , Z 4,0 , Y ), we define the set TI (QZ1,0
(102) given at the top of the next page. Now, with these
4 Y , it follows, by definition, that the
definitions, fixing QZ1,0

15



M[
21 −1
12 −1 M[
11 −1 M[

Pe(7) , Pr 
=E





j=1

i=1



k=1

(M −1
22
X
l=0

M[
21 −1
12 −1 M[
11 −1 M[

Pr 

j=1

i=1

P (Y |Z̃ ijk , Z 22,l ) ≥

k=1

l=0

(M −1
22
X

P (Y |Z̃ ijk , Z 22,l ) ≥

l=0

1

e

1,0 Z4 Y

l=1

nf (Q̃0Z 3 Z

4,0 Y

1

)

)

P (Y |Z̃ 0 , Z 22,l ) 

MX
22 −1

+

MX
22 −1 

e

oM22 −1 
l=1

nf (Q̃lZ 4 Y )
1

−e

(99)
)

P (Y |Z̃ 0 , Z 22,l )

l=0


n
oM22 −1 n
4 Y ),
TI (QZ1,0
Q̃0Z 3 Z4,0 Y ∈ S0 ,
Q̃lZ 4 Y
, Q̂lZ 3
1

MX
22 −1



F0 


∈ S1 :

nf (Q̂lZ 3

1,0

Z4 Y

)

l=1



≥e

nf (QZ 4

1,0

Y

)

)

n
o
4 Y ) ,
S0 (QZ1,0
Q̃0Z 3 Z4,0 Y : Q̃0Zi = PZi , Q̃0Z4,0 Y = QZ4,0 Y , ∀1 ≤ i ≤ 4 ,
n 1
oM22 −1
oM22 −1 n
4 Y ) ,
: Q̃lZi = PZi , Q̃lY = QY ,
, Q̂lZ 3 Z4 Y
S1 (QZ1,0
Q̃lZ 4 Y
1

1,0

l=1

Q̂lZi

=

PZi , Q̂lZ 3 Y
1,0

l=1

3 Y , ∀1 ≤ i ≤ 4, ∀1 ≤ l ≤ M22 − 1
= QZ1,0

1

error event

j=1

i=1

(M −1
22
X

k=1

P (Y |Z̃ ijk , Z 4,l ) ≥

l=0

MX
22 −1

)

P (Y |Z̃ 0 , Z 4,l )

l=0

(105)

can be rewritten, in terms of types, as follows
M[
21 −1
12 −1 M[
11 −1 M[
i=1

j=1

k=1

[

(106)

TI (QZ 4

1,0 Y

)


(Z̃ ijk , z 4,0 , y) ∈ T (Q̃0Z 3 Z4,0 Y ),


1

oM22 −1
 n
l
(Z̃ ijk , Z 4,l , y) ∈ T (Q̃Z 4 Y )
,
1

ol=1
n

M22 −1

 (z̃ 0 , Z 4,l , y) ∈ T (Q̂l 3
)
Z Z4 Y
1,0

l=1







.

(107)






We next analyze the probability of (107), conditioned on F0 .
Note that the inner union in (107) is over vectors of types (an
exponential number of them). Finally, as before, we simplify
the notations of (107), and write it equivalently as
M[
11 −1 M[
12 −1 M[
21 −1 [
i=1







j=1

k=1

(108)

l

Z̃ ijk ∈ Al,0 ,

(Z̃ ijk , Z 4,m ) ∈ Al,m ,
Z 4,m ∈ Ãl,m ,

for m = 1, . . . , M22 − 1

for m = 1, . . . , M22 − 1







(109)

where, again, the index “l” in the inner union runs over the
combinations of types (namely, l = {Q̃lZ 4 Y , Q̂lZ 3 Z4 Y }l ) that
1

(102)
(103)

o
Q̃lZ4 Y = Q̂lZ4 Y , Q̃lZ 3 Y = Q̃m
Z 3 Y , ∀l, m .

M[
21 −1
12 −1 M[
11 −1 M[

(100)

1,0

4 Y ), and the various sets {Al,j , Ãl,j }l,j
belong to TI (QZ1,0

(104)

1

correspond to the typical sets in (107) (recall that
(z 1,0 , z 2,0 , z 3,0 , z 4,0 , y) are given in this stage). Similarly as
in the proof of Theorem 1, we derive upper bound on a generic
probability which have the form of (109). In the following,
we give a generalization of Lemma 1 to the probability of a
union indexed by K values. The proof is very similar to the
proof of Lemma
 1, and thus omitted for brevity. For a given
subset J = j1 , . . . , k|J | of {1, . . . , J} we write Z J as a
shorthand for (Zj1 , . . . , Zj|J | ).
N

N

1
J
Lemma 2 Let
{Z1 (i)}i=1
, . . . , {ZJ (i)}i=1
and
NJ+1
NJ+1
NJ+1
be
{V1 (i)}i=1 , {V2 (i)}i=1 , . . . , {VK (i)}i=1
independent
sequences
of
independently
and
identically distributed (i.i.d.) RVs on the alphabets
Z1 × . . . × ZJ × V1 × . . . × VK , respectively, with Z1 (i) ∼
PZ1 , . . . , ZJ (i) ∼ PZJ , V1 (i) ∼ PV1 , . . . , VK (i) ∼ PVK . Fix
N
N
N
a sequence of sets {Ai,1 }i=1 , {Ai,2 }i=1 , . . . , {Ai,K }i=1 ,
where Ai,j ⊆ Z1 × . . . × ZJ × Vj , for 1 ≤ j ≤ K
N
and for all 1 ≤ i ≤ N . Also, fix a set {Ai,0 }i=1 where
Ai,0 ⊆ Z1 × . . . × ZJ for all 1 ≤ i ≤ N , and another
N
N
N
sequence of sets {Gi,1 }i=1 , {Gi,2 }i=1 , . . . , {Gi,K }i=1 , where
Gi,j ⊆ Vj , for 1 ≤ j ≤ K and for all 1 ≤ i ≤ N . Let
U = (Z1 , Z2 , . . . , ZJ , UJ+1 ) with UJ+1 , (V1 , . . . , VK ).
Finally, define Bl,J given in (110), for l = 1, 2, . . . , N , and
Z(iJ1 ) = (Z1 (i1 ), . . . , ZJ (iJ )). Then, a general upper bound
is given by (111), shown at the top of the next page.

Applying Lemma 2 on (107) (or, (109)) we obtain (112),
shown at the top of the next page, where N1 = M11 , N2 =
M12 , N3 = M21 , N4 = 1, and
U = (Z 11 , Z 12 , Z 21 , U 4 )

(113)

in which U 4 = (Z 4,1 , . . . , Z 4,M22 −1 ), and Bl,J is given in
(114), also shown at the top of the next page. The various

16

Bl,J ,




uJ : z1J ∈ Al,0 ,


Pr

i1 ,j

Z(iJ1 ) ∈ Al,0 ,

l=1

K
\

k=1

≤ min




1,


Pr


z1J , vj ∈ Al,j ,

j=1


(N (
[ [
J

K
\



i=1

j=1

·

≤ min

k=1




1,



Bl,J

vj ∈ Gl,j for some uJ c

k=1

min




Y

j∈J



Nj  Pr

min

(N
[

P (Y |Z̃ ijk , Z 4,l ) ≥

U J ∈ Bl,J

J ⊆{1,...,4}J 6=∅



Y

j∈J

Nj  Pr

(

[

U J ∈ Bl,J

l

)


l=1






,

(115)

namely, we have 15 possibilities. We claim that possibilities {1, 2, 3, 12, 13, 23, 123} do not affect the outer
minimum in (112), and so we left with possibilities
{4, 14, 24, 34, 124, 134, 234, 1234}. This observation follows
from the same arguments used in (86)-(91) for the second term
at the r.h.s. of (44). For example, possibilities {1, 2, 3} do not
affect the outer minimum due to the fact that the probabilities
that correspond to possibilities {14, 24, 34}, respectively, are
smaller. Indeed, the multiplicative factors in (112) for each of
the pairs (1, 14), (2, 24), and (3, 34), are the same, but the
respective probabilities in (112) are smaller for {14, 24, 34}
(due to the same reason used in (91)). Similarly, possibilities
{12, 13, 23, 123} do not affect the outer minimum due to
possibilities {124, 134, 234, 1234}, respectively.
In the following, we analyze the remaining terms. For
example, the term that corresponds to possibility “1234”, is
given by
(
)
[
Pe,1234 , M11 M12 M21 Pr
(116)
U ∈ Bl,1234 ,
l

.



(111)

F0





(112)



(z̃ 111 , z 4,0 , y) ∈ T (Q̃0X1 X2,0 Y ),
n
oM22 −1
uJ : (z̃ 111 , z 4,l , y) ∈ T (Q̃lZ 4 Y )
,
=
1
l=1
 n
oM22 −1


 (z̃ , z , y) ∈ T (Q̂j
, for some uJ c
0
4,l
X1,0 X2 Y )







)


P (Y |Z̃ 0 , Z 4,l )







possibilities for the set J are,

1; 2; 3; 4;



 12; 13; 14; 23; 24; 34;

123; 124; 134; 234;



1234

(110)

))


)

l=0



,



l=1

MX
22 −1

l=0







j=1

K
\

Z(iJ1 ), Vk (j) ∈ Al,k ,
Vk (j) ∈ Gl,k

J ⊆{1,...,J+1}J 6=∅


(M −1
21 −1
22
12 −1 M[
11 −1 M[
 M[
X

K
\







(114)






which similarly to the passage from (105) to (107), can be
rewritten as in (117), shown at the top of the next page.
Equation (117) has the same form of the probability in (71),
which we already analyzed. Accordingly, we similarly obtain
(120), where E7 (·, ·) is defined in (A.4), and S{4} (Q) is given
in (A.1).
The other terms are handled in a similar fashion. Specifically, let Ẑ , {Z1 , Z2 , Z3 }, and define
the sets U
= {1, 2, 3, 12, 13, 23, 123}, and Ũ
=
{14, 24, 34, 124, 134, 234, 1234}. Then, define for any5 u ∈
{1, 2, . . . , 7}:
(
)
[
(6)
Pe,u , MU (u) · Pr
U Ũ(u) ∈ Bl,Ũ (u) ,
(121)
l

where
MU (1) , M11 ; MU (2) = M12 ; MU (3) = M21 ;
MU (4) = M11 M12 ; MU (5) , M11 M21 ;
MU (6) = M12 M21 MU (7) = M11 M12 M21 .

(122)

Accordingly, following (49)-(84), we get (123), shown at the
top of the next page, where Eu (·, ·) is defined in (A.4). Note
that the mutual information term in the above exponent is due
to the averaging over Ẑ U (u) , and it is resulted by using the
method of types as in (72). This concludes the analysis for
5 Note

(6)

that Pe,7 correspond to Pe,1234 in (117).

17

Pe,1234 = M11 M12 M21 Pr
= M11 M12 M21 E

E

(

Pr

(M −1
22
X

P (Y |Z̃ 111 , Z 4,l ) ≥

l=0
(M −1
22
X

(

Pr

= exp −n

min

∈S{4} (QZ 4

1,0

n
o
(6)
4 Y , R22 )
, exp −nÊ7 (QZ1,0

(6) ·
=
Pe,u

(

exp −n

QZ 3 |Z

min

4,0 Y

1

∈S{4} (QZ 4

1,0 Y

o
4 Y , R22 )
, exp −nÊu(6) (QZ1,0
n

MX
22 −1
l=0

4,0 Y

)

Y

)

= exp −n

QZ 3 |Z
1

4,0 Y

min

∈S{4} (QZ 4

1,0

n
o
(6)
4 Y , R22 )
, exp −nÊ8 (QZ1,0

Y

)

P (Y |Z̃ 0 , Z 4,l ) F0 , Z̃ 111

)

F0

)

F0

)

)

(117)

(118)
)

(119)
(120)

)
h
i
4 Y )
IQ (Ẑ U (u) ; Z4,0 , Y |Ẑ 123\U (u) ) + Eu (QZ13 Z4,0 Y , QZ1,0
(123)

l

·

P (Y |Z̃ 0 , Z 4,l ) F0 , Z̃ 111

h
i
4 Y )
IQ (Z13 ; Z4,0 , Y ) + E7 (QZ13 Z4,0 Y , QZ1,0

possibilities {14, 24, 34, 124, 134, 234, 1234}, and we left with
possibility {4}, which is very similar to (75). Accordingly,
using the same arguments in (78)-(84), we obtain
(
)
[
(6)
Pe,8 , Pr
U 4 ∈ Bl,4
(

)

l=0

P (Y |Z̃ 111 , Z 4,l ) ≥

1

P (Y |Z̃ 0 , Z 4,l ) F0

P (Y |Z̃ 111 , Z 4,l ) ≥

l=0

QZ 3 |Z

MX
22 −1

l=0
MX
22 −1

l=0

(

·

( M −1
22
X

)

4 Y )
E0 (QZ13 Z4,0 Y , QZ1,0

(124)

where E0 (·, ·) is, again, defined in (A.4). Wrapping up, using
(100), (112), and the last results, after averaging w.r.t. F0 , we
get (129), shown at the top of the next page, where Ru for
u = 1, 2, . . . , 7 is defined in (A.6).
This concludes the analysis of the error event (m̂11 6=
0, m̂12 6= 0, m̂21 6= 0) in (98). The other types of errors
are analyzed in a similar manner. For (m̂11 6= 0, m̂12 =
0, m̂21 = 0), the average probability of error, associated
with the decoder in (14) is given in (131), given at the
top of the next page, where F0 , (Z̃ 0 , Z 22,0 , Y ). Thus,
due to the fact that (Z 12,0 , Z 21,0 ) are now fixed, they play
a same role as Y and Z 22,0 . Accordingly, following the
same steps as in (78)-(84), we get (132), presented at the
top of the next page, where E6 (·, ·) and E7 (·, ·) are defined
in (A.4), and S{2,3,4} (Q) is given in (A.1). Again, since
(Z 12,0 , Z 21,0 ), which correspond to (Z2,0 , Z3,0 )), are fixed,
(2)
they are conjugated to (Z4,0 , Y ). The error exponent of Pe
which corresponds to (m̂11 = 0, m̂12 6= 0, m̂21 = 0) can
be derived in the same way. We get that the exponent of
(2)
Pe is obtained by replacing the role of Z1 with Z2 and

(3)

R1 with R2 , in (132)-(134). Similarly, Pe , corresponding
to (m̂11 6= 0, m̂12 6= 0, m̂21 = 0), is upper bounded by
(136), presented at the top of the next page, where S{3,4} (Q)
is defined in (A.1).
(4)
(5)
Finally, the error exponents of Pe and Pe , corresponding
to (m̂11 6= 0, m̂12 = 0, m̂21 6= 0) and (m̂11 = 0, m̂12 6=
0, m̂21 6= 0), respectively, are obtained in the same way. The
(4)
exponent of Pe is obtained by replacing the role of Z2 with
Z3 , and changing the minimization in (137) to over the indexes
(5)
{1, 3, 5}, and the exponent of Pe is obtained by replacing the
role of Z1 with Z3 , and changing the minimization in (137)
to over the indexes {2, 3, 6}.

A PPENDIX A
D EFINITIONS FOR T HEOREM 2
In this appendix, we give the definitions of the various
parameters appearing in Theorem 2. For simplicity of notation,
in the following, we use the indexes {1, 2, 3, 4} instead of
{11, 12, 21, 22}, respectively. Let Z , (Z1 , Z2 , Z3 ), and
U , {1, 2, 3, 12, 13, 23, 123}. For u ∈ {0, 1, 2, . . . , 7}, Z U (u)
is a random vector consisting of the RVs corresponding to the
indexes in U(u), for example, Z 1 , Z U (1) = Z1 , Z 12 ,
Z U (4) = (Z1 , Z2 ), Z 123 , Z U (7) = (Z1 , Z2 , Z3 ), and so on,
where we define Z U (0) = ∅. Let also Z̃ , {Z1 , Z2 , Z3 , Z4 },
I ⊆ {1, 2, 3, 4}, and Z̃ I be the restriction of the entries of Z̃
on the set I. Then, let
o
n
SI (Q) , Q̃ : Q̃z̃I Y1 = Qz̃ I Y1 , Q̃Zi = PZi , for i ∈ I c .
(A.1)

18

Pe(6)

·

(

(







≤ E min 1, min e

=E

min


(6)
−n Êu
(QZ 4


(6)
−n Êu
(QZ 4

(

= exp −n
(6)
4 Y
EHK (QZ1,0

) , max



Pe(1) = Pr
=E

,R22 )−n−1 log MŨ (u)

"

,R22 )−n−1 log MŨ (u)

1,0 Y



= E exp −n max max
·

Y



u∈{1:7}

min e
u∈{1:7}
"
(


(

1,0

u

4 Y
Êu(6) (QZ1,0



(6)

,e

−nÊ8 (QZ 4

1,0 Y

(6)

+

,e

−nÊ8 (QZ 4

1
, R22 ) − log MŨ(u)
n

1,0



+

))

(125)




(126)

,R22 )

,R22 )
Y



(6)
4 Y
, Ê8 (QZ1,0

)#)

, R22 )

#)
h
i
(6)
4 ||WY |Z 4 |PZ 4 ) + E
4 Y )
min D(QY |Z1,0
HK (QZ1,0
1,0
1,0

(128)

QY |Z 4

1,0


i
h
(6)
(6)
4 Y , R22 )
4 Y , R22 ) − Ru
, Ê8 (QZ1,0
max Êu (QZ1,0

u∈{1:7}

P (Y |Z̃ i00 , Z 22,l ) ≥

i=1
l=0
"M −1 (M −1
22
11
X
[

Pr

i=1

(

≤ exp −n

"

MX
22 −1

)#

P (Y |Z̃ 0 , Z 22,l )

l=0
MX
22 −1

P (Y |Z̃ i00 , Z 22,l ) ≥

l=0

·

Pe(1)

(129)

+

"M −1 (M −1
22
11
X
[

(

min

QY |Z 4

1,0

)

P (Y |Z̃ 0 , Z 22,l )

l=0

h

(130)

4 ||WY |Z 4 |PZ 4 ) +
D(QY |Z1,0
1,0
1,0

F0

(1)
4 Y
EHK (QZ1,0

#)

i
)

#)

h

i
(1)
(1)
4 Y , R22 )
4 Y , R22 ) − R1
) , max Ê (QZ1,0
, Ê8 (QZ1,0
+
h
i
4
4 Y , R22 ) =
4 Y , QZ 4 Y )
Ê (1) (QZ1,0
min
IQ (Z1 ; Z2,0
, Y ) + E7 (QZ1 Z2,0
1,0
(1)
4 Y
EHK (QZ1,0

QZ

∈S{2,3,4} (QZ 4

QZ

∈S{2,3,4} (QZ 4

4
1 |Z2,0 Y

1,0 Y

(1)

4 Y , R22 ) =
Ê8 (QZ1,0

Pe(3)

min

4
1 |Z2,0 Y

(

·

≤ exp −n

1,0 Y

"

)

)

4 Y , QZ 4 Y )
E6 (QZ1 Z2,0
1,0

#)
h
i
(3)
4 ||WY |Z 4 |PZ 4 ) + E
4 Y )
min D(QY |Z1,0
HK (QZ1,0
1,0
1,0

QY |Z 4

QZ 2 |Z 4
1

3,0

Y

(3)

4 Y , R22 ) =
Ê2 (QZ1,0

QZ 2 |Z 4
1

3,0 Y

(3)

4 Y , R22 ) =
Ê4 (QZ1,0

∈S{3,4} (QZ 4

1,0 Y

min

∈S{3,4} (QZ 4

3,0 Y

Y

min

QZ 2 |Z 4
1

f (QZ14 Y1 ) , EQ

1,0

∈S{3,4} (QZ 4

3,0 Y

(3)

4 Y , R22 ) =
Ê8 (QZ1,0

∈S{3,4} (QZ 4

QZ 2 |Z 4
1

(131)

(132)
(133)
(134)
(135)

(136)

1,0


i
h
(3)
(3)
4 Y , R22 )
4 Y , R22 ) − Ru
, Ê8 (QZ1,0
) , max
max Êu (QZ1,0
+
u∈{1,2,4}
h
i
(3)
4
4 Y , QZ 4 Y )
4 Y , R22 ) =
IQ (Z1 ; Z3,0
, Y |Z2 ) + E5 (QZ12 Z3,0
Ê1 (QZ1,0
min
1,0


(3)
4 Y
EHK (QZ1,0

Define

(127)

1,0 Y

min

1,0 Y

)

)

)

)

h
i
4
4 Y , QZ 4 Y )
IQ (Z2 ; Z3,0
, Y |Z1 ) + E6 (QZ12 Z3,0
1,0

h
i
4
4 Y , QZ 4 Y )
IQ (Z1 , Z2 ; Z3,0
, Y ) + E7 (QZ12 Z3,0
1,0
4 Y , QZ 4 Y )
E3 (QZ12 Z3,0
1,0

(137)
(138)
(139)
(140)
(141)

and let


f (Q̂) − IQ̂ (Z4 ; Z13 , Y1 ).
max
 r0 (QZ13 Y1 ) , R22 +
Q̂:
Q̂∈S
(Q)
{1,2,3}
log WY1 |X1 X2 (Y1 |X1 (Z1 , Z2 ), X2 (Z3 , Z4 ))
IQ̂ (Z4 ;Z13 ,Y1 )≤R22
(A.2)
(A.3)

19

inequality follows from the fact that min {1, x} ≤ 1. The third
term in (38) follows in a similar fashion, and the forth term
follows from the fact that min {1, x} ≤ x, and thus we get
(B.5), which concludes the proof.

For u ∈ {0, 1, 2, . . . , 7}, define
Eu (Q̃Z14 Y1 , QZ14 Y1 ) ,
min
Q̂: Q̂∈S{1,2,3} (Q̃)
Q̂∈Du (Q̃Z 4 Y ,QZ 4 Y )
1

1

i
h
IQ̂ (Z4 ; Z U (u) , Y1 ) − R22 ,
+

1 1

(A.4)
where


A PPENDIX C
C OMPUTATIONAL A SPECTS OF

THE

E XPONENTS

In this appendix, we discuss the computation of (8j), similarly as in [21]. We start with an alternative formulation of
(8j). Recall that

h
i
Du (Q̃Z14 Y1 , QZ14 Y1 ) , Q̂ : max r0 (QZ14 Y1 ), f (QZ14 Y1 )
Ẽ1 (R1 , R2 ) = min {D(Q||W ) + E(Q, R1 , R2 )} , (C.1)
Q

h
i 
where
≤ max f (Q̃Z14 Y1 ), f (Q̂) + R22 − IQ̂ (Z4 ; Z U (u) , Y1 )
h

+
i
(A.5)
E(Q, R1 , R2 ) = max Ê1 (Q, R2 ) − R1 , Ê2 (Q, R2 ) .
+
Finally, we let
(C.2)
R1 , R11 ; R2 , R12 ; R3 , R21 ; R4 , R11 + R12 ;
R5 , R11 + R21 ; R6 , R12 + R21 ;
R7 , R11 + R12 + R21 .

(A.6)

Using all the above definition, we define (A.7)-(A.30), shown
at the top of page 20.
A PPENDIX B
P ROOF OF L EMMA 1
We prove a generalized version of Lemma 1, where we conL2
L2
sider random sequences, {V2 (i)}i=1
, . . . , {VK (i)}i=1
, rather
than single RVs V2 , . . . , VK . Lemma 1 is then obtained on
substituting L2 = 1. We start with the following result which
can be thought of as an extension of [11, Lemma 2].
L2
L2
1
Lemma 3 Let
{V1 (i)}L
i=1 , {V2 (i)}i=1 , . . . , {VK (i)}i=1
be independent sequences of independently and
identically distributed (i.i.d.) RVs on the alphabets
V1 × V2 × . . . × VK , respectively, with V1 (i) ∼
PV1 , V2 (i) ∼ PV2 , . . . , VK (i) ∼ PVK . Fix a sequence
N
N
N
of sets {Ai,1 }i=1 , {Ai,2 }i=1 , . . . , {Ai,K−1 }i=1 , where
Ai,j ⊆ V1 × Vj+1 , for 1 ≤ j ≤ K − 1 and for all
N
1 ≤ i ≤ N . Also, fix a set {Ai,0 }i=1 where Ai,0 ⊆ V1
for all 1 ≤ i ≤ N , and another sequence of sets
N
N
N
{Gi,2 }i=1 , {Gi,3 }i=1 , . . . , {Gi,K }i=1 , where Gi,j ⊆ Vj ,
for 2 ≤ j ≤ K and for all 1 ≤ i ≤ N . We have (B.1), shown
at the top of page 21, with (V1 , . . . , VK ) ∼ PV1 · · · × PVK .

Proof of Lemma 3: The second term in (B.1) follows by
first applying the union bound over i as in (B.2), shown at the
top of page 21, and then we apply the truncated union bound to
the union over j, and obtain (B.3). The third term is obtained
similarly by applying the union bounds in the opposite order,
and the upper bound of 1 is trivial.
We are now in a position to prove Lemma 1.
Proof of Lemma
S 1: To obtain (38) we weaken (B.1) as
follows. Let F , N
l=1 {V1 ∈ Bl,1 }. The second term in (38)
follows from (B.4), shown at the top of page 21, where the
second equality follows from T
the fact that the inner term in
N
the expectation vanishes over l=1 {V1 ∈
/ Bl,1 }, and the third

In the following, for a given QY1 |X1 X2 , we show that
Ê1 (Q, R2 ) and Ê2 (Q, R2 ) can be calculated efficiently. For
˜ Q̃) ≡ I (X1 ; X2 , Y1 ) and I(
ˆ Q̂) ≡
brevity, we let I(
Q̃
IQ̂ (X2 ; X1 , Y1 ). Recall that

i 
h
˜ Q̃) + I(
ˆ Q̂) − R2
,
I(
Ê1 (Q, R2 ) =
min
+

Q̃∈S(Q),Q̂∈Ŝ(Q̃),
Q̂∈L(Q̃,Q)

Ê2 (Q, R2 ) =

min
Q̃∈S(Q),Q̂∈Ŝ(Q̃),
Q̂∈L̂(Q̃,Q)

(C.3)
i
h
IˆQ̂ (X2 ; Y1 ) − R2 , (C.4)
+

where L and L̂ are defined in (8e) and (8f), respectively,
S(Q) = {Q̃ : Q̃X1 = PX1 , Q̃X2 Y1 = QX2 Y1 }, and
Ŝ(Q̃) = {Q̂ : Q̂X2 = PX2 , Q̂X1 Y1 = Q̃X1 Y1 }. In [21],
it was shown that Ê1 (Q, R2 ) can be equivalently expressed in
terms of the minimum between the following terms:
Ê1′ (Q, R2 ) ,
Ê1′′ (Q, R2 ) ,
Ê1′′′ (Q, R2 )

,

min

˜ Q̃),
I(

(C.5)

Q̃∈S(Q),max[t0 (Q),f (Q)]≤f (Q̃)

min

ˆ Q̂)≤R2
Q̃∈S(Q),Q̂∈Ŝ(Q̃),I(
ˆ Q̂)
max[t0 (Q),f (Q)]≤f (Q̂)+R2 −I(

min
Q̃∈S(Q),Q̂∈Ŝ(Q̃)
t0 (Q),f (Q)≤f (Q̂)

˜ Q̃),
I(

(C.6)


i 
h
˜
ˆ
.
I(Q̃) + I(Q̂) − R2
+

(C.7)
Using the same arguments as in [21], it can be shown that
Ê2 (Q, R2 ) can be equivalently be expressed as
i
h
IQ̂ (X2 ; Y1 ) − R2 .
Ê2′′ (Q, R2 ) ,
min
Q̃∈S(Q),Q̂∈Ŝ(Q̃)
max[t0 (Q),f (Q)]≤f (Q̂)

+

(C.8)
Accordingly, from (C.5)-(C.7) and (C.8), we see that (C.3)
and (C.4) can be expressed in terms of convex optimization
problems, namely, for a given QY1 |X1 X2 , the terms Ê1 (Q, R2 )
and Ê2 (Q, R2 ) (i.e., the inner terms of the minimization
problem in (C.1)) can be calculated efficiently, as desired.
Finally, we discuss the computation of (C.1). Generally
speaking, the minimization over QY1 |X1 X2 might not be a

20

Ê (1) (QZ14 Y1 , R22 ) ,
Ê (2) (QZ14 Y1 , R22 ) ,
(1)

Ê8 (QZ14 Y1 , R22 ) ,
(2)

Ê8 (QZ14 Y1 , R22 ) ,
(3)

Ê1 (QZ14 Y1 , R22 ) ,
(3)

Ê2 (QZ14 Y1 , R22 ) ,
(3)

Ê4 (QZ14 Y1 , R22 ) ,
(3)

Ê8 (QZ14 Y1 , R22 ) ,
(4)

Ê1 (QZ14 Y1 , R22 ) ,
(4)

Ê3 (QZ14 Y1 , R22 ) ,
(4)

Ê5 (QZ14 Y1 , R22 ) ,
(4)

Ê8 (QZ14 Y1 , R22 ) ,
(5)

Ê2 (QZ14 Y1 , R22 ) ,
(5)

Ê3 (QZ14 Y1 , R22 ) ,
(5)

Ê6 (QZ14 Y1 , R22 ) ,
(5)

Ê8 (QZ14 Y1 , R22 ) ,
Êu(6) (QZ14 Y1 , R22 ) ,
(6)

Ê8 (QZ14 Y1 , R22 ) ,

min
Q̃: Q̃∈S{2,3,4} (Q)

min
Q̃: Q̃∈S{1,3,4} (Q)

min
Q̃: Q̃∈S{2,3,4} (Q)

min
Q̃: Q̃∈S{1,3,4} (Q)

min
Q̃: Q̃∈S{3,4} (Q)

min
Q̃: Q̃∈S{3,4} (Q)

min
Q̃: Q̃∈S{3,4} (Q)

min
Q̃: Q̃∈S{3,4} (Q)

min
Q̃: Q̃∈S{2,4} (Q)

min
Q̃: Q̃∈S{2,4} (Q)

min
Q̃: Q̃∈S{2,4} (Q)

min
Q̃: Q̃∈S{2,4} (Q)

min
Q̃: Q̃∈S{1,4} (Q)

min
Q̃: Q̃∈S{1,4} (Q)

min
Q̃: Q̃∈S{1,4} (Q)

min
Q̃: Q̃∈S{1,4} (Q)

min
Q̃: Q̃∈S{4} (Q)

min
Q̃: Q̃∈S{4} (Q)

h
i
IQ̃ (Z1 ; Z24 , Y1 ) + E7 (Q̃Z14 Y1 , QZ14 Y1 ) ,

h
i
IQ̃ (Z2 ; Z1 , Z34 , Y1 ) + E7 (Q̃Z14 Y1 , QZ14 Y1 ) ,

(A.7)
(A.8)

E6 (Q̃Z14 Y , QZ14 Y1 ),

(A.9)

E5 (Q̃Z14 Y , QZ14 Y1 ),

(A.10)

h
i
IQ̃ (Z U (1) ; Z34 , Y1 |Z 12\U (1) ) + E5 (Q̃Z14 Y1 , QZ14 Y ) ,

h
i
IQ̃ (Z U (2) ; Z34 , Y1 |Z 12\U (2) ) + E6 (Q̃Z14 Y1 , QZ14 Y ) ,

h
i
IQ̃ (Z U (4) ; Z34 , Y1 |Z 12\U (4) ) + E7 (Q̃Z14 Y1 , QZ14 Y ) ,

(A.11)
(A.12)
(A.13)

E3 (Q̃Z14 Y , QZ14 Y1 ),

(A.14)

h
i
IQ̃ (Z U (1) ; Z2 , Z4 , Y1 |Z 13\U (1) ) + E4 (Q̃Z14 Y1 , QZ14 Y1 ) ,

(A.15)

h
i
IQ̃ (Z U (3) ; Z2 , Z4 , Y1 |Z 13\U (3) ) + E6 (Q̃Z14 Y1 , QZ14 Y1 ) ,

h
i
IQ̃ (Z U (5) ; Z2 , Z4 , Y1 |Z 13\U (5) ) + E7 (Q̃Z14 Y1 , QZ14 Y1 ) ,

(A.16)
(A.17)

E2 (Q̃Z14 Y1 , QZ14 Y1 ),

(A.18)

h
i
IQ̃ (Z U (2) ; Z1 , Z4 , Y1 |Z 23\U (2) ) + E4 (Q̃Z14 Y1 , QZ14 Y1 ) ,

(A.19)

h
i
IQ̃ (Z U (3) ; Z1 , Z4 , Y1 |Z 23\U (3) ) + E5 (Q̃Z14 Y1 , QZ14 Y1 ) ,

h
i
IQ̃ (Z U (6) ; Z1 , Z4 , Y1 |Z 23\U (6) ) + E7 (Q̃Z14 Y1 , QZ14 Y1 ) ,
E1 (Q̃Z14 Y1 , QZ14 Y1 ),

h
i
IQ̃ (Z U (u) ; Z4 , Y1 |Z 123\U (u) ) + Eu (Q̃Z14 Y1 , QZ14 Y1 ) , u ∈ {1, . . . , 7} ,

E0 (Q̃Z14 Y1 , QZ14 Y1 ),

h

i
(u)
Ê (u) (QZ14 Y1 , R22 ) − Ru , Ê8 (QZ14 Y1 , R22 ) , u ∈ {1, 2} ,
+


i
h
(3)
(3)
(3)
max Êu (QZ14 Y1 , R22 ) − Ru , Ê8 (QZ14 Y1 , R22 ) ,
EHK (QZ14 Y1 ) , max
+
u∈{1,2,4}


i
h
(4)
(4)
(4)
max Êu (QZ14 Y1 , R22 ) − Ru Ê8 (QZ14 Y1 , R22 ) ,
EHK (QZ14 Y1 ) , max
u∈{1,3,5}
,


i
h
(5)
(5)
max Êu(5) (QZ14 Y1 , R22 ) − Ru , Ê8 (QZ14 Y1 , R22 ) ,
EHK (QZ14 Y1 ) , max
+
u∈{2,3,6}


i
h
(6)
(6)
EHK (QZ14 Y1 ) , max max Êu(6) (QZ14 Y1 , R22 ) − Ru , Ê8 (QZ14 Y1 , R22 ) ,
u∈{1:7}
+


(u)
D(QY1 |Z14 ||WY1 |Z14 |PZ14 ) + min EHK (QZ14 Y1 ) .
ẼHK (R11 , R12 , R21 , R22 ) ,
min
(u)

EHK (QZ14 Y1 ) , max

QY

4:
1 |Z1

u∈{1:6}

(A.20)
(A.21)
(A.22)
(A.23)
(A.24)
(A.25)
(A.26)
(A.27)
(A.28)
(A.29)
(A.30)

QZi =PZi , 1≤i≤4

convex problem, and thus one should resort to global opti-

mization methods (e.g., a simple algorithm is an exhaustive

21

Pr

 ( (
N
[ [


i,j

K−1
\

V1 (i) ∈ Al,0 ,

l=1

(

(V1 (i), Vk+1 (j)) ∈ Al,k ,

k=1

"

(

≤ min 1, L1 E min 1, L2 Pr
N
[

K
\

Vk (j) ∈ Gl,k

k=2
N
[

(

l=1

(

V1 ∈ Al,0 ,

K−1
\

K
\

(V1 , Vk+1 ) ∈ Al,k ,

k=1

K−1
\

))



Vk ∈ Gl,k

k=2
K
\

)

)

V1

))#

,

))#)

(B.1)

Vk (j) ∈ Gl,k


j
l=1
k=1
k=2
  ( (

))
N
K−1
K
 [ [

\
\
≤ L1 E Pr
V1
V1 ∈ Al,0 ,
(V1 , Vk+1 (j)) ∈ Al,k ,
Vk (j) ∈ Gl,k
 


(B.2)

"

(

L2 E min 1, L1 Pr

Pr

 ( (
N
[ [


i,j

≤ L1 Pr

(

l=1

(

V1 ∈ Al,0 ,

(V1 , Vk+1 ) ∈ Al,k ,

V1 (i) ∈ Al,0 ,

l=1

K−1
\

K
\

(V1 (i), Vk+1 (j)) ∈ Al,k ,

k=1

 ( (
N
[ [

j

Vk (j) ∈ Gl,k

l=1

(V1 , Vk+1 (j)) ∈ Al,k ,

K
\

k=1

))



))


k=2

K−1
\

V1 ∈ Al,0 ,

Vk ∈ Gl,k

k=2

k=1

{Vk }K
k=2

k=2

 ( (
))
N
K−1
K

[ [
\
\
Vk (j) ∈ Gl,k
V1 (i) ∈ Al,0 ,
(V1 (i), Vk+1 (j)) ∈ Al,k ,
Pr


i,j
l=1
k=1
k=2
)#
"
(
(N (
))
K−1
K
[
\
\
≤ L1 E min 1, L2 Pr
V1
V1 ∈ Al,0 ,
(V1 , Vk+1 ) ∈ Al,k ,
Vk ∈ Gl,k
l=1

(

min 1, L2 Pr

(

(

N
[

l=1

(

(

+ I {F } min 1, L2 Pr
= I {F } min 1, L2 Pr

(

L1 E min 1, L2 Pr
≤ L1 L2 Pr

(N (
[
l=1

(V1 , Vk+1 ) ∈ Al,k ,

(

(

(

l=1

(V1 , Vk+1 ) ∈ Al,k ,

V1 ∈ Al,0 ,

(V1 , Vk+1 ) ∈ Al,k ,

search over a fine grid of probability simplex). Nonetheless,
in the following we somewhat simplify these optimizations.

Vk ∈ Gl,k

k=2

(V1 , Vk+1 ) ∈ Al,k ,

k=1

Vk ∈ Gl,k

K
\

K
\

k=2

Vk ∈ Gl,k

)

Vk ∈ Gl,k

k=2
K
\

k=2

k=1

K−1
\

V1

))

Vk ∈ Gl,k

(V1 , Vk+1 ) ∈ Al,k ,

k=1
K−1
\

K−1
\

K
\

)

k=2
K
\

k=1

(

V1 ∈ Al,0 ,

Vk ∈ Gl,k

(V1 , Vk+1 ) ∈ Al,k ,

V1 ∈ Al,0 ,

V1 ∈ Al,0 ,

N
[

K−1
\

k=1
K−1
\

l=1
( N (
[

K
\

k=2

V1 ∈ Al,0 ,

l=1
(N
[

l=1

≤ I {F }

"

N
[

(B.3)

k=2

k=1

(

(

K−1
\

V1 ∈ Al,0 ,

= I {F } min 1, L2 Pr
c

k=1

V1

)

)

))

V1

V1

))

))
(B.4)

)

V1

))#

))

We first see that (C.1) can be rewritten as
n
o
Ẽ1 (R1 , R2 ) , min Ẽ1′ (R1 , R2 ), Ẽ1′′ (R1 , R2 )

(B.5)

(C.9)

22

where
Ẽ1′ (R1 , R2 )

and

=
inf
Q: R1 <Ê1 (Q,R2 )−Ê2 (Q,R2 )
o
n
D(Q||W ) + Ê1 (Q, R2 ) − R1 ,

Ẽ1′′ (R1 , R2 ) =

inf
n
o
D(Q||W ) + Ê2 (Q, R2 ) .

(C.10)

Obviously, we should get that R < IW (X; Y ), namely,
the minimum in (D.4) should be equal to IW (X; Y ). To
see that this is indeed the case, note that since the above
optimization problem is convex, the linear constraint is met
with equality, and we note that f (W ) = −HW (Y |X),
f (Q) = −D(Q||W |PX ) − HQ (Y |X), and IQ (X; Y ) =
HW (Y ) − HQ (Y |X). Using the last facts, we get
R<

Q: R1 ≥Ê1 (Q,R2 )−Ê2 (Q,R2 )

(C.11)

=

Let us analyze Ẽ1′ (R1 , R2 ) as a function of R1 . For R1 = 0,
we have
n
o
(C.12)
Ẽ1′ (0, R2 ) = inf D(Q||W ) + Ê1 (Q, R2 ) .

min

Q:QY =WY ,QX =PX ,f (W )=f (Q)

min

Q:QY =WY ,QX =PX ,
HW (Y |X)=D(Q||W |PX )+HQ (Y |X)

= IW (X; Y )
+

R1 =0

ing the critical rate R1,crit = Ê1 ( Q∗Y1 |X1 X2

R1 =0

, R2 ), it is easily noticed that for R1 ≤
Ê2 ( Q∗Y1 |X1 X2
R1 =0
R1,crit , the exponent is an affine function
Ẽ1′ (R1 , R2 ) = Ẽ1′ (0, R2 ) − R1 .

D(Q||W |PX )

as required.
In our case, using the equivalent representation of our error
exponent in (C.5)-(C.7), we readily get that the error exponent
in Theorem 1 is positive if6 :
R1 <

(C.13)

R1 <

Furthermore, for R1 ≤ R1,crit , it is readily seen that
Ẽ1 (R1 , R2 ) = Ẽ1′ (R1 , R2 ).

min

= IW (X; Y ),

, and defin, R2 ) −

HW (Y ) − HQ (Y |X)

Q:QY =WY ,QX =PX ,
HW (Y |X)=D(Q||W |PX )+HQ (Y |X)

Q

Now, letting the minimizer be Q∗Y1 |X1 X2

IQ (X; Y )

(C.14)
R1 <

For R1 > R1,crit , however, since the optimization of Q is not
convex, the term cannot be simplified anymore.

˜ Q̃),
I(

min

(D.5)

Q̃∈S(W ),max[t0 (W ),f (W )]≤f (Q̃)

min

ˆ Q̂)≤R2
Q̃∈S(W ),Q̂∈Ŝ(Q̃),I(
ˆ Q̂)
max[t0 (W ),f (W )]≤f (Q̂)+R2 −I(

min
Q̃∈S(W ),Q̂∈Ŝ(Q̃)
max[t0 (W ),f (W )]≤f (Q̂)



˜ Q̃),
I(

(D.6)

i 
h
˜
ˆ
I(Q̃) + I(Q̂) − R2
+

(D.7)
A PPENDIX D
P ROOF OF (10)
First, note that the following region:
R1 < IW (X1 ; Y1 |X2 ),

(D.1)

R1 < IW (X1 ; Y1 ) + [IW (X2 ; Y1 |X1 ) − R2 ]+ ,

(D.2)

evaluated with PX1 X2 Y1 = PX1 × PX2 × WY1 |X1 X2 , is
equivalent to (10). Thus, to show that (10) is achievable, it
suffices to show that the above region is achievable. Now,
recall that the ordinary random coding exponent, in the singleuser setting, is given by
o
n
Er (R) = min D(QY |X ||W |PX ) + [IQ (X; Y ) − R]+ .
Q

From [25, Lemma 9] it can be shown that Er (R) can be
rewritten as
n
D(Q̃Y |X ||W |PX )
Er (R) =
min
(Q,Q̃)∈D:f (Q̃)≤f (Q)
o
+ [IQ (X; Y ) − R]+ , (D.3)

where f (Q) = EQ {log W (Y |X)}, and D is the set of (Q, Q̃)
distributions such that QY = Q̃Y , and QX = Q̃X = PX . The
last representation is very similar, in some sense, to the error
exponent formula in Theorem 1. It can be seen that Er (R) is
positive as long as
R<

min

Q:QY =WY ,QX =PX ,f (W )≤f (Q)

IQ (X; Y ).

(D.4)

˜ Q̃) ≡ I (X1 ; X2 , Y1 ) and I(
ˆ Q̂) ≡
where we recall that I(
Q̃
IQ̂ (X2 ; X1 , Y1 ). In the following, we show that (D.5) and
(D.7) correspond to (D.1) and (D.2), respectively. Finally, we
show that (D.5) is dominated by (D.5) and (D.7), and thus
superfluous. Indeed, for (D.5), we have
˜ Q̃)
I(

min
Q̃∈S(W ),max[t0 (W ),f (W )]≤f (Q̃)

=

min
Q̃Y |X2 =WY |X2 ,max[t0 (W ),f (W )]≤f (Q̃)

≥

min
Q̃Y |X2 =WY |X2 ,f (W )≤f (Q̃)

IQ̃ (X1 ; X2 , Y )

IQ̃ (X1 ; X2 , Y ).

(D.8)

Now, as before, we note that (using the fact that the minimization over Q̃ in (D.8) is such that Q̃Y |X2 = WY |X2 )
IQ̃ (X1 ; X2 , Y ) = IQ̃ (X1 ; X2 ) + IQ̃ (X1 ; Y |X2 )

(D.9)

= IQ̃ (X1 ; X2 ) + HW (Y |X2 )
− HQ̃ (Y |X1 , X2 ),

(D.10)

f (W ) = −HW (Y |X1 , X2 ),

(D.11)

f (Q̃) = −D(Q̃||W |PX ) − HQ̃ (Y |X1 , X2 ).

(D.12)

and

Thus, we have (D.13), shown at the top of the next page, where
6 To show that (10) is achievable, we consider a lower bound
on Ẽ(R
the contribution of Ê2 (Q, R2 ), namely,
 1 , R2 ), which ignores
h
i
minQ D(Q||W |PX ) + Ê1 (Q, R2 ) − R1
.
+

23

min
Q̃Y |X2 =WY |X2 ,f (W )≤f (Q̃)

=

IQ̃ (X1 ; X2 , Y )

min
Q̃Y |X2 =WY |X2 ,
D(Q̃||W |PX )+HQ̃ (Y |X1 ,X2 )≤HW (Y |X1 ,X2 )

≥ IW (X1 ; Y |X2 ) +

IQ̃ (X1 ; X2 ) + HW (Y |X2 ) − HQ̃ (Y |X1 , X2 )

min
Q̃Y |X2 =WY |X2 ,
D(Q̃||W |PX )+HQ̃ (Y |X1 ,X2 )≤HW (Y |X1 ,X2 )

IQ̃ (X1 ; X2 ) + D(Q̃||W |PX )

= IW (X1 ; Y |X2 )

the inequality follows from the fact that −HQ̃ (Y |X1 , X2 ) ≥
D(Q̃||W |PX ) − HW (Y |X1 , X2 ) induced by the optimization
constraint, and the last equality is achieved by taking Q̃ = W
and Q̃X1 ,X2 = PX1 PX2 . The constraint in (D.7) is handled
in a similar manner. Indeed, using the same manipulations,
we get (D.14), shown at the top of the next page, where
the inequality is due to the fact that −HQ̃ (Y |X1 , X2 ) ≥
D(Q̃||W |PX ) − HW (Y |X1 , X2 ), the second equality follows
by taking Q̂ = W , and the last equality follows by taking Q̃
such that X2 − Y − X1 is a Markov chain.
Finally, we show that the constraint in (D.6) is superfluous.
To this end, we will show that for R2 < IW (X2 ; Y |X1 ),
the r.h.s. of (D.6) reduces to R1 + R2 < I(X1 , X2 ; Y ),
which is dominated by (D.5) and (D.7) (or, equivalently, by
(D.13) and (D.14)), and for R2 ≥ IW (X2 ; Y |X1 ), (D.6)
reduces to R1 < IW (X1 ; Y ), already supported by (D.7)
(see (D.14)). Whence, (D.6) is redundant. Indeed, for R2 ≥
IW (X2 ; Y |X1 ), the r.h.s. of (D.6) can be lower bounded
as in (D.15), presented at the top of the next page, where
in (a) we use the definition of t0 (W ) in (8b), (b) follows
from the assumption that R2 ≥ IW (X2 ; Y |X1 ), (c) is due to
(D.11)-(D.12), (d) follows from the fact that −HQ̃ (Y |X1 ) ≥
D(Q̂||W |PX ) + IQ̂ (X1 ; X2 ) − HW (Y |X1 ) induced by the
optimization constraint, and (e) is achieved by taking Q̂ = W ,
Q̂X1 X2 = Q̂X1 Q̂X2 , and Q̃ such that X2 − Y − X1 is a
Markov chain. Thus, for R2 ≥ IW (X2 ; Y |X1 ), we obtained
that R1 < IW (X1 ; Y ), as required. On the other hand,
for R2 < IW (X2 ; Y |X1 ), the r.h.s. of (D.6) can be lower
bounded as shown in (D.16), given in the next page, where
(a) is due to (D.11)-(D.12), (b) is because Q̂ ∈ S(Q̃) and
thus HQ̃ (Y |X1 ) = HQ̂ (Y |X1 ), and (c) follows from the
fact that −HQ̂ (Y |X1 ) ≥ D(Q̂||W |PX ) + IQ̂ (X1 ; X2 ) −
HW (Y |X1 , X2 ) − R2 induced by the optimization constraint.
Whence, we obtained that R1 + R2 ≤ IW (X1 , X2 ; Y ), as
required.
ACKNOWLEDGMENT
The authors would like to thank the associate editor, Jun
Chen, and the anonymous referees for their suggestions and
comments which helped improving the content of this paper.
The authors are also grateful to Jonathan Scarlett for very
helpful comments on a previous version of this paper, and for
drawing our attention to [21] (and its extended version which

(D.13)

is not published yet), which was unknown to the authors at
the time of writing the original version of this paper.
R EFERENCES
[1] A. El Gamal and Y. H. Kim, Network Information Theory. Cambridge
University Press, 2011.
[2] E. C. Shannon, “Two-way communication channels,” in Proc. 4th
Berkeley Symp. on Mathematical Statistics and Probability, vol. 1.
Berkeley, CA: Univ. California Press, 1961, pp. 611–64.
[3] R. Ahlswede, “The capacity region of a channel with two senders and
two receivers,” Annals Probabil., vol. 2, no. 5, pp. 805–814, 1974.
[4] A. B. Carleial, “Interference channels,” IEEE Trans. on Inf. Theory, vol.
IT-24, pp. 60–70, Jan. 1978.
[5] H. Sato, “Two-user communication channels,” IEEE Trans. on Inf.
Theory, vol. IT-23, pp. 295–304, May. 1977.
[6] A. B. Carleial, “A case where intereference does not reduce capacity,”
IEEE Trans. on Inf. Theory, vol. IT-21, pp. 569–570, Sep. 1975.
[7] R. Benzel, “The capacity region of a class of discrete additive degraded
interference channels,” IEEE Trans. on Inf. Theory, vol. IT-25, pp. 228–
231, Mar. 1979.
[8] T. S. Han and K. Kobayashi, “A new achievable rate region for the
interference channel,” IEEE Trans. on Inf. Theory, vol. IT, no. 27, pp.
49–60, Jan. 1981.
[9] R. Etkin, N. Merhav, and E. Ordentlich, “Error exponents of optimum
decoding for the interference channel,” IEEE Trans. on Inf. Theory,
vol. 56, no. 1, pp. 40–56, Jan. 2010.
[10] C. Chang, R. Etkin, and E. Ordentlich, “Interference
channel capacity region for randomized fixed-composition
codes,” HP Labs Technical Report, 2009. [Online]. Available:
http://www.hpl.hp.com/techreports/2008/HPL-2008-194R1.html
[11] J. Scarlett, A. Martinez, and A. G. i Fábregas, “Multiuser coding
techniques for mismatched decoding,” submitted to IEEE Trans. on Inf.
Theory, Nov. 2013. [Online]. Available: arxiv.org/pdf/1311.6635
[12] R. G. Gallager, Information Theory and Reliable Communication. New
York: Wiley, 1968.
[13] I. Csiszár and J. Korner, Information Theory: Coding Theorems for
Discrete Memoryless Systems. Academic Press, 2011.
[14] N. Merhav, “Relations between random coding exponents and the
statistical physics of random codes,” IEEE Trans. on Inf. Theory, vol. 55,
no. 1, pp. 83–92, Jan. 2009.
[15] ——, “Exact random coding exponents of optimal bin index decoding,”
IEEE Trans. on Inf. Theory, vol. 60, no. 10, pp. 6024–6031, Oct. 2014.
[16] ——, “List decoding-random coding exponents and expurgated exponents,” IEEE Trans. on Inf. Theory, vol. 60, no. 11, pp. 6749–6759,
Nov. 2014.
[17] ——, “Exact correct-decoding exponent for the wiretap channel decoder,” IEEE Trans. on Inf. Theory, vol. 60, no. 12, pp. 7606–7615,
Dec. 2014.
[18] W. Huleihel, N. Weinberger, and N. Merhav, “Erasure/list random
coding error exponents are not universally achievable,” submitted
to IEEE Trans. on Inf. Theory, Dec. 2015. [Online]. Available:
http://arxiv.org/abs/1410.7005
[19] N. Merhav, “The generalized random energy model and its application to
the statistical physics of ensembles of hierarchical codes,” IEEE Trans.
on Inf. Theory, vol. 55, no. 3, pp. 1250–1268, May 2009.
[20] N. Shulman, “Communication over an unknown channel via common broadcasting,” Ph.D. dissertation, Tel-Aviv University, 2003,
http://citeseerx.ist.psu.edu/viewdoc.

24

min
Q̃Y |X2 =WY |X2 ,Q̂Y |X1 =Q̃Y |X1
D(Q̂||W |PX )+HQ̂ (Y |X1 ,X2 )≤HW (Y |X1 ,X2 )

≥


i 
h
˜ Q̃) + I (X1 ; X2 ) + H (Y |X1 ) − H (Y |X1 , X2 ) − R2
I(
Q̃
Q̂
Q̂

min
Q̃Y |X2 =WY |X2 ,Q̂Y |X1 =Q̃Y |X1
D(Q̂||W |PX )+HQ̂ (Y |X1 ,X2 )≤HW (Y |X1 ,X2 )

+

n
h
˜ Q̃) + I (X1 ; X2 ) + D(Q̂||W |PX ) + H (Y |X1 )
I(
Q̃
Q̂
− HW (Y |X1 , X2 ) − R2

=



min
Q̃Y |X2 =WY |X2 ,Q̃Y |X1 =WY |X1

=

n

min
Q̃Y |X2 =WY |X2 ,Q̃Y |X1 =WY |X1

i 
+

i 
h
IQ̃ (X1 ; Y ) + IQ̃ (X1 ; X2 |Y ) + HQ̃ (Y |X1 ) − HW (Y |X1 , X2 ) − R2
+

IW (X1 ; Y ) + IQ̃ (X1 ; X2 |Y ) + [HW (Y |X1 ) − HW (Y |X1 , X2 ) − R2 ]+

= IW (X1 ; Y ) + [IW (X2 ; Y |X2 ) − R2 ]+ ,

min

ˆ Q̂)≤R2
Q̃∈S(W ),Q̂∈Ŝ(Q̃),I(
ˆ Q̂)
max[t0 (W ),f (W )]≤f (Q̂)+R2 −I(
(a)

=

˜ Q̃) ≥
I(

min

ˆ Q̂)≤R2
Q̃∈S(W ),Q̂∈Ŝ(Q̃),I(
ˆ Q̂)
t0 (W )≤f (Q̂)+R2 −I(

min

ˆ Q̂)≤R2
Q̃∈S(W ),Q̂∈Ŝ(Q̃),I(
maxQ̂: Q̂∈S(W ),Î(Q̂)≤R [f (Q̂)−IQ̂ (X2 ;X1 ,Y )]≤f (Q̂)−IQ̂ (X2 ;X1 ,Y )

o

(D.14)

˜ Q̃)
I(

IQ̃ (X1 ; X2 , Y )

2

(b)

≥

min

ˆ Q̂)≤R2
Q̃∈S(W ),Q̂∈Ŝ(Q̃),I(
f (W )−IW (X2 ;X1 ,Y )≤f (Q̂)−IQ̂ (X2 ;X1 ,Y )

(c)

=

IQ̃ (X1 ; X2 , Y )

min

ˆ Q̂)≤R2
Q̃∈S(W ),Q̂∈Ŝ(Q̃),I(
−HW (Y |X1 )≤−D(Q̂||W |PX )−IQ̂ (X1 ;X2 )−HQ̃ (Y |X1 )

(d)

≥ IW (X1 ; Y ) +

HW (Y ) − HQ̃ (Y |X1 ) + IQ̃ (X1 ; X2 |Y )

min

ˆ Q̂)≤R2
Q̃∈S(W ),Q̂∈Ŝ(Q̃),I(
−HW (Y |X1 )≤−D(Q̂||W |PX )−IQ̂ (X1 ;X2 )−HQ̃ (Y |X1 )

D(Q̂||W |PX ) + IQ̂ (X1 ; X2 ) + IQ̃ (X1 ; X2 |Y )

(e)

= IW (X1 ; Y )

(D.15)

min

ˆ Q̂)≤R2
Q̃∈S(W ),Q̂∈Ŝ(Q̃),I(
ˆ Q̂)
max[t0 (W ),f (W )]≤f (Q̂)+R2 −I(
(a)

=

min

ˆ Q̂)≤R2
Q̃∈S(W ),Q̂∈Ŝ(Q̃),I(
ˆ Q̂)
f (W )≤f (Q̂)+R2 −I(

˜ Q̃)
I(

min

HW (Y ) − HQ̃ (Y |X1 ) + IQ̃ (X1 ; X2 |Y )

min

HW (Y ) − HQ̂ (Y |X1 ) + IQ̃ (X1 ; X2 |Y )

ˆ Q̂)≤R2
Q̃∈S(W ),Q̂∈Ŝ(Q̃),I(
−HW (Y |X1 ,X2 )≤−D(Q̂||W |PX )−HQ̂ (Y |X1 )−IQ̂ (X1 ;X2 )+R2

(b)

=

˜ Q̃) ≥
I(

ˆ Q̂)≤R2
Q̃∈S(W ),Q̂∈Ŝ(Q̃),I(
−HW (Y |X1 ,X2 )≤−D(Q̂||W |PX )−HQ̂ (Y |X1 )−IQ̂ (X1 ;X2 )+R2

(c)

≥ IW (X1 , X2 ; Y ) − R2
+

min

ˆ Q̂)≤R2
Q̃∈S(W ),Q̂∈Ŝ(Q̃),I(
−HW (Y |X1 ,X2 )≤−D(Q̂||W |PX )−HQ̂ (Y |X1 )−IQ̂ (X1 ;X2 )+R2

≥ IW (X1 , X2 ; Y ) − R2

D(Q̂||W |PX ) + IQ̂ (X1 ; X2 ) + IQ̃ (X1 ; X2 |Y )
(D.16)

25

[21] J. Scarlett, A. Martinez, and A. G. i Fábregas, “Mismatched multi-letter
successive decoding for the multiple-access channel,” in Proc. ISIT 2014,
Jul. 2014, pp. 2539–2543.
[22] J.
Scarlett,
“Reliable
Communication
Under
Mismatched
Decoding,” Ph.D. dissertation, University of Cambridge, 2014,
http://itc.upf.edu/biblio/1061.
[23] B. Bandemer, A. El Gamal, and Y. K. Kim, “Optimal achievable rates for
interference networks with random codes,” IEEE Trans. on Inf. Theory,
vol. 61, no. 12, pp. 6536–6549, Dec. 2015.
[24] L. Weng, S. S. Pradhan, and A. Anastasopoulos, “Error exponent regions
for Gaussian broadcast and multiple-access channels,” IEEE Trans. on
Inf. Theory, vol. 54, no. 7, pp. 2919–2942, July 2008.
[25] R.
Gallager,
“Fixed
composition
arguments
and
lower
bounds to error probability,” July 1994. [Online]. Available:
www.rle.mit.edu/rgallager/documents/notes5.pdf

