1

Exact Error and Erasure Exponents for the
Asymmetric Broadcast Channel
Daming Cao

Vincent Y. F. Tan

arXiv:1801.05112v2 [] 17 Jan 2018

Abstract
We derive exact (ensemble-tight) error and erasure exponents for the asymmetric broadcast channel given a random superposition codebook. We consider Forney’s optimal decoder for both messages and the message pair for the receiver that decodes both
messages. We prove that the optimal decoder designed to decode the pair of messages achieves the optimal trade-off between the
total and undetected exponents associated with the optimal decoder for the private message. We propose convex optimization-based
procedures to evaluate the exponents efficiently. Numerical examples are presented to illustrate the results.
Index Terms
Broadcast channels, Degraded Message Sets, Erasure decoding, Undetected Error, Error exponents, Superposition coding.

I. I NTRODUCTION
A. Background and Related Works
The broadcast channel [1] has been extensively studied in multi-user information theory. Although the capacity region is
still unknown, some special cases have been solved. One example is the broadcast channel with degraded message sets, also
known as the asymmetric broadcast channel (ABC). For this channel, one receiver desires to decode both the private message
m1 and the common message m2 while the other receiver desires to decode only m2 .
The capacity region for the ABC was derived by Körner and Marton and is well known [2]. The earliest work on error
exponents is that by Körner and Sgarro [3]. Later, Kaspi and Merhav [4] improved this work by deriving a tighter lower
bound for the error exponent. Most recently, Averbuch et al. derived the exact random coding error exponents and expurgated
exponents for the ensemble of fixed composition codes in [5] and [6], respectively.
In this paper, we are interested decoders with an erasure option. In this setting, the decoders may, instead of declaring
that a particular message or set of messages is sent, output an erasure symbol. For the discrete memoryless channel (DMC),
Forney [7] found the optimal decoder and derived a lower bound the total and undetected error exponents using Gallager-style
bounding techniques. Csiszár and Körner [8, Thm. 10.11] derived universally attainable erasure and error exponents using a
generalization of the maximum mutual information (MMI) decoder. Telatar [9] also analyzed an erasure decoding rule with
a general decoding metric. Moulin [10] generalized this family of decoders and proposed a new decoder parameterized by a
weighting function. Recently, Merhav [11] derived lower bounds to these exponents by using a novel type-class enumerator
method. In a breakthrough, Somekh-Baruch and Merhav [12] derived the exact random coding exponents for erasure decoding.
Recently, Huleihel et al. [13] showed that the random coding exponent for erasure decoding is not universally achievable
and established a simple relation between the total and undetected error exponents. Weinberger and Merhav [14] analyzed a
simplified decoder for erasure decoding. Hayashi and Tan [15] derived ensemble-tight moderate deviations and second-order
results for erasure decoding over additive DMCs. For the ABC, Tan [16] derived lower bounds on the total and undetected error
exponents of an extended version of the universal decoder in Csiszár and Körner [8, Thm. 10.11]. Moreover, Merhav in [17]
analyzed a random coding scheme with a binning (superposition coding) structure and showed that a potentially suboptimal
bin index decoder achieves the random coding error exponent for decoding only the bin index.
B. Main Contributions
In this paper, we generalize Merhav’s result in [17] by considering erasure decoding for the ABC with a superposition
codebook structure. In this problem, for the decoder that aims to decode both messages, there are six exponents of interest: the
total and undetected exponents corresponding to the individual messages m1 , m2 and the pair of messages (m1 , m2 ). We show
that the optimal decoder for the pair of messages (m1 , m2 ) achieves the optimal trade-off between the total and undetected
exponents pertaining to the private message m1 . Our main technical contribution is to handle statistical dependencies between
codewords that share the same cloud center. Lemma 5 provides a technical lemma that is then used to establish the equality
between the total random coding error exponents pertaining to the first message (i.e., the private message m1 ) and the message
pair, which partially ameliorates this problem.
Finally, we show that the minimizations required to evaluate these error exponents can be cast as convex optimization
problems, and thus, can be solved efficiently. We also present numerical examples to illustrate these exponents and the tradeoffs
involved in the erasure decoding problem for the ABC.
D. Cao is with the Southeast University of China (e-mail: dmcao@seu.edu.cn).
V. Y. F. Tan is with the National University of Singapore (e-mail: vtan@nus.edu.sg).

2

II. P ROBLEM F ORMULATION
A. Notation
Throughout this paper, random variables (RVs) will be denoted by upper case letters, their specific values will be denoted by
the respective lower case letters, and their alphabets will be denoted by calligraphic letters. A similar convention will apply to
random vectors of dimension n ∈ N and their realizations. For example, the random vector X n = (X1 , . . . , Xn ) may take on
a certain realization xn = (x1 , . . . , xn ) in X n , the n-th order Cartesian power of X , which is the alphabet of each component
of this vector.
The distributions associated with random variables will be denoted by the letters P or Q, with subscripts being the names
of the random variables, e.g., QUXY stands for a joint distribution of a triple of random variables (U, X, Y ) on U × X × Y,
the Cartesian product alphabets of U, X and Y. In accordance with these notations, the joint distribution induced by QY and
QX|Y will be denoted by QXY , QX QX|Y . Information measures induced by the joint distribution QXY (or Q for short)
will be subscripted by Q. For example, IQ (X; Y ) denotes the mutual information of the random variables X and Y with joint
distribution Q = QXY .
For a sequence xn , let P̂xn denote its empirical distribution or type. The type class TPX of PX is the set of all xn whose
empirical distribution is PX . For given conditional distribution QX|U and sequence un , TPX|U (un ) denotes the conditional
type class of xn (PX|U -shell) given un , namely, the set of sequences xn whose joint empirical distribution with un is given
by PX|U P̂un .
The probability of an event E will be denoted by Pr{E}, and the expectation operator with respect to a joint distribution
.
Q, will be denoted by EQ {·}. For two positive sequences {an } and {bn }, the notation an = bn means that {an } and {bn }
·

are of the same exponential order, i.e., limn→∞ n1 ln abnn = 0. Similarly, an ≤ bn means that lim supn→∞ n1 ln abnn ≤ 0. The
indicator function of an event E will be denoted by 1{E}. The notation |x|+ will stand for max{x, 0} and notation [M ] stands
for {1, . . . , M }. Finally, logarithms and exponents will be understood to be taken to the natural base.
B. System Model
We consider a discrete memoryless ABC W : X → Y × Z with a finite input alphabet X , finite output alphabets Y and Z
and a transition probability matrix {W (y, z|x) : x ∈ X , y ∈ Y, z ∈ Z}. Let WY : X → Y and WZ : X → Z be respectively
the Y- and Z-marginals of W .
Assume there is a random codebook C with superposition structure for this ABC, where the message pair (m1 , m2 ) is
destined for user Y and the common message m2 is destined for user Z. Specifically, fix a distribution PUX (u, x) and
randomly generate M2 = enR2 “cloud centers” {U n (m2 ) : m2 ∈ M2 = [M2 ]} according to the distribution
P (un ) ,

n
Y

PU (ui ).

(1)

i=1

For each cloud center U n (m2 ), randomly generate M1 = enR1 “satellite” codewords {X n (m1 , m2 ) : m1 ∈ M1 = [M1 ]}
according to the conditional distribution
n
Y
PX|U (xi |ui ).
(2)
P (xn |un ) :=
i=1

n

The two decoders with erasure options are given by g1 : Y → (M1 ∪ {e1 }) × (M2 ∪ {e2 }) and g2 : Z n → (M2 ∪ {e2 })
where ej is the erasure symbol for message mj , j = 1, 2.

C. Definitions of Error Probabilities and Error Exponents
In this paper, we focus on six different error probabilities associated to terminal Y. We do not consider the total and
undetected error probabilities at terminal Z as they follow from the DMC setting that Somekh-Baruch and Merhav [12]
considered. Define the disjoint decoding regions according to the decoder g1 as Dm1 m2 = {y n : g1 (y n ) = (m1 , m2 )}.
Moreover, let {Dm1 : m1 ∈ M
S1 } and {Dm2 : m2 ∈ M2 } be the disjoint decoding regions associated to messages m1 and
m2 respectively, i.e., Dm1 = m2 ∈M2 Dm1 m2 and similarly for Dm2 . For terminal Y, define for message mj , j = 1, 2 and
the message pair (m1 , m2 ), the conditional total error and undetected error probabilities as

c
xn (m1 , m2 )
(3)
etj (m1 , m2 ) , WYn Dm
j


[
Dm̂j xn (m1 , m2 )
(4)
euj (m1 , m2 ) , WYn
m̂j ∈Mj \{mj }

etY

euY

(m1 , m2 ) ,

(m1 , m2 ) ,

WYn

WYn




c
xn (m1 , m2 )
Dm
1 ,m2

[
Dm̂1 m̂2 xn (m1 , m2 ) .
(m̂1 ,m̂2 )6=(m1 ,m2 )

(5)
(6)

3

Then we may define the average total and undetected error probabilities at terminal Y as follows:
X
1
etj ,
etj (m1 , m2 )
M1 M2

(7)

(m1 ,m2 )∈M1 ×M2

euj ,
etY ,
euY ,

1
M1 M2

1
M1 M2
1
M1 M2

X

euj (m1 , m2 )

(8)

X

etY (m1 , m2 )

(9)

X

euY (m1 , m2 ).

(10)

(m1 ,m2 )∈M1 ×M2

(m1 ,m2 )∈M1 ×M2

(m1 ,m2 )∈M1 ×M2

Using the Neyman-Pearson theorem, Forney [7] showed that the best/optimal trade-off between the average total and undetected
error probabilities is attained by the decoding regions


n
n P Pr(y |Cj (mj ))
∗
nT
,
y
:
Dm
,
(11)
≥
e
j
′
n
m′j 6=mj Pr(y |Cj (mj ))


WYn (y n |xn (m1 , m2 ))
nT
n P
∗
,
(12)
≥
e
,
y
:
Dm
n n n
′
′
1 m2
(m′ ,m′ )6=(m1 ,m2 ) WY (y |x (m1 , m2 ))
1

2

n

where the distribution of the output y conditioned on the subcodebook C1 (m1 ) = {xn (m1 , m2 ) : m2 ∈ M2 } is
X
1
Pr(y n |C1 (m1 )) ,
WYn (y n |xn (m1 , m2 ))
M2

(13)

m2 ∈M2

and similarly for Pr(y n |C2 (m2 )).
We would like to find the exact error exponents Ejt , Eju , EYt and EYu , j = 1, 2. These are the exponents associated to the
expectation of the error probabilities, where the expectation is taken with respect to the randomness of the codebook C which
possess the superposition structure as described in Section II-B. In other words,


1
t
t
(14)
E1 (R1 , R2 , T ) , lim sup − ln EC [e1 ] ,
n
n→∞

and similarly for the other exponents E1u , EYt , EYt , E2t , and E2u . We show, in fact, that the lim sup in (14) is a limit. These
exponents are also called random coding error exponents. If these exponents are known exactly, we say that ensemble-tight
results are established.
III. M AIN R ESULTS

AND

D ISCUSSIONS

The main result in this paper are stated below in Theorems 1 and 2, establishing exact random coding error exponents
for the messages mj , j = 1, 2, and the message pair at terminal Y, i.e., the random coding exponents corresponding to the
probabilities in (7)–(10).
Before stating our results, we state a few additional definitions. For a given probability distribution Q = QUXY on U ×X ×Y,
rates R1 and R2 , and the fixed random coding distribution P = PUX , define
β(Q, R1 ) , D(QX|U kPX|U |QU ) + IQ (X; Y |U ) − R1

(15)

γ(Q, R2 ) , D(QU kPU ) + IQ (U ; Y ) − R2

(16)

Φ(Q, R1 , R2 ) , γ(Q, R2 ) + |β(Q, R1 )|+

(17)

+

∆(Q, R1 , R2 ) , | − γ(Q, R2 )|+ − β(Q, R1 ) + .

(18)

A. Main Results
Theorem 1: The error exponents E1t , E1u , EYt and EYu are given by
E1t = EYt = min{Ψa , Ψb },

and E1u = EYu = E1t + T

(19)

where
h
Ψa , min D(Q̂UXY kPUXY ) +
Q̂U XY

h
Ψb , min D(Q̂UXY kPUXY ) +
Q̂U XY

min
QU X|Y ∈L1 (Q̂U XY ,R1 ,R2 ,T )

min
QX|U Y ∈L2 (Q̂U XY ,R1 ,T )

i
Φ(QUX|Y Q̂Y , R1 , R2 )

|β(QX|UY Q̂UY , R1 )|+

i

(20)
(21)

4

with PUXY (u, x, y) , PUX (u, x)WY (y|x) and the sets L1 and L2 are defined as
o
n
1
+ EQ̂ ln WY − T ≤ ∆(Q, R1 , R2 )
L1 (Q̂UXY , R1 , R2 , T ) , QUX|Y : EQ ln
WY
n
o
1
L2 (Q̂UXY , R1 , T ) , QX|UY : EQ ln
+ EQ̂ ln WY − T ≤ | − β(Q, R1 ) + ,
WY

(22)
(23)

where Q in (22) is equal to Q = QUX|Y Q̂Y , Q in (23) is equal to Q = QX|UY Q̂UY , and the expectation EQ̂ ln WY can be
P
explicitly written as EQ̂ ln WY = u,x,y Q̂UXY (u, x, y)WY (y|x).
The proof of Theorem 1 is provided in Section VI.
Theorem 2: The error exponents E2t and E2u are given by
E2t = max{Ψa , Ψc },

and E2u = E2t + T,

(24)

where
h
Ψc , min D(Q̂UXY kPUXY ) +
Q̂U XY

min
QU X|Y ∈L3 (Q̂U XY ,R1 ,R2 ,T )

i
Φ(QUX|Y Q̂Y , R1 , R2 )

(25)

with
o
n
1
+ s0 (Q̂UXY , R1 ) − T ≤ ∆(Q, R1 , R2 )
L3 (Q̂UXY , R1 , R2 , T ) , QUX|Y : EQ ln
WY

(26)

where Q in (26) is equal to Q = QUX|Y Q̂Y , and
s0 (Q̂UXY , R1 ) , −

min



β(Q̃, R1 ) − EQ̃ ln WY

(27)

Q̃X|U Y :β(Q̃,R1 )≤0

and where Q̃ in (27) is equal to Q̃ = Q̃X|UY Q̂UY .
The proof of Theorem 2 is provided in Section VII.

B. Remarks and Discussion of Results
•

•

•

Eqn. (19) in Theorem 1 implies that the optimal decoder for the pair of messages (m1 , m2 ) (i.e., that given by the region
in (12)) achieves the optimal trade-off between the total and undetected error exponents pertaining to the private message
m1 . This observation is non-trivial. For the case that the user Y wishes to decode only the private message m1 , the
optimal decoder for the pair of messages (m1 , m2 ), called the joint decoder, declares the message m̂1 of the decoded
message pair (m̂1 , m̂2 ) is the final output. It is not clear that this decoding strategy is optimal exponent-wise. The main
difference between the error events for these two decoders is that the user Y can decode the correct private message m1
but the wrong common message m2 . This is an error event for the joint decoder (but not for the one that focuses only
on m1 ). However, Lemma 5 implies that on the exponential scale, the exponents of the two decoders are the same, i.e.,
is no loss in optimality of using the joint decoder for decoding only message m1 . Moreover, this lemma also simplifies
the calculation of the exponents by handling statistical dependencies between codewords that share the same cloud center
(see (50 to follow)).
In Theorem 1, the total error exponent for the private message m1 is the minimum of two exponents Ψa and Ψb . The
first exponent Ψa means that the user Y is in a regime where it decodes the pair of messages (m̂1 , m̂2 ). Intuitively
speaking, this exponent Ψa achieves the minimum in (19) when R2 > I(U ; Y ) in which the performance of two-step
decoding is sub-optimal. Loosely speaking, the second exponent Ψb means that user Y knows the true common message
m̃1 (given by a genie), then decodes the “satellite” codeword X n (m̃1 , m2 ). In contrast to the single-user DMC case,
now every codeword is generated according to a conditional distribution PX|U . Thus all codewords are conditioned on
a particular un (m2 ) sequence rather than being generated according to a marginal distribution PX . This is also reflected
in the expression of the inner optimization in (21) which is averaged over the random variable U (see definition of β
in (15)).
For the case that user Y wishes to decode the common message m2 , it can either decode the true transmitted codeword
X n (m1 , m2 ) or just decode the entire sub-codebook for the common message m2 , i.e., C2 (m2 ) = {X n (m1 , m2 ) :
m1 ∈ [M1 ]}. This explains the maximization in (24). When R1 is large, the term Ψc in (25) of Theorem 2 implies
n
that
P user Y is more likely than not to decode the “cloud center” U (m2 ) according to the “test channel” WY |U (y|u) ,
x WY (y|x)PX|U (x|u). This corresponds to the second decoding strategy, i.e. decoding the entire sub-codebook C2 (m2 )
indexed by the common message m2 .

5

IV. C ONVEX O PTIMIZATION I SSUES
To evaluate E1t in Theorem 1, we need to numerically solve the minimization problems Ψa and Ψb . As will be shown
below, these problems can be solved efficiently even though they are not convex.
For the second term Ψb in (21), we can split the feasible region of the inner minimization, i.e., L2 (Q̂UXY , R1 , T ) (see (23)),
into two closed sets, namely L21 (Q̂UXY ) , L2 (Q̂UXY , R1 , T ) ∩ B1 (Q̂UY , R1 ) and L22 (Q̂UXY ) , L2 (Q̂UXY , R1 , T ) ∩
B2 (Q̂UY , R1 ), where
B1 (Q̂UY , R1 ) , {QX|UY : β(QX|UY Q̂UY , R1 ) ≥ 0}

(28)

B2 (Q̂UY , R1 ) , {QX|UY : β(QX|UY Q̂UY , R1 ) ≤ 0}.

(29)

We denote the corresponding minimization problems pertaining to Ψb in (21) (and (23)) in which the function | · |+ is inactive
or active as Ψb1 and Ψb2 , respectively, i.e.,
h
i
min
β(QX|UY Q̂UY , R1 )
(30)
Ψb1 , min D(Q̂UXY kPUXY ) +
QX|U Y ∈L21 (Q̂U XY )

Q̂U XY

Ψb2 ,

min

Q̂U XY :L22 (Q̂U XY )6=∅

D(Q̂UXY kPUXY ),

where the sets L21 and L22 are defined as
n
o
1
L21 (Q̂UXY ) , QX|UY : EQ ln
+ EQ̂ ln WY − T ≤ 0, β(Q, R1 ) ≥ 0
WY
n
o
1
L22 (Q̂UXY ) , QX|UY : EQ ln
+ EQ̂ ln WY − T + β(Q, R1 ) ≤ 0, β(Q, R1 ) ≤ 0 ,
WY

(31)

(32)
(33)

and where Q in (32) and (33) is equal to Q = QX|UY Q̂UY . We thus have Ψb = min{Ψb1 , Ψb2 }.
As the minimization problem Ψb2 is convex, it can be solved efficiently. However Ψb1 is non-convex due to the non-convex
constraint β(QX|UY Q̂UY ) ≥ 0 in the inner optimization.1 For the inner optimization, if we remove this constraint in L21 , the
modified problem, denoted as Ψ′b1 and as follows
h
i
min
β(QX|UY Q̂UY , R1 ) ,
(34)
Ψ′b1 , min D(Q̂UXY kPUXY ) +
Q̂U XY

QX|U Y ∈L′21 (Q̂U XY )

where
o
n
1
+ EQ̂ ln WY − T ≤ 0 ,
L′21 (Q̂UXY ) , QX|UY : EQ ln
WY

(35)

Ψb = min{Ψ′+
b1 , Ψb2 },

(36)

is convex and can be solved efficiently. Furthermore, we have the following proposition.
Proposition 3: For the optimization problem Ψb1 , if the optimal solution to the inner optimization of the modified problem
Ψ′b1 is not feasible for the original problem Ψb1 , i.e., β(QX|UY Q̂UY ) < 0, then there exists an optimal solution to the original
inner optimization problem that satisfies β(QX|UY Q̂UY ) = 0. Moreover, in this case, the optimal value of Ψb is equal that
for Ψb2 (i.e., Ψb2 is active in the minimum that defines Ψb ).
Proof: Let Q∗1 and Q∗2 (two distributions of the form Q = QX|UY Q̂UY ) be optimal solutions to the modified and original
inner optimizations of Ψ′b1 and Ψb1 , respectively. Assume, to the contrary, that β(Q∗2 ) > 0. Due to the continuity of β(Q)
in Q, there exists a conditional probability distribution Q̄ = αQ∗1 + (1 − α)Q∗2 for some α ∈ (0, 1) that satisfies β(Q̄) = 0.
As the first constraint in L21 is convex in Q, the solution Q̄ is feasible (for Ψb1 ). Note that the optimal value of objective
function (in Ψb1 ) is β(Q∗2 ) > 0 while β(Q̄) = 0. This is a contradiction. Hence, there exists an optimal solution to the original
inner optimization problem Ψb1 satisfying β(QX|UY Q̂UY ) = 0. Moreover, this optimal solution of Ψb1 (i.e., (Q̂∗ , Q∗ ) with
β(Q∗X|UY Q̂∗UY ) = 0) is also feasible for Ψb2 . As a result, in this case, the optimal value of Ψb is equal to that for Ψb2
because Ψb = min{Ψb1 , Ψb2 }.
In summary, we can solve the non-convex optimization problem Ψb by solving two convex problems Ψb2 and Ψ′b1 , i.e.,
′+
∗
∗
where the superscript “+” of Ψ′+
b1 means the value of Ψb1 is active in the minimization if the optimal solution (Q̂ , Q ), is
∗
∗
also feasible for the original optimization Ψb1 , i.e., β(QX|UY Q̂UY ) ≥ 0. In other words,
(
min{Ψ′b1 , Ψb2 }
β(Q∗X|UY Q̂∗UY ) ≥ 0
.
(37)
Ψb =
Ψb2
else

Consequently, Ψb can be solved efficiently.
1 In

this section, we drop the dependences of β(·) and γ(·) on the rates R1 and R2

6

For Ψa in (20), let
Ω(QUX|Y Q̂Y ) , EQU X|Y Q̂Y ln

1
+ EQ̂ ln WY − T,
WY

(38)

then similarly, we can partition the feasible region of the inner minimization into four parts and denote the corresponding inner
optimization problems as follows:
1) If γ(Q) ≥ 0 and β(Q) ≥ 0, then
Φ∗a1 , min γ(Q) + β(Q),

such that Ω(Q) ≤ 0.

(39)

Φ∗a2 , min γ(Q) such that Ω(Q) + β(Q) ≤ 0.

(40)

Q

2) If γ(Q) ≥ 0 and β(Q) ≤ 0, then
Q

3) If γ(Q) ≤ 0 and γ(Q) + β(Q) ≥ 0, then
Φ∗a3 , min γ(Q) + β(Q),

such that Ω(Q) ≤ 0.

(41)

such that Ω(Q) + γ(Q) + β(Q) ≤ 0.

(42)

Q

4) If γ(Q) ≤ 0 and γ(Q) + β(Q) ≤ 0, then
Φ∗a4 , 0

where Q in the above definitions is equal to Q = QUX|Y Q̂Y (compare the above to the definition of the optimization problem
Ψa in (20)). Thus we have,


(43)
Ψa = min D(Q̂UXY kPUXY ) + min{Φ∗ai (Q̂UXY )} .
i∈[4]

Q̂U XY

We can rewrite the objective functions of Φ∗a1 and Φ∗a3 as follows

min γ(QUX|Y Q̂Y ) + β(QUX|Y Q̂Y )

QU X|Y

= min [γ(QU|Y Q̂Y ) + min β(QX|UY QU|Y Q̂Y )]
QU |Y

QX|U Y

(44)

where the notation γ(QU|Y Q̂Y ) is consistent due to the fact that the function γ(Q, R2 ) (see (16)) only depends on the marginal
distribution QUY . Therefore, by using a similar argument as that for Ψb1 above, we can remove the non-convex constraint
β(Q) ≥ 0 in Φ∗a1 due to Φ∗a2 . We can also remove the non-convex constraint γ(Q) + β(Q) ≥ 0 in Φ∗a3 due to Φ∗a4 . Denote
these two modified optimizations as Φ′a1 and Φ′a3 , respectively. We can merge these two modified optimizations Φ′a1 and Φ′a3
into a new convex optimization problem Φ∗a5 i.e.,
Φ∗a5 , min γ(Q) + β(Q) such that Ω(Q) ≤ 0.

(45)

We now state and prove a proposition that simplifies the calculation of (43).
Proposition 4: For the inner minimization problem in (43), i.e., mini∈[4] {Φ∗ai (Q̂UXY )}, without loss of optimality, we can
replace Φ∗a1 and Φ∗a3 with the new convex optimization problem Φ∗a5 .
Proof: Let Q∗1 , Q∗3 and Q∗5 (three distributions of the form Q∗ = Q∗XU|Y Q̂Y ) be optimal solutions to the modified and
new optimizations Φ′a1 , Φ′a3 and Φ∗a5 , respectively. There are two cases for the solution Q∗5 , namely case (i) γ(Q∗5 ) ≥ 0 and
case (ii) γ(Q∗5 ) ≤ 0.
In case (i), as the solution Q∗5 is also optimal for the problem Φ′a1 , we only need to consider the solution Q∗3 to the problem
Φ′a3 . Note that the convex objective functions of Φ′a3 and Φ∗a5 are the same and the convex feasible set of Φ′a3 is a subset of
the convex feasible set of Φ∗a5 . Then the solution Q∗3 must satisfy γ(Q∗3 ) = 0 by using a similar argument as that for Ψb1 in
the proof of Proposition 3. Moreover, we may assume that this solution Q∗3 is feasible for the original problem Φ∗a3 (if not,
similar to the discussion for Ψb1 , we do not need to consider this term Φ∗a3 in (43) due to Φ∗a4 ). Hence, the optimal solution
Q∗3 to the problem Φ∗a3 satisfies γ(Q∗3 ) = 0 and β(Q∗3 ) + 0 ≥ 0 is also feasible for the problem Φ∗a1 . Therefore, we can remove
the term Φ∗a3 in the inner minimization of (43).
For case (ii), using a similar argument as above, we can show that the solution Q∗1 with γ(Q∗1 ) = 0 and β(Q∗1 ) ≥ 0 is
feasible for the problem Φ∗a3 , therefore, we can remove this term Φ∗a1 in the inner minimization of (43).
In summary, without loss of optimality, we can replace Φ∗a1 and Φ∗a3 with the new convex optimization problem Φ∗a5 .
Moreover, the optimal value of Φ∗a5 is active (see (37)) in the inner minimization problem in (43) if
[

γ(Q∗5 ) ≥ 0 ∩ β(Q∗5 ) ≥ 0

γ(Q∗5 ) ≤ 0 ∩ γ(Q∗5 ) + β(Q∗5 ) ≥ 0 .
(46)
This completes the proof of Proposition 4.

7

0.09
0.08

Error Exponent

0.07
0.06
0.05
0.04
0.03
0.02
0.01
0
0.00

0.05

0.10

0.12

0.15

0.17

0.20

Fig. 1. Total error exponents E1t and E2t as a function of R2 for two different values of R1 and where the threshold T = 0.

0.06

Error Exponent

0.05

0.04

0.03

0.02

0.01

0
0.00

0.02

0.04

0.07

0.10

0.12

Fig. 2. Total error exponents E1t and E2t as a function of R1 for two different values of R2 and where the threshold T = 0.

For the second term Ψa2 , we can also remove the non-convex constraint γ(Q) ≥ 0 in Φ∗a2 due to Φ∗a4 . Therefore, we can solve
the minimization problem Ψa in (20) efficiently, as the remaining case Φ∗a4 is a convex minimization problem.
Similarly to the above, we can also efficiently calculate E2t in Theorem 2 as s0 (Q̂, R1 ) is a convex minimization problem.
V. N UMERICAL E VALUATIONS
In this section, we present a numerical example to illustrate the values of the error exponents in Theorem 1 and 2. Specifically,
we consider binary symmetric channels (BSCs): Y = X ⊕ Z2 , where X, Y, Z2 ∈ {0, 1} and Z2 ∼ Bern(p2 ). Let U be binary
as well and U ∼ Bern(0.5). Also, let X = U ⊕ Z1 , where Z1 ∈ {0, 1} and Z1 ∼ Bern(p1 ). In this example, we fix p1 = 0.1
and p2 = 0.2, and all the rates are in nats.2
When T = 0, there is no erasure and the decoder performs maximum likelihood (ML) decoding. We obtain a threedimensional exponent-rate region (Ejt , R1 , R2 ) for decoding (m1 , m2 ). To obtain a two-dimensional plot, we consider projections: we fix one rate and vary the other rate and plot the error exponent Ejt , j = 1, 2. Figure 1 shows one projection
for R1 = 0.02 and R1 = 0.08 nats/channel use. For message m1 , the range of R2 for which E1t > 0 (i.e., R2 < 0.17 for
2 All

the Matlab® code to reproduce Figs. 1–4 can be found at https://www.ece.nus.edu.sg/stfpage/vtan/isit18.zip.

8

0.12

Error Exponent

0.1

0.08

0.06

0.04

0.02

0
0.00

0.02

0.04

0.06

0.08

0.10

Fig. 3. Total error exponent E1t and undetected error exponent E1u for message m1 as a function of T for two different pairs of (R1 , R2 ).

R1 = 0.02 and R2 = 0 for R1 = 0.08) coincides with that for the set of achievable rate pairs (R1 , R2 ) corresponding to our
choice of input distribution PUX for decoding only message m1 , namely
\
{R1 ≤ I(X; Y |U ) = 0.07}
{R1 + R2 ≤ I(X; Y ) = 0.19}.
(47)

Moreover, we see that E1t for a fixed R1 is horizontal for R2 below a critical value and curved for R2 above this value. For
message m1 , the range of R2 for which E2t > 0 (i.e., R2 < 0.17 for R1 = 0.02 and R2 < 0.12 for R1 = 0.08) coincides that
for the set of achievable rate pairs (R1 , R2 ) corresponding to our choice of input distribution PUX for decoding only m2 , i.e.,
[
{R2 ≤ I(U ; Y ) = 0.12}
{R1 + R2 ≤ I(X; Y ) = 0.19}.
(48)

Figure 2 shows the other projection for R2 = 0.05 and R2 = 0.15 nats/channel use. It also can be checked that the range of R1
for both messages (m1 , m2 ) coincides with (47). When R2 = 0.05 ≤ I(U ; Y ), we see the curve of E2t rapidly decreases for
R1 below a critical value and remains horizontal for R1 above the critical value. This is because when R2 = 0.05 ≤ I(U ; Y ),
the rate pair (R1 , R2 ) is always achievable, i.e., (R1 , R2 ) belongs to the region defined in (48). When R2 = 0.15 ≥ I(U ; Y ),
we see two error exponents E1t and E2t are equal.
Figures 3 and 4 illustrate the optimal trade-off between the total error exponent and the undetected error exponent as a
function of the threshold T for two different pairs of (R1 , R2 ). We observe that for both messages, the total error exponent
decreases and the undetected error exponent increases when the threshold T increases. We also observe that the smallest
threshold T for which the total error exponent is zero depends on the rate pair (R1 , R2 ) and decreases as either rate increases.
VI. P ROOF

OF

T HEOREM 1

Proof of Theorem 1: Assume, without loss of generality, that the true transmitted message pair is (m1 , m2 ) = (1, 1).
Denote the random sub-codebook {U n (m′2 ) : m′2 ∈ M2 \ {1}} as CU′ , and the (total) error event E1 as

 X
(49)
P (Y n |C1 (m′1 )) > P (Y n |C1 (1))e−nT .
E1 ,
m′1 6=1

Given the optimal decoding region D1∗ in (11), by using the law of total probability, the average total error probability for
message m1 is


EC [et1 (1, 1)] = E(U n (1),X n (1,1),Y n ) ECU′ [Pr{E1 |(U n (1), X n (1, 1), Y n ), CU′ }] ,
(50)
where the conditioning on c′U in (50) is due to the shared “cloud” codebook {U n (m2 ) : m2 ∈ M2 }.

9

0.25

Error Exponent

0.2

0.15

0.1

0.05

0
0.00

0.05

0.10

0.15

0.20

Fig. 4. Total error exponent E2t and undetected error exponent E2u for message m2 as a function of T for two different pairs of (R1 , R2 ).

Next, we calculate the error probability given (U n (1), X n (1, 1), Y n ) = (un , xn , y n ) with joint type Q̂UXY and the subcodebook c′U . For brevity, define the quantities
F1 ,

X

m′1 ∈M1 \{1}

X

X

WYn (y n |X n (m′1 , m′2 ))

(51)

m′2 ∈M2 \{1}

WYn (y n |X n (m′1 , 1))

(52)

f3 , WYn (y n |xn )
X
WYn (y n |X n (1, m′2 )).
F4 ,

(53)

F2 ,

m′1 ∈M1 \{1}

(54)

m′2 ∈M2 \{1}

Note that f3 is a deterministic quantity given (X n (1, 1), Y n ) = (xn , y n ) while the others are random. These definitions allow
us to express Pr{E1 } compactly as follows:

Pr{E1 } = Pr F1 + F2 > (f3 + F4 ) · e−nT .

(55)

We first state the following lemmas. Although Lemma 5 is only used in the proof of Lemma 6, we provide the proof of
Lemma 5 in this section as the notations therein are important and useful for the remainder of the proof of Theorem 1. The
proof of Lemma 6 is relegated to the appendices.
Lemma 5: For given y n , c′U and T ≥ 0, there exists a constant c > 0 such that for n sufficiently large,
Pr{F1 ≤ e−nT · F4 } ≤ e−n·c

(56)

Lemma 6: For given y n , c′U and T ≥ 0, we have

Pr max{F1 , F2 } > max{f3 , F4 } · e−nT

.
= max Pr{F1 > f3 · e−nT }, Pr{F2 > f3 · e−nT } .
Proof of Lemma 6: See Appendix A.

(57)

10

Proof of Lemma 5: Let QU|Y be a conditional type such that QU|Y P̂yn is a joint type defined on U × Y. Define:
1
ln {U n (m′2 ) : m′2 6= 1, U n (m′2 ) ∈ TQU |Y (y n )}
n
Q0 (y n ) , {QU|Y : λ(QU|Y , y n ) ≥ 0}
X
WYn (y n |X n (m′1 , m′2 ))
A(QU|Y ) ,

λ(QU|Y , y n ) ,

(58)
(59)
(60)

m′1 ∈M1 \{1}
m′2 ∈M2 \{1}
U n (m′2 )∈TQU |Y (y n )

X

B(Q′U|Y ) ,

WYn (y n |X n (1, m′2 )).

(61)

m′2 ∈M2 \{1}
(y n )
U n (m′2 )∈TQ′
U |Y

Consider the left-hand-side of (56):
Pr{F1 ≤ e−nT · F4 }
(
X
A(QU|Y ) ≤ e−nT
= Pr
QU |Y ∈Q0 (y n )

≤ Pr
≤

(

[

QU |Y ∈Q0 (y n )

X

QU |Y ∈Q0 (y n )

X

B(Q′U|Y

Q′U |Y ∈Q0 (y n )


A(QU|Y ) ≤ e−nT B(QU|Y )

)

)

)


Pr A(QU|Y ) · enT ≤ B(QU|Y ) ,

(62)

(63)
(64)

where (62) is due to the fact that each codeword X n (m1 , m2 ), m1 ∈ M1 is generated from a unique “cloud center” U n (m2 ).
Let QX|UY be a conditional type such that QX|UY P̂un yn is a joint type defined on U × Y × X for some (un , y n ) ∈ U n × Y n .
Define N1 (QUXY ) to be the number of codewords X n (1, m′2 ), m′2 6= 1 whose joint type with (U n (m′2 ), Y n ) is QUXY , i.e.,
N1 (QUXY ) , {X n (1, m′2 ) : m′2 6= 1, (U n (m′2 ), X n (1, m′2 ), Y n ) ∈ TQU XY } .

(65)

Define f (QUXY ) , −EQU XY ln W . Now, we consider the following term:
Pr{B(QU|Y ) ≥ ent }
 X

−nf (QU XY )
nt
= Pr
N1 (QUXY )e
≥e

(66)

QX|U Y


.
= max Pr N1 (QUXY ) ≥ en(f (QU XY )+t) ,
QX|U Y

(67)

where QUXY = QX|UY QU|Y Q̂Y and (67) is from a standard large deviation argument (see Merhav [17, Eqs. (15)–(20)]).
n
Then, for a given QUXY , N1 (QUXY ) is a binomial random variable with enλ(QU |Y ,y ) trials and “success” probability
TQX|U Y (un , y n )
TQX|U

(un )

 .
n
TQX|U (un ) = e−n[D(QX|U kPX|U |QU )+IQ (X;Y |U)] .
· PX

Thus, by a standard large deviations analysis (see Merhav [18, pp. 167–169]), we have

n
.
Pr N1 (QUXY ) ≥ en(f (QU XY )+t) = e−nE3 (QU XY ,t,λ(QU |Y ,y )) ,

(68)

(69)

where

E3 (QUXY , t, r) ,

(

|β(QUXY , R1 ) + R1 − r|+
∞

QUXY ∈ L4 (t, r, R1 )
else

(70)

and where
L4 (t, r, R1 ) , {QUXY : t + f (QUXY ) ≤ |r − β(QUXY , R1 ) − R1 |+ } .

(71)

E3∗ (t, r) , min E3 (QUXY , t, r).

(72)

For brevity, define
QX|U Y

11

Therefore by combining (67) and (69), we have
lim −

n→∞

1
ln Pr{B(QU|Y ) ≥ ent } = min E3 (QUXY , t, λ(QU|Y , y n ))
QX|U Y
n
= E3∗ (t, λ(QU|Y , y n ))

(73)
(74)

Similarly as before, let R1′ = λ(QU|Y , y n ) + R1 , we have
lim −

n→∞

1
ln Pr{A(QU|Y ) ≥ ent } = E3∗ (t, R1′ ).
n

(75)

On the other hand, define N2 (QUXY ) be the number of codewords X n (m′1 , m′2 ), m′1 6= 1, m′2 6= 1 whose joint type with
(U n (m′2 ), Y n ) is QUXY , i.e.,
N2 (QUXY ) , {X n (m′1 , m′2 ) : m′1 6= 1, m′2 6= 1, (U n (m′2 ), X n (m′1 , m′2 ), Y n ) ∈ TQU XY } .

(76)

Now, we have
Pr{A(QU|Y ) ≤ ent }
 X

−nf (QU XY )
nt
= Pr
N2 (QUXY )e
≤e

(77)

QX|U Y

.
= Pr



min N2 (QUXY )e−nf (QU XY ) ≤ ent

QX|U Y



(78)

 \


−nf (QU XY )
nt
= Pr
,
N2 (QUXY )e
≤e

(79)

QX|U Y

by using a similar argument as that for [17, Eq. (30)], we have

n
.
β(Q′UXY , R1 ) + R1 + t + f (Q′UXY )
Pr{A(QU|Y ) ≤ ent } = 1 R1′ ≤ min
′
QX|U Y

o
,
+

(80)

where Q′UXY = Q′X|UY QU|Y Q̂Y . We now find the minimum value of t for which the value of this indicator function is unity
by using a similar method as that for [17, Eq. (31)]. The condition in the indicator function above is equivalent to
n

o
′
′
.
(81)
β(Q
,
R
)
+
R
+
a
t
+
f
(Q
)
R1′ ≤ min
max
1
1
UXY
UXY
′
QX|U Y 0≤a≤1

Define the function g(R1 , R1′ , Q′UXY ) , R1′ − β(Q′UXY , R1 ) − R1 if R1′ ≥ β(Q′UXY , R1 ) + R1 and −∞ otherwise. Then (81)
is also equivalent to


R1′ − β(Q′UXY , R1 ) − R1
′
−
f
(Q
)
+
t ≥ max
min
(82)
UXY
Q′X|U Y 0≤a≤1
a
[−f (Q′UXY ) + g(R1 , R1′ , Q′UXY )]
= max
′

(83)

QX|U Y

= R1′ +
=

max

Q′X|U Y :β(Q′U XY ,R1 )+R1 ≤R′1

max

Q′X|U Y :β(Q′U XY ,R1 )≤λ(QU |Y ,y n )

, s1 .





− f (Q′UXY ) − β(Q′UXY , R1 ) − R1



(84)


− f (Q′UXY ) − β(Q′UXY , R1 ) + λ(QU|Y , y n )

Lemma 7: E3∗ (t, R1′ ), as defined in (72), vanishes for all t ≤ s1 .
Proof of Lemma 7: See Appendix B.
Thus, in summary, we have
(
o
n
. 0
nt
n(t+ǫ)

=
Pr e ≤ A(QU|Y ) ≤ e
exp − nE3∗ (t, R1′ )

t < s1 − ǫ
t ≥ s1

.

(85)
(86)

(87)

12

Now let ǫ > 0 be an arbitrarily small constant. We can calculate the term Pr{A(QU|Y )·enT ≤ B(QU|Y )} (a summand in (64))
as follows:
Pr{A(QU|Y ) · enT ≤ B(QU|Y )}
X
=
Pr{A = a} · Pr{B ≥ enT · a}

(88)

a

n
o

1
. X
Pr iǫ ≤ ln A ≤ (i + 1)ǫ · Pr B ≥ en(T +iǫ)
=
n
i


. X
exp − nE3∗ (iǫ, R1′ ) · exp − nE3∗ (T + iǫ, λ(QU|Y , y n ))
=

(89)
(90)

i≥s1 /ǫ


.
= exp − nE3∗ (T + s1 , λ(QU|Y , y n )) ,

(91)

where (91) is from the facts that the dominant contribution to the sum over i is due only to the term with index i = s1 /ǫ and
E3∗ (s1 , R1′ ) = 0; see Lemma 7. Thus, from (64) and (91), we have
Pr{F1 ≤ e−nT · F4 }
X
·

exp − nE3∗ (T + s1 , λ(QU|Y , y n ))
≤

(92)

QU |Y ∈Q0 (y n )

.
= exp



≤ e−n·c

−n

min

QU |Y ∈Q0 (y n )

E3∗ (T


+ s1 , λ(QU|Y , y ))
n

for some constant c > 0.

(93)
(94)

We need to justify the final inequality (94) carefully. This inequality follows from the fact that the exponent in (93), namely
minQU |Y ∈Q0 (yn ) E3∗ (T + s1 , λ(QU|Y , y n )), vanishes if and only if the following condition (see (70), (71) and (72)) is satisfied:
∃ QU|Y ∃ QX|UY such that



s1 + T + f (QUXY ) ≤ λ(QU|Y , y n ) − β(QUXY , R1 ) − R1
\
λ(QU|Y , y n ) − β(QUXY , R1 ) − R1 ≥ 0 ,

where QU|Y satisfies that λ(QU|Y , y n ) ≥ 0. Equivalently,



min
min s1 + T + f (QUXY ) − λ(QU|Y , y n ) − β(QUXY , R1 ) − R1 :
QU |Y ∈Q0 (y n ) QX|U Y

n
λ(QU|Y , y ) − β(QUXY , R1 ) − R1 ≥ 0 ≤ 0.

(95)

(96)

However, by recalling the definition of the constant s1 in (86), we see that this condition is equivalent to
(


min
f (QUXY ) + β(QUXY , R1 )
min n
QU |Y ∈Q0 (y )

−

QX|U Y :β(QU XY ,R1 )
≤λ(QU |Y ,y n )−R1

min

Q′X|U Y :β(Q′U XY ,R1 )≤
λ(QU |Y ,y n )



f (Q′UXY

)+

β(Q′UXY


, R1 )

)

≤ −(R1 + T ) < 0,

(97)

which cannot be true due to the fact the feasible set of the first inner minimization is a subset of the one of the second inner
minimization. This concludes the proof of Lemma 5.
Now, we continue the proof of Theorem 1 by using Lemmas 5 and 6. We reuse the notations in the proof of Lemma 5
.
above. From (55), and using the asymptotic equality to first-order in the exponent notation =, we have

.
Pr{E1 } = Pr max{F1 , F2 } > max{f3 , F4 } · e−nT .
(98)

By using Lemma 6, we have


.
Pr{E1 } = max Pr{F1 > f3 · e−nT }, Pr{F2 > f3 · e−nT } .

(99)

Next, we consider the first term in the right-hand-side of (99). Let
s,−

1
ln(f3 · e−nT ) = f (Q̂UXY ) + T.
n

(100)

13

Now, we have


ECU′ Pr{F1 > f3 · e−nT CU′ }




X
X
= ECU′ Pr
N2 (QUXY )e−nf (QU XY ) ≥ e−ns CU′ 

(101)

QU |Y ∈Q0 (y n ) QX|U Y



.
= ECU′ 

X

max Pr N2 (QUXY )e−nf (QU XY ) ≥ e−ns

QU |Y ∈Q0 (y n )

X

′
CU

E



max

ECU′



=

QU |Y ∈Q0 (y n )

.
=
.
=

QU |Y ∈Q0 (y n )

n

QX|U Y


o
CU′ 

o
n
−nf (QU XY )
−ns
′
max Pr N2 (QUXY )e
≥e
CU

QX|U Y

o
n
n(f (QU XY )−s)
′
max Pr N2 (QUXY ) ≥ e
CU
QX|U Y


exp{−nE3∗ (−s, R1 + Λ(QU|Y , Y n ))}

max
ECU′
X
.
= max
Pr{Λ(QU|Y , Y n ) = λ} · exp{−nE3∗ (−s, R1 + λ)},
QU |Y ∈Q0 (y n )
QU |Y

(102)
(103)
(104)
(105)
(106)

λ≥0

where Q = QX|UY QU|Y Q̂Y , and the derivation of (105) is similar to that of (69) (so the details are omitted). Note that the
sum over λ ≥ 0 in (106) is only over a finite set of λ since λ as defined in (58) only takes on finitely many values.
Recall that λ(QU|Y , y n ) is the exponent of the number of “cloud centers” U n (m′2 ) whose conditional type with Y n is QU|Y .
By using standard large deviations analysis (see Merhav [18, pp. 167–169]), for some small enough ǫ > 0, we have




.
(107)
Pr{Λ(QU|Y , Y n ) = λ} = 1 λ ∈ | − γ(QUY , R2 )|+ − ǫ, | − γ(QUY , R2 )|+ + ǫ · exp{−n|γ(QUY , R2 )|+ },
where QUY = QU|Y Q̂Y . Note that the function γ(Q, R2 ) (see (16)) only depends on the marginal distribution QUY , the
notation γ(QUY , R2 ) is consistent. Therefore, we have


ECU′ Pr{F1 > f3 · e−nT }


.
= max exp{−nE3∗ (−s, R1 + | − γ(QUY , R2 )|+ )} · exp{−n|γ(QUY , R2 )|+ }
QU |Y

i
h
.
= exp − n min E3∗ (−s, R1 + | − γ(QUY , R2 )|+ ) + |γ(QUY , R2 )|+
QU |Y

i
h
= exp − n min E3 (QUX|Y Q̂Y , −s, R1 + | − γ(QUY , R2 )|+ ) + |γ(QUY , R2 )|+
QU X|Y


= exp − n
min
Φ(QUX|Y Q̂Y , R1 , R2 ) ,

(108)
(109)
(110)
(111)

QU X|Y ∈L1 (Q̂U XY ,R1 ,R2 ,T )

where (111) is due to the fact that
|β(QUXY , R1 ) − | − γ(QUY , R2 )|+ |+ + |γ(QUY , R2 )|+ = Φ(QUX|Y Q̂Y , R1 , R2 ).

(112)

Finally, after averaging over (U n (1), X n (1, 1), Y n ), we have


1
ln E(U n (1),X n (1,1),Y n ) ECU′ [Pr{F1 > f3 · e−nT CU′ }]
nh
i
= min D(Q̂UXY kPUXY ) +
min
Φ(QUX|Y Q̂Y , R1 , R2 ) .
lim −

n→∞

Q̂U XY

(113)

QU X|Y ∈L1 (Q̂U XY ,R1 ,R2 ,T )



For the remaining term E(U n (1),X n (1,1),Y n ) ECU′ [Pr{F2 > f3 · e−nT CU′ }] (second term in (99)), the proof is similar to the
proof for (113), therefore we will only provide an outline. Once again, define N3 (QUXY ) be the number of codewords
X n (m′1 , 1) whose joint type with (U n (1), Y n ) is QUXY , i.e.,
N3 (QUXY ) , {X n (m′1 , m′2 ) : m′1 6= 1, (U n (1), X n (m′1 , 1), Y n ) ∈ TQU XY } .

(114)

14

Now, we have


ECU′ Pr{F1 > f3 · e−nT CU′ }
 X

= Pr
N3 (QUXY )e−nf (QU XY ) ≥ e−ns

(115)

QX|U Y

.
= exp

n

o
− n min E3 (QUXY , −s, R1 ) ,
QX|U Y

(116)

where QUXY = QX|UY Q̂UY . After averaging over (U n (1), X n (1, 1), Y n ), we have
lim −

n→∞



1
ln E ECU′ [Pr{F2 > f3 · e−nT CU′ }] = Ψb .
n

Then, due to (99), we have E1t = min{Ψa , Ψb }.
For the total error probability of the message pair, according to the optimal decoding region (12), we obtain


EC [etY (1, 1)] = EC Pr{F1′ + F2 > f3 · e−nT C}

(117)

(118)

where

F1′ ,

X

m′1 ∈M1

X

WYn (Y n |X n (m′1 , m′2 )).

(119)

m′2 ∈M2 \{1}

′
As the difference between F1 and F1′ is only in the number
is exactly one
 of m1 (the difference
 and the rates are asymptotically
−nT
′
equal), the exponents of ECU′ Pr{F1 > f3 · e
CU } and ECU′ Pr{F1′ > f3 · e−nT CU′ } are identical. Therefore, we have
EYt = E1t . In [13, Lemma 1], it was shown that E1u = E1t + T and EYu = EYt + T. This concludes the proof of Theorem 1.

VII. P ROOF

OF

T HEOREM 2

Proof of Theorem 2: Assume the true transmitted message pair is (m1 , m2 ) = (1, 1). Define the (total) error event E2 as
 X

n
′
n
−nT
E2 ,
.
(120)
P (Y |C2 (m2 )) > P (Y |C2 (1))e
m′2 6=1

The average total error probability for message m2 associated to the decoding region in (11) is given by
EC [et2 (1, 1)] = E(U n (1),X n (1,1),Y n ) [Pr{E2 |(U n (1), X n (1, 1), Y n )}] .

(121)

Similarly, for given (U n (1), X n (1, 1), Y n ) = (un , xn , y n ) with joint type Q̂UXY , we have
Pr{E2 } = Pr{F1′ > (f3 + F2 ) · e−nT }
.
= Pr{F1′ > max{f3 , F2 } · e−nT }.

(122)
(123)

Let ǫ > 0 be arbitrarily small and define
K1 ,

1
ln F2
n

and k2 ,

1
ln f3 = −f (Q̂UXY ).
n

(124)

Then we have

Pr F1′ > max{f3 , F2 } · e−nT (un , xn , y n )
n
o
X
Pr {K1 = k1 | (un , xn , y n )} · Pr F1′ > en[max{k1 ,k2 }−T ] (un , xn , y n )
=

(125)

k1

n
o
. X
Pr {iǫ ≤ K1 < (i + 1)ǫ | (un , xn , y n )} · Pr F1′ > en[max{iǫ,k2 }−T ] (un , xn , y n )
=

(126)

i

.
=

X

i≥s0 (Q̂,R1 )/ǫ

n
o
exp{−E5 (Q̂UY , iǫ)} · Pr F1′ > en[max{iǫ,k2 }−T ] (un , xn , y n )

n
o
.
= Pr F1′ > en[max{s0 (Q̂,R1 ),k2 }−T ] (un , xn , y n ) ,

(127)
(128)

where (127) is due to Lemma 8 below, and (128) is from the facts that the dominant contribution to the sum over i is due to
the term i = s0 (Q̂, R1 ) and E5 (Q̂UY , s0 (Q̂, R1 )) = 0 (similarly to Lemma 7).

15

Lemma 8: Assume that (U n (1), X n (1, 1), Y n ) = (un , xn , y n ) with joint type Q̂UXY , we have


X
n
n
n
′
n(t+ǫ)
n
n
n
n
n n
nt
WY (Y |X (m1 , 1)) ≤ e
(U (1), X (1, 1), Y ) = (u , x , y )
Pr e ≤
m′1 6=1

.
=

(

0

t < s0 (Q̂UXY , R1 ) − ǫ


exp − nE5 (Q̂UY , t)

where

E5 (Q̂UY , t) , min

QX|U Y

(129)

t ≥ s0 (Q̂UXY , R1 )



|β(Q, R1 )|+ : t ≤ −f (Q) + | − β(Q, R1 )|+ .

(130)

where Q in (130) is equal to Q = QX|UY Q̂UY .
Proof of Lemma 8: Similar to that of (87) where now the rate and conditional distribution are R1 and QU|Y (instead of
R1′ and Q̂U|Y ). This concludes the proof of Lemma 8.
Now, we continue the proof of Theorem 2. Since the right-hand-side of the inequality in (128) is constant for a given triple
(U n (1), X n (1, 1), Y n ) = (un , xn , y n ), similarly to the calculation for Pr{F1 > f3 · e−nT } in (111), we obtain

Pr F1′ > max{f3 , F2 } · e−nT (un , xn , y n )
(
)
 

.
(131)
= exp − n min E3 QUXY , max{s0 (Q̂UXY , R1 ), k2 } − T, R1 + | − γ(QUY , R2 )|+ + |γ(QUY , R2 )|+
QU X|Y

.
= exp

(

− n max



min

QU X|Y
∈L1 (Q̂U XY ,R1 ,R2 ,T )

Φ(QUX|Y Q̂Y , R1 , R2 ),

min

QU X|Y
∈L3 (Q̂U XY ,R1 ,R2 ,T )

)
Φ(QUX|Y Q̂Y , R1 , R2 )
,

(132)

where (132) is due to the fact that the function minQU X|Y [. . .] (i.e., the exponent in (131)) is non-decreasing in the parameter
max{s0 (Q̂UXY , R1 ), k2 }−T (where the first term in (132) corresponds to the parameter k2 −T and the second one corresponds
to the parameter s0 (Q̂UXY , R1 ) − T ).
By combining (123) and (132) and averaging over (U n (1), X n (1, 1), Y n ), we have
lim −

n→∞

1
1
ln EC [et2 (1, 1)] = lim − ln E(U n (1),X n (1,1),Y n ) [Pr{E2 |(U n (1), X n (1, 1), Y n )}]
n→∞
n
n
= max{Ψa , Ψc }.

(133)
(134)

Finally, the equality E2u = E2t + T is due to [13, Lemma 1]. This concludes the proof of Theorem 2.
A PPENDIX A
P ROOF OF L EMMA 6
Proof: Note that f3 , defined in (53), is constant in this proof. We have

Pr max{F1 , F2 } > max{f3 , F4 } · e−nT


= Pr max{F1 , F2 } > F4 · e−nT , F4 > f3 + Pr{F4 ≤ f3 } · Pr max{F1 , F2 } > f3 · e−nT |F4 ≤ f3


= Pr max{F1 , F2 } > F4 · e−nT , F4 > f3 + Pr{F4 ≤ f3 } · Pr max{F1 , F2 } > f3 · e−nT


.
= Pr max{F1 , F2 } > F4 · e−nT , F4 > f3 + Pr{F4 ≤ f3 } · max Pr{F1 > f3 · e−nT }, Pr{F2 > f3 · e−nT } ,

(135)
(136)
(137)

where (136) is due to the fact that (F1 , F2 ) is independent of F4 . See the definitions of F1 , F2 and F4 in (51)–(54).
Recall the random codebook generation with superposition structure as described in Section II-B. We may rewrite F1 as
X
X
X
WYn (y n |X n (2, m′2 )).
(138)
WYn (y n |X n (m′1 , m′2 )) +
F1 =
m′1 ∈M1 \{1,2} m′2 ∈M2 \{1}

m′2 ∈M2 \{1}

Note that all the X n (m1 , m2 ) terms in F1 and F4 are generated in an i.i.d. manner. Hence the final term in (138), a non-negative
random variable, has the same distribution as F4 . Since WYn (y n |·) ≥ 0 and e−nT ≤ 1, for any given c′U , we obtain
Pr{F1 > f3 · e−nT } ≥ Pr{F1 > f3 } ≥ Pr{F4 > f3 }.

(139)

The final inequality in (139) follows from the fact that if we have two random variables A and A′ which have the same
distribution and B is a non-negative random variable, then clearly Pr{A + B ≥ c} ≥ Pr{A′ ≥ c} for all c ∈ R. Now, we
focus on the term qn , Pr{F4 > f3 }. Assume that the limit of qn exists (otherwise, we may pick a convergent subsequence
and work with that subsequence in the following). There are two cases: case (i) limn→∞ qn = 0 and case (ii) limn→∞ qn > 0.

16

•

For case (i), from (137), we have:

Pr max{F1 , F2 } > max{f3 , F4 } · e−nT


.
= Pr max{F1 , F2 } > F4 · e−nT , F4 > f3 + max Pr{F1 > f3 · e−nT }, Pr{F2 > f3 · e−nT }
 
.
= max Pr max{F1 , F2 } > F4 · e−nT , F4 > f3 , Pr{F1 > f3 · e−nT }, Pr{F2 > f3 · e−nT }

.
= max Pr{F1 > f3 · e−nT }, Pr{F2 > f3 · e−nT } ,

(140)
(141)
(142)

where (140) is due to the fact that Pr{F4 ≤ f3 } = 1 − qn tends to 1, and the final step (142) is due to the fact that

Pr max{F1 , F2 } > F4 · e−nT , F4 > f3
≤ Pr{F4 > f3 }

≤ Pr{F1 > f3 · e
•

(143)

−nT

},

(144)

and where (144) is due to (139).
For case (ii), on the one hand, we have

Pr max{F1 , F2 } > F4 · e−nT , F4 > f3

≥ 1 − Pr max{F1 , F2 } ≤ F4 · e−nT − Pr{F4 ≤ f3 }
≥ 1 − Pr{F1 ≤ F4 · e

≥ Pr{F4 > f3 } − e
.
= 1,

−nT

(145)

} − Pr{F4 ≤ f3 }

(146)

−n·c

(147)
(148)

where (147) is due to Lemma 5 and (148) is due to the fact that (147) does not tend to 0 (and is obviously bounded
above by 1) from the assumption that limn→∞ qn > 0. From (137), we have

.
(149)
Pr max{F1 , F2 } > max{f3 , F4 } · e−nT = 1.
On the other hand, due to (139), we have

max Pr{F1 > f3 · e−nT }, Pr{F2 > f3 · e−nT }
≥ Pr{F1 > f3 · e−nT }
≥ Pr{F4 > f3 }
.
= 1,

(150)
(151)
(152)

where (151) is due to (139), and (152) is due to the fact that (151) does not tend to 0 from the assumption that
limn→∞ qn > 0. Thus, for case (ii), combining (149) and (152), we have


.
(153)
Pr max{F1 , F2 } > max{f3 , F4 } · e−nT = max Pr{F1 > f3 · e−nT }, Pr{F2 > f3 · e−nT } .

Since for both cases, we arrive at the same conclusions in (142) and (153), this completes the proof of Lemma 6.
A PPENDIX B
P ROOF OF L EMMA 7

Proof: As E3∗ (t, R1′ ) is non-decreasing for t, we only need to show that E3∗ (t, R1′ ) = 0 when t = s1 . There are two cases
for s1 : case (i) s1 > −∞ and case (ii) s1 = −∞.
∗
′∗
∗
• For case (i), assume that the optimal solution corresponding to s1 is Q = QX|UY QU|Y Q̂Y . Now, we take QUXY = Q
′
for the constraint in L4 (s1 , R1 , R1 ) in (71), then we have
s1 + f (Q∗ ) − |R1′ − β(Q∗ , R1 ) − R1 |+
= [−f (Q∗ ) − β(Q∗ , R1 ) + λ(QU|X , y n )] + f (Q∗ ) − |λ(QU|X , y n ) − β(Q∗ , R1 )|+
∗

n

∗

n

∗

= [−f (Q∗) − β(Q , R1 ) + λ(QU|X , y )] + f (Q ) − [λ(QU|X , y ) − β(Q , R1 )]
= 0,

(154)
(155)
(156)

where (155) is due to the fact Q∗ satisfies the constraint λ(QU|X , y n ) ≥ β(Q∗ , R1 ) in (85). Therefore, we have Q∗ ∈
L4 (s1 , R1′ , R1 ) and |β(Q∗ , R1 ) + R1 − R1′ |+ = 0. Thus, E3∗ (t, R1′ ) = 0.
′
∗
′
• For case (ii), the constraint in L4 (−∞, R1 , R1 ) in (71) always holds true. This is easy to check that E3 (−∞, R1 ) = 0.
This completes the proof of Lemma 7.
Acknowledgements: D. Cao is supported by the China Scholarship Council (No. 201706090064) and the National Natural
Science Foundation of China under Grant No. 61571122.

17

R EFERENCES
[1] T. Cover, “Broadcast channels,” IEEE Trans. on Inform. Th., vol. 18, no. 1, pp. 2–14, Jan 1972.
[2] J. Körner and K. Marton, “General broadcast channels with degraded message sets,” IEEE Trans. on Inform. Th., vol. 23, no. 1, pp. 60–64, Jan 1977.
[3] J. Körner and A. Sgarro, “Universally attainable error exponents for broadcast channels with degraded message sets,” IEEE Trans. on Inform. Th.,
vol. 26, no. 6, pp. 670–679, Nov 1980.
[4] Y. Kaspi and N. Merhav, “Error exponents for broadcast channels with degraded message sets,” IEEE Trans. on Inform. Th., vol. 57, no. 1, pp. 101–123,
Jan 2011.
[5] R. Averbuch and N. Merhav, “Exact random coding exponents and universal decoders for the asymmetric broadcast channel,” arXiv:1702.08003, 2017.
[6] R. Averbuch, N. Weinberger, and N. Merhav, “Expurgated bounds for the asymmetric broadcast channel,” arXiv:1711.10299, 2017.
[7] G. Forney, “Exponential error bounds for erasure, list, and decision feedback schemes,” IEEE Trans. on Inform. Th., vol. 14, no. 2, pp. 206–220, Mar
1968.
[8] I. Csiszár and J. Körner, Information theory: Coding theorems for discrete memoryless systems. Cambridge University Press, 2011.
[9] E. Telatar, “Multi-access communications with decision feedback decoding,” Ph.D. dissertation, Massachusetts Institute of Technology, 1992.
[10] P. Moulin, “A Neyman-Pearson approach to universal erasure and list decoding,” IEEE Trans. on Inform. Th., vol. 55, no. 10, pp. 4462–4478, Oct 2009.
[11] N. Merhav, “Error exponents of erasure/list decoding revisited via moments of distance enumerators,” IEEE Trans. on Inform. Th., vol. 54, no. 10, pp.
4439–4447, Oct 2008.
[12] A. Somekh-Baruch and N. Merhav, “Exact random coding exponents for erasure decoding,” IEEE Trans. on Inform. Th., vol. 57, no. 10, pp. 6444–6454,
Oct 2011.
[13] W. Huleihel, N. Weinberger, and N. Merhav, “Erasure/list random coding error exponents are not universally achievable,” IEEE Trans. on Inform. Th.,
vol. 62, no. 10, pp. 5403–5421, Oct 2016.
[14] N. Weinberger and N. Merhav, “Simplified erasure/list decoding,” IEEE Trans. on Inform. Th., vol. 63, no. 7, pp. 4218–4239, July 2017.
[15] M. Hayashi and V. Y. F. Tan, “Asymmetric evaluations of erasure and undetected error probabilities,” IEEE Trans. on Inform. Th., vol. 61, no. 12, pp.
6560–6577, Dec 2015.
[16] V. Y. F. Tan, “Error and erasure exponents for the asymmetric broadcast channel,” in IEEE Information Theory Workshop - Fall, Jeju, S. Korea, 2015,
pp. 153 – 157.
[17] N. Merhav, “Exact random coding error exponents of optimal bin index decoding,” IEEE Trans. on Inform. Th., vol. 60, no. 10, pp. 6024–6031, Oct
2014.
[18] ——, “Statistical physics and information theory,” Foundations and Trends® in Communications and Information Theory, vol. 6, no. 1–2, pp. 1–212,
2010.

