1

Common-Message Broadcast Channels with
Feedback in the Nonasymptotic Regime: Full
Feedback
arXiv:1706.07731v1 [cs.IT] 23 Jun 2017

Kasper Fløe Trillingsgaard, Student Member, IEEE, Wei Yang, Member, IEEE,
Giuseppe Durisi, Senior Member, IEEE, and Petar Popovski, Fellow, IEEE

Abstract
We investigate the maximum coding rate achievable on a two-user broadcast channel for the case where
a common message is transmitted with feedback using either fixed-blocklength codes or variable-length
codes. For the fixed-blocklength-code setup, we establish nonasymptotic converse and achievability bounds.
An asymptotic analysis of these bounds reveals that feedback improves the second-order term compared to
the no-feedback case. In particular, for a certain class of anti-symmetric broadcast channels, we show that
the dispersion is halved. For the variable-length-code setup, we demonstrate that the channel dispersion is
zero.

I. I NTRODUCTION
We consider a two-user common-message discrete-time memoryless broadcast channel (CMDMBC) with full feedback. When fixed-length codes are used, it is well-known that feedback does
The work of K. F. Trillingsgaard and P. Popovski was supported by the European Research Council (ERC Consolidator Grant Nr.
648382 WILLOW) within the Horizon 2020 Program. The work of G. Durisi was supported by the Swedish Research Council under
the grant 2016-03293. The material of this paper was presented in part at the 2017 IEEE International Symposium on Information
Theory [1].
K. F. Trillingsgaard and P. Popovski are with the Department of Eletronic Systems, Aalborg University, 9220, Aalborg Øst,
Denmark (e-mail: {kft,petarp}@es.aau.dk).
W. Yang is with the Department of Electrical Engineering, Princeton University, 08544, Princeton, USA (e-mail:
weiy@princeton.edu).
G. Durisi is with the Department of Electrical Engineering, Chalmers University of Technology, 41296, Gothenburg, Sweden
(e-mail: durisi@chalmers.se).
June 26, 2017

DRAFT

2

not improve capacity (as in the point-to-point setup), which is given by [2]
C = sup min I(P, Wk ).
P

k∈{1,2}

(1)

Here, W1 and W2 denote the component channels from the encoder to the two decoders and the
supremum is over all input distributions P . In this paper, we show that feedback can improve the
speed at which the maximum coding rate approaches capacity as the blocklength increases, and that
the improvement in the speed of convergence differs depending on whether one uses fixed-length
or variable-length codes.
For the no-feedback case, a CM-DMBC is equivalent to a compound channel, whose capacity
was characterized in [3], [4], and whose second-order coding rate (i.e., the second-order expansion
of the maximum coding rate in the limit of large blocklength) was found in [5]. Specifically, it
was proven in [5] that the second-order term in the asymptotic expansion of the logarithm of the
∗
maximum number of codewords Mno-f
(n, ) (here “no-f” stands for no feedback) in the limit of large

blocklength n and for a fixed average error probability  ∈ (0, 1) is in general a function of both the
dispersion [6, Eq. (222)] of the individual component channels and of the directional derivatives of
their mutual informations computed at the capacity-achieving input distribution (CAID).
In contrast, when feedback is present, the capacity of a CM-DMBC differs in general from that of
the compound channel [7]. This is because, for the compound channel with feedback, the transmitter
can send a training sequence and learn the state of the compound channel via the feedback link. It
can then adapt the input distribution to maximize the mutual information of that specific component
channel. This communication scheme cannot be used in the CM-DMBC because both decoders are
required to decode the message.
In the fixed-length-code setup, it is known that feedback does not improve the second-order
term for point-to-point discrete memoryless channels (DMCs) under certain symmetry conditions.
Specifically, it was shown in [8] that feedback does not improve the second-order term for weakly
input-symmetric DMCs. This result was extended to a broader class of DMCs in [9], where it
was shown that the same holds when the conditional information variance is constant for all input
symbols.
When variable-length codes are used, feedback is known to improve the speed at which the
maximum coding rate converges to capacity for the point-to-point setup. This was first demonstrated

June 26, 2017

DRAFT

3

by Burnashev [10], who proved that the error exponent with variable-length codes and full feedback
is given by
E(R) =

e1
C
e − R)
(C
e
C

(2)

e Here, C
e denotes the point-to-point capacity and C
e1 denotes the maximum
for all 0 < R < C.
relative entropy between conditional output distributions. Yamamoto and Itoh [11] proposed a twophase scheme that achieves the error exponent in (2) and Berlin et al. [12] provided an alternative
and simpler proof of the converse. For the CM-DMBC, Truong and Tan [13] established upper and
lower bounds on the error exponent using arguments similar to those of Burnashev, Yamamoto,
and Itoh. The bounds in [13] are shown to be tight for the case where the broadcast channel is
stochastically degraded.
For the regime of large average blocklength and fixed error probability, it was shown in [8] that
there is no square-root penalty in the asymptotic expansion of the maximum coding rate achievable
with variable-length codes for point-to-point DMCs, a result known as zero-dispersion. Moreover,
this fast convergence to capacity can be achieved using only stop feedback (also known as decision
feedback). Namely, the feedback link is used only to stop the transmitter. For CM-DMBCs, however,
stop feedback is not sufficient to achieve zero dispersion. Specifically, we recently showed that the
asymptotic expansion of the maximum coding rate with variable-length codes and stop feedback
contains a square-root penalty term, provided that some mild technical conditions are satisfied [14].
Contributions: We show that the presence of full feedback improves the second-order term in the
asymptotic expansions of the maximal coding rate for a general class of CM-DMBCs. Specifically,
we prove nonasymptotic achievability and converse bounds on the maximal number of codewords
Mf∗ (n, ) and Mvf∗ (n, ) (here “f” and “vf” stand for feedback and variable-length plus feedback,
respectively) that can be transmitted over a CM-DMBC with feedback and with relability 1 − 
using fixed-length codes and variable-length codes, respectively. Here, n denotes the blocklength
in the fixed-length setup whereas n stands for the average blocklength in the variable-length setup.
Through an asymptotic analysis of our bounds, we obtain the following results.
•

For the variable-length case, we show that full feedback yields zero dispersion. In light of our
previous result for stop-feedback codes in [14], this novel result shows that variable-length
codes combined with full feedback attain a second-order term that is strictly better than the
one of variable-length codes with stop-feedback.

June 26, 2017

DRAFT

4

•

For the fixed-length case, we show that the second-order term depends on the directional
derivatives of the mutual informations of the two component channels evaluated at the CAID
through a channel-dependent parameter that we shall denote by η ∈ (0, 1). Specifically, we
p
show that the second-order term is larger or equal to η 2 V1 + (1 − η)2 V2 Q−1 (2) (here,  <
1/2), where V1 and V2 denote the conditional information variances of the two component
channels evaluated at P ∗ . Furthermore, if the weighted sum of the conditional information
variances given a specific input symbol x takes the same value for all x, the upper bound
p
η 2 V1 + (1 − η)2 V2 Q−1 (2) is tight. For CM-DMBCs satisfying V1 = V2 and a certain
“antisymmetric property” (which will be made precise in Definition 3 on page 13), the parameter
p
η is equal to 1/2 and the second-order term simplifies to V1 /2Q−1 (2), thereby demonstrating
that, in this case, full feedback halves the dispersion compared to the no-feedback case.

The intuition behind our results is as follows. Feedback allows the encoder to compute the
accumulated information density at both decoders and to adapt the input distribution accordingly.
Specifically, the encoder makes small adjustments to the input distribution in order to favor the
decoder with the smallest information density and to drive both information densities close to their
arithmetic mean.
The problem of computing the maximum coding rate when fixed-length codes are used then
becomes roughly equivalent to the one of computing the -quantile of the arithmetic mean of
the two information densities. The desired result follows because the arithmetic mean of the two
information densities has variance V1 /2 when V1 = V2 . Hence, the dispersion is halved. Furthermore,
the improvement from Q−1 () to Q−1 (2) is achieved as follows: if the arithmetic mean of the
information densities is below a suitably chosen threshold shortly before the end of the transmission,
the encoder changes the input distribution to either the CAID of W1 or to the one of W2 . In this
way, it can ensure that at least one of the two decoders is successful with high probability.
When variable-length codes are used, each decoder attempts decoding as soon as the information
density at that decoder exceeds a certain threshold. Since the information densities at both decoders
are driven towards their arithmetic mean using the above mentioned feedback scheme, both decoders
attempt decoding at approximately the same time. This means that the stochastic overshoot of the
arithmetic mean of the two information densities that results in the square-root penalty when
fixed-length codes are used can be virtually eliminated by using variable-length codes. Hence, the
dispersion is zero.
June 26, 2017

DRAFT

5

Organization: In Section II, we introduce the system model. Our nonasymptotic bounds and
asymptotic expansions for fixed-length codes with feedback and variable-length codes with feedback
are presented in Section III and Section IV, respectively. Section V concludes the paper.
Notation: We denote vectors by boldface letters; their entries are denoted by roman letters.
Upper case, lower case, and calligraphic letters denote random variables (RVs), deterministic
quantities, and sets, respectively. The cardinality of a set is denoted by | · |. The inner product
between two vectors x and y is denoted by hx, yi, and the l1 -norm and the l2 -norm are denoted by
k·k1 and k·k2 , respectively. The vectors 0d and 1d denote a d-dimensional column vectors whose
entries are all zero and all one, respectively. We let N, Z, Z+ , R, and R+ denote the set of natural
numbers, the set of integers, the set of nonnegative integers, the set of real numbers, and the set of
nonnegative real numbers, respectively. We also denote by Rd0 , the set of d-dimensional real vectors
whose entries sum to zero. We let c denote an arbitrary positive constant whose value may change
at each occurrence and | · |+ denotes max{0, ·}. Furthermore, we denote the base e logarithm by
log(·). Throughout the paper, the index k is used to designate one of the two decoders. Hence,
it always belongs to the set {1, 2}, although this is sometimes not explicitly mentioned. We also
set k̄ = 3 − k. For a probability distribution P , we let P n be the joint probability distribution of
the vector [X1 , . . . , Xn ], whose entries {Xi } are independently and identically distributed (i.i.d.)
according to P . We let E[·] and Var[·] denote the expectation and the variance, respectively. For
a probability distribution Q, we denote the expectation with respect to Q by EQ [·]. For a RV X
with probability distribution P on X and a RV Y which is the output of a channel transition matrix
W : X 7→ Y, we let P W (·) denote the induced output distribution on Y; furthermore, we denote
the joint probability distribution of (X, Y ) by P × W . Given two probability distributions P and
Q on a common measurable space, we define, for every α ∈ (0, 1), the Neyman-Pearson function
β1−α (P, Q) as the minimum type-II error probability of a binary hypothesis test between P and Q
subject to the constraint that the type-I error probability does not exceed α. Finally, for two functions
f (·) and g(·), the notation f (x) = O(g(x)), as x → ∞, means that limx→∞ |f (x)/g(x)| ≤ ∞ and
f (x) = o(g(x)), as x → ∞, means that limx→∞ |f (x)/g(x)| = 0.

June 26, 2017

DRAFT

6

II. S YSTEM M ODEL
We consider a CM-DMBC with input alphabet X and output alphabets Y1 = Y2 = Y. We assume
that the channel outputs at any given time i are conditionally independent given the input, namely
W (y1,i , y2,i |xi ) , W1 (y1,i |xi )W2 (y2,i |xi ).

(3)

The capacity of the CM-DMBC is given in (1). We shall assume that it is achieved by P ∗ and
that this CAID is unique. We denote the capacities of the two component channels by C1 and C2 ,
respectively.
For every input distribution P and every n ∈ N, we denote the information density between the
vectors xn and ykn as
ıP,Wk (x

n

; ykn )

,

n
X
i=1

log

Wk (yk,i |xi )
.
P Wk (yk,i )

(4)

Furthermore, we let
Ik (P ) , EP ×Wk [ıP,Wk (X; Yk )]

(5)

Vk (P ) , EP [VarWk [ıP,Wk (X; Yk )|X]]

(6)

be the mutual information and

be the conditional information variance. Finally, we let Vk , Vk (P ∗ ) and we let h∇Ik , vi denote the
|X |

directional derivative of the mutual information Ik (·) along the direction v ∈ R0 at the point P ∗
X
h∇Ik , vi ,
vx D(Wk (·|x)||PY∗k ).
(7)
x∈X

Here, D(·||·) denotes the relative entropy, PY∗k = P ∗ Wk (·) is the capacity-achieving output distribution (CAOD). Without loss of generality, we have also assumed in (7) that X = {1, . . . , N } where
N = |X |.
Besides (3) and the uniqueness of P ∗ , we also assume that the channel laws satisfy the following
conditions
1) P ∗ (x) > 0 for all x ∈ X .
2) Vk > 0 for k ∈ {1, 2}
3) Ck > C for k ∈ {1, 2}.
The following lemma provides a relation between h∇I1 , ·i and h∇I2 , ·i that will be important in
the asymptotic analyses of our converse and achievability bounds.
June 26, 2017

DRAFT

7
|X |

Lemma 1: There exists a unique η ∈ (0, 1) such that for all v ∈ R0
η h∇I1 , vi + (1 − η) h∇I2 , vi = 0.

(8)

Proof: Let ∇k ∈ R|X |−1 be the gradient of ∇Ik , [v̄, −h1|X |−1 , v̄i] with respect to v̄ ∈ R|X |−1 .
Note that the concavity of the mutual information and the assumption Ck > C imply that ∇k cannot
be the zero vector. Since P ∗ maximizes mink I(P, Wk ), it follows that h∇1 , v̄ih∇2 , v̄i ≤ 0 for all
v̄. As a result, we have that
∇1
∇1

+
2

∇2
∇2

= 0|X |−1 .

(9)

= w 6= 0|X |−1 .

(10)

2

Indeed, assume that
∇1
∇1

+
2

∇2
∇2

2

Then, it follows from (10) and the Cauchy-Schwarz inequality that
h∇1 , wi = ∇1

+
2

h∇1 , ∇2 i
≥0
∇2 2

(11)

and similarly that h∇2 , wi ≥ 0. Here, the inequalities hold with equality if and only if (9) holds,
i.e., when ∇1 and ∇2 are linearly dependent and point in opposite directions. Hence, since w 6=
0|X |−1 , we conclude that h∇1 , wi > 0 and h∇2 , wi > 0. But this contradicts the assumption that
h∇1 , wih∇2 , wi ≤ 0. Now, (8) follows from (9) with η = (1/ ∇1 2 )/(1/ ∇1

2

+ 1/ ∇2 2 ).

Uniqueness of η follows trivially.
We use (8) to define the channel-dependent constant η ∈ (0, 1) as follows:
η=

h∇I2 , vi
.
h∇I2 , vi − h∇I1 , vi

(12)

|X |

Here, v is an arbitrary vector in R0 satisfying h∇I1 , vi =
6 0. Note that by Lemma 1, the value of η
does not depend on v. For notational convenience, we set η1 = η and η2 = 1 − η in the remainder
of the paper.
Next, we define the notions of fixed-length feedback (FLF) codes and variable-length feedback
(VLF) codes.
Definition 1: An (n, M, )-FLF code for the CM-DMBC consists of:
1) n encoding functions fi : M × Y i−1 × Y i−1 7→ X , i = 1, . . . , n (possibly randomized),
mapping the message J, drawn uniformly from M , {1, . . . , M }, and the past channel
outputs Y1i−1 , Y2i−1 to the channel input Xi = fi (J, Y1i−1 , Y2i−1 ).
June 26, 2017

DRAFT

8

2) Two decoders gk : Y n 7→ M satisfying


P gk (Ykn ) 6= J ≤ ,

k ∈ {1, 2}.

(13)

The maximum code size achievable with blocklength n and average error probability not exceeding
 is denoted by
Mf∗ (n, ) , max{M : ∃(n, M, )-FLF code} .

(14)

Definition 2: An (n, M, )-VLF code for the CM-DMBC consists of:
1) A RV U ∈ U with |U| ≤ 3, which is known at both the encoder and the decoders.
2) A sequence of encoding functions fi : U × M × Y n−1 × Y n−1 7→ X , each one mapping the
message J, drawn uniformly at random from the set M, the past channel outputs Y1i−1 , Y2i−1 ,
and the auxiliary RV U to the channel input Xn = fn (U, J, Y1n−1 , Y2n−1 ).
3) Two nonnegative integer-valued RVs τ1 and τ2 that are stopping times with respect to the
filtrations F1,n , σ(U, Y1n ) and F2,n , σ(U, Y2n ), respectively, and satisfy


E max τk ≤ n.
k

4) A sequence of decoders gk,n : U × Y n 7→ M satisfying


P J 6= gk,τk (U, Ykτk ) ≤ ,
k ∈ {1, 2}.

(15)

(16)

The maximum code size achievable with average blocklength n and average error probability not
exceeding  is denoted by
Mvf∗ (n, ) , max{M : ∃(n, M, )-VLF code} .

(17)

We depict our system model in Fig. 1.
III. F IXED -L ENGTH F EEDBACK C ODES
In this section, we present nonasymptotic achievability and converse bounds on Mf∗ (n, ) for FLF
codes. These bounds are then analyzed in the large-n regime. Under some technical assumptions,
the asymptotic expansions of our bounds are shown to match up to the second order. We then
introduce a class of antisymmetric CM-DMBCs for which the second-order term in the asymptotic
expansion of Mf∗ (n, ) takes on a simple expression, which allows for an insightful comparison
with the no-feedback case.
June 26, 2017

DRAFT

9

Fig. 1. The system model considered in this paper. Here, D stands for a delay of one unit of time.

A. Nonasymptotic bounds
We first state a Verdú-Han-type converse bound for FLF codes.
Theorem 2: Every (n, M, )-FLF code for the CM-DMBC satisfies1
"
#
n


X X
1
ηk
ıP ∗ ,Wk Yk,i ; fi (J, Y1i−1 , Y2i−1 ) ≤ log M − λ − e−λ
 ≥ PJ,Y1n ,Y2n
2
i=1
k

(18)

for every λ > 0, where
PJ,Y1n ,Y2n (j, y1n , y2n )

n
1 Y
W1 (y1,i |fi (j, y1i−1 , y2i−1 ))W2 (y2,i |fi (j, y1i−1 , y2i−1 )).
,
M i=1

(19)

Proof: Fix an (n, M, )-FLF code with encoding functions {fi } and decoding functions {gk }.
Define the following auxiliary probability distributions on M × Y n × Y n
(k)
QJ,Y1n ,Y2n (j, y1n , y2n )

n
1 Y
,
W (y |fi (j, y1i−1 , y2i−1 ))P ∗ Wk (yk,i ).
M i=1 k̄ k̄,i

(20)

Recall that k̄ = 1 when k = 2 and k̄ = 2 when k = 1. When (J, Y1n , Y2n ) ∼ PJ,Y1n ,Y2n , both decoders
(k)

have an average error probability not exceeding  because of (13). When (J, Y1n , Y2n ) ∼ QJ,Y1n ,Y2n ,
the average error probability at decoder k is 1 − 1/M . The meta-converse bound in [6, Th. 27] and
the inequality [6, Eq. (106)] then imply that
1
(k)
≥ β1− (PJ,Y1n ,Y2n , QJ,Y1n ,Y2n )
M
"
#
!
dPJ,Y1n ,Y2n
1
≥
PJ,Y1n ,Y2n log (k)
≤ log γ − 
γ
dQJ,Y n ,Y n
1

1

(21)
(22)

2

Recall that η1 = η and η2 = 1 − η, where η was defined in (12).

June 26, 2017

DRAFT

10

for every γ > 0 and k ∈ {1, 2}. Let
Ak (j, y1n , y2n )

,

n
X

ıP ∗ ,Wk (fi (j, y1i−1 , y2i−1 ); yk,i ).

(23)

i=1

By setting log γ , log M − λ and by using (19) and (20) in (22), we obtain
h
i
 ≥ max PJ,Y1n ,Y2n Ak (J, Y1n , Y2n ) ≤ log M − λ − e−λ .
k

(24)

We obtain the desired result (18) from (24) through the following chain of inequalities:
h
i
1X
n
n
PJ,Y1n ,Y2n Ak (J, Y1 , Y2 ) ≤ log M − λ − e−λ
(25)
≥
2 k
h[ n
oi
1
n
n
Ak (J, Y1 , Y2 ) ≤ log M − λ − e−λ
(26)
≥ PJ,Y1n ,Y2n
2
k
hX
i
1
ηk Ak (J, Y1n , Y2n ) ≤ log M − λ − e−λ .
(27)
≥ PJ,Y1n ,Y2n
2
k
P
Here, (25) follows because maxk ak ≥ 12 k ak for every pair (a1 , a2 ) ∈ R2+ , (26) follows from the
P
union bound, and (27) follows because k ηk bk ≤ ζ imply that either b1 ≤ ζ or b2 ≤ ζ for every
triple (b1 , b2 , ζ) ∈ R3 .
Before stating our achievability bound, we need to introduce some notation. We let S ≥ 2, L,
and m denote arbitrary integers. We also let S , {1, . . . , S} and L , {1, . . . , L}. Furthermore, we
index each element x of X SLm as follows:
x = (x1 (1), . . . , x1 (S), . . . . . . , xL (1), . . . , xL (S)).

(28)

Here, x` (s) = (x`,1 (s), . . . , x`,m (s)) ∈ X m . For a given vector b` ∈ S ` , we let x` (b` ) ,
(x1 (b1 ), . . . , x` (b` )). We use a similar notation for the elements in the set Y SLm . Finally, we define
the minimum error probability achievable on an CM-DMBC using fixed-length codes with no
feedback of blocklength nB and with S L codewords:
∗ (nB , S L ) , min{ : ∃(nB , S L , ) finite-length no-feedback code}.

(29)

We are now ready to state our achievability bound for FLF codes.
Theorem 3: Let P1 , . . . , PS be types of sequences in X m , let τ ∈ (0, ), let ζ > 0, and let {h` }L`=1
be arbitrary mappings from X (`−1)m × Y (`−1)m × Y (`−1)m to S. Then
log Mf∗ (Lm + nB ,  + ∗ (nB , S L ))
n
o


τ
≥ sup γ : min P ık (xL (B L ); YLk (B L )) ≤ γ <  − τ − e−ζ + log
k
2
− SL|X | log(1 + m) − L log S − ζ.
June 26, 2017

(30)
DRAFT

11

Here, x ∈ X SLm is an arbitrary element in the set
n
F , x ∈ X SLm : x` (s) has type Ps ,

∀s ∈ S, ∀` ∈ L}

(31)

and PY1 ,Y2 ,B L denotes the probability distribution of (Y1 , Y2 , B L ) on B × B × S L defined by
PY1 ,Y2 ,B L (y1 , y2 , bL )
,

L
Y

S Y
Y

`=1

s=1 k

!
Wkm (yk,` (s)|x` (s))

n 

o
`−1
`−1 `−1
× 1 h` x`−1 (b`−1 ), y`−1
(b
),
y
(b
)
=
b
`
1
2

(32)

for yk,` (b) ∈ Y m . Finally,
ık (x` (b` ); yk,` (b` )) ,

m
X

ıPb` ,Wk (x`,i (b` ); yk,`,i (b` ))

(33)

i=1

and ık (·; ·) in (30) is defined as follows:
ık (xL (bL ); yLk (bL )) ,

L
X

ık (x` (b` ); yk,` (b` )).

(34)

`=1

Sketch of the proof: Each codeword of length Lm is divided into L blocks of length m,
which are of constant composition. Within each block `, feedback is used to compute the index b` ,
which selects one out of the S available subcodewords (the vectors x` (b` ), b` = 1, . . . , S). We then
communicate the sequence bL to the decoders using a code with S L codewords of length nB . The
desired bound then follows by applying the achievability bound [5, Th. 3] for compound DMCs
without feedback. The term −SL|X | log(1 + m) in (30) represents the penalty due to the use of
constant composition codes. The details of the proof are given in Appendix A.
Remark 1: The achievability bound in Theorem 3 holds also under the more stringent error
probability constraint maxj∈M P[gk (Ykn ) 6= j|J = j] ≤ .
B. Asymptotic analysis
By analyzing Theorem 2 and Theorem 3 in the large-blocklength limit, we will next establish
asymptotic expansions for our converse and achievability bounds that match up to the second order
provided that condition (36) is satisfied. In particular, we show in the next theorem that in this case
the channel dispersion [6, Def. 1] is
V , η 2 V1 + (1 − η)2 V2 .
June 26, 2017

(35)
DRAFT

12

Theorem 4: Suppose that
η 2 Var[ıP ∗ ,W1 (x; Y1 )|X = x] + (1 − η)2 Var[ıP ∗ ,W2 (x; Y2 )|X = x] = V

(36)

for all x ∈ X , where V is defined in (35). Then, for every  ∈ (0, 1/2), we have
log Mf∗ (n, ) = nC −

√
nV Q−1 (2) + O(n1/3 log n).

(37)

Proof: See Appendix B for the proof of the converse part and Appendix C for the proof of the
achievability part.
Remark 2: The assumption  ∈ (0, 1/2) is crucial for (37) to hold. Indeed, when  > 1/2, one
can achieve log Mf∗ (n, ) = n mink Ck + o(n) by using a standard point-to-point fixed-length code
of rate R < mink Ck and codewords generated i.i.d. according to P1∗ (the CAID of W1 ) with
probability 1/2 and another code of rate R and codewords generated i.i.d. according to P2∗ (the
CAID of W2 ) with probability 1/2. This implies that the strong converse does not hold.
Remark 3: The assumption (36) is a multiuser analogue of the assumption in [9, Th. 2] under
which the authors of [9] show that feedback does not improve the second-order terms of point-topoint DMCs. If it does not hold, one can further improve the dispersion term by combining our
feedback scheme with the one proposed in [9].
Remark 4: If the error probability constraint (13) is replaced with the more stringent constraint
P[(g1 (Y1n ), g2 (Y2n )) 6= (J, J)] ≤ , then the asymptotic expansion in (38) continues to hold except
that Q−1 (2) needs to be replaced with Q−1 ().
Note that the asymptotic expansion in (37) is achievable independently on whether (36) holds.
Specifically, we have the following result.
When the assumption (36) is not satisfied, we do not know the precise second-order term in the
asymptotic expansion of the converse. Our achievability result, though, continues to hold.
Theorem 5: For every  ∈ (0, 1/2), we have
√
√
nC + O( n) = log Mf∗ (n, ) ≥ nC − nV Q−1 (2) + O(n1/3 log n).

(38)

Proof: See Appendix C.

June 26, 2017

DRAFT

13

C. Antisymmetric CM-DMBCs
We shall apply our results to the class of antisymmetric CM-DMBCs defined as follows.
Definition 3: A CM-DMBC is antisymmetric if |X | is even, Y can be decomposed in disjoint
sets Y 1 , . . . , Y m , and the channel transition matrices can be decomposed as follows:




p11 W 11 · · · p1r W 1r
p21 W 21 · · · p2r W 2r
W1 =
and W2 =
.
(39)
p21 W 21 · · · p2r W 2r
p11 W 11 · · · p1r W 1r
P
Here, ri=1 pki = 1 for k ∈ {1, 2} and {W 1i } and {W 2i } are weakly symmetric channel transition
matrices2 with dimensions |X2 | ×|Y i |. For notational convenience, we let W (1) , [p11 W 11 , · · · , p1r W 1r ]
and W (2) , [p21 W 21 , · · · , p2r W 2r ].
Remark 5: The antisymmetric Z-channel is an example of an antisymmetric CM-DMBC, where
m = 2, W 11 = W 12 = W 21 = W 22 = 1, 1 − p11 = p12 = q, and p21 = 1 − p22 = 0.
The following corollary of Theorem 4 and Theorem 5 shows that the dispersion is halved for
antisymmetric CM-DMBCs compared to the no-feedback case. This extends the result reported in
[1] to a broader class of channels.
Corollary 6: For every antisymmetric CM-DMBC satisfying mink Ck > C, we have
r
nV1 −1
∗
log Mf (n, ) = nC −
Q (2) + O(n1/3 log n),  ∈ (0, 1/2).
2

(40)

Proof: We need to show that, for every antisymmetric CM-DMBC, we have that η1 = η2 = 1/2,
that V1 = V2 , and that
Var[ıP ∗ ,W1 (x; Y1 ) + ıP ∗ ,W2 (x; Y2 )|X = x] = 2V1 ,

x ∈ X.

We first show that P ∗ is the uniform distribution on X . In the following, we let αP =

(41)
P|X |/2
x=1

P (x)

and αP = 1 − αP for every input distribution P on X . Note that

2

H(Y1 |X) = αP H(r1 ) + αP H(r2 )

(42)

H(Y2 |X) = αP H(r1 ) + αP H(r2 )

(43)

A channel transition matrix is weakly symmetric if the rows are permutations of each other and all column sums are equal. The

CAID and CAOD of a weakly symmetric channel are uniform [15, pp. 189–190].

June 26, 2017

DRAFT

14

where rk denotes the first row of Wk . Define


αP p11 + αP p21
αP p1r + αP p2r
P Y1 (y) =
1|Y 1 | , . . . ,
1|Y r | .
|Y 1 |
|Y r |

(44)

It follows that [15, Th. 2.6.4]
0 ≤ D(PY1 ||P Y1 ) =

r
X

(αP p1j + αP p2j ) log

j=1

|Y j |
− H(Y1 )
αP p1j + αP p2j

(45)

which implies
r
X
H(Y1 ) ≤
(αP p1j + αP p2j ) log
j=1

|Y j |
.
αP p1j + αP p2j

(46)

|Y j |
.
αP p1j + αP p2j

(47)

Similarly,
H(Y2 ) ≤

r
X
(αP p1j + αP p2j ) log
j=1

As a result of (42)–(43), (46)–(47), and because of symmetry, we have
1
min Ik (P ) ≤
k
2

!
2|Y j |
(p1j + p2j ) log
− H(r1 ) − H(r2 ) .
p
+
p
1j
2j
j=1

r
X

(48)

This upper bound holds with equality when P is uniform. Hence, we have shown that P ∗ is the
uniform distribution on X , and consequently, we also have that V1 = V2 , that PY∗1 = PY∗2 and that
(41) holds.
We next argue that η1 = η2 = 1/2. Define the permutation π of {1, . . . , |X |} as follows: π ,
|X |

[|X /2| + 1, . . . , |X |, 1, . . . , |X /2|]. We first show that for every v ∈ R0
X
h∇I1 , vπ i =
vπ (x)D(W1 (·|x)||PY∗1 )

(49)

x∈X

=

X

vπ (x)D(W2 (·|π(x))||PY∗2 )

(50)

v(x)D(W2 (·|x)||PY∗2 )

(51)

x∈X

=

X
x∈X

= h∇I2 , vi .

(52)

Here, vπ denotes the vector v whose entries are permuted according to π. In particular, since
π(π(x)) = x for all x ∈ X , (52) implies that
h∇I1 , v + vπ i = h∇I2 , v + vπ i .

June 26, 2017

(53)

DRAFT

15

1

1−

qk

qk
2

qk
1−

X
1−

3

1

qk

Yk

qk

2

qk

qk
4

1−

qk

Fig. 2. An antisymmetric CM-DMBC composed of two binary symmetric channels. This figure illustrates the component channel
Wk .

|X |

By the uniqueness of P ∗ and by (39), there cannot exist a vector v ∈ R0 such that h∇I1 , v + vπ i
and h∇I2 , v + vπ i are simultaneously positive or simultaneously negative, and hence h∇I1 , v + vπ i
|X |

must be equal to zero for all v ∈ R0 . Therefore, by using (52), we conclude that
0 = h∇I1 , v + vπ i = h∇I1 , vi + h∇I1 , vπ i = h∇I1 , vi + h∇I2 , vi .

(54)

Since η in (8) is unique, (54) implies that η1 = η2 = 1/2. The desired result is then established by
invoking Theorem 4 and Theorem 5.
D. A specific CM-DMBC
We shall next consider the antisymmetric CM-DMBC depicted in Fig. 2, which we shall use for
evaluating numerically the accuracy of the asymptotic expansion provided in Corollary 6. For this
specific class of antisymmetric CM-DMBC, we shall derive next an alternative achievability bound
that yields tighter numerical results for small values of n than the generic achievability bound in
Theorem 3. This bound, which is a random-coding union (RCU)-type of achievability bound, is
based on a minimum distance mismatched decoder.
Theorem 7: For the CM-DMBC depicted in Fig. 2, there exists an (n, M, )-FLF code satisfying
(
)
n
t  
X
X
n −n
≤
PZ (n) (t) min 1, (M − 1)
2
.
(55)
1
k
t=0
k=0

June 26, 2017

DRAFT

16

0.6
Rate, bits/ch. use

0.5

converse

Capacity C

normal approximation (feedback)

0.4
0.3

achieviability (RCU, feedback)

0.2
normal approximation (no feedback)

0.1
0
0

500

1000
Blocklength n

1500

2000

Fig. 3. Comparison between the RCU-type achievability bound in (55), the converse bound in (18), and the normal approximation
in (40) for the CM-DMBC depicted in Fig. 2 with q1 = 0.05, q2 = 0.10, and  = 10−3 . The normal approximation (feedback) is
the expression in (40) with the O(·) term omitted. The normal approximation (no feedback) is the expression in [5, Eq. (12)] with
√
the o( n) term omitted.

(n)

Here, PZ (n) denotes the probability mass function of the RV Z1

which is defined through the

1

following recursion
(0)

Zk , 0
(i)

(56)
(i−1)

Zk , Zk




 E1(i) if Z1(i−1) > Z2(i−1) or Z1(i−1) = Z2(i−1) and Z (i) = 0


+
 E (i) if Z (i−1) < Z (i−1) or Z (i−1) = Z (i−1) and Z (i) = 1
2
1
2
1
2
(i)

for i ∈ {1, . . . , n}, where Ek ∼ Bern(qk ) and Z

(i)

(57)

∼ Bern(1/2) are independent RVs.

Proof: See Appendix D.
Let W1 and W2 be as depicted in Fig. 2 with q1 = 0.05 and q2 = 0.10. This channel is an
antisymmetric CM-DMBC and, hence, it satisfies the conditions of Corollary 6. We plot the
achievability bound given in Theorem 7, the converse bound given in Theorem 2, and the first
two terms of the asymptotic expansion (normal approximation) in Corollary 6. We observe that the
normal approximation is an accurate proxy for the maximum coding rate for the considered range
June 26, 2017

DRAFT

17

of n. Note that the achievability bound in Theorem 7 is not capacity-achieving since it is based
on mismatched decoding. The plotted achievability bound is thus expected to be accurate only for
moderate values of n. The generic achievability bound in Theorem 3 is not plotted since it is not
accurate numerically for moderate values of n. This is because of the use of constant composition
codes and because the sequence B L needs to be communicated explicitly.
IV. VARIABLE -L ENGTH F EEDBACK C ODES
We first present a Fano-type converse bound and a nonasymptotic achievability bound for VLF
codes. We then show that these bounds imply that the second-order term in the asymptotic expansion
of log Mvf∗ (n, ) is zero.
A. Nonasymptotic bounds
Our converse result for VLF codes is based on Lemma 1 and on [10, Lem 1 and Lem 2].
Theorem 8: Every (n, M, )-VLF code with 0 ≤  ≤ 1 − 1/M satisfies
log M ≤

nC + h()
1−

(58)

where h(x) , −x log x − (1 − x) log(1 − x) is the binary entropy function.
Proof: See Appendix E.
Our nonasymptotic achievability bound for VLF codes leverages ideas similar to in Theorem 3
and in [8, Th. 3]. The achievable scheme consists of two phases: a fixed-length transmission phase
via an FLF code and a variable-length transmission phase via a variable-length stop-feedback code.
Theorem 9: Let P1 , . . . , PS be probability distributions on X , let γ ≥ 0 and 0 ≤ q ≤ 1 be
arbitrary scalars, and τmax be an arbitrary integer larger than Lm. The stopping times τk and τ̄k for
k ∈ {1, 2} are defined as follows:

τk , inf n ≥ Lm : Sk,n (X n , Ykn ; B L ) ≥ γ or n = τmax

τ̄k , inf n ≥ Lm : Sk,n (X̄ n , Ykn ; B L ) ≥ γ or n = τmax .

(59)
(60)

Here, we have defined for n ≥ Lm
Sk,n (x

n

, ykn ; bL )

,

L X
m
X

ıPb` ,Wk (xν(`,i) ; yk,ν(`,i) )

`=1 i=1
n
X

+

ıP ∗ ,Wk (xi ; yk,i )

(61)

i=Lm+1
June 26, 2017

DRAFT

18

where ν(`, i) , (` − 1)m + i, and the joint probability distribution of (X n , X̄ n , Y1n , Y2n , B L ) is

PX n ,X̄ n ,Y1n ,Y2n ,B L (xn , x̄n , y1n , y2n , bL )
!
Y
=
Wkn (ykn |xn )
k

×

L Y
m
Y

!
o
n
Pb` (xν(`,i) )Pb` (x̄ν(`,i) )1 b` = h` (x`−1 , y1`−1 , y2`−1 )

`=1 i=1
∗ n−Lm

× (P )

(xnLm+1 )(P ∗ )n−Lm (x̄nLm+1 ).

(62)

Then, for every positive integer M and nB , there exists an (n, M, )-VLF code with
 h
i

n ≤ (1 − q) E max τk + nB
k
n
o
∗
L
 ≤ q + (1 − q) (nB , S ) + max (1 − q)(M − 1)P[τk ≥ τ̄k ] .

(63)
(64)

k

Remark 6: Following steps similar to those in [8, Eqs. (111)-(118)], one can further upper-bound
 in (64) as follows:

 ≤ q + (1 − q) ∗ (nB , S L ) + exp(−γ) + max P[τk = τmax ] .

(65)

k

Here, we have treated the event {τk = τmax } as an error.
Remark 7: Compared to the nonasymptotic achievability bound for VLF codes for DMCs reported in [8], in our bounds, the stopping times τk and τ̄k are lower- and upper-bounded by Lm and
τmax , respectively. These bounds simplify the asymptotic analysis of the achievability bound.
Proof: See Appendix F.
B. Asymptotic analysis
The following result reveals that one can achieve zero dispersion by using VLF codes.
Theorem 10: For every  ∈ (0, 1), we have
log Mvf∗ (n, ) ≥

nC
+ O(n1/3 log n).
1−

(66)

Remark 8: We have previously shown in [14, Th. 4] that there is a square-root penalty in the
asymptotic expansion of the maximal coding rate when variable codes with stop-feedback are
employed. Theorem 10 shows that this square-root penalty vanishes when full feedback is present.
Proof: See Appendix G.
June 26, 2017

DRAFT

19

V. C ONCLUSION
In this paper, we investigated the maximal coding rate for the CM-DMBC with feedback. When
fixed-length codes are employed, we demonstrated that the second-order term is reduced by a factor
√
of more than 1/ 2 under mild technical conditions. Under an additional symmetry condition, we
also proved that the asymptotic expansions of the our converse and achievability bounds match
up to the second order. This improved second-order term is in contrast to the point-to-point setup,
where it is shown that the second-order term is unaltered under similar symmetry conditions [9].
We also found that the second-order term vanishes under certain mild technical conditions if we
allow the use of variable-length codes. This result together with the one previously reported in [16]
implies that zero-dispersion is achievable when feedback is available and variable-length codes are
used but that stop-feedback is not sufficient to attain it.
A PPENDIX A
P ROOF OF T HEOREM 3
We consider feedback schemes in which the encoders can be represented as follows: there exists
M vectors in X SLm , denoted by {x(1) , . . . , x(M ) }, such that
(j)

fi (j, Y1i−1 , Y2i−1 ) = x`(i),i−m(`(i)−1) (B`(i) )

(67)

for i ∈ {1, . . . , Lm}. Here, `(i) , di/me and
(`−1)m

B` , h` (X (`−1)m , Y1

(`−1)m

, Y2

)

(68)

where X (`−1)m denotes the sequence of channel inputs transmitted up to time (` − 1)m.
In the remainder of the proof, we shall use Yk,` to denote (Yk,(`−1)m+1 , . . . , Yk,`m ) and we let
Yk denote (Yk,1 , . . . , Yk,L ). The conditional probability distribution of (Y1 , Y2 , B L ) given that
X = x ∈ X SLm is then given by
PY1 ,Y2 ,B L |X (y1 , y2 , bL |x)
 n 
L Y
o

Y
m
=
Wk (yk,` |x` (b` )) 1 h` x`−1 (b`−1 ), y1`−1 , y2`−1 = b` .
`=1

(69)

k

Next, we shall apply the achievability bound for the compound channel with channel state information at the receiver reported in [5, Th. 3]. In particular, we let X SLm be the input alphabet,

June 26, 2017

DRAFT

20

B , Y Lm × S L be the output alphabets, and consider the compound channel with transition
probability
PYk ,B L |X (yk , bL |x)
 n 
L Y

o
X Y
m
,
Wk (yk,` |x` (b` )) 1 h` x`−1 (b`−1 ), y1`−1 , y2`−1 = b`
yk̄

=

∈Y Lm
L
Y

`=1

(70)

k

!
Wkm (yk,` |x` (b` )) PB L |X (bL |x).

(71)

`=1

Moreover, we set F as in (31) and take as auxiliary channel
QYk ,B L (yk , bL ) ,

L
1 Y
(Pb Wk )m (yk,` ).
S L `=1 `

(72)

It will turn out convenient to define also the following probability measure:
QX (x) ,

L Y
S
Y
(Ps )m (x` (s)).

(73)

`=1 s=1

Note that
X

QX (x)PYk ,B L |X (yk , bL |x)

x∈X SLm

≤

X
x∈X SLm

QX (x)

L
Y

Wkm (yk,` |x` (b` ))

(74)

`=1

L
Y

(Pb` Wk )m (yk,` )

(75)

= S QYk ,B L (yk , bL ).

(76)

=

`=1
L

We observe that this compound channnel is equivalent to a CM-DMBC with encoding functions
satisfying (67), provided that the decoders have knowledge about B L . We can readily provide both
decoders with knowledge of B L using a finite blocklength code with nB channel uses and an error
probability ∗ (nB , S L ) defined in (29) at the end of the transmission. Hence, we apply [5, Th. 3]
and conclude that
Mf∗ (Lm + nB ,  + ∗ (nB , S L )) ≥

June 26, 2017

κτ
β1−+τ

(77)

DRAFT

21

where
β1−+τ =

sup
x∈F,k∈{1,2}

β1−+τ (PYk ,B L |X=x , QYk ,B L )

κτ = inf max QYk ,B L [E]
E k∈{1,2}

(78)
(79)

and the infimum in the definition of κτ is with respect to all sets E ⊆ B satisfying
∀x ∈ F, ∃k : PYk ,B L |X=x [E] ≥ τ.

(80)

We conclude the proof by providing an upper bound on β1−+τ and a lower bound on κτ .
Upper bound on β1−+τ : By symmetry, β1−+τ (PYk ,B L |X=x , QYk ,B L ) takes the same value for
all x ∈ F. To upper-bound β1−+τ , we apply [6, Eq. (103)] to obtain




PYk ,B L |X (Yk , B L |x)
log β1−+τ ≤ − sup γ0 : max Px log
< γ0 ≤  − τ .
(81)
k
QYk ,B L (Yk , B L )
Here, x is an arbitrary element in F. We further upper-bound (81) by lower-bounding
log

PY

L (Yk ,B
k ,B |X

QY

k ,B

L (Yk

L |x)

,B L )

as follows:



PYk ,B L |X (Yk , B L |x)
≥ γ0
Px log
QYk ,B L (Yk , B L )



= Px ık (x(B L ); Yk ) + log S L PB L |X (B L |x) ≥ γ0
h


L
L
L
≥ Px ık (x(B ); Yk ) + log S PB L |X (B |x) ≥ γ0 ,

(82)


S L PB L |X (B L |x) ≥ e−ζ
(83)


≥ Px ık (x(B L ); Yk ) − ζ ≥ γ0 , S L PB L |X (B L |x) ≥ e−ζ
(84)




≥ Px ık (x(B L ); Yk ) − ζ ≥ γ0 − Px S L PB L |X (B L |x) < e−ζ
(85)


≥ Px ık (x(B L ); Yk ) − ζ ≥ γ0 − e−ζ .
(86)
 
Here, we have used that P[A, B] = P[A] − P[A \ B] ≥ P[A] − P B { for any events A and B with
B { being the complement of the set B, and (86) follows because


Px PB L |X (B L |x) < e−ζ /S L


X
e−ζ
L
L
=
PB L |X (b |x)1 PB L |X (b |x) < L
S
L
L
b ∈S

X e−ζ 
e−ζ
L
≤
1 PB L |X (b |x) < L
SL
S
L
L

(87)
(88)

b ∈S

≤ e−ζ .
June 26, 2017

(89)
DRAFT

22

Lower bound on κτ : We follow steps similar to [5, Eq. (28)–(29)]. Specifically, for any set E
satisfying (80), we have
X

PYk ,B L |X=x [E] ≥ τ 1{x ∈ F} .

(90)

k

By averaging (90) over X ∼ QX in (73) and by using (76), we obtain
X X
τ QX [F] ≤
QX (x)PYk ,B L |X=x [E]
k

≤ SL

(91)

x∈X SLm

X

QYk ,B L (E).

(92)

k

This implies that
max QYk ,B L (E) ≥
k

τ QX (F)
.
2S L

(93)

Since E is arbitrary, we have shown that
τ QX (F)
.
2S L

κτ ≥

(94)

Next, by using that [17, Lem 2.6]
QX (F) ≥ (1 + m)−SL|X |

(95)

we conclude that
log κτ ≥ log

τ
− SL|X | log(1 + m) − L log S.
2

(96)

We establish the desired result (30) by substituting (86) and (96) in (77).
A PPENDIX B
P ROOF OF T HEOREM 4 ( CONVERSE )

AND OF

T HEOREM 5 ( CONVERSE )

By Theorem 2, every (n, M, )-FLF satisfies
1
 ≥ PJ,Y1n ,Y2n [A(J, Y1n , Y2n ) ≤ log M − λ] − e−λ
2

(97)

where
A(j, y1n , y2n )

,

X
k

June 26, 2017

ηk

n
X



ıP ∗ ,Wk yk,i ; fi (j, y1i−1 , y2i−1 ) .

(98)

i=1

DRAFT

23

Observe also that
"
X

EPY

i−1 ,Y i−1 ,J=j
1,i ,Y2,i |Y1
2

=

X

k

Wk (Yk,i |fi (j, Y1i−1 , Y2i−1 ))
ηk log
PY∗k (Yk,i )

#

ηk D(Wk (·|fi (j, Y1i−1 , Y2i−1 ))||PY∗k )

(99)

k

nX
o
≤ max
ηk D(Wk (·|x)||PY∗k )
x∈X

(100)

k

= C + max
x∈X

nX

∗

ηk h∇Ik , 1x − P i

o

(101)

k

= C.

(102)

Here, in (101), we let 1x be the |X |-dimensional vector that has a one in the xth entry and zeroes
in all other entries and we have used (7) and Lemma 1.
Proof of Theorem 4 (converse): Next, we apply a Berry-Esseen-type central-limit theorem for
martingales due to Bolthausen to estimate the probability PY1n ,Y2n |J=j [A(j, Y1n , Y2n ) ≤ log M − η]
[18, p. 2] (see also [19]) in a manner similar to [9, Th. 2].
Theorem 11: Let 0 < γ < ∞ and let {Xi }ni=1 , n ≥ 2, be a martingale difference sequence3 with
respect to the filtration {Fi }ni=0 where |Xi | ≤ γ almost surely i = 1, . . . , n. Let σi2 , E[Xi2 |Fi−1 ]
and σ̄ 2 , E[Xi2 ]. Furthermore, assume that
s2n

,

n
X
i=1

σ̄i2

=

n
X

σi2

(103)

i=1

almost surely. Then, there exists a constant 0 < L(γ) < ∞ that depends only on γ, so that
" n
#
1X
nL(γ) log n
sup P
Xi ≤ t − Q(−t) ≤
.
(104)
s i=1
s3n
t
To apply this result, we note that, for every j ∈ M,
(
"
1 X
Wk (Yk,i |fi (j, Y1i−1 , Y2i−1 ))
√
ηk log
PY∗k (Yk,i )
V
k
"
##)n
X
Wk (Yk,i |fi (j, Y1i−1 , Y2i−1 ))
ηk log
− EPY ,Y |Y i−1 ,Y i−1 ,J=j
1,i 2,i 1
PY∗k (Yk,i )
2
k

(105)

i=1

3

∞
A sequence {Xi }∞
i=1 is a martingale difference sequence with respect to the filtration {Fi }i=0 if it satisfies the following two

conditions for all t ∈ N: Xi is Fi -measurable and E[Xi |Fi−1 ] = 0 almost surely [18].

June 26, 2017

DRAFT

24

is a uniformly bounded martingale difference sequence with respect to the filtration {σ(Y1i , Y2i )}ni=1 .
Furthermore, the conditional variance σi2 (defined as in Theorem 11) of the RVs in (105) is equal
to V because of (36). It then follows from Theorem 11 and from (102) that
PY1n ,Y2n |J=j [A(j, Y1n , Y2n ) ≤ log M − λ]


nC − log M + λ
c log n
√
≥Q
− √ .
n
nV

(106)

Here, the constant in the last term depends only on the component channels {Wk }. Substituting
(106) into (97), we conclude that


nC − log M + λ
1
c log n
√
≥ Q
− √
− e−λ .
2
n
nV

(107)

By solving for log M , by setting λ = log n, and by performing a Taylor expansion of Q−1 (·) around
2, we obtain
log M ≤ nC −
= nC −

√
√


 
c log n
−λ
+e
nV Q
+λ
2 + √
n

(108)

nV Q−1 (2) + O(log n)

(109)

−1

which is the desired result.
Proof of Theorem 5 (converse): When (36) is not satisfied, we resort to Chebyshev inequality
[20, Eq. (3.1.1)] instead of the central limit theorem. Specifically, since X and Y are finite-cardinality
alphabets, there exists a constant K < ∞ such that
"
#
X
Wk (Yk,i |fi (J, Y1i−1 , Y2i−1 ))
Var
ηk log
J, Y1i−1 , Y2i−1 ≤ K
∗
P
(Y
)
k,i
Yk
k

(110)

for i ∈ {1, . . . , t}. It follows from (97), (102), (110), and Chebyshev inequality that
2( + e−λ ) ≥ PJ,Y1n ,Y2n [A(J, Y1n , Y2n ) ≤ log M − λ]
Kn
≥1−
.
(log M − nC − λ)2

(111)
(112)

By solving for log M and by setting λ = log n, we obtain that for all  ∈ (0, 1/2) and for all
sufficiently large n
s
log M ≤ nC +

June 26, 2017

√
Kn
+ log n = nC + O( n).
1 − 2( + 1/n)

(113)

DRAFT

25

A PPENDIX C
P ROOF OF T HEOREM 4 ( ACHIEVABILITY )

AND OF

T HEOREM 5 ( ACHIEVABILITY )

To establish that the RHS of (38) is achievable (which implies achievability in Theorem 4 as
well), we start by setting in Theorem 3 the parameter S to 5 (recall that S controls the number
of subcodewords available in each of the L blocks). Let now κ be the smallest integer larger than
C −1 log 5. Furthermore, set the number of blocks and the number of channel uses per block in
Theorem 3 to
L = Ln , bn1/3 c

m = mn , bn/Ln c − κ.

and

(114)

We use the remaining κLn channel uses to communicate the sequence B Ln ∈ {1, . . . , 5}Ln to the
decoders. Since κ > C −1 log 5, the rate log 5/κ of the code is smaller than C. Hence, its error
probability can be made to decay exponentially in Ln
∗ (κLn , 5Ln ) ≤ exp(−ωLn )

(115)

√
for some positive constant ω [17, Th. 10.10]. In Theorem 3, we also set τ = 1/ n, ζ = n1/3 .
Next, we specify the types {Pb }5b=1 in Theorem 3. Let ρ > 0 (a constant that we shall specify
|X |

later) and let v0 be an arbitrary nonzero vector in R0 satisfying
h∇I1 , v0 i = ρ.

(116)

We next define the following probability distributions
(n)

P b , P ∗ − (−1)b v0 n−1/3 ,
(n)

P 3 , P ∗,

(n)

P 4 , P1∗ ,

b ∈ {1, 2}

(117)

(n)

P 5 , P2∗ .

(118)

(n)

Since P ∗ (x) > 0 for all x ∈ X , we conclude that P b are legitimate probability distributions for all
(n)

sufficiently large n. Now, let Pb

(n)

be the type Q(n) ∈ Pmn (X ) that minimizes P b − Q(n) (recall

that Pmn (X ) denotes the set of types of mn -dimensional sequences and k·k denotes the Euclidean
(n)

distance). We then choose the types in Theorem 3 as Pb = Pb .
(n)

Observe that Pb

(n)

− Pb

1
(n)

= O(1/n) and that Ik (·) is differentiable. Hence, we have
(n)

Ik (Pb ) = Ik (P b ) + O(1/n),

b ∈ {1, . . . , 5}.

(119)

n
The mappings {h` }L`=1
, which use the feedback to determine which subcodeword to transmit

in each of the Ln blocks, are chosen as follows: in the first Ln − 1 blocks, we let the transmitter
June 26, 2017

DRAFT

26
(n)

choose between subcodewords of type P1

(n)

and of type P2

depending on which decoder has

the largest accumulated information density. This balances the information densities at the two
decoders so that the difference is tightly concentrated around zero (as we shall see later). In the last
(n)

block, the transmitter chooses a subcodeword of type P3

(which approximates the CAID P ∗ ) if

the arithmetic average of the information densities is above a suitably chosen threshold γ1 (specified
(n)

in (140)). Otherwise, it chooses uniformly at random between the subcodeword of type P4
(n)

approximates the CAID of W1 ) and the one of type P5

(which

(which approximates the CAID of W2 ).

n
Mathematically, we can express the chosen mappings {h` }L`=1
as follows: h1 = 2 and for ` =

2, . . . , Ln − 1,
`−1
`−1
h` (x`−1 (B `−1 ), Y`−1
), Y`−1
))
1 (B
2 (B
o
n
`−1
`−1
`−1
`−1
`−1
= 1 + 1 ı1 (x`−1 (B `−1 ); Y`−1
(B
))
≥
ı
(x
(B
);
Y
(B
))
.
2
2
1

(120)

For ` = Ln , we let T be a uniformly distributed RV on {1, 2} and set
`−1
`−1
h` (x`−1 (B `−1 ), Y`−1
), Y`−1
))
1 (B
2 (B

P

`−1
`−1

3,
if
(B `−1 ); Y`−1
)) ≥ γ1

k (B
k ηk ık (x


P
`−1
, 4, if k ηk ık (x`−1 (B `−1 ); Y`−1
)) < γ1 and T = 1
k (B




5, if P η ı (x`−1 (B `−1 ); Y`−1 (B `−1 )) < γ and T = 2.
1
k
k k k
(n)

(n)

(n)

Roughly speaking, the threshold γ1 is chosen so that P3 , P4 , and P5

(121)

are used with probability

(1 − 2), , and , respectively.
Using Theorem 3 with the parameters listed above, we obtain
log Mf∗ (n, )
≥ log Mf∗ (Ln (mn + κ), )
n


≥ sup γ : max P ık (x(B Ln ); Yk (B Ln )) < γ

(122)

k

o
√
1/3
≤  − ∗ (κLn , S Ln ) − 1/ n − e−n
1
+ log √ − SLn |X | log(1 + mn ) − Ln log S − n1/3
2 n
n
o


Ln
Ln
−1/2
≥ sup γ : min P ık (x(B ); Yk (B )) < γ ≤  − c1 n
log n

(123)

k

+ O(n
June 26, 2017

1/3

log n)

(124)
DRAFT

27

for some c1 > 0. In (124), we used that
√
√
1/3
1/3
∗ (κLn , S Ln ) + 1/ n + e−n ≤ e−ωLn + 1/ n + e−n
≤ c1 n−1/2 log n
for sufficiently large n. To conclude the proof, we show that


p
√
γ , Ln mn C − (Ln − 1)mn V Q−1 2 − 2 2(c1 + c2 )n−1/2 log n

(125)
(126)

(127)

(the constant c2 > 0 will be defined shortly) satisfies


P ık (x(B Ln ); Yk (B Ln )) < γ ≤  − c1 n−1/2 log n

(128)

for all sufficiently large n. The desired result (38) then follows by using (128) in (124) to further
lower-bound log Mf∗ (n, ), by observing that (Ln − 1)mn = n + O(n2/3 ), and by performing a
Taylor expansion of Q−1 (·) in (127) around 2.
Proof of (128): To simplify the notation, we set
(b)

Zk,`,i , ıP (n) ,W (x`,i (b); Yk,`,i (b))
k

b

Z k,`1 ,`2 ,

`2 X
mn
X

(B )

Zk,`,i` .

(129)
(130)

`=`1 i=1
(b)

The RVs Zk,`,i are independent for all k, b, `, and i. Note also that Z k,1,Ln = ık (x(B Ln ); Yk (B Ln )).


Hence, the left-hand side of (128) can be rewritten as P Z k,1,Ln < γ .
Let `(i) , di/mn e. It will turn out convenient to define the following random quantities as well:
X

Zi∗ ,
ηk ıP ∗ ,Wk x`(i),i−(`(i)−1)mn (B` ); Yk,`(i),i−(`(i)−1)mn (B` )
(131)
k∈{1,2}
(Ln −1)mn
∗

Z ,

X

Zi∗

(132)

i=1

A,

LX
mn
n −1 X

(n)

X

`=1 i=1 k∈{1,2}

PB Wk (Yk,`,i (B` ))
ηk log ` ∗
PYk (Yk,`,i (B` ))

E , Z 1,1,Ln −1 − Z 2,1,Ln −1 .

(133)
(134)

In the remainder of the proof, we shall make use of the following decomposition:
∗

Z k,1,Ln −1 = Z − A − ηk̄ (−1)k E.

June 26, 2017

(135)

DRAFT

28
∗

We next show that Z is accurately approximated by a normal distribution with mean (Ln − 1)mn C
and variance (Ln − 1)mn V , whereas both A and E are of order n1/3 . To prove these claims, we rely
on the Berry-Esseen-type central limit theorem for martingales given in Theorem 11, on Hoeffding
inequality [21], on Azuma-Hoeffding inequality [20, Th. 2.2.1], and on the following stabilization
lemma.
(1)

(2)

Lemma 12 (Stabilization lemma): Let {X` } and {X` } be i.i.d. RVs with mean µ1 > 0 > µ2
satisfying
h
i
h
i
2
2
(b)
(b)
P X` ≥ v ≤ e−β|v−µb |+ , P X` ≤ v ≤ e−β|µb −v|+

(136)
(2)

for all b ∈ {1, 2} and all ` ∈ N. Define the sequence {Y` } as follows: Y1 = X1 and

 Y + X (1)
for Y`−1 < 0
`−1
`
Y` =
 Y`−1 + X (2)
for Y`−1 ≥ 0

(137)

`

for ` ≥ 2. Let c ≥ 1 satisfy
r
min{µ1 , −µ2 } ≥

 2
π
c
exp
.
β
4

(138)

Then
√

P[|Y` | ≥ v] ≤ 2e−c

β(v−µ1 +µ2 )

.

(139)

The proof of this lemma is delegated to Appendix H.
Let now c3 > 0 be an arbitrary constant and define the thresholds
γ1 , γ − mn C + n1/3 log n
√
γ2 , (Ln − 1)mn C − c3 n log n.

(140)
(141)
∗

Here, γ is given in (127). Roughly speaking, γ1 is chosen so as to be the 2-quantile of Z − A for
∗

large n, whereas γ2 is needed to upper-bound the probability of the (rare) event that Z − A is far
smaller than its mean. Note also that γ1 > γ2 for sufficiently large n. Define the four disjoint events
n ∗
o
E1,m , Z − A ∈ [γ2 , γ1 ), T = m , m ∈ {1, 2}
(142)
n ∗
o
E2 , Z − A ≥ γ1
(143)
n ∗
o
(144)
E3 , Z − A < γ2 .

June 26, 2017

DRAFT

29

Using the events defined above, we obtain the following upper bound







P Z k,1,Ln < γ ≤ P E1,k̄ + P E1,k ∩ Z k,1,Ln < γ



+ P E2 ∩ Z k,1,Ln < γ + P[E3 ] .

(145)



In the following, we shall upper-bound each of these four probabilities. It turns out that only P E1,k̄
yields a nonvanishing contribution, which converges to  from below at a rate O(n−1/2 log n) as
n → ∞. The remaining three probabilities all vanish at a rate of O(1/n). This implies that there
exists a constant c1 > 0 such that the inequality (128) holds for all sufficiently large n.


Bound on P E1,k̄ : We first establish a bound on the upper-tail probability of A in (142). For
b ∈ {1, 2}, we have
(n)

D(Pb Wk ||PY∗k )
(n)

(n)

= D(Wk ||PY∗k |P b ) − Ik (P b ) + O(1/n)


= D(Wk ||PY∗k |P ∗ ) − (−1)b h∇Ik , v0 i n−1/3


∗
b
−1/3
− Ik (P ) − (−1) h∇Ik , v0 i n
+ O(n−2/3 )

(146)

= O(n−2/3 ).

(148)

(147)

Here, (146) follows from the Golden formula I(PX , PY |X ) = D(PY |X ||QY |PX ) − D(PY ||QY ) and
from (119); (147) follows from the differentiability of Ik (·) and of D(Wk ||PY∗k |·) at P ∗ , by Taylorexpanding Ik (·) and D(Wk ||PY∗k |·) around P ∗ , and by using (117); finally, (148) follows because
D(Wk ||PY∗k |P ∗ ) = Ik (P ∗ ) = C for k ∈ {1, 2}. Thus, there exist positive convergent sequences
(b)

{ζn } for b ∈ {1, 2} such that
X

(n)

ηk D(Pb Wk ||PY∗k ) = ζn(b) n−2/3 .

(149)

k
(n)

Next, since Pb

− P∗

1

= O(n−1/3 ), there exists a constant c4 > 0 such that
X
(n)
ηk log Pb Wk (y)/PY∗k (y) ≤ c4 n−1/3

(150)

k

June 26, 2017

DRAFT

30

for sufficiently large n. Hence, for sufficiently large n,
h
i
1/3
P A ≥ n log n
#
"L −1 m
(n)
n
n X
X
X
PB` Wk (Yk,`,i (B` ))
≥ n1/3 log n
=P
ηk log
∗
(Y
(B
))
P
k,`,i
`
Yk
`=1 i=1 k
≤ exp −

(151)

!
(b) 2
+

n1/3 log n − n−2/3 (Ln − 1)mn maxb∈{1,2} ζn
2c24 n−2/3 (Ln − 1)mn


≤ exp −cn1/3 log2 n
 
1
.
=O
n

(152)
(153)
(154)

Here, (152) follows from the Azuma-Hoeffding inequality [20, Th. 2.2.1] applied to the bounded
martingale difference sequence
(
(n)
X
PB`(i) Wk (Yk,`(i),i−(`(i)−1)mn (B`(i) ))
ηk log
PY∗k (Yk,`(i),i−(`(i)−1)mn (B`(i) ))
k
"
#)(Ln −1)mn
(n)
X
PB`(i) Wk (Yk,`(i),i−(`(i)−1)mn (B`(i) ))
−E
ηk log
F i−1
∗
P
(Y
k,`(i),i−(`(i)−1)mn (B`(i) ))
Y
k
k

(155)

i=1

with respect to the filtration
n
F i , σ B1 , . . . , B`(i+1) , Y1,1 , . . . , Y1,`(i)−1 , Y1,`(i),1 , . . . , Y1,`(i),i−(`(i)−1)mn
o
, Y2,1 , . . . , Y2,`(i)−1 , Y2,`(i),1 , . . . , Y2,`(i),i−(`(i)−1)mn .

(156)

The inequality (152) follows also from (149), which implies that


(n)
(Ln −1)mn
X
X
PB`(i) Wk (Yk,`(i),i−(`(i)−1)mn (B`(i) ))
E
ηk log
F i−1 
∗
P
(Y
(B
))
k,`(i),i−(`(i)−1)m
`(i)
n
Y
k
i=1
k
≤ (Ln − 1)mn max ζn(b) n−2/3 .
b∈{1,2}

(157)

(b)

Finally, (153) holds for sufficiently large n because ζn is convergent for b ∈ {1, 2}.
Next, we shall invoke the Berry-Esseen-type central limit theorem for martingales given in
Theorem 11. Specifically, we define the increasing filtration
Fi , σ(Z1∗ , . . . , Zi∗ , B1 , . . . , B`(i+1) )

(158)

and the sequence
s
Di ,

June 26, 2017

V
(n)

VB`(i)

Zi∗ − E[Zi∗ |Fi−1 ]



(159)

DRAFT

31

where
(n)
Vb

, EP (n) ×W

k

b

X


VarWk
ηk ıP ∗ ,Wk (X; Yk ) X = V + O(n−1/3 ).

(160)

k

One can readily verify that {Di } is a martingale difference sequence since Di is Fi -measurable (B`(i)
q
is Fi−1 -measurable, which implies that E[Di |Fi−1 ] = V /VB (n) E[Zi∗ − E[Zi∗ |Fi−1 ] |Fi−1 ] = 0).
`(i)

Furthermore, |Di | is bounded. Next, for all ` ∈ {1, . . . , Ln − 1}, because x` (b) is of constant
composition for b ∈ {1, 2} and ` ∈ {1, . . . , Ln }, it follows that
`mn
X

E[Zi∗ |Fi−1 ] = mn

X

= mn

X

(n)

ηk D(Wk ||PY∗k |Pb )

(161)

k

i=(`−1)mn +1

(n)

ηk C + ∇Ik , Pb

− P∗



(162)

k

= mn C.

(163)

Here, (162) follows because D(Wk ||PY∗k |P ) is linear in P ∈ P(X ) and (163) follows from Lemma 1.
It also follows that
`mn
X



E Di2 |Fi−1

i=(`−1)mn +1

=

`mn
X

V

i
h
E (Zi∗ − E[Zi∗ |Fi−1 ])2 Fi−1

(n)

VB`

(164)

i=(`−1)mn +1

= mn V.

(165)

Recall here the definition of V in (35) and of Zi∗ in (131). Moreover, (160) implies that there exists
a constant d1 > 0 such that
V
(n)
Vb

≤

1
1 − d1 n−1/3

(166)

for all sufficiently large n and for b ∈ {1, 2}.

June 26, 2017

DRAFT

32



We next upper-bound P E1,k̄ as follows:


P E1,k̄
i
1 h ∗
≤ P Z < γ1 + n1/3 log n + O(1/n)
2 
(Ln −1)mn

1
≤ P
2

X
i=1

Zi∗

E[Zi∗ |Fi−1 ]

(167)


1/3

−
γ1 + n log n − (Ln − 1)mn C 
p
p
<
1 − d1 n−1/3
1 − d1 n−1/3

+ O(1/n)
"
1
1
≤ P p
2
V (Ln − 1)mn

(168)
(Ln −1)mn

X
i=1

γ1 + n1/3 log n − (Ln − 1)mn C
Di < p
V (Ln − 1)mn (1 − d1 n−1/3 )

#

+ O(1/n)

 √
1
(Ln − 1)mn C − γ1 − n1/3 log n
2c2 log n
√
≤ Q p
+
2
n
V (Ln − 1)mn (1 − d1 n−1/3 )
√
2c1 log n
√
≤−
.
n

(169)
(170)
(171)

Here, (167) follows from (142), from (154), and because T is uniform on {1, 2} and is independent of
(Y1 , Y2 ); (168) follows from (163); (169) follows from (166); (170), which holds for some constant
c2 > 0 and sufficiently large n, follows from Theorem 11; finally, (171) follows from (127) and
(140).



Bound on P E1,k ∩ Z k,1,Ln < γ : We shall first show that E in (135) is sufficiently
concentrated around 0. Specifically, let
m

n
1X
(b)
(b)
(Z
− Z2,`,i )
(172)
2 i=1 1,`,i
P n −1 (B` )
are independent RVs and E = L`=1
F` . It follows from (116)–(117),

(b)

F`

 (b)
for b ∈ {1, 2}. The F`

,

(n)

(119), and from Taylor’s theorem that there exist convergent sequences {ξb } such that
(n)

(n)

(n)

I1 (Pb ) − I2 (Pb ) = −2(−1)b (ρn−1/3 + ξb n−2/3 ).

(173)

 (b) 
(n)
n
Consequently, since the {x`,i (b)}m
= µb ,
i=1 are of constant composition, it follows that E F`
where
(n)

(n)

µb , −(−1)b (ρmn n−1/3 + ξb mn n−2/3 ) = O(n1/3 ).
(b)

Since F`

is a sum of independent RVs, it follows from Hoeffding inequality that
 (b)

− 1 2
P F` ≥ v ≤ e 2mn c5

June 26, 2017

(174)

(n) 2

v−µb

+

(175)
DRAFT

33

and
 (b)

− 1 2
P F` ≤ v ≤ e 2mn c5

(n)

µb −v

2
+

.

Here, c5 ≥ max`,i max{1, |Z1,`,i − Z2,`,i |}. We now choose ρ so that ρ >
(b)

(176)
p

2

4πc25 ec5 . Next, we

(b)

apply Lemma 12 with X` = F` , β = 1/(2mn c25 ), and c = 2c5 and conclude that, for sufficiently
large n,
q
(n)
(n)


− m2 (n1/3 log n−µ1 +µ2 )
1/3
n
P |E| ≥ n log n ≤ 2e
≤ 3/n.

(177)

In the last step, we used that ξn mn n−2/3 = O(1).
Define
ηmax = max ηk .

(178)

k

It now follows that there exists a constant c6 > 0 such that



P E1,k ∩ Z k,1,Ln < γ



≤ P E1,k ∩ |E| ≤ n1/3 log n, Z k,1,Ln < γ + 3/n


≤ P Z k,Ln ,Ln < γ − γ2 + ηmax n1/3 log n|BLn = 3 + k + 3/n

2 
√
c6
≤ exp −
+ 3/n
mn (Ck − C) − 2c3 n log n
mn
= O(1/n) .

(179)
(180)
(181)
(182)

Here, (179) follows from of (177); (180) follows because if E1,k occurs then BLn = 3 + k (see
∗

∗

(121)), because Z − A ≥ γ2 , and because Z k,1,Ln = Z − A − ηk̄ (−1)k E + Z k,Ln ,Ln . Finally,
(181) follows from (127), (141), and from Hoeffding inequality applied to Z k,Ln ,Ln






Bound on P E2 ∩ Z k,1,Ln < γ : The upper bound on P E2 ∩ Z k,1,Ln < γ follows by
an argument similar to the one we used to establish (182). Specifically,



P E2 ∩ Z k,1,Ln < γ
h ∗
i
≤ P Z − A ≥ γ1 , |E| ≤ n1/3 log n, Z k,1,Ln < γ + 3/n
h
i
k
1/3
= P Z k,1,Ln −1 + ηk̄ (−1) E ≥ γ1 , |E| ≤ n log n, Z k,1,Ln < γ, BLn = 3
+ 3/n
i
h
1/3
≤ P Z k,1,Ln −1 ≥ γ1 − ηmax n log n, Z k,1,Ln < γ, BLn = 3 + 3/n
June 26, 2017

(183)

(184)
(185)

DRAFT

34

h
i
≤ P Z k,Ln ,Ln < γ − γ1 + ηmax n1/3 log n, BLn = 3 + 3/n
h
i
1/3
1/3
≤ P Z k,Ln ,Ln < mn C − n log n + ηmax n log n|BLn = 3 + 3/n


cn2/3 log2 n
≤ exp −
+ 3/n
mn
= O(1/n).

(186)
(187)
(188)
(189)

∗

Here, (183) follows from (177); (184) follows from (135) and because Z − A ≥ γ1 implies
BLn = 3 (see (121) and (143)); (186) follows because Z k,1,Ln −Z k,1,Ln −1 = Z k,Ln ,Ln ; (187) follows
because (127) and (140); (187) follows from Hoeffding inequality; and finally, (188) follows because
ηmax < 1.
Bound on P[E3 ]: The upper bound on P[E3 ] follows by an application of Azuma-Hoeffding

(Ln −1)mn
inequality [20, Th. 2.2.1] applied to the martingale difference sequence Zi∗ −E[Zi∗ |Fi−1 ] i=1
for the filtration
{Fi = σ(Z1∗ , . . . , Zi∗ , B1 , . . . , B`(i+1) )}i .

(190)

Specifically,
"

√

∗

#

P[E3 ] = P Z − A < (Ln − 1)mn C − c3 n log n

(191)

" (Ln −1)mn
#

X 
√
≤P
Zi∗ − E[Zi∗ |Fi−1 ] < −c3 n log n + n1/3 log n
i=1

+ O(1/n)


√
c(c3 n log n − n1/3 log n)
≤ exp −
+ O(1/n)
(Ln − 1)mn
= O(1/n).

(192)
(193)
(194)

In (191), we have used (141), (192) follows from (154), and (193) follows from Azuma-Hoeffding
inequality [20, Th. 2.2.1].
A PPENDIX D
P ROOF OF T HEOREM 7
We first construct an auxiliary channel that embeds our feedback scheme. To this end, we write
the input Xi of the channel as
Xi = X i + 2Bi
June 26, 2017

(195)
DRAFT

35

where i ∈ {1, . . . , n}, X i ∈ {1, 2}, and

i−1
i−1


if d(X , Y1i−1 ) > d(X , Y2i−1 )

 0
Bi =

i−1

if d(X

, Y1i−1 ) < d(X

i−1

, Y2i−1 )



 Z (i) if d(X i−1 , Y i−1 ) = d(X i−1 , Y i−1 ).
1
2
1

(196)

Here, d(·, ·) denotes the Hamming distance. Through (195), we define the auxiliary component
channels PY n |X n = PX n |X n ◦ PYkn |X n . We note that, by symmetry, the component channels PY1n |X n
k

and PY2n |X are identical, i.e., PY1n |X n (y n |xn ) = PY2n |X n (y n |xn ) for all xn ∈ {1, 2}n . Hence, the
n

average error probabilities at both decoders are the same. We next apply the RCU bound under
minimum distance decoding to the component channel PY1n |X n .
The remaining steps follow closely the proof of the RCU bound in [6, Th. 16]. Consider first
the average error probability of a binary codebook C = (C(1), . . . , C(M )) ∈ {1, 2}M ×n with a
minimum Hamming distance decoder averaged over all randomly generated codebooks with i.i.d.
entries uniformly distributed on {1, 2}:
E[C ]
" " M
##
M
[
1 X
n
≤
E P
{d(C(j), Y1n ) ≤ d(C(m), Y1n )} X = C(m) .
M m=1
j=1;j6=m

(197)

The symmetry in the probability distribution of the codewords in C implies that all terms in the
summation on the right-hand side of (197) are identical. Hence, we obtain
E[C ]
≤ PX n (1),...,X n (M ),Y1n

"M
[

#
n

n

d(X (j), Y1n ) ≤ d(X (1), Y1n )

(198)

j=2


= EX n (1),Y1n PX n (2),...,X n (M )

[
M



d(X

n

(j), Y1n )

≤

n
d(X 1 , Y1n )

n
X 1 , Y1n


(199)

j=2

h
n
h
ioi
n
n
n
≤ EX n (1),Y1n min 1, (M − 1)PX n (2) d(X (2), Y1n ) ≤ d(X (1), Y1n ) X (1), Y1n
(200)
=

n
X




n
PZ (n) (t) min 1, (M − 1)P d(X (2), Y1n ) ≤ t .

(201)

1

t=0

Here,
PX n (1),...,X n (M ),Y1n (xn (1), . . . , xn (M ), y1n ) = 2−nM PY1n |X n (1) (y1n |xn (1)).

(202)

n

The desired result follows by noting that d(X (2), Y1n ) is a Binomial RV with parameters n and
n

n

1/2. Indeed, X (2) is uniformly distributed on {1, 2}n , independent of X (1) and Y1n .
June 26, 2017

DRAFT

36

A PPENDIX E
P ROOF OF T HEOREM 8
We first establish the result for deterministic VLF codes with |U| = 1. At the end of the proof,
we show that (58) holds also when |U| > 1 by using the same argument as in [8, Th. 4]. By [10,
Lem. 1], we have that
n
o
log M = H(J) ≤ min H(J) − H(J|Ykτk ) + h() +  log M.

(203)

ηk ak for all (a1 , a2 ) ∈ R2+ , we obtain
n
o
(1 − ) log M ≤ min H(J) − H(J|Ykτk ) + h()
k

X 
≤
ηk H(J) − H(J|Ykτk ) + h().

(204)

k

Using that mink∈{1,2} ak ≤

P

k

(205)

k

It will turn out convenient in the remainder of the proof to use the notations of conditional entropy
and conditional mutual information given a sigma-algebra F. These two quantities are defined as
follows:
H(Z|F) , −

X

P (z|F) log P (z|F)

(206)

z∈Z

X

I(Z; T |F) ,

P (z, t|F) log

(z,t)∈Z×T

P (z, t|F)
.
P (z|F)P (t|F)

(207)

As in [13], we simply write Y n in place of σ(Y n ) when F = σ(Y n ). Continuing from (205), we
obtain the following chain of inequalities:
(1 − ) log M − h()
X

τk
X

i−1
i
≤
ηk E
H(J|Yk ) − H(J|Yk ) + h()
i=1

k

=

X

(208)

ηk E

X
∞

1{τk ≥ i}

H(J|Yki−1 )

−

H(J|Yki )





i=1

k


X
∞
X

i−1
i
=
E
ηk 1{τk ≥ i} H(J|Yk ) − H(J|Yk )
i=1

i=1

(211)

k

X
∞
i
h
X
i−1
i
i−1
i−1
=
E
ηk 1{τk ≥ i} E H(J|Yk ) − H(J|Yk ) Y1 , Y2
June 26, 2017

(210)

k


 X
∞
X
 i−1 i−1
i−1
i
=
E E
ηk 1{τk ≥ i} H(J|Yk ) − H(J|Yk ) Y1 , Y2

i=1

(209)

(212)

k
DRAFT

37

X

∞
X
i−1
=
E
ηk 1{τk ≥ i} I(J; Yk,i |Yk )
≤

i=1
∞ 
X

(213)

k

P[τ1 ≥ i, τ2 ≥ i] E

X

i=1

ηk I(J; Yk,i |Yki−1 )


τ1 ≥ i, τ2 ≥ i

k

+

X

i
h
i−1
ηk P[τk ≥ i, τk̄ < i] E I(J; Yk,i |Yk ) τk ≥ i, τk̄ < i .

(214)

k

Here, the expectation in (208) is with respect to Y1∞ , Y2∞ , τ1 and τ2 , (210) follows from Tonelli’s
theorem [22, Th. 18.3], (211) follows from the law of total expectation where the outer expectation
is with respect to (Y1i−1 , Y2i−1 ) and the inner expectation is with respect to (Y1,i , Y2,i ), and (212)
follows because the event {τk ≥ i} is Fk,i−1 -measurable.
Now, the Markov chain (Y1n−1 , Y2n−1 , J) − Xi − (Y1,i , Y2,i ) and the data-processing inequality
imply that
I(J; Yk,i |Yki−1 ) ≤ I(Xi ; Yk,i |Yki−1 ).

(215)

We also note that
X

i−1
E
ηk I(Xi ; Yk,i |Yk ) τ1 ≥ i, τ2 ≥ i
k

=

X

h 
i

ηk E Ik PXi |Y1i−1 ,Y2i−1 ·|Y1i−1 , Y2i−1
τ1 ≥ i, τ2 ≥ i

(216)

i
 h

i−1
i−1
i−1
i−1
ηk Ik E PXi |Y1 ,Y2 ·|Y1 , Y2
τ1 ≥ i, τ2 ≥ i

(217)

k

≤

X
k

≤C+

X

D
h
i
E

ηk ∇Ik , E PXi |Y1i−1 ,Y2i−1 ·|Y1i−1 , Y2i−1 τ1 ≥ i, τ2 ≥ i − P ∗

(218)

k

= C.

(219)

Here, (217) follows from Jensen’s inequality and from the concavity of mutual information, (218)
follows again from the concavity of mutual information, and (219) follows from Lemma 1. Similarly,
we also have that I(Xi , Yk,i |Yki−1 ) ≤ Ck . Substituting (215) and (219) in (214), we find that
(1 − ) log M ≤

∞
X

P[τ1 ≥ i, τ2 ≥ i] C

i=1

+

X
k

ηk Ck

∞
X

P[τk ≥ i, τk̄ < i] + h()

h
i
X 

= E min τk C +
E |τk − τk̄ |+ ηk Ck + h()
k

June 26, 2017

(220)

i=1

(221)

k
DRAFT

38

h
i


≤ E min τk C + E |τk − τk̄ | max ηk Ck + h()
k
k

h
i


= E max τk C + E |τk − τk̄ | max ηk Ck − C + h()

(222)

≤ nC + h().

(224)

k

k

(223)

In (224), we have used (15) and that
η1 C1 ≤ η1 C + η1 h∇I1 , P1∗ − P ∗ i

(225)

= η1 C − η2 h∇I2 , P1∗ − P ∗ i

(226)

≤ η1 C + η2 C

(227)

=C

(228)

where (225) follows from the concavity of mutual information, (226) follows from Lemma 1, and
(227) follows because, by the concavity of mutual information, C + h∇I2 , P1∗ − P ∗ i ≥ I2 (P1∗ ) ≥ 0.
The same argument shows that η2 C2 ≤ C.
For VLF codes with |U| > 1, the argument just outlined only shows only that


log M ≤ CE max τk U = u
k

X 




+
ηk h(P J 6= Jˆk |U = u ) − P J 6= Jˆk |U = u log M .

(229)

k

By taking expectations with respect to U on both sides and by applying Jensen’s inequality to the
binary entropy function, we obtain the desired result.
A PPENDIX F
P ROOF OF T HEOREM 9
The proof follows closely the proofs of [8, Th. 3] and [16, Th. 1]. We let Υ be a Bernoulli RV
with P[Υ = 1] = q and let its probability mass function be given by PS . The RV U is defined by
following domain and probability mass function
m
U , {0, 1} × X
· · × X m} ×X ∞
| × ·{z

(230)

SLm times

PU , PS × P1 × · · · × P1 × · · · × PS × · · · × PS ×(P ∗ )∞ .
|
{z
}
|
{z
}
Lm times

June 26, 2017

(231)

Lm times

DRAFT

39
(u)

(u)

The realization of U = u implicitly defines codebooks {Cj,` (b) ∈ X m } and {C̄j

∈ X ∞ } for

(j, b, `) ∈ M × {1, 2} × {1, . . . , L}. The encoding functions are defined as follows:

 

ν(`,i−1) ν(`,i−1)
(u)
ν(`,0) ν(`,0)
fν(`,i) (u, j, y1
, y2
) , Cj,` h` xν(`,0) , y1
, y2

(232)

i

(u)

fLm+nB +i (u, j, ·, ·) = (C̄j )i

(233)

for ` ∈ {1, . . . , L}, i ∈ {1, . . . , m}, and i ∈ {1, . . . , ∞} (recall that ν(`, i) = (` − 1)m + i). At
the time indices Lm + 1, . . . , Lm + nB , the transmitter sends B L using a fixed-blocklength code.
To keep the notation compact, we omit the superscript (u) in the remaining part of the proof.
At time n ≥ Lm + nB , decoder k computes the information densities
Sk,n (j) ,

m
L X
X



ν(`,i)−1
ν(`,i)−1
ıPB` ,Wk fν(`,i) (U, Y1
, Y2
); Yk,ν(`,i)

`=1 i=1

+

n
X

ıP ∗ ,Wk (fi (U, j, ·, ·); Yk,i )

(234)

i=Lm+nB +1

for j ∈ M. Define the stopping times
τk (j) = 1{Υ = 0} inf{n ≥ Lm + nB : Sk,n (j) ≥ γ or n = τmax + nB }

(235)

and let τk∗ be the time at which decoder k makes the final decision:
τk∗ , min τk (j).

(236)

gk,τk∗ (U, Yk k , B L ) , max{j ∈ M : τk (j) = τk∗ }.

(237)

j∈M

The output of decoder k at time τk∗ is
τ∗

τ∗

When Υ = 1, we have τk∗ = 0, and hence the decoder gk,τk∗ (U, Yk k ) outputs M . The average
blocklength is then given by
h
i
h
i
∗
∗
E max τk = (1 − q)E max τk |Υ = 0
k

k

M
i
1 X h
≤ (1 − q)
E max τk (j)|J = j, Υ = 0
k
M j=1

= (1 − q)E[max τk (1)|J = 1, Υ = 0]
 h
i

= (1 − q) E max τk + nB
k

June 26, 2017

(238)
(239)
(240)
(241)

DRAFT

40

where the expectation is over J, Y1∞ , Y2∞ , and U (B L is deterministic given these RVs). Here, (239)
follows from (236); (240) follows from symmetry; and (241) follows from the definition of τk in
(59). We next bound the average error probability:
h
i
τk∗
L
∗
P gk,τk (U, Yk , B ) 6= J
h
i
τ∗
≤ q + (1 − q)P gk,τk∗ (U, Yk k , B L ) 6= J|S = 0
+ (1 − q)∗ (nB , S L )
h
i
τ∗
≤ q + (1 − q)P gk,τk∗ (U, Yk k , B L ) 6= 1|J = 1, S = 0
+ (1 − q)∗ (nB , S L )

(242)

(243)

≤ q + (1 − q)P[τk (1) ≥ τk∗ |S = 0] + (1 − q)∗ (nB , S L )
" M
#
[
= q + (1 − q)P
{τk (1) ≥ τk (j)} S = 0 + (1 − q)∗ (nB , S L )

(244)
(245)

j=2

≤ q + (1 − q)(M − 1)P[τk (1) ≥ τk (2)|S = 0] + (1 − q)∗ (nB , S L )

(246)

= q + (1 − q)(M − 1)P[τk ≥ τ̄k ] + (1 − q)∗ (nB , S L ).

(247)

Here, (243) follows from (237) and (247) follows by noting that, given J = 1, the RVs
(Sk,n (1), Sk,n (2), τk (1), τk (2))

(248)

where the RVs {Sk,n (j)} are defined in (234), have the same joint distribution as

Sk,n (X n ; Ykn ), Sk,n (X̄ n ; Ykn ), τk + nB , τ̄k + nB .

(249)

We conclude the proof by noting that the tuple (U, h` , fn , {gk,n }, {τk∗ }) defines an (n, M, )-VLSF
code satisfying (63) and (64).
A PPENDIX G
P ROOF OF T HEOREM 10
We let n̄ be a variable related to the average blocklength n (it is roughly equal to (1 − )n̄), and
we analyze the achievability bound in Theorem 9 in the limit n̄ → ∞. We set S = 2 and let κ be

June 26, 2017

DRAFT

41

the smallest integer strictly larger than C −1 log 2. We also set
√
L = Ln̄ , b(n̄ − n̄ log n̄)1/3 c
j (n̄ − √n̄ log n̄)1/3 k
m = mn̄ ,
Ln̄

τmax

(250)
(251)

n̄− , Ln̄ mn̄
√
= n̄+ , bn̄ + n̄ log n̄c

(252)
(253)

√
and nB , κLn̄ = O(n̄1/3 ). Note that n̄+ − n̄− = O( n̄ log n̄). As in the proof of Theorem 5, we
have that
∗ (nB , 2Ln̄ ) ≤ exp(−ωLn̄ ) , ∗n̄

(254)

for some positive constant ω. In Appendix G-A, we prove that there exists a constant c1 such that,
for all sufficiently large n̄,
max P[τk = n̄+ ] ≤
k

c1
.
n̄

(255)

|X |

Next, we let v0 ∈ R0 be an arbitrary vector satisfying h∇I1 , v0 i > 0 > h∇I2 , v0 i. We define
the probability distributions P1 and P2 as follows
(n)

Pb

, P ∗ − (−1)b v0 n−1/3
(n̄)

for b ∈ {1, 2}. For sufficiently large n, Pb

(256)

are indeed legitimate probability distributions (recall

n̄
that P ∗ (x) > 0, ∀x ∈ X ). Moreover, for ` ∈ {1, . . . , Ln̄ }, we recursively define {h` }L`=1
and
n̄
{B` }L`=1
as follows

h` (X

ν(`,0)

ν(`,0)
ν(`,0)
, Y1
, Y2
)

n
o
, 1 + 1 Z 1,ν(`,0) ≥ Z 2,ν(`,0)
ν(`,0)

B` , h` (X ν(`,0) , Y1

ν(`,0)

, Y2

).

(257)
(258)

Here, ν(`, i) = (` − 1)mn + i and
Zk,t , ıP (n̄)

B`(t) ,Wk

Z k,t ,

t
X

Zk,i .

(Xt ; Yk,t )

(259)
(260)

i=1

June 26, 2017

DRAFT

42

In view of Theorem 9, we set for all integers n̄ > 0
γn̄ , C n̄ − 2n̄1/3 log n̄
n̄( − ∗n̄ − c1 /n̄) − 1
qn̄ ,
n̄ − 1
Mn̄ , bexp(γn̄ − log n̄)c.

(261)
(262)
(263)

Thus, we conclude that


∗
Ln̄
qn̄ + (1 − qn̄ ) (Mn̄ − 1) exp(−γn̄ ) +  (nB , 2 ) + max P[τk = τmax ]
k

n̄( − ∗n̄ − c1 /n̄) − 1 n̄(1 −  + ∗n̄ + c1 /n̄) 1
≤
+
+ ∗n̄ + c1 /n̄
n̄ − 1
n̄ − 1
n̄
= .

(264)
(265)

In Appendix G-B, we shall prove that there exists an integer n̄0 ≥ 0 such that, for all n̄ ≥ n̄0 ,
i
h
(266)
E max τk ≤ n̄.
k

Here, τk is defined by (59) with γ replaced by γn̄ . It then follows that
 h
i
 n̄(1 −  + ∗ + c /n̄)
1
n̄
(n̄ + κLn̄ ) , nn̄ .
(1 − qn̄ ) E max τk + nB ≤
k
n̄ − 1

(267)

We conclude the proof by invoking Theorem 9 with q = qn̄ , γ = γn̄ , and M = Mn̄ , which implies
that there exists a sequence of (nn̄ , Mn̄ , )-VLF codes for all n̄ ≥ n̄0 satisfying
log Mn̄ ≥ C n̄ − 2n̄1/3 log n̄ − log n̄ =

nn̄ C
1/3
+ O(nn̄ log nn̄ ).
1−

(268)

Before proceeding to the proofs of (255) and (266), we first introduce some notation. It follows
(1)

from Taylor’s theorem and from Lemma 1 that there exist positive convergent sequences {ζn̄ } and
(2)

{ζn̄ } such that
X

(n̄)

(b)

ηk Ik (Pb ) = C − n̄−2/3 ζn̄

(269)

k
(max)

for b ∈ {1, 2}. Let also ζn̄

(b)

, maxb∈{0,1} ζn̄ and let µb,n̄ for b ∈ {1, 2} be defined as
h
i
(n̄)
(n̄)
µb,n̄ , mn̄ I1 (Pb ) − I2 (Pb ) = O(n̄1/3 ).

(270)

We shall use the following decomposition for t ≥ n̄−
Z k,t = Z t − ηk̄ (−1)k E t .

June 26, 2017

(271)

DRAFT

43

Here,
Zt ,

X

ηk Zk,t

(272)

Zi

(273)

k

Zt ,

t
X
i=1

Et ,

t
X
(Z1,i − Z2,i ).

(274)

i=1
(max)

Some observations are in order. It follows from (269) that {Z t − tC + n̄−2/3 tζn̄

} is a sub-

martingale and that {Z t − tC} is a super-martingale with respect to the filtration {σ(Z t )}t (notice
P
that k ηk Zk,t ≤ C by concavity of mutual information and by the definition of {ηk }). Next,
observe that E t − E n̄− is a sum of i.i.d. RVs and that, by applying Lemma 12 as in the proof of
Theorem 5, we obtain the following concentration inequality for E n̄−
q


− m2 |ξ−µ1,n̄ +µ2,n̄ |+
n̄
.
P |E n̄− | ≥ ξ ≤ 2e

(275)

A. Proof of (255)
This inequality readily follows by an application of the Azuma-Hoeffding inequality:
h
i
max P τk = n̄+
k
h
i
≤ max P Z k,n̄+ −1 < γn̄
k
o
i
h
n
= max P min Z n̄− − ηk (−1)k E n̄− + (Z k,n̄+ −1 − Z k,n̄− ) < γn̄
k
k


≤ max P Z n̄− + min{Z k,n̄+ −1 − Z k,n̄− } < γn̄ + ηmax |E n̄− |
k
k


1 1/3
≤ max P Z n̄− + Z k,n̄+ −1 − Z k,n̄− < γn̄ + n̄ log n̄ + O(1/n̄)
k
2
2 !
(max)
c (n̄+ − 1)C − (n̄+ − 1)n̄−2/3 ζn̄
− γn̄ − 12 n̄1/3 log n̄ +
≤ 2 exp −
n̄+ − 1
+ O(1/n̄)
= O(1/n̄).

(276)
(277)
(278)
(279)

(280)
(281)

Here, (277) follows from the decomposition (271), (278) follows by setting ηmax = maxk ηk , (279)
follows from (275), which implies that


 
1 1/3
1
P ηmax |En̄− | ≥ n̄ log n̄ ≤ O
.
2
n̄
June 26, 2017

(282)
DRAFT

44

Finally, (280) follows from the Azuma-Hoeffding inequality [20, Th. 2.2.1] applied to the submartingale
n
on̄+ −1
(max)
Z min{t,n̄− } + 1{t > n̄− } (Z k,t − Z k,n̄− ) − tC + tn̄−2/3 ζn̄
.

(283)

t=1

B. Proof of (266)
The idea is to upper-bound E[maxk τk ] via the following stopping time:
τe , inf{t ≥ n̄− : Z t ≥ γ
en̄ or t = n̄+ }

(284)

γ
en̄ , γn̄ + n̄1/3 log n̄.

(285)

where

Intuitively, since γ
en̄ −γn̄ = n̄1/3 log n̄, the stopping time τe is rarely smaller than maxk τk . In addition,
the expectation of τe can be upper-bounded by means of Doob’s optional stopping theorem. This is
simpler than upper-bounding the expectation of the maximum maxk τk of the two stopping times.
Formally, by using that max τk ≤ n+ , we upper-bound E[maxk τk ] in terms of E[e
τ ] as follows:
h
i
h
i
E max τk ≤ E[e
τ ] + n̄+ P τe < max τk .
(286)
k

k

In the remaining part of the proof, we demonstrate that there exist constants c2 and c3 , which do
not depend on n̄, such that the following upper bounds hold for sufficiently large n̄
γ
en̄
+ c2
E[e
τ] ≤
C
i
h
n̄+ P τe < max τk ≤ c3 .
k

(287)
(288)

Consequently, we have that
h
i γ
en̄
E max τk ≤
+ c2 + c3 ≤ n̄
k
C

(289)

for all sufficiently large n̄, as desired.

June 26, 2017

DRAFT

45

Proof of (287): Applying Doob’s optional stopping theorem [23, Th. 10.10] to the sub
(max)
martingale Z t − tC + n−2/3 tζn
and the stopping time τe, we obtain
t

 
0 ≤ E Z τe − E[e
τ ] C − n−2/3 ζn(max) .

(290)

Hence, we conclude that there exists a constant c1 such that, for all sufficiently large n,
 

E Z τe
1 + c1 n−2/3 .
(291)
E[e
τ] ≤
C
 
In order to upper-bound E Z τe , we apply the Azuma-Hoeffding inequality [20, Th. 2.2.1] to the
super-martingale {Z t − tC} to obtain




c|ξ − n̄− C|2+
.
P Z n̄− ≥ ξ ≤ exp −
n̄−

(292)

We shall next apply the following lemma, which is readily proven using integration and the upper
bound Q(x) ≤ e−x

2 /2

for all x ≥ 0.


Lemma 13: Suppose that P[X ≥ ξ] ≤ exp −a|ξ − b|2+ for a > 0, b ∈ R, and ξ ∈ R. Then, for
all c ≥ b, we have
E[X1{X ≥ c}] ≤ (c +

p

π/a) exp −a|c − b|2+ .

(293)

Let a0 be a constant not depending on n such that |Zk,t | ≤ a0 with probability one. It follows that
there exists a positive constant c2 such that




 


en̄ + E Z n̄− 1 Z n̄− ≥ γ
en̄
E Z τe = E Z τe1 Z n̄− < γ


√
c|e
γn̄ − n̄− C|2+
≤γ
en̄ + a0 + (e
γn̄ + c n̄− ) exp −
n̄−
≤γ
en̄ + c2

(294)
(295)
(296)

for sufficiently large n̄. Here, (295) follows because |Zt | ≤ a0 and from Lemma 13, and (296)
√
follows because γ
en̄ − n̄− C = O( n̄ log n̄).

June 26, 2017

DRAFT

46

Proof of (288): We use the following chain of inequalities:
h
i
P τe < max τk
k
o
i
h
n
≤ P min Z τe − ηk̄ (−1)k E τe < γn̄
k
h
n
o
i
≤ P min γ
en̄ − ηk̄ (−1)k E τe < γn̄
k


en̄ − γn̄
≤ P ηmax |E τe| > γ


≤ P ηmax (|E n̄− | + |E τe − E n̄− |) > n1/3 log n


1 1/3
≤ P ηmax |E τe − E n̄− | > n log n + O(1/n)
2


1 1/3
≤ P ηmax max |E t − E n̄− | > n log n + O(1/n)
t∈{n̄− ,...,n̄+ }
2
#
"
1/3
E t − E n̄−
n̄ log n̄
≥
≤ (n̄+ − n̄− )
max
P
t∈{n̄− +1,...,n̄+ }
t − n̄−
2ηmax (t − n̄− )


cn̄2/3 log2 n̄
≤ 2(n̄+ − n̄− )
max
exp −
t∈{n̄− +1,...,n̄+ }
t − n̄−
√

≤ O( n̄ log n̄) exp −cn̄1/6 log n̄
 
1
=O
.
n̄

(297)
(298)
(299)
(300)
(301)
(302)
(303)
(304)
(305)
(306)

Here, (297) follows from (59), from (271), and from (284); (298) follows because Z τe ≥ γ
en̄
(cf. (284)); (300) follows by the triangle inequality and because γ
en̄ − γn̄ = n1/3 log n; (301) follows
from (282); and finally, (303) follows from the union bound and (304) follows from Hoeffding
inequality (indeed, E t − E n̄− is a sum of bounded i.i.d. RVs with zero mean). We conclude that
there exists a positive constant c3 such that (288) holds.
A PPENDIX H
P ROOF OF L EMMA 12
We start by showing that P[Y1 ≥ v] ≤ e−α(v−µ1 +µ2 ) and that P[Y1 ≤ v] ≤ e−α(−v−µ1 +µ2 ) for
all v ∈ R. Then, we show that the statement P[Y`−1 ≥ v] ≤ e−α(v−µ1 +µ2 ) implies P[Y` ≥ v] ≤
e−α(v−µ1 +µ2 ) for all integers ` ≥ 2. Hence, (139) follows by applying an analogous argument to
P[Y` ≤ v] and by mathematical induction.

June 26, 2017

DRAFT

47

√
Set α = c β. First note that
h
i
(2)
P[Y1 ≥ v] = P X1 ≥ v

(307)

2

≤ e−β|v−µ2 |+
≤e

(308)

2
−α(v−µ2 )+ α
4β

(309)

≤ e−αv

(310)

≤ e−α(v−µ1 +µ2 ) .

(311)

Here, (309) follows because −β|x|2+ + αx − α2 /(4β) ≤ 0 for all x ∈ R, (310) follows because
p
√ 2
2
α2 /(4β) = c2 /4 ≤ πec /4 = αc π/βec /4 ≤ −αµ2 /c ≤ −αµ2 . Using the similar inequality
α2 /(4β) ≤ αµ1 , we also have that
h
i
(2)
P[Y1 ≤ v] = P X1 ≤ v

(312)

2

≤ e−β|µ2 −v|+

(313)

2
−α(µ2 −v)+ α
4β

≤e

(314)

≤ e−α(−v−µ1 +µ2 ) .

(315)

Next, suppose that P[Y`−1 ≥ v] ≤ e−α(v−µ1 +µ2 ) for some integer ` ≥ 2. Then, we have
P[Y` ≥ v]
h
h
i
(2)
= E 1{Y`−1 ≥ 0} P X` ≥ v − Y`−1 |Y`−1
h
ii
(1)
+ 1{Y`−1 < 0} P X` ≥ v − Y`−1 |Y`−1
h

≤ E 1{Y`−1 ≥ 0} exp −β |v − Y`−1 − µ2 |2+
i
2
+ 1{Y`−1 < 0} exp −β|v − Y`−1 − µ1 |+
h

≤
sup
E 1{Z ≥ 0} exp −β|v − Z − µ2 |2+

(316)

(317)

Z:
P[Z≥v]≤exp(−α(v−µ1 +µ2 ))

≤

sup
Z:
P[Z≥v]≤exp(−α(v−µ1 +µ2 ))

+ 1{Z < 0} exp −β |v − µ1 |2+
h
i
2
E exp −β|v − Z − µ2 |+



= E exp −β|v − Z − µ2 |2+ .

June 26, 2017

i

(318)
(319)
(320)

DRAFT

48



Here, (319) follows since exp −β|v − µ1 |2+ ≤ exp −β|v − z − µ2 |2+ for all z ≥ µ1 − µ2 and
because Z satisfying P[Z ≥ µ1 − µ2 ] = 1 is a feasible solution to the maximization problem.
Moreover, the RV Z has cumulative distribution function FZ (z) = 1 − e−α|z−µ1 +µ2 |+ and (320)
thus follows because Z stochastically dominates all RVs Z satisfying P[Z ≥ v] ≤ e−α(v−µ1 +µ2 )
and because the function

f (z) , exp −β|v − z − µ2 |2+


is monotonically nondecreasing in z, which imply that E f (Z) ≥ E[f (Z)] [24].

(321)

Set z̄ = µ1 − µ2 . Then, for v ≥ µ1 = z̄ + µ2 , we have


E exp −β|v − Z − µ2 |2+
v−µ
Z 2

e−β(v−µ2

≤α

−z)2 −α(z−z̄)

Z∞
dz + α

z̄

(322)

v−µ2

Z∞
≤α

e−α(z−z̄) dz

e

√
2
2
α
β(z−v+µ2 )+ 2√
−α(v−µ2 −z̄)+ α
−
4β
β

dz + e−α(v−µ2 −z̄)

(323)

−∞
α2
4β

= αe e−α(v−µ2 −z̄)

Z∞

1

√

e− 2 (

2βz)2

dz + e−α(v−µ2 −z̄)

(324)

−∞



√

= 1 +

= 1 +

√

παe
√
β

α2
4β

α

Z∞



1 2
1
√
e− 2 ξ dξ  e−α(v−µ2 −z̄)
2π
−∞

2

παe 4β  αµ2 −(v−z̄)
√
e e
β

≤ e−α(v−z̄) .

(325)

(326)
(327)

Here, (322) holds because v ≥ z̄ + µ2 , (323) follows from
β(v − µ2 − z)2 + α(z − z̄)

2
p
α
α2
=
β(z − v + µ2 ) + √
+ α(v − µ2 − z̄) −
4β
2 β
and (327) follows from the inequality log(1 + z) ≤ z and (138) because


!
α2
α2
√
√
√
c2
4β
4β
4
παe
παe
παe
 = exp
√
1+ √
≤ exp √
≤ exp(−αµ2 ) .
β
β
β

(328)

(329)

Since µ2 ≤ 0, (327) also holds for v ≥ z̄. This implies (139) by mathematical induction.
June 26, 2017

DRAFT

49

R EFERENCES
[1] K. F. Trillingsgaard, W. Yang, G. Durisi, and P. Popovski, “Feedback halves the dispersion for some common-message broadcast
channels,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Barcelona, Spain, 2017.
[2] A. El Gamal and Y.-H. Kim, Network Information Theory.

New York: Cambridge Univ. Press, 2011.

[3] D. Blackwell, L. Breiman, and A. Thomasian, “The capacity of a class of channels,” Ann. Math. Stat., pp. 1229–1241, 1959.
[4] J. Wolfowitz, Coding Theorems of Information Theory.

Englewood Cliffs, NJ: Prentice-Hall, 1962.

[5] Y. Polyanskiy, “On dispersion of compound DMCs,” in Proc. Allerton Conf. Commun., Contr., Comput., Monticello, IL, 2013,
pp. 26–32.
[6] Y. Polyanskiy, H. V. Poor, and S. Verdú, “Channel coding rate in the finite blocklength regime,” IEEE Trans. Inf. Theory,
vol. 56, no. 5, pp. 2307–2359, 2010.
[7] B. Shrader and H. Permuter, “Feedback capacity of the compound channel,” IEEE Trans. Inf. Theory, vol. 55, no. 8, pp.
3629–3644, 2009.
[8] Y. Polyanskiy, H. V. Poor, and S. Verdú, “Feedback in the non-asymptotic regime,” IEEE Trans. Inf. Theory, vol. 57, no. 8, pp.
4903–4925, 2011.
[9] Y. Altug and A. B. Wagner, “Feedback can improve the second-order coding performance in discrete memoryless channels,”
in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Honolulu, HI, Jul. 2014.
[10] M. V. Burnashev, “Data transmission over a discrete channel with feedback. Random Transmission time,” Probl. Inf. Transm.,
vol. 12, no. 4, pp. 10–30, 1976.
[11] H. Yamamoto and K. Itoh, “Asymptotic performance of a modified Schalkwijk-Barron scheme for channels with noiseless
feedback,” IEEE Trans. Inf. Theory, vol. 25, no. 6, pp. 729–733, Nov. 1979.
[12] P. Berlin, B. Nakiboglu, B. Rimoldi, and E. Teletar, “A simple converse of Burnashev’s reliability function,” IEEE Trans. Inf.
Theory, vol. 55, no. 7, pp. 3074–3080, Jul. 2009.
[13] L. V. Truong and V. Y. F. Tan, “On the reliability function of the common-message broadcast channel with variable-length
feedback,” Jan. 2017, arXiv:1701.01530 [cs.IT].
[14] K. F. Trillingsgaard, W. Yang, G. Durisi, and P. Popovski, “Variable-length coding with stop-feedback for the common-message
broadcast channel,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Barcelona, Spain, 2016.
[15] T. M. Cover and J. A. Thomas, Elements of information theory, 2nd ed. Hoboken, NJ, USA: John Wiley & Sons, 2012.
[16] K. F. Trillingsgaard, W. Yang, G. Durisi, and P. Popovski, “Variable-length coding with stop-feedback for the common-message
broadcast channel in the nonasymptotic regime,” Jul. 2016, arXiv:1607.03519 [cs.IT].
[17] I. Csiszár and J. Körner, Information Theory: Coding Theorem for Discrete Memoryless Systems, 2nd ed. New York, NY,
USA: Cambridge Univ. Press, 2012.
[18] M. E. Machkouri and L. Ouchti, “Exact convergence rates in the central limit theorem for a class of martingales,” Bernoulli,
vol. 13, no. 4, pp. 981–999, Nov. 2007.
[19] E. Bolthausen, “Exact convergence rates in some martingale central limit theorems,” The Annals of Probability, vol. 10, no. 3,
pp. 672–688, 1982.
[20] M. Raginsky and I. Sason, Concentration of Measure Inequalities in Information Theory, Communications, and Coding, 2nd
ed.

Delft, Netherlands: Now Publisher, 2014.

[21] W. Hoeffding, “Probability inequalities for sums of bounded random variables,” J. Am. Stat. Assoc., vol. 58, no. 301, pp. 13–30,
1963.
[22] P. Billingsley, Probability and Measure, Anniversary Ed. Hoboken, NJ, USA: Wiley, 2012.

June 26, 2017

DRAFT

50

[23] D. Williams, Probability with Martingales.

New York, NY, USA: Cambridge Univ. Press, 1991.

[24] P. M. Yildiz, “Lecture notes for Microeconomics Theory III, Chapter 4,” 2015, available on MITOpenCourseware.

June 26, 2017

DRAFT

