1

Wyner’s Common Information under Rényi
Divergence Measures
Lei Yu and Vincent Y. F. Tan, Senior Member, IEEE

arXiv:1709.02168v2 [] 25 Jan 2018

Abstract
We study a generalized version of Wyner’s common information problem (also coined the distributed source simulation
problem). The original common information problem consists in understanding the minimum rate of the common input to
independent processors to generate an approximation of a joint distribution when the distance measure used to quantify the
discrepancy between the synthesized and target distributions is the normalized relative entropy. Our generalization involves
changing the distance measure to the unnormalized and normalized Rényi divergences of order α = 1 + s ∈ [0, 2]. We show that
the minimum rate needed to ensure the Rényi divergences between the distribution induced by a code and the target distribution
vanishes remains the same as the one in Wyner’s setting, except when the order α = 1+s = 0. This implies that Wyner’s common
information is rather robust to the choice of distance measure employed. As a byproduct of the proofs used to the establish the
above results, the exponential strong converse for the common information problem under the total variation distance measure is
established.
Index Terms
Wyner’s common information, Distributed source simulation, Rényi divergence, Total variation distance, Exponential strong
converse

I. I NTRODUCTION
How much common randomness is needed to simulate two correlated sources in a distributed fashion? This problem, termed
distributed source simulation, was first studied by Wyner [1], who used the normalized relative entropy (Kullback-Leibler
divergence or KL divergence) to measure the approximation level (discrepancy) between the simulated joint distribution and
the joint distribution of the original correlated sources. He defined the minimum rate needed to ensure that the normalized
relative entropy vanishes asymptotically as the common information between the sources. He also established a single-letter
characterization for the common information, i.e., the common information between correlated sources X and Y (with target
distribution πXY ) is
CWyner (X; Y ) =
min
I(XY ; W ).
(1)
PXY W : PXY =πXY , X−W −Y

The common information is also known to be one of many reasonable measures of the dependence between two random
variables [2, Section 14.2.2] (other measures include the mutual information and the Gács-Körner-Witsenhausen common
information). A related notion is that of the exact common information which was introduced by Kumar, Li, and El Gamal [3].
They assumed variable-length codes and exact generation of the correlated sources (X, Y ), instead of block codes and
approximate simulation of πXY as assumed by Wyner [1]. The exact common information is not smaller than Wyner’s
common information. However, it is still not known whether they are equal in general. Furthermore, the common information
problem can be also be regarded as a distributed coordination problem. The concept of coordination was first introduced by
Cuff, Permuter, and Cover [4], [5], who used the total variation (TV) distance to measure the level of approximation between
the simulated and target distributions.
Wyner’s common information problem is also closely related to the channel resolvability problem, which was first studied
by Han and Verdú [6], and subsequently studied by Hayashi [7], [8], Liu, Cuff, and Verdú [9], and Yu and Tan [10] among
others. For the achievability part, both problems rely on so-called soft-covering lemmas [5]. The channel resolvability or
common information problems have several interesting applications—including secrecy, channel synthesis, and source coding.
For example, in [11] it was used to study the performance of a wiretap channel system under different secrecy measures.
In [12] it was used to study the reliability and secrecy exponents of a wiretap channel with cost constraints. In [13] it was
used to study the exact secrecy and reliability exponents for a wiretap channel.
A. Main Contributions
Different from Wyner’s work, we use (normalized and unnormalized) Rényi divergences of order 1 + s ∈ [0, 2] to measure
the level of approximation between the simulated and target distributions. This is motivated in part by our desire to understand
the sensitivity of the divergence as approximation measure on Wyner’s common information. We prove that for the distributed
The authors are with the Department of Electrical and Computer Engineering, National University of Singapore (NUS) (Emails: leiyu@nus.edu.sg,
vtan@nus.edu.sg). The second author is also with the Department of Mathematics, NUS.

2

source simulation problem, the minimum rate needed to guarantee that the (normalized and unnormalized) Rényi divergences
vanish asymptotically is equal to Wyner’s common information (except for the case when Rényi parameter is equal to 0). This
implies that Wyner’s common information in (1) is rather robust to the distance measure. For the achievability part, by using the
method of types and typicality arguments, we prove that the optimal Rényi divergences vanish (at least) exponentially fast if the
code rate is larger than Wyner’s common information. However, for the converse part, the proof is not straightforward and we
have to first consider an auxiliary problem. We first prove an exponential strong converse for the common information problem
under the TV distance measure, i.e., when the code rate is smaller than Wyner’s common information, the TV distance between
the induced distribution and the target distribution tends to one (at least) exponentially fast. Even though our proof technique
mirrors that of Oohama [14] to establish the exponential strong converse for the Wyner-Ziv problem, it differs significantly in
some aspects. To wit, some intricate continuity arguments are required to assert that the strong converse exponent is positive for
all rates below CWyner (X; Y ) (see part (i) of Lemma 1). Furthermore and interestingly, by leveraging a key relationship between
the Rényi divergence and the TV distance [15], this exponential strong converse implies the converse for the normalized Rényi
divergence (which in turn also implies the strong converse for the unnormalized Rényi divergence).
It is worth noting that it is quite natural to use various divergences to measure the discrepancy between two distributions.
Wyner [1] used the KL divergence to measure the level of approximation in the distributed source synthesis problem;
Hayashi [7], [8] and Yu and Tan [10] respectively used the KL divergence and the Rényi divergence to study the channel
resolvability problem. The latter also applied their results to study the capacity region for the wiretap channel under these
generalized measures. Furthermore, in probability theory, Barron [16] and Bobkov, Chistyakov and Götze [17] respectively
used the KL divergence and the Rényi divergence to study the central limit theorem, i.e., they used them to measure the
discrepancy between the induced distribution of sum of i.i.d. random variables and the normal distribution with the same mean
and variance. Furthermore, special instances of Rényi entropies and divergences—including the KL divergence, the collision
entropy (the Rényi divergence of order 2), and min-entropy (the Rényi divergence of order ∞)—were used to study various
information-theoretic problems (including security, cryptography, and quantum information) in several works in the recent
literature [10], [11], [18]–[22].
B. Notation
We use PX (x) to denote the probability distribution of a random variable X. This will also be denoted as P (x) (when the
random variable X is clear from the context). We also use PeX , PbX and QX to denote various probability distributions with alphabet X . All alphabets considered in the sequel are finite. The set of probability measureson X is denoted as P (X ), and the set
of conditional probability measures on Y given a variable in X is denoted as P(Y|X ) := PY |X : PY |X (·|x) ∈ P(Y), x ∈ X .
Furthermore, the support P
of a distribution P ∈ P(X ) is denoted as supp(P ) = {x ∈ X : P (x) > 0}.
n
We use Txn (x) := n1 i=1 1 {xi = x} to denote the type (empirical distribution) of a sequence xn , TX and VY |X to
respectively denote a type of sequences in X n and a conditional type of sequences in Y n (given a sequence xn ∈ X n ). For
a type TX , the type class (set of sequences having the same type TX ) is denoted by TTX . For a conditional type VY |X and a
sequence xn , the VY |X -shell of xn (the set of y n sequences having the same conditional type VY |X given xn ) is denoted by
TVY |X (xn ). For brevity, sometimes we use T (x, y) to denote the joint distributions T (x)V (y|x) or T (y)V (x|y).
The ǫ-typical set of QX is denoted as
Tǫn (QX ) := {xn ∈ X n : |Txn (x) − QX (x)| ≤ ǫQX (x), ∀x ∈ X } .

(2)

The conditionally ǫ-typical set of QXY is denoted as
Tǫn (QY X |xn ) := {y n ∈ Y n : (xn , y n ) ∈ Tǫn (QXY )} .
For brevity, sometimes we write
and
as
and
respectively.
The TV distance between two probability mass functions P and Q with a common alphabet X is defined as
1 X
|P (x) − Q(x)|.
|P − Q| :=
2
Tǫn (QX )

Tǫn (QY X |xn )

Tǫn

(3)

Tǫn (xn )

(4)

x∈X

By the definition of ǫ-typical set, we have that for any xn ∈ Tǫn (QX ),
ǫ
(5)
|Txn − QX | ≤ .
2
Fix distributions PX , QX ∈ P(X ). The relative entropy and the Rényi divergence of order 1 + s are respectively defined as
X
PX (x)
(6)
PX (x) log
D(PX kQX ) :=
QX (x)
x∈supp(PX )

D1+s (PX kQX ) :=

1
log
s

X

x∈supp(PX )

PX (x)1+s QX (x)−s ,

(7)

3

✒

PX n |Mn

X n✲

Mn
❅
❅
❘ PY n |Mn
❅

Y n✲

Fig. 1. Distributed source synthesis problem, where the random variable Mn ∈ Mn := {1, . . . , enR }.

and the conditional versions are respectively defined as
D(PY |X kQY |X |PX ) := D(PX PY |X kPX QY |X )

D1+s (PY |X kQY |X |PX ) := D1+s (PX PY |X kPX QY |X ),

(8)
(9)

where the summations in (6) and (7) are taken over the elements in supp(PX ). Throughout, log is to the natural base e and
s ≥ −1. It is known that lims→0 D1+s (PX kQX ) = D(PX kQX ) so a special case of the Rényi divergence (or the conditional
version) is the usual relative entropy (or the conditional version).
Given a number a ∈ [0, 1], we define ā = 1 − a. We also define [x]+ = max {x, 0}.
C. Problem Formulation
In this paper, we consider the distributed source simulation problem illustrated in Fig. 1. Given a target distribution πXY ,
we wish to minimize the alphabet size of a random variable Mn that is uniformly distributed over1 Mn := {1, . . . , enR } (R
is a positive number known as the rate), such that the generated (or synthesized) distribution
PX n Y n (xn , y n ) :=

X
1
PX n |Mn (xn |m)PY n |Mn (y n |m)
|Mn |

(10)

m∈Mn

n
. The pair of random mappings (PX n |Mn , PY n |Mn )
forms a good approximation to the product distribution πX n Y n := πXY
constitutes a synthesis code.
Different from Wyner’s seminal work on the distributed source simulation problem [1], we employ the unnormalized Rényi
divergence
(11)
D1+s (PX n Y n kπX n Y n )

and the normalized Rényi divergence
1
D1+s (PX n Y n kπX n Y n )
n

(12)

to measure the discrepancy between PX n Y n and πX n Y n . The minimum rates required to ensure these two measures vanish
asymptotically are respectively termed the unnormalized and normalized Rényi common information, and denoted as
o
n
(13)
T1+s (πXY ) := inf R : lim D1+s (PX n Y n kπX n Y n ) = 0 ,
n→∞
o
n
1
(14)
Te1+s (πXY ) := inf R : lim D1+s (PX n Y n kπX n Y n ) = 0 .
n→∞ n
It is clear that

Te1+s (πXY ) ≤ T1+s (πXY ).

(15)

We also denote the minimum rate required to ensure the TV distance is bounded above by some constant ε ∈ [0, 1]
asymptotically as
o
n
(16)
TεTV (πXY ) := inf R : lim sup |PX n Y n − πX n Y n | ≤ ε .
n→∞

We say that the strong converse property for the common information problem under the TV distance holds if TεTV (πXY )
does not depend on ε ∈ [0, 1).
1 For

simplicity, we assume that enR and similar expressions are integers.

4

II. M AIN R ESULTS
Our main result concerns Wyner’s common information problem when the discrepancy measure is the unnormalized or
normalized Rényi divergence. It is stated as follows.
Theorem 1 (Rényi Common Informations). The unnormalized and normalized and Rényi common informations satisfy
(
CWyner (X; Y ) s ∈ (−1, 1]
T1+s (πXY ) = Te1+s (πXY ) =
.
(17)
0
s = −1

Furthermore, for s ∈ (−1, 1], the optimal Rényi divergence D1+s (PX n Y n kπX n Y n ) in the definitions of the Rényi common
informations decays at least exponentially fast in n when R > CWyner (X; Y ).

Remark 1. For the converse part, T1+s (πXY ) ≥ Te1+s (πXY ) ≥ CWyner (X; Y ) for s ∈ [0, 1] is implied by Wyner’s work [1]
and the monotonicity of the Rényi divergence. For the achievability part, Te1+s (πXY ) ≤ CWyner (X; Y ) for s ∈ (−1, 0] is
also implied by Wyner’s work [1] and the monotonicity of the Rényi divergence. Furthermore, since a channel resolvability
code for the memoryless channel PX|W × PY |W can be used to form a common information code, the achievability part
for the common information problem can be obtained from existing channel resolvability results. Specifically, T1+s (πXY ) ≤
CWyner (X; Y ) for s ∈ (−1, 0] can be obtained from Hayashi’s [7], [8] or Han, Endo, and Sasaki’s results [12]. In addition,
Te1+s (πXY ) ≤ T1+s (πXY ) ≤ C1+s (X; Y ) for s ∈ (0, 1] with
X

C1+s (X; Y ) :=
min
(18)
PW (w) D1+s PX|W (·|w)PY |W (·|w)kPXY
PXY W : PXY =πXY , X−W −Y

w

can be obtained from the present authors’ results [10], but as shown in Theorem 1, this bound is not tight since C1+s (X; Y ) >
CWyner (X; Y ) in general for s ∈ (0, 1]. This is because, on the one hand, for the channel resolvability problem, the discrete
memoryless channel is fixed, and, by construction, imposes a product conditional distribution of the output given the input (which
is a product distribution), but for the common information problem, the synthesizer has the freedom to choose PX n Y n |Mn =
PX n |Mn × PY n |Mn , so that the Markov chain X n − Mn − Y n holds; on the other hand, for the common information problem,
in the sequel, we will show that if we utilize a truncated channel (which is not memoryless) as the synthesizer. This results
in a smaller achievable rate for the case s ∈ (0, 1]. Therefore, our converse for s ∈ [−1, 0) and achievability for s ∈ (0, 1] are
new (and also tight).
Remark 2. An exponential achievability result for s ∈ (−1, 0] can be obtained from Hayashi’s [7], [8] and Han, Endo, and
Sasaki’s results [12], where i.i.d. codes were employed.

For this theorem, the proof of the converse part for the unnormalized Rényi common information is provided in Appendix
A, and the proof of the converse part for the normalized Rényi common information is provided in Section IV. Observe that
the unnormalized Rényi divergence is stronger than the normalized one in the sense of (15), hence Te1+s (πXY ) ≤ T1+s (πXY ).
This implies, on one hand, the achievability result for the normalized Rényi common information Te1+s (πXY ) can be obtained
directly from the achievability result for the unnormalized version T1+s (πXY ), and on the other hand, the converse result for
the normalized Rényi common information Te1+s (πXY ) implies the converse result for the unnormalized version T1+s (πXY ).
The Rényi common informations are the same for all s ∈ (−1, 1], and also same as Wyner’s common information
CWyner (X; Y ) (which corresponds to s = 0 for the normalized case). For the case s ∈ (−1, 1], to obtain the (unnormalized and
normalized) Rényi common informations, we utilize a random code with (W n , X n , Y n ) (W is the auxiliary random variable
in the definition of CWyner (X; Y )) distributed according to a truncated product distribution, i.e., a product distribution governed
by QnW XY but whose mass is truncated to the typical set Tǫn (QW XY ).2 On one hand, the random sequences (W n , X n , Y n )
so generated are almost uniformly distributed over the typical set Tǫn (QW XY ); and on the other hand, the Rényi common
informations can be expressed as some Rényi divergences. Moreover, these Rényi divergences evaluated at the truncated
distribution are almost the same regardless of the parameter s ∈ (−1, 1]. Therefore, by using this truncated code, Wyner’s
common information is achievable for any s ∈ (−1, 1].
However, the proof of the converse part for the normalized Rényi common information is not straightforward.3 We attempted
to use the method of types to prove it, just as in [10] for the Rényi resovability problem, but failed since the code for the
common information problem is arbitrary and does not need to be i.i.d. In particular, it is not i.i.d. In the following two
2 Interestingly, a truncated code is not necessary for s ∈ (−1, 0] case, since an i.i.d. code (without truncation) is optimal as well for this case. This point
can be seen from the work of Yu and Tan [10].
3 More precisely, the proof of the converse part for s ∈ (−1, 0) case is not easy. The converse part for s = 0 case was proven by Wyner [1], in which the
1
n ) is small then 1 H (X n Y n )
D(PX n Y n kπXY
continuity of the normalized entropy under the normalized KL divergence measure was used, i.e., when n
n P
is arbitrarily close to Hπ (XY ). But it is not straightforward to apply Wyner’s proof to the case s ∈ (−1, 0), since we do not know whether a strong enough
continuity condition for the normalized entropy holds under the normalized Rényi divergence measure with order α = 1 + s ∈ (0, 1). Even if a strong enough
continuity condition holds, it is not straightforward to prove. Note that we were not able to directly utilize ideas in Wyner’s converse proof to demonstrate
p (u)
1
this point. The definition of the “relative entropy typical set” A(n, ǫ1 ) := u : n
log p1 (u) ≤ ǫ1 is crucial in Wyner’s proof. If we adopt this set with this
0
definition for the Rényi divergence setting (with Rényi parameter < 1), it is not clear to us whether P1 (Ac (n, ǫ1 )) vanishes (cf. Equation (A.7) in Wyner’s
paper).

5

sections, we provide an indirect proof using the following strategy: We first prove an exponential strong converse for Wyner’s
common information problem under the TV distance measure in Section III. Then by using a relationship between the Rényi
divergence and the TV distance [15], we show this exponential strong converse implies the converse for normalized Rényi
divergence in Section IV.
As an intermediate result, the common information under the TV distance measure is characterized in the following theorem.
Theorem 2 (Common Information under the TV Distance Measure). The following hold:
(i) The common information under the TV distance measure satisfies
(
CWyner (X; Y ) ε ∈ [0, 1)
TV
Tε (πXY ) =
.
0
ε=1

(19)

Hence, the strong converse property for the common information problem under the TV distance holds.
(ii) Furthermore, there exists a sequence of synthesis codes with rate R > CWyner (X; Y ), such that |PX n Y n − πX n Y n | tends
to zero exponentially fast as n tends to infinity.
(iii) On the other hand, for any sequence of synthesis codes with rate R < CWyner (X; Y ), we have that |PX n Y n − πX n Y n |
tends to one exponentially fast as n tends to infinity.
Part (ii) is an exponential achievability result while the part (iii) is an exponential strong converse result. Combining parts (ii)
and (iii) implies part (i). By Pinsker’s inequality for Rényi divergences [23], the achievability results (including the exponential
achievability result) in Theorem 1 implies the achievability results (including the exponential achievability result) in Theorem 2.
Conversely, the exponential strong converse result in part (iii) of Theorem 2 implies the converse results in Theorem 1 for both
unnormalized and normalized Rényi divergences. To prove part (iii), we draw on several key ideas from Oohama’s work [14] on
the exponential strong converse for the Wyner-Ziv problem. However, there are several key differences in our proofs, including
the way we establish that the strong converse exponent is positive for all rates larger than CWyner (X; Y ) and the treatment of
the cases when various probability mass functions take on the value zero.
We note that conclusion in part (ii) (the exponential achievability result) in Theorem 2 can be also obtained by using the
soft-covering lemma by Cuff [5, Lemma IV.1].
The proof of the conclusion in part (iii) is provided in the next section. As mentioned above, the other parts follow directly
from Theorem 1.
III. T HE P ROOF

OF

PART ( III )

IN

T HEOREM 2

In this section, we provide an exponential strong converse theorem for the common information problem under the TV
distance measure, which will be used to derive the converse for normalized Rényi divergence in next section.
We define
n
o
Q := QXY U ∈ P(X × Y × U) : |U| ≤ |X ||Y|, supp(QXY ) ⊆ supp(πXY ) .
(20)

Given α ∈ [0, 1] and an arbitrary distribution QXY U ∈ Q, define the linear combination of the likelihood ratios for (x, y, u) ∈
supp(QXY U ),
!
QXY |U (x, y|u)
QXY |U (x, y|u)
QXY (x, y)
(α)
+ α log
+ log
.
(21)
ωQXY U (x, y|u) := ᾱ log
πXY (x, y)
QX|U (x|u)QY |U (y|u)
πXY (x, y)

This function is finite for all (x, y, u) ∈ supp(QXY U ). For QXY U ∈ Q and θ ∈ [0, ∞), define the negative cumulant generating
functions as
h
i
(α)
(22)
Ω(α,θ) (QXY U ) := − log EQXY U exp − θωQXY U (X, Y |U ) ,
Ω(α,θ) :=

min

QXY U ∈Q

Ω(α,θ) (QXY U ),

(23)

where EQXY U is only taken over the set supp(QXY U ) (this means we only sum over the elements (x, y, u) such that
QXY U (x, y, u) > 0).
Finally, we define the large deviations rate functions
Ω(α,θ) − θαR
,
1 + (5 − 3α)θ
F (R) :=
sup
F (α,θ) (R).

F (α,θ) (R) :=

(24)
(25)

(α,θ)∈[0,1]×[0,∞)

In view of the definitions above, we have the following theorem. The proof of this theorem is provided in Appendix B.

6

Theorem 3. For any synthesis code such that
1
log |Mn | ≤ R,
n
we have

(26)


|PX n Y n − πX n Y n | ≥ 1 − 4 exp − nF (R) .

(27)

If we show F (R) > 0, then Theorem 3 implies the exponential strong converse for TV distance measure. To that end, we
need the following lemma.
Lemma 1. The following conclusions hold.
(i) If R < CWyner (X; Y ), then
F (R) > 0.

(28)

F (R) = 0.

(29)

(ii) If R ≥ CWyner (X; Y ), then

The proof of Lemma 1 is provided in Appendix C. We remark that Lemma 1, especially part (i), plays an central role
in claiming the exponential strong converse theorem for the common information problem with the TV distance measure. Its
proof is completely different from that for the corresponding statement in [14] and requires some intricate continuity arguments
(e.g., [25, Lemma 14]). As we have seen in Theorem 3, F (R) in (25) is a lower bound on the exponent of 1−|PX n Y n − πX n Y n |.
This can be regarded as the strong converse exponent.
Combining Lemma 1 and Theorem 3, we conclude that the exponent in the right hand side of (27) is strictly positive if
the rate is smaller than CWyner (X; Y ). Hence, we obtain the exponential strong converse result given in the conclusion (iii) of
Theorem 2.
IV. C ONVERSE P ROOF

OF

T HEOREM 1 FOR THE N ORMALIZED R ÉNYI C OMMON I NFORMATION

In this section, we provide a proof of the converse part of Theorem 1 for the normalized Rényi common information. To
this end, we need the following relationships between the Rényi divergence and the TV distance.
Lemma 2 (Relationship between the Rényi Divergence and the TV Distance (Sason [15])). For any s ∈ (−1, +∞),
inf

PX ,QX :|PX −QX |≥ǫ

D1+s (PX kQX ) =
=

and for any s ∈ (0, 1),

inf

PX ,QX :|PX −QX |=ǫ

inf

q∈[0,1−ǫ]

D1+s (PX kQX )

d1+s (q + ǫkq),



+
1−s
1
1
inf d1−s (q + ǫkq) ≥ min 1,
log
− log 2 ,
q∈[0,1−ǫ]
s
1−ǫ s


where
d1+s (pkq) :=

(

1
s

log(p1+s q −s + p̄1+s q̄ −s ),
p log pq + p̄ log p̄q̄ ,

s ≥ −1, s 6= 0
s=0

(30)
(31)

(32)

(33)

denotes the binary Rényi divergence of order 1 + s.4 We also have
inf

PX ,QX :|PX −QX |≥ǫ

D0 (PX kQX ) =

inf

PX ,QX :|PX −QX |=ǫ

D0 (PX kQX )

= 0.

(34)
(35)

Remark 3. Pinsker’s inequality provides a lower bound for inf PX ,QX :|PX −QX |≥ǫ D1+s (PX kQX ) or inf PX ,QX :|PX −QX |=ǫ
D1+s (PX kQX ), i.e.,
inf

PX ,QX :|PX −QX |=ǫ

Hence
4 For

(1+s)ǫ2
2

D1+s (PX kQX ) ≥

(1 + s)ǫ2
.
2

is also a lower bound of inf q∈[0,1−ǫ] d1+s (q + ǫkq).

s = 0 case, the binary Rényi divergence is known as the binary relative entropy, and it is usually denoted as d(pkq).

(36)

7

Remark 4. Using (31) and the lower bound in (32), it is easy to obtain the following improved lower bounds. For any s ∈ (0, 1),
inf

PX ,QX :|PX −QX |≥ǫ

D1−s (PX kQX ) =

inf

sup D1−t (PX kQX )

(37)

D1−t (PX kQX )

(38)

PX ,QX :|PX −QX |≥ǫ t∈[s,1)

≥ sup

inf

t∈[s,1) PX ,QX :|PX −QX |≥ǫ

≥ sup

inf

t∈[s,1) q∈[0,1−ǫ]

d1−t (q + ǫkq)


+


1
1
1−t
log
− log 2
≥ sup min 1,
t
1−ǫ
t
t∈[s,1)
h
i+

1

s ∈ (0, 12 ],

hlog 4(1−ǫ)
i+
1
1
1−s
=
s ∈ ( 12 , 1), ǫ > 12

s log 1−ǫ − s log 2


0
s ∈ ( 12 , 1), ǫ ≤ 12

and for any s ∈ [0, +∞),
inf

PX ,QX :|PX −QX |≥ǫ

D1+s (PX kQX ) ≥

inf

D1−t (PX kQX )

(43)

inf

inf

t∈(0,1) q∈[0,1−ǫ]

d1−t (q + ǫkq)



+
1−t
1
1
min 1,
log
− log 2
t
1−ǫ
t
t∈(0,1)

+
1
= log
.
4 (1 − ǫ)

≥ sup

(41)

(42)

t∈(0,1) PX ,QX :|PX −QX |≥ǫ

≥ sup

(40)

sup D1−t (PX kQX )

PX ,QX :|PX −QX |≥ǫ t∈(0,1)

≥ sup

(39)



(44)
(45)
(46)

Remark 5. The improved lower bounds (41) and (46) (or combining (31) and the lower bound in (32)) implies if
|PX − QX | → 1,

(47)

D1+s (PX kQX ) → ∞.

(48)

then for any s ∈ (−1, +∞),

Combining Lemma 2 with Theorem 3, we have the converse part for the normalized Rényi divergence, which implies the
strong converse for the unnormalized Rényi divergence.
Theorem 4. For any synthesis codes such that
lim sup
n→∞

1
log |Mn | < CWyner (X; Y ),
n

(49)

1
D1+s (PX n Y n kπX n Y n ) > 0.
n

(50)

we have for any s > −1,
lim inf
n→∞

Remark 6. This theorem establishes the converse part of Theorem 1 for the normalized Rényi common information.
Remark 7. Since lim inf n→∞ n1 D1+s (PX n Y n kπX n Y n ) > 0 implies D1+s (PX n Y n kπX n Y n ) → ∞, the theorem above implies
the strong converse for the Wyner’s common information problem under the unnormalized Rényi divergence.
Proof: Theorem 3 states if

1
n

log |Mn | < CWyner (X; Y ), then |PX n Y n − πX n Y n | → 1 exponentially fast. In other words,
|PX n Y n − πX n Y n | ≥ 1 − e−nδn ,

for some sequence δn > 0 such that lim inf n→∞ δn > 0. Therefore, using Lemma 2 we have






1
1−s
1−s
1
n
n
n
n
δ
−
lim inf δn > 0.
)
≥
lim
inf
min
1,
kπ
D
(P
log
2
=
min
1,
lim inf
n
X Y
1+s
X Y
n→∞
n→∞
n→∞ n
s
ns
s
This completes the proof.

(51)

(52)

8

V. C ONCLUSION AND F UTURE W ORK
In this paper, we studied a generalized version of Wyner’s common information problem (or the distributed source simulation
problem), in which the unnormalized and normalized Rényi divergences were used to measure the level of approximation. We
showed the minimum rate needed to ensure that the unnormalized or normalized Rényi divergence vanishes asymptotically
remains the same as the one under Wyner’s setting where the relative entropy was used.
In the future, we plan to investigate the second-order coding rate for Wyner’s common information under the unnormalized
Rényi divergence or the TV distance. For the unnormalized Rényi divergence, the one-shot achievability bound given in
Lemma 3 can be used to obtain an achievability bound for the second-order coding rate. In fact, it can easily be shown that the
optimal second-order coding rate scales as O( √1n ). For the TV distance, the one-shot achievability bound given by Cuff [5]
can be used to derive an achievability bound. However, the converse parts for both cases are not straightforward. One may
leverage the perturbation approach [26] used to prove the second-order coding rate for the Gray-Wyner problem in [27], [28].
This is left as future work.
Furthermore, we are also interested in various closely-related problems. Among them, the most interesting one is the
distributed channel synthesis problem under the Rényi divergence measure: The coordination problem or distributed channel
synthesis problem was first introduced by Cuff, Permuter, and Cover [4], [5]. In this problem, an observer (encoder) of a source
sequence describes the sequence to a distant random number generator (decoder) that produces another sequence. What is the
minimum description rate needed to produce achieve a joint distribution that is statistically indistinguishable, under the TV
distance, from the distribution induced by a given channel? For this problem, Cuff [5] provided a complete characterization
of the minimum rate. We can enhance the level of coordination by replacing the TV measure with the Rényi divergence. For
this enhanced version of the problem, we are interested in characterizing the corresponding admissible rate region.
P ROOF

OF

T HEOREM 1

FOR THE

A PPENDIX A
U NNORMALIZED R ÉNYI C OMMON I NFORMATION

A. Achievability
Next we focus on the achievability part. We first consider the case s ∈ (0, 1]. First we introduce the following one-shot
achievability bound (i.e., achievability bound for blocklength n equal to 1).
Lemma 3 (One-Shot Achievability Bound). [10] Consider a random mapping PX|W and a random codebook U = {W (i)}i∈M
with W (i) ∼ PW , i ∈ M, where M = {1, . . . , eR }. We define
1 X
PX|W (x|w(m))
(53)
PX|U (x| {w(i)}i∈M ) :=
|M|
m∈M

Then we have for s ∈ (0, 1],

esD1+s (PX|U kπX |PU ) ≤ esD1+s (PX|W kπX |PW )−sR + esD1+s (PX kπX )
≤ 2e

sΓ1+s (PW ,PX|W ,πX ,R)

,

(54)
(55)

where
Γ1+s (PW , PX|W , πX , R)

:= max D1+s (PX|W kπX |PW ) − R, D1+s (PX kπX ) .

(56)

Remark 8. This lemma provides a one-shot achievability bound for general source synthesis problems, not only for the
distributed source synthesis or common information problem as studied in this paper.
By setting πX , PX|W , PW , and R to πX n Y n , PX n Y n |W n = PX n |W n PY n |W n ,5 PW n , and nR respectively, Lemma 3 can be
used to derive an achievability result for the common information problem. Applying Lemma 3 and taking limits appropriately,
we obtain if there exists a sequence of distributions PW n PX n |W n PY n |W n such that limn→∞ D1+s (PX n Y n kπX n Y n ) → 0
and R > lim supn→∞ n1 D1+s (PX n Y n |W n kπX n Y n |PW n ), then there exists a sequence of codes such that
lim sup D1+s (PX n Y n |Un kπX n Y n |PUn )
n→∞
o
n
1
≤ lim sup log esD1+s (PX n Y n |W n kπX n Y n |PW n )−nsR + esD1+s (PX n Y n kπX n Y n )
n→∞ s


1
≤ log lim sup es(D1+s (PX n Y n |W n kπX n Y n |PW n )−nR) + 1
s
 n→∞

1
s(n(R−ǫ)−nR)
≤ log lim sup e
+1
s
n→∞
= 0,
5 The

pair (X n , Y n ) plays the role of X in Lemma 3.

(57)
(58)
(59)
(60)

9

where (59) follows since R > lim supn→∞ n1 D1+s (PX n Y n |W n kπX n Y n |PW n ) implies there exists a constant ǫ > 0 such that
R − ǫ > n1 D1+s (PX n Y n |W n kπX n Y n |PW n ) holds for all sufficiently large n. Therefore, the minimum achievable rate satisfies

inf R : D1+s (PX n Y n |Un kπX n Y n |PUn ) → 0
1
(61)
≤
inf
lim sup D1+s (PX n Y n |W n kπX n Y n |PW n ).
n
{PW n ,PX n |W n ,PY n |W n }∞
:
n→∞
n=1
D1+s (PX n Y n kπX n Y n )→0

Let QW XY be a distribution such that QXY = πXY and X − W − Y . For the optimization in (61), to obtain an upper
bound, we set the distributions
PW n (wn ) ∝ QnW (wn ) 1 {wn ∈ Tǫn′ (QW )} ,
PX n |W n (xn |wn ) ∝ QnX|W (xn |wn ) 1 {xn ∈ Tǫn (QW X |wn )} ,
n

n

PY n |W n (x |w ) ∝

QnY |W

n

n

n

(x |w ) 1 {y ∈

Tǫn

and

n

(QW Y |w )} ,

(62)
(63)
(64)

where 0 < ǫ′ < ǫ ≤ 1. Then we have
PX n Y n (xn , y n )
X
=
PW n (wn ) PX n |W n (xn |wn ) PY n |W n (xn |wn )

(65)

wn

=

X Qn (wn ) 1 {wn ∈ T n′ (QW )} QnX|W (xn |wn ) 1 {xn ∈ Tǫn (QW X |wn )}
W
ǫ
n (T n )
Q
QnX|W (Tǫn (QW X |wn ) |wn )
′
n
ǫ
W
w
×

≤
=

QnW

QnY |W (xn |wn ) 1 {y n ∈ Tǫn (QW Y |wn )}

QnY |W (Tǫn (QW Y |wn ) |wn )
P
n
n
n n
w n QW XY (w , x , y )
n
n
n
n
n
(Tǫ′ ) minwn ∈Tǫn′ QX|W (Tǫ (QW X |w ) |w ) minwn ∈Tǫn′ QnY |W (Tǫn (QW Y |wn ) |wn )

πX n Y n (xn , y n )
,
1 − δn

(66)
(67)
(68)

where in (68) δn is defined as 1 minus the denominator
 This follows since
 of (67). Here we claim that δn → 0 as n → ∞.
QnW (Tǫn′ ) → 1, minwn ∈Tǫn′ QnX|W Tǫn (QW X |wn )|wn → 1, and minwn ∈Tǫn′ QnY |W Tǫn (QW Y |wn )|wn → 1, where the last
two limits hold due to the following lemma.

Lemma 4. Assume 0 < ǫ′ < ǫ ≤ 1, then as n → ∞, QnX|W Tǫn (QW X |wn )|wn converges uniformly6 to 1 (in wn ∈ Tǫn′ (QW )).
More explicitly,


 1  ǫ−ǫ′ 2 (min)
′ 2
(min) 

−
nQX|W
nQX|W
− 1 ǫ−ǫ
1 − QnX|W Tǫn (QW X |wn )|wn ≤ |X | |W| e 3 1+ǫ′
+ e 2 1−ǫ′
,
(69)
(min)

for all wn ∈ Tǫn′ (QW ), where QX|W := min(x,w):QX|W (x|w)>0 QX|W (x|w).

This lemma is a stronger version of the conditional typicality lemma in [2], since here the probability converges uniformly,
instead of converging pointwise. However, the proof is merely a refinement of the conditional typicality lemma [2, Appendix 2A]
(by applying the Chernoff bound, instead of the law of large numbers), and hence omitted here. Besides, a similar lemma can
be found in [30, Lemma 2.12], which is established based on a slightly different definition of strong typicality.
Using this upper bound of PX n Y n (xn , y n ) we have
D1+s (PX n Y n kπX n Y n )
X
1
1+s
n n −s
n n
= log
PX
n Y n (x , y )πX n Y n (x , y )
s
n
n
x ,y
X  πX n Y n (xn , y n ) 1+s
1
−s
n n
πX
≤ log
n Y n (x , y )
s
1
−
δ
n
n
n
x ,y
1+s

1
1
= log
s
1 − δn
→ 0.
6 This

(70)
(71)
(72)
(73)


means that for any η > 0, there exists an integer N = Nη such that maxwn ∈T n′ (QW ) 1 − Qn
Tǫn (QW X |w n )|w n ≤ η for all n > Nη .
X|W
ǫ
Here the notion of “uniform convergence” is a slightly different from the conventional one [29, Definition 7.7]. In the conventional definition, the domain of
the functions are fixed but here, the domain Tǫn′ (QW ) depends on n.

10

Let [TW VX|W ] denote the joint distribution of X and W induced by the type TW and conditional type VX|W . Now define
the sets of tuples of types and conditional types:


 (TW , VX|W , VY |W ) : ∀w, |TW (w) − QW (w)| ≤ ǫ′ QW (w) 
∀(w, x), [TW VX|W ](w, x) − QW X (w, x) ≤ ǫQW X (w, x)
A :=
, and
(74)


∀(w, y), [TW VY |W ](w, y) − QW Y (w, y) ≤ ǫQW Y (w, y)


(TW , VX|W , VY |W ) : ∀(w, x, y),


[TW VX|W VY |W ](w, x, y)
(1 + ǫ)2
(1 − ǫ)2
B :=
.
(75)
≤
≤


′
′
1+ǫ
QW XY (w, x, y)
1−ǫ


In (75), if QW XY (w, x, y) = 0, this imposes that TW VX|W VY |W (w, x, y) = 0. It is easy to verify that A ⊆ B. Let δ1,n
and δ2,n be two arbitrary sequences tending to zero as n → ∞. Using these notations, we can write
1
D1+s (PW n X n Y n kPW n πX n Y n )
n
X
1
=
log
P (wn ) (P (xn |wn ) P (y n |wn ))1+s π −s (xn , y n )
(76)
ns
w n ,xn ,y n
X
1
log
P (wn , xn , y n )
=
ns
w n ,xn ,y n
!s
QnX|W (xn |wn ) 1 {xn ∈ Tǫn (QW X |wn )} QnY |W (xn |wn ) 1 {y n ∈ Tǫn (QW Y |wn )}
−s
n n
πX
(77)
×
n Y n (x , y )
QnX|W (Tǫn (QW X |wn ) |wn )
QnY |W (Tǫn (QW Y |wn ) |wn )
X
X
1
=
log
P (wn , xn , y n )
ns
n
n
n
TW ,VX|W ,VY |W w ∈TTW ,x ∈TVX|W (w ),
y n ∈TVY |W (w n )

QnX|W (xn |wn ) 1 {xn ∈ Tǫn (QW X |wn )} QnY |W (xn |wn ) 1 {y n ∈ Tǫn (QW Y |wn )}

×
≤

1
log
ns

×
≤−

QnY |W (Tǫn (QW Y |wn ) |wn )

−s
n n
πX
n Y n (x , y )

(78)

P (wn , xn , y n )

(TX ,VX|W ,VY |W )∈A w n ∈TTW ,xn ∈TVX|W (w n ),

e

y n ∈TVY |W (w n )
!s
P
P
n w,x T (w,x) log Q(x|w) n w,y T (w,y) log Q(y|w)

e

1 − δ1,n

1
1
log(1 − δ1,n )(1 − δ2,n ) +
log
n
ns
×

≤

QnX|W (Tǫn (QW X |wn ) |wn )
X
X

!s

max

(TX ,VX|W ,VY |W )∈B

max

(TX ,VX|W ,VY |W )∈B

esn

X

P

w,x

1 − δ2,n
X

e−ns

P

x,y

T (x,y) log π(x,y)

X

n

(79)

P (wn , xn , y n )

n

n

(TX ,VX|W ,VY |W )∈B w ∈TTW ,x ∈TVX|W (w ),

T (w,x) log Q(x|w)+sn

T (w, x) log Q (x|w) +

w,x

X

P

y n ∈TVY |W (w n )

w,y

T (w,y) log Q(y|w)−ns

T (w, y) log Q (y|w) −

w,y

P

x,y

X

T (x,y) log π(x,y)

(80)
!

T (x, y) log π (x, y)

x,y

1
log(1 − δ1,n )(1 − δ2,n )
n
!
X
(1 + ǫ)2 X
(1 − ǫ)2 X
Q (w, x) log Q (x|w) +
Q (x, y) log π (x, y)
Q (w, y) log Q (y|w) −
≤
′
1+ǫ
1 − ǫ′ x,y
w,x
w,y
−

1
log(1 − δ1,n )(1 − δ2,n )
n
(1 − ǫ)2
(1 + ǫ)2
1
=−
(H
(X|W
)
+
H
(Y
|W
))
+
HQ (XY ) − log(1 − δ1,n )(1 − δ2,n )
Q
Q
1 + ǫ′
1 − ǫ′
n
4ǫ
1
(1 − ǫ)2
IQ (XY ; W ) +
HQ (XY ) − log(1 − δ1,n )(1 − δ2,n ),
=
′
′
1+ǫ
1−ǫ
n
where (79) follows from Lemma 4, (80) follows since A ⊆ B, (81) follows since
X
X
P (wn , xn , y n ) ≤ 1,
−

n

n

n

(TX ,VX|W ,VY |W )∈B w ∈TTW ,x ∈TVX|W (w ),
y n ∈TVY |W (w n )

(81)

(82)
(83)
(84)

(85)

11

and (83) follows since QXY = πXY .
Letting n → ∞ in (84), we have
1
4ǫ
(1 − ǫ)2
IQ (XY ; W ) +
HQ (XY ).
D1+s (PW n X n Y n kPW n πX n Y n ) ≤
′
1+ǫ
1 − ǫ′
n→∞ n
Combining (86) with (61) and (73), we obtain

4ǫ
(1 − ǫ)2
IQ (XY ; W ) +
HQ (XY ).
inf R : D1+s (PX n Y n |Un kπX n Y n |PUn ) → 0 ≤
1 + ǫ′
1 − ǫ′
Since ǫ > ǫ′ > 0 are arbitrary, and HQ (XY ) = Hπ (XY ) ≤ log {|X ||Y|} is bounded, we have

inf R : D1+s (PX n Y n |Un kπX n Y n |PUn ) → 0 ≤ IQ (XY ; W ).

(86)

lim sup

(87)

(88)

Since the distribution QW XY is arbitrary, we can minimize IQ (XY ; W ) over all distributions satisfying QXY = πXY and
X − W − Y . Hence

min
IQ (XY ; W ) = CWyner (X; Y ).
(89)
inf R : D1+s (PX n Y n |Un kπX n Y n |PUn ) → 0 ≤
QXY W : QXY =πXY , X−W −Y

Observe that

1
D1+s (PX n Y n |Un kπX n Y n |PUn ) = log EUn
s

 X

xn ,y n

n

n

PX n Y n |Un (x , y |Un )



PX n Y n |Un (xn , y n |Un )
πX n Y n (xn , y n )

s 
,

(90)

where EUn is the expectation taken with respect to the distribution PUn . Hence D1+s (PX n Y n |Un kπX n Y n |PUn ) → 0 implies
that there must exist at least one sequence of codebooks indexed by {un }∞
n=1 such that D1+s (PX n Y n |Un =un kπX n Y n ) → 0.
Therefore, the Rényi common information for s ∈ (0, 1] is not larger than CWyner (X; Y ). This completes the proof for the
case s ∈ (0, 1].
Now we prove the case s ∈ (−1, 0). Since D1+s (PX n Y n kπX n Y n ) is non-decreasing in s, the result for s ∈ (0, 1] implies
the achievability result for s ∈ (−1, 0).
B. Exponential Achievability
Since D1+s (PX n Y n Un kπX n Y n × PUn ) is non-decreasing in s, to prove the exponential result for s ∈ (−1, 1], we only need
to show the result holds for s ∈ (0, 1]. To this end, we use the random code given in Appendix A-A. For this code, by Lemma
3, we obtain
esD1+s (PX n Y n Un kπX n Y n ×PUn )
≤ esD1+s (PW n X n Y n kPW n πX n Y n )−nsR + esD1+s (PX n Y n kπX n Y n )


= esD1+s (PX n Y n kπX n Y n ) esD1+s (PW n X n Y n kPW n πX n Y n )−nsR−sD1+s (PX n Y n kπX n Y n ) + 1 .

(91)
(92)

Taking log’s and normalizing by s,

D1+s (PX n Y n Un kπX n Y n × PUn )


1
= D1+s (PX n Y n kπX n Y n ) + log esD1+s (PW n X n Y n kPW n πX n Y n )−nsR−sD1+s (PX n Y n kπX n Y n ) + 1
(93)
s
1
≤ D1+s (PX n Y n kπX n Y n ) + esD1+s (PW n X n Y n kPW n πX n Y n )−nsR−sD1+s (PX n Y n kπX n Y n ) .
(94)
s
Note that in (68), δn tends to zero exponentially
fast as n → ∞, since QnW (Tǫn′ ),
We first consider the first term of (94).


n
n
n
n
n
n
n
n
n
n
minwn ∈Tǫ′ QX|W Tǫ (QW X |w )|w , and minwn ∈Tǫ′ QY |W Tǫ (QW Y |w )|w all tend to one exponentially fast as n →
∞. Combining this with (73), we obtain that D1+s (PX n Y n kπX n Y n ) → 0 exponentially fast.
Furthermore, by (84) we can write the exponent of the second term of (94) as
1
1
lim inf sR − sD1+s (PW n X n Y n kPW n πX n Y n ) + sD1+s (PX n Y n kπX n Y n )
n→∞
n
 n
(1 − ǫ)2
4ǫ
= sR − s
IQ (XY ; W ) +
HQ (XY ) .
(95)
1 + ǫ′
1 − ǫ′

Since HQ (XY ) = Hπ (XY ) ≤ log {|X ||Y|} is bounded and R > IQ (XY ; W ), by choosing sufficiently small ǫ > ǫ′ > 0, we
can ensure this exponent is positive.
Combining the two points above, we conclude that the optimal D1+s (PX n Y n Un kπX n Y n × PUn ) tends to zero exponentially
fast as long as R > CWyner (X; Y ). On the other hand, by a similar argument in Appendix A-A, D1+s (PX n Y n |Un kπX n Y n |PUn ) →
0 exponentially fast implies that there must exist at least one sequence of codebooks indexed by {un }∞
n=1 such that
D1+s (PX n Y n |Un =un kπX n Y n ) → 0

exponentially fast. Hence the proof is completed.

12

A PPENDIX B
P ROOF OF T HEOREM 3
A. Proof of Theorem 3
In this section, we present the proof of Theorem 3. In the proof, we adapt the information spectrum method proposed by
Oohama [14] to first establish a non-asymptotic lower bound on |PX n Y n − πX n Y n |. Invoking the lower bound (cf. Lemma 6)
and applying Cramér’s bound in the theory of large deviations [31], we can obtain a further lower bound on |PX n Y n − πX n Y n |
leading to (27).
Let PMn X n Y n be the joint distribution of (Mn , X n , Y n ), induced by the synthesis code, i.e.,
PMn X n Y n (m, xn , y n ) =

1
PX n |Mn (xn |m)PY n |Mn (y n |m).
|Mn |

(96)

In the following, for brevity sometimes we omit the subscript, and write PMn X n Y n as P .
Let QX n Y n and QX n Y n |Mn be arbitrary distributions. Given any η > 0, define the following information-spectrum sets and
support sets:
o
n
πX n Y n (xn , y n )
1
≥
−η
× Mn ,
(97)
A1 := (xn , y n ) : log
n
QX n Y n (xn , y n )
o
n
PX n |Mn (xn |w)PY n |Mn (y n |m)
1
≥
−η
,
(98)
A2 := (xn , y n , m) : log
n
QX n Y n |Mn (xn , y n |m)
n
o
QX n Y n |Mn (xn , y n |m)
1
A3 := (xn , y n , m) : log
≤
R
+
η
,
(99)
n
πX n Y n (xn , y n )
(100)
Ae1 := supp(πX n Y n ) × Mn ,
Ae2 := supp(PX n Y n Mn ),
Ae := Ae1 ∩ Ae2 .

(101)

(102)

n n
). For i = 1,Q
. . . , n, let QXi Yi Ui Vi be any
Qndistribution and let QX Y =
QnChoose Ui = Mn andQVni = (X , Y
n
n
n
i−1
i−1
i−1
i−1
,
where
Q
=
Q
=
Q
and
Q
Q
=
Q
Xi Yi |Vi
X Y |Mn
Y
Y
i=1 Xi Yi |Mn X
i=1 Xi Yi |Ui Vi
i=1 Xi Yi |X
i=1 Xi Yi |Vi
and QXi Yi |Ui Vi are conditional distributions induced by QXi Yi Ui Vi . Paralleling (97) to (99), given any η > 0, we define the
following memoryless version of information-spectrum sets:
(
)
n
QXi Yi |Vi (xi , yi |vi )
1X
n n n
B1 := (x , y , v ) :
log
≤ η × Mnn ,
(103)
n i=1
πXY (xi , yi )
(
)
n
QXi Yi |Ui Vi (xi , yi |ui , vi )
1X
n n
n n
B2 := (x , y , u , v ) :
log
≤η ,
(104)
n i=1
PXi |Ui Vi (xi |ui , vi )PYi |Ui Vi (yi |ui , vi )
(
)
n
QXi Yi |Ui Vi (xi , yi |ui , vi )
1X
n n
n n
B3 := (x , y , u , v ) :
log
≤R+η .
(105)
n i=1
πXY (xi , yi )

i−1

i−1

We first present a non-asymptotic lower bound on |PX n Y n − πX n Y n |, i.e., a non-asymptotic converse bound for the problem.

Lemma 5. For any synthesis code such that
1
log |Mn | ≤ R,
n
we have
|PX n Y n − πX n Y n | ≥ 1 − P

3
\

i=1


Ai Ae − 3e−nη ,

(106)

(107)

n
n
n
n
e =P n n
where P (·|A)
e denotes the conditional distribution of (X , Y , Mn ) ∼ PMn X n Y n given that (X , Y , Mn ) ∈
X Y Mn |A
e with PMn X n Y n denoting the distribution induced by the synthesis code.
A,

The proof of Lemma 5 is given in Appendix B-B.
Invoking Lemma 5 and choosing the distributions QX n Y n and QX n Y n |Mn as in the paragraph above (103), we obtain the
following lemma.
Lemma 6. Given the conditions in Lemma 5, we have
|PX n Y n − πX n Y n | ≥ 1 − P

3
\

i=1


Bi Ae − 3e−nη .

(108)

13

The proof of Lemma 6 is given in Appendix B-C.
In the following, for simplicity, we will use Qi to denote QXi Yi Ui Vi and use Pi to denote PXi Yi Ui Vi . Let α ∈ [0, 1]. Then
(α)
we need the following definitions to further lower bound (108). Similar to the definition of ωQXY U (x, y|u) in (21), we define
!
QXi Yi |Vi (xi , yi |vi )
QXi Yi |Ui Vi (xi , yi |ui , vi )
(α)
ωQi ,Pi (xi , yi |ui , vi ) := ᾱ log
+ log
πXY (xi , yi )
PXi |Ui Vi (xi |ui , vi )PYi |Ui Vi (yi |ui , vi )
+ α log

QXi Yi |Ui Vi (xi , yi |ui , vi )
.
πXY (xi , yi )

(109)

Then, similar to the definition of Ω(α,θ) (QXY U ) in (22), we define
Ω(α,λ) ({Qi }ni=1 ) := − log

X

xn ,y n ,m

n
i
h

X
(α)
ωQi ,Pi (xi , yi |ui , vi ) .
PX n Y n Mn |Ae(xn , y n , m) exp − λ

(110)

i=1

e
where ui = m, vi = (xi−1 , y i−1 ), and PX n Y n Mn |Ae is the conditional distribution of (X n , Y n , Mn ) given (X n , Y n , Mn ) ∈ A.
Applying Cramér’s bound [31, Section 2.2] and utilizing Lemma 6, we obtain the following lemma. The proof of this lemma
is similar to that of [14, Proposition 1], and hence we omit it for the sake of brevity.
Lemma 7. For any (α, λ) ∈ [0, 1] × [0, ∞), given the condition in Lemma 5, we have
|PX n Y n − πX n Y n | ≥ 1 − 4 exp −n

1 (α,λ)
({Qi }ni=1 )
nΩ

− λαR
1 + (1 + ᾱ)λ

!

.

(111)

Let
Ω(α,λ) := inf

1 (α,λ)
Ω
({Qi }ni=1 ).
n

inf

n≥1 {Qi }n
i=1

(112)

Define
θ :=

λ
.
1 − 2ᾱλ

(113)

λ=

θ
.
1 + 2ᾱθ

(114)

Hence, we have

The next lemma is essential in the proof.
Lemma 8. For α ∈ [0, 1] and λ ∈ [0, 21ᾱ ), we have
Ω(α,λ) ≥

Ω(α,θ)
.
1 + 2ᾱθ

(115)

The proof of Lemma 8 is similar to that of [14, Proposition 2] and given in Appendix B-D. In the proof of Lemma 8, we
adopt ideas from [14] and choose appropriate distributions QXi Yi Ui Vi via the recursive method.
Combining Lemmas 7 and 8 yields
|PX n Y n − πX n Y n |
Ω(α,λ) − λαR
≥ 1 − 4 exp −n
1 + (1 + ᾱ)λ
≥ 1 − 4 exp −n

Ω(α,θ)
1+2ᾱθ

1+

!

θαR
1+2ᾱθ
(1+ᾱ)θ
1+2ᾱθ

−

Ω(α,θ) − θαR
= 1 − 4 exp − n
1 + (5 − 3α)θ

≥ 1 − 4 exp − nF (R) ,

!

!

(116)
(117)
(118)
(119)

where (119) follows from the definition of F (R) in (25) and the fact that (118) holds for any (α, θ) ∈ [0, 1] × (0, +∞). The
proof of Theorem 3 is now complete.

14

B. Proof of Lemma 5
Define πX n Y n Mn := πX n Y n PMn |X n Y n . Then
|PX n Y n − πX n Y n |
= |PX n Y n Mn − πX n Y n Mn |
≥ π(Ae1 ∩ A1 ∩ A3 ) − P (Ae1 ∩ A1 ∩ A3 )
=1−

π(Aec1

∪ Ac1 ∪
3
\


= 1 − P Ae ∩


≥ 1 − P Ae ∩


= 1 − P Ae ∩

i=1
3
\

i=1
3
\

(120)
(121)

− P (Ae1 ∩ A1 ∩ A3 )

Ai − P (Ae1 ∩ A1 ∩ A3 ∩ (Ac2 ∪ Aec2 )) − π(Aec1 ∪ Ac1 ∪ Ac3 )
Ac3 )

Ai
Ai

i=1





− P (Ac2 ) − P (Aec2 ) − π(Aec1 ) − π(Ac1 ) − π(Ac3 )

− P (Ac2 ) − π(Ac1 ) − π(Ac3 )

(122)
(123)
(124)
(125)

The last three terms above can each be bounded above by e−nη because
X

P (Ac2 ) =

P (xn , y n , m)

(126)

P (w)Q(xn , y n |m)e−nη

(127)

(xn ,y n ,m)∈Ac2

≤
n

(x ,y

X
n

,m)∈Ac2

≤ e−nη ,

(128)

and
π(Ac3 ) =
n

(x ,y

≤
n

(x ,y

≤
n

X
n

X
n

(x ,y
−nη

≤e

(129)

Q(xn , y n |m)e−n(R+η) P (m|xn , y n )

(130)

Q(xn , y n |m)e−n(R+η)

(131)

,m)∈Ac3

X
n

π(xn , y n )P (m|xn , y n )

,m)∈Ac3

,m)∈Ac3

(132)

,

and
π(Ac1 ) =
n

X

(x ,y

≤

n

π(xn , y n )

(133)

Q(xn , y n )e−nη

(134)

)∈Ac1

X

(xn ,y n )∈Ac1
−nη

≤e

(135)

.

Therefore, we have
3


\
Ai − 3e−nη
|PX n Y n − πX n Y n | ≥ 1 − P Ae ∩

(136)

i=1

≥1−P

3
\

i=1


Ai Ae − 3e−nη .

(137)

15

C. Proof of Lemma 6
Recall that in Appendix B-A, we choose Ui = Mn and Vi = (X i−1 , Y i−1 ). Then QX n Y n and QX n Y n |Mn can be written
as follows:
n
Y
QXi Yi |X i−1 Y i−1 (xi , yi |xi−1 , y i−1 )
(138)
QX n Y n (xn , y n ) =
=
QX n Y n |Mn (xn , y n |m) =
=

i=1
n
Y

i=1
n
Y

i=1
n
Y
i=1

QXi Yi |Vi (xi , yi |vi ),

(139)

QXi Yi |Mn X i−1 Y i−1 (xi , yi |m, xi−1 , y i−1 )

(140)

QXi Yi |Ui Vi (xi , yi |ui , vi ).

(141)

Now recall from Appendix B-A that the joint distribution of (X n , Y n , Mn ) induced by the code is PX n Y n Mn . The marginal
distributions of PX n Y n Mn are as follows:
πX n Y n (xn , y n ) =
PX n |Mn (xn |m) =
=
=
PY n |Mn (y n |m) =
=
=

n
Y

i=1
n
Y

i=1
n
Y

i=1
n
Y

i=1
n
Y

i=1
n
Y

i=1
n
Y

i=1

πXY (xi , yi ),

(142)

PXi |Mn X i−1 (xi |m, xi−1 )

(143)

PXi |Mn X i−1 Y i−1 (xi |m, xi−1 , y i−1 )

(144)

PXi |Ui Vi (xi |ui , vi ),

(145)

PYi |Mn Y i−1 (yi |m, y i−1 )

(146)

PYi |Mn X i−1 Y i−1 (yi |m, xi−1 , y i−1 )

(147)

PYi |Ui Vi (yi |ui , vi ),

(148)

where (144) and (147) follow from the Markov chains Xi − Mn X i−1 − Y i−1 and Yi − Mn Y i−1 − X i−1 under distribution
PX n Y n Mn (these two Markov chains can be easily obtained by observing that PX i Y i Mn = PMn PXi |Mn X i−1 PYi |Mn Y i−1 ).
Using Lemma 5 and (138)–(148), we obtain
|PX n Y n − πX n Y n | ≥ 1 − P

3
\

i=1


Bi Ae − 3e−nη .

(149)

D. Proof of Lemma 8
1) Removing Dependence on the Indices: Recall from Appendix B-A that the joint distribution of (X n , Y n , Mn ) is
PX n Y n Mn and PXi Yi Ui Vi is induced by PX n Y n Mn . Further, recall that Qi denotes QXi Yi Ui Vi and Pi denotes PXi Yi Ui Vi .
Define


(α)
(α,λ)
(150)
gQi ,Pi (xi , yi |ui , vi ) := exp − λωQi ,Pi (xi , yi |ui , vi ) ,
(α)

where ωQi ,Pi (xi , yi |ui , vi ) is defined in (109).
Recall the definition of Ω(α,λ) ({Qi }ni=1 ) in (110), then we obtain that


exp − Ω(α,λ) ({Qi }ni=1 ) =

X

xn ,y n ,m

PX n Y n Mn |Ae(xn , y n , m)

n
Y

(α,λ)

gQi ,Pi (xi , yi |ui , vi ),

(151)

i=1

e
where ui = m, vi = (xi−1 , y i−1 ), and PX n Y n Mn |Ae is the conditional distribution of (X n , Y n , Mn ) given (X n , Y n , Mn ) ∈ A.

16

For i = 1, . . . , n, define
C̃i :=

X

xn ,y n ,m
(α,λ)|i
PX n Y n M |Ae(xn , y n , m)
n
(α,λ)

Λi
(α,λ)|i

Obviously, PX n Y n M

:=

({Qj }ij=1 ) :=

n n
e(x , y , m)

n |A

PX n Y n Mn |Ae(xn , y n , m)

PX n Y n Mn |Ae(xn , y n , m)

Qi

j=1

i
Y

(α,λ)

(152)

gQj ,Pj (xj , yj |uj , vj ),

j=1
(α,λ)

gQj ,Pj (xj , yj |uj , vj )

C̃i

(153)

,

C̃i
.
C̃i−1

(154)

is a distribution induced by normalizing all the terms of the summation in the definition

of C̃i .
(α,λ)
({Qj }ij=1 ), defined in
Similarly to [14, Lemma 7], we obtain the following lemma, which will be used to simplify Λi
(154), in Appendix B-D2.
Lemma 9. For i = 1, . . . , n, we have
(α,λ)

Λi

({Qj }ij=1 ) =

X

xn ,y n ,m

(α,λ)|i−1

PX n Y n M

(α,λ)
n n
e(x , y , m)gQi ,Pi (xi , yi |ui , vi ).

(155)

n |A

Furthermore, combining (151), (152) and (154) gives us
n

 Y
(α,λ)
({Qj }ij=1 ).
Λi
exp − Ω(α,λ) ({Qi }ni=1 ) =

(156)

i=1

2) Completion of the Proof of Lemma 8: Assume U and V are two countable sets. Paralleling (20) to (23), for (α, θ) ∈
(0, 1] × (0, ∞), we define the following quantities:
n
o
e := QXY UV ∈ P(X × Y × U × V) : supp(QXY ) ⊆ supp(πXY ) ,
Q
(157)
!
QXY |UV (x, y|u, v)
QXY |UV (x, y|u, v)
QXY |V (x, y|v)
(α)
+ α log
+ log
, (158)
ω
eQXY U V (x, y|u, v) := ᾱ log
πXY (x, y)
QX|UV (x|u, v)QY |UV (y|u, v)
πXY (x, y)
i
h

e (α,λ) (QXY UV ) := − log EQXY U V exp − θω (α)
(159)
Ω
QXY U V (X, Y |U, V ) ,
e (α,λ) :=
Ω

inf

e
QXY U V ∈Q

e (α,λ) (QXY UV ),
Ω

(160)

where EQXY U V in (159) is only taken over the set supp(QXY UV ).
Recall that ui = m and vi = (xi−1 , y i−1 ). For each i = 1, . . . , n, define
X
(α,λ)|i−1
PX n Y n M |Ae(xn , y n , m),
P (α,λ) (xi , yi , ui , vi ) :=
n
xn
i+1 ,yi+1

(161)

n

(α,λ)|i−1

where PX n Y n Mn (xn , y n , m) was defined in (153).
Combining Lemma 9 and (161) yields
(α,λ)

Λi

({Qj }ij=1 ) =

X

(α,λ)

P (α,λ) (xi , yi , ui , vi )gQi ,Pi (xi , yi |ui , vi ).

(162)

xi ,yi ,ui ,vi

Note that Qi = QXi Yi Ui Vi can be chosen arbitrarily for all i = 1, . . . , n. Here we apply the recursive method. For each
i = 1, . . . , n, we choose QXi Yi Ui Vi such that
QXi Yi Ui Vi (xi , yi , ui , vi ) = P (α,λ) (xi , yi , ui , vi ).

(163)

Then, let QXi Yi |Vi , QXi Yi |Ui Vi be induced by QXi Yi Ui Vi .
Define
(α,λ)
hQi (xi , yi |ui , vi )

:=

(α,λ)
gQi ,Pi (xi , yi |ui , vi )

λᾱ
(xi |ui , vi )PYλiᾱ|Ui Vi (yi |ui , vi )
PX
i |Ui Vi

λᾱ
(yi |ui , vi )
(xi |ui , vi )QYλᾱ
QX
i |Ui Vi
i |Ui Vi

!−1

,

(164)

17

(α,λ)

where gQi ,Pi was defined in (150). In the following, for brevity, we drop the subscripts of the distributions. From (162), we
obtain
(α,λ)

Λi

(α,λ)

({Qj }ij=1 ) = EQi [gQi ,Pi (Xi , Yi |Ui , Vi )]
"

λᾱ
λᾱ
PX
|U V (Xi |Ui , Vi )PYi |Ui Vi (Yi |Ui , Vi )
(α,λ)
hQi (Xi , Yi |Ui , Vi ) λᾱi i i
(Yi |Ui , Vi )
QXi |Ui Vi (Xi |Ui , Vi )QYλᾱ
i |Ui Vi

= EQi


≤ EQi

hn

1
i1−2λᾱ
o 1−2λ
ᾱ

(α,λ)
hQi (Xi , Yi |Ui , Vi )

#!λᾱ
PYi |Ui Vi (Yi |Ui , Vi )
× EQi
QYi |Ui Vi (Yi |Ui , Vi )


 (α, λ )
e 1−2λᾱ (Qi )
≤ exp − 1 − 2λᾱ Ω
!
e (α,θ) (Qi )
Ω
= exp −
1 + 2ᾱθ
!
e (α,θ)
Ω
≤ exp −
1 + 2ᾱθ


Ω(α,θ)
,
= exp −
1 + 2ᾱθ
"

EQi

"

#

PXi |Ui Vi (Xi |Ui , Vi )
QXi |Ui Vi (Xi |Ui , Vi )

(165)
(166)
#!λᾱ
(167)
(168)
(169)
(170)
(171)

where (166) follows from (164); (167) follows from Hölder’s inequality; (168) follows from the definitions of Ω(α,θ) (·) and
(α,λ)
e (α,θ)
hQi (·) in (22) and (164) respectively; (169) follows from (113) and (114); (170) follows since Ω(α,θ) (QXY UV ) ≥ Ω
for any QXY UV such that supp(QXY ) ⊆ supp(πXY ) (The fact that Qi satisfies this point will be shown in the following
paragraph); and (171) follows since by the support lemma [2], the cardinality bounds |V| ≤ 1, |U| ≤ |X ||Y| are sufficient to
e (α,θ) .
exhaust Ω
Now we show that according to the choice of QXi Yi Ui Vi , we have supp(QXi Yi ) ⊆ supp(πXY ), which was used in (170).
e and hence the marginal distributions
Note that PX n Y n Mn (xn , y n , m) > 0 and πX n Y n (xn , y n ) > 0 for any (xn , y n , m) ∈ A,
n n
e
PXi Yi Ui Vi , PXi |Ui Vi and PYi |Ui Vi when evaluated at any (x , y , m) ∈ A is positive as well. According to the choice of
QXi Yi Ui Vi in (163), we have that QXi Yi Ui Vi is also positive when evaluated at (xn , y n , m) ∈ Ae (this point can be shown via
mathematical induction), i.e.,
o
n
(172)
supp(QXi Yi Ui Vi ) ⊇ (x, y, u, v) : ∃(xn , y n , m) ∈ Ae : xi = x, yi = y, m = u, (xi−1 , y i−1 ) = v .

On the other hand, also according to the choice of QXi Yi Ui Vi , we have
n
o
supp(QXi Yi Ui Vi ) ⊆ (x, y, u, v) : ∃(xn , y n , m) ∈ Ae : xi = x, yi = y, m = u, (xi−1 , y i−1 ) = v .

Therefore,

n
o
supp(QXi Yi Ui Vi ) = (x, y, u, v) : ∃(xn , y n , m) ∈ Ae : xi = x, yi = y, m = u, (xi−1 , y i−1 ) = v .

Further, we have

n
o
supp(QXi Yi ) = (x, y) : ∃(xn , y n , m) ∈ Ae : xi = x, yi = y

(173)

(174)

(175)

⊆ {(x, y) : ∃(xn , y n , m) ∈ supp(πX n Y n ) × Mn : xi = x, yi = y}

(176)

= supp(πXY ).

(177)

Combining (156) and (171), we obtain that
n

1 (α,λ)
1X
(α,λ)
({Qj }ij=1 )
log Λi
Ω
({Qi }ni=1 ) = −
n
n i=1
≥

Ω(α,θ)
.
1 + 2ᾱθ

(178)
(179)

Finally, combining (112) and (179), we have that
Ω(α,λ) ≥
The proof of Lemma 8 is now complete.

Ω(α,θ)
.
1 + 2ᾱθ

(180)

18

A PPENDIX C
P ROOF OF L EMMA 1
Let U be a random variable taking values in a finite alphabet U. Define a set of joint distributions on X × Y × U as
n
o
P ∗ := PXY U : |U| ≤ |X ||Y|, PXY = πXY , X − U − Y .
(181)

and let

R∗ :=

min

PXY U ∈P ∗

I(XY ; U ).

(182)

A. Preliminary Lemmata for the Proof of Lemma 1
By the support lemma [2, Appendix C], we have the following lemma [1].
Lemma 10. Wyner’s common information CWyner (X; Y ) satisfies
CWyner (X; Y ) = R∗ .

(183)

Before proceeding the proof of Lemma 1, we present an alternative expression for Wyner’s common information. Recall
that given a number a ∈ [0, 1], we define ā = 1 − a. Then for any α ∈ [0, 1] and QXY U ∈ Q, define

R(α) (QXY U ) := ᾱ D(QXY kπXY ) + D(QXY |U kQX|U QY |U |QU )
R

(α)

:=

min

+ αD(QXY |U kπXY |QU ),

QXY U ∈Q

R

(α)

(QXY U )

1 (α)
R .
α
α∈(0,1]

Rsh := sup

(184)
(185)

(186)

By observing that both P ∗ and Q are compact, and by utilizing the fact that a continuous function defined on a compact set
attains its minimum, we obtain the following.
Fact 1. Both the minima in the definitions of R∗ in (182) and R(α) in (185) are attained.
We then have the following lemma.
Lemma 11. The following conclusions hold.
(i) For any α ∈ (0, 1], we have
1 (α)
R ≤ R∗ .
α

(187)

∞

Moreover, there exists some decreasing sequence {αk }k=1 ⊂ R such that limk→∞ αk = 0 and
1 (αk )
R
≥ R∗ − c(αk ),
αk

(188)

where {c(αk )}∞
k=1 ⊂ R is another sequence such that limk→∞ c(αk ) = 0.
(ii) We have
Rsh = R∗ = CWyner (X; Y ).

(189)

Lemma 11 is similar to [14, Property 3], but the proofs are different. Essentially, in both the proof of [14, Property 3] and
e XY U is used to establish the inequality
our proof, an intermediate distribution Q
R∗ − c(αk ) ≤

1 (αk ) e
1 (αk )
R
(QXY U ) ≤
R
.
αk
αk

(190)

However, the construction of such an intermediate distribution is different for these two proofs. The construction in [14] does
e XY U to satisfy the Markov chain X − U − Y , but also requires
not apply to our case, since our case does not only require Q
e
that QXY = πXY .
Proof of Lemma 11: It is easy to show (187). Hence, by the definition of Rsh in (186),
Rsh ≤ R∗ .

∞
{αm }m=1

(191)

In the following we prove (188). Let
be an arbitrary sequence of decreasing positive real numbers such that
(m)
limm→∞ αm = 0, and let QXY U be a minimizing distribution of (185) with α = αm . The existence of this minimizing

19

distribution is guaranteed by Fact 1. Since P(X × Y × U) is compact (following from the definition of Q), there must exist
(mk )
e
some sequence of increasing integers {mk }∞
k=1 such that QXY U converges to some distribution QXY U . Consider,
1 (α)
R
α
α∈(0,1]
1
≥ lim sup
R(αmk )
α
mk
k→∞
(

ᾱmk 
(m )
(m ) (m )
(m )
(m )
D(QXYk kπXY ) + D(QXYk|U kQX|Uk QY |Uk |QU k )
= lim sup
αmk
k→∞
)

Rsh = sup

(mk )

(m )

+ D(QXYk|U ||πXY |QU

≥ lim sup
k→∞

+



ᾱmk
αmk



)

o
n
(m )
(m ) (m )
(m )
(m )
lim inf D(QXYk kπXY ) + D(QXYk|U kQX|Uk QY |Uk |QU k )

(192)
(193)

(194)

k→∞

(m )
lim inf D(QXYk|U ||πXY
k→∞

(mk )

|QU

)


e XY kπXY ) + D(Q
e XY |U kQ
e X|U Q
e Y |U |Q
e U ) + D(Q
e XY |U ||πXY |Q
e U ).
= ∞ D(Q

(195)
(196)

Observe that Rsh is finite due to (191). Hence it holds that

That is,

Therefore, under (199) and (200), we have

e XY kπXY ) = 0,
D(Q
e XY |U kQ
e X|U Q
e Y |U |Q
e U ) = 0.
D(Q

(197)
(198)

e XY = πXY ,
Q
e XY |U = Q
e X|U Q
e Y |U .
Q

(199)

e XY |U kπXY |Q
eU )
(196) ≥ D(Q
e XY |U , Q
e XY )
= I(Q

(201)

(200)

(202)
(203)

∗

≥R .

Combining (191), (196) and (203) yields us

Rsh = R∗ = lim

k→∞

1
R(αmk ) .
αmk

(204)

∗
Therefore, there exists some sequence {c(αmk )}∞
k=1 ⊂ R (e.g., the sequence {R −
limk→∞ c(αmk ) = 0 and
1
R∗ − c(αmk ) ≤
R(αmk ) ≤ R∗ .
αmk

1
αmk

R(αmk ) }∞
k=1 ⊂ R) such that
(205)

This concludes the proof.
We also have the following crucial lemma.
Lemma 12. Let α ∈ (0, 1] and QXY U ∈ Q. Then we have

or equivalently,

1
lim Ω(α,θ) = R(α) ,
θ↓0 θ

(206)

1 (α,θ)
Ω
= R(α) + ǫ(α,θ) ,
θ

(207)

where Ω(α,θ) and R(α) were defined in (23) and (185) respectively, and ǫ(α,θ) is a term that vanishes as θ ↓ 0, the rate being
dependent on α.
Proof of Lemma 12: To show this lemma, we first need to show that
(
1 (α,θ)
Ω
(QXY U ),
(α,θ)
b
R
(QXY U ) := θ (α)
R (QXY U ),

θ>0
θ=0

(208)

20

is continuous in (θ, QXY U ) ∈ [0, 1+1 ᾱ ) × Q. It is easy to observe that
h
i
(α)
Ω(α,θ) (QXY U ) = − log EQXY U exp − θωQXY U (X, Y |U )
X 1−θ(1+ᾱ)
θᾱ
θ
= − log
(x, y, u) QU|XY (u|x, y)QX|U (x|u)QY |U (y|u)
(QU (u)πXY (x, y))
QXY U

(209)
(210)

x,y,u

b (α,θ) (QXY U ) is jointly continuous on (0, 1 ) × Q. Therefore,
is jointly continuous in (θ, QXY U ) ∈ [0, 1+1 ᾱ ) × Q, hence R
1+ᾱ
(α,θ)
b
to show the continuity of R
(QXY U ) in (θ, QXY U ) ∈ [0, 1+1 ᾱ ) × Q, it suffices to show it is continuous at any point in
{0} × Q, i.e.,
1 (α,θ)
Ω
(QXY U ) = R(α) (Q′XY U )
(211)
lim
(θ,QXY U )→(0,Q′XY U ) θ

for any Q′XY U ∈ Q.
Let



(α)
QXY U (x, y, u) exp − θωQXY U (x, y|u)
(α,θ)
.

QXY U (x, y, u) := P
(α)
(x,
y|u)
Q
(x,
y,
u)
exp
−
θω
XY
U
x,y,u
QXY U

(212)

Invoking the definition of Ω(α,θ) (QXY U ) in (22), we obtain

i
h
∂Ω(α,θ) (QXY U )
(α)
= EQ(α,θ) ωQXY U (X, Y |U ) ,
XY U
∂θ

and

Hence for fixed QXY U

h
i
∂ 2 Ω(α,θ) (QXY U )
(α)
= −VarQ(α,θ) ωQXY U (X, Y |U ) .
2
XY U
∂θ
∈ Q, we have
∂Ω(α,θ) (QXY U )
∂θ

which implies that
θ

(213)

(214)

= R(α) (QXY U ) > 0,

(215)

∂ 2 Ω(α,θ) (QXY U )
≤ 0,
∂θ2

(216)

θ=0

∂Ω(α,θ) (QXY U )
≤ Ω(α,θ) (QXY U ) ≤ θR(α) (QXY U ).
∂θ

(217)

Furthermore, observe that R(α) (QXY U ) is continuous in QXY U ∈ Q, hence
lim

QXY U →Q′XY U

On the other hand, observe that

∂Ω(α,θ) (QXY U )
∂θ

lim

(θ,QXY U )→(0,Q′XY U )

R(α) (QXY U ) = R(α) (Q′XY U ).

(218)

given in (213) is continuous in (θ, QXY U ) ∈ [0, 1+1 ᾱ ) × Q. Hence

X
∂Ω(α,θ) (QXY U )
(α)
=
(X, Y |U )
Q′XY U (x, y, u)ωQ′
XY U
∂θ
x,y,u
= R(α) (Q′XY U ).

(219)
(220)

Therefore, combining (217), (218), and (220), we observe that the limit lim(θ,QXY U )→(0,Q′XY U ) θ1 Ω(α,θ) (QXY U ) exists, and
b(α,θ) (QXY U )
moreover, lim(θ,QXY U )→(0,Q′XY U ) θ1 Ω(α,θ) (QXY U ) = R(α) (Q′XY U ). Hence, we obtain (211). In other words, R
1
is jointly continuous in (θ, QXY U ) ∈ [0, 1+ᾱ ) × Q. In addition, observe that Q is a compact set. By using the following lemma
b (α,θ) (QXY U ) is continuous in θ ∈ [0, 1 ).
we can assert that minQXY U ∈Q R
1+ᾱ

Lemma 13 (Lemma 14 in [25]). Let X and Y be two metric spaces and let K ⊂ X be a compact set. Let f : X × Y → R
be a (jointly) continuous real-valued function. Then the function g : Y → R, defined as
g(y) := min f (x, y),
x∈K

(221)

∀ y ∈ Y,

is continuous on Y.
Considering the point θ = 0, we obtain
lim

min

θ→0 QXY U ∈Q

b (α,θ) (QXY U ) =
R

min

QXY U ∈Q

b (α,0) (QXY U ) =
R

min

QXY U ∈Q

R(α) (QXY U ) = R(α) ,

(222)

21

where the first equality follows from Lemma 13 which essentially says that the limit and minimum operations can be swapped.
On the other hand, observe that
lim

min

θ→0 QXY U ∈Q

b (α,θ) (QXY U ) = lim
R

min

θ→0 QXY U ∈Q

1
1 (α,θ)
Ω
(QXY U ) = lim Ω(α,θ) .
θ→0 θ
θ

(223)

Combining (222) and (223), we obtain (206) as desired.
B. Proof of Part (i) in Lemma 1

Using Lemma 10, we obtain that if R < CWyner (X; Y ), then
R + τ ≤ R∗

(224)

for some τ > 0. Further, invoking (188) and (224), we obtain that there exists k0 such that for any k ≥ k0 ,
R+τ ≤

1 (αk )
R
+ c(αk ),
αk

(225)

τ
.
2

(226)

and
c(αk ) ≤
Referring to (225) and (226), we obtain that for any k ≥ k0 ,
R+

τ
1 (αk )
R
.
≤
2
αk

(227)

Therefore, invoking (25), we conclude that for any k ≥ k0 ,
F (R) ≥ sup F (αk ,θ) (R)

(228)

θ≥0

≥

F (αk ,θ) (R)

sup

(229)

θ∈[0, 1+1ᾱ )
k

Ω(αk ,θ) − θαk R
θ∈[0, 1+1ᾱ ) 1 + (5 − 3αk )θ
k
o
1 n (αk )
≥
sup
θR
+ θǫ(αk ,θ) − θαk R
θ∈[0, 1+1ᾱ ) 1 + 5θ
k
θ n (αk ,θ) αk τ o
≥
sup
ǫ
+
2
θ∈[0, 1 ) 1 + 5θ

=

sup

(230)
(231)
(232)

1+ᾱk

≥ sup
e
θ∈[0,θ]

≥

αk τ θ
4(1 + 5θ)

(233)

αk τ θe
,
e
4(1 + 5θ)

(234)

where (231) follows from Lemma 12 and the inequality 1 + (5 − 3αk )θ ≤ 1 + 5θ, (232) follows from (227), and (233) follows
e Since the expression in (234) is
since there exists a sufficiently small θe ∈ (0, 1+1ᾱk ) such that |ǫ(αk ,θ) | ≤ 14 αk τ for all θ ≤ θ.
positive, we have F (R) > 0 as desired.
C. Proof of Part (ii) in Lemma 1
Because exp(·) is convex, applying Jensen’s inequality, we obtain
i
h
(α)
Ω(α,θ) (QXY U ) ≤ θEQXY U ωQXY U (X, Y |U ) = θR(α) (QXY U ).

(235)

Hence we have

Ω(α,θ) ≤

min

QXY U ∈Q

= θR(α) .

θR(α) (QXY U )

(236)
(237)

22

Thus, recalling the definition of F (α,θ) (R) in (24), we obtain that
Ω(α,θ) − θαR
1 + (5 − 3α)θ
θα( α1 R(α) − R)
≤
1 + (5 − 3α)θ
θα(Rsh − R)
≤
1 + (5 − 3α)θ
≤ 0,

F (α,θ) (R) =

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

where (241) follows from the assumption R ≥ CWyner (X; Y ) = Rsh . On the other hand, note that
lim F (α,θ) = 0.

θ→0

(242)

Hence, combining (241) and (242), we conclude that
F =

sup

F (α,θ) (R) = 0.

(243)

(α,θ)∈[0,1]×[0,∞)

ACKNOWLEDGEMENTS
The authors are supported by a Singapore National Research Foundation (NRF) National Cybersecurity R&D Grant (R-263000-C74-281 and NRF2015NCR-NCR003-006).
R EFERENCES
[1] A. Wyner. The common information of two dependent random variables. IEEE Trans. on Inform. Theory, 21(2):163–179, 1975.
[2] A. El Gamal and Y.-H. Kim. Network Information Theory. Cambridge university press, 2011.
[3] G. R. Kumar, C. T. Li, and A. El Gamal. Exact common information. In IEEE International Symposium on Information Theory (ISIT), pages 161–165.
IEEE, 2014.
[4] P. Cuff, H. Permuter, and T. Cover. Coordination capacity. IEEE Trans. on Inform. Theory, 56(9):4181–4206, 2010.
[5] P. Cuff. Distributed channel synthesis. IEEE Trans. on Inform. Theory, 59(11):7071–7096, 2013.
[6] T. Han and S. Verdú. Approximation theory of output statistics. IEEE Trans. on Inform. Theory, 39(3):752–772, 1993.
[7] 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.
[8] M. Hayashi. Exponential decreasing rate of leaked information in universal random privacy amplification. IEEE Trans. on Inform. Theory, 57(6):3989–
4001, 2011.
[9] J. Liu, P. Cuff, and S. Verdú. Eγ -resolvability. IEEE Trans. on Inform. Theory, 63(5):2629–2658, 2017.
[10] L. Yu and V. Y. F. Tan. Rényi resolvability and its applications to the wiretap channel. arXiv preprint 1707.00810, 2017.
[11] M. R. Bloch and J. N. Laneman. Strong secrecy from channel resolvability. IEEE Trans. on Inform. Theory, 59(12):8077–8098, 2013.
[12] T. S. Han, H. Endo, and M. Sasaki. Reliability and secrecy functions of the wiretap channel under cost constraint. IEEE Trans. on Inform. Theory,
60(11):6819–6843, 2014.
[13] M. B. Parizi, E. Telatar, and N. Merhav. Exact random coding secrecy exponents for the wiretap channel. IEEE Trans. on Inform. Theory, 63(1):509–531,
2017.
[14] Y. Oohama. Exponent function for source coding with side information at the decoder at rates below the rate distortion function. arXiv preprint
arXiv:1601.05650, 2016.
[15] I. Sason. On the Rényi divergence, joint range of relative entropies, and a channel coding theorem. IEEE Trans. on Inform. Theory, 62(1):23–34, 2016.
[16] A. R. Barron. Entropy and the central limit theorem. The Annals of Probability, pages 336–342, 1986.
[17] S. G. Bobkov, G. P. Chistyakov, and F. Götze. Rényi divergence and the central limit theorem. arXiv preprint arXiv:1608.01805, 2016.
[18] J. Hou and G. Kramer. Effective secrecy: Reliability, confusion and stealth. In IEEE International Symposium on Information Theory (ISIT), pages
601–605. IEEE, 2014.
[19] S. Beigi and A. Gohari. Quantum achievability proof via collision relative entropy. IEEE Trans. on Inform. Theory, 60(12):7980–7986, 2014.
[20] Y. Dodis and Y. Yu. Overcoming weak expectations. In Theory of Cryptography, pages 1–22. Springer, 2013.
[21] M. Hayashi and V. Y. F. Tan. Equivocations, exponents, and second-order coding rates under various Rényi information measures. IEEE Trans. on
Inform. Theory, 63(2):975–1005, 2017.
[22] V. Y. F. Tan and M. Hayashi. Analysis of remaining uncertainties and exponents under various conditional Rényi entropies. Accepted to IEEE Trans.
on Inform. Theory. Available at arXiv preprint arXiv:1605.09551, 2018.
[23] T. Van Erven and P. Harremoës. Rényi divergence and Kullback-Leibler divergence. IEEE Trans. on Inform. Theory, 60(7):3797–3820, 2014.
[24] L. Yu and V. Y. F. Tan. Wyner’s common information under Rényi divergence measures. arXiv preprint arXiv:1709.02168, 2017.
[25] V. Y. F. Tan, A. Anandkumar, L. Tong, and A. S. Willsky. A large-deviation analysis of the maximum-likelihood learning of Markov tree structures.
IEEE Trans. on Inform. Theory, 57(3):1714–1735, 2011.
[26] W.-H. Gu and M. Effros. A strong converse for a collection of network source coding problems. In IEEE International Symposium on Information
Theory (ISIT), pages 2316–2320. IEEE, 2009.
[27] S. Watanabe. Second-order region for Gray–Wyner network. IEEE Trans. on Inform. Theory, 63(2):1006–1018, 2017.
[28] L. Zhou, V. Y. F. Tan, and M. Motani. Discrete lossy Gray-Wyner revisited: Second-order asymptotics, large and moderate deviations. IEEE Trans. on
Inform. Theory, 63(3):1766–1791, 2017.
[29] W. Rudin. Principles of Mathematical Analysis. McGraw-Hill, 1976.
[30] I. Csiszar and J. Körner. Information Theory: Coding Theorems for Discrete Memoryless Systems. Cambridge University Press, 2011.
[31] A. Dembo and O. Zeitouni. Large Deviations Techniques and Applications. Springer-Verlag, 2nd edition, 1998.

