Resolvability on Continuous Alphabets
Matthias Frey, Igor Bjelaković and Sławomir Stańczak
Technische Universität Berlin

arXiv:1801.03964v2 [] 15 Feb 2018

Abstract—We characterize the resolvability region for a large
class of point-to-point channels with continuous alphabets. In
our direct result, we prove not only the existence of good
resolvability codebooks, but adapt an approach based on the
Chernoff-Hoeffding bound to the continuous case showing that
the probability of drawing an unsuitable codebook is doubly
exponentially small. For the converse part, we show that our
previous elementary result carries over to the continuous case
easily under some mild continuity assumption.

I. I NTRODUCTION
Channel resolvability has been established as an important
tool in information-theoretic security [4], [3], [7]. In particular, strong secrecy can be derived directly from channel
resolvability. The latter, roughly speaking, is defined as the
asymptotically smallest rate of a uniform random seed that
is needed to generate a channel input for which the channel
output well approximates a given target output under some
suitable approximation measure. Potential measures that are
commonly used in the literature are the Kullback-Leibler
divergence and the variational distance. In this paper, we focus
on the latter one which is strong enough to be related to
security concepts from cryptography [11].
To the best of our knowledge, Wyner [22] was the first to
propose the problem of approximating a given output distribution over a communication channel with as little randomness
as possible on the transmitter side. In [22], he used a normalized Kullback-Leibler divergence to measure the deviation
between the actual and the target output distribution. Han and
Verdú [13] introduced the notion of channel resolvability and
formulated a similar problem except that they assumed the
variational distance as a metric. Hou and Kramer [15] considered unnormalized Kullback-Leibler divergence to measure
the distance between the distributions. The results of [4], [7],
[6] show that not only good resolvability codebooks exist
but also that the probability of drawing an unsuitable random
codebook is doubly exponentially small. Second order results
for resolvability rate are presented in [21], [6] and for MAC
in [10], [11]. Nonasymptotic results are obtained in [14].
Converse theorems for arbitrary input and output distribution (without i.i.d. assumption across channel uses) are contained in [13], [23] and [19] for MAC. A converse resolvability
result based on Kullback-Leibler divergence is shown in [22]
and a simpler argument is given in [16]. As we focus on
variational distance, these results do not carry over to our case.
The work was supported by the German Research Foundation (DFG) under
grant STA864/7-1 and by the German Federal Ministry of Education and
Research under grant 16KIS0605.

For MAC with finite alphabets and i.i.d. inputs, we have
established direct and converse results in [11]. In this work,
we extend those results to continuous alphabets in the pointto-point setting.
II. P RELIMINARIES
A channel W = ((X , F ), (Y, G), K) is given by an input
alphabet X with σ-algebra F , an output alphabet Y with σalgebra G and a stochastic kernel K which defines a stochastic
transition between the input and output alphabets. I.e., K is a
mapping from X × G to [0, 1] such that K(·, A) is measurable
for each A ∈ G and K(x, ·) is a probability measure on (Y, G)
for each x ∈ X . We assume throughout this paper that the
input and output alphabets are Polish with Borel σ-algebra. X
and Y are random variables denoting the channel input and
output respectively. Given σ-algebras F and G, we denote their
product σ-algebra by F ⊗G. Likewise, the product of n copies
of F is denoted by F ⊗n . Q
The nth extension of K is given
n
by K ⊗n (xn , j=1 Aj ) := nj=1 K(xj , Aj ). An input distribution QX on (X , F ) induces a joint Rdistribution QX,Y on
(X × Y, F ⊗ G) via QX,Y (A1 × A2 ) := A1 K(x, A2 )QX (dx)
for A1 ∈ F , A2 ∈ G. The induced output distribution is
denoted QY . A codebook for the input alphabet X with block
exp(nR)
length n and rate R is a tuple C = (C(m))m=1 , where the
codewords are C(m) ∈ X n . We define the input distribution
Pexp(nR)
induced by C as PX n |C (A) := exp(−nR) m=1
1C(m)∈A .
PX n |C and K ⊗n induce an input-output distribution PX n ,Y n |C
and output distribution PY n |C . Any QX on (X , F ) induces a
distribution PC on the set of possible codebooks by drawing all the components of all the codewords i.i.d. from X
according to QX . Given probability measures µ and ν on
(X , F ), we define the variational distance as kµ − νkTV :=
supA∈F (µ(A)−ν(A)). We say that µ is absolutely continuous
with respect to ν, in symbols µ ≪ ν, if all ν-null sets are
µ-null sets. If µ ≪ ν, the Radon-Nikodym theorem states
that there exists a measurable function dµ
dν : X → [0, ∞),
called the Radon-Nikodym
derivative,
such
that for every
R
(x)ν(dx).
Given
a
channel
and an
A ∈ F , µ(A) = A dµ
dν
input distribution, we define for any x ∈ X and y ∈ Y the
information density of (x, y) as i(x, y) := log dK(x,·)
dQY (y). By
convention, we say that the information density is ∞ on the
singular set where K(x, ·) is not absolutely continuous with
respect to QY and −∞ where the relative density is 0. Note
that if the information density is finite almost everywhere,
we can pick versions of the Radon-Nikodym derivatives such
that i(x, y) is measurable with respect to F ⊗ G [24, Chap.
5, Theorem 4.44]. In this case, we can define the mutual
information of X and Y as I(X; Y ) := EQX,Y i(x, y).

×

III. R ESOLVABILITY R EGION
Given a channel W = ((X , F ), (Y, G), K) and an output distribution QY , a rate R ∈ [0, ∞) is called achievable if there is a sequence (Cℓ )ℓ≥1 of codebooks with
strictly increasing block lengths nℓ and rate R such that
limℓ→∞ PY nℓ |Cℓ − QY nℓ TV = 0. The resolvability region
SW,QY is the closure of the set of all achievable rates.
Theorem 1. Let W = ((X , F ), (Y, G), K) be a channel such
that X is compact and for each A ⊆ Y, x 7→ K(x, A) is a
continuous mapping. Let QY be an output distribution. Define
G(QY ) := {QX :QX induces QY through W,
IQX,Y (X; Y ) < ∞}.




1
1
+√
PY n |C − QY n TV > µ 1 + √
PC
n
n


1
≤ exp − nµ exp(nR)
3

 
 (3)
 1
7 p
3
+
exp −n 2 (c−d−1) ,
+ 3π/2 exp
6
4


where



ρ
log n
+ 3√
µ := Q Q−1 (ξ) + d √
nV
V2 n
tends to ξ for n → ∞.

In order to prove these theorems, given a codebook C, we
write the variational distance as

Then
SW,QY =



R∈R:R≥

inf

QX ∈G(QY )

PY n |C − QY n

TV

PY n |C (A) − QY n (A)
A∈G ⊗n

Z 
dPY n |C n
= sup
(y ) − 1 QY n (dy n )
dQY n
A∈G ⊗n A
+

dPY n |C n
(y ) − 1
= EQY n
dQY n


IQX,Y (X; Y ) .

The inclusion “⊇” is a direct consequence of Theorem 4
in Section IV, which is a variation of Theorem 2, our main
direct result. Theorems 2 and 4 do not require the input
alphabet to be compact and in many practically relevant cases,
Theorem 2 even states that not only there exists a sequence
of codebooks witnessing that the rate is achievable, but also
that the probability of randomly drawing a “bad” codebook
vanishes doubly exponentially with increasing block length.
The inclusion “⊆” is a consequence of Theorem 5 proven in
Section V.
IV. D IRECT R ESULTS
The main result of this section is the following theorem.
Theorem 2. Given a channel W = ((X , F ), (Y, G), K),
an input distribution QX such that the moment-generating
function EQX,Y exp(t · i(X, Y )) of the information density
exists and is finite for some t > 0, and R > I(X; Y ), there
exist γ1 > 0 and γ2 > 0 such that for large enough block
lengths n, the randomized codebook distributions of block
length n and rate R satisfy


PC PY n |C − QY n TV > exp(−γ1 n)
≤ exp (exp (−γ2 n)) . (1)

With a slight refinement of the proof, we can also establish
the following second-order result.
Theorem 3. Given a channel W = ((X , F ), (Y, G), K),
an input distribution QX such that the information density
i(X, Y ) has finite central second moment V and finite absolute
third moment ρ, ξ > 0 and c > 1, suppose the rate R depends
on n in the following way:
r
V −1
log n
Q (ξ) + c
,
(2)
R = I(X; Y ) +
n
n
where Q := 1 − Φ with Φ the distribution function of the
standard normal density. Then, for any d ∈ (0, c − 1) and n
that satisfy n(c−d)/2 ≥ 6, we have

(4)

= sup

(5)

Note that throughout the proofs, we only consider codebooks C for which PY n |C is absolutely continuous with respect
to QY n . We can do this because K ⊗n (xn , ·) is absolutely
continuous with respect to QY n for almost every xn , and so
the probability of drawing a codebook for which PY n |C is not
absolutely continuous with respect to QY n is 0. The existence
of the other Radon-Nikodym derivatives that appear in this
proof can be assumed by a similar argument.
We define the typical set


1
(6)
Tε := (xn , y n ) : i(xn , y n ) ≤ I(X; Y ) + ε
n
and split PY n |C into two measures
P1,C (A) := exp(−nR)
exp(nR)

·

X

m=1

K ⊗n (C(m), A ∩ {y n : (C(m), y n ) ∈ Tε })

(7)

P2,C (A) := exp(−nR)
exp(nR)

·

X

m=1

K ⊗n (C(m), A ∩ {y n : (C(m), y n ) ∈
/ Tε }) .

(8)

We observe PY n |C = P1,C + P2,C , which allows us to split (5)
into a typical and an atypical part
PY n |C − QY n TV

+
dP1,C n
dP2,C n
= EQY n
(y ) +
(y ) − 1
dQY n
dQY n
+

dP1,C n
(y ) − 1 + P2,C (Y n ).
≤ EQY n
dQY n

(9)

We next state and prove two lemmas that we will use as tools
to bound the typical and atypical parts of this term separately.

Lemma 1 (Bound for atypical terms). Suppose QX n ,Y n (X n ×
Y n \ Tε ) ≤ µ and δ ∈ [0, 1]. Then



1
PC P2,C (Y n ) > µ(1 + δ) ≤ exp − δ 2 µ exp(nR) .
3

Proof. Observe EPC (P2,C (Y n )) = QX n ,Y n (X n × Y n \ Tε ) ≤
µ and bound
PC (P2,C (Y n ) > µ(1 + δ))
= PC (exp(nR)P2,C (Y n ) > µ exp(nR)(1 + δ))
exp(nR)

= PC

X

m=1

K ⊗n (C(m), {y n : (C(m), y n ) ∈
/ Tε })
!

> µ exp(nR)(1 + δ)


1
≤ exp − δ 2 µ exp(nR) .
3

The inequality follows from the Chernoff-Hoeffding bound [8,
Ex. 1.1] by noting that we sum probabilities (i.e. values in
[0, 1]) on the left side, that these probabilities are independently distributed under PC and that by the hypothesis of the
lemma the expectation of the term on the left is bounded by
µ exp(nR).
Lemma 2 (Bound for typical terms). Let δ, λ > 0 and define
r := exp(n(R − I(X; Y ) − ε)).

(10)

Suppose r/(6λ) ≥ 1. Then
PC
≤

!
+
dP1,C n
EQY n
(y ) − 1 > δ
dQY n
!
r
 2
3π
λ
3λ
√ + exp(−λ) exp(−δλ).
exp
1+
2
4r
r
(11)


Before we prove this lemma, we make an observation that
we need in the proof.
Lemma 3. Let f be a measurable function mapping codebooks and elements of Y n to the nonnegative reals and let
λ, δ > 0. Then
P̂ := PC (EQn f (C, y n ) > δ)


≤ EQn EPC exp(λf (C, y n )) exp(−δλ).

(12)

Proof. An application of the Chernoff bound yields

P̂ ≤ EPC (exp (λEQn f (C, y n ))) exp(−δλ).
We can then prove (12) by successive applications of Jensen’s
inequality and Fubini’s theorem.
Proof of Lemma 2. We begin by examining parts of the term
in (11) for fixed, but arbitrary C and y n and rewrite
r

dP1,C n
(y ) =
dQY n

exp(nR)

X

m=1

exp (n(−I(X; Y ) − ε))

·

dK ⊗n (C(m), ·) n
(y )1(C(m),yn )∈Tε .
dQY n

Now, we observe that the indicator function bounds the relative
density to be at most exp(n(I(X; Y )+ε)) and thus every term
in the sum to range within [0, 1] and that furthermore


dP1,C n
(y ) ≤ exp (n(−I(X; Y ) − ε))
EPC r
dQY n


exp(nR)
X
dK ⊗n (C(m), ·) n
·
EPC
(y )
dQY n
m=1
= r.

We then use these observations to yield, for any ξ > 0,
!

+ !
dP1,C n
PC exp λ
(y ) − 1
> exp(λξ)
dQY n


dP1,C n
(y ) > 1 + ξ
(13)
= PC
dQY n


dP1,C n
(y ) > (1 + ξ) r
= PC r
dQY n


2
ξ
 r ,
≤ exp − 
(14)
2 1 + ξ3
where (13) holds because the two measured events are
equal and (14) follows by the Chernoff-Hoeffding bound [17,
Theorem 2.3b]. (14) can be upper bounded by
 2 
ξ
(15)
exp − r
3

for ξ ≤ 1 (in particular) and by


ξ
exp − r
3

(16)

for ξ ≥ 1 (in particular).We will in the following use the
substitutions
a := exp(λξ)
r
r
log(a) 2r
3
b :=
−
λ.
λ
3
2r

(17)
(18)

Since we will be using (18) for integration by substitution, we
note that it implies
! r
r
3
3
d
2 3
λ
a = exp bλ
+λ
.
(19)
db
2r
2r
2r
We have, e.g. by [2, Eq. 21.9],

+ !!
dP1,C n
EPC exp λ
(y ) − 1
dQY n
!
+ !

Z ∞
dP1,C n
(y ) − 1
> a da
=
PC exp λ
dQY n
0

(20)

and upper bound this integral by splitting the integration
domain into three parts: The integration over [0, 1] can be

upper bounded by 1 (since the integrand is a probability). The
integration over [1, exp(λ)] can be upper bounded by


Z ∞
(log a)2
(21)
r
da
exp −
3λ2
1
3

Z ∞
3
3 2
3 2
b2 λ2 2r
+ λ4 2r
+ 2bλ3 2r
exp −
=
r
3λ2
0
(22)
! r
r
3
3
2 3
λ
+λ
db
+ bλ
2r
2r
2r
 2
 2 r
Z ∞
3
b
3λ
exp −
=
db · exp
λ
.
(23)
2
4r
2r
0

(21) follows by substituting (15) as well as (17) and enlarging
the integration domain to [1, ∞), which can be done because
the integrand is nonnegative. (22) follows by the rule for
integration by substitution using (18).
The integration over [exp(λ), ∞) can be upper bounded by


Z ∞
Z ∞
log a
r da =
a−r/(3λ) da (24)
exp −
3λ
exp(λ)
exp(λ)
 r
λ
exp(λ(1 − r/(3λ)))
≤ exp(−λ), (25)
≤ 6 exp −
=
r/(3λ) − 1
r
6

where (24) is by (16) and the inequalities are true because
n
i+ now apply Lemma 3 with f (C, y ) :=
hr/(6λ) ≥ 1. We
dP1,C
n
. In the resulting bound, we substitute the
dQY n (y ) − 1
bound of 1 for integration domain [0, 1] as well as (23)
and (25), substitute back (10) and note that exp(−b2 /2) is
the well-known unnormalized standard normal density, and
get (11).
Proof of Theorem 2. In order to bound the atypical term in
the sum (9), note first that for any α > 1,
QX n ,Y n (X n × Y n \ Tε )
= QX n ,Y n ({(xn , y n ) : i(xn , y n )/n > I(X; Y ) + ε})
= QX n ,Y n {(xn , y n ) : exp ((α − 1)i(xn , y n ))
≤

Z

> exp ((α − 1)n (I(X; Y ) + ε))}

X n ×Y n



exp ((α − 1)i(xn , y n )) QX,Y (d(xn , y n ))


PC P2,C (Y n ) > 2 exp(−nβ1 )


1
≤ exp − exp(n(R − β1 )) . (30)
3
To bound the typical term in (9), we apply Lemma 2 with
λ := exp(nβ2 ) and δ := exp(−nβ1 ), which yields
!

+
dP1,C n
PC EQY n
(y ) − 1 > exp(−nβ1 ) ≤
dQY n
r


3
3π
exp
exp(−n(R − I(X; Y ) − ε − 2β2 ))
1+
2
4


1
· exp − n(R − I(X; Y ) − ε − 2β2 )
2
!
+ exp(− exp(nβ2 ))

· exp (− exp(n(β2 − β1 ))) ,

(31)
as long as n is sufficiently large such that exp(n(R −
I(X; Y ) − ε))/6 ≥ 1.
We are now ready to put everything together: Considering (9), (30) and (31), an application of the union bound
yields the sum of (30) and (31) as an upper bound for
PC PY n |C − QY n TV > 3 exp(−nβ1 ) .
We choose ε < R−I(X; Y ), then β1 < (R−I(X; Y )−ε)/2
small enough to satisfy (29), then β2 such that β1 < β2 <
(R − I(X; Y ) − ε)/2, and finally we choose γ1 < β1 and
γ2 < min(R − β1 , β2 − β1 ). With these choices, we get (1)
for all sufficiently large n, thereby concluding the proof.

(26)
The existence of the moment-generating function is only
needed to ensure the doubly exponential convergence in (1).
In fact, modifying the preceding proof slightly, we can also
establish the following variation of Theorem 2.

· exp (−(α − 1)n (I(X; Y ) + ε))
α−1

Z
dK ⊗n (C(m), ·) n
(y )
= exp log
dQY n
X n ×Y n
!
· QX,Y (d(xn , y n ))

· exp (−n(α − 1) (I(X; Y ) + ε))

= exp (−n(α − 1) (I(X; Y ) + ε − Dα (QX,Y ||QX QY )))
(27)
≤ exp(−nβ1 ),

Note that since the moment-generating function EQX,Y exp(t ·
i(X, Y )) exists and is finite for some t > 0, there is
some α′ > 1 such that Dα′ (QX,Y ||QX QY ) is finite, and
thus Dα (QX,Y ||QX QY ) is finite and continuous in α for
α ≤ α′ [20]. Since Dα (QX,Y ||QX QY ) → I(X; Y ) for
α → 1, we can choose α > 1, but sufficiently close to 1
such that the bound on β1 is positive.
We can now apply Lemma 1 with µ := exp(−nβ1 ) and
δ := 1 and get

(28)

where (26) follows by applying Markov’s inequality and (28)
as long as
β1 ≤ (α − 1) (I(X; Y ) + ε − Dα (QX,Y ||QX QY )) . (29)

Theorem 4. Given a channel W = ((X , F ), (Y, G), K), an
input distribution QX such that I(X; Y ) exists and is finite,
there exist γ1 > 0 and γ2 > 0 such that for large enough
block lengths n, the randomized codebook distributions of
block length n and rate R satisfy


(32)
lim PC PY n |C − QY n TV > δ = 0
n→∞

Proof. The statement (1) is proven with an application of the
union bound, using as ingedrients (9), (30) and (31). (9) and
(31) do not require that the moment-generating function of the

information density exists and moreover, (31) can be weakened
to
!
+
Z 
dP1,C n
δ
n
lim PC
=0
(y ) − 1 QY n (dy ) >
n→∞
2
Y n dQY n
for any δ > 0. In order to find a suitable replacement for (30),
we consider
EPC (P2,C (Y n )) = QX n ,Y n (X n × Y n \ Tε ) =


n


X
1
i(xj , yj ) − I(X; Y ) > ε 
QX n ,Y n  (xn , y n ) :


n j=1

and note that by the law of large numbers, it vanishes for any
ε > 0 as n tends to infinity. So by Markov’s inequality


δ
EP (P2,C (Y n ))
PC P2,C (Y n ) >
≤2 C
2
δ
also vanishes for any δ > 0. Thus, applying the union bound
similarly as in the proof of Theorem 2, we can derive (32).
Proof of Theorem 3. We consider the typical set as defined
in (6), with
r
log n
V −1
Q (ξ) + d
.
(33)
ε :=
n
n
In preparation for bounding the atypical term in (9), we
observe
QX n ,Y n (X n × Y n \ Tε )

= QX n ,Y n ({(xn , y n ) : i(xn , y n )/n > I(X; Y ) + ε})
(
n
r n
X
1
n n
n
n
(x , y ) :
= QX ,Y
i(xk , yk ) − I(X; Y )
n
V
k=1
)!
log n
> Q−1 (ξ) + d √
nV
(34)


ρ
log n
+ 3 √ = µ,
(35)
≤ Q Q−1 (ξ) + d √
nV
V2 n
where (34) follows by substituting (33) and (35) by the BerryEsseen
√ Theorem. Knowing this, we apply Lemma 1 with δ :=
1/ n and get


√ 
1
n
PC P2,C (Y ) > µ(1 + 1/ n) ≤ exp − nµ exp(nR) .
3
(36)
In order to get a bound for the typical part of (9), we apply
√
Lemma 2 with λ := exp( n2 (R−I(X; Y )−ε)) and δ := 1/ n,
which yields
!
+

√
dP1,C n
(37)
(y ) − 1 > 1/ n
PC EQY n
dQY n
!
r
 
 n

3
3π
≤ 1+
+ exp − (R − I(X; Y ) − ε)
exp
2
4
2



1
1
n(R − I(X; Y ) − ε)
· exp − √ exp
n
2
(38)

!
 


1
3
1
+ n− 2 (c−d) exp −n 2 (c−d−1)
= 1+
4
(39)
!
r
 


3π
7
1
3
(40)
+
exp −n 2 (c−d−1) ,
≤
exp
2
4
6
r

3π
exp
2

where (38) is the application of Lemma 2 taking into account
the condition n(c−d)/2 ≥ 6 and (39) follows by substituting (2)
and (33). The inequality (40) holds because of the condition
n(c−d)/2 ≥ 6 .
Finally, we arrive at (3) by combining (36) and (40) using
the union bound.
V. C ONVERSE R ESULT
The main result of this section is Theorem 5, the converse
result for resolvability of continuous channels. We first prove
Lemma 4, a version of the theorem in which only a finite output alphabet is considered, and then show how the statement
can be generalized to continuous alphabets by looking at a
sequence of discrete approximations of the channel.
Theorem 5. Let ((X , F ), (Y, G), K) be a channel such that X
is compact and for each A ⊆ Y, x 7→ K(x, A) is a continuous
mapping. Let QY be an output distribution and (Cℓ )ℓ≥1 a
sequence of codebooks with strictly increasing block lengths
nℓ and fixed rate R such that PY nℓ |Cℓ − QY nℓ TV = δℓ ≤
1/4 with δℓ → 0. Then there is a joint probability measure
QX,Y with marginal QY for Y such that QX induces QY
through K and IQX,Y (X; Y ) ≤ R.
Lemma 4. Let ((X , F ), (Y, G), K) be a channel such that X
is compact, (Y, G) is a finite discrete space and x 7→ K(x, ·)
is a continuous mapping from X to the probability measures
on Y. Let QY be an output distribution, and (Cℓ )ℓ≥1 be a
sequence of codebooks with strictly increasing block lengths
nℓ and fixed rate R such that
PY nℓ |Cℓ − QY nℓ
with δℓ → 0. Define
(ℓ)

QX :=
(ℓ)

TV

= δℓ ≤

nℓ
1 X
PXj |Cℓ
nℓ j=1

1
4

(41)

(42)

(ℓ)

and QX,Y induced by QX through K. Then there is a strictly
(ℓi )
increasing sequence (ℓi )i≥1 such that QX,Y
converges weakly
to some QX,Y , the marginal QX induces the marginal QY
through K and I(X; Y ) ≤ R.
Proof of Lemma 4. Since X is compact, the space of measures µ on (X , F )) such that µ(X ) ≤ 1 endowed with
the weak topology is compact [1, Corollary 31.3]. There(ℓ)
fore, (QX )ℓ≥1 must have a convergent subsequence, or, put
differently, there is a strictly increasing sequence (ℓi )i≥1
(ℓ )
such that (QXi )i≥1 converges weakly to some QX̂ . By [9,
(ℓi )
Theorem A.5.9], QX,Y
converges weakly to some QX̂,Ŷ and

the marginal QX̂ induces the marginal QŶ through K. We
note
PYj |Cℓ − QY TV
1X
PYj |Cℓ ({y}) − QY ({y})
=
2

IQX,Y (X; Y ) ≤ lim inf IQ(ℓ) (X; Y ) ≤ R.
ℓ→∞

y∈Y

=

1X
2

X

y∈Y y nℓ ∈Y nℓ
yj =y

≤

1
2

y

X

nℓ

∈Y

nℓ


PY nℓ |Cℓ ({y nℓ }) − QY nℓ ({y nℓ })

PY nℓ |Cℓ ({y nℓ }) − QY nℓ ({y nℓ })

= PY nℓ |Cℓ − QY nℓ

TV

and therefore
(ℓ)

QY − QY

TV

nℓ
1 X
PY |C − QY
nℓ j=1 j ℓ

=

nℓ
1 X
≤
PYj |Cℓ − QY
nℓ j=1

≤ PY nℓ |Cℓ − QY nℓ

TV

TV

TV

.

(43)

(ℓ)
QY

converges to QY in total variation and thus, in
So
particular, weakly. Moreover, we have QY = QŶ because
marginalization is a continuous operation under the weak
topology, so we can write QX,Y instead of QX̂,Ŷ . We further
observe
nℓ R ≥ HPX nℓ |C (X) ≥ IPX nℓ ,Y nℓ |C (X nℓ ; Y nℓ )
ℓ
ℓ
X
K ⊗nℓ (xnℓ , {y nℓ })
PX nℓ ,Y nℓ |Cℓ ({(xnℓ , y nℓ )}) log
=
PY nℓ |Cℓ ({y nℓ })
nℓ
nℓ
=

x ∈X
y nℓ ∈Y nℓ
nℓ X
X
j=1 x∈X
y∈Y

X

(ℓ)

(ℓ)

QX,Y ({x, y}) log QY ({y}) + HPY nℓ |C (Y nℓ )
ℓ

x∈X
y∈Y

= nℓ IQ(ℓ) (X; Y ) − nℓ HQ(ℓ) (Y ) + HPY nℓ |C (Y nℓ )
X,Y

Y

A∈G

= PY nℓ |Cℓ − QY

ℓ

1
δℓ
1
δℓ
≥ nℓ IQ(ℓ) (X; Y ) + δℓ log
+ nℓ δℓ log
n
ℓ
X,Y
2
2|Y | 2
2|Y|

(44)



δℓ
,
≥ nℓ IQ(ℓ) (X; Y ) + δℓ log
X,Y
2|Y|

where (44) is an application of [5, Lemma 2.7]1 taking
into consideration (41) and (43). Thus, in particular, because
1 Note that the definition of the variational distance in [5] differs from the
one used in this paper by a factor of 1/2

TV

.

We can therefore apply Lemma 4 to the codebook sequence
(k−1)
(k)
)i≥1
(Cℓ(k−1) )i≥1 to obtain a subsequence (ℓi )i≥1 of (ℓi
(ℓ

y∈Y

X,Y

Proof of Theorem 5. Pick an increasing
sequence (Gk )k≥1 of
S
finite algebras on Y such that k≥1 Gk generates G. Recur(k)
sively construct sequences (ℓi )i≥1 for each k ≥ 0. Set
(k)
(0)
ℓi := i. In order to construct (ℓi )i≥1 for k > 0, first define
a discrete finite alphabet Yk := {y ⊆ Y : y is an atom of Gk }
and note that any probability measure µ on Y induces
S a
probability measure µ(k) on Yk via µ(k) (A) := µ ( A)
and conversely, µ(k) can be seen as a probability measure
on (Y, Gk ) by assigning to any set in Gk the sum of the
probabilities of all contained atoms, or, put equivalently, µ(k)
can be seen as the restriction of µ to Gk .
So for each x ∈ X , K(x, ·) induces a probability measure
K (k) (x, ·) on Yk and thus we get a stochastic kernel K (k)
and thereby a channel ((X , F ), (Yk , P(Yk )), K (k) ). x 7→
K (k) (x, ·) is a continuous map to the space of probability
vectors on Yk , because x 7→ K(x, y) is continuous for each
(k)
y ∈ Yk . Furthermore, QY induces QY in the same way. A
codebook Cℓ is also a codebook for the new channel, and we
(k)
note that also PY nℓ |Cℓ is induced by PY nℓ |Cℓ in the same way.
S
(k)
So for any A ⊆ Yk , we have PY nℓ |Cℓ (A) = PY nℓ |Cℓ ( A)
S
(k)
and QY (A) = QY ( A). Thus,


(k)
(k)
(k)
(k)
= sup PY nℓ |Cℓ (A) − QY (A)
PY nℓ |Cℓ − QY
TV
A⊆Yk

≤ sup PY nℓ |Cℓ (A) − QY (A)

i

PXj ,Yj |Cℓ ({(x, y)}) log K(x, {y})

+ HPY nℓ |C (Y nℓ )
ℓ
X (ℓ)
K(x, {y})
= nℓ
QX,Y ({x, y}) log (ℓ)
QY ({y})
x∈X
+ nℓ

the mutual information is lower semicontinuous in the weak
topology [18, Theorem 1], we can conclude

(k)

)

(k)

i
converges weakly to some QX,Y such that
such that QX,Y
(k)
(k)
QX induces QY through K (k) . Because of the subsequence
(k)
construction, all the QX,Y are compatible with each other and
seeing them as measures on (X × Y, F ⊗ Gk ), we can define
a probability measure QX,Y on (X × Y, F ⊗ G) as the unique
S
(k)
extension [2, Theorem 3.1] of k≥1 QX,Y to the σ-algebra
F ⊗ G. Since also the marginals are compatible (the marginals
for X are even identical), we can apply [12, Corollary 5.2.3]
and obtain IQ(k) (X; Y ) → IQX,Y (X; Y ). Since we know
X,Y
from the statement of Lemma 4 that for all k, IQ(k) (X; Y ) ≤
X,Y
R, it follows that IQX,Y (X; Y ) ≤ R, completing the proof of
the theorem.

R EFERENCES
[1] H. Bauer. Measure and Integration Theory. de Gruyter, 2001.
[2] P. Billingsley. Probability and Measure. Wiley, 3rd edition, 1995.
[3] M. R. Bloch and J. N. Laneman. Strong secrecy from channel
resolvability. Trans. Inf. Theory, 59(12):8077–8098, 2013.
[4] I. Csiszár. Almost independence and secrecy capacity. Problems Inform.
Transmission, 32(1):40–47, 1996.
[5] I. Csiszár and J. Körner. Information theory: coding theorems for
discrete memoryless systems. Cambridge University Press, 2011.

[6] P. Cuff. Soft covering with high probability. In ISIT, pages 2963–2967.
IEEE, 2016.
[7] I. Devetak. The private classical capacity and quantum capacity of a
quantum channel. Trans. Inf. Theory, 51(1):44–55, 2005.
[8] D. P. Dubhashi and A. Panconesi. Concentration of measure for the
analysis of randomized algorithms. Cambridge University Press, 2009.
[9] P. Dupuis and R. S. Ellis. A weak convergence approach to the theory
of large deviations, volume 902. John Wiley & Sons, 2011.
[10] M. Frey, I. Bjelaković, and S. Stańczak. MAC resolvability: First and
second order results. In CNS: Workshop on Physical-Layer Methods for
Wireless Security, pages 569–573. IEEE, 2017.
[11] M. Frey, I. Bjelaković, and S. Stańczak. The MAC resolvability region,
semantic security and its operational implications. arXiv:1710.02342,
2017.
[12] R. M. Gray. Entropy and information theory. Springer Science &
Business Media, 1st edition, 2011. https://ee.stanford.edu/∼ gray/it.pdf.
[13] T. S. Han and S. Verdú. Approximation theory of output statistics. Trans.
Inf. Theory, 39(3):752–772, 1993.
[14] M. Hayashi. General nonasymptotic and asymptotic formulas in channel
resolvability and identification capacity and their application to the
wiretap channel. Trans. Inf. Theory, 52(4):1562–1575, 2006.
[15] J. Hou and G. Kramer. Informational divergence approximations to
product distributions. In Canadian Workshop on Information Theory
(CWIT), pages 76–81. IEEE, 2013.
[16] Jie Hou. Coding for relay networks and effective secrecy for wire-tap
channels. PhD thesis, Universitätsbibliothek der TU München, 2014.
[17] C. McDiarmid. Concentration. In M. Habib, C. McDiarmid, J. RamirezAlfonsin, and B. Reed, editors, Probabilistic Methods for Algorithmic
Discrete Mathematics, pages 195–248. Springer, Berlin, Heidelberg,
1998.
[18] E. Posner. Random coding strategies for minimum entropy. Trans. Inf.
Theory, 21(4):388–391, 1975.
[19] Y. Steinberg. Resolvability theory for the multiple-access channel. Trans.
Inf. Theory, 44(2):472–487, Mar 1998.
[20] T. van Erven and P. Harremoës. Rényi divergence and Kullback-Leibler
divergence. Trans. Inf. Theory, 60(7):3797–3820, July 2014.
[21] S. Watanabe and M. Hayashi. Strong converse and second-order
asymptotics of channel resolvability. In ISIT, pages 1882–1886. IEEE,
2014.
[22] A. Wyner. The common information of two dependent random variables.
Trans. Inf. Theory, 21(2):163–179, 1975.
[23] H. Yagi. Channel resolvability theorems for general sources and
channels. In ISIT, pages 2741–2745, 2017.
[24] Erhan Çınlar. Probability and Stochastics. Springer, 2010.

