1

On The Reliability Function of Discrete
Memoryless Multiple-Access Channel with
Feedback
arXiv:1801.07777v1 [cs.IT] 23 Jan 2018

Mohsen Heidari, Achilleas Anastasopoulos, and S. Sandeep Pradhan

Abstract
We derive a lower and upper bound on the reliability function of discrete memoryless multiple-access
channel (MAC) with noiseless feedback and variable-length codes (VLCs). The bounds are similar to the
one for point-to-point channels, increasing linearly with respect to an appropriate distance between the rate
pair and the capacity boundary. For the lower bound on the error exponent, we adapt Yamamoto and Itoh’s
coding scheme consisting of a data and a confirmation stage. In the data stage we use arbitrary feedback
capacity-achieving codes. In the confirmation stage, each transmitter sends one bit of information to the
receiver using a pair of codebooks of size two, one for each transmitter. The codewords at this stage are
selected randomly according to an appropriately optimized joint probability distribution. For the upper
bound on the error exponent, we adopt the proof techniques of Burnashev for the reliability function
of the point-to-point case. The upper bound is derived by studying the rate of decrease of appropriate
message entropies.

I. I NTRODUCTION
For communications over discrete memoryless channels (DMC) noiseless feedback does not increase
the capacity [1]. Furthermore, Dobrushin [4] and later Haroutunian [5] showed that feedback does not
improve the error exponent of symmetric channels when fixed-length codes are used. Nevertheless,
feedback can be very useful in the context of variable-length codes.
In a remarkable work, Burnashev [2] demonstrated that the error exponent improves for DMCs with
feedback and variable-length codes. The error exponent has a simple form
E(R) = (1 −

R
)C1 ,
C

(1)

The authors are with the Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor,
MI, 48105 USA e-mail: mohsenhd, anastas, pradhanv@umich.edu

January 25, 2018

DRAFT

2

where R is the (average) rate of transmission, C is the capacity of the channel, and C1 is the maximal
relative entropy between conditional output distributions. Berlin et al [6] have provided a simpler derivation of the Burnashev bound that emphasizes the link between the constant C1 and the binary hypothesis
testing problem. Yamamoto and Itoh [7] introduced a coding scheme that its error exponent achieves
E(R) in (1). Their scheme consists of two distinct transmission phases that we called the data and the

confirmation phase, respectively. In the data stage the message is encoded using a capacity achieving
fixed blocklength code. During the confirmation phase, the transmitter sends one bit of information to
the receiver. The decoder performs a binary hypothesis test to decide if 0 or 1 is transmitted.
In the context of communications over multi-user channels, the benefits of feedback are more prominent.
For instance, Gaarder and Wolf [8] showed that feedback can expand the capacity region of discrete memoryless multiple-access channels (MAC). Characterizing the capacity and the error exponent for MACs
remains an open problem. Using directed information measures, Kramer [9] was able to characterize
the feedback-capacity region of two-user DM-MAC with feedback. However, the characterization is in
the form of infinite letter directed information measures which is not computable in general. The error
exponent for discrete memoryless MAC without feedback is studied in [12], [13].
In this paper, we study the error exponent of discrete memoryless MAC with noiseless feedback.
In particular, we derive an upper bound and a lower bound. For that, let (||R||, θR ) denote the polar
coordinate of (R1 , R2 ) in R2 . In this setting, the upper bound is
Eu (R1 , R2 ) = (1 −

||R||
)Du
C(θR )

(2)

where C(θR ) is the point of the capacity frontier at the angle determined by R. The lower-bound is
the same as Eu but with different constant Dl . The constants Dl and Du are determined by the relative
entropy between the conditional output distributions. We demonstrate how for symmetric channels the
two bounds coincide. For that we provide an example for which Dl = Du , which implies that the bounds
are tight.
The paper is organized as follows: In Section II, basic definitions and the problem formulation are
provided. In Section III, we derive a lower-bound for the reliability function. In Section IV, we characterize
an upper-bound for the reliability function. Finally, Section V concludes the paper.
II. P ROBLEM F ORMULATION

AND

D EFINITIONS

Consider a discrete memoryless MAC with input alphabets X1 , X2 , and output alphabet Y . The channel
conditional probability distribution is denoted by Q(y|x1 , x2 ) for all (y, x1 , x2 ) ∈ Y × X1 × X2 . Such

January 25, 2018

DRAFT

3

setup is denoted by (X1 , X2 , Y, Q). Let y t and xti , i = 1, 2, be the channel output and the inputs sequences
after t uses of the channel, respectively. Then, the following condition is satisfied:
t−1
P (yt |y t−1 , xt−1
1 , x2 ) = Q(yt |x1t , x2t ).

(3)

We assume that the output of the channel as a feedback is available at the encoders with one unit of
delay.
Definition 1. A (M1 , M2 , N )- variable-length code (VLC) for a MAC (X1 , X2 , Y, Q) with feedback is
defined by
•

A pair of messages W1 , W2 that are randomly and uniformly selected from {1, 2, . . . , Mi }, i = 1, 2.

•

Two sequences of encoding functions
ei,t : {1, 2, . . . , Mi } × Y t−1 → Xi ,

i = 1, 2,

one for each transmitter.
•

A sequence of decoding functions
dt : Y t → {1, 2, ..., M1 } × {1, 2, ..., M2 }.

•

A stopping time T w.r.t the filtration Ft defined as the σ -algebra of Y t . Furthermore, T satisfies
E[T ] ≤ N .

It is assumed that a message Wi , i = 1, 2, is selected for Transmitter i from the set [1 : Mi ] with uniform
distribution. Given the message Wi , the tth output of Transmitter i is given by Xi,t = ei,t (Wi , Y t−1 ).
Let (Ŵ1,t , Ŵ2,t ) = dt (Y t ). Then, the decoded messages at the decoder are denoted by Ŵ1 = Ŵ1,T , and
Ŵ2 = Ŵ2,T . In what follows, for any (M1 , M2 , N ) VLC, we define average rate-pair, error probability,

and error exponent. Average rates for a (M1 , M2 , N )-variable-length code are defined as
(i)

RN ,

log2 Mi
,
E[T ]

i = 1, 2.

The probability of error is defined as


Pe = P (Ŵ1 , Ŵ2 ) 6= (W1 , W2 ) .

2 Pe
The exponent of a VLC with probability of error Pe and stopping time T is defined as E = − log
.
E[T ]

Definition 2. A reliability function E(R1 , R2 ) is said to be achievable for a MAC if for any R1 , R2 > 0
and ǫ > 0 there exists a (M1 , M2 , N )-VLC such that
−

January 25, 2018

log2 Mi
log2 Pe
≥ E(R) − ǫ, and
≥ Ri − ǫ,
N
N

DRAFT

4

where i = 1, 2, and Pe is the error probability of the VLC.
Definition 3. The reliability function of a MAC with feedback is defined as the supremum of all achievable
reliability functions E(R1 , R2 ).
A. The Feedback-Capacity Region of MAC
We summarize Kramer’s results presented in [9] for the feedback capacity of MAC. We use directed
information and conditional directed information as defined in [9]. The normalized directed information
from a sequence Xn to a sequence Y n when causally conditioned on Zn is denoted by
In (X → Y ||Z) =

1
I(Xn → Y n ||Zn ).
n

(4)

The feedback-capacity region of a discrete memoryless MAC with feedback (X1 , X2 , Y, Q) is denoted
by C , and is the closure of the set of all rate-pairs (R1 , R2 ) such that
R1 ≤ IL (X1 → Y ||X2 )
R2 ≤ IL (X2 → Y ||X1 )
R1 + R2 ≤ IL (X1 X2 → Y ),

where L is a positive integer, and PX1L X2L Y L factors as
L
Y

l−1
l−1
P1,l (xl1 |xl−1
)P2,l (xl2 |xl−1
)Q(yl |x1,l x2,l ).
1 y
2 y

(5)

l=1

Definition 4. Let λ1 , λ2 , λ3 ≥ 0, and λ1 + λ2 + λ3 = 1. Define
Cλ = sup

sup

λ1 IL (X1 → Y |X2 ) + λ2 IL (X2 → Y |X1 ) + λ3 IL (X1 X2 → Y ),

L∈N PX L X L Y L
1

2

where PX1L X2L Y L factors as in Definition (5).
Fact 1. The feedback-capacity of a discrete memoryless MAC with feedback is the same as the closure
of the set of rate-pairs (R1 , R2 ) such that the inequality
λ1 R1 + λ2 R2 + λ3 (R1 + R2 ) ≤ Cλ

holds for all λ1 , λ2 , λ3 ≥ 0, with λ1 + λ2 + λ3 = 1.

January 25, 2018

DRAFT

5

B. Notational Conventions
For more convenience, we denote a rate-pair (R1 , R2 ) by (R1 , R2 , R3 ), where R3 = R1 + R2 . For a
(X1 , X2 , Y, Q) MAC we use the following notational conventions.
IL1 = IL (X1 → Y ||X2 )

(6)

IL2 = IL (X2 → Y ||X1 )

(7)

IL3 = IL (X1 X2 → Y )

(8)

The Kullback–Leibler divergence for the MAC with transition probability matrix Q is defined as
X
Q(y|x1 , x2 )
DQ (x1 , x2 ||z1 , z2 ) =
,
Q(y|x1 , x2 ) log2
Q(y|z1 , z2 )
y∈Y

where (x1 , x2 ), (z1 , z2 ) ∈ X1 × X2 . For notational conventions we denote
D1 (x1 , x2 ||z1 , z2 ) = DQ (x1 , x2 ||z1 , x2 )
D2 (x1 , x2 ||z1 , z2 ) = DQ (x1 , x2 ||x1 , z2 )
D3 (x1 , x2 ||z1 , z2 ) = DQ (x1 , x2 ||z1 , z2 ).

III. A L OWER -B OUND

FOR THE

R ELIABILITY F UNCTION

We build upon Yamamoto-Itoh transmission scheme for p.t.p. channel coding with feedback [7]. The
scheme sends the messages W1 , W2 through blocks of length n. The transmission process is performed
in two stages: 1) The “data transmission” stage taking up to n(1− γ) channel uses, 2) The “confirmation”
stage taking up to nγ channel uses, where γ is a design parameter, and takes values from [0, 1].
Stage 1: For the first stage, we use any coding scheme that achieves the feedback-capacity of the
MAC. The length of this coding scheme is at most n(1 − γ). Let Ŵ1 , Ŵ2 denote the decoder’s estimation
of the messages at the end of the first stage. Define the following random variables:
Hi = 1{Ŵi 6= Wi },

i = 1, 2.

Note that Ŵi is also known at each of the encoders. Therefore, at the end of the first stage, transmitter
i has access to Wi , Ŵ1 , Ŵ2 , and Hi , where i = 1, 2.

Stage 2: The objective of the second stage is to inform the receiver whether the hypothesis Θ0 :
(Ŵ1 , Ŵ2 ) = (W1 , W2 ) or Θ1 : (Ŵ1 , Ŵ2 ) 6= (W1 , W2 ) is correct. For this purpose, each transmitter

employs a code of size two and length γn. Denote the codewords of such code by two pairs of sequences
(x1 (0), x2 (0)) and (x1 (1), x2 (1)) with length γn, and with elements chosen from X1 × X2 . We select

these four sequences in a way that they have a joint-type Pn , where Pn is a design parameter. During
this stage, Transmitter 1 sends x1 (H1 ), and Transmitter 2 sends x2 (H2 ).

January 25, 2018

DRAFT

6

Decoding: Upon receiving the channel output, the receiver estimates H1 , H2 . Denote this estimation
by Ĥ1 , Ĥ2 . Using the values of these random variables, the decoder determines which of the two
hypotheses was correct. If (Ĥ1 , Ĥ2 ) = (0, 0), then the hypothesis Θ̂ = Θ0 is declared. Otherwise,
Θ̂ = Θ1 is declared. Because of the feedback, Θ̂ is also available at each encoders. If Θ̂ = Θ0 , then

transmission stops and a new data packet is transmitted at the next block. Otherwise, the message is
transmitted again at the next block. The process continues until Θ̂ = Θ0 occurs.
Theorem 1. The following is a lower-bound for the reliability function of any discrete memoryless MAC:
P
λi Ri
El (R1 , R2 ) =
min (1 − i
)Dl ,
(9)
λ1 ,λ2 ,λ3 ≥0
Cλ
λ1 +λ2 +λ3 =1

where,
Dl ,

min E [Di (X1 , X2 ||Z1 , Z2 )] ,

sup

PX1 X2 Z1 Z2 i=1,2,3

(10)

and the supremum is taken over all probability distributions PX1 X2 Z1 Z2 defined over X1 × X2 × X1 × X2 .
Proof. The proof is given in Appendix A.
Note that the confirmation stage in our proposed scheme can be formulated as a decentralized binary
hypothesis problem. This problem is the counterpart to the sequential binary hypothesis testing problem
identified in [6] for the ptp channel. Note also that the encoding functions used for this stage are chosen
randomly from all function-pairs ei : {0, 1} → Xi , i = 1, 2 according to a joint type Pn .
IV. A N U PPER - BOUND

FOR THE

R ELIABILITY F UNCTION

In this part of the paper, we establish an upper-bound for the reliability function of any discrete
memoryless MAC. For i = 1, 2, 3, define
Di =

max Di (x1 , x2 ||z1 , z2 ).

(11)

x1 ,z1 ∈X1 ,
x2 ,z2 ∈X2

Theorem 2 (Upper-bound). For any (N, M1 , M2 ) VLC with probability of error Pe , there exist δ > 0
(as a function of Pe , M1 , M2 ) such that the following is an upper-bound for the reliability function of
this VLC
Eu (R1 , R2 ) =

min

λ1 ,λ2 ,λ3 ≥0
λ1 +λ2 +λ3 =1

1−

P3

i=1 λi Ri
Cλ

!

Du + δ

(12)

where Du = min{D1 , D2 }, and δ is a function such that
lim

lim

Pe →0 M1 M2 →∞

January 25, 2018

δ(Pe , M1 M2 ) = 0

DRAFT

7

Before providing the proof, we point out a few remarks on Eu (R1 , R2 ) and the lower bound El (R1 , R2 )
defined in Theorem 1.
Note that El and Eu are different in the constants Du and Dl . More precisely, we have

Eu
El

≈

Du
Dl .

Furthermore, we can rewrite the lower bound and the upper bound as in (2). For that, suppose (R1 , R2 )
is a point inside the capacity region C . Consider the intersection of the boundary of the capacity region
and the line passing (R1 , R2 ) and the origin. Note that the point of intersection depends on (R1 , R2 )
through θR which is the angle of (R1 , R2 ) in polar coordinates. Denote this point by C(θR ). Therefore,
with this notation, we can rewrite El and Eu as a function of C(θR ) as it is done in (2).
We can show that the lower bound and the upper bound are tight for a class of MACs. Here, we
provide an example of such channels.
Example 1. Consider a MAC with input alphabets X1 = X2 = {0, 1, 2}, and output alphabet Y =
{0, 1, 2}. The transition probability of the channel is described by the following relation:
Y = X1 ⊕3 X2 ⊕3 Np ,

where the additions are modulo-3 addition, and Np is a random variable with P (Np = 1) = P (Np =
2) = p, and P (Np = 0) = 1 − 2p, where 0 ≤ p ≤ 1/2. It can be shown that for this channel
Dl = Du = (1 − 3p) log

1 − 2p
.
p

The argument in the above example can be extended to m-ary additive MACs for m > 2 where the
transition probability of the channel is described by
Y = X1 ⊕m X2 ⊕m Np ,

where all the random variables take values from Zm , and Np is a random variable with P (Np = i) = p
for any i ∈ Zm , i 6= 0 and P (Np = 0) = 1 − (m − 1)p. It can be shown that for this channel
Dl = Du = (1 − mp) log

1 − (m − 1)p
.
p

However, the error exponent bounds are not tight for the case of m = 2. These bounds are given in
the following example.
Example 2. Consider a binary additive MAC described by
Y = X1 ⊕2 X2 ⊕2 Np ,

where the inputs and output alphabets are binary, and P (Np = 1) = p, P (Np = 0) = 1 − p. In this setup
Du = (1 − 2p) log

January 25, 2018

1−p
p ,

where as Dl = 32 (1 − 2p) log

1−p
p

DRAFT

8

A. Proof of the Upper-Bound
In this part of the paper, we provide a series of Lemmas that are used to prove the Theorem. The
proof is given in Appendix D. Define the following random processes.
Ht1 , H(W1 | FW2 × Ft )
Ht2 , H(W2 | FW1 × Ft )
Ht3 , H(W1 , W2 | Ft ),

Lemma 1. For a (M1 , M2 , N )-VLC with probability of error Pe the following inequality holds
E[HTi ] ≤ hb (Pe ) + Pe log2 (M1 M2 − 1),

for

i = 1, 2, 3.

Proof. The proof follows from Fano’s Lemma as in [2].
In the next two lemmas we provide bounds on the rate of decrease of the entropies Ht1 , Ht2 , Ht3 .
Lemma 2. Given a (M1 , M2 , N )-VLC, there exists a probability distribution PX1L X2L Y L that factors as
in (5) such that the following inequalities hold almost surely for 1 ≤ t ≤ L
1
E[Ht+1
− Ht1 |FW2 × Ft ] ≥ −IL1 ,
2
E[Ht+1
− Ht2 |FW1 × Ft ] ≥ −IL2 ,
3
− Ht3 |Ft ] ≥ −IL3 .
E[Ht+1

where i = 1, 2, 3, and ILi is defined as in (6)-(8).
Proof. The proof is given in Appendix B.
Lemma 3. There exists ǫ > 0 such that, if Hti ≤ ǫ, then
1
E[log Ht+1
− log Ht1 |FW2 × Ft ] ≥ −(D1 + ǫ),
2
E[log Ht+1
− log Ht2 |FW1 × Ft ] ≥ −(D2 + ǫ),
3
E[log Ht+1
− log Ht3 |Ft ] ≥ −(D3 + ǫ)

holds almost surely, where Di , i = 1, 2, 3 are defined in (11).
Proof. The proof is given in Appendix C.
We need the following lemma to proceed. The lemma is a result of Lemma 4 in [2], and we omit its
proof.

January 25, 2018

DRAFT

9

Lemma 4. There exists a constant K > 0 such that for any t ≥ 1 and i = 1, 2, 3, the following inequality
holds almost surely w.r.t FW1 × FW2 × Ft
i
log Hti − log Ht+1
≤ K.

We can show that the constant K in the lemma is
K=

max

max

j,l∈[1:M1 ] y∈Y
k,m∈[1:M2 ]

Q̂j,k (y)
Q̂l,m (y)

.

(i)

Lemma 5. For i = 1, 2, 3, define random process {Zt }t≥1 as

 i


Ht − ǫ
log Hti − log ǫ
(i)
i
i
+
t
+
f
(log
H
−
log
ǫ)
1{Hti ≤ǫ}
Zt =
+
+
t
1
i
{Ht ≥ǫ}
t
Di
ILi
where the function fi is defined as fi (y) =

1−e−µi y
Di µi .

(13)
(i)

Then, there exist µi > 0 such that Zt

is a

submartingale w.r.t FW1 × FW2 × Ft .
Outline of the proof: Suppose W2 = m for some m ∈ [1 : M2 ]. Given this event and using the
(i)

same argument as in the proof of Theorem 1 in [2] we can show that Zt |W2 = m is a submartingale
for all m. More precisely, the inequality
(i)

(i)

E{Zt − Zt+1 |FW1 × FW2 } ≤ 0,
holds almost surely w.r.t FW1 × FW2 . Taking the expectation of the both sides in the above inequality
gives
(i)

(i)

E{Zt − Zt+1 } ≤ 0,
(i)

Thus, Zt

∀t ≥ 0, i = 1, 2, 3.

is a submartingale for i = 1, 2, 3 and w.r.t FW1 × FW2 × Ft .

Corollary 1. Suppose α1 , α2 , α3 are non-negative numbers such that α1 + α2 + α3 = 1. Define Zt =
(1)

α1 Zt

(2)

+ α2 Zt

(3)

+ α3 Zt . Then, Zt is a submartingale w.r.t FW1 × FW2 × Ft .

The proof of Theorem 2 follows from the above Corollary and is provided in Appendix D.
V. C ONCLUSION
We derive a lower and upper bound on the reliability function of discrete memoryless MAC with
noiseless feedback and variable-length codes. For the lower bound, we adapt Yamamoto and Itoh’s coding
scheme consisting of a data and a confirmation phase. For the upper bound, we adopt the proof techniques
of Burnashev for the reliability function of the point-to-point case. The two bounds have the same shape
with the difference being the constants at zero rate. We identify a new, decentralized sequential binary

January 25, 2018

DRAFT

10

hypothesis testing problem that relates to the second phase of the achievable scheme and the log-drift
of the entropies in the upper bound. This is the counterpart to the sequential binary hypothesis testing
problem identified in [6] for the ptp channel. We demonstrate how for symmetric channels the two bounds
coincide.
A PPENDIX A
P ROOF

OF

T HEOREM 1

Proof. At each block a re-transmission occurs with probability q , an error occurs with probability Peb
and a correct decoding process happens with probability 1 − q − Peb . The probability of a re-transmission
at each block is
q = P (Θ̂ = Θ1 ).

The probability of error at each block is
Peb = P (Θ1 )P (Θ̂ = Θ0 |Θ1 ).

Therefore, with this setting the total probability of error for the transmission of a message is
∞
X
Peb
Pe =
q k Peb =
.
1−q

(14)

k=0

The number of blocks required to complete the transmission of one message is a geometric random

variable with probability of success 1 − q . Thus, the expected number of blocks for transmission of a
message is

1
1−q .

Next, we derive an upper-bound for q and Peb . For shorthand, denote H12 = (H1 , H2 ), Ĥ12 = (Ĥ1 , Ĥ2 ).
Then


Peb = P Ĥ12 = 00, H12 6= 00
X
=
P (H12 = a)P (Ĥ12 = 00|H12 = a).
a∈{01,10,11}

R2
R1
R2
R1
, 1−γ
). Suppose ( 1−γ
, 1−γ
) is inside
Note that the effective rates of this transmission scheme are ( 1−γ

the feedback-capacity region of the channel. Then, from the definition of the capacity region, there exist
a sequence ζn , n ≥ 1 with ζn → 0 such that after the first stage
P ((Ŵ1 , Ŵ2 ) 6= (W1 , W2 )) ≤ ζn .

Equivalently, the effective rates are inside the capacity region, if the following inequality holds for any
λi ≥ 0, i = 1, 2, 3:
1
(λ1 R1 + λ2 R2 + λ3 (R1 + R2 )) < Cλ ,
1−γ

January 25, 2018

(15)

DRAFT

11

where Cλ is given in Definition 4. Denote R3 = R1 + R2 and define
P
λi Ri
∗
γ =
min (1 − i
).
λ1 ,λ2 ,λ3 ≥0
Cλ

(16)

λ1 +λ2 +λ3 =1

Then, (15) implies that γ <

γ ∗.

The probability of error is therefore bounded by
Peb ≤

X

P (Ĥ12 = 00|H12 = a)

(17)

a∈{01,10,11}

Suppose (X1 (0), X1 (1), X2 (0), X2 (1)) are random variables with joint distribution Pn . Then for i, j ∈
{0, 1} define

h
i
D̄Pn (00||ij) = EPn DQ X1 (0), X2 (0)||X1 (i), X2 (j) .

From the description of the transmission scheme, the codewords for the confirmation stage are selected
with joint-type Pn . In addition, the decoding process is performed using ML decoding. Therefore, the
following bounds hold for a ∈ {01, 10, 11}:
P (Ĥ12 = 00|H12 = a) ≤ 2−nγ D̄Pn (00||a) .

Thus, from (17), the probability of error is upper bounded by
Peb ≤ 3 × 2−nγDl,n

(18)

Where Dl,n = maxPn mina∈{01,10,11} D̄Pn (00||a).
Next we derive an upper bound for q . We have
q = P (Θ̂ = Θ1 )
= P (Θ0 )P (Θ̂ = Θ1 |Θ0 ) + P (Θ1 )P (Θ̂ = Θ1 |Θ1 )
≤ P (Θ̂ = Θ1 |Θ0 ) + ζn ,

where the last inequality holds because of the following inequalities 1) P (Θ1 ) ≤ ζn , and 2) P (Θ0 ), P (Θ̂ =
Θ1 |Θ1 ) ≤ 1. Note that
P (Θ̂ = Θ1 |Θ0 ) =

X

P (Ĥ12 = a|H12 = 00)

X

2−nγ D̄Pn (a||00)

a∈{01,10,11}

≤

a∈{01,10,11}

≤ 3 × 2−nγ D̃l,n ,

January 25, 2018

DRAFT

12

where D̃l,n = mina∈{01,10,11} D̄Pn (a||00). Therefore, there exists a sequence {qn }n≥1 with qn → 0 such
that q < qn + ζn . Using this inequality and the inequality at (18), we derive the following upper-bound
for the total probability of error given in (14)
Pe ≤

3
1 − q n − ζn

2−nγDl,n .

Therefore, the error exponent is bounded from below as
γDl,n
− log2 Pe
≥ sup
+ ξn
E[T ]
(1 − qn − ζn )

where ξn =

1−qn −ζn
)
1 log2 (
3
n
1−qn −ζn .

Note that for any ǫ > 0 there exists large enough n such that qn + ζn <

ǫ, Dl,n > Dl − ǫ, ξn < ǫ. Set γ = γ ∗ − ǫ. Then
− log2 Pe
≥ γ ∗ Dl − σ(ǫ)
E[T ]

where σ is a function of ǫ such that limǫ→0 σ(ǫ) = 0. Finally, the proof is complete by replacing γ ∗
from (16).

A PPENDIX B
P ROOF

OF

L EMMA 2

Proof. Given Y t = y t , W1 = m1 , W2 = m2 , we obtain
1
E[Ht+1
− Ht1 |m2 , y t ]

= −I(W1 ; Yt+1 |m2 , y t )
t
= −I(W1 ; Yt+1 |m2 , xt+1
2 ,y )
t+1
t
t
= −H(Yt+1 |m2 , xt+1
2 , y ) + H(Yt+1 |m2 , x2 , W1 , y )
t
= −H(Yt+1 |m2 , xt+1
2 ,y )
t+1 t
+ H(Yt+1 |m2 , xt+1
2 , W1 , X1 , y )
(a)

t+1
t+1 t
t
= −H(Yt+1 |m2 , xt+1
2 , y ) + H(Yt+1 |x2 , X1 , y )

1
t
(m2 , xt+1
, −Jt+1
2 ,y )

January 25, 2018

(19)

DRAFT

13

where (a) follows because condition on the channel inputs X1,t+1 , X2,t+1 , the output Yt+1 is independent
1 (.) as in (19). Similarly for the case when i = 2
of W1 , W2 . We denote the right-hand side of (a) by Jt+1

the following lower-bound holds
2
E[Ht+1
− Ht2 |m1 , y t ]
t
t+1 t+1 t
= −H(Yt+1 |m1 , xt+1
1 , y ) + H(Yt+1 |X2 , x1 , y )
2
t
, −Jt+1
(m1 , xt+1
1 , y ).

(20)

Using a similar argument for the case when i = 3, we can show that the following inequality holds
3
E[Ht+1
− Ht3 |y t ] ≥ −I(X1t+1 , X2t+1 ; Yt+1 |y t )
3
, −Jt+1
(y t ).

(21)

1 , J2 , J3 .
Consider the quantities at the right-hand side of (19), (20) and (21), i.e., the functions Jt+1
t+1 t+1

The proof is complete using the following lemma.
1 , J 2 , J 3 ) is inside the feedback-capacity region C almost surely.
Lemma 6. The vector (Jt+1
t+1 t+1

Proof: We use the alternative representation for C which is given in Fact 1. For any non-negative
numbers λ1 , λ2 , λ3 , let
t+1 t
t+1 t
t+1 t
1
2
3
t
Jλ (m1 , m2 , xt+1
1 , x2 , y ) = λ1 Jt+1 (m2 , x2 , y ) + λ2 Jt+1 (m1 , x1 , y ) + λ3 Jt+1 (y )

Note that
t+1 t
Jλ (m1 ,m2 , xt+1
1 , x2 , y ) ≤

sup
PW

E{Jλ (W1 , W2 , X1t+1 , X2t+1 , Y t )},

(22)

t+1 t+1 t+1
X
Y
1 W2 X1
2

where the supremum is taken over all proability distributions such that PX1t+1 X2t+1 Y t+1 factors as in
(5). From the definition of Jλ , the expectation at the right-hand side of the above inequality equals
P
i
i E[λi Jt+1 ]. Each expectation inside the summation can be bounded as follows
1
E{Jt+1
(W2 , X2t+1 , Y t )} = H(Yt+1 |W2 , X2t+1 , Y t ) − H(Yt+1 |X2t+1 , X1t+1 , Y t )

≤ H(Yt+1 |X2t+1 , Y t ) − H(Yt+1 |X2t+1 , X1t+1 , Y t )
= I(X1,t+1 ; Yt+1 |X2t+1 Y t )

Similarly,
2
E{Jt+1
(W1 , X1t+1 , Y t )} ≤ I(X2,t+1 ; Yt+1 |X1t+1 Y t )
3
E{Jt+1
(Y t )} ≤ I(X1,t+1 , X2,t+1 ; Yt+1 |Y t )

January 25, 2018

DRAFT

14

Therefore, using the above bounds and the definition of Cλ , we have
E{Jλ (W1 , W2 , X1t+1 , X2t+1 , Y t )} ≤ Cλ
The lemma follows from the above inequality and (22).

A PPENDIX C
P ROOF

OF

L EMMA 3

Proof. We prove the first statement of the lemma. The second and the third statements follow by a similar
argument. Given Y t = y t , W2 = m, define the following quantities
fi|m = P (W1 = i|Y t = y t , W2 = m)
fi|m (yt+1 ) = P (W1 = i|Y t = y t , W2 = m, Yt+1 = yt+1 )
Qi,m (yt+1 ) = P (Yt+1 = yt+1 |W1 = i, W2 = m, Y t = y t ),

where i ∈ [1 : M1 ], yt+1 ∈ Y . Since Ht1 < ǫ, then there exist ǫ′ (as a function of ǫ) and an index
l ∈ [1 : M1 ] such that fl|m ≥ 1 − ǫ′ and fi|m ≤
fˆi|m =

ǫ′
M1 −1

for all i ∈ [1 : M1 ], i 6= l. Denote

fi|m
,
1 − fl|m

i 6= l.

Using the grouping axiom we have
Ht1 = H(W1 |W2 = m, y t ) = hb (fl|m ) + (1 − fl|m )H(X̂)

where X̂ is a random variable with probability distribution P (X̂ = i) = fˆi|m , i ∈ [1 : M1 ], i 6= l. Note
that
hb (fl|m ) ≈ −(1 − fl|m ) log(1 − fl|m).

Therefore,
Ht1 ≈ −(1 − fl|m)(log(1 − fl|m ) − H(X̂))
≈ (1 − fl|m) log(1 − fl|m )

(23)

where the last approximation is due to the fact that − log(1 − fl|m ) ≫ H(X̂). Next, we derive an
1 . Note that
approximation for Ht+1

fl|mQl,m (yt+1 )
fl|m (yt+1 ) = P
j fj|m Qj,m (yt+1 )

January 25, 2018

DRAFT

15

The denominator can be written as
fl|mQl,m (yt+1 ) + (1 − fl|m )

X

fˆj|mQj,m (yt+1 ).

j6=l

The above quantity is approximately equals to Ql,m (y). Therefore,
P
ˆ
j6=l fj|m Qj,m (yt+1 )
(1 − fl|m (yt+1 )) = (1 − fl|m ) P
j fj|m Qj,m (yt+1 )
P
ˆ
j6=l fj|m Qj,m (yt+1 )
≈ (1 − fl|m )
Ql,m (yt+1 )
This implies that fl|m (yt+1 ) ≈ 1. Therefore, using the same argument for Ht1 we have
1
Ht+1
≈ −(1 − fl|m(yt+1 ))(log(1 − fl|m (yt+1 ))

P
h
i
ˆ
j6=l fj|m Qj,m (yt+1 )
= −(1 − fl|m(yt+1 )) log(1 − fl|m ) + log(
)
Ql,m (yt+1 )
≈ −(1 − fl|m(yt+1 )) log(1 − fl|m ).

(24)

As a result of the approximations in (23) and (24), we obtain
1
(1 − fl|m(y)) log(1 − fl|m)
Ht+1
≈
1
(1 − fl|m ) log(1 − fl|m )
Ht
P
ˆ
j6=l fj|m Qj,m (y)
=
Ql,m (y)

Note that
P (Yt+1 = y|W2 = m, y t ) ≈ Ql,m (y)

Therefore,
H1
E{log t+1
|y t } ≈ E{log
Ht1

P

ˆ

j6=l fj|m Qj,m (Yt+1 )

}
Ql,m (Yt+1 )
P
ˆ
X
j6=l fj|m Qj,m (y)
=
Ql,m (y) log
Ql,m (y)
y
(a)

= −D(Ql,m ||

X

fˆj|mQj,m)

j6=l

(b)

≥−

X

fˆj|mD(Ql,m ||Qj,m )

j6=l

≥ − max D(Ql,m ||Qj,m )
j6=l

(c)

≥ −(D1 + ǫ)

where (a) is due to the definition of Kullback–Leibler divergence, (b) is due to the convexity of
Kullback–Leibler divergence, and (c) is due to the definition of D1 .

January 25, 2018

DRAFT

16

A PPENDIX D
P ROOF

T HEOREM 2

OF

Proof. Since {Zt } is a submartingale, then Z0 ≤ E[ZT ]. By the definition of {Zt } we have E[ZT ] =
P3
i
i
i=1 αi E[ZT ]. For any of processes {Zt },
 i

HT − ǫ
i
E[ZT ] = E
1{HTi ≥ǫ}
ILi



HTi
log HTi − log ǫ
+ fi (log
) 1{HTi ≤ǫ} + E[T ]
+E
Di + ǫ
ǫ


 i

(a)
log HTi − log ǫ
HT − ǫ
1
+
E
≤E
+ E[T ]
+
Di + ǫ
µi Di
ILi
=
(b)

≤

E[HTi ] − ǫ E[log HTi ] − log ǫ
1
+
+
+ E[T ]
i
Di + ǫ
µi Di
IL

E[HTi ] − ǫ log E[HTi ] − log ǫ
1
+
+ E[T ]
+
i
Di + ǫ
µi Di
IL

where (a) follows from the inequality fi (y) ≤

1
µi Di ,

(25)

and (b) follows by applying Jensen’s inequality for

the function log(x).
Define η(Pe ) = hb (Pe )+Pe log(M1 M2 ). Using Lemma 1, the right-hand side of (25) is upper bounded
as
≤

η(Pe ) − ǫ log(η(Pe )) − log ǫ
1
+
+
+ E[T ]
i
D
+
ǫ
µ
IL
i
i Di

η(Pe )
η(Pe ) − ǫ log Pe + log Pe − log ǫ
1
+
=
+
+ E[T ]
i
Di + ǫ
µi Di
IL
log Pe
≤
+ E[T ](1 + δi (Pe , M1 M2 , ǫ)),
Di + ǫ

(26)

where the function δi is defined as
δi (Pe , M1 M2 , ǫ) = k

η(Pe ) − ǫ
ILi log M(3)1 M2
R

+

N

Note that we use the equation E[T ] =

log M1 M2
R(3)
N

e)
log η(P
Pe − log ǫ

(Di + ǫ) log M(3)1 M2
RN

+

1
µi Di log M(3)1 M2
RN

k

in the definition of δi . Observe that limPe →0 limM1 M2 →∞ δi (Pe , M1 M2 , ǫ) =

0. Thus, from (26) and the definition of {Zt } we obtain

E[ZT ] ≤

3
X
i=1

≤

log Pe

αi
+ αi E[T ](1 + δi (Pe , ǫ, M1 , M2 ))
Di + ǫ
3

X
log Pe
δi (Pe , M1 M2 , ǫ)),
+ E[T ](1 +
Dmin

(27)

i=1

where Du ,

min{D̄P1 , D̄P2 , D̄P3 }.

Note that

Z0 =

3
X
i=1

January 25, 2018

αi

log Mi − ǫ
.
i
IN

DRAFT

17

Dividing by E[T ] gives
3

(i)

X R
ǫ
Z0
− i
αi N
=
i
E[T ]
IN
IN E[T ]
i=1
3
X

=

(i)

αi

i=1

Note that

Z0
E[T ]

≤

E[ZT ]
.
E[T ]

RN
ǫ
)
(1 −
i
log M1 M2
IN

Next, we multiply both sides of (27) by

Du
.
E[T ]

Therefore, using above equation

we get:
log Pe
−
≤ Du
E[T ]

3
X

!
3
(i)
X
RN
ǫ
αi i (1 −
δi (Pe , M1 M2 , ǫ),
1−
) + Du
log M1 M2
IN
i=1
i=1

Given any non-negative numbers λi , i = 1, 2, 3, that sum-up to 1, set
λi I i
αi = P3 N i .
i=1 λi IN

Thus, the following inequality holds:
log Pe
≤ Du
−
E[T ]
+ Du

1−

3
X
i=1

3
X

!
(i)
λi RN
ǫ
)
(1 −
P3
i
log M1 M2
i=1 λi IN

δi (Pe , M1 M2 , ǫ)

i=1

(a)

≤ Du

1−

P3

(i)

i=1 λi RN
Cλ

!

+ δ(Pe , M1 M2 , ǫ),

where (a) follows from Definition 4, and the function δ is defined as
"
#
3
(i)
X
ǫλi RN
δi (Pe , M1 M2 , ǫ) +
.
δ(Pe , M1 M2 , ǫ) = Du
log M1 M2
i=1

The theorem follows as the following condition is satisfied:
lim

lim

Pe →0 M1 M2 →∞

δ(Pe , M1 M2 , ǫ) = 0.

R EFERENCES
[1] C. E. Shannon. The zero error capacity of a noisy channel. IRE Trans. on Inform. Th., 2(3):8–19, 1956
[2] M. V. Burnashev, “Data transmission over a discrete channel with feedback. Random transmission time,” Problemy Peredachi
Informatsii, vol. 12, no. 4, pp. 10–30, Oct.-Dec. 1976.
[3] J. Schalkwijk and T. Kailath, “A coding scheme for additive noise channels with feedback–I: No bandwidth constraint,”
IEEE Trans. Inform. Theory, vol. 12, no. 2, pp. 172–182, Apr 1966.
[4] R. L. Dobrushin, “An asymptotic bound for the probability error of information transmission through a channel without
memory using the feedback,” Problemy Peredachi Informatsii, vol. 8, pp. 161–160, 1962.

January 25, 2018

DRAFT

18

[5] E. A. Haroutunian, “Lower bound for error probability in channels with feedback,” Problemy Peredachi Informatsii, vol.
13, pp. 36–44, 1977.
[6] P. Berlin, B. Nakiboglu, B. Rimoldi, and E. Telatar, “A simple converse of burnashev’s reliability function,” IEEE Trans.
Information Theory, vol. 55, no. 7, pp. 3074–3080, July 2009.
[7] H. Yamamoto and K. Itoh, “Asymptotic performance of a modified schalkwijk-barron scheme for channels with noiseless
feedback (corresp.),” IEEE Transactions on Information Theory, vol. 25, no. 6, pp. 729–733, Nov 1979.
[8] N. T. Gaarder and J. K. Wolf, “The capacity region of a multiple-access discrete memoryless channel can increase with
feedback,” IEEE Trans. Inf. Theory, vol. 21, no. 1, pp. 100–102, 1975.
[9] G. Kramer, Directed Information for channels with Feedback. PhD thesis, Swiss Federal Institute of Technology, Zurich,
1998.
[10] L. V. Truong and V. Y. F. Tan, ”Error exponent of the common-message broadcast channel with variable-length feedback,”
2017 IEEE International Symposium on Information Theory (ISIT), Aachen, 2017, pp. 186-190.
[11] M. Heidari, F. Shirani and S. S. Pradhan, ”On the necessity of structured codes for communications over MAC with
feedback,” 2017 IEEE International Symposium on Information Theory (ISIT), Aachen, 2017, pp. 2298-2302.
[12] A. Nazari, S. S. Pradhan and A. Anastasopoulos, ”Error Exponent for Multiple Access Channels: Upper Bounds,” in IEEE
Transactions on Information Theory, vol. 61, no. 7, pp. 3605-3621, July 2015.
[13] R. Gallager, “A perspective on multi-access channels,” IEEE Trans. Information Theory, vol. 31, pp. 124–142, Mar. 1985.

January 25, 2018

DRAFT

