1

Asymptotic Coupling and Its Applications in
Information Theory
Lei Yu and Vincent Y. F. Tan, Senior Member, IEEE

arXiv:1712.06804v1 [] 19 Dec 2017

Abstract
A coupling of two distributions PX and PY is a joint distribution PXY with marginal distributions equal to PX and PY .
Given marginals PX and PY and a real-valued function f (PXY ) of the joint distribution PXY , what is its minimum over all
couplings PXY of PX and PY ? We study the asymptotics of such coupling problems with different f ’s. These include the maximal
coupling, minimum distance coupling, maximal guessing coupling, and minimum entropy coupling problems. We characterize the
limiting values of these coupling problems as the number of copies of X and Y tends to infinity. We show that they typically
converge at least exponentially fast to their limits. Moreover, for the problems of maximal coupling and minimum excess-distance
probability coupling, we also characterize (or bound) the optimal convergence rates (exponents). Furthermore, for the maximal
guessing coupling problem we show that it is equivalent to the probability distribution approximation problem. Therefore, some
existing results the latter problem can be used to derive the asymptotics of the maximal guessing coupling problem. We also study
the asymptotics of the maximal guessing coupling problem for two general sources and a generalization of this problem, named
the maximal guessing coupling through a channel problem. We apply the preceding results to several new information-theoretic
problems, including exact intrinsic randomness, exact resolvability, channel capacity with input distribution constraint, and perfect
stealth and secrecy communication.
Index Terms
Coupling, Maximal Guessing, Intrinsic Randomness, Channel Resolvability, Perfect Stealth and Secrecy

I. I NTRODUCTION
A coupling of two probability distributions PX and PY is a joint distribution PXY such that the marginal on X and Y are
PX and PY respectively. Given two marginal distributions PX and PY and a function f (PXY ) of the joint distribution PXY ,
what is the minimum of f (PXY ) over all couplings PXY of PX and PY ? This problem been studied for different functions
f [1]–[4]. In this work, we investigate asymptotics of several coupling problems for product marginal distributions, when the
dimension of the distributions tends to infinity. These problems include the maximal coupling problem, the minimum distance
coupling problem, the maximal guessing coupling problem, and the minimum entropy coupling problem (or the maximum
mutual information coupling problem). Our results have several applications in information theory, including the following:
1) Exact intrinsic randomness: The intrinsic randomness is the problem in determining the amount of randomness contained
∞
in a source [5]. Given an arbitrary general source X = {X n }n=1 (usually called the coin source), we try to approximate,
∞
by using X = {X n }n=1 , a uniform random number with as large rates as possible. Vembu and Verdú [5] and Han [6]
determined the supremum of achievable uniform random number generation rates, by invoking the information spectrum
method. In this paper, we consider a new variation of this problem, named the exact intrinsic randomness. We require
the output to be exactly a uniform random number. Since in general there is no function satisfying such requirement, we
relax the mapping to be an asymptotic function (i.e., the mapping asymptotically almost surely approaches some target
function as the blocklength goes to infinity; see Definition III.2), instead of a function.
2) Exact resolvability: The channel resolvability problem is the problem of determining how much information needed to
simulate a random process through a given channel so that it approximates a target output distribution. This problem
was first studied by Han and Verdú [7]. In [7], the total variation (TV) distance and the normalized relative entropy
(Kullback-Leibler divergence) were used to measure the level of approximation. The resolvability problem with the
unnormalized relative entropy was studied by Hayashi [8], [9]. Recently, Liu, Cuff, and Verdú [10] and Yu and Tan
[11] extended the theory of resolvability by respectively using the so-called Eγ metric with γ ≥ 1 and various Rényi
divergences to measure the level of approximation. In this paper, we define a new variation of the channel resolvability
problem, named exact channel resolvability. We now require the output to exactly match the target distribution. Again
since in general there is no function satisfying such requirement, we relax the mapping to be an asymptotic function.
A related problem named exact common information was studied by Kumar, Li, and Gamal [12], where different from
our definition, they required the mapping to be a function but variable-length codes are allowed. For their problem, to
obtain the exact output distribution, the input, in general, does not follow the uniform distribution. Hence Kumar, Li,
and Gamal’s definition is input-distribution sensitive, in contrast to our definition here.
The authors are with the Department of Electrical and Computer Engineering, National University of Singapore (Emails: leiyu@nus.edu.sg, vtan@nus.edu.sg).
V. Y. F. Tan is also with the Department of Mathematics, National University of Singapore.

2

3) Perfect stealth and secrecy communication: In [13], Hou and Kramer defined a new security measure—effective secrecy—
for wiretap channels that includes not only reliability and secrecy but also stealth. They used ideas from channel
resolvability to study the effective secrecy capacity (the maximum rate can be transmitted in the stealthy and secret
way) of wiretap channels, where they used the relative entropy to measure the level of secrecy and stealth. In contrast,
we generalize the effective secrecy problem by forcing the channel output to exactly match the target distribution instead
asymptotically. Hence our version can be considered as a perfect stealth and secrecy communication problem.
A. Main Contributions
Our main contributions are as follows:
1) We study the asymptotics of several coupling problems, including the problems of maximal coupling, minimum distance
coupling, maximal guessing coupling problem, and minimum entropy coupling problem (or maximum mutual information
coupling problem). We characterize the limiting values of these coupling problems as the dimension goes to infinity.
We show that they typically converge at least exponentially fast to the limits. Moreover, for the maximal coupling and
minimum excess-distance probability coupling problems, we also characterize the optimal convergence rates of these
two coupling problems. Interestingly, product couplings achieve the optimal limiting values of these coupling problems,
but they cannot achieve the optimal convergence rates. Hence for these two problems, non-product couplings strictly
outperform product couplings in the exponent sense. Furthermore, we show the maximal guessing coupling problem is
equivalent to the traditional probability distribution approximation problem [6, Sec. 2.1]. Therefore, some existing results
on the latter problem can be used to derive asymptotic results on the former problem.
2) We also consider the asymptotics of the maximal guessing coupling problem for two general sources and a generalization
of this problem, named the maximal guessing coupling through a channel problem. We derive upper and lower bounds for
the fundamental limits of these two problems. As a by-product, these upper bounds and lower bounds are also bounds for
the fundamental limits of the general source-channel resolvability problem, in which the source and channel are general
and the source is a part of the channel input.
3) We apply the preceding results to several novel information-theoretic problems, including the exact intrinsic randomness,
exact resolvability, channel capacity with input distribution constraint, and perfect stealth and secrecy communication
problems. For the exact intrinsic randomness and exact source resolvability problems, we show that they are respectively
equivalent to the traditional (approximate) intrinsic randomness and source resolvability problems. For the exact resolvability problem, we completely characterize the optimal rate for full-rank channels. For the problem of channel capacity
with an input distribution constraint, we show that the channel capacity under condition that the input distribution is
constrained to be some product distribution is the Gäcs-Körner common information between the channel input and the
channel output. For perfect stealth and secrecy communication, we show that 1) the perfect stealth-secrecy capacity is
positive if and only if the wiretap channel is a PZ -redundant channel; 2) for full-rank wiretap channels, the perfect
stealth-secrecy capacity is zero, and the perfect stealth capacity (the maximum rate can be transmitted in the perfectly
stealthy way) is the Gäcs-Körner common information CGK (X; Y ), where PX is the unique distribution that induces PZ
through PZ|X .
B. Notation
We use PX (x) to denote the probability distribution of a random variable X, which is also shortly denoted as P (x) (when
the random variable X is clear from the context). We also use PX , PeX , and QX to denote various probability distributions with
alphabet X . The set of probability distributions on X is denoted as P (X ), and the set of conditional probability distributions
on Y given a variable
P in X is denoted as P (Y|X ) := PY |X : PY |X (·|x) ∈ P (Y) , x ∈ X . Given PX and PY |X , we write
[PY |X ◦ PX ](y) := x PP
Y |X (y|x)PX (x).
n
We use Txn (x) := n1 i=1 1 {xi = x} to denote the type (empirical distribution) of a sequence xn , and TX to denote a
n
type of sequences in X . For a type TX , the type class (set of sequences having the same type TX ) is denoted by TTX . The
set of types of sequences in X n is denoted as Pn (X ) := {Txn : xn ∈ X n }. The -typical set relative to QX is denoted as
Tn (QX ) := {xn ∈ X n : |Txn (x) − QX (x)| ≤ QX (x) , ∀x ∈ X }. For brevity, we sometimes write Tn (QX ) as Tn . Other
notation generally follow the book by Csiszár and Körner [14].
The total variation distance between two probability mass functions P and Q with a common alphabet X is defined by
1X
|P − Q| :=
|P (x) − Q(x)|.
(1)
2
x∈X

By the definition of -typical set, we have that for any xn ∈ Tn (QX ), |Txn − QX | ≤ 2 .
We use P X or P Y |X to denote the vector or matrix form of PX or PY |X . We use P ⊗n to denote n-fold Kronecker product
of a vector or matrix P . We use Z to denote a sequence of random variables {Zn }∞
n=1 .

3

For any given sequence of random variables Z = {Zn }∞
n=1 , we introduce quantities which play an important role in
information spectrum methods [6]. For δ ∈ [0, 1], δ-limit superior in probability


δ-p- lim sup Zn := inf α : lim sup P{Zn > α} ≤ δ .
(2)
n→∞

n→∞

For δ = 0, p- lim supn→∞ Zn := 0-p- lim supn→∞ Zn and p- lim inf n→∞ Zn := −(p- lim supn→∞ (−Zn )). Furthermore,
P
(y|x)
ıX;Y (x; y) := log YP|X
is the information density, and ıX (x) := ıX;X (x; x) = log PX1(x) is the entropy density. We define
Y (y)
H(Z) := p- lim supn→∞ ıZn (Zn ) and H(Z) := p- lim inf n→∞ ıZn (Zn ).
.
˙ g(n) if lim supn→∞ 1 log f (n) ≤ 0. In addition, f (n) =
˙ g(n) and
Finally, we write f (n) ≤
g(n) if and only if f (n) ≤
n
g(n)
˙
g(n) ≤ f (n).
C. Preliminaries
Definition I.1. The set of couplings of PX ∈ P (X ) and PY ∈ P (Y) is defined as
C(PX , PY ) := {QXY ∈ P (X × Y) : QX = PX , QY = PY }

(3)

Any QXY ∈ C(PX , PY ) is called a coupling of PX , PY .
Definition I.2. The maximal equality-probability over couplings of two distributions PX , PY ∈ P (X ) is defined as
M(PX , PY ) :=

max

PXY ∈C(PX ,PY )

P {Y = X} .

(4)

Any QXY ∈ C(PX , PY ) achieving M(PX , PY ) is called a maximal coupling of PX , PY .
The maximal coupling problem has the following property.
Lemma I.1 (Maximal Coupling Equality). [1] Given two distributions PX and PY , we have
M(PX , PY ) = 1 − |PX − PY |.

(5)

n
Assume PX , QX are two distributions defined on a set X . If PX = QX , then obviously, |PX
− QnX | = 0 for all n ∈ N. If
PX 6= QX , the following lemma holds.

Lemma I.2 (Asymptotics of Total Variation). [15, Theorem 11.9.1] Assume PX , QX are two distinct distributions defined on
n
− QnX | → 1 exponentially fast as n → ∞. More explicitly, the exponent is
a set X . Then |PX
lim −

n→∞

1
n
log (1 − |PX
− QnX |) = min max {D(RX kPX ), D(RX kQX )}
n
RX ∈P(X )
= B(PX , QX ),

(6)
(7)

where
B(PX , QX ) := max − ln
0≤λ≤1

X

PX (x)λ QX (x)1−λ

(8)

x

denotes the Chernoff information between PX and QX .
n
Remark I.1. Statement 2 of this lemma is unsurprising since on the one hand, 1 − |PX
− QnX | is the smallest type-I plus
n
n
type-II error of a binary hypothesis test between PX and QX (see, for example, [16, Theorem 13.1.1]); and on the other hand,
B(PX , QX ) is the exponent of this error probability [15, Theorem 11.9.1].

II. M AXIMAL C OUPLING AND M INIMUM D ISTANCE C OUPLING
In this section, we focus on asymptotic behaviors of two basic coupling problems: the maximal coupling problem and the
minimum distance coupling problem.
A. Maximal Coupling
n
We first consider the asymptotic behavior of maximal equality-probability M(PX
, PYn ). First, it is obvious that if PX = PY ,
n
n
then M(PX , PY ) = 1 for all n ∈ N. Furthermore, the optimal coupling for this case is PXY (x, y) = PX (x)1{y = x}. On the
other hand, if PX 6= PY , we have the following theorem.

Proposition II.1 (Maximal Coupling). Assume PX , PY are two distinct distributions defined on a set X . Then given product
n
n
marginal distributions PX
and PYn , we have M(PX
, PYn ) → 0 exponentially fast as n → ∞. More explicitly, the exponent is
lim −

n→∞

1
n
log M(PX
, PYn ) = min max {D(QkPX ), D(QkPY )} = B(PX , PY ),
Q
n

(9)

4

n
where B(PX , PY ) is defined in (8). A product coupling PX n Y n = PXY
with PXY achieving M(PX , PY ) only achieves the
exponent − log M(PX , PY ) = − log (1 − |PX − PY |), which is suboptimal in general, i.e.,

B(PX , PY ) ≤ − log (1 − |PX − PY |) .

(10)

Proof: We prove Statement 2) using a property of the TV distance. According to the maximal coupling equality (Lemma I.1)
and Lemma I.2, we have
n
n
M(PX
, PYn ) = 1 − |PX
− PYn |
.
= e−n minQ∈P(X ) max{D(QkPX ),D(QkPY )} .

(11)
(12)

Hence the optimal exponent is minQ∈P(X ) max {D(QkPX ), D(QkPY )} = B(PX , PY ).
n
For a product coupling PX n Y n = PXY
with PXY achieving M(PX , PY ), we have
n

P {Y n = X n } = P {Y = X} .

(13)

Hence the best exponent for product couplings is − log M(PX , PY ) = − log (1 − |PX − PY |) .
The following example shows the inequality in (10) can be strict.
Example II.1. PX = { 12 , 12 }, PY = { 14 , 34 } then
min max {D(QkPX ), D(QkPY )} ≤ D(PX kPY ) =
Q

2
1 1
+ log < − log (1 − |PX − PY |) = 2.
2 2
3

(14)

B. Minimum Distance Coupling – Transportation Theory
Next we consider the minimum (expected) distance coupling problem, which is the main problem studied in transportation
theory. The Wasserstein metric is a special case of this coupling problem by specializing the distance measure to be the
quadratic distortion measure.
Define an additive function (general distance or distortion)
n

d(xn , y n ) :=

1X
d(xi , yi )
n i=1

(15)

where d(x, y) is some arbitrary function (distance) of x, y.
Definition II.1. The minimum (expected) distance over couplings of two distributions PX , PY is defined as
D(PX , PY ) :=

min

PXY ∈C(PX ,PY )

Ed(X, Y ).

(16)

Any QXY ∈ C(PX , PY ) achieving D(PX , PY ) is called a minimum (expected) distance coupling of PX , PY .
n
Then given two marginal product distributions PX
and PYn , the minimum expected distance over couplings of PX , PY is
clearly
n
D(PX
, PYn ) = D(PX , PY ).
(17)

Next we consider another important coupling problem.
Definition II.2. The minimum excess-distance probability over couplings of two distributions PX , PY is defined as
ed (PX , PY ) :=
D

min

PXY ∈C(PX ,PY )

P {d(X, Y ) > d} .

(18)

ed (PX , PY ) is called a minimum excess-distance probability coupling of PX , PY .
Any QXY ∈ C(PX , PY ) achieving D
The excess-distance probability (or excess-distortion probability) is an important distortion measure in information theory
[4], [6]. An asymptotic result for the problem of minimum excess-distance probability coupling is stated in the following
theorem. The proof is provided in Appendix A.
Proposition II.2 (Minimum Excess-Distance Probability Coupling). Given two distributions PX and PY , we have:
ed (P n , P n ) → 1 exponentially fast as n → ∞. Moreover, define the exponent
1) If D(PX , PY ) > d, D
X
Y


1
ed (P n , P n ) .
E(d) := lim inf − log 1 − D
X
Y
n→∞
n
Then
E(d) =
min
max {D(QX kPX ), D(QY kPY )} ,
QXY :EQ d(X,Y )≤d

(19)
(20)

5

n
ed (PX , PY ) only achieves the exponent
However, an optimal product coupling PX n Y n = PXY
with PXY achieving D


max −td − log Ee−td(X,Y ) ≤ E(d).
(21)
t≥0

ed (P n , P n ) → 0 at least exponentially fast as n → ∞. Moreover, define the exponent
2) If D(PX , PY ) < d, D
X
Y
1
ed (P n , P n ).
log D
X
Y
n


E(d) ≥ max td − log Eetd(X,Y ) .

E(d) := lim inf −
n→∞

Then

t≥0

(22)
(23)


ed (P n , P n ) ≤ 1. An optimal product coupling PX n Y n = P n with PXY achieving
3) If D(PX , PY ) = d, 21 + O √1n ≤ D
X
Y
XY

ed (PX , PY ) achieves the lower bound 1 + O √1 .
D
2

n


ed (PX , PY ) = 1 ≤ d.
Remark II.1. For the first case, the exponent is infinity if inf d D
III. M AXIMAL G UESSING C OUPLING
For the maximal coupling and minimum distance coupling problems, we showed that product couplings suffice to achieve
the optimal limiting values of maximal equality-probability and minimum excess-distance probability (although they cannot
achieve the optimal exponents). In the following, we consider several coupling problems for which product couplings are not
optimal in achieving the optimal limiting values.
A. Maximal Guessing Coupling: Memoryless Sources
Next we define a new coupling problem, named the maximal guessing coupling problem.
Definition III.1. The maximal guessing probability over couplings of PX , PY is defined as
G(PX , PY ) :=

max

max P {Y = f (X)} .

PXY ∈C(PX ,PY ) f :X →Y

(24)

Any QXY ∈ C(PX , PY ) achieving G(PX , PY ) is called a maximal guessing coupling of PX , PY . Moreover, if a maximal
guessing coupling satisfies G(PX , PY ) = 1, then we call it deterministic coupling. Given a sequence of distribution pairs
(PX n , PY n ), if a sequence of maximal guessing couplings {QX n ,Y n }n∈N satisfies G(PX n , PY n ) → 1 as n → ∞, then
{QX n ,Y n }n∈N is called an asymptotically deterministic coupling.
Besides, we introduce a new concept, named the asymptotic function.
Definition III.2. We say Y n is an asymptotic function of X n if limn→∞ P {Y n = fn (X n )} = 1 for some sequence of
functions {fn }∞
n=1 .
Hence under the asymptotically deterministic coupling {QX n ,Y n }n∈N , Y n is an asymptotic function of X n . Furthermore,
the quantity maxf P {Y = f (X)} is called the guessing probability; see [17]–[20]. Note that here and also in these papers,
the guessing terminal is only allowed to guess once; however, in [21]–[24] it is only allowed to guess multiple times.
The deterministic coupling and asymptotically deterministic coupling are closely related to the distribution matching problem
[25], [26], which is the following. Given a sequence of distribution pairs (PX n , PY n ), find a sequence of distributions PW n and
a sequence of deterministic couplings of (PW n , PY n ) such that PW n and PX n are asymptotically equal under a normalized
or unnormalized divergence measure. If we weaken the couplings to be a sequence of asymptotically deterministic couplings,
and strengthen the constraint on the closeness of PW n and PX n to be the equality PW n = PX n , then the distribution matching
problem becomes the asymptotically deterministic coupling problem. That is, given a sequence of distribution pairs (PX n , PY n ),
we would like to find a sequence of couplings of (PX n , PY n ) such that G(PX n , PY n ) → 1 as n → ∞. Furthermore, our
results concerning maximal guessing couplings or asymptotically deterministic couplings will be applied to information-theoretic
problems in Sections IV–VII.
By the maximal coupling equality (Lemma I.1), we can prove the following property of maximal guessing coupling, which
shows the equivalence between the maximal guessing coupling problem and probability distribution approximation problem [6].
Definition III.3. Define the minimum conditional α-Rényi entropy over couplings of two distributions PX , PY as
(c)
Hα
(PX , PY ) :=

with

min

PXY ∈C(PX ,PY )

Hα (Y |X)


! α1 
X
α
.
log E 
PYα|X (y|X)
Hα (Y |X) :=
1−α
y

(25)

(26)

6

(c)

We also call the minimum conditional ∞-Rényi entropy H∞ (PX , PY ) over couplings of PX , PY as minimum conditional
(c)
min-entropy, and the minimum conditional 1-Rényi entropy H1 (PX , PY ) over couplings of PX , PY (shortly denoted as
(c)
H (PX , PY )) as minimum conditional entropy.
Theorem III.1 (Maximal Guessing Coupling Equality). The maximal guessing coupling problem is equivalent to the probability
distribution approximation problem. That is,
(c)

1 − e−H∞ (PX ,PY ) = G(PX , PY ) = min |PY − Pf (X) |.
f

(27)

Moreover, assume that f is an optimal function for the probability distribution approximation problem, and Pf (X),Y is a
maximal coupling of PX , PY , i.e., f is a minimizer of minf |PY − Pf (X) | and Pf (X),Y is a maximizer of the problem
maxPf (X),Y ∈C(Pf (X) ,PY ) P {Y = f (X)}. Then PX PY |f (X) is a maximal guessing coupling of PX , PY .
Proof: Exchanging minimization operations, we have
G(PX , PY ) = min
f

min

PXY ∈C(PX ,PY )

P {Y 6= f (X)} .

(28)

Now we prove that given a function f ,
min

PXY ∈C(PX ,PY )

P {Y 6= f (X)} =

min

Pf (X),Y ∈C(Pf (X) ,PY )

P {Y 6= f (X)} .

(29)

Denote QX,Y := arg minPXY ∈C(PX ,PY ) P {Y 6= f (X)} and Qf (X),X,Y (v, x, y) := QX,Y (x, y)1{v = f (x)}. Then we have
min

PXY ∈C(PX ,PY )

P {Y 6= f (X)} = PQX,Y {Y 6= f (X)}

(30)

= PQf (X),Y {Y 6= f (X)}

(31)

≥

(32)

min

Pf (X),Y ∈C(Pf (X) ,PY )

P {Y 6= f (X)} .

On the other hand, denote Qf (X),Y := arg minPf (X),Y ∈C(Pf (X) ,PY ) P {Y 6= f (X)} and Qf (X),X,Y (v, x, y) := PX (x)1{v =
f (x)}QY |f (X) (y|v) = PX (x)QY |f (X) (y|f (x))1{v = f (x)}. Then we also have
min

Pf (X),Y ∈C(Pf (X) ,PY )

P {Y 6= f (X)} = PQf (X),Y {Y 6= f (X)}

(33)

= PQX,Y {Y 6= f (X)}

(34)

≥

(35)

min

PXY ∈C(PX ,PY )

P {Y 6= f (X)} .

Combining (32) and (35) we have the desired equality (29).
Substitute (29) into (28), then we have
min

PXY ∈C(PX ,PY )

min P {Y 6= f (X)} = min
f

f

min

Pf (X),Y ∈C(Pf (X) ,PY )

P {Y 6= f (X)}

= min |PY − Pf (X) |,
f

(36)
(37)

where (37) follows from Lemma I.1.
n
n
Furthermore, the first equality of (27) follows from maxf P {Y = f (X)} = e−H∞ (Y |X ) .
By Theorem III.1, to solve the maximal guessing coupling problem, we only need to compute
min PY − Pf (X) ,

(38)

X

(39)

f (x)

which is equivalent to
min

{A(y)}y

|PY (y) − PX (A(y))| ,

y

where {A(y)}y is a partition of X . This problem involving the search for an optimal partition has been shown to be NP-hard.
Proposition III.1. [27] The problem in (39) is NP-hard.
However, when we consider the asymptotic scenario, the optimal limiting value of this coupling problem can be easily
determined. Furthermore, we also provide bounds on the rates of convergence of the coupling problems to their limiting
values.
n
Theorem III.2 (Maximal Guessing Coupling). Given two product marginal distributions PX
and PYn , we have:
n
n
1) If H(X) > H(Y ), then G(PX , PY ) → 1 at least exponentially fast as n → ∞. Define the optimal exponent as

E (PX , PY ) := lim inf −
n→∞

1
n
log (1 − G(PX
, PYn )) .
n

(40)

7

Then E (PX , PY ) ≥ Eiid (PX , PY ) with
Eiid (PX , PY ) :=

1
max t (H1+t (X) − H1−t (Y )) .
2 t∈[0,1]

n
2) If H(X) < H(Y ), then G(PX
, PYn ) → 0 at least exponentially fast as n → ∞. Define the optimal exponent as
1
n
E (PX , PY ) := lim inf − log G(PX
, PYn ).
n→∞
n
Then
E (PX , PY ) ≥ sup min {δ (PX ), δ (PY ), (1 − )H(Y ) − (1 + )H(X)} ,

(41)

(42)
(43)

∈(0,1)
(min)

(min)

and PX
:= minx:PX (x)>0 PX (x).
with δ (PX ) := 31 2 PX
n
3) If H(X) = H(Y ), then G(PX
, PYn ) ≥ G(PX , PY )n for all n.
n
n
Since maxfn P {Y n = fn (X n )} = e−H∞ (Y |X ) , the three statements above are respectively equivalent to
(c)
n
1) If H(X) > H(Y ), then H∞ (PX
, PYn ) → 0 at least exponentially fast as n → ∞.
(c)
n
2) If H(X) < H(Y ), then H∞ (PX
, PYn ) → ∞ linearly as n → ∞.
(c)
(c)
n
3) If H(X) = H(Y ), then H∞ (PX , PYn ) ≥ nH∞ (PX , PY ) for all n.
Remark III.1. The exponent for the case H(X) ≥ H(Y ) can be infinity if there exists a coupling PXY such that Y can be
expressed as a function of X.
Remark III.2. By the equivalence between the maximal guessing coupling problem and probability distribution approximation
problem (Theorem III.1), the exponential bounds given in the theorem above are also bounds for the probability distribution
approximation problem minf |PY − Pf (X) |.
n
Remark III.3. The theorem above implies given two product distributions PX
and PYn with H(X) > H(Y ), there exists a
n
n
joint distribution PX Y satisfying the following property
X
min
|PY n (y n ) − PX n (A(y n ))| → 0, as n → ∞,
(44)
n
{A(y )}yn

yn

where {A(y n )}yn is a partition of X n . Hence the probability values of PX n asymptotically forms a refinement of the probability
values of PY n in the sense of (44). This is just a restatement of the soft-covering lemma [28].
Remark III.4. Besides the first-order result above, the second-order result can be obtained as well by using the equivalence
between maximal guessing coupling problem and probability distribution approximation problem (Theorem III.1) and the
second-order result for the probability distribution approximation problem [29].
Proof of Theorem III.2: Proof of Statement 1): From the soft-covering lemma or the probability distribution approximation
problem [6, Theorem 2.1.1] we know that if H(X) > H(Y ), there exists a sequence of functions fn (xn ) such that
|Pfn (X n ) − PY n | → 0

(45)

exponentially fast, with the exponent at least Eiid (PX , PY ). On the other hand, by the equivalence between the maximal
guessing coupling problem and the probability distribution approximation problem (Theorem III.1),
max

max P {Y n = fn (X n )} → 1

n ,P n ) f
PX n Y n ∈C(PX
n
Y

at least exponentially fast as n → ∞. Furthermore, Eiid (PX , PY ) is an exponent obtained by i.i.d. codes [11].
Proof of Statement 2):
X
P {Y n = fn (X n )} =
PX n Y n (xn , y n )1 {y n = fn (xn )}

(46)

(47)

xn ,y n

=

X

PX n Y n (xn , y n )1 {y n = fn (xn ), xn ∈ Tn (PX )}

xn ,y n

X

+

PX n Y n (xn , y n )1 {y n = fn (xn ), xn ∈
/ Tn (PX )}

(48)

xn ,y n

≤

X

PX n Y n (xn , y n )1 {y n ∈ A} + PX n ((Tn (PX ))c )

(49)

xn ,y n

= PY n (A) + PX n ((Tn (PX ))c )
=

(50)

PY n (A ∩ Tn (PY
−n(1−)H(Y )

)) + PY n (A ∩ (Tn (PY ))c ) + PX n ((Tn (PX ))c )
|A|e
+ PY n ((Tn (PY ))c ) + PX n ((Tn (PX ))c )
−n((1−)H(Y )−(1+)H(X))
−nδ (PY )
−nδ (PX )

≤
˙ e
≤

+e

+e

(51)
(52)
(53)

8

n
where A := {fn (xn ) : xn ∈ Tn (PX )}. Hence if H(X) < H(Y ), G(PX
, PYn ) → 0 exponentially fast as n → ∞.
n
Proof of Statement 3): An optimal product coupling PX n Y n = PXY with PXY achieving G(PX , PY ) achieves the lower
bound G n (PX , PY ).
The theorem above does not give an asymptotically tight expression for H(X) = H(Y ) case. However, we conjecture the
following:
n
Conjecture III.1 (Asymptotically Deterministic Coupling). Assume H(X) = H(Y ). Then G(PX
, PYn ) → 1 if and only if
G(PX , PY ) = 1 (this is also equivalent to the fact that PX and PY have the same probability values).
n
This conjecture implies when H(X) = H(Y ), G(PX
, PYn ) → 1 requires some “matched” condition on the distributions.
Next we prove the conjecture above is true if PX or PY is a uniform distribution.

Proposition III.2 (Asymptotically Deterministic Coupling with Uniform PX or PY ). Assume X = [1 : M ] and PX (x) =
1
1
M , ∀x ∈ [1 : M ] or Y = [1 : M ] and PY (y) = M , ∀y ∈ [1 : M ] for some M ∈ N, and H(X) = H(Y ) = log M . Then
n
n
G(PX , PY ) → 1 if and only if G(PX , PY ) = 1. That is, there exists a (asymptotically deterministic) coupling PX n Y n ∈
n
C(PX
, PYn ) for which Y n is an asymptotic function of X n , if and only if there exists a (deterministic) coupling PXY ∈
C(PX , PY ) for which Y is a function of X. More explicitly, for the case that PX is uniform but PY is not, we have
n
G(PX
, PYn ) ≤ αn where
!
 1

η(Y )
1
Φ − log 2 − p
(54)
αn := 1 −
2
n
nV 3 (Y )
with Φ(·) denotes the cumulative distribution function (cdf) of the standard Gaussian distribution, V (Y ) := Var [log PY (Y )]
n
, PYn ) ≤ βn
and η(Y ) := EPY [| log PY (Y ) + H(PY )|3 ]; and for the case that PY is uniform but PX is not, we have G(PX
where
!

 

 
1
1
1
1
η(X)
p
βn := 1 − sup
.
(55)
1−
Φ
log k − 1 +
k
n
k
nV 3 (X)
k>1 2
Obviously, limn→∞ αn = limn→∞ βn = 43 .
n
Proof: If G(PX , PY ) = 1, then G(PX
, PYn ) = 1 for any n, regardless of whether PX is uniform or PY is uniform.
Next we focus on the other direction.
Case 1 (PX is uniform): If G(PX , PY ) < 1, then by the assumption H(X) = H(Y ) = log M , we know that PX is uniform
but PY is not. For this case, we have

|PY n − Pfn (X n ) | ≥

1
2

X

PY n (y n )

(56)

1
y n :PY n (y n )< 2M
n


1
y : PY (y ) <
2M n
(
)
n
1X
1
1
n
= PY n y : −
log PY (yi ) > H(Y ) + log 2
2
n i=1
n
!
 1

1
η(Y )
≥
Φ − log 2 − p
,
2
n
nV 3 (Y )
1
= PY n
2



n

n

n

(57)
(58)
(59)

where (56) follows since Pfn (X n ) (y n ) ≥ M1n or Pfn (X n ) (y n ) = 0 for every y n ∈ Y n and thus |PY n (y n ) − Pfn (X n ) (y n )| ≥
PY n (y n ) for every y n such that PY n (y n ) < 2M1 n , and (59) follows from the Berry–Esseen theorem [30, Sec. XVI.5]. Hence

n
G(PX
, PYn )

= 1 − min |PY n
fn

1
− Pfn (X n ) | ≤ 1 −
2


1
η(Y )
Φ − log 2 − p
n
nV 3 (Y )


!
→

3
as n → ∞.
4

(60)

Case 2 (PY is uniform): If G(PX , PY ) < 1, then by the assumption H(X) = H(Y ) = log M , we know that PY is uniform

9

but PX is not. For this case, we have
|PY n

1
− Pfn (X n ) | ≥ sup
k>1 2



1
Pfn (X n ) (y ) − n
M
y n :Pfn (X n ) (y n )> Mkn


X
1
1
≥ sup
PX n (xn ) − n
M
k>1 2 n
k
n
X

n


(61)

(62)

x :PX n (x )> M n

!!
1
1
η(X)
−
Φ
log k − p
Φ( log k) + p
n
n
nV 3 (X) k
nV 3 (X)
!

 



1
1
1
1
η(X)
p
= sup
1−
Φ
log k − 1 +
,
2
k
n
k
nV 3 (X)
k>1

where (62) follows since to make (61) as small as possible, the function fn must be injective on the set xn : PX n (xn ) >
(63) follows from the Berry–Esseen theorem [30, Sec. XVI.5] and

X
k xn : PX n (xn ) > Mkn
1
η(X)
n
≥
PX n (x ) ≥
.
Φ( log k) + p
n
Mn
nV 3 (X)
k
n
n
1
≥ sup
2
k>1

1

η(X)



(63)
(64)
k
Mn

,

(65)

x :PX n (x )> M n

Hence
n
G(PX
, PYn )

1
= 1−min |PY n −Pfn (X n ) | ≤ 1−sup
fn
k>1 2



1
1−
k

!
 

 
1
3
1
η(X)
p
log k − 1 +
→ as n → ∞. (66)
Φ
n
k
4
nV 3 (X)

Similar to the conjecture concerning asymptotically deterministic couplings, we also have the following conjecture concerning
the deterministic couplings.
n
, PYn ) = 1 if and only if G(PX , PY ) = 1. That is, there exists a deterministic
Conjecture III.2 (Deterministic Coupling). G(PX
n
n
n
coupling PX n Y n ∈ C(PX , PY ) for which Y is a function of X n , if and only if there exists a deterministic coupling
PXY ∈ C(PX , PY ) for which Y is a function of X.

Next we prove the conjecture above for two special cases.
Proposition III.3 (Entropy Criterion of Deterministic Coupling). 1) If Hα (X) < Hα (Y ) for some α ∈ [0, ∞], then for
n
, PYn ) < 1.
any n, G(PX
n
2) If Hα (X) = Hα (Y ) for some α ∈ [0, ∞], then G(PX
, PYn ) = 1 if and only if G(PX , PY ) = 1. That is, there exists a
n
n
deterministic coupling PX n Y n ∈ C(PX , PY ) for which Y n is a function of X n , if and only if there exists a deterministic
coupling PXY ∈ C(PX , PY ) for which Y is a function of X. This is also equivalent to the fact that PX and PY have
the same set of probability values.
n
Proof: We first prove Statement 1). Suppose G(PX
, PYn ) = 1. Then

nHα (X) = Hα (X n )
n

(67)
n

= Hα (X Y )
n

(68)

≥ Hα (Y )

(69)

= nHα (Y ),

(70)

where (68) follows from (57). This contradicts with the assumption Hα (X) < Hα (Y ).
n
n
We next prove Statement 2). Obviously if G(PX , PY ) = 1 then G(PX
, PYn ) = 1. Next we prove if G(PX
, PYn ) = 1 then
G(PX , PY ) = 1.
Since in (70) we show Hα (X) ≥ Hα (Y ), and as assumed, Hα (X) = Hα (Y ), we have the equality in (70) is attained,
i.e., Hα (X n ) = Hα (Y n ). Hence Hα (X n Y n ) = Hα (X n ) = Hα (Y n ). That is, Y n is a function of X n , and X n is also a
n
function of Y n . Hence the mapping between X n and Y n is bijective, which further implies PX
and PYn have the same set of
probability values.
n
Since PX
and PYn have the same number of positive probability values, we have the support size of PX and PY are equal.
Denote the size as k, i.e., k := |supp(PX )| = |supp(PY )|. Suppose p1 ≥ p2 ≥ ... ≥ pk and q1 ≥ q2 ≥ ... ≥ qk are the
positive probability values of PX and PY , respectively, ordered in a non-increasing fashion. Then the positive probability
n
values of PX
and PYn must be pn1 ≥ pn−1
p2 ≥ ... ≥ pn−1
pk−1 ≥ pnk and q1n ≥ q1n−1 q2 ≥ ... ≥ qkn−1 qk−1 ≥ qkn . Hence
1
k
p1 = q1 , p2 = q2 , pk−1 = qk−1 , pk = qk . Next we prove pi = qi , i ∈ [3 : k − 2].

10

W

f  w

X

Y

PY |WX

Fig. 1. General source-channel resolvability.

Remove pi1 pn−i
, i ∈ [0 : n] and q1i q2n−i , i ∈ [0 : n] from the lists pn1 ≥ pn−1
p2 ≥ ... ≥ pn−1
pk−1 ≥ pnk and q1n ≥ q1n−1 q2 ≥
2
1
k
n−1
n
... ≥ qk qk−1 ≥ qk , respectively. Then the maximum values among the resulting lists are respectively pn−1
p3 and q1n−1 q3 .
1
They must be equal. Hence p3 = q3 . In the same way, we can show pi = qi , i ∈ [3 : k − 2].
1
Proposition III.4 (Deterministic Coupling with Uniform PX ). If PX (x) = M
, ∀x ∈ [1 : M ] for some M ∈ N, then for any
n
n
n
PY , G(PX , PY ) = 1 if and only if G(PX , PY ) = 1. That is, there exists a deterministic coupling PX n Y n ∈ C(PX
, PYn ) for
n
n
which Y is a function of X , if and only if there exists a deterministic coupling PXY ∈ C(PX , PY ) for which Y is a function
of X.

The proof of Proposition III.4 is provided in Appendix B.
B. Maximal Guessing Coupling: General Sources and Coupling Through a Channel
In the previous subsection, we showed the maximal guessing coupling problem is equivalent to the probability distribution
approximation problem. Hence to obtain the maximal guessing coupling of a pair of sources, we only need to solve the problem
of probability distribution approximation for these sources. Here instead, we consider a more general variation of probability
distribution approximation problem, called the general source-channel resolvability problem. This is illustrated in Fig. 1, and
will be proven to be equivalent to a maximal guessing coupling through a channel problem.
Consider a pair of distributions (PW , PZ ) and a channel PY |W X (this is a source-dependent channel which reduces to a
source-independent channel if we set PY |W X = PY |X ). Denote the output of the channel PY |W X with input X = f (W ) as
Yf . Obviously, the distribution of Yf is
X
PYf (y) =
PW (w)PY |W X (y|w, f (w)).
(71)
w

If we consider f (W ) as a guessing function and Yf as the final estimate variable of the target variable Z, then the optimization
problem minPW Z ∈C(PW ,PZ ) minf P {Z 6= Yf } can be seen as the problem of maximal guessing coupling through a channel.
It is a generalization of the maximal guessing coupling problem, since it reduces to the maximal guessing coupling problem
if the channel is set to the identity channel, i.e., PY |W X (y|w, x) = 1{y = x} for all (w, x, y).
Definition III.4. Define the maximal guessing probability through a channel PY |X over couplings of (PW , PZ ) as
G(PW , PZ |PY |X ) :=

max

max

max

PW Z ∈C(PW ,PZ ) f :W→X PY |W Z :PY |W (y|w)=PY |X (y|f (w))

P {Z = Y } .

(72)

Any QXY ∈ C(PX , PY ) achieving G(PW , PZ |PY |X ) is called a maximal guessing coupling of PX , PY through the channel
PY |X .
On the other hand, the source-channel resolvability problem is minf |PZ − PYf |. Similar to Theorem III.1, the following
theorem states the equivalence between the problem of maximal guessing coupling through a channel and the source-channel
resolvability problem.
Theorem III.3 (Maximal Guessing Coupling Through a Channel). The problem of maximal guessing coupling through a
channel is equivalent to the source-channel resolvability problem. That is,
G(PW , PZ |PY |X ) = 1 − min |PZ − PYf |.
f

(73)

Remark III.5. Note that the coupling PW Z and the channel PY |X are not independent, i.e., the channel PY |X is allowed to
be embedded into the optimal coupling PW Z . If such embedding is not allowed, then the problem reduces to
e W , PZ |PY |X ) :=
G(P

max

PW Z ∈C(PW ,PZ )

max P {Z = Y } ,
f

(74)

where the probability is taken under the distribution PW Z (w, z)PY |X (y|f (w)). However, for this problem, the equivalence
above no longer holds.

11

Proof: Exchanging minimization operations, we have
1 − G(PW , PZ |PY |X ) = min
f

min

= min
f

PZ|W Y :

= min
f

PZ|Y :

= min
f

min

PW Z ∈C(PW ,PZ ) PY |W Z :PY |W (y|w)=PY |X (y|f (w))

min

P

w,y

P

y

PZ|W Y (z|w,y)=PZ (z)

min
PZ|Y (z|y)=PZ (z)

min

PYf Z ∈C(PYf ,PZ )

P {Z 6= Y }

P {Z 6= Y }

(75)
(76)

P {Z 6= Y }

(77)

P {Z 6= Yf }

(78)

= min |PZ − PYf |,

(79)

f

where (77) follows since the optimized objective P {Z 6= Y } depends only on the joint distribution of Y, Z.
1) One-shot Bounds: Next we derive bounds for the source-channel resolvability problem.
Theorem III.4 (General Source-Channel Resolvability). 1) [28, Theorem VII.1] For any source distribution PW , codebook
distribution PX|W , and channel PY |W X , we bound the expected total variation error of the distribution of Y induced by a
randomly constructed codebook. Let B be a randomly generated collection of channel inputs x(w) ∈ X , w ∈ W, each drawn
independently according to PX|W . Let PY |C be the output distribution induced by applying the codebook. For any τ > 0, we
have
1
(80)
EC PY |C − PY ≤ P (Aτ ) + eτ /2 ,
2
where the expectation is with respect to the random codebook, and


PW (w)PY |W X (y|w, x)
Aτ := (w, x, y) : log
>τ .
(81)
PY (y)
2) Conversely, for any function f : W 7→ X , distributions PW and PZ , channel PY |W X , and τ > 0, we have
PYf − PZ ≥ P (Bτ ) − e−τ ,

(82)

where Yf is the output of the channel PY |W X with input X = f (W ), and


PW (w)PY |W X (y|w, x)
>τ .
Bτ := (w, x, y) : log
PZ (y)

(83)

Remark III.6. For any τ > 0, we have
1
P (Bτ ) − e−τ ≤ min |PZ − PYf | ≤ min |PY − PZ | + P (Aτ ) + eτ /2 .
PX|W
f
2

(84)

Proof: Statement 1) is exactly [28, Theorem VII.1], hence we only need prove Statement 2). To this end, we borrow the
ideas in [31], [32]. First, define
T := {y ∈ Y : PY (y) ≥ eτ PZ (y)} .

(85)

Then, by the definition of the TV distance, we have
|PY − PZ | ≥ PY (T ) − PZ (T ).

(86)

Here PZ (T ) can be bounded as
PZ (T ) =

X

PZ (y) ≤ e−τ

y∈T

X

PY (y) ≤ e−τ .

(87)

y∈T

Since
PY (y) =

X

P (w)PY |W X (y|w, f (w)), y ∈ Y,

(88)

w

denoting PY |W =w,X=f (w) (y) = PY |W X (y|w, f (w)), we have
X
PZ (T ) =
P (w)PY |W =w,X=f (w) {y : PY (y) ≥ eτ PZ (y)}

(89)

w

(
=

X
w

P (w)PY |W =w,X=f (w)

y:

)
X
w

τ

P (w)PY |W X (y|w, f (w)) ≥ e PZ (y) .

(90)

12

P
τ
Note that P (w)PY |W X (y|w, f (w)) ≥ eτ PZ (y) implies
w P (w)PY |W X (y|w, f (w)) ≥ e PZ (y). Hence we obtain the
following lower bound:
X

PY (T ) ≥
P (w)PY |W =w,X=f (w) y : P (w)PY |W X (y|w, f (w)) ≥ eτ PZ (y) .
(91)
w

Thus, plugging (87) and (91) into (86), we obtain Statement 2).
If consider a identity channel PY |W X (y|w, x) = 1{y = x}, the source-channel resolvability problem reduces to the sourcesource resolvability problem (using a general source to generate another general source) or equivalently, the probability
distribution approximation problem. That is, minf |PZ − PYf | = minf |PZ − Pf (W ) | where PW is a source distribution
and PZ is a target distribution. Theorem III.4 results in the following corollary.
Corollary III.1 (General Source-Source Resolvability: Probability Distribution Approximation). For any source distribution
PW and target distribution PZ , we have
min

PW Z ∈C(PW ,PZ )

P (A0τ ) − e−τ ≤ min |PZ − Pf (W ) | ≤
f

where
A0τ


:=

1
P (A0τ ) + eτ /2 ,
2
PW Z ∈C(PW ,PZ )
min

PW (w)
>τ
(w, z) : log
PZ (z)

(92)


.

(93)

2) Asymptotics: When consider asymptotics, Theorem III.4 results in the following corollary.
Corollary III.2 (General Source-Channel Resolvability). For any source distribution PW , channel PY |W X , and target
distribution PZ , we have
PX|W :p- lim supn→∞

inf

1
1
n
n
n
n
n i(W X ;Y )− n i(W )≤0

lim sup |PY n − PZ n |
n→∞

≤ lim sup min |PZ n − PYfnn |
n→∞

≤

(94)

fn

PX|W :p- lim supn→∞

inf

1
1
n
n
n
n
n i(W X ;Y )− n i(W )<0

lim sup |PY n − PZ n | .

(95)

n→∞

Moreover, if consider a identity channel PY |W X (y|w, x) = 1{y = x}, Corollary III.2 results in the following corollary.
Corollary III.3 (General Source-Source Resolvability: Probability Distribution Approximation). For any source distribution
PW and target distribution PZ , we have (94)-(95) with i(W n X n ; Y n ) replaced by i(X n ) and Y n replaced by X n . Equivalently,
inf

δ≥0,PW Z ∈C(PW ,PZ ):δ -p- lim supn→∞

1
1
n
n
n i(Z )− n i(W )≤0

δ

≤ lim sup min |PZ n − Pfn (W n ) |
n→∞

≤

(96)

fn

inf

δ≥0,PW Z ∈C(PW ,PZ ):δ -p- lim supn→∞

1
1
n
n
n i(Z )− n i(W )<0

δ,

(97)

where C(PW , PZ ) := {PW Z : PW n Z n ∈ C(PW n , PZ n ), ∀n}.
3) Maximal Guessing Coupling for General Sources and Channels: According to the equivalence between the maximal
guessing coupling problem and probability distribution approximation problem (Theorem III.1) and the equivalence between
the problem of maximal guessing coupling through a channel and the problem of source-channel resolvability (Theorem III.3),
we have the following corollary.
Corollary III.4 (Maximal Guessing Coupling for General Sources and Channels). The bounds given in Theorem III.4 and
Corollary III.2 are also bounds for the maximal guessing coupling problem through a channel. The bounds given in Corollaries
III.1 and III.3 are also bounds for the maximal guessing coupling problem.
C. Application to Minimum Entropy Coupling
The problems of minimum entropy coupling and maximum mutual information coupling were first studied in [3]. In this
subsection, we study the asymptotics of these coupling problems. In [3], the authors showed solving the minimum entropy
coupling problem or maximum mutual information coupling problem is NP-hard. However, in this section, we show that is
not the case for the asymptotic regime. The following corollaries can be easily obtained from combining Theorem III.2 and
Fano’s inequality. Hence we omit the proofs here.
Corollary III.5 (Minimum Conditional Entropy Coupling). Recall from Definition III.3 the minimum conditional entropy
n
H(c) (PX , PY ) := minPXY ∈C(PX ,PY ) H(Y |X) over couplings of PX , PY . Then given two product marginal distributions PX
n
and PY , we have

13

n
1) H(c) (PX
, PYn ) − n max{0, H(Y ) − H(X)} → 0 as n → ∞ if H(X) 6= H(Y );
(c)
n
2) H (PX , PYn ) ≤ nH(c) (PX , PY ) for all n if H(X) = H(Y ).

Corollary III.6 (Minimum Joint Entropy Coupling). Define the minimum joint entropy over couplings of two distributions
n
PX , PY as H(PX , PY ) := minPXY ∈C(PX ,PY ) H(XY ). Then given two product marginal distributions PX
and PYn , we have
n
1) H(PX
, PYn ) − n max{H(X), H(Y )} → 0 as n → ∞ if H(X) 6= H(Y );
n
2) H(PX , PYn ) ≤ nH(PX , PY ) for all n if H(X) = H(Y ).
Corollary III.7 (Maximum Mutual Information Coupling). Define the maximum mutual information over couplings of two
n
distributions PX , PY as I(PX , PY ) := maxPXY ∈C(PX ,PY ) I(X; Y ). Then given two product marginal distributions PX
and
n
PY , we have
n
1) I(PX
, PYn ) − n min{H(X), H(Y )} → 0 as n → ∞ if H(X) 6= H(Y );
n
2) I(PX , PYn ) ≥ nI(PX , PY ) for all n if H(X) = H(Y ).
Corollary III.8 (Maximum GK Common Information Coupling). Define the maximum GK common information over couplings
of two distributions PX , PY as CGK (PX , PY ) := maxPXY ∈C(PX ,PY ) CGK (X; Y ). Then given two product marginal distributions
n
PX
and PYn , we have
n
1) CGK (PX
, PYn ) − n min{H(X), H(Y )} → 0 as n → ∞ if H(X) 6= H(Y );
n
2) CGK (PX , PYn ) ≥ nCGK (PX , PY ) for all n if H(X) = H(Y ).
Corollary III.9 (Maximum Conditional Mutual Information Coupling). Define the maximum conditional mutual information
over couplings of two distributions PX , PY Z as I (c) (PX , PY Z ) := maxPXY Z ∈C(PX ,PY Z ) I(X; Y |Z). Then given two product
n
marginal distributions PX
and PYnZ , we have
n
1) I (c) (PX
, PYnZ ) − n min{H(X), H(Y |Z)} → 0 as n → ∞ if H(X) 6= H(Y |Z);
(c)
n
2) I (PX , PYnZ ) ≥ nI (c) (PX , PY Z ) for all n if H(X) = H(Y |Z).
n n
PZ to generate (Y n , Z n ) with joint distribution PYnZ if
For Corollary III.9, we use (X n , Z n ) with joint distribution PX
n
n
n
n
H(X) > H(Y |Z), or reversely, use (Y , Z ) to generate (X , Z ) if H(X) < H(Y |Z).
We also generalize our result to the minimum Rényi entropy, and get the following corollary. The proof is provided in
Appendix C.

Corollary III.10 (Minimum Rényi Conditional Entropy Coupling). Recall from Definition III.3 the minimum conditional α(c)
Rényi entropy Hα (PX , PY ) := minPXY ∈C(PX ,PY ) Hα (Y |X) over couplings of PX , PY . Then given two product marginal
(c)
n
n
, PYn ) → 0 as n → ∞, if
and PYn with H(X) > H(Y ), we have Hα (PX
distributions PX
α>

log |Y|
E (PX , PY ) + log |Y|

(98)

and E (PX , PY ) defined in (40) denotes the optimal exponent for the maximal guessing coupling problem.
IV. E XACT I NTRINSIC R ANDOMNESS
In the next four sections, we apply the results above on the maximal guessing coupling problem to several informationtheoretic problems. First, we consider a new version of intrinsic randomness problem, named exact intrinsic randomness, and
apply our results on maximal guessing coupling to this problem.
The lossless source coding problem, intrinsic randomness problem, and source resolvability problem consist of three
ingredients:
1) a source distribution PX n ,
2) a random variable Mn ∈ [1 : enR ],
3) and a mapping between them PX n |Mn or PMn |X n .
U
Define the uniform distribution as PM
:= Unif[1 : enR ]. In the lossless source coding problem, the source distribution
n
n
n
PX n = PX and X is an asymptotic function of Mn under the reconstruction mapping PX n |Mn ; in the intrinsic randomness
n
U
problem, the source distribution PX n = PX
, Mn is a function of X n under the randomness extractor PMn |X n , and PMn , PM
n
U
n
are asymptotically equal under some distance measure; and in the source resolvability problem, PMn = PMn , X is a
n
deterministic function of Mn under the resolvability code PX n |Mn , and PX n , PX
are asymptotically equal under some distance
n
U
measure. However, we usually cannot find a joint distribution PMn X n such that PX n = PX
, PMn = PM
, and X n is a function
n
n
of Mn or Mn is a function of X under PMn X n ; see Proposition III.4. Therefore, in the traditional intrinsic randomness problem
n
and source resolvability problem, we relax the constraint on marginal distributions, i.e., we do not constrain that PX n = PX
U
U
n
and PMn = PMn , but require that PMn , PMn or PX n , PX are asymptotically equal under some distance measure. In this paper
n
we define exact intrinsic randomness by relaxing the constraint on the mapping. Specifically, we require that PX n = PX
,
U
n
PMn = PMn , and Mn is an asymptotic function of X .

14

U
Definition IV.1. Given a memoryless source PX and a uniform random variable Mn with distribution PM
= Unif[1 : enR ],
n
define the exact intrinsic randomness rate S E (PX ) as the minimum rate needed to ensure there exists a code PMn |X n such
U
that PMn = PM
, and Mn is an asymptotic function of X n (limn→∞ maxfn P {Mn = fn (X n )} = 1). That is,
n


U
n
(99)
S E (PX ) := sup R : ∃PMn |X n : PMn = PMn , lim max P {Mn = fn (X )} = 1 ,
n→∞ fn

or equivalently,

S E (PX ) := sup R : ∃PX n Mn ∈

n
U
)
C(PX
, PM
n


: lim max P {Mn = fn (X )} = 1 .
n

n→∞ fn

(100)

From Theorem III.1, we know that the problems of exact and approximate intrinsic randomness are equivalent.
n
Corollary IV.1 (Equivalence Between Exact and Approximate Intrinsic Randomness). Given a memoryless source PX
and a
U
uniform distribution PMn ,

min

U
min P {Mn 6= fn (X n )} = min |PM
− Pfn (X n ) |.
n

n ,P U ) fn
PX n Mn ∈C(PX
Mn

fn

(101)

Combining Corollary IV.1 and existing results on approximate intrinsic randomness, we completely characterize the exact
intrinsic randomness rate.
Theorem IV.1 (Exact Intrinsic Randomness).
S E (PX ) = H(X).

(102)

Remark IV.1. It is easy to verify that Corollary IV.1 also holds for general sources. On the other hand, Vembu and Verdú [5]
showed for a general source X, the intrinsic randomness rate for the approximate intrinsic randomness problem is H(X).
Hence for a general source X, the intrinsic randomness rate S E (PX ) for the exact intrinsic randomness problem (defined
similarly to the memoryless case) is S E (PX ) = H(X).
Proof: For the approximate intrinsic randomness problem, Han [6, Theorem 1.6.1] showed there exists a code for the
approximate intrinsic randomness problem if R < H(X) and only if R ≤ H(X). Invoking Corollary IV.1 completes the proof
of Theorem IV.1.
n
, the optimal (maximum) code rate Rn∗ generated under
Theorem IV.2 (Second Order Rate). Given a memoryless source PX
the condition that the output forms a uniform random variable, i.e., Mn ∼ Unif[1 : enRn ] and Mn is an ε-asymptotic function
of the output X n , i.e., lim supn→∞ minfn P {Mn 6= fn (X n )} ≤ ε, satisfies
r


V (X) −1
1
∗
Rn = H(X) −
,
(103)
Q (ε) + o √
n
n

where Q is the Gaussian Q-function, and V (X) is the variance of ıX (X).
Proof: Similarly to the proof of Theorem IV.1, we can prove Theorem IV.2 by the equivalence between maximal guessing
coupling problem and source resolvability problem (which is also approximate intrinsic randomness for this case) (Theorem
III.1), and the the second order rate results for the approximate intrinsic randomness given by Hayashi [33].
V. E XACT R ESOLVABILITY
The maximal guessing coupling problem through a channel defined in Section III-B is the minimization of the error probability
of the channel output Y n and the target variable Z n . Theorem III.3 shows this problem is equivalent to the traditional channel
resolvability problem (with the TV distance measure).
In this section, we consider a new channel (or source) resolvability problem, named exact channel (or source) resolvability
U
problem. In this problem, we require that PY n = PYn , PMn = PM
, and the channel input X n is an asymptotic function of
n
Mn (limn→∞ maxfn P {X n = fn (Mn )} = 1).
U
Definition V.1. Given a uniform random variable Mn with distribution PM
= Unif[1 : enR ] a memoryless channel PY |X ,
n
and a target distribution PY , define the exact channel resolvability rate GE (PY |X , PY ) as the minimum rate needed to
ensure there exists a code PX n |Mn such that PY n = PYn , and the channel input X n is an asymptotic function of Mn
(limn→∞ maxfn P {X n = fn (Mn )} = 1). That is,


n
n
n
GE (PY |X , PY ) := inf R : ∃PX n |Mn : PY = PY , lim max P {X = fn (Mn )} = 1 .
(104)
n→∞ fn

If the channel PY |X is an identity channel, we define exact source resolvability rate


n
GE (PX ) := inf R : ∃PX n |Mn : PX n = PX
, lim max P {X n = fn (Mn )} = 1 ,
n→∞ fn

(105)

15

or equivalently,


U
n
n
GE (PX ) := inf R : ∃PMn X n ∈ C(PM
,
P
)
:
lim
max
P
{X
=
f
(M
)}
=
1
.
n
n
X
n
n→∞ fn

(106)

n
U
Corollary V.1 (Source Resolvability). Given a memoryless source PX
and a uniform distribution PM
,
n
n
min P {X n 6= fn (Mn )} = min |PX
− Pfn (Mn ) |.

min

U ,P n ) fn
PMn X n ∈C(PM
X
n

fn

(107)

Furthermore,
GE (PX ) = H(X).

(108)

Remark V.1. It is easy to verify that the equivalence (107) also holds for general sources. On the other hand, Han and Verdú
[7] showed for a general source X, the resolvability rate for the approximate source resolvability problem is H(X). Hence
for a general source X, the resolvability rate GE (PX ) for the exact source resolvability problem (defined similarly to the
memoryless case) is GE (PX ) = H(X).
Proof: The equivalence (107) follows from Theorem III.1. Furthermore, Han and Verdú [7] showed there exists a code
for the approximate source resolvability problem if R < H(X) and only if R ≤ H(X). Combining these two observations
gives us (108).
Denote

P(PY |X , QY ) := PX : PY |X ◦ PX = QY ,
(109)
and assume P(PY |X , QY ) 6= ∅. We are now are ready to establish the following multiletter characterization for the exact
channel resolvability rate.
Proposition V.1 (Multiletter Characterization of GE (PY |X , PY )).
GE (PY |X , PY ) =

inf

PX ∈P(PY |X ,PY )

H(X) = lim

min

n→∞ PX n ∈P(P n

,PYn )
Y |X

1
H(X n ),
n

(110)


where P(PY |X , PY ) := PX : PX n ∈ P(PYn|X , PYn ), ∀n .
Remark V.2. Different from our definition, Li and El Gamal [34] defined an exact common information rate by considering
variable-length coding. However, the exact common information rate has a similar characterization as (110), i.e., the exact
common information rate
1
C E (X; Y ) = lim
min
H(Wn ).
(111)
n
n
n→∞ PWn |X n Y n :X →Wn →Y n
Proof: According to the definition of GE (PY |X , PY ) and Remark V.1, we have GE (PY |X , PY ) = inf PX ∈P(PY |X ,PY ) H(X).
Next we prove GE (PY |X , PY ) = limn→∞ minPX n ∈P(PYn|X ,PYn ) n1 H(X n ).
First it is easy to lower bound GE (PY |X , PY ) as
GE (PY |X , PY ) =

inf

PX ∈P(PY |X ,PY )

H(X) ≥ lim sup

inf

n→∞ PX n ∈P(PYn|X ,PYn )

1
H(X n )
n

(112)

where (112) follows since H(X) ≥ lim supn→∞ n1 H(PX n ) for any X with a finite alphabet X (see [6, Theorem 1.7.2]).
Assume n = mk +l, l < k with a fixed number k. For the first mk symbols, we use the code fmk in [7] to exactly synthesize
m
k
k
(1)
PX
> k1 H(X k )
k with PX k ∈ P(PY |X , PY ). By Corollary V.1, we have that if the code rate R
n
o
(1)
lim P X mk = fmk (Mmk ) = 1,
(113)
m→∞

(1)
Mmk

mkR(1)

where
∼ Unif[1 : e
]. On the other hand, for each of the last l symbols, we use a single-letter code f1 to
(2)
approximately synthesize PX with PX ∈ P(PY |X , PY ). Here we assume f1 satisfies PX − Pf1 (M (2) ) ≤ |X |e−Rm where
(2)
M (2) ∼ Unif[1 : eRm ]. Obviously, there exists at least one code f1 satisfying this condition. By the equivalence (107), we
(2)
know that there exists a coupling PM (2) X ∈ C(PM (2) , PX ) satisfying minf1 P X 6= f1 (M (2) ) ≤ |X |e−Rm .
mkR(1) +lR(2)

m
For this concatenated code, we have the overall code rate is
, and the overall minimum guessing error probability
mk+l
is upper bounded as
n
o
n
o
(1)
min P {X n 6= fn (Mn )} ≤ P X mk 6= fmk (Mmk ) + l min P X 6= f1 (M (2) )
(114)
fn
f1
n
o
(2)
(1)
≤ P X mk 6= fmk (Mmk ) + k|X |e−Rm ,
(115)

16

(1)

(2)

(2)

where Mn = (Mmk , (M (2) )l ). We choose R(1) , Rm such that R(1) > k1 H(X k ) for some PX k ∈ P(PYk |X , PYk ), limn→∞ Rm =
(2)
√
(2)
(2)
mkR(1) +lRm
∞ and Rm = o(m) (e.g., Rm = m). Then for fixed k, the overall rate limn→∞
= R(1) , and the overall
mk+l
minimum guessing error probability
n
o
(2)
(1)
lim min P {X n 6= fn (Mn )} ≤ lim P X mk 6= fmk (Mmk ) + lim k|X |e−Rm

n→∞ fn

m→∞

m→∞

= 0.

(116)
(117)

This implies we get a channel resolvability code with rate minPX k ∈P(P k

Y |X

GE (PY |X , PY ) ≤ lim inf

min

1
k
,PYk ) k H(X ).

k→∞ P k ∈P(P k ,PYk )
X
Y |X

Since k is arbitrary, we have

1
H(X k ).
k

(118)

Combining (112) and (118), we have GE (PY |X , PY ) = limn→∞ minPX n ∈P(PYn|X ,PYn ) n1 H(X n ).
Furthermore, we can bound GE (PY |X , PY ) as follows.
Proposition V.2.
GTV (PY |X , PY ) ≤ GE (PY |X , PY ) ≤ GE (PY |X , PY ),

(119)

where GTV (PY |X , PY ) := minPX ∈P(PY |X ,PY ) I(X; Y ) denotes the channel resolvability rate under the TV distance measure,
and GE (PY |X , PY ) := minPX ∈P(PY |X ,PY ) H(PX ).
n
with PX ∈ P(PY |X , PY ). The lower
Proof: The upper bound is obtained by choosing X n in (110) such that PX n = PX
bound is obtained by the following chain of inequalities:

1
H(X n )
n
1
≥ lim inf
min
I(X n ; Y n )
n→∞ PX n ∈P(P n ,PYn ) n
Y |X
1
(H(Y n ) − H(Y n |X n ))
= lim inf
min
n→∞ PX n ∈P(P n ,PYn ) n
Y |X

GE (PY |X , PY ) = lim

min

n→∞ PX n ∈P(P n

,PYn )
Y |X

(120)
(121)
(122)

n

= lim inf

1X
(H(Yi ) − H(Yi |Xi ))
PX n ∈P(PY |X ,PYn ) n
i=1

= lim inf

1X
I(Xi ; Yi )
PX n ∈P(PY |X ,PYn ) n
i=1

n→∞

minn

(123)

n

n→∞

minn

(124)

= lim inf

min

I(XJ ; YJ |J)

(125)

≥ lim inf

min

I(XJ ; YJ )

(126)

n→∞ PX n ∈P(P n ,PYn )
Y |X
n→∞ PX n ∈P(P n ,PYn )
Y |X

=

min

PX ∈P(PY |X ,PY )

I(X; Y ),

(127)

where in (125) J ∼ Unif[1 : n] denotes a time-sharing random variable, (125) follows from that YJ is independent of J since
Y n are i.i.d. under PYn , and in (127) X := XJ , Y := YJ .
Proposition V.3. Neither the upper bound GE (PY |X , PY ) nor the lower bound GTV (PY |X , PY ) is tight in general, i.e., there
exists PY |X , PY such that
GE (PY |X , PY ) < GE (PY |X , PY )

(128)

GTV (PY |X , PY ) < GE (PY |X , PY ).

(129)

and also there exists PY |X , PY such that

This proposition implies the exact and approximate channel resolvability are not equivalent. In general, the exact channel
resolvability requires a larger rate.

17

A. PY -non-redundant Channel
Although the upper bound GE (PY |X , PY ) is not tight in general, we will show it is tight for some special cases, e.g., full-rank
channels and additive channels. Hence next, we focus on full-rank channels and additive channels, and prove GE (PY |X , PY ) =
GE (PY |X , PY ) for these two classes of channels.
Definition V.2. We say PY |X is a PY -non-redundant channel if given PY |X and PY , the equation P Y |X P X = P Y has a
unique solution PX . That is, there exists a unique distribution PX that induces PY through PY |X .
Definition V.3. We say PY |X is a full-rank channel if rank(P Y |X ) = |X |.
Definition V.4. We say PX is a degenerate distribution if PX (x0 ) = 1 for some x0 and PX (x) = 0 for x 6= x0 .
Lemma V.1. Properties:
1) If PY |X is a PY -non-redundant channel, then either PY |X is a full-rank channel or PX is a degenerate distribution.
2) For any n ∈ N, PYn|X is a PYn -non-redundant channel, if and only if PY |X is a PY -non-redundant channel.
3) Any additive channel Y = X + Z with Z independent
of X, is a full-rank channel.
Qn
4) If PX n ∈ P(PYn|X , PYn ) for some n ∈ N, then i=1 PXi ∈ P(PYn|X , PYn ).
Remark V.3. In general, PX n ∈ P(PYn|X , PYn ) does not imply PX n must be a product distribution or that is uniquely defined.
However if PY |X is a PY -non-redundant channel, it does imply that PX n must be a product distribution and that it is unique.
Proof: Proof of Property 1): Consider the linear equation P Y |X Q = P Y where we do not constrain Q to a probability
distribution, i.e., some components can be negative. We know that it must have no solution, a unique solution, or infinitely
many solutions.
If P X is a probability distribution and the linear equation P Y |X P X =PP Y has a unique solution, then it means that
the set of solutions of P Y |X Q = P Y and the probability simplex {P X : x PX (x) = 1, PX (x) ≥ 0} intersect at a single
point. Hence either P Y |X Q = P Y has a single unique solution, or it has infinitely many solutions but they intersect with
the probability simplex at the vertices points of the probability simplex. These two cases respectively correspond to the case
rank(P Y |X ) = |X | and the case where the solution is PX (x0 ) = 1 for some x0 and PX (x) = 0 for x 6= x0 .
Property 2) follows from Property 1).
Proof of Property 3): P Y |X = I |X | ⊗ P Z , where I |X | denotes a identity matrix with size |X |. Hence rank(P Y |X ) =
rank(I |X | )rank(P Z ) = |X |.
Property 4) is obvious.
Theorem V.1. If the channel PY |X is a PY -non-redundant channel, then
GE (PY |X , PY ) = GE (PY |X , PY ) = H(PX ),

(130)

where PX is the unique distribution that induces PY through PY |X .
Proposition V.4. For a Gaussian channel PY |X and a Gaussian distribution PY , we have PX ∈ P PY |X , PY
Gaussian and unique. So for this case,
GE (PY |X , PY ) = GE (PY |X , PY ) = H(PX ) = ∞.



is also
(131)

Remark V.4. The exact channel resolvability rate is infinite, although the approximate channel resolvability rate GTV (PY |X , PY ) =
NY
1
2 log NZ is finite. This point is different from the exact common information. Li and El Gamal [34] showed the exact common
information CE (X; Y ) satisfies
I(X; Y ) ≤ CWyner (X; Y ) ≤ C E (X; Y ) ≤ I(X; Y ) + 24.
where CWyner (X; Y ) is Wyner’s common information, and C E (X; Y ) is the exact common information. Applying this result
to two jointly Gaussian random variables shows that only a finite amount of common randomness is needed for simulating
them in a distributed manner.
Theorem V.2 (Second Order Rate for PY -non-redundant Channels). Given a memoryless PY -non-redundant channel, the
optimal (minimum) code rate Rn∗ needed to ensure the channel output follows distribution PYn and X n is an ε-asymptotic
function of the output Mn , i.e., lim supn→∞ minfn P {X n 6= fn (Mn )} ≤ ε, satisfies
r


V (X) −1
1
∗
Rn = H(X) +
Q (ε) + o √
,
(132)
n
n
where PX is the unique distribution that induces PY through PY |X .
Proof: For PY -non-redundant channels, the channel input distribution is unique and equal to PX . Hence for this case, the
exact channel resolvability problem is equivalent to the exact source resolvability problem. On the other hand, by Corollary

18

V.1 we know that the exact source resolvability problem is also equivalent to the approximate source resolvability problem.
Hence the exact channel resolvability problem is equivalent to the approximate source resolvability problem. Furthermore, for
the latter problem, Nomura and Han [35, Theorem 1.6.1] showed that the optimal rate is as in (132).
VI. C HANNEL C APACITY W ITH I NPUT D ISTRIBUTION C ONSTRAINT
Definition VI.1. Given a distribution PX , the channel capacity with input distribution constraint PX is defined as the maximum
∞
n
c
rate R such that there exists a sequence of codes (PX n |Mn , PM
cn |Y n )n=1 satisfying PX n = PX and limn→∞ P{Mn = Mn } = 1
with Mn ∼ Unif[1 : enR ]. That is,
n
n
o
o
∞
n
c
C (PX ) := sup R : ∃(PX n |Mn , PM
(133)
cn |Y n )n=1 : PX n = PX , lim P Mn = Mn = 1 .
n→∞

Definition VI.2. [36] The Gäcs-Körner (GK) common information between the correlated source (X, Y ) is defined as
CGK (X; Y ) :=

sup

H(f (X)).

(134)

f,g:f (X)=g(Y )

Theorem VI.1. C (PX ) = CGK (X; Y ), where CGK (X; Y ) denotes the GK common information between X and Y (under the
distribution PX PY |X ).
Remark VI.1. C (PX ) ≤ I(X; Y ) ≤ C, where C denotes the traditional Shannon capacity (i.e., the channel capacity without
the input distribution constraint).
Proof: Assume W is a common part of X and Y (under distribution PX PY |X ) (i.e., W = g(X) = h(Y ) a.s. for some
functions g and h). If R < H(W ), then according to Theorem III.2 there exists a maximal guessing coupling PMn W n such that
PMn = Unif[1 : enR ] and maxfn P {Mn = fn (W n )} → 1. Assume fn is a maximizing function of maxfn P {Mn = fn (W n )}.
n
n
n n
n
(xn |wn ) as the encoder, and PW
b = fn (wn )} as the decoder. Then PX n = PX
Apply PW n |Mn (wn |m)PX|W
|Y (w |y ) · 1 {m
cn } = 1. Hence C (PX ) ≥ CGK (X; Y ).
and limn→∞ P{Mn = M
On the other hand, we can convert a code for the problem of channel capacity with input distribution constraint PX into a
n
code for the GK common information problem. For any code (PX n |Mn , PM
cn |Y n ) satisfying PX n = PX and limn→∞ P{Mn =
cn } = 1, the induced joint distribution of X n and Y n is the product distribution P n . Hence (PM |X n , P c n ) forms a
M
XY
n
Mn |Y
code for the GK common information problem [36]. According to the converse for GK common information problem, we
conclude that the code rate is not larger than CGK (X; Y ).
Theorem VI.2 (Second Order Rate). Given a distribution PX , the optimal (maximum) code rate Rn∗ needed to ensure there
n
cn } ≤ ε, satisfies
and lim supn→∞ P{Mn 6= M
exists a sequence of codes satisfying PX n = PX
r
r




V (W ) −1
V (W ) −1
1
1
∗
CGK (X; Y ) −
Q (ε) + o √
≤ Rn ≤ CGK (X; Y ) −
Q (µ(ε)) + o √
,
(135)
n
n
n
n
where W is a common random variable of X and Y (under the distribution PX PY |X ) and
µ(ε) :=

1 − (1 − θ) (1 − ξ)

inf
√

θ,ξ∈(ε,1):2(1−ρm (X;Y |W ))

where
ρm (X; Y |W ) :=

(136)

ξ(1−ξ)(θξ−ε)(θ(1−ξ)+ε)≤ε

sup
g:X ×W→R,h:Y×W→R:
E[var(g(X,W )|W )]E[var(h(Y,W )|W )]>0

p

E[cov(g(X, W ), h(Y, W )|W )]
p
E[var(g(X, W )|W )] E[var(h(Y, W )|W )]

(137)

denotes the conditional maximal correlation [37] between X and Y given the common random variable W .
Proof: Achievability (Lower Bound): Consider the
q coding scheme used
 inthe proof of Theorem VI.1. By the achievability

) −1
(ε)+o √1n , then there exists a maximal guessing coupling
part of Theorem IV.2, we have that if Rn < H(W )− V (W
n Q
PMn W n such that PMn = Unif[1 : enRn ] and lim supn→∞ minfn P {Mn 6= fn (W n )} ≤ ε. On the other hand, the legitimate
cn = fn (W n ). Hence lim supn→∞ minf P {Mn 6= fn (W n )} ≤
user first recovers W n losslessly and then reconstructs Mn as M
n
cn } ≤ ε.
ε implies lim supn→∞ P{Mn 6= M
Converse (Upper Bound): To show the converse part, we need the following lemma, which is a slight refinement of [38,
Lemma 1.1].

Lemma VI.1. [38, Lemma 1.1] Given two random variables X, Y with joint distribution PXY , assume
P {U 6= V } ≤ ε

(138)

for some ε > 0 and some random variables U, V such that U → X → Y → V . Then
inf P {U 6= f (W )} ≤ µ(ε),
f

(139)

19

where W is a common random variable of X and Y , and µ(ε) is defined in (136).
cn ) as (X, Y, U, V ), we have
Apply this lemma to our setting by the identification (X n , Y n , Mn , M
 n
o
cn .
inf P {Mn 6= f (W n )} ≤ µ P Mn 6= M
f

(140)

Taking limsup’s, we have
 n
o
cn
lim sup inf P {Mn 6= f (W n )} ≤ lim sup µ P Mn 6= M
n→∞

f

(141)

n→∞

≤ µ(ε),

(142)

where (142) follows q
since µ(ε) is continuous and non-decreasing in ε. Then by the converse part of Theorem IV.2, we have
) −1
that Rn < H(W ) − V (W
(µ(ε)) + o √1n .
n Q
VII. P ERFECT S TEALTH AND S ECRECY C OMMUNICATION
In this section, we apply the preceding results on exact resolvability to the perfectly stealthy and secret communication over
the discrete memoryless wiretap channel [39], [40]. Stealthy communication was studied by Hou and Kramer [13] and Yu
and Tan [11], where the relative entropy and the Rényi divergence were respectively used to measure the level of stealth of
communication. In this paper, we consider a perfectly stealthy and secret communication system, where the wiretapper is forced
to observe a channel output exactly, instead approximately, following a target distribution and, at the same time, the secret
part of transmitted messages is independent of the wiretapper’s observation. For this new problem, we aim at characterizing
the rate region of secret and non-secret parts of the transmitted messages.
Consider a discrete memoryless wiretap channel PY Z|X , and two messages (M0 , M1 ) that are uniformly distributed over
M0 := [1 : enR0 ] and M1 := [1 : enR1 ] respectively. A sender wants to transmit the pair (M0 , M1 ) to a legitimate user
reliably, and, at the same time, ensure that M1 is exactly independent from the wiretapper’s observation Z n .
Definition VII.1. An (n, R0 , R1 ) secrecy code is defined by two stochastic mappings PX n |M0 M1 : M0 × M1 7→ X n and
n
PM
c1 |Y n : Y 7→ M0 × M1 .
c0 M
Given a target distribution PZ , we wish to maximize the alphabet size (or rate) of M1 such that the distribution PM1 Z n
induced by the code is equal to the target distribution PM1 PZn and M1 can be decoded correctly asymptotically.
Definition VII.2. The tuple (R0 , R1 ) is PZ -achievable if there exists a sequence of (n, R0 , R1 ) secrecy codes with induced
distribution PM0 M1 Z n M
c0 M
c1 such that
1) Error constraint:


c0 , M
c1 ) = 0;
lim P (M0 , M1 ) 6= (M
(143)
n→∞

2) Secrecy constraint:
Here we assume PZ
by any secrecy code.

PM1 Z n = PM1 PZn .
(144)


satisfies P PZ|X , PZ 6= ∅ (P PZ|X , PZ is defined in (109)); otherwise, (144) cannot be satisfied

Definition VII.3. The PZ -admissible region is defined as
R(PZ ) := Closure {(R0 , R1 ) : (R0 , R1 ) is PZ -achievable} .

(145)

The perfect stealth-secrecy capacity is defined as
C(PZ ) :=

max
(R0 ,R1 )∈R(PZ )

R1 .

(146)

There are two reasons we assume M0 , M1 follow uniform distributions. Firstly, this assumption is consistent with the
setting in traditional communication problems. Secondly, even if the sources (or messages) to be transmitted (denote them
n
U
as S0 , S1 ) are not uniform, by Theorem IV.1 we know that for k = 0, 1, there exists PSkn Mk ∈ C(PX
, PM
) such that
k
k
n
limn→∞ maxfn P {Mk = fn (Sk )} = 1 if the rate Rk of Mk satisfies Rk > H(Sk ). Hence using PMk |Skn , k = 0, 1, we
transform the sources into two uniformly distributed messages. Moreover, for the error constraint, if the legitimate user can
recover M0 , M1 , he can recover S0 , S1 as well since limn→∞ maxfn P {Mk = fn (Skn )} = 1. For the secrecy constraint,
PM1 Z n = PM1 PZn implies PS1 Z n = PS1 PZn . Therefore, the perfect stealth and secrecy communication of uniform messages
implies the perfect stealth and secrecy communication of non-uniform messages if Rk > H(Sk ), k = 0, 1. Obviously, the
converse holds if Rk < H(Sk ), k = 0, 1. Therefore, the perfect stealth and secrecy communication of non-uniform messages
is feasible if and only if (H(S0 ), H(S1 )) is PZ -achievable. This ensures that we only need to consider uniform messages.

20

A. Main Result
For full-rank channels, we completely characterize the admissible region.
Theorem VII.1. If the wiretap channel PZ|X is of full-rank (including additive channels and identity channels), we have


(R0 , R1 ) : R0 ≤ CGK (X; Y )
R(PZ ) =
,
(147)
R1 = 0
where PX is the unique distribution that induces the target distribution PZ .
Proof: The achievability part follows from the result on channel capacity with input distribution constraint (Theorem VI.1
in the previous section). Now we prove the converse part.
⊗n
⊗n
Note that P ⊗n
Z = P Z n |M1 =m1 = P Z|X P X n |M1 =m1 for any m1 , and P Z|X is invertible. Hence
−1
⊗n


⊗n
−1
P
P X n |M1 =m1 = P ⊗n
P
=
P
(148)
Z
Z
Z|X
Z|X
⊗n
does not depend on m1 , hence X n is independent of M1 . On the other hand, M1 →
for any m1 . Note that (P −1
Z|X P Z )
n
n
X → Y forms a Markov chain, hence Y n is independent of M1 . That is, R1 = 0.
The converse part for R0 ≤ CGK (X; Y ) follows from the converse part of Theorem VI.1.
For general channels, we derive an upper bound and a lower bound for the perfect stealth-secrecy capacity.

Theorem VII.2. The perfect stealth-secrecy capacity is bounded as
max

PU T X :U →T →Z,PX ∈P(PZ )

I(U ; Y ) − I(U ; T ) ≤ C(PZ )
≤

(149)

max

min

PU X :PX ∈P(PZ ) PT |XZ :PZ|T is of full-rank,X→T →Z

I(U ; Y ) − I(U ; T ).

(150)

Remark VII.1. The lower bound can be further lower bounded as
max

PU T X :U →T →Z,PX ∈P(PZ )

I(U ; Y ) − I(U ; T ) ≥

max

PU X :U ⊥Z,PX ∈P(PZ )

I(U ; Y ).

(151)

The upper bound can be further upper bounded as
max

min

PU X :PX ∈P(PZ ) PT |XZ :PZ|T is of full-rank,X→T →Z

I(U ; Y ) − I(U ; T ) ≤

max

PU X :PX ∈P(PZ )

I(U ; Y ) − I(U ; Z).

(152)

Proof: Achievability: Suppose PU T X is a distribution such that U → T → Z, PX ∈ P(PZ ). Then we use the following
scheme to obtain the inner bound.
e1 > R1 . For each message m1 ∈ [1 : enR1 ]
Codebook generation: Fix the conditional pmf PU |T and PX|U T and let R
e1 −R1 )
n(R
generate a subcodebook C(m1 ) consisting of e
randomly and independently generated sequences un (l), l ∈ [(m1 −
Q
e
e
n
1)en(R1 −R1 ) + 1 : m1 en(R1 −R1 ) ], each according toQ i=1 PU (ui ).
n
Encoding: Generate a sequence tn according to i=1 PT (ti ). Upon receiving message m1 ∈ [1 : enR1 ] and sequence tn ,
(n)
the encoder chooses a sequence un (l) ∈ C(m1 ) such that (un (l), tn ) ∈ T . If no such sequence exists,
Qn it picks l = 1. For
n
n
n
n
n
n
brevity, denote U = U (L). Then upon U = u , T = t , the encoder generates xn according to i=1 PX|U T (xi |ui , ti )
and transmits it.
Decoding: Let 0 > . Upon receiving y n , the decoder declares that m̂1 ∈ [1 : enR1 ] is sent if it is the unique message such
(n)
that (un (l), y n ) ∈ T0 for some un (l) ∈ C(m̂1 ); otherwise it declares an error.
Analysis of Error Probability and Secrecy: Consider T n as a side information, then the achievability scheme above is also a
Gelfand-Pinsker code for the channel coding problem with non-causal side information at the transmitter. By Gelfand-Pinsker’s
proof [41, pp. 181], we have that if R1 < I(U ; Y ) − I(U ; T ) then


c1 = 0.
lim P M1 6= M
(153)
n→∞

Furthermore,
PZ n |M1 (z n |m1 ) =

X

n
n n n
n n
n n
PZ|U
T (z |u , t )PT (t )PU n (L)|T n M1 (u |t , m1 )

(154)

n
PZ|T
(z n |tn )PTn (tn )PU n (L)|T n M1 (un |tn , m1 )

(155)

un ,tn

=

X
un ,tn

=

X

n
PZ|T
(z n |tn )PTn (tn )

(156)

tn

= PZn (z n ),

(157)

21

where (155) follows from U → T → Z.
Converse: Similar to the proof of Theorem VII.1, it can be shown that T n is independent of M with Ti generated through
a channel PTi |Xi Zi such that PZi |Ti is of full-rank and Xi → Ti → Zi .
nR1 ≤ I(Y n ; M )
n

(158)
n

= I(Y ; M ) − I(T ; M )
n
X
=
I(Yi ; M |Vi ) − I(Ti ; M |Vi )
=

i=1
n X
X

(159)
(160)

PVi (vi ) (I(Yi ; M |Vi = vi ) − I(Ti ; M |Vi = vi ))

(161)

i=1 vi

≤n

max

min

PU X :PX ∈P(PZ ) PT |XZ :PZ|T is of full-rank,X→T →Z

I(U ; Y ) − I(U ; T ),

(162)

n
where Vi := Y i−1 Ti+1
, (160) follows from the standard steps in the weak converse proof for the wiretap channel [41, pp.
555], and (162) follows since PTi |Xi Zi is arbitrary such that PZi |Ti is of full-rank and Xi → Ti → Zi and (162) reduces to
(161) if U is set to M .

Definition VII.4. A function f (X) is said to be a sufficient statistic relative to PZ|X if X is independent of Z given f (X)
for any distribution on X (i.e., for any distribution on X, X → f (X) → Z forms a Markov chain).
The lower bound and upper bound in Theorem VII.2 coincide for full-rank sufficient statistic channels.
Corollary VII.1 (Full-rank Sufficient Statistic Channel). If there exists a sufficient statistic f (X) relative to PZ|X such that
PZ|f (X) is full-rank, then
C(PZ ) =
max
I(U ; Y ) − I(U ; f (X)).
(163)
PU X :Pf (X) ∈P(PZ )

Furthermore, for full-rank channels C(PZ ) = 0 for any PZ .
Remark VII.2. If PZ|X = PZ|X2 with X2 = f (X) for some function f , and PZ|X2 is of full-rank, then the perfect secrecy
capacity C(PZ ) = maxPU X :PX2 ∈P(PZ ) I(U ; Y ) − I(U ; X2 ).
As a special case of Corollary VII.1, we have the following result.
Corollary VII.2 (Gaussian Wiretap Channel). If X = (X1 , X2 ), the channel satisfies Y = X1 + X2 + E1 , Z = X2 + E2 , with
Ek ∼ N (0, Nk ), k = 1, 2 and EX12 ≤ P1 , and PZ = N (0, NZ ) with NZ ≥ N2 , then the perfect secrecy capacity


P1
1
C(PZ ) = log 1 +
.
(164)
2
N1
Similar to Definition V.2, here we define PZ -redundant channel as follows.
Definition VII.5. A channel PY Z|X is a PZ -redundant channel if there exist two distributions QX and Q0X that induce the
same PZ through PZ|X but induce two different distributions of Y through PY |X .
We give a sufficient and necessary condition for that the stealth-secrecy capacity is positive. The proof of the following
theorem is provided in Appendix D.
Theorem VII.3. C(PZ ) > 0 if and only if the channel PY Z|X is a PZ -redundant channel.
VIII. C ONCLUSION AND F UTURE W ORK
In this paper, we studied asymptotics of several coupling problems, including the problems of maximal coupling, minimum distance coupling, maximal guessing coupling, and minimum entropy coupling. We also applied these results to some
information-theoretic problems, including the problems of exact intrinsic randomness, exact resolvability, and perfect stealth
and secret communication.
Our results generalize or extend several classical and recent results. Firstly, our results on exact intrinsic randomness extend
those by Vembu and Verdú [5] and Han [6] as we consider the scenario in which the output exactly follows a uniform
distribution. Secondly, our resolvability results extend those by Han and Verdú [7], by Hayashi [8], [9], and by Yu and Tan
[11] as we consider the scenario in which output exactly follows a target distribution. Finally, our results for the wiretap channel
extend those by Hou and Kramer [13] and those by Yu and Tan [11] as we measure the effective secrecy (or the leakage)
using an exact distribution constraint.

22

A. Open Problems
There are also some interesting problems that remain to be solved.
1) The optimal exponent of the minimum excess-distance probability coupling problem for the case in which d < D(PX , PY )
has been solved in this paper. However, the optimal exponent for the case in which d > D(PX , PY ) is still unknown.
Besides, the minimum excess-distance probability and the corresponding optimal exponent for the case d = D(PX , PY )
are still unknown.
2) In this paper, we characterized the limiting value of the maximal guessing coupling problem for the case H(X) 6= H(Y ).
However, it is still open for the case H(X) = H(Y ). Furthermore, the optimal exponent for this problem is still unknown.
The same comment applies to the optimal exponent for the minimum entropy coupling problem.
3) Under the assumption of uniform distributions, we provided the necessary and sufficient condition for the existence of a
deterministic coupling or an asymptotically deterministic coupling for two product marginal distributions. However, the
general case, stated in Conjectures III.1 and III.2, is still open.
4) An achievability result on the minimum (conditional) Rényi entropy coupling problem was provided in Corollary III.10.
Other minimum Rényi entropy coupling (or maximum Rényi mutual information coupling) problems are still open.
5) We only characterized the exact channel resolvability rate for full-rank channels. The complete characterization of the
exact channel resolvability rate for general channels is still open.
6) We provided a sufficient and necessary condition in Theorem VII.3 for the scenario in which the stealth-secrecy capacity
is positive. We also characterized the stealth-secrecy capacity for the full-rank sufficient statistic channel in Corollary
VII.1. However, the complete characterization of the perfect stealth-secrecy capacity for general channels is still open.
Acknowledgments
The authors are supported by a Singapore National Research Foundation (NRF) National Cybersecurity R&D Grant (R-263000-C74-281 and NRF2015NCR-NCR003-006).
A PPENDIX A
P ROOF OF P ROPOSITION II.2
Proof of Statement 1): Observe that max {D(QX kPX ), D(QY kPY )} is continuous in QXY ∈ P(X × Y). By [11, Lem. 5],
we know
lim

n→∞ TXY ∈Pn (X ×Y):

=

max {D(TX kPX ), D(TY
min
P
x,y TXY (x,y)d(x,y)≤d

max {D(QX kPX ), D(QY
Pmin
QXY ∈P(X ×Y): x,y QXY (x,y)d(x,y)≤d

kPY )}

kPY )} .

(165)

Hence to prove Statement 1), we only need to show the exponent E(d) is
lim

n→∞ TXY ∈Pn (X ×Y):

max {D(TX kPX ), D(TY
min
P
x,y TXY (x,y)d(x,y)≤d

kPY )} .

(166)

Next we prove this point.
First we prove the converse part.
n

n

P {d(X , Y ) ≤ d} = P

(
X

)
TX n Y n (x, y)d(x, y) ≤ d

(167)

x,y

=

X

n

n

PX n Y n (x , y )1

(
X

xn ,y n

)
Txn yn (x, y)d(x, y) ≤ d

(
=

X

(168)

x,y

PX n Y n (TTXY )1

)
X

TXY (x, y)d(x, y) ≤ d

(169)

x,y

TXY

(
≤

X

min{PX n (TTX ), PY n (TTY )}1

)
X

TXY (x, y)d(x, y) ≤ d

≤ (n + 1)|X kY| max min{PX n (TTX ), PY n (TTY )}1
TXY

(
X

)
TXY (x, y)d(x, y) ≤ d

=e

(171)

x,y

(
)
n
o
X
.
−nD(TX kPX ) −nD(TY kPY )
1
TXY (x, y)d(x, y) ≤ d
= max min e
,e
TXY

(170)

x,y

TXY

(172)

x,y

−n minTXY :Px,y TXY (x,y)d(x,y)≤d max{D(TX kPX ),D(TY kPY )}

(173)

23

The exponent E(d) is lower bounded by
min
max {D(TX kPX ), D(TY
P
TXY : x,y TXY (x,y)d(x,y)≤d

kPY )} .

(174)

n
Next we prove the achievability part. First we note that finding a coupling PX n Y n of PX
and PYn that maximizes
n
n
n
n
n
P {d(X , Y P) ≤ d} is equivalent to finding a “coupling” {PX Y (TTXY )}TXY of {PX (TTX )}TX and {PY n (TTY )}TY that
n n
maximizes
TXY PX Y (TTXY ) · 1 {ETXY d(X, Y ) ≤ d}. This is because, on one hand, if we get a desired “coupling”
n
n
{PX Y (TTXY )}TXY , and for each type TXY , let the sequences in the type class TTXY uniformly share the total probability
PX n Y n (TTXY ), i.e.,
PX n Y n (TTXY )
, (xn , y n ) ∈ TTXY ,
(175)
PX n Y n (xn , y n ) =
|TTXY |

then the marginal distributions are also uniform in each type class. Moreover, the marginal distributions have the probabilities
of the type classes {PX n (TTX )}TX and {PY n (TTY )}TY . This two points ensure that the marginal distributions are respectively
n
PX
and PYn .
∗
n (TT )}
Now we find a desired “coupling” {PX n Y n (TTXY )}TXY of {PX n (TTX )}TX and {PYP
Y
TY . Denote TXY as a type
∗
P
that achieves minTXY : x,y TXY (x,y)d(x,y)≤d max {D(TX kPX ), D(TY kPY )} . Obviously, x,y TXY (x, y)d(x, y) ≤ d. Without
∗
∗
loss of generality, we only consider the case of D(TX
kPX ) ≥ D(TY∗ kPY ). We allocate PX n (TTX∗ ) to PX n Y n (TTXY
), i.e., set
∗
∗
∗
∗
PX n Y n (TTXY ) = PX n (TTX ) and PX n Y n (TTXY ) = 0 for all TXY withTP
X = TX but TXY 6= TXY . On the other hand, there
n n
is no restriction for the probabilities of other joint types. Hence we set
∗ to be
TXY ∈C(TX ,TY ) PX Y (TTXY ) TX ,TY :TX 6=TX
any coupling of {PX n (TTX )}TX 6=T ∗ and {PY n (TTY )}TY . Then for such a coupling {PX n Y n (TTXY )}TXY , we have
X
(
)
X
P {d(X n , Y n ) ≤ d} = P
TX n Y n (x, y)d(x, y) ≤ d
(176)
x,y

=

X

n

n

PX n Y n (x , y )1

(
X

xn ,y n

)
Txn yn (x, y)d(x, y) ≤ d

(
=

X

(177)

x,y

PX n Y n (TTXY )1

)
X

TXY (x, y)d(x, y) ≤ d

(178)

x,y

TXY

(
∗
≥ PX n Y n (TTXY
)1

)
X

∗
TXY

(x, y)d(x, y) ≤ d

(179)

x,y

= PX n (TTX∗ )
∗
.
= e−nD(TX kPX ) .

(180)
(181)

∗
kPX ) ≥ D(TY∗ kPY ), we have
By symmetry, for the case of D(TX
∗

˙ e−nD(TY kPY ) .
P {d(X n , Y n ) ≤ d} ≥

(182)

Therefore,
∗
E(d) ≤ max {D(TX
kPX ), D(TY∗ kPY )}

=
TXY :

P

x,y

min
TXY (x,y)d(x,y)≤d

max {D(TX kPX ), D(TY kPY )} .

(183)
(184)

Invoking (165), we complete the proof of Statement 1).
n
Proof of Statements 2) and 3): Proof of the achievability by product couplings: For the product coupling PX n Y n = PXY
where PXY := arg minPXY ∈C(PX ,PY ) Ed(X, Y ), by the
for the cases of Statement 1)
 large deviation theory, the exponents

and 2) are respectively maxt≥0 −td − log Ee−td(X,Y ) , and maxt≥0 td − log Eetd(X,Y ) , and for the case of Statement 3),
by the central limit theorem,


1
1
n
n
P {d(X , Y ) ≤ d} = + O √
.
(185)
2
n
A PPENDIX B
P ROOF OF P ROPOSITION III.4
We split the proof into three cases.
n
Case 1: If PY (y1 ) is irrational for some y1 ∈ Y and PY (y2 ) is rational for other some y2 ∈ Y, then G(PX
, PYn ) = 1 only if
1
n−1
PY (y1 ) = a1n with a1 rational. Consider the term PY (y1 ) (PY (y2 ))
. It is irrational since PY (y1 ) is irrational and PY (y2 )
n−1
n
is rational. Hence for any n, PY (y1 ) (PY (y2 ))
is not a multiple of the probability value PX
(xn ) = M1n .

24

Fig. 2.

[42] A standard maximal coupling for distributions (µ, ν) that keeps the region III unchanged and transfers the region I to the region II.
1

n
Case 2: If PY (y) is irrational ∀y ∈ Y, then G(PX
, PYn ) = 1 only if for any y, PY (y) = ayn with ay rational. Consider the
n−1
n−1
terms PY (yi ) (PY (yj ))
. Next we prove there must exist some (i, j) such that PY (yi ) (PY (yj ))
is irrational. Suppose
n
n−1
PY (yi )
PY (yi ) (PY (yj ))
is rational for any (i, j). Then PY (yj ) is rational since (PY (yj )) is rational. That is, PY (yi ) = ki,j PY (yj )
P
P|Y|
P|Y|
for some rational ki,j . Therefore, y∈Y PY (y) = i=1 ki,1 PY (y1 ) = PY (y1 ) i=1 ki,1 is irrational, since PY (y1 ) is irrational
P|Y|
P
n−1
and i=1 ki,1 is rational. However this contradicts the fact that y∈Y PY (y) = 1 is rational. Therefore, PY (yi ) (PY (yj ))
1
n
n
is irrational for some (i, j), and hence it cannot be composited by the probability values PX (x ) = M n for any
n n.

1 n
n
, PYn ) = 1 implies ab = k M
,
Case 3: If PY (y) is rational ∀y ∈ Y, then denote PY (y) = ab with a, b coprime, and G(PX


Ma n
Ma
a
k0 a
Ma n
Ma
0
i.e., b
/ N. Assume M = k b. Then PY (y) = b = M .
= k. Hence b|M , otherwise, b
∈
/ N since b ∈ Q and b ∈
n
, PYn ) = 1. Therefore, the theorem
Hence G(PX , PY ) = 1. On the other hand, it is obvious that G(PX , PY ) = 1 implies G(PX
holds for the case where PY (y) is rational ∀y ∈ Y.
Combining these three cases above, we complete the proof.

A PPENDIX C
P ROOF OF C OROLLARY III.10
n
and
We only need consider α < 1 case, since Hα (Y n |X n ) is decreasing in α. Consider a maximal guessing coupling of PX
n
which cascades a probability distribution approximation code fn (x ) with a maximal coupling code PY n |fn (X n ) . Here
we adopt a standard maximal coupling code (see Fig. 2) which satisfies
(
1,
Pfn (X n ) (y n ) ≤ PYn (y n );
n n
PY n |fn (X n ) (y |y ) =
(186)
PYn (y n )
n
n n
n
Pf (X n ) (y n ) , Pfn (X ) (y ) > PY (y ).

PYn ,

n

Then by Theorem III.2, we know
n
G(PX
, PYn ) → 1

(187)

at least exponentially fast as n → ∞. The optimal exponent is denoted as E (PX , PY ).
n
Assume (PX n Y n , fn ) is a maximizing distribution-function pair of G(PX
, PYn ); see the definition of maximal guessing
coupling in III.1. Then denote Z n := fn (X n ), and under PX n Y n we have
e(1−α)Hα (Y

n

|X n )
n

n

≤ e(1−α)Hα (Y |fn (X ))
X
=
P (z n )P α (y n |z n )

(188)
(189)

z n ,y n

=

X


P (z n ) 1 {PY n (z n ) ≥ P (z n )}

zn



X
PY n (z n ) α
α n n
n
n
+
P (y |z ) 1 {PY n (z ) < P (z )}
+
P (z n )
y n 6=z n

X
n
≤
P (z ) 1 {PY n (z n ) ≥ P (z n )}


(190)

zn

PY n (z n ) α
+ (|Y|n − 1)
P (z n )



PY n (z n )
P (z n )
|Y|n − 1

1−

α 


1 {PY n (z n ) < P (z n )}

α
X
X
PY n (z n )
=
P (z n )1 {PY n (z n ) ≥ P (z n )} +
P (z n )
1 {PY n (z n ) < P (z n )}
n)
P
(z
zn
zn
+



(191)

25

+

X

1−α

P (z n ) (|Y|n − 1)


1−

zn
n

PY n (z n )
P (z n )

α

1 {PY n (z n ) < P (z n )}

(192)

≤ PZ n {z : PY n (z n ) ≥ P (z n )}
α
P (z n )1 {PY n (z n ) < P (z n )} PY n (z n )
+ PZ n {z : PY n (z ) < P (z )}
PZ n {z n : PY n (z n ) < P (z n )}
P (z n )

α
P
n
n
n
n
PY n (z n )
(1−α)n
n
n
n
z n P (z )1 {PY (z ) < P (z )}
n
n
+ |Y|
1−
PZ {z : PY (z ) < P (z )}
PZ n {z n : PY n (z n ) < P (z n )}
P (z n )
1−α
n
n
n
n
n
n
α
n
n
= PZ n {z : PY n (z ) ≥ P (z )} + PZ n {z : PY n (z ) < P (z )} PY n {z : PY n (z ) < P (z n )}
!α
X
(1−α)n 1−α
n
n
n
n
n
n
n
+ |Y|
PZ n {z : PY n (z ) < P (z )}
(P (z ) − PY n (z )) 1 {PY n (z ) < P (z )}
n

n

n

P

zn

zn
1−α α

1−α

= 1 − (δ + p) + (δ + p)


= 1 − (δ + p) + (δ + p)

pα + |Y|(1−α)n (δ + p)
δ
α
p
1−α α
+ |Y|(1−α)n (δ + p)
δ
δ+p

≤ 1 + |Y|(1−α)n δ α
≤ 1 + |Y|

(194)
(195)
(196)
(197)

(1−α)n −αnE(PX ,PY )

e

(198)

→ 1, as n → ∞,
where (191) follows since

(193)

(199)
P

y n 6=z n

P α (y n |z n ) for α < 1 is maximized by the uniform distribution
n

n

P (y |z ) =

PY n (z n )
P (z n )
n
|Y| − 1

1−

(200)

for y n 6= z n (this point is similar to the fact that the uniform distribution maximizes the Rényi entropy), (191) follows since xα
with 0 < α < 1 is concave in x, in (195) p := PY n {PY n (z n ) < P (z n )} , δ := |PZ n − PY n |, and PZ n {PY n (z n ) < P (z n )} =
δ + p.
A PPENDIX D
P ROOF OF T HEOREM VII.3
Proof of “if”: Suppose that QX and Q0X induce the same PZ through PZ|X but induce two different distributions of Y
(B)
through PY |X . Define PX := BQX + (1 − B)Q0X , where B ∈ [0, 1] with distribution PB such that PB (0)PB (1) > 0.
Consider a new wiretap channel PY Z|B = PY |B PZ .
C1 (PZ ) ≥

max

PU X :U ⊥Z,PX ∈P(PZ )

I(U ; Y ) ≥ I(B; Y ) > 0.

(201)

The last inequality follows the following argument via contradiction. Suppose I(B; Y ) = 0, then B ⊥ Y . Hence PY |B=0 =
PY |B=1 = PY . This contradicts with the assumption that QX and Q0X induce two different distributions of Y through PY |X .
Proof of “only if”: We prove this by contradiction. That is, we need to show if for any two distributions QX and Q0X that
induce the same PZ through PZ|X , they must induce a same distribution of Y through PY |X , then the perfect stealth-secrecy
capacity is zero.
Suppose P Z|X QX = P Z has infinitely many solutions; otherwise, by Lemma V.1, PZ|X is a full-rank channel or
P Z|X QX = P Z has a single unique solution PX which is a degenerate distribution. For the former case, by Theorem
VII.1 we have the perfect stealth-secrecy capacity is zero. For the latter case, since nR1 ≤ I(Y n ; X n ) = 0, we have the
perfect stealth-secrecy capacity is also zero. So we only need to consider the case that P Z|X QX = P Z has infinitely many
solutions
In addition, note that we also only need to consider
P the case that there exists a solution to P Z|X QX = P Z which
is an interior point of the probability simplex {P X : x PX (x) = 1, PX (x)
P ≥ 0}. This is because if all the solutions to
P Z|X QX = P Z are at the boundary of the probability simplex {P X : x PX (x) = 1, PX (x) ≥ 0}, then there exists a
set X0 such that the solutions satisfy QX (x0 ) = 0 for any x0 ∈ X0 . Hence remove the corresponding columns of P Z|X
and the corresponding rows of P X , and denote the resulting matrix and vector as P Z|X and QX respectively, then we get
equation P Z|X QX =
PP Z . For this new equation, there exists a solution which is an interior point of the probability simplex
{P X ∈ P(X \X0 ) : x PX (x) = 1, PX (x) ≥ 0}.
Suppose PY is the distribution induced by Q0X through PY |X where Q0X is a distribution inducing PZ through PZ|X .
b = 0 and
By subtracting Q0X from the solutions to P Z|X QX = P Z and P Y |X QX = P Y , we get the equation P Z|X Q
0
b
b
b
P Y |X Q = 0 (here Q denotes QX − QX ). Denote SZ as the set of solutions to P Z|X Q = 0 and SY as the set of solutions
b = 0. Then by assumption, SZ ⊆ SY .
to P Y |X Q

26

Note that the set of solutions to P Z|X QX = P Z (with QX constrained to be a probability distribution) is the intersection P
of the set of solutions to P Z|X Q = P Z without the probability constraint on Q and the probability simplex
∗
{P X : x PX (x) = 1, PX (x)
X = P Z which is an interior point of the
P ≥ 0}. If there exists a solution QX to P Z|X Q|X
probability simplex {P X : x PX (x) = 1, PX (x) ≥ 0}, then the subspace of R | spanned by the set SZ is the same to the
orthogonal complement of the subspace of R|X | spanned by the rows of P Z|X , and also the same
 to the set ofthe solutions to
P Z|X Q = 0 (without the probability constraint). Since SZ ⊆ SY (or equivalently, SZ + Q0X ⊆ SY + Q0X ), Q∗X is also a
solution to P Y |X QX = P Y . Since Q∗X is an interior point of the probability simplex, similarly, we have that the subspace of
R|X | spanned by the set SY is the same to the set of the solutions to P Y |X Q = 0 (without the probability constraint). Denote
SZ0 as the set of solutions to P Z|X Q = 0 (without the probability constraint) and SY0 as the set of solutions to P Y |X Q = 0
(without the probability constraint). Then SZ0 ⊆ SY0 .
A vector Q is a solution to P Z|X Q = 0 (without probability constraint) if and only if it lies in the orthogonal complement
of the subspace of R|X | spanned by the rows of P Z|X . Hence SZ0 ⊆ SY0 means that the orthogonal complement of the row
space of P Z|X is a subset of that of the row space of P Y |X . It means that the row space of P Y |X is a subset of the row space
of P Z|X . Hence every row of P Y |X is a linear combination of the rows of P Z|X . Thus, P Y |X = AP Z|X for some matrix
A. On the other hand, observe that AP Z|X QX = AP Z , AP Z|X = P Y |X , and P Y |X QX = P Y . Hence AP Z = P Y .
n
Now we prove the following property for any n: for all distributions QX n that induce PZn through PZ|X
, they must induce
n
n
the same distribution of Y through PY |X . Consider the equation
⊗n
P ⊗n
Z|X QX n = P Z .

(202)

⊗n ⊗n
A⊗n P ⊗n
PZ
Z|X QX n = A

(203)

Multiply A⊗n at both sides, then we get
which is equivalent to
AP Z|X

⊗n

⊗n

QX n = (AP Z )

.

(204)

Substituting AP Z|X = P Y |X and AP Z = P Y , we get
⊗n
P ⊗n
Y |X QX n = P Y .

(205)

n
, they
Observe A, PZ are fixed, hence PY is fixed as well. This means for all distributions QX n that induce PZn through PZ|X
n
n
must induce the same distribution PY through PY |X .
Using on the property above, we return to proving that the perfect stealth-secrecy capacity is zero. Note that by the secrecy
constraint,
X
n
PZn (·) = PZ n |M (·|m) =
PZ|X
(·|xn )PX n |M (xn |m)
(206)
xn
n
. By the property stated in
for any m. Hence for any m, PX n |M (·|m) is a distribution that induces PZn through PZ|X
n
n |M (·|m) induces the same distribution of Y
(206),
we
have
that
for
different
m,
P
through
PYn|X , i.e., PY n |M (·|m) =
X
P
n
n
n
n
is independent of M , i.e.,
xn PY |X (·|x )PX n |M (x |m) does not depend on m. Consequently, Y

nR1 ≤ I(Y n ; M ) = 0.

(207)

R EFERENCES
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]

H. Thorisson. Coupling, stationarity, and regeneration, volume 14. Springer New York, 2000.
C. Villani. Optimal transport: old and new, volume 338. Springer Science & Business Media, 2008.
M. Kovačević, I. Stanojević, and V. Šenk. On the entropy of couplings. Information and Computation, 242:369–382, 2015.
Y. Steinberg and S. Verdú. Simulation of random processes and rate-distortion theory. IEEE Transactions on Information Theory, 42(1):63–86, 1996.
S. Vembu and S. Verdú. Generating random bits from an arbitrary source: Fundamental limits. IEEE Transactions on Information Theory, 41(5):1322–
1332, 1995.
T. S. Han. Information-spectrum methods in information theory. Springer, 2003.
T. Han and S. Verdú. Approximation theory of output statistics. IEEE Trans. on Inform. Theory, 39(3):752–772, 1993.
M. Hayashi. General nonasymptotic and asymptotic formulas in channel resolvability and identification capacity and their application to the wiretap
channel. IEEE Trans. on Inform. Theory, 52(4):1562–1575, 2006.
M. Hayashi. Exponential decreasing rate of leaked information in universal random privacy amplification. IEEE Trans. on Inform. Theory, 57(6):3989–
4001, 2011.
J. Liu, P. Cuff, and S. Verdú. Eγ -resolvability. IEEE Trans. on Inform. Theory, 63(5):2629–2658, 2017.
L. Yu and V. Y. F. Tan. Rényi resolvability and its applications to the wiretap channel. arXiv preprint 1707.00810, 2017.
G. R. Kumar, C. T. Li, and A. El Gamal. Exact common information. In Information Theory (ISIT), 2014 IEEE International Symposium on, pages
161–165. IEEE, 2014.
J. Hou and G. Kramer. Effective secrecy: Reliability, confusion and stealth. In IEEE International Symposium on Information Theory (ISIT), pages
601–605. IEEE, 2014.
I. Csiszár and J. Körner. Information Theory: Coding Theorems for Discrete Memoryless Systems. Cambridge University Press, 2011.
T. M. Cover and J. A. Thomas. Elements of Information Theory. Wiley-Interscience, 2nd edition, 2006.
Erich E. L. Lehmann and J. P. Romano. Testing statistical hypotheses. Springer Science & Business Media, 2006.
M. Ben-Bassat and J. Raviv. Rényi’s entropy and the probability of error. IEEE Transactions on Information Theory, 24(3):324–331, 1978.

27

[18] S. Berens. Conditional Rényi entropy. PhD thesis, Master’s thesis, Mathematisch Instituut, Universiteit Leiden, 2013.
[19] L. Yu and P. Cuff. The Shannon cipher system with a guessing eavesdropper. In Information Theory (ISIT), 2017 IEEE International Symposium on,
pages 749–753. IEEE, 2017.
[20] I. Issa and A. B. Wagner. Measuring secrecy by the probability of a successful guess. IEEE Transactions on Information Theory, 63(6):3783–3803,
2017.
[21] N. Merhav and E. Arikan. The shannon cipher system with a guessing wiretapper. IEEE Transactions on Information Theory, 45(6):1860–1866, 1999.
[22] E. Arikan and N. Merhav. Guessing subject to distortion. IEEE Transactions on Information Theory, 44(3):1041–1056, 1998.
[23] C. Schieler and P. Cuff. The henchman problem: Measuring secrecy by the minimum distortion in a list. IEEE Trans. on Inform. Theory, 62(6):3436–3450,
2016.
[24] L. Yu, H. Li, and W. Li. Source-channel secrecy for shannon cipher system. IEEE Transactions on Information Theory, 63(4):2596–2622, 2017.
[25] P. Schulte and G. Böcherer. Constant composition distribution matching. IEEE Transactions on Information Theory, 62(1):430–434, 2016.
[26] P. Schulte and B. Geiger. Divergence scaling of fixed-length, binary-output, one-to-one distribution matching. arXiv preprint arXiv:1701.07371, 2017.
[27] M. R. Garey and D. S. Johnson. Computers and intractability: A guide to the theory of NP-completeness, volume 29. wh freeman New York, 2002.
[28] P. Cuff. Distributed channel synthesis. IEEE Trans. on Inform. Theory, 59(11):7071–7096, 2013.
[29] W. Kumagai and M. Hayashi. Second-order asymptotics of conversions of distributions and entangled states based on rayleigh-normal probability
distributions. IEEE Transactions on Information Theory, 63(3):1829–1857, 2017.
[30] W. Feller. An introduction to probability theory and its applications, volume 2. John Wiley & Sons, 2008.
[31] S. Watanabe and M. Hayashi. Strong converse and second-order asymptotics of channel resolvability. In Information Theory (ISIT), 2014 IEEE
International Symposium on, pages 1882–1886. IEEE, 2014.
[32] H. Yagi. Channel resolvability theorems for general sources and channels. arXiv preprint arXiv:1701.08362, 2017.
[33] M. Hayashi. Second-order asymptotics in fixed-length source coding and intrinsic randomness. IEEE Transactions on Information Theory, 54(10):4619–
4637, 2008.
[34] C. T. Li and A. El Gamal. Distributed simulation of continuous random variables. IEEE Transactions on Information Theory, 2017.
[35] R. Nomura and T. S. Han. Second-order resolvability, intrinsic randomness, and fixed-length source coding for mixed sources: Information spectrum
approach. IEEE Transactions on Information Theory, 59(1):1–16, 2013.
[36] Peter P. Gács and J. Körner. Common information is far less than mutual information. Problems of Control and Information Theory, 2(2):149–162,
1973.
[37] L. Yu, H. Li, and C. W. Chen. Generalized common informations: Measuring commonness by the conditional maximal correlation. arXiv preprint
arXiv:1610.09289, 2016.
[38] I. Csiszár and P. Narayan. Common randomness and secret key generation with a helper. IEEE Transactions on Information Theory, 46(2):344–366,
2000.
[39] A. Wyner. The wire-tap channel. Bell Labs Technical Journal, 54(8):1355–1387, 1975.
[40] I. Csiszár and J. Körner. Broadcast channels with confidential messages. IEEE Trans. on Inform. Theory, 24(3):339–348, 1978.
[41] A. El Gamal and Y.-H. Kim. Network Information Theory. Cambridge university press, 2011.
[42] D. A. Levin, Y. Peres, and E. L. Wilmer. Markov chains and mixing times, volume 107. American Mathematical Soc., 2017.

