1

Exponent Function for One Helper Source Coding
Problem at Rates outside the Rate Region

arXiv:1504.05891v5 [cs.IT] 12 Jan 2018

Yasutada Oohama

Abstract—We consider the one helper source coding problem
posed and investigated by Ahlswede, Körner and Wyner. Two
correlated sources are separately encoded and are sent to a
destination where the decoder wishes to decode one of the two
sources with an arbitrary small error probability of decoding.
In this system, the error probability of decoding goes to one as
the source block length n goes to infinity. This implies that we
have a strong converse theorem for the one helper source coding
problem. In this paper we provide the much stronger version of
this strong converse theorem for the one helper source coding
problem. We prove that the error probability of decoding tends
to one exponentially and derive an explicit lower bound of this
exponent function.
Index Terms—One helper source coding problem, strong converse theorem, exponent of correct probability of decoding

I. I NTRODUCTION
We consider the one helper source coding problem posed
and investigated by Ahlswede, Körner and Wyner. Two correlated sources are separately encoded and are sent to a
destination where the decoder wishes to decode one of the two
sources with an arbitrary small error probability of decoding.
In this system, the error probability of decoding goes to one
as the source block length n goes to infinity. This implies that
we have a strong converse theorem for the one helper source
coding problem. In this paper we provide the much stronger
version of this strong converse theorem for the one helper
source coding problem. We prove that the error probability
of decoding tends to one exponentially and derive an explicit
lower bound of this exponent function.
II. P ROBLEM F ORMULATION
∞
{(Xt , Yt )}t=1

Let X and Y be finite sets and
be a stationary
discrete memoryless source. For each t = 1, 2, · · · , the random
pair (Xt , Yt ) takes values in X × Y, and has a probability
distribution
pXY = {pXY (x, y)}(x,y)∈X ×Y
∞
We write n independent copies of {Xt }∞
t=1 and {Yt }t=1 ,
respectively as

X n = X1 , X2 , · · · , Xn and Y n = Y1 , Y2 , · · · , Yn .
We consider a communication system depicted in Fig. 1. Data
(n)
sequences X n and Y n are separately encoded to ϕ1 (X n )
(n)
and ϕ2 (Y n ) and those are sent to the information processing
center. At the center the decoder function ψ (n) observes
Y. Oohama is with University of Electro-Communications, 1-5-1 Chofugaoka Chofu-shi, Tokyo 182-8585, Japan.

(n)

X

Y

Fig. 1.
(n)

Xn
ϕ1 (X n )
✲ ϕ(n)
1
rate R1 ❅
❅
(n)
❅
Yn
ϕ2 (Y n )
❅
❘
✲ ϕ(n)
✲ψ (n)
2
rate R2

✲ Ŷ n

One helper source coding system.
(n)

(ϕ1 (X n ), ϕ2 (Y n )) to output the estimation Ŷ n of Y n .
(n)
(n)
The encoder functions ϕ1 and ϕ2 are defined by

(n)
ϕ1 : X n → M1 = { 1, 2, · · · , M1 } , 
(1)
(n)
ϕ2 : Y n → M2 = { 1, 2, · · · , M2 } , 
(n)

where for each i = 1, 2, kϕi k (= Mi ) stands for the range
(n)
of cardinality of ϕi . The decoder function ψ (n) is defined
by
ψ (n) : M1 × M2 → Y n .
(2)
The error probability of decoding is
o
n
(n)
(n)
(n)
P(n)
) = Pr Ŷ n 6= Y n ,
e (ϕ1 , ϕ2 , ψ
(n)

(3)

(n)

where Ŷ n = ψ (n) (ϕ1 (X n ), ϕ2 (Y n )). A rate pair (R1 , R2 )
is ε-achievable if for any δ > 0, there exist a positive
(n)
(n)
integer n0 = n0 (ε, δ) and a sequence of triples {(ϕ1 , ϕ2 ,
(n)
ψ )}n≥n0 such that for n ≥ n0 ,
1
(n)
log kϕi k ≤ Ri + δ for i = 1, 2,
n
(n)
(n)
(n)
) ≤ ε.
P(n)
e (ϕ1 , ϕ2 , ψ
For ε ∈ (0, 1), the rate region RAKW (ε|pXY ) is defined by
RAKW (ε|pXY )
:= { (R1 , R2 ) : (R1 , R2 ) is ε-achievable for pXY } .
Furthermore, define
RAKW (pXY ) :=

\

RAKW (ε|pXY ).

ε∈(0,1)

We can show that the two rate regions RAKW (ε| pXY ), ε ∈
(0, 1) and RAKW (pXY ) satisfy the following property.
Property 1:
a) The regions RAKW (ε|pXY ), ε ∈ (0, 1), and RAKW (
pXY ) are closed convex sets of R2+ , where
R2+ := {(R1 , R2 ) : R1 ≥ 0, R2 ≥ 0}.

2

b) RAKW (ε|pXY ) has another form using (n, ε)-rate region
RAKW (n, ε|pXY ), the definition of which is as follows.
We set
RAKW (n, ε|pXY ) = {(R1 , R2 ) :
(n)

(n)

There exists (ϕ1 , ϕ2 , ψ (n) ) such that
1
(n)
log ||ϕi || ≤ Ri , i = 1, 2,
n
(n)
(n)
(n)
P(n)
) ≤ ε}.
e (ϕ1 , ϕ2 , ψ
Using RAKW (n, ε|pXY ), RAKW (ε|pXY ) can be expressed as


[ \
RAKW (ε|pXY ) = cl 
RAKW (n, ε|pXY ) .
m≥1 n≥m

Proof of this property is given in Appendix A.
It is well known that RAKW (pXY ) was determined by
Ahlswede, Körner and Wyner. To describe their result we
introduce an auxiliary random variable U taking values in a
finite set U. We assume that the joint distribution of (U, X, Y )
is
pUXY (u, x, y) = pU (u)pX|U (x|u)pY |X (y|x).

The above condition is equivalent to U ↔ X ↔ Y . Define
the set of probability distribution p = pUXY by
P(pXY ) := {pUXY : |U| ≤ |X | + 1, U ↔ X ↔ Y }.

Fig. 2.

A typical shape of R(pXY ).

On the converse coding theorem Ahlswede et al. [3] obtained the following.
Theorem 2 (Ahlswede et al. [3]): For each fixed ε ∈ (0, 1),
we have
RAKW (ε|pXY ) = R(pXY ).
Gu and Effors [5] examined a speed of convergence for
(n)
Pe to tend to 1 as n → ∞ by carefully checking the proof
of Ahlswede et al. [3]. However they could not obtain a result
on an explicit form of the exponent function with respect to
the code length n.
Our aim is to find an explicit form of the exponent function
for the error probability of decoding to tend to one as n → ∞
when (R1 , R2 ) ∈
/ RAKW (pXY ). To examine this quantity, we
define the following quantity. Set
(n)

(n)

(n)

(n)

(n)
(n)
P(n)
) := 1 − P(n)
),
c (ϕ1 , ϕ2 , ψ
e (ϕ1 , ϕ2 , ψ

Set

G(n) (R1 , R2 |pXY )

R(p) := {(R1 , R2 ) : R1 , R2 ≥ 0 ,
R1 ≥ Ip (X; U ), R2 ≥ Hp (Y |U )},
[
R(p).
R(pXY ) :=

:=

(R1 + R2 ) = Hp (Y ).

(4)

The minimun is attained by (R1 , R2 ) = (0, Hp (Y )). This
result implies that
R(pXY ) ⊆ {(R1 , R2 ) : R1 + R2 ≥ Hp (Y )} ∩ R2+ .
Furthermore, the point (0, Hp (Y )) always belongs to
R(pXY ).
Property 2 part a) is a well known property. Proof of
Property 2 part b) is easy. Proofs of Property 2 parts a) and
b) are omitted. A typical shape of the rate region R(pXY ) is
shown in Fig. 2.
The rate region RAKW (pXY ) was determined by Ahlswede
and Körner [1] and Wyner [2]. Their result is the following.
Theorem 1 (Ahlswede, Körner [1] and Wyner [2]):
RAKW (pXY ) = R(pXY ).

(n)

G(R1 , R2 |pXY ) := lim G(n) (R1 , R2 |pXY ),

We can show that the region R(pXY ) satisfies the following
property.
Property 2:
a) The region R(pXY ) is a closed convex subset of R2+ .
b) For any pXY , we have
min

min

(n)
(1/n) log kϕi k≤Ri ,i=1,2

p∈P(pXY )

(R1 ,R2 )∈R(pXY )

(n)

(ϕ1 ,ϕ2 ,ψ (n) ):



1
(n)
(n)
(n)
log P(n)
).
−
c (ϕ1 , ϕ2 , ψ
n

n→∞

G(pXY ) := {(R1 , R2 , G) : G ≥ G(R1 , R2 |pXY )}.
By time sharing we have that


nR1 + mR1′ nR2 + mR2′
(n+m)
,
pXY
G
n+m
n+m
nG(n) (R1 , R2 |pXY ) + mG(m) (R1′ , R2′ |pXY )
≤
. (5)
n+m
Choosing R = R′ in (5), we obtain the following subadditivity
property on {G(n) (R1 , R2 |pXY ) }n≥1 :
G(n+m) (R1 , R2 |pXY )
nG(n) (R1 , R2 |pXY ) + mG(m) (R1 , R2 |pXY )
,
≤
n+m
from which we have that G(n) (R1 , R2 |pXY ) exists and satisfies the following:
lim G(n) (R1 , R2 |pXY ) = inf G(n) (R1 , R2 |pXY ).

n→∞

n≥1

The exponent function G(R1 , R2 |pXY ) is a convex function
of (R1 , R2 ). In fact, from (5), we have that for any α ∈ [0, 1]
G(αR1 + ᾱR1′ , αR2 + ᾱR2′ |pXY )
≤ αG(R1 , R2 |pXY ) + ᾱG(R1′ , R2′ |pXY ).

3

The region G(pXY ) is also a closed convex set. Our main aim
is to find an explicit characterization of G(pXY ). In this paper
we derive an explicit outer bound of G (pXY ) whose section
by the plane G = 0 coincides with RAKW (pXY ).
III. M AIN R ESULT
In this section we state our main result. We first explain
that the region R(pXY ) can be expressed with a family of
supporting hyperplanes. To describe this result we define a set
of probability distributions on U ×X ×Y by

min

p∈Psh (pXY )

{µIp (X; U ) + Hp (Y |U )} .

Ω̃(µ,λ) (p),

min
p∈Psh (pXY )

λ≥0,µ∈[0,1]

Furthermore, define
Rsh (pXY ) :=

\

{(R1 , R2 ) : µR1 + R2
µ≥0
≥ R(µ) (pXY )},
\
{(R1 , R2 ) : µR1 + R2
Rsh (pXY ) :=
µ∈[0,1]
≥ R(µ) (pXY )}.

Then we have the following property.
Property 3:
a) The bound |U| ≤ |X | is sufficient to describe R(µ) (
pXY ).
b) For every µ ≥ 0, we have
min

(R1 ,R2 )∈R(pXY )

{µR1 + R2 } = R(µ) (pXY ).

(6)

c) For every µ ≥ 1, we have R(µ) (pXY ) = Hp (Y ).
d) For any pXY we have
Rsh (pXY ) = Rsh (pXY ) = R(pXY ).

(7)

Property 3 part a) is stated as Lemma 9 in Appendix B.
Proof of this lemma is given in this appendix. Proofs of
Property 3 parts b), c) and d) are given in Appendix C. Set
Q(pY |X ) := {q = qUXY : |U| ≤ |X |, U ↔ X ↔ Y,
pY |X = qY |X }.
For µ ∈ [0, 1], β, α ≥ 0, and for q = qUXY ∈ Q(pY |X ),
define
(µ,β)

ωq|pX (x, y|u)


qX|U (x|u)
qX (x)
1
,
+ β µ log
+ log
pX (x)
pX (x)
qY |U (y|u)
o
n
(µ,β)
(µ,β,α)
fq|pX (x, y|u) := exp −αβωq|pX (x, y|u) ,
oi
h
n
(µ,β)
Ω(µ,β,α) (q|pX ) := − log Eq exp −αωq|pX (X, Y |U ) ,
:= log

Ω(µ,β,α) (pXY ) :=

min

Ω(µ,β,α) (q|pX ),

q∈Q(pY |X )

Ω

Ω̃(µ,λ) (pXY ) :=

:=

R(µ) (pXY ) :=

(µR1 + R2 |pXY )

(µ,β,α)

(pXY ) − αβ(µR1 + R2 )
,
1 + α{1 + β(2 + µ)}
F (R1 , R2 |pXY ) := sup F (µ,β,α) (µR1 + R2 |pXY ).
:=

Furthermore, set

Ω̃(µ,λ) (pXY ) − λ(µR1 + R2 )
,
2 + λ(5 + µ)
F̃ (µ,λ) (µR1 + R2 |pXY ).
F̃ (R1 , R2 |pXY ) :=
sup

For µ ≥ 0, define

F

pX|U (x|u)
1
+ log
,
pX (x)
pY |U (Y |U )
h
n
oi
Ω̃(µ,λ) (p) := − log Ep exp −λω̃p(µ) (X, Y |U ) .
ω̃p(µ) (x, y|u) := µ log

F̃ (µ,λ) (µR1 + R2 |pXY )

Psh (pXY ) := {p = pUXY : |U| ≤ |X |, U ↔ X ↔ Y }.

(µ,β,α)

We next define a function serving as a lower bound of
F (R1 , R2 |pXY ). For each pUXY ∈ Psh (pXY ), define

µ∈[0,1],
β,α≥0

We can show that the above functions satisfies the following
property.
Property 4:
a) The cardinality bound |U| ≤ |X | in Q(pY |X ) is sufficient
to describe the quantity Ω(µ,β,α) (pXY ). Furthermore, the
cardinality bound |U| ≤ |X | in Psh (pXY ) is sufficient to
describe the quantity Ω̃(µ,λ) (pXY ).
b) For any R1 , R2 ≥ 0, we have
F (R1 , R2 |pXY ) ≥ F̃ (R1 , R2 |pXY ).
c) Fix any p = pUXY ∈ Psh (pXY ) and µ ∈ [0, 1]. For
λ ∈ [0, 1], Ω̃(µ,λ) (p) exists and is nonnegative. We define
(λ)
a probability distribution p(λ) = pUXY by
n
o
(µ)
p(u, x, y) exp −λω̃p (x, y|u)
oi .
h
n
p(λ) (u, x, y) :=
(µ)
Ep exp −λω̃p (X, Y |U )

Then for λ ∈ [0, 1/2], Ω̃(µ,λ) (p) is twice differentiable.
Furthermore, for λ ∈ [0, 1/2], we have
h
i
d (µ,λ)
Ω̃
(p) = Ep(λ) ω̃p(µ) (X, Y |U ) ,
dλ
h
i
d2 (µ,λ)
Ω̃
(p) = −Varp(λ) ω̃p(µ) (X, Y |U ) .
2
dλ

The second equality implies that Ω̃(µ,λ) (p |pXY ) is a
concave function of λ ∈ [0, 1/2].
d) For every (µ, λ) ∈ [0, 1] × [0, 1/2], define
ρ(µ,λ) (pXY )
:=

max

(ν,p)∈[0,λ]
×Psh (pXY ):
Ω̃(µ,λ) (p)
=Ω̃(µ,λ) (pXY )

h
i
Varp(ν) ω̃p(µ) (X, Y |U ) ,

and set
ρ = ρ(pXY ) :=

max

(µ,λ)∈[0,1]×[0,1/2]

ρ(µ,λ) (pXY ).

Then, we have ρ(pXY ) < ∞. Furthermore, for any
(µ, λ) ∈ [0, 1] × [0, 1/2], we have
Ω̃(µ,λ) (pXY ) ≥ λR(µ) (pXY ) −

λ2
ρ(pXY ).
2

(8)

4

e) For every τ ∈ (0, (1/2)ρ(pXY )), the condition (R1 , R2 +
τ) ∈
/ R(pXY ) implies


ρ(pXY ) 2
τ
F̃ (R1 , R2 |pXY ) >
> 0,
·g
4
ρ(pXY )
where g is the inverse function of ϑ(a) := a +
(3/2)a2 , a ≥ 0.
Property 3 part a) is stated as Lemma 10 in Appendix
B. Proof of this lemma is given in this appendix. Proof of
Property 4 part b) is given in Appendix D. Proofs of Property
4 parts c), d), and e) are given in Appendix E.
Our main result is the following.
Theorem 3: For any R1 , R2 ≥ 0, any pXY , and for any
(n)
(n)
(n)
(ϕ1 , ϕ1 , ψ (n) ) satisfying (1/n) log ||ϕi || ≤ Ri , i = 1, 2,
we have
(n)

From Theorem 3 and Property 4 part e), we have the following
corollary.
Corollary 2: For each fixed ε ∈ (0, 1), we choose the above
positive integer n0 =n0 (ε, ρ(pXY )). Then, for any n ≥ n0 ,
we have
RAKW (n, ε|pXY ) ⊆ R(pXY ) − κn (0, 1).
The above result together with


RAKW (ε|pXY ) = cl 

[ \

m≥1 n≥m



RAKW (n, ε|pXY )

yields that for each fixed ε ∈ (0, 1), we have

(n)

(n)
P(n)
) ≤ 5 exp {−nF (R1 , R2 |pXY )} . (9)
c (ϕ1 , ϕ2 , ψ

It follows from Theorem 3 and Property 4 part d) that
if (R1 , R2 ) is outside the capacity region, then the error
probability of decoding goes to one exponentially and its
exponent is not below F (R1 , R2 |pXY ). It immediately follows
from Theorem 3 that we have the following corollary.
Corollary 1:
G(R1 , R2 |pXY ) ≥ F (R1 , R2 |pXY ),
G(pXY ) ⊆ G(pXY )
= {(R1 , R2 , G) : G ≥ F (R1 , R2 |pXY )} .
Proof of Theorem 3 will be given in the next section.
The exponent function at rates outside the rate region was
derived by Oohama and Han [7] for the separate source coding
problem for correlated sources [6]. The techniques used by
them is a method of types [8], which is not useful to prove
Theorem 3. Some novel techniques based on the information
spectrum method introduced by Han [9] are necessary to prove
this theorem.
From Theorem 3 and Property 4 part e), we can obtain an
explicit outer bound of RAKW (ε|pXY ) with an asymptotically
vanishing deviation from RAKW (pXY ) = R(pXY ). The
strong converse theorem established by Ahlswede et al. [3]
immediately follows from this corollary. To discribe this outer
bound, for κ > 0, we set
R(pXY ) − κ(0, 1)
:= {(R1 , R2 − κ) : (R1 , R2 ) ∈ R(pXY )},
which serves as an outer bound of R(pXY ). For each fixed
ε ∈ (0, 1), we define κn = κn (ε, ρ(pXY )) by
s
!

4
5
κn := ρ(pXY )ϑ
(10)
log
nρ(pXY )
1−ε
s




6
ρ(pXY )
5
5
(a)
+ log
.
log
= 2
n
1−ε
n
1−ε
Step (a) follows from ϑ(a) = a + (3/2)a2 . Since κn → 0
as n → ∞, we have the smallest positive integer n0 =
n0 (ε, ρ(pXY )) such that κn ≤ (1/2)ρ(pXY ) for n ≥ n0 .

RAKW (ε|pXY ) = RAKW (pXY ) = R(pXY ).
This recovers the strong converse theorem proved by
Ahlswede et al. [3].
Proof of this corollary will be given in the next section.

IV. P ROOF

OF THE

M AIN R ESULT

Let (X n , Y n ) be a pair of random variables from the
(n)
information source. We set S = ϕ1 (X n ). Joint distribution
pSX n Y n of (S, X n , Y n ) is given by
p

SX n Y n

n

n

n

(s, x , y ) = pS|X n (s|x )

n
Y

pXt Yt (xt , yt ).

t=1

It is obvious that S ↔ X n ↔ Y n . Then we have the
following.
(n)
(n)
Lemma 1: For any η > 0 and for any (ϕ1 , ϕ2 , ψ (n) )
(n)
satisfying (1/n) log ||ϕi || ≤ Ri , i = 1, 2, we have
(n)

(n)

(n)
P(n)
) ≤ pSX n Y n
c (ϕ1 , ϕ2 , ψ



q̂SX n Y n (S, X n , Y n )
1
− η,
log
n
pSX n Y n (S, X n , Y n )
1
qX n (X n )
0 ≥ log
− η,
n
pX n (X n )
pX n |S (X n |S)
1
− η,
R1 ≥ log
n
pX n (X n )

1
1
R2 ≥ log
−
η
+ 4e−nη .
n
pY n |S (Y n |S)
0≥

(11)
(12)

(13)

The probability distributions appearing appearing in the two
inequalities (11) and (12) in the right members of (13) have
a property that we can select them arbitrary. In (11), we can
choose any probability distribution q̂SX n Y n on S×X n ×Y n .
In (12), we can choose any distribution qX n on X n .
Proof of this lemma is given in Appendix F. From Lemma
1 we obtain the following lemma.

5

(n)

(n)

Lemma 2: For any η > 0 and for any (ϕ1 , ϕ2 , ψ (n) )
(n)
satisfying (1/n) log ||ϕi || ≤ Ri , i = 1, 2, we have
(n)

(n)

Pc(n) (ϕ1 , ϕ2 , ψ (n) )
(
n
1X
qX (Xt )
≤ pSX n Y n 0 ≥
− η,
log t
n t=1
pXt (Xt )

or equivalently that I(Yt ; SX t−1 |Xt ) = 0. Furthermore, we
have the following Markov chain:

n

R1 ≥

pX |SX t−1 (Xt |S, X t−1 )
1X
− η,
log t
n t=1
pXt (Xt )

Y t−1 ↔ SX t−1 ↔ (Xt , Yt )

n

R2 ≥

1X
1
− 2η
log
n t=1
pYt |SX t−1 Y t−1 (Yt |S, X t−1 , Y t−1 )

)

+4e−nη .

Proof: In (11) in Lemma 1, we choose q̂
form

SX n Y n

Lemma 3: Suppose that for each t = 1, 2, · · · , n, the joint
distribution pSX t Y t of the random vector SX t Y t is a marginal
distribution of pSX n Y n . Then we have the following Markov
chain:
SX t−1 ↔ Xt ↔ Yt
(14)

or equivalently that I(Xt Yt ; Y t−1 |SX t−1 ) = 0. The above
two Markov chains are equivalent to the following one long
Markov chain:
Y t−1 ↔ SX t−1 ↔ Xt ↔ Yt .

having the

q̂SX n Y n (S, X n , Y n )
n
Y

pXt |SX t−1 Y t (Xt |S, X t−1 , Y t )
= pS (S)
t=1

× pYt |SY t−1 (Yt |S, Y t−1 ) .
n
Y

(n)

qXt (Xt ).

n

pX |U (Xt |Ut )
1X
− η,
log t t
n t=1
pXt (Xt )
)
n
1X
1
R2 ≥
− 2η + 4e−nη .
log
n t=1
pYt |Ut (Yt |Ut )

R1 ≥

n
pX n |S (X n |S) Y pXt |SX t−1 (Xt |S, X t−1 )
,
=
pX n (X n )
pXt (Xt )
t=1

pY n |S (Y n |S) =

n
Y

pYt |SY t−1 (Yt |S, Y t−1 ).

The following is well known as the Cramèr’s bound in the
large deviation principle.
Lemma 5: For any real valued random variable Z and any
α ≥ 0, we have

t=1

Then the bound (13) in Lemma 1 becomes

(n)
(n)
(n)
n
n
P(n)
(ϕ
,
ϕ
,
ψ
)
≤
p
SX Y
c
1
2
0≥

1
n

n
X
t=1

log

Pr{Z ≥ a} ≤ exp [− (αa − log E[exp(αZ)])] .
Let p
form:

pYt |SY t−1 (Yt |S, Y t−1 )
− η,
pYt |SX t−1 Y t−1 (Yt |S, X t−1 , Y t−1 )

n
1X
qX (Xt )
0≥
− η,
log t
n t=1
pXt (Xt )

n
pX |SX t−1 (Xt |S, X t−1 )
1X
− η,
log t
n t=1
pXt (Xt )
n

1
1X
− 2η
log
R2 ≥
n t=1
pYt |SX t−1 Y t−1 (Yt |S, X t−1 , Y t−1 )
+4e−nη ,

completing the proof.

(n)

= pSX n Y n be a probability distribution havig the

pSX n Y n (s, xn , y n ) = pS|X n (s|xn )

n
Y

pXY (xt , yt )

t=1

for (s, xn , y n ) ∈ M1 × X n × Y n .

n
pX |SX t−1 (Xt |S, X t−1 )
1X
− η,
log t
R1 ≥
n t=1
pXt (Xt )
)
n
1
1X
R2 ≥
− η + 4e−nη
n t=1 pYt |SY t−1 (Yt |S, Y t−1 )
(
n
1X
qX (Xt )
≤ pSX n Y n 0 ≥
− η,
log t
n t=1
pXt (Xt )

R1 ≥

(n)

(n)
P(n)
)
c (ϕ1 , ϕ2 , ψ
(
n
qX (Xt )
1X
− η,
log t
≤ pSX n Y n 0 ≥
n t=1
pXt (Xt )

t=1

We further note that

(16)

Proof of this lemma is given in Appendix G. For t =
1, 2, · · · , n, let Ut be a random variable taking values in Ut =
M1 ×X t−1 . Define Ut by Ut := (S, X t−1 ). From Lemmas
2 and 3, we have the following.
(n)
(n)
Lemma 4: For any η > 0 and for any (ϕ1 , ϕ2 , ψ (n) )
(n)
satisfying (1/n) log ||ϕi || ≤ Ri , i = 1, 2, we have

In (12) in Lemma 1, we choose qX n having the form
qX n (X n ) =

(15)

For µ ∈ [0, 1] and β, α ≥ 0, we define
Ω(µ,β,α) (p(n) , qX n )
#
" n
βα
µβα
α
Y qX
(Xt ) pXt (Xt )pYt |Ut (Yt |Ut )
t
.
:= − log Ep(n)
pα (Xt )
pµβα (Xt |Ut )
t=1 Xt
Xt |Ut

By Lemmas 4 and 5, we have the following proposition.
Proposition 1: For any µ ∈ [0, 1], any α, β ≥ 0, and any
(n)
(n)
(n)
(ϕ1 , ϕ2 , ψ (n) ) satisfying (1/n) log ||ϕi || ≤ Ri , i = 1, 2,
we have
)

(n)

(n)

P(n)
, ϕ2 , ψ (n) )
c (ϕ
1
≤ 5 exp −n [1 + α{1 + β(2 + µ)}]−1


1 (µ,β,α) (n)
×
Ω
(p , qX n ) − αβ(µR1 + R2 ) .
n

6

Proof: When Ω(µ,β,α) (p(n) , qX n ) ≤ nαβ(µR1 + R2 ), the
bound we wish to prove is obvious. In the following argument
we assume that Ω(µ,β,α) (p(n) , qX n ) > nαβ(µR1 + R2 ). By
Lemma 4, for µ ∈ [0, 1] and α, β ≥ 0, we have the following
chain of inequalities:
(n)

n
pα
1X
X |U (Xt |Ut )
− βµη,
log t α t
n t=1
pXt (Xt )
)
n
1X
1
βR2 ≥
− 2βη + 4e−nη
log β
n t=1
pYt |Ut (Yt |Ut )

≤ pSX n Y n β(µR1 + R2 ) + {1 + β(2 + µ)}η
#)
"
µβ
β
n
1X
pXt (Xt ) pXt (Xt )pYt |Ut (Yt |Ut )
log
≥−
n t=1
qXt (Xt )
pµβ
Xt |Ut (Xt |Ut )


n
1X
pXt (Xt )
log
n t=1
qXt (Xt )
×

β
pµβ
Xt (Xt )pYt |Ut (Yt |Ut )

pµβ
Xt |Ut (Xt |Ut )

:=

=

X

pSX n Y n (s, xn , y n )

t=1

by

(µ,β,α)

pSX t Y t (s, xt , y t ) := Ct−1 pSX t Y t (s, xt , y t )
t
Y
(µ,β,α)
fqX ||pX ,pX Y |U (xi , yi |ui )
×

where

i

(n)

completing the proof.
Set

Ct :=

X

:= inf

n≥1

min

max

qQ
X n :qX n =
p(n) :
n
t=1 qXt
S↔X n ↔Y n

1 (µ,β,α) (n)
Ω
(p , qX n ).
n

By Proposition 1 we have the folloing corollary.

i i

pSX t Y t (s, xt , y t )

i

t
Y

i=1

s,xt ,y t

(α,µ,β)
||pXi ,pXi Yi |Ui (xi , yi )
i

fqX

are constants for normalization. For t = 1, 2, · · · , n, define
(µ,β,α)

Φt

−1
:= Ct Ct−1
,

(19)

where we define C0 = 1. Then we have the following lemma.
Lemma 6: For each t = 1, 2, · · · , n, and for any (s, xt , y t ) ∈
M1 ×X t ×Y t , we have
(µ,β,α) −1 (µ,β,α)
) pSX t−1 Y t−1 (s, xt−1 , y t−1 )
×pXt Yt |SX t−1 Y t−1 (xt , yt |s, xt−1 , y t−1 )
(µ,β,α)
×fqX ||pX ,pX Y |U (xt , yt |ut ).

(µ,β,α)

pSX t Y t (s, xt , y t ) = (Φt

t

Ω(µ,β,α) (pXY )

i

(18)

For this choice of η and (17), we have
(n)

(µ,β,α)
(xt , yt |ut ).
t ||pXt ,pXt Yt |Ut

fqX

(s,xt ,y t )∈M1 ×X t ×Y t

i=1

(n)
P(n)
) ≤ 5e−nη
c (ϕ1 , ϕ2 , ψ

= 5 exp −n [1 + α{1 + β(2 + µ)}]−1


1 (µ,β,α) (n)
×
Ω
(p , qX n ) − αβ(µR1 + R2 ) ,
n

n
Y

.

For each t = 1, 2, · · · , n, we define the probability distribution
n
o
(µ,β,α)
(µ,β,α)
pSX t Y t := pSX t Y t (s, xt , y t )

Step (a) follows from Lemma 5. We choose η so that

η=

pµβα
Xt |Ut (xt |ut )

s,xn ,y n

≥ − [β(µR1 + R2 ) + {1 + β(2 + µ)}η] + 4e−nη
 
(a)
≤ exp n αβ(µR1 + R2 ) + α{1 + β(2 + µ)}η

1 (µ,β,α) (n)
n
+ 4e−nη .
(17)
(p , qX )
− Ω
n

− αβ(µR1 + R2 )
.
1 + α{1 + β(2 + µ)}

t

α (x )
qX
t
t

By definition we have
o
n
exp −Ω(µ,β,α) (p(n) , qX n )



1 (µ,β,α) (n)
(p , qX n )
nΩ

(µ,β,α)
(xt , yt |ut )
t ||pXt ,pXt Yt |Ut
µβα
(xt )pβα
p
pα
Yt |Ut (yt |ut )
X (xt ) Xt

fqX

#

−η = αβ(µR1 + R2 ) + α{1 + β(2 + µ)}η
1
− Ω(µ,β,α) (p(n) , qX n ).
n
Solving (18) with respect to η, we have

(n)

We shall call Ω(µ,β,α) (pXY ) the communication potential.
The above corollary implies that the analysis of Ω(µ,α,β) (
pXY ) leads to an establishment of a strong converse theorem
for the one helper source coding problem. In the following
argument we drive an explicit lower bound of Ω(µ,β,α) (pXY ).
For each t = 1, 2, · · · , n, set ut = (s, xt−1 ) ∈ Ut . For each
t = 1, 2, · · · , n, define

βµR1 ≥

= pSX n Y n

(n)

(n)
P(n)
)
c (ϕ1 , ϕ2 , ψ
#)
(
"
(µ,β,α)
(pXY ) − αβ(µR1 + R2 )
Ω
.
≤ 5 exp −n
1 + α{1 + β(2 + µ)}

(n)

Pc(n) (ϕ1 , ϕ2 , ψ (n) )
(
" n
#
1X
qXt (Xt )
≤ pSX n Y n 0 ≥
−η ,
log
n t=1
pXt (Xt )

+4e−nη (

Corollary 3: For any µ ∈ [0, 1], any β, α ≥ 0, and any
(n)
(n)
(n)
(ϕ1 , ϕ2 , ψ (n) ) satisfying (1/n) log ||ϕi || ≤ Ri , i = 1, 2,
we have

t

t t

t

Furthermore, we have
X (µ,β,α)
(µ,β,α)
pSX t−1 Y t−1 (s, xt−1 , y t−1 )
Φt
=
s,xt ,y t

×pXt Yt |SX t−1 Y t−1 (xt , yt |s, xt−1 , y t−1 )
(µ,β,α)
(xt , yt |ut ).
t ||pXt ,pXt Yt |Ut

×fqX

(20)

7

Proof of this lemma is given in Appendix H. Define

:=

Proof: Set

(µ,β,α)
(µ,β,α)
(ut ) = pSX t−1 (s, xt−1 )
pUt
X (µ,β,α)
pSX t−1 Y t−1 (s, xt−1 , y t−1 ).
y t−1

Qn (pY |X ) := {q = qUXY : |U| ≤ |M1 ||X n−1 ||Y n−1 |,
qY |X = pY |X , U ↔ X ↔ Y },

From Lemmas 3 and 6, we have the following lemma.
Lemma 7:
X (µ,β,α)
(µ,β,α)
(ut )pXt |Ut (xt |ut )pYt |Xt (yt |xt )
pUt
Φt
=
ut ,xt ,yt

(µ,β,α)
(xt , yt |ut ).
t ||pXt ,pXt Yt |Ut

×fqX

Ω̂(µ,β,α)
(pXY
n

) :=

min

Ω(µ,β,α) (q|pXY ).

q∈Qn (pY |X )

Let Ut be random variables taking values in M1 × X t−1 . We
(µ,β,α)
(ut ) and choose qXt Yt |Ut
choose qUt so that qUt (ut ) = pUt
so that

(21)

Proof: We first observe that for (s, xt , y t ) ∈ S × X t × Y t
and for t = 1, 2, · · · , n,

qXt Yt |Ut (xt , yt |ut ) = pXt Yt |Ut (xt , yt |ut ).

(25)

Then we have

pXt Yt |SX t−1 Y t−1 (xt , yt |s, xt−1 , y t−1 )

(a)

= pXt |SX t−1 Y t−1 (xt |s, xt−1 , y t−1 )

qYt |Xt Ut (yt |xt , ut ) = pYt |Xt (yt |xt ) = qYt |Xt (yt |xt ). (26)

×pYt |SX t Y t−1 (yt |s, xt , y t−1 )
Step (a) follows from Lemma 3. The equation (26) imply that

(a)

= pXt |SX t−1 (xt |s, xt−1 )pYt |Xt (yt |xt )

Step (a) follows from Lemma 3. Then by Lemma 6, we have
X (µ,β,α)
(µ,β,α)
pSX t−1 Y t−1 (s, xt−1 , y t−1 )
=
Φt

qt = qUt Xt Yt ∈ Qn (pY |X ).
Hence we have the following chain of inequalities:

s,xt ,y t

×pXt Yt |SX t−1 Y t−1 (xt , yt |s, xt−1 , y t−1 )

(µ,β,α) (a)

Φt

(µ,β,α)
×fqX ||pX ,pX Y |U (xt , yt |ut ),
t
t
t t
t

=

X

(µ,β,α)

(µ,β,α)

s,xt ,y t

(b)

=

×pXt |SX t−1 (xt |s, xt−1 )pYt |Xt (yt |xt )

(µ,β,α)

× fqU X Y |pX (xt , yt |ut )
t
t t t
n
o (c)
n
o
(µ,β,α)
= exp −Ω
(qt |pX ) ≤ exp −Ω̂(µ,β,α)
(p
)
XY
n
n
o
(d)
= exp −Ω(µ,β,α) (pXY ) .
(27)

s,xt ,yt

×pXt |SX t−1 (xt |s, xt−1 )pYt |Xt (yt |xt )
(µ,β,α)
(xt , yt |ut ),
t ||pXt ,pXt Yt |Ut

×fqX

Step (a) follows from Lemma 7. Step (b) follows from (25).
Step (c) follows from qt ∈ Qn (pY |X ) and the definition
(µ,β,α)
of Ω̂n
(pXY ). Step (d) follows from Property 4 part a).
Hence we have the following:

completing the proof.
We have the following.
Lemma 8:
(µ,β,α)

log Φt

.

(22)
max

t=1

Proof: From (19) we have
(µ,β,α)

log Φt

× fqX ||pX ,pX Y |U (xt , yt |ut )
t
t
t t
t
X
qUt (ut )pXt |Ut (xt |ut )pYt |Xt (yt |xt )

ut ,xt ,yt

(µ,β,α)

×fqX ||pX ,pX Y |U (xt , yt |ut )
t
t
t t
t
X (µ,β,α)
pSX t−1 (s, xt−1 )
=

n
X

qUt (ut )pXt |Ut (xt |ut )pYt |Xt (yt |xt )

ut ,xt ,yt

pSX t−1 Y t−1 (s, xt−1 , y t−1 )

Ω(µ,β,α) (p(n) , qX n ) = (−1)

X

=

= − log Ct + log Ct−1 .

(23)

Furthermore, by definition we have
Ω(µ,β,α) (p(n) , qX n ) = − log Cn , C0 = 1.

(24)

From (23) and (24), (22) is obvious.
The following proposition is a mathematical core to prove
our main result.
Proposition 2: For any µ ∈ [0, 1] and any β, α ≥ 0, we
have
Ω(µ,β,α) (pXY ) ≥ Ω(µ,β,α) (pXY ).

1

qQ
X n :qX n = n
n
t=1 qXt
n
1X
(a)

= −

n

Ω(µ,β,α) (p(n) , qX n ) ≥
(µ,β,α)

log Φt

1 (µ,β,α) (n)
Ω
(p , qX n )
n

(b)

≥ Ω(µ,β,α) (pXY ).

(28)

t=1

Step (a) follows from Lemma 8. Step (b) follows from (27).
Since (28) holds fo any n ≥ 1 and any pSX n Y n satisfying
S ↔ X n ↔ Y n , we have that for any µ ∈ [0, 1] and any
β, α ≥ 0,
Ω(µ,β,α) (pXY ) ≥ Ω(µ,β,α) (pXY ).
Thus, Proposition 2 is proved.

8

Proof of Theorem 3: For any µ ∈ [0, 1], β, α ≥ 0, for
(n)
(n)
any R1 , R2 ≥ 0 and for any (ϕ1 , ϕ2 , ψ (n) ) satisfying
(n)
(1/n) log ||ϕi || ≤ Ri , i = 1, 2, we have the following:
)
(
1
5
log
(n)
(n)
(n)
n
Pc (ϕ , ϕ , ψ (n) )
1

(n)

Z

X

(a)

≥

Y

Fig. 3.

Step (a) follows from Corollary 3. Step (b) follows from
Proposition 2. Since the above bound holds for any µ ∈ [0, 1]
and any β, α ≥ 0, we have
(
)
1
5
log
≥ F (R1 , R2 |pXY ).
(n)
(n)
(n)
n
Pc (ϕ , ϕ , ψ (n) )
1

✲ φ(n)
✒

✲ Ẑ n

(n)

2

Ω(µ,β,α) (pXY ) − αβ(µR1 + R2 )
1 + α{1 + β(2 + µ)}
(b) Ω(µ,β,α) (p
XY ) − αβ(µR1 + R2 )
≥
1 + α{1 + β(2 + µ)}
= F (µ,β,α) (µR1 + R2 |pXY ).

Zn
ϕ3 (Z n )
✲ ϕ(n)
3
rate R3

Xn
ϕ1 (X n )
✲ ϕ(n)
1
rate R1 ❅
❅
(n)
❅
Yn
ϕ2 (Y n )
❅
❘
✲ ϕ(n)
✲ψ (n)
2
rate R2

✲ Ŷ n

One helper source coding system investigated by Wyner.

for n ≥ n0 , which implies that for n ≥ n0 ,
RAKW (n, ε|pXY ) ⊆ R(pXY ) − κn (0, 1),
completing the proof.

2

Thus (9) in Theorem 3 is proved.
Proof of Corollary 2: Since g is an inverse function of ϑ,
the definition (10) of κn is equivalent to
 s



5
4
κn
=
.
(29)
log
g
ρ(pXY )
nρ(pXY )
1−ε
By the definition of n0 = n0 (ε, ρ(pXY )), we have that
κn ≤ (1/2)ρ(pXY ) for n ≥ n0 . We assume that for n ≥ n0 ,
(R1 , R2 ) ∈ RAKW (n, ε|pXY ). Then there exists a sequence
(n)
(n)
{(ϕ1 , ϕ2 , ψ (n) ) }n≥n0 such that for n ≥ n0 , we have
1
(n)
log ||ϕi || ≤ Ri , i = 1, 2,
n
(n)
(n)
(n)
P(n)
) ≤ ε.
e (ϕ1 , ϕ2 , ψ

(n)

(n)

(n)

(30)

for any n ≥ n0 (ε, ρ(pXY )). We claim that for n ≥ n0 ,
we have (R1 , R2 + κn ) ∈ R(pXY ). To prove this claim we
suppose that (R1 , R2 + κn∗ ) does not belong to R(pXY )
for some n∗ ≥ n0 . Then we have the following chain of
inequalities:
5 exp [−n∗ F (R1 , R2 |pXY )]



(a)
κn∗
n∗ ρ(pXY ) 2
·g
< 5 exp −
4
ρ(pXY )



n∗ ρ(pXY )
4
5
(b)
= 5 exp −
log
4
n∗ ρ(pXY )
1−ε

 
1−ε
= 1 − ε.
(31)
= 5 exp log
5
Step (a) follows from κn∗ ≤ (1/2)ρ(pXY ) and Property 4 part
d). Step (b) follows from (29). The bound (31) contradicts (30).
Hence we have (R1 , R2 +κn ) ∈R(pXY ) or equivalent to
(R1 , R2 ) ∈ R(pXY ) − κn (0, 1)

W YNER

We consider a communication system depicted in Fig. 2.
Data sequences X n , Y n , and Z n , respectively are separately
(n)
(n)
(n)
encoded to ϕ1 (X n ), ϕ2 (Y n ), and ϕ3 (Z n ). The encoded
(n)
(n)
n
n
data ϕ1 (X ) and ϕ2 (Y ) and are sent to the informa(n)
tion processing center 1. The encoded data ϕ1 (X n ) and
(n)
ϕ3 (Z n ) and are sent to the information processing center 2.
(n)
At the center 1 the decoder function ψ (n) observes (ϕ1 (X n ),
(n)
n
n
n
ϕ2 (Y )) to output the estimation Ŷ of Y . At the center
(n)
(n)
2 the decoder function φ(n) observes (ϕ1 (X n ), ϕ3 (Z n ))
to output the estimation Ẑ n of Z n . The error probability of
decoding is
(n)

(n)
1 − ε ≤ P(n)
)
c (ϕ1 , ϕ2 , ψ

≤ 5 exp {−nF (R1 , R2 |pXY )}

BY

(n)

(n)
P(n)
, φ(n) )
e (ϕ1 , ϕ2 , ϕ3 , ψ
o
n
= Pr Ŷ n 6= Y n or Ẑ n 6= Z n ,

Then by Theorem 3, we have
(n)

V. O NE H ELPER P ROBLEM S TUDIED

(n)

where Ŷ n = ψ (n) ( ϕ1 (X n ), ϕ2 (Y n )) and Ẑ n = ψ (n) (
(n)
(n)
ϕ1 (X n ), ϕ3 (Z n )).
A rate triple (R1 , R2 , R3 ) is ε-achievable if for any δ > 0,
there exist a positve interger n0 = n0 (ε, δ) and a sequence
(n)
(n)
of three encoders and two decoders functions {(ϕ1 , ϕ2 ,
(n)
ϕ3 , ψ (n) , φ(n) )}n≥n0 such that for n ≥ n0 (ε, δ),
1
(n)
log ||ϕi || ≤ Ri + δ for i = 1, 2, 3,
n
(n)
(n)
(n)
(n)
P(n)
, φ(n) ) ≤ ε.
e (ϕ1 , ϕ2 , ϕ3 , ψ
The rate region RW (ε|pXY Z ) is defined by
RW (ε|pXY Z ) := {(R1 , R2 , R3 ) :
(R1 , R2 , R3 ) is ε-achievable for pXY Z }.
Furthermore, define
RW (pXY Z ) :=

\

RW (ε|pXY Z ).

ε∈(0,1)

We can show that the two rate regions RW (ε| pXY Z ), ε ∈
(0, 1) and RW (pXY Z ) satisfy the following property.
Property 5:

9

a) The regions RW (ε|pXY Z ), ε ∈ (0, 1), and RW ( pXY Z )
are closed convex sets of R3+ .
b) We set
RW (n, ε|pXY Z ) = {(R1 , R2 , R3 ) :
(n)

(n)

On the strong converse theorem Csiszár and Körner [8]
obtained the following.
Theorem 5 (Csiszár and Körner [8]): For each fixed ε ∈
(0, 1), we have

(n)

RW (ε|pXY Z ) = R(pXY Z ).

There exists (ϕ1 , ϕ2 , ϕ3 , ψ (n) ) such that
1
(n)
log ||ϕi || ≤ Ri , i = 1, 2, 3
n
(n)
(n)
(n)
(n)
P(n)
) ≤ ε},
e (ϕ1 , ϕ2 , ϕ3 , ψ

To examine a rate of convergence for the error probability
of decoding to tend to one as n → ∞ for (R1 , R2 , R3 ) ∈
/
RW (pXY Z ), we define the following quantity. Set

which is called the (n, ε)-rate region. Using RW (n,
ε|pXY Z ), RW (ε|pXY Z ) can be expressed as


[ \
RW (ε|pXY Z ) = cl 
RW (n, ε|pXY Z ) .
m≥1 n≥m

It is well known that RW (pXY Z ) was determined by Wyner.
To describe his result we introduce an auxiliary random
variable U taking values in a finite set U. We assume that
the joint distribution of (U, X, Y, Z) is

(n)

(n)

P(pXY Z ) := {p = pUXY Z : |U| ≤ |X | + 2,
U ↔ X ↔ Y Z}.

R(p) := {(R1 , R2 , R3 ) : R1 , R2 , R3 ≥ 0,
R1 ≥ Ip (X; U ), R2 ≥ Hp (Y |U ),
R3 ≥ Hp (Z|U )},
[
R(p).
R(pXY Z ) :=

G(R1 , R2 , R3 |pXY Z ) := lim G(n) (R1 , R2 , R3 |pXY Z ),
n→∞

:= {(R1 , R2 , R3 , G) : G ≥ G(R1 , R2 , R3 |pXY Z )}.
By time sharing we have that


nR1 +mR′1 nR2 +mR′2 nR2 +mR′2
p
,
,
G(n+m)
XY
Z
n+m
n+m
n+m

nG(n) (R1 , R2 , R3 |pXY Z ) + mG(m) (R1′ , R2′ , R3′ |pXY Z )
.
n+m
(33)

Choosing R = R′ in (33), we obtain the following subadditivity property on {G(n) (R1 , R2 , R3 |pXY Z ) }n≥1 :

p∈P(pXY Z )

We can show that the region R(pXY Z ) satisfies the following
property.
Property 6:
a) The region R(pXY Z ) is a closed convex subset of R3+ .
b) For any pXY Z , and any γ ∈ [0, 1], we have

G(n+m) (R1 , R2 , R3 |pXY Z )
nG(n) (R1 , R2 , R3 |pXY Z ) + mG(m) (R1 , R2 , R3 |pXY Z )
≤
,
n+m
from which we have that G(R1 , R2 , R3 |pXY Z ) exists and
satisfies the following:
G(R1 , R2 , R3 |pXY Z )
= inf G(n) (R1 , R2 , R3 |pXY Z ).

(R1 + γ̄R2 + γR3 )

n≥1

(32)

The minimun is attained by (R1 , R2 , R3 ) = (0, Hp (Y ),
Hp (Z)). This result implies that
"
\
{(R1 , R2 , R3 ) : R1 + γ̄R2 + γR3
R(pXY Z ) ⊆
γ∈[0,1]

#

≥ γ̄Hp (Y ) + γHp (Z)} ∩ R3+ .
Furthermore, the point (0, Hp (Y ), Hp (Z)) always belongs to R(pXY Z ).
The rate region RW (pXY Z ) was determined by Wyner [2].
His result is the following.
Theorem 4 (Wyner [2]):
RW (pXY Z ) = R(pXY Z ).

(n)

ψ (n) ,φ(n) ):
(n)
(1/n) log kϕi k
≤Ri ,i=1,2,3

≤

Set

= γ̄Hp (Y ) + γHp (Z).

(n)

G(pXY Z )

The above condition is equivalent to U ↔ X ↔ Y Z. Define
the set of probability distribution on U ×X ×Y ×Z by

min

(n)

:= 1 − Pe(n) (ϕ1 , ϕ2 , ϕ3 , ψ (n) , φ(n) ),
G(n) (R1 , R2 , R3 |pXY Z )


1
(n) (n) (n) (n) (n)
log P(n)
),
:=
min
−
c (ϕ1 , ϕ2 , ϕ3 , ψ , φ
(n)
(n)
(n)
n
(ϕ1 ,ϕ2 ,ϕ3 ,

pUXY (u, x, y, z) = pU (u)pX|U (x|u)pY Z|X (y, z|x).

(R1 ,R2 ,R3 )∈R(pXY )

(n)

(n)
, φ(n) )
P(n)
c (ϕ1 , ϕ2 , ϕ3 , ψ

The exponent function G(R1 , R2 , R3 |pXY Z ) is a convex function of (R1 , R2 , R3 ). In fact, by time sharing we have that


nR1 +mR′1 nR2 +mR′2 nR2 +mR′2
G(n+m)
p
,
,
XY
Z
n+m
n+m
n+m
≤

nG(n) (R1 , R2 , R3 |pXY Z ) + mG(m) (R1′ , R2′ , R3′ |pXY Z )
,
n+m

from which we have that for any α ∈ [0, 1]
G(αR1 + ᾱR1′ , αR2 + ᾱR2′ , αR3 + ᾱR3′ |pXY Z )
≤ αG(R1 , R2 , R3 |pXY Z ) + ᾱG(R1′ , R2′ , R3′ |pXY Z ).
The region G(pXY Z ) is also a closed convex set. Our main aim
is to find an explicit characterization of G(pXY Z ). In this paper
we derive an explicit outer bound of G (pXY Z ) whose section
by the plane G = 0 coincides with RW (pXY Z ). We first
explain that the region R(pXY Z ) has another expression using

10

the supporting hyperplane. We define two sets of probability
distributions on U ×X ×Y ×Z by
Psh (pXY Z ) := {p = pUXY Z : |U| ≤ |X |,
U ↔ X ↔ Y Z},
Q(pY Z|X ) := {q = qUXY Z : |U| ≤ |X |,
pY Z|X = qY Z|X , U ↔ X ↔ Y Z}.
For µ ≥ 0 and γ ∈ [0, 1], set
R(µ,γ) (pXY Z ) :=

max

p∈Psh (pXY Z )

{µIp (X; U )

We next define a function serving as a lower bound of
F (R1 , R2 , R3 |pXY Z ). For each p = pUXY Z ∈ Psh (pXY Z ),
define
pX|U (x|u)
ω̃p(µ,γ) (x, y, z|u) := µ log
pX (x)


1
1
,
+ γ log
+ γ̄ log
pY |U (y|u)
pZ|U (z|u)
h
n
oi
Ω̃(µ,γ,λ) (p) := − log Ep exp −λωp(µ,γ) (X, Y, Z|U ) .

Furthermore, set

Ω̃(µ,γ,λ) (pXY Z ) :=

+γ̄Hp (Y |U ) + γHp (Z|U )} ,

Ω̃(µ,γ,λ) (pXY Z ) − λ[µR1 + γ̄R2 + γR3 ]
,
2 + λ(5 + µ)
F̃ (R1 , R2 , R3 |pXY Z )

Rsh (pXY Z )
\
{(R1 , R2 , R3 ) : µR1 + γ̄R2 + γR3
=
(µ,γ)
(pXY Z )},
µ≥0,γ∈[0,1] ≥ R

:=

:=

Rsh (pXY Z )
\
{(R1 , R2 , R3 ) : µR1 + γ̄R2 + γR3
=
(µ,γ)
(pXY Z )}.
(µ,γ)∈[0,1]2 ≥ R

min

(R1 ,R2 ,R3 )∈R(pXY Z )

sup
2

{µR1 + γ̄R2 + γR3 }

We can show that the above functions and sets satisfy the
following property.
Property 8:
a) The cardinality bound |U| ≤ |X | in Q(pY |X ) is sufficient
to describe the quantity Ω(µ,β,α) (pXY ). Furthermore, the
cardinality bound |U| ≤ |X | in Q(pY Z|X ) is sufficient to
describe the quantity Ω̃(µ,γ,λ) (pXY Z ).
b) For any R1 , R2 , R3 ≥ 0, we have
F (R1 , R2 , R3 |pXY Z ) ≥ F̃ (R1 , R2 , R3 |pXY Z ).

= R(µ,γ) (pXY Z ).

c) Fix any p = pUXY Z ∈ Psh (pXY Z ) and (µ, γ) ∈ [0, 1]2 .
For λ ∈ [0, 1], Ω̃(µ,γ,λ) (p) exists and is nonnegative. We
(λ)
define a probability distribution p(λ) = pUXY Z by

c) For every µ ≥ 1 and γ ∈ [0, 1], we have
R(µ,γ) (pXY Z ) = γ̄Hp (Y ) + γHp (Z).

p(λ) (u, x, y, z)

d) For any pXY Z we have
Rsh (pXY Z ) = Rsh (pXY Z ) = R(pXY Z ).

min

Ω(µ,γ,β,α) (q|pX ),

q∈Q(pY Z|X )

F (µ,γ,β,α)(µR1 + γ̄R2 + γR3 )
Ω(µ,γ,β,α) (pXY Z ) − αβ[µR1 + γ̄R2 + γR3 ]
,
1 + α{1 + β(2 + µ)}
F (R1 , R2 , R3 |pXY Z )
:=

(µ,γ)∈[0,1]2 ,
β,α≥0

F (µ,γ,β,α) (µR1 + γ̄R2 + γR3 |pXY Z ).

n
o
(µ,γ)
p(u, x, y, z) exp −λωp (x, y, z|u)
h
n
oi .
:=
(µ,γ)
Ep exp −λωp (X, Y, Z|U )

(34)

For (µ, γ) ∈ [0, 1]2 , β, α ≥ 0, and for q = qUXY Z ∈
Q(pY Z|X ), define

qX|U (x|u)
qX (x)
(µ,γ,β)
ωq|pX (x, y, z|u) := log
+ β µ log
pX (x)
pX (x)

1
1
,
+ γ log
+γ̄ log
qY |U (y|u)
qZ|U (z|u)
o
n
(µ,γ,β)
(µ,γ,β,α)
(x, y, z|u) := exp −αωq|pX (x, y, z|u) ,
fq|pX
i
h
(µ,γ,β,α)
(X, Y, Z|U ) ,
Ω(µ,γ,β,α)(q|pX ) := − log Eq fq|pX
Ω(µ,γ,β,α)(pXY Z ) :=

F̃ (µ,γ,λ) (µR1 + γ̄R2 + γR3 |pXY Z ).

(µ,γ)∈[0,1] ,
λ≥0

Then we have the following property.
Property 7:
a) The bound |U| ≤ |X | is sufficient to describe R(µ) (
pXY Z ).
b) For every µ ≥ 0 and γ ∈ [0, 1], we have

sup

Ω̃(µ,γ,λ) (p),

F̃ (µ,γ,λ) (µR1 + (γ̄R2 + γR3 )|pXY Z )

Furthermore, define

:=

min
p∈Psh (pXY Z )

Then for λ ∈ [0, 1/2], Ω̃(µ,γ,λ) (p) is twice differentiable.
Furthermore, for λ ∈ [0, 1/2], we have
d (µ,γ,λ)
Ω̃
(p)
dλ
h
i
= Ep(λ) ωp(µ,γ) (X, Y, Z|U ) ,
d2 (µ,γ,λ)
Ω̃
(p)
dλ2
h
i
= −Varp(λ) ωp(µ,γ) (X, Y, Z|U ) .

The second equality implies that Ω̃(µ,γ,λ) (p) is a concave
function of λ ∈ [0, 1/2].
d) For (µ, γ, λ) ∈ [0, 1]2 × [0, 1/2], define
ρ(µ,γ,λ) (pXY Z )
:=

max

(ν,p)∈[0,λ]
×Psh (pXY Z ):
Ω̃(µ,γ,λ) (p)
=Ω̃(µ,γ,λ) (pXY Z )

h
i
Varp(ν) ω̃p(µ,γ) (X, Y, Z|U ) ,

11

and set
ρ = ρ(pXY Z ) :=

max

(µ,γ,λ)∈[0,1]2 ×[0,1/2]

ρ(µ,γ,λ) (pXY Z ).

Then we have ρ(pXY Z ) < ∞. Furthermore, for any
(µ, γ, λ) ∈ [0, 1]2 × [0, 1/2], we have
Ω̃(µ,γ,λ) (pXY Z ) ≥ λR(µ,γ) (pXY Z ) −

λ2
ρ(pXY Z ).
2

e) For every τ ∈ (0, (1/2)ρ(pXY Z )), the condition (R1 ,
R2 + τ, R3 + τ ) ∈
/ R(pXY Z ) implies
F (R1 , R2 , R3 |pXY Z )


ρ(pXY Z ) 2
τ
>
·g
> 0,
4
ρ(pXY Z )
Since proofs of the results stated in Property 8 are quite
parallel with those of the results stated in Property 4, we omit
them. Our main result is the following.
Theorem 6: For any R1 , R2 , R3 ≥ 0, any pXY Z , and for
(n)
(n)
(n)
(n)
any (ϕ1 , ϕ2 , ϕ3 , ψ (n) , φ(n) ) satisfying (1/n) log ||ϕi ||
≤ Ri , i = 1, 2, 3, we have
(n)
(n)
(n)
(n)
P(n)
, φ(n) )
c (ϕ1 , ϕ2 , ϕ3 , ψ

≤ 7 exp {−nF (R1 , R2 , R3 |pXY Z )} .
It follows from Theorem 6 and Property 8 part d) that if
(R1 , R2 , R3 ) is outside the capacity region, then the error
probability of decoding goes to one exponentially and its
exponent is not below F (R1 , R2 , R3 |pXY Z ). It immediately
follows from Theorem 3 that we have the following corollary.
Corollary 4:
G(R1 , R2 , R3 |pXY Z ) ≥ F (R1 , R2 , R3 |pXY Z ),
G(pXY Z ) ⊆ G(pXY Z )
= {(R1 , R2 , R3 , G) : G ≥ F (R1 , R2 , R3 |pXY Z )} .
Proof of Theorem 6 will be given in the next section.
The exponent function at rates outside the rate region was
derived by Oohama and Han [7] for the separate source coding
problem for correlated sources [6]. The techniques used by
them is a method of types [8], which is not useful to prove
Theorem 3. Some novel techniques based on the information
spectrum method introduced by Han [9] are necessary to prove
this theorem.
From Theorem 6 and Property 8 part e), we can obtain an
explicit outer bound of RW (ε|pXY Z ) with an asymptotically
vanishing deviation from RW (pXY Z ) = R(pXY Z ). The
strong converse theorem established by Csiszár and Körner
[8] immediately follows from this corollary. To discribe this
outer bound, for κ > 0, we set
R(pXY Z ) − κ(0, 1, 1)
:= {(R1 , R2 − κ, R3 − κ) : (R1 , R2 , R3 ) ∈ R(pXY Z )},

which serves as an outer bound of R(pXY Z ). For each fixed
ε ∈ (0, 1), we define κ̃n = κ̃n (ε, ρ(pXY Z )) by
s
!

7
4
(35)
log
κ̃n := ρ(pXY )ϑ
nρ(pXY )
1−ε
s




6
7
7
ρ(pXY )
(a)
= 2
+ log
.
log
n
1−ε
n
1−ε
Step (a) follows from ϑ(a) = a + (3/2)a2 . Since κ̃n → 0
as n → ∞, we have the smallest positive integer n1 =
n1 (ε, ρ(pXY Z )) such that κ̃n ≤ (1/2)ρ(pXY Z ) for n ≥ n1 .
From Theorem 6 and Property 8 part e), we have the following
corollary.
Corollary 5: For each fixed ε ∈ (0, 1), we choose the above
positive integer n1 =n1 (ε, ρ(pXY Z )). Then, for any n ≥ n1 ,
we have
RW (ε|pXY Z ) ⊆ R(pXY Z ) − κ̃n (0, 1, 1).
The above result together with


[ \
RW (ε|pXY Z ) = cl 
RW (n, ε|pXY Z )
m≥1 n≥m

yields that for each fixed ε ∈ (0, 1), we have

RW (ε|pXY Z ) = RW (pXY Z ) = R(pXY Z ).
This recovers the strong converse theorem proved by Csiszár
and Körner [8].
Proof of this corollary is quite parallel with that of Corollary
2. We omit the detail.

A PPENDIX
A. Properties of the Rate Regions
In this appendix we prove Property 1. Property 1 part a)
can easily be proved by the definitions of the rate distortion
regions. We omit the proofs of this part. In the following
argument we prove the part b).
Proof of Property 1 part b: We set
\
RAKW (n, ε|pXY ).
RAKW (m, ε|pXY ) =
n≥m

By the definitions of RAKW (m, ε|pXY ) and RAKW (ε|pXY ),
we have that RAKW (m, ε|pXY ) ⊆ RAKW (ε|pXY ) for m ≥ 1.
Hence we have that
[
(36)
RAKW (m, ε|pXY ) ⊆ RAKW (ε|pXY ).
m≥1

We next assume that (R1 , R2 ) ∈ RAKW (ε|pXY ). Set
(δ)

RAKW (ε|pXY )
:= {(R1 + δ, R2 + δ) : (R1 , R2 ) ∈ RAKW (ε|pXY )}
Then, by the definitions of RAKW (n, ε |pXY ) and RAKW (
ε|pXY ), we have that for any δ > 0, there exists n0 (ε, δ) such
that for any n ≥ n0 (ε, δ),
(R1 + δ, R2 + δ) ∈ RAKW (n, ε|pXY ),

12

which implies that

where

(δ)

[

RAKW (ε|pXY ) ⊆

π(pX|U (·|u)) :=

RAKW (n, ε|pXY )

= RAKW (n0 (δ), ε|pXY )


[
⊆ cl 
RAKW (m, ε|pXY ) .

× log
(37)

m≥1

Here we assume that there exists a pair (R1 , R2 ) belonging to
RAKW (ε|pXY ) such that


[
RAKW (m, ε|pXY ) .
(38)
(R1 , R2 ) ∈
/ cl 
m≥1

Since the set in the right hand side of (38) is a closed set, we
have


[
(R1 + δ, R2 + δ) ∈
/ cl 
RAKW (m, ε|pXY )
(39)
m≥1

for some small δ > 0. On the other hand we have (R1 +
(δ)
δ, R2 + δ) ∈ RAKW (ε|pXY ), which contradicts (37). Thus we
have
[
RAKW (m, ε|pXY )
⊆ RAKW (ε|pXY ) ⊆ cl 

m≥1



RAKW (m, ε|pXY ) . (40)

Note here that RAKW (ε|pXY ) is a closed set. Then from (40),
we conclude that


[
RAKW (ε|W ) = cl 
RAKW (m, ε|pXY )
m≥1



= cl 

[ \

m≥1 n≥m

completing the proof.



RAKW (n, ε|pXY ) ,

B. Cardinality Bound on Auxiliary Random Variables
We first prove the following lemma.
Lemma 9:
R(µ) (pXY ) :=
= R(µ) (pXY ) :=

min

p∈P(pXY )

min

{µIp (X; U ) + Hp (Y |U )}

p∈Psh (pXY )

{µIp (X; U ) + Hp (Y |U )} .

Proof: We bound the cardinality |U| of U to show that the
bound |U| ≤ |X | is sufficient to describe R(µ) (pXY ). Observe
that
X
pX (x) =
pU (u)pX|U (x|u),
(41)
u∈U

µIp (X; U ) + Hp (Y |U ) =

X

u∈U

pU (u)π(pX|U (·|u)), (42)


 pµ

"
X
X|U (x|u)

 pµX (x)

x̃∈X

#−1 

pY |X (y|x̃)pX|U (x̃|u)
.


For each u ∈ U, π(pX|U (·|u)) is a continuous function of
pX|U (·|u). Then by the support lemma,
|U| ≤ |X | − 1 + 1 = |X |
is sufficient to express |X | − 1 values of (41) and one value
of (42).
Next we prove the following lemma.
Lemma 10: The cardinality bound |U| ≤ |X | in Q(pY |X )
is sufficient to describe the quantity Ω(µ,β,α) (pXY ). The
cardinality bound |U| ≤ |X | in Psh (pXY ) is sufficient to
describe the quantity Ω̃(µ,λ) (pXY ).
Proof: We first bound the cardinality |U| of U in Q(pY |X )
to show that the bound |U| ≤ |X | is sufficient to describe
Ω(µ,β,α) (pXY ). Observe that
X
qX (x) =
qU (u)qX|U (x|u),
(43)

u∈U
n
o
(µ,λ,α)
exp −Ω
(q|pX )
X
=
qU (u)Π(µ,β,α) (qX , qXY |U (·, ·|u)), (44)

m≥1

[

pX|U (x|u)pY |X (y|x)

(x,y)∈X ×Y

n≥n0 (ε,δ)



X

u∈U

where
Π(µ,λ,α) (qX , qXY |U (·, ·|u))
o
n
X
(µ,β)
qXY |U (x, y|u) exp −αωq|pX (x, y|u) .
:=
(x,y)

∈X ×Y

The value of qX included in Π(µ,β,α) (qX , qXY |U (·, ·|u))
must be preserved under the reduction of U. For each
u ∈ U, Π(µ,β) (qX , qXY |U (·, ·|u)) is a contineous function of
qXY |U (·, ·|u). Then by the support lemma,
|U| ≤ |X | − 1 + 1 = |X |
is sufficient to express |X | − 1 values of (43) and one value of
(44). We next bound the cardinality |U| of U in Psh (pXY ) to
show that the bound |U| ≤ |X | is sufficient to describe Ω(µ,λ)
(pXY ). Observe that
X
pX (x) =
pU (u)pX|U (x|u),
(45)
u∈U
n
o
(µ,λ)
exp −Ω
(p)
X
=
pU (u)Π̃(µ,λ) (pX , pXY |U (·, ·|u)),
u∈U

where
Π̃(µ,λ) (pX , pXY |U (·, ·|u))
n
o
X
pXY |U (x, y|u) exp −λωp(µ) (x, y|u) .
:=
(x,y)

∈X ×Y

(46)

13

The value of qX included in Π̃(µ,λ) (pX , qXY |U (·, ·|u)) must
be preserved under the reduction of U. For each u ∈
U, Π̃(µ,λ) (pX , pXY |U (·, ·|u)) is a contineous function of
pXY |U (·, ·|u). Then by the support lemma,
|U| ≤ |X | − 1 + 1 = |X |
is sufficient to express |X | − 1 values of (45) and one value
of (46).
C. Supporting Hyperplain Expressions of R(pXY )
In this appendix we prove Property 3 parts b), c), and d).
We first prove the part b).
Proof of Property 3 part b): For any µ ≥ 0, we have the
following chain of inequalities:
min

(R1 ,R2 )∈R(pXY )

=

min

p∈P(pXY )

(a)

=

min

{µR1 + R2 }

{µIp (X; U ) + Hp (Y |U )}

Step (a) follows from Lemma 9 stating that the cardinality
bound |U| ≤ |X | + 1 in P(pXY ) can be reduced to that |U| ≤
|X | in Psh (pXY ).
We next prove the part c).
Proof of Property 3 part c): For µ ≥ 1, we have the
following:

min

{R1 + R2 } = Hp (Y ).

(47)

Step (a) follows from Property 2 part b). The equality is
attained by (R1 , R2 ) = (0, Hp (Y )). Hence, by Property 3
part b), we have that for µ ≥ 1,
R(µ) (pXY ) =

min

(R1 ,R2 )∈R(pXY )

≤

min

p∈P(pXY )

min

{µ∗ Ip (U ; X) + Hp (Y |U )} − ǫ

p∈Psh (pXY )

{µ∗ Ip (U ; X) + Hp (Y |U )} − ǫ

∗

= R(µ ) (pXY ) − ǫ.

(48)

Step (a) follows from the definition of R(pXY ). The inequality
(48) implies that (R̂1 , R̂2 ) ∈
/ Rsh (pXY ). Thus Rsh (pXY ) ⊆
R(pXY ) is concluded. We next prove R(pXY ) ⊆ Rsh (pXY ).
We assume that (R1 ,R2 ) ∈ R(pXY ). Then, for each µ ≥ 0,
we have the following:
min

(R1 ,R2 )∈R(pXY )

(a)

{µR1 + R2 } = R(µ) (pXY ).

Then we have
Řsh (pXY ) ∩ Rsh (pXY ) = Rsh (pXY ) = R(pXY ). (49)
On Řsh (pXY ), we have the following:
(a) \
Řsh (pXY ) =
{(R1 , R2 ) : µR1 + R2 ≥ Hp (Y )}
= {(R1 , R2 ) : R1 + R2 ≥ Hp (Y )}

(a)

(R1 ,R2 )∈R(pXY )

=

{µ∗ R1 + R2 } − ǫ

µ≥1

{µR1 + R2 }

(R1 ,R2 )∈R(pXY )

≥

(a)

min

(R1 ,R2 )∈R(pXY )

Step (a) follows from Property 2 part b) Hence we have
R(pXY ) ⊆ Rsh (pXY ). We finally show Rsh (pXY ) = R(
pXY ). Set
\
Řsh (pXY ) =
{(R1 , R2 ) :
µ≥1 µR1 + R2 ≥ R(µ) (pXY )}.

= R(µ) (pXY ).

min

µ∗ R̂1 + R̂2 ≤

µR1 + R2 ≥

{µIp (X; U ) + Hp (Y |U )}

p∈Psh (pXY )

Then we have

{µR1 + R2 } = Hp (Y ),

completing the proof.
We finally prove the part d). We first prepare a lemma useful
to prove this property. From the convex property of the region
R(pXY ), we have the following lemma.
Lemma 11: Suppose that (R̂1 , R̂2 ) does not belong to
R(pXY ). Then there exist ǫ > 0 and µ∗ ≥ 0 such that for
any (R1 , R2 ) ∈ R(pXY ) we have
µ∗ (R1 − R̂1 ) + (R2 − R̂2 ) − ǫ ≥ 0.

(b)

= {(R1 , R2 ) : R1 + R2 ≥ R(1) (pXY )} ⊇ Rsh (pXY ).
(50)

Steps (a) and (b) follow from Property 2 part c). From (49),
(50), we have Rsh (pXY ) = R(pXY ).
D. Proof of Property 4 Part b)
In this appendix we prove Property 4 part b). Fix q =
qUXY ∈ Q(pY |X ), arbitrary. For pUXY = (pU|X , pXY ) ∈
Psh (pXY and for qY |U , define
(µ)
ω̂p,q
(x, y|u)
Y |U


pX|U (x|u)
1
:= β µ log
,
+ log
pX (x)
qY |U (y|u)
h
n
oi
Ω̂(µ,β) (p, qY |U ) := − log Ep exp −βωp(µ) (X, Y |U ) .

Then we have the following two lemmas.
1
] and any
Lemma 12: For any µ ∈ [0, 1], β ≥ 0, α ∈ [0, β+1
q = qUXY ∈ Q(pY |X ), there exists p = pUXY ∈ Psh (pXY )
such that

Proof of this lemma is omitted here. Lemma 11 is equivalent
to the fact that if the region R(pXY ) is a convex set, then for
any point (R̂1 , R̂2 ) outside the region R(pXY ), there exists
a line which separates the point (R̂1 , R̂2 ) from the region
R(pXY ).
Proof of Property 3 part d): We first prove Rsh (pXY )
⊆ R(pXY ). We assume that (R̂1 , R̂2 ) ∈
/ R(pXY ). Then by
Lemma 11, there exist ǫ > 0 and µ∗ ≥ 0 such that for any
(R1 , R2 ) ∈ R(pXY ), we have

Lemma 13: For any µ, β satisfying µ ∈ [0, 1], β ∈ [0, 1),
any p = pUXY ∈ Psh (pXY ), and any stochastic matrix qY |U
induced by qUXY ∈ Q(pY |X ), we have

µ∗ R̂1 + R̂2 ≤ µ∗ R1 + R2 − ǫ.

Ω̂(µ,β) (p, qY |U ) ≥ (1 − β)Ω̃(µ, 1−β ) (p).

Ω(µ,β,α) (q|pX ) ≥ αΩ̂(µ,β) (p, qY |U ).

β

(51)

(52)

14

From Lemmas 12 and 13 we have the following corollary.
Corollary 6: For any µ, β, α satisfying µ ∈ [0, 1], β ∈ [0, 1),
1
] and any q = qUXY ∈ Q(pY |X ), there exists
α ∈ [0, β+1
p = pUXY ∈ Psh (pXY ) such that
β

Ω(µ,β,α) (q|pX ) ≥ α(1 − β)Ω̃(µ, 1−β ) (p).

(53)

From (53), we have that for any µ ∈ [0, 1], β ∈ [0, 1), α ∈
1
[0, β+1
], we have
β

Ω(µ,β,α) (pXY ) ≥ α(1 − β)Ω̃(µ, 1−β ) (pXY ).

(54)

Proof of Lemma 12: We fix µ ∈ [0, 1], β ≥ 0, α ≥ 0
arbitrary. For each q = qUXY ∈ Q(pY |X ), we choose p =
pUXY ∈ Psh (pXY ) so that pU|X = qU|X . Then we have the
following:
n
o
exp −Ω(µ,β,α) (q|pX )
(
)α 
β
pµβ
p
(X)
X (X)qY |U (Y |U )
X

= Eq 
µβ
qX (X)
qX|U
(X|U )
(
)α
β
pµβ
p
(U,
X)
X (X)qY |U (Y |U )
UX
= Eq 
qUX (U, X)
pµβ
X|U (X|U )
ᾱ 

α
 pµβ ᾱ (X|U ) 
X|U

×
α
 q µβ ᾱ (X|U ) 
X|U
"
#!α
µβ
β
(b)
pUX (U, X) pX (X)qY |U (Y |U )
≤ Eq
qUX (U, X)
pµβ
X|U (X|U )
"
µβ αᾱ #!ᾱ
pX|U (X|U )
× Eq
qX|U (X|U )
n
o
= exp −αΩ̂(µ,β) (p, qY |U ) Aᾱ ,

and any q = qUXY ∈ Q(pY |X ), we have the following chain
of inequalities:
n
o
exp −Ω̂(µ,β) (p, qY |U )


) 1−β
( µβ
β
β
1−β 
p
(X|U
)p
(Y
|U
)
qY |U (Y |U ) 
Y |U
 X|U
= Ep 

µβ
p
pX (X)
Y |U (Y |U )
β
n
o q
β
Y |U (Y |U )
≤ exp (1 − β)Ω̃(µ, 1−β ) (p)
Ep
pY |U (Y |U )
o
n
β
)
(µ, 1−β
(p) .
= exp −(1 − β)Ω̃

(a)

Step (a) follows from Hölder’s inequality. Thus we have (52)
in Lemma 13.
Proof of Property 4 part b): We evaluate lower bounds of
F (R1 , R2 |pXY ) to obtain the following chain of inequalities:
F (R1 , R2 |pXY )
(a)

≥

sup

µ∈[0,1],
β∈[0,1)

1
]
α∈[0, β+1

sup

µ∈[0,1],
β∈[0,1)

=

1
2 + β(3 + µ)

o
n
β
× (1 − β)Ω̃(µ, 1−β ) (pXY ) − β(µR1 + R2 )
sup

µ∈[0,1],
β∈[0,1),
β
λ= 1−β
(c)

=

(1 − β)Ω̃(µ,λ) (pXY ) − β(µR1 + R2 )
2 + β(3 + µ)

sup
µ∈[0,1],
λ
β= 1+λ
,λ≥0

(55)

where we set

(d)

=

=

α
1 + α{1 + β(2 + µ)}

n
o
β
× (1 − β)Ω̃(µ, 1−β ) (pXY ) − β(µR1 + R2 )

(b)

=

sup

(1 − β)Ω̃(µ,λ) (pXY ) − β(µR1 + R2 )
2 + β(3 + µ)

Ω̃(µ,λ) (pXY ) − λ(µR1 + µR2 )
2 + λ(5 + µ)
µ∈[0,1],λ≥0
sup

F̃ (µ,β) (µR1 + R2 |pXY ).

sup

(56)

µ∈[0,1],λ≥0

A := Eq

"

pX|U (X|U )
qX|U (X|U )

µβ αᾱ #

.

Step (a) follows from Hölder’s inequality. From (55), we can
see that it suffices to show A ≤ 1 to complete the proof. When
1
α
βα
ᾱ ≤ 1 or equivalent to α ∈ [0, β+1 ], we have µβ ᾱ ≤ 1.
Then we apply Hölder’s inequality to A to obtain


µβ α



µβ αᾱ
 
pX|U (X|U )
 ≤ Eq
A = Eq  µβ α
qX|U (X|U )
q ᾱ (X|U )
pX|Uᾱ (X|U )
X|U

= 1.

Step (a) follows from the definition of F (R1 , R2 |pXY ) and
(54) in Corollary 6. Step (b) follows from that
sup
1
α∈[0, β+1
]

α
1
=
.
1 + α{1 + β(2 + µ)}
2 + β(3 + µ)

Steps (c) and (d) follow from that
β
λ
⇔ λ ≥ 0, β =
.
1−β
1+λ

β ∈ [0, 1), λ =
From (56), we have
F (R1 , R2 |pXY ) ≥

sup
µ∈[0,1],λ≥0

Hence we have (51) in Lemma 12.
Proof of Lemma 13: We fix µ ∈ [0, 1], β ∈ [0, 1),
1
α ∈ [0, β+1
], arbitrary. For any p = pUXY ∈ Psh (pXY ),

= F̃ (R1 , R2 |pXY ),
completing the proof.

F̃ (µ,λ) (µR1 + R2 |pXY )

15

E. Proof of Property 4 parts c), d), and e)
In this appendix we prove Property 4 parts c), d), and e).
We first prove the parts c) and d).
Proof of Property 4 parts c), d): We first prove the the
part c). We first show that for each p ∈ Psh (pXY ) and µ ∈
[0, 1], Ω̃(µ,λ) (p) exists for λ ∈ [0, 1]. On a lower bound of
exp[−Ω̃(µ,λ) (p)], for λ ∈ [0, 1], we have the following:
exp[−Ω̃(µ,λ) (p)]

µλ
X
pX (x)
pUXY (u, x, y)
=
pλY |U (y|u) (57)
pX|U (x|u)
(u,x,y)
∈U ×X ×Y

(a)

X

≥

pUXY (u, x, y)pX (x)pY |U (y|u).

(58)

(u,x,y)
∈U ×X ×Y

pX (x)
pX|U (x|u)

µλ

exp[−Ω̃(µ,λ) (p)] ≤

X

(u,x,y)
∈U ×X ×Y

X

=

≥ pX (x)pY |U (y|u).

≤

X



pX (x)
pUXY (u, x, y)
pX|U (x|u)

µλ

µλ
pU (u)p1−µλ
X|U (x|u)pX (x)

pU (u)

u∈U

=

X

X

a,b∈A

2

{ς(a) − ς(b)}
2
a,b∈A

2
X
X
p(λ) (a)ς 2 (a) + 
p(λ) (a)ς(a) ≤ 0.
=−
X

=−

!1−µλ

pX|U (x|u)

x∈X

pU (u) = 1.

X

!µλ

pX (x)

x∈X

Step (a) follows from (57) and pλY |U (y|u) ≤ 1. Step (b) follows
from µλ ∈ [0, 1] and Hölder’s inequality. We next prove that
that for each p ∈ Psh (pXY ) and µ ∈ [0, 1], Ω̃(µ,λ) (p) is twice
differentiable for λ ∈ [0, 1/2]. For simplicity of notations, set
a := (u, x, y), A := (U, X, Y ), A := U × X × Y,
ω̃p(µ) (x, y|u) := ς(a),
Ω̃(µ,λ) (p) := ξ(λ).
Then we have
Ω̃(µ,λ) (p) = ξ(λ) = − log 



pA (a)e−λς(a)  .

X

(b)

p(λ) (a)ς 2 (a) =

=e

ξ(λ)

X

a∈A
(c)

X

p(a)ς 2 (a)e−λς(a)+ξ(λ)

a∈A

p
p
p(a) e−2λς(a) ς 4 (a)

sX
p
2ξ(λ)−ξ(2λ)
p(a)ς 4 (a)
≤ e
a∈A

(d)

sX
p
p(a)ς 4 (a).
≤ e2ξ(λ)

(63)

a∈A

Step (a) follows from (62). Step (b) follows from (61). Step
(c) follows from Cauchy-Schwarz inequality and (60). Step (d)
follows from that ξ(2λ) ≥ 0 for 2λ ∈ [0, 1]. Note that ξ(λ)
exists for λ ∈ [0, 1/2]. Furtheomore we have the following:
X
p(a)ς 4 (a) < ∞.
a∈A

u∈U

X

(62)

a∈A

a∈A

′′

(59)



p(λ) (a)p(λ) (b)

a∈A

(u,x)
∈U ×X
(b)

ξ (λ) = −e


2
X
−
ς(b)}
{ς(a)
e−λ{ς(a)+ς(b)} 
×
p(a)pA (b)
2

− ξ ′′ (λ) ≤

It is obvious that the lower bound (58) of exp[−Ω̃(µ,λ) (p)]
take some positive value. This implies that Ω̃(µ,λ) (p) exists
for λ ∈ [0, 1]. We next show that ξ(λ) ≥ 0 for λ ∈ [0, 1]. On
upper bounds of exp[−Ω̃(µ,λ) (p)] for λ ∈ [0, 1], we have the
following chain of inequalities:
(a)

2ξ(λ)

(a)

pλY |U (y|u)

a∈A

a∈A

′′

On upper bound of −ξ ′′ (λ) ≥ 0 for λ ∈ [0, 1/2], we have the
following chain of inequalities:

Step (a) follows from that for λ ∈ [0, 1],


By simple computations we have


X
X
p(a)ς(a)e−λς(a)  =
p(λ) (a)ς(a),
ξ ′ (λ) = eξ(λ) 

(60)

Hence, by (63), ξ (λ) exists for λ ∈ [0, 1/2]. We next prove
the part d). We derive the lower bound (8) of Ω̃(µ,λ) (pXY ).
Fix any (µ, λ) ∈ [0, 1] ×[0, 1/2] and any p ∈ Psh (pXY ). By
the Taylor expansion of ξ(λ) = Ω̃(µ,λ) (p) with respect to λ
around λ = 0, we have that for any p ∈ Psh (pXY ) and for
some ν ∈ [0, λ]
1
Ω̃(µ,λ) (p) = ξ(0) + ξ ′ (0)λ + ξ ′′ (ν)λ2
2
h
i λ2
h
i
= λEp ω̃p(µ) (X, Y |U ) − Varp(ν) ω̃p(µ) (X, Y |U )
2
h
i
2
(a)
λ
(64)
≥ λR(µ) (pXY ) − Varp(ν) ω̃p(µ) (X, Y, Z|U ) .
2
Step (a) follows from p ∈ Psh (pXY ),
h
i
Ep ω̃p(µ) (X, Y |U ) = µIp (X; U ) + Hp (Y |U ),

The quantity p(λ) (a) = pA (a), a ∈ A has the following form:

and the definition of R(µ) (pXY ). Let (νopt , popt ) ∈ [0, λ]×
Psh (pXY ) be a pair which attains ρ(µ,λ) (pXY ). By this
definition we have that

p(λ) (a) = eξ(λ) p(a)e−λς(a) .

Ω̃(µ,λ) (popt ) = Ω̃(µ,λ) (pXY )

a∈A

(λ)

(61)

(65)

16

and that for any ν ∈ [0, λ],
i
h
Varp(ν) ωp(µ)
(X, Y |U )
opt
opt
i
h
(X,
Y
|U
)
= ρ(µ,λ) (pXY ).
≤ Var (νopt ) ωp(µ)
opt
popt

F. Proof of Lemma 1

(66)

On lower bounds of Ω(µ,λ) (pXY ), we have the following chain
of inequalities:
(a)

Ω̃(µ,λ) (pXY ) = Ω̃(µ,λ) (popt )
i
h
(b)
λ2
(X,
Y
|U
)
≥ λR(µ) (pXY ) − Varp(ν) ω̃p(µ)
opt
opt
2
2
(c)
λ
≥ λR(µ) (pXY ) − ρ(µ,λ) (pXY )
2
2
(d)
λ
≥ λR(µ) (pXY ) − ρ(pXY ).
2

To prove Lemma 1, we prepare a lemma. Set


pSX n Y n (s, xn , y n )
1
n n
≥ −η .
An := (s, x , y ) : log
n
qSX n Y n (s, xn , y n )
Furthermore, set


pX n (xn )
1
≥
−η
,
B̃n := xn : log
n
qX n (xn )
Bn := B̃n × M1 × Y n , Bnc := B̃nc × M1 × Y n ,
(n)
C˜n := {(s, xn ) : s = ϕ1 (xn ),
pX n |S (xn |s) ≤ M1 enη pX n (xn )},
n
Cn := C˜n × Y , C c := C˜c × Y n ,
n

n

(n)

Dn := {(s, xn , y n ) : s = ϕ1 (xn ),
pY n |S (y n |s) ≥ (1/M2 )e−nη },
(n)

Step (a) follows from (65). Step (b) follows from (64). Step
(c) follows from (66). Step (d) follows from the definition of
ρ(pXY ).
We next prove the part e). For the proof we use the following
lemma.
Lemma 14: When τ ∈ (0, (1/2)ρ], the maximum of
o
1 n ρ 2
− λ + τλ
2 + 6λ
2
for λ ∈ (0, 1/2] is attained by the positive λ0 satisfying
τ
3
(67)
ϑ(λ0 ) := λ0 + λ20 = .
2
ρ
Let g(a) be the inverse function of ϑ(a) for a ≥ 0. Then the
condition of (67) is equivalent to λ0 = g( τρ ). The maximum
is given by
 
o ρ
n ρ
1
ρ 2 τ
2
2
.
− λ0 + τ λ0 = λ0 = g
2 + 6λ0
2
4
4
ρ

By an elementary computation we can prove this lemma.
We omit the detail.
Proof of Property 4 part e): By the hyperplane expression
Rsh (pXY ) of R(pXY ) stated Property 3 part b) we have that
when (R1 , R2 + τ ) ∈
/ R(pXY ), we have
∗

R(µ ) (pXY ) − (µ∗ R1 + R2 ) > τ

(68)

for some µ∗ ∈ [0, 1]. Then for each positive τ , we have the
following chain of inequalities:
F̃ (R1 , R2 |pXY ) ≥
∗

λ∈(0,λ∗ ]

,λ)

(µ∗ R1 + R2 |pXY )

(pXY ) − λ(µ∗ R1 + R2 )
2 + λ(5 + µ)
λ∈(0,1/2]
n
(a)
ρ
1
− λ2
≥ sup
2
λ∈(0,1/2] 2 + 6λ

=

sup

Ω̃(µ

∗

sup F̃ (µ

En := {(s, xn , y n ) : s = ϕ1 (xn ),
(n)
(n)
ψ (n) (ϕ1 (xn ), ϕ2 (y n )) = y n }.
Then we have the following lemma.
Lemma 15:
pSX n Y n (Acn ) ≤ e−nη , pSX n Y n (Bnc ) ≤ e−nη ,
pSX n Y n (Cnc ) ≤ e−nη , pSX n Y n (Dnc ∩ En ) ≤ e−nη .
Proof: We first prove the first inequality.
X
pSX n Y n (s, xn , y n )
pSX n Y n (Acn ) =
(s,xn ,y n )∈Acn

(a)

=

Step (a) follows from Property 4 part d). Step (b) follows from
(68). Step (c) follows from Lemma 14.

e−nη qSX n Y n (s, xn , y n )

(s,xn ,y n )∈Acn
e−nη qVn (Acn )

≤ e−nη .

Step (a) follows from the definition of An . On the second
inequality we have
X
pSX n Y n (Bnc ) = pX n (B̃nc ) =
pXn (xn )
c
xn ∈B̃n

(a)

≤

X

c
xn ∈B̃n

 
e−nη qX n (xn ) = e−nη qX n B̃nc ≤ e−nη .

Step (a) follows from the definition of Bn . We next prove the
third inequality.
=

pSX n Y n (Cnc ) = pSX n (C˜nc )
X
X
s∈M1

,λ)


∗
+ λR(µ ) (pXY ) − λ(µ∗ R1 + R2 )
o (c) ρ  τ 
(b)
1 n ρ 2
− λ + τ λ = g2
.
> sup
2
4
ρ
λ∈(0,1/2] 2 + 6λ

X

≤

≤

pX n (xn )

(n)

xn :ϕ1 (xn )=s
pX n (xn )≤(1/M1 )e−nη
×pX n |S (xn |s)

1 −nη X
e
M1

s∈M1

X

pX n |S (xn |s)

(n)

xn :ϕ1 (xn )=s
pX n (xn )≤(1/M1 )e−nη
×pX n |S (xn |s)

1 −nη
e
|M1 | = e−nη .
M1
Finally we prove the fourth inequality. We first observe that
X
pX n (xn )
pS (s) =
pX n (xn ), pX n |S (xn |s) =
.
pS (s)
(n)
n
n
≤

x :ϕ1 (x )=s

17

We have the following chain of inequalities:

Then we have the following.
(n)

pSX n Y n (Dnc ∩ En )
X
X
=
pS (s)
s∈M1

pX n |S (xn |s)

c

+pSX n Y n ([An ∩ Bn ∩ Cn ∩ Dn ] ∩ En )
≤ pSX n Y n (An ∩ Bn ∩ Cn ∩ Dn )

(n)
xn :ϕ1 (xn )=s

X

×

pY n |X n (y n |xn )

+pSX n Y n (Acn ) + pSX n Y n (Bnc ) + pSX n Y n (Cnc )
+pSX n Y n (Dnc ∩ En )

(n)
y :ψ
(s,ϕ2 (y n ))=y n
n
pY n |S (y |s)≤(1/M2 )e−nη
(n)

n

=

pS (s)

X

o
1 −nη n n
(n)
e
pS (s)
y : ψ (n) (s, ϕ2 (y n )) = y n
M2

s∈M1

≤

s∈M1
(a)

≤

(a)

X

X

s∈M1

X

(n)

(n)
P(n)
) = pSX n Y n (En )
c (ϕ1 , ϕ2 , ψ
= pSX n Y n (An ∩ Bn ∩ Cn ∩ Dn ∩ En )

pY n |S (y n |s)

≤ pSX n Y n (An ∩ Bn ∩ Cn ∩ Dn ) + 4e−nη .

(n)

y n :ψ (n) (s,ϕ2 (y n ))=y n
pY n |S (y n |s)≤(1/M2 )e−nη

Step (a) follows from Lemma 15.

1 −nη
e
M2 = e−nη .
pS (s)
M2

In this appendix we prove Lemma 3.
Proof of Lemma 3: We first prove the following Markov
chain (14) in Lemma 3:

Step (a) follows from that the number of y n correctly decoded
does not exceed M2 .
Proof of Lemma 1: By definition we have
pSX n Y n (An ∩ Bn ∩ Cn ∩ Dn )

pSX n Y n (S, X n , Y n )
1
≥ −η,
log
= pSX n Y n
n
q̂SX n Y n (S, X n , Y n )
n
1
qX n (X )
0 ≥ log
− η,
n
pX n (X n )
pX n |S (X n |S)
1
1
− η,
log M1 ≥ log
n
n
pX n (X n )

1
1
1
log M2 ≥ log
−η .
n
n
pY n |S (Y n |S)
(n)

(n)

G. Proof of Lemma 3

SX t−1 ↔ Xt ↔ Yt .
We have the following chain of inequalities:
I(Yt ; SX t−1 |Xt ) = H(Yt |Xt ) − H(Yt |SX t−1 Xt )
(a)

≤ H(Yt |Xt ) − H(Yt |SX n ) = H(Yt |Xt ) − H(Yt |X n )
(b)

= H(Yt |Xt ) − H(Yt |Xt ) = 0.
(n)

Step (a) follows from that S = ϕ1 (X n ) is a function
of X n . Step (b) follows from the memoryless property of
the information source {(Xt , Yt )}∞
t=1 . Next we prove the
following Markov chain (15) in Lemma 3:
Y t−1 ↔ SX t−1 ↔ (Xt , Yt ).

(n)

Then for any (ϕ1 , ϕ2 , ψ (n) ) satisfying (1/n) log ||ϕi || ≤
Ri , i = 1, 2, we have

We have the following chain of inequalities:
I(Xt Yt ; Y t−1 |SX t−1 )

pSX n Y n (An ∩ Bn ∩ Cn ∩ Dn )

1
pSX n Y n (S, X n , Y n )
≤ pSX n Y n
≥ −η,
log
n
q̂SX n Y n (S, X n , Y n )
qX n (X n )
1
− η,
0 ≥ log
n
pX n (X n )
n
pX n |S (X |S)
1
R1 ≥ log
− η,
n
pX n (X n )

1
1
−
η
.
R2 ≥ log
n
pY n |S (Y n |S)
Hence, it suffices to show
(n)

(n)

+4e−nη
to prove Lemma 1. By definition we have
(n)

(a)

= H(Y t−1 |X t−1 ) − H(Y t−1 |X n Yt )

(b)

= H(Y t−1 |X t−1 ) − H(Y t−1 |X t−1 Yt ) = 0.
(n)

Step (a) follows from that S = ϕ1 (X n ) is a function of
X n . Step (b) follows from the memoryless property of the
information source {(Xt , Yt )}∞
t=1 .
H. Proof of Lemma 6

(n)
P(n)
) ≤ pSX n Y n (An ∩ Bn ∩ Cn ∩ Dn )
c (ϕ1 , ϕ2 , ψ

(n)

= H(Y t−1 |SX t−1 ) − H(Y t−1 |SX t−1 Xt Yt )
≤ H(Y t−1 |X t−1 ) − H(Y t−1 |X n SYt )

(n)
P(n)
) = pSX n Y n (En ) .
c (ϕ1 , ϕ2 , ψ

In this appendix we prove Lemma 6.
(µ,β,α)
Proof of Lemma 6 : By the definition of pSX t Y t (s, xt , y t ),
for t = 1, 2, · · · , n, we have
(µ,β,α)

pSX t Y t (s, xt , y t ) = Ct−1 pSX t Y t (s, xt , y t )
t
Y
(µ,β,α)
fqX ||pX ,pX Y |U (xi , yi |ui ).
×
i=1

i

i

i i

i

(69)

18

Then we have the following chain of equalities:
(µ,β,α)

pSX t Y t (s, xt , y t ) = Ct−1 pSX t Y t (s, xt , y t )
t
Y
(µ,β,α)
fqX ||pX ,pX Y |U (xi , yi |ui )
×
i

=

=

i

i i

i

i=1
Ct−1 pSX t−1 Y t−1 (s, xt−1 , y t−1 )
t−1
Y (µ,β,α)
×
fqX ||pX ,pX Y |U (xi , yi |ui )
i
i
i i i
i=1
×pXt Yt |SX t−1 Y t−1 (xt , yt |s, xt−1 , y t−1 )
(µ,β,α)
×fqX ||pX ,pX Y |U (xt , yt |ut )
t

(b)

[7] Y. Oohama and T. S. Han, “Universal coding for the Slepian-wolf data
compression system and the strong converse theorem,”IEEE Transactions on Information Theory, vol IT-40, no.6, 1908-1919, Nov. 1994.
[8] I. Csiszár and J. Körner, Information Theory: Coding Theorems for
Discrete Memoryless Systems. London, U.K., Academic, 1981.
[9] T. S. Han, Information-Spectrum Methods in Information Theory.
Springer-Verlag, Berlin, New York, 2002. The Japanese edition was
published by Baifukan-publisher, Tokyo, 1998.

(a)

t

t t

t

(µ,β,α)
Ct−1 Ct−1 pSX t−1 Y t−1 (s, xt−1 , y t−1 )
×pXt Yt |SX t−1 Y t−1 (xt , yt |s, xt−1 , y t−1 )
(µ,β,α)
×fqX ||pX ,pX Y |U (xt , yt |ut )
t
t
t t
t
(µ,β,α) −1 (µ,β,α)
) pSX t−1 Y t−1 (s, xt−1 , y t−1 )
×pXt Yt |SX t−1 Y t−1 (xt , yt |s, xt−1 , y t−1 )
(µ,β,α)
×fqX ||pX ,pX Y |U (xt , yt |ut ).
t
t
t t
t

= (Φt

(70)

Steps (a) and (b) follow from (69). From (70), we have
(µ,β,α) (µ,β,α)
pSX t Y t (s, xt , y t )
(µ,β,α)
pSX t−1 Y t−1 (s, xt−1 , y t−1 )

Φt
=

(71)

×pXt Yt |SX t−1 Y t−1 (xt , yt |s, xt−1 , y t−1 )
(µ,β,α)
(xt , yt |ut ).
t ||pXt ,pXt Yt |Ut

×fqX

(72)

Taking summations of (71) and (72) with respect to s, xt , y t ,
we obtain
(µ,β,α)

=

Φt
X

(µ,β,α)

pSX t−1 Y t−1 (s, xt−1 , y t−1 )

s,xt ,y t

×pXt Yt |SX t−1 Y t−1 (xt , yt |s, xt−1 , y t−1 )
(µ,β,α)
(xt , yt |ut ),
t ||pXt ,pXt Yt |Ut

×fqX

completing the proof.
Acknowledgements
We are very grateful to Dr. Shun Watanabe and Dr. Shigeaki
Kuzuoka for their helpful comments.
R EFERENCES
[1] R. F. Ahlswede and J. Körner, “Source coding with side information
and a converse for degraded broadcast channels,” IEEE Trans. Inform.
Theory, vol. IT-21, pp. 629-637, Nov. 1975.
[2] A. D. Wyner, “On source coding with side information at the decoder,”
IEEE Trans. Inform. Theory, vol. IT-21, pp. 294-300, May 1975.
[3] R. Ahlswede, P. Gàs, and J. Körner, “Bounds on conditional probabilities
with applications in multi-user communication,” Z. Wahrscheinlichkeitstheorie verw. Gebiete, vol. 34, pp. 157-177, 1976.
[4] A. D. Wyner and J. Ziv, “The rate-distortion function for source coding
with side information at the decoder,” IEEE Trans. Inform. Theory, vol.
IT-22, pp. 1-10, Jan. 1976.
[5] W. Gu and M. Effors, “A strong converse for a collection of network
source coding problems,” Proceedings of the IEEE International Symposium on Information Theory, Soul, Korea, pp.2356-2320, June 2009.
[6] D. Slepian and J. K. Wolf, “Noiseless coding of correlated information
sources,” IEEE Trans. Inform. Theory, vol. IT-19, pp. 471-480, July
1973.

