On the Reliability Function of Distributed
Hypothesis Testing Under Optimal Detection

arXiv:1801.03687v1 [] 11 Jan 2018

Nir Weinberger, Member, IEEE and Yuval Kochman, Member, IEEE

Abstract
The distributed hypothesis-testing problem with full side-information is studied. The trade-off (reliability function) between the type 1 and type 2 error exponents under limited rate is studied in the following way. First,
the problem of determining the reliability function of distributed hypothesis-testing is reduced to the problem of
determining the reliability function of channel-detection codes (in analogy to a similar result which connects the
reliability of distributed compression and ordinary channel codes). Second, a single-letter random-coding bound
based on an hierarchical ensemble, as well as a single-letter expurgated bound, are derived for the reliability of
channel-detection codes. Both bounds are derived for the optimal detection rule. We believe that the resulting bounds
are ensemble-tight, and hence optimal within the class of quantization-and-binning schemes.
Index Terms
Binning, channel-detection codes, distributed hypothesis-testing, error exponents, expurgated bounds, hierarchical
ensembles, multiterminal data compression, random coding, side information, statistical inference, superposition
codes.

I. I NTRODUCTION
In the hypothesis-testing (HT) problem, a detector needs to decide between two hypotheses regarding the
underlying distribution of some observed data; the hypotheses are commonly known as the null hypothesis and
the alternative hypothesis. Two types of error probability are defined - the type 1 error probability of deciding on
the alternative hypothesis when the null hypothesis prevails, and type 2 error probability for the opposite event.
The celebrated Neyman-Pearson lemma (e.g., [1, Prop. II.D.1]) states that the detector which achieves the optimal
trade-off between the two error probabilities takes the form of comparing the likelihood-ratio to a threshold.
In the context of this work, we only consider data which is a sequence Z1 , . . . , Zn of independent and identically
distributed observations, and therefore the hypotheses correspond to the distribution of a random variable Z . In
information-theoretic literature (e.g., [2], [3, Ch. 11], [4, Ch. 1], [5, Sec. 2]), large-deviations theory, most notably
Sanov’s theorem, is usually applied to this problem. In particular, Stein’s theorem provides the largest exponential
The material in this paper was presented in part at the Information Theory and Applications (ITA) Workshop, San Diego, California, USA,
February 2017.

2

decrease rate of the type 2 error probability when the type 1 error probability is bounded away from one. More
generally, the reliability function, i.e., the optimal trade-off between the two types of exponents when both are
strictly positive, is also known.
As a special case of the HT problem, one may consider a pair of random variables Z = (X, Y ), instances of
which are fully observed by the detector. If, however, the detector does not directly observe the data sequence, the
characterization of the optimal performance is much more challenging. A common model for such a scenario is
known as distributed hypothesis-testing (DHT), and its reliability function is the subject of this paper.
The DHT model was introduced by Berger [6] as an example for a problem at the intersection of multi-terminal
information theory and statistical inference. In this model, one encoder observes X1 , . . . , Xn , while the other
observes the corresponding Y1 , . . . , Yn ; they produce codewords to be sent over limited-rate noiseless links to a
common detector. The goal is to characterize the optimal detection performance, under a given pair of encoding rates.
As a starting point, usually an asymmetric model (sometimes referred to as the side-information case) is studied,
in which the Y -observations are fully available to the decoder, and thus there is only a single rate constraint.
The first major breakthrough on this problem was in a notable paper by Ahlswede and Csiszár [7], who addressed
a special scenario termed testing against independence. In this case, the null hypothesis states that (X, Y ) have a
given joint distribution PXY , whereas the alternative hypothesis states that they are independent, but with the same
marginals as in the null hypothesis. This case is special since the Kullback–Leibler divergence, which is usually
associated with Stein’s exponent of HT, can be identified as the mutual information between X and Y under PXY ,
which is naturally related to compression rates. This allowed the authors to use distributed compression, specifically
quantization-based encoding techniques from [8], [9], to derive Stein’s exponent for the side-information testingagainst-independence problem [7, Th. 2]. Quantization-based encoding was also used for an achievable Stein’s
exponent for a general pair of memoryless hypotheses [7, Th. 5], but without a converse bound.
As summarized in [10, Sec. IV], later progress on this problem for a pair of general hypotheses was nonconsecutive, and contributions were made by several groups of researchers. First, in [11], the achievable bound on
Stein’s exponent from [7, Th. 5] was improved, and also generalized beyond the side-information case. Then, in
[12], achievable bounds on the full trade-off between the two types of exponents were derived. In [13], Stein’s
exponent for side-information cases was further significantly improved using binning, as will be described in the
sequel.
Interestingly, when either the X -marginal or the Y -marginal of the hypotheses is different, positive exponents can
be obtained even for zero-rate encoders [10, Sec. V].1 For this case, achievable Stein’s exponents and exponential
trade-offs were derived in [10, Th. 5.5] and [11], [12], [15], along with matching converse bounds when some kind
of assumptions are imposed.
In the last decade, a renewed interest in the problem arose, aimed both at tackling more elaborated models,
as well as at improving the results on the basic model. As for the former, Stein’s exponents under positive rates
1

There is also a variant of one-bit encoding, see [10, Sec. V] and [14].

3

were explored in successive refinement models [16], for multiple encoders [17], for interactive models [18], [19],
under privacy constraints [20], combined with lossy compression [21], over noisy channels [22], [23], for multiple
decision centers [24], as well as over multi-hop networks [25]. Exponents for the zero-rate problem were studied
under restricted detector structure [14] and for multiple encoders [26]. The finite blocklength and second-order
regimes were addressed in [27].
As for the basic model, which this work also investigates, the encoding approach used in [13] is currently the best
known. It is based on quantization and binning, just as used, e.g., for distributed lossy compression (the Wyner-Ziv
problem [28, Ch. 11] [29]). First, the encoding rate is reduced by quantization of the source vector to a reproduction
vector chosen from a codebook. Second, the rate is further reduced by binning of the reproduction vectors. As the
detector is equipped with side information, it can identify the true reproduction vector with high reliability. In the
context of DHT, it can then decide on one of the hypotheses using this reproduction and the side information. In
[17] it was shown that a quantization-and-binning scheme achieves the optimal Stein’s exponent in a testing against
conditional independence problem (as well as in a model inspired by the Gel’fand-Pinsker problem [30], and also
in a Gaussian model). In [31], the quantization-and-binning scheme was shown to be necessary for the case of
DHT with degraded hypotheses. In [32], [33], improved exponents were derived (for a doubly-symmetric binary
source) by refining the analysis of the effect of binning errors. In addition, a full achievable exponent trade-off
was presented, and Körner-Marton coding [34] was used in order to extend the analysis to the symmetric-rate case
(for the symmetric source). Finally, [35] suggested an improved detection rule, in which the reproduction vectors
in the bin are exhausted one-by-one, and the null hypothesis is declared if a single vector is jointly typical with
the side-information vector.
It is evident that the detectors above are all sub-optimal, as they are based upon the two-stage process of
reproduction and then testing. However, the decoding of the source vector (or its quantized version) is totally
superfluous for the DHT system, as the requirement from the latter is only to distinguish between the hypotheses.
In fact, this detection procedure is still sub-optimal even if quantization is used without binning, and only the
second stage of the detector is employed. While [35] offered an improved detector, it is still sub-optimal.2 In this
work, we investigate the performance of the optimal detector. In fact, the optimal detector directly follows from
the standard Neyman-Pearson lemma (see Section III). Nonetheless, analyzing its performance is highly non-trivial
for DHT.
Specifically, we study the reliability function in the side-information case, and will be guided by the following
methodology. Recall that for distributed lossless compression systems (the Slepian-Wolf problem [28, Ch. 10] [37]),
the side information helps to fully reproduce the source. The concept of binning the source vectors was originally
conceived for this problem, and a common wisdom for this problem states that the source vectors which belong to the
same bin should constitute a good channel code for the memoryless channel induced by the conditional distribution
2
Recently in the zero-rate regime, [27] considered the use of an optimal Neyman-Pearson-like detector, rather than the possibly sub-optimal
Hoeffeding-like detector [36] that was used in [12].

4

of Y given X . This intuition was made precise in [38, Th. 1][39], [40], which showed that the reliability function3 of
distributed compression is directly related to the reliability of channel coding. The idea is to use structured binning,4
using a sequence of channel codes which achieves the channel reliability function. At a given blocklength, such
a channel code corresponds to one bin of the distributed compression system.5 All other bins of the system are
generated by permuting6 the source vectors of the first bin. Due to the memoryless nature of the problem, all bins
generated this way are essentially as good as the original one, and this allows to directly link the reliability function
of distributed compression to that of channel coding. While the reliability of channel codes is itself only known
above the critical rate [4, Corollary 10.4], this characterization has two advantages nonetheless. First, analyzing
channel codes is simpler than analyzing a distributed compression systems. Second, any bound on the reliability of
channel codes immediately translates into a bound on the reliability of distributed compression systems. Specifically,
the expurgated bound [4, Problem 10.18] and the sphere-packing bound [4, Th. 10.3] can be immediately used,
rather than just a random-coding bound [4, Th. 10.2]. Noting the similarity between the distributed compression
problem and the DHT problem, it is natural to ask whether structured binning is useful for the DHT problem, and
what are the the properties of a “good” bin for the DHT problem?
To address these questions, we introduce the concept of channel-detection (CD) codes. Such codes are not
required to carry information, but are rather designed for the task of distinguishing between two possible channel
distributions.7 Namely, a codeword from the code is chosen with a uniform probability over the codewords, and
the detector should decide on the prevailing channel, based only on the output vector (and its knowledge of the
codebook). It will be evident that this is the same problem encountered by the detector of a DHT system, given
the encoded message. It will be shown that optimal DHT systems (in the exponential sense) can be generated
by optimal CD codes, just like distributed compression systems are generated from ordinary channel codes. From
this observation, the close relation between the reliability of DHT systems and CD codes will be determined. An
illustration of the analogy between the relations distributed compression/channel coding and DHT/CD relations
appears in Fig. 1 (with all quantities there will be formally defined in the sequel). .
This intimate connection allows us to derive bounds on the reliability function of DHT using bounds on the
reliability of CD codes. Concretely, we will derive both random-coding bounds and expurgated bounds on the
reliability of CD codes under the optimal Neyman-Pearson detector. The analysis goes beyond that of [42] in
two senses: first, it is based on a Chernoff distance characterization of the optimal exponents, which leads to
simpler single-letter bounds; and second, the analysis is performed for an hierarchical ensemble 8 , corresponding
3
The reliability function of distributed lossless compression is the optimal exponential decrease of the error probability as a function of
the compression rate.
4
Also mentioned in [17] for the DHT problem, though recognized as inessential.
5
More precisely, this is done type-by-type, i.e., per the subsets of source sequences that share the same empirical distribution.
6
This permutation technique, originally developed in [38], [41] will be useful here too, and will be reviewed in more detail in what follows.
7
In [42], a a somewhat different channel-detection setting is considered, where the code is required to simultaneously be a good channel
code (in the ordinary sense), as well as a good CD code. In this work, it will only be required that the codewords of the CD code are
different from one another.
8
Yielding superposition codes [43], such as the ones used for the broadcast channel, wee, e.g., [28, Ch. 5])

5

Distributed Source Coding
xn

encoder

decoder

010 : : :

fn (xn )

Distributed Hypothesis Testing
x
^n

'n (fn (xn ); y n )

xn

encoder

010 : : :

fn (xn )

detector

H=H̄

'n (fn (xn ); y n )

yn

yn
PXY =P̄XY

PXY

Channel Coding

Channel Detection
PY jX

X

PY jX

Y

Y

X

P̄Y jX

Figure 1. An analogy between distributed compression and DHT.

to quantization-and-binning schemes.
The outline of the rest of the paper is as follows. The system model and preliminaries, such as notation conventions
and background on ordinary HT, will be given in Section II. The main result of the paper, namely an achievable
bound on the reliability function of DHT under optimal detection, will be stated in Section III, along with some
consequences. For the sake of proving these bounds, the reduction of the DHT reliability problem to the CD
reliability problem will be considered in Section IV. While only achievability bounds will ultimately be derived,
the reduction to CD codes has both an achievability part as well as a converse part. Derivation of single-letter
achievable bounds on the reliability of CD codes will be considered in Section V. From this, the achievability
bounds on the DHT reliability will immediately follow. Afterwards, a discussion on computational aspects along
with a numerical example are given in Section VI. Several directions for further research are highlighted in Section
VII.

6

II. S YSTEM M ODEL
A. Notation Conventions
Throughout the paper, random variables will be denoted by capital letters, specific values they may take will
be denoted by the corresponding lower case letters, and their alphabets will be denoted by calligraphic letters.
Random vectors and their realizations will be superscripted by their dimension. For example, the random vector
X n = (X1 , . . . , Xn ) (n positive integer), may take a specific vector value xn = (x1 , . . . , xn ) ∈ X n , the nth order

Cartesian power of X , which is the alphabet of each component of this vector. The Cartesian product of X and Y
(finite alphabets) will be denoted by X × Y .
We will follow the standard notation conventions for probability distributions, e.g., PX (x) will denote the
probability of the letter x ∈ X under the distribution PX . The arguments will be omitted when we address the
entire distribution, e.g., PX . Similarly, generic distributions will be denoted by Q, Q, and in other similar forms,
subscripted by the relevant random variables/vectors/conditionings, e.g. QXY , QX|Y . The joint distribution induced
by QX and QY |X will be denoted by QX × QY |X .
In what follows, we will extensively utilize the method of types [4], [44] and use the following notations. The
type class of a type QX at blocklength n, i.e., the set of all xn ∈ X n with empirical distribution QX , will be
denoted by Tn (QX ). The set of all type classes of vectors of length n from X n will be denoted by Pn (X ), and the
def S
set of all possible types over X will be denoted by P(X ) = ∞
n=1 Pn (X ). Similar notations will be used for pairs

of random variables (and larger collections), e.g., Pn (U × X ), and Tn (QU XY ) ⊆ U n × X n × Y n . The conditional
type class of xn for a conditional type QY |X , namely, the subset of Tn (QY ) such that the joint type of (xn , y n )

is QXY , will be denoted by Tn (QY |X , xn ) (sometimes called the Q-shell of xn [4, Definition 2.4]). For a given
QX ∈ Pn (X ), the conditional type classes QY |X such that Tn (QY |X , xn ) is not empty when xn ∈ Tn (QX ) will

be denoted by Pn (Y, QX ). The probability simplex for an alphabet X will be denoted by S(X ).
For two distributions PX , QX over the same finite alphabet X , the variational distance (L1 norm) will be denoted
by
def

kPX − QX k =

X

x∈X

|PX (x) − QX (x)| .

(1)

When optimizing a function of a distribution QX over a probability simplex S(X ), the explicit display of the
constraint will be omitted. For example, for a function f (Q), minQ f (Q) will be used instead of minQ∈S(X ) f (Q).
The expectation operator with respect to a given distribution, e.g., Q, will be denoted by EQ [·] where the subscript
Q will be omitted if the underlying probability distribution is clear from the context. In general, information-theoretic

quantities will be denoted by the standard notation [3], with subscript indicating the distribution of the relevant
random variables, e.g. HQ (X|Y ), IQ (X; Y ), IQ (X; Y |U ), under Q = QU XY . As an exception, the entropy of
X under Q will be denoted by H(QX ). The binary entropy function will be denoted by hb (q) for 0 ≤ q ≤ 1.

The conditional Kullback–Leibler divergence between conditional two distributions, e.g., QX|U and PX|U , when

7

averaged with the distribution QU will be denoted by D(QX|U ||PX|U |QU ), and in case that U is degenerated, the
notation will be simplified to D(QX ||PX ).

The Hamming distance between two vectors, xn ∈ X n and xn ∈ X n will be denoted by dH (xn , xn ). The

complement of a set A will be denoted by Ac . For a finite multiset A, the number of distinct elements will be
denoted by |A|. The probability of the event A will be denoted by P(A), and its indicator function will be denoted
by I(A).
.
For two positive sequences, {an } and {bn } the notation an = bn , will mean asymptotic equivalence in the

exponential scale, that is, limn→∞

1
n

˙ bn will mean lim supn→∞
log( abnn ) = 0. Similarly, an ≤

so on. The notation an ∼
= bn will mean that limn→∞

an
bn

1
n

log( abnn ) ≤ 0, and

= 1. The ceiling function will be denoted by ⌈·⌉. The

notation |t|+ will stand for max{t, 0}. Logarithms and exponents will be understood to be taken to the natural
base. Throughout, for the sake of brevity, we will ignore integer constraints on large numbers. For example, ⌈enR ⌉
will be written as enR . For n ∈ N, the set {1, . . . , n} will be denoted by [n].

B. Ordinary Hypothesis-Testing
Before getting into the distributed scenario, we will shortly review in this section ordinary HT between a pair of
hypotheses. Consider a random variable Z over a finite alphabet Z , whose distribution according to the hypothesis
H (respectively, H ) is given by P (respectively, P ). It is common in the literature to refer to H (respectively, H ) as

the null hypothesis (respectively, the alternative hypothesis). However, we will refrain from using such terminology,
and the two hypotheses will be considered to have an equal stature.
Given n i.i.d. observations Z n , a (possibly randomized) detector

φ : Z n → H, H ,

(2)



def
p1 (φ) = P φ(Z n ) = H ,

(3)

has type 1 and type 2 error probabilities9 given by

and

def

p2 (φ) = P [φ(Z n ) = H] .

(4)

The family of detectors which optimally trades between the two types of error probabilities is given by the NeymanPearson lemma [1, Prop. II.D.1], [3, Th. 11.7.1] by10

9


def 
φ∗n,T (z n ) = I P (z n ) ≤ enT · P (z n ) ,

(5)

Also called the false-alarm probability and misdetection probability in engineering applications.
Since the two hypotheses are assumed to be discrete, randomized tie-breaking should be used if a given constraint on one of the error
probabilities should be matched exactly. Nonetheless, this randomization has no effect on the exponential behavior, which is the focus of
this paper (in the distributed scenario). Thus, we will not dwell on randomized detectors too much in what follows.
10

8

where T ∈ R is a threshold parameter. This parameter controls the trade-off between the probability of the two
types of error - the larger T is, the type 1 error probability increases and the type 2 error probability decreases,
and vice-versa.
To describe bounds on the error probabilities of the optimal detector, let us define the hypothesis-testing reliability
function [2, Section II] as
def

D2 (D1 ; P, P ) =

min

Q: D(Q||P )≤D1

D(Q||P ).

(6)

For brevity, we shall omit the dependence on P, P as they remain fixed and can be understood from context. As
is well known [2, Th. 3], for a given D1 ∈ (0, D(P ||P )), there exists a proper choice of T such that
p1 (φ∗n.T ) ≤ exp(−n · D1 ),

(7)

p2 (φ∗n.T ) ≤ exp [−n · D2 (D1 )] .

(8)

Furthermore, it is also known that this exponential behavior is optimal [2, Corollary 2], in the sense that if
1
lim inf − log p1 (φ∗n,T ) ≥ D1
n→∞
n

(9)

1
lim sup − log p2 (φ∗n,T ) ≤ D2 (D1 ).
n
n→∞

(10)

then

It should be noted, however, that the detector (5) and the bounds on its error probability (7)-(8) are exactly optimal
for any given n. In fact, in what follows, we will use these relations for n = 1.
The function D2 (D1 ) is known to be a convex function of D1 , continuous on (0, ∞) and strictly decreasing prior
to any interval on which it is constant [2, Th. 3]. Furthermore, it is known [2, Th. 7] that it can be represented as
D2 (D1 ) = sup {−τ · D1 + (τ + 1) · dτ } ,

(11)

τ ≥0

where
def

dτ = − log

"

X

z∈Z

P

τ/τ +1

(z)P

1/τ +1

#

(z) ,

(12)

is the Chernoff distance between distributions. The representation (11) will be used in the sequel to derive bounds
on the reliability of DHT systems.

C. Distributed Hypothesis-Testing
Let {(Xi , Yi )}ni=1 be n independent copies of a pair of random variables (X, Y ) ∈ (X , Y), where X and Y are
finite alphabets. Under H , the joint distribution of (X, Y ) is given by PXY , whereas under H , this distribution is
given by P XY . We assume that both probability measures are absolutely continuous with respect to one another,

9

xn

encoder

detector

010 : : :

fn (xn )

H=H̄

'n (fn (xn ); y n )

yn
PXY =P̄XY
Figure 2. A DHT system.

i.e., PXY ≫ P XY , as well as PXY ≪ P XY ,11 and thus it can be assumed without loss of generality (w.l.o.g.) that
supp(PX ) = supp(P X ) = X and supp(PY ) = supp(P Y ) = Y . For brevity, we denote the probability of an event
A under H (respectively, H ) by P (A) [respectively, P (A)].
def

A DHT system Hn = (fn , ϕn ), as depicted in Fig. 2, is defined by an encoder
fn : X n → [mn ],

(13)

which maps a source vector into an index i = fn (xn ), and a detector (possibly randomized12)
ϕn : [mn ] × Y n → {H, H}.

(14)

The inverse image of fn for i ∈ [mn ], i.e.,
def

fn−1 (i) = {xn ∈ X n : fn (xn ) = i} ,

is called the bin associated with index i. The rate of Hn is defined as
Hn is defined as

1
n

(15)

log mn , the type 1 error probability of



def
p1 (Hn ) = P ϕn (fn (X n ), Y n ) = H ,

(16)

and the type 2 error probability is defined as

def

p2 (Hn ) = P [ϕn (fn (X n ), Y n ) = H] .

(17)

In the sequel, conditional error probabilities given an event A will be abbreviated as, e.g.,

11



def
p1 (Hn |A) = P ϕn (fn (X n ), Y n ) = H|A .

(18)

This implies that both types of Stein’s exponent for this problem are finite.
Randomized encoding can also be defined. In this case, the encoder takes the form fn : X n → S([mn ]), where fn (xn ) is a probability
vector whose ith entry is the probability of mapping xn to the index i ∈ [mn ]. In the sequel, we will also use a rather simple form of
randomized encoding, which does not require this general definition. There, the source vector xn will be used to randomly generate a new
source vector X̃ n , and the latter will be encoded by a deterministic encoder (see the proof of the achievability part of Theorem 6 in Appendix
B-A).
12

10
def

A sequence of DHT systems will be denoted by H = {Hn }n≥1 . The sequence H is associated with two different
exponents for each of the two probabilities defined above. The infimum type 1 exponent of a sequence of systems
H is defined by

1
lim inf − log p1 (Hn ),
n→∞
n

(19)

and the supremum type 1 exponent is defined by
1
lim sup − log p1 (Hn ).
n
n→∞

(20)

Analogous exponents can be defined for the type 2 error probability.
The reliability function of a DHT system is the optimal trade-off between the two types of exponents achieved
by any encoder-detector pair of a given rate R. Specifically, the infimum DHT reliability function is defined by


1
def
nR
−n·E1
−
,
(21)
E2 (R, E1 ; PXY , P XY ) = sup lim inf − log p2 (Hn ) : ∀n, mn ≤ e , p1 (Hn ) ≤ e
n→∞
n
H
and the supremum DHT reliability function E2+ (R, E1 ; PXY , P XY ) is analogously defined, albeit with a lim sup.
For brevity, the dependence on PY |X , P Y |X will be omitted henceforth whenever it is understood from context.
III. M AIN R ESULT: B OUNDS

ON

T HE R ELIABILITY F UNCTION

OF

DHT

To begin the discussion on the reliability function of DHT systems, we note that for a given encoder fn , the
form of the optimal detector is just a comparison of likelihoods, as in ordinary HT. Indeed, it readily follows from
(5) that the optimal detector has the form

P
P

n n
nT ·
n n
H
xn : fn (xn )=i P XY (x , y )
xn : fn (xn )=i PXY (x , y ) < e
n def
∗
ϕn,T (i, y ) =

H otherwise

(22)

for some T ∈ R which sets the trade-off between the two error probabilities.

Hence, the characterization of the DHT reliability function is reduced to finding optimal encoders, to wit,
a partition of the alphabet X n into bins, and then, for a given sequence of optimal encoders, finding singleletter expressions for the resulting error exponents, under optimal detection (22). These problems are much more
challenging then the characterization of the optimal detector. Nonetheless, just like in distributed compression and
channel coding problems mentioned in the introduction, achievability bounds can be derived using random-coding
ensembles. Specifically, the main result of this paper, which we next describe, is a random-coding bound and an
expurgated bound, obtained under an optimal Neyman-Pearson detector. Before that, we state the trivial converse
bound, obtained when X n is not compressed, or alternatively, when R = log|X | (immediately deduced from the
discussion in Section II-B).

11

Proposition 1. The supremum DHT reliability function is bounded as
E2+ (R, E1 ; PXY , P XY ) ≤

min

QXY :D(QXY ||PXY )≤E1

D(QXY ||P XY ).

(23)

To state our achievability bound, we will need several additional notations. We denote the Chernoff distance
between symbols by
def

dτ (x, x̃) = − log

τ/τ +1

1/τ +1

X

PY |X (y|x)P Y |X (y|x̃),

def

1X
dτ (xi , x̃i ).
n

(24)

y∈Y

and between vectors by
dτ (xn , x̃n ) =

n

(25)

i=1

Further, when (X, X̃) are distributed according to QX X̃ we define the average Chernoff distance as
h
i
def
dτ (QX X̃ ) = EQ dτ (X, X̃) ,

(26)

and when X is distributed according to QX , we denote, for brevity,
def

dτ (QX ) = EQ [dτ (X, X)] .

(27)

Next, we denote
′
Brc
(R, Rb , QU X , τ )
def

=

min
(QU XY ,QU XY ):QU X =QU X , QY =QY

(

τ · D(QY |U X ||PY |X |QU X ) + D(QY |U X ||P Y |X |QU X )


+ max |IQ (U ; Y ) − Rb |+ , IQ (U, X; Y ) − H(QX ) + R

)
+ τ · max IQ (U ; Y ) − Rb , IQ (U, X; Y ) − H(QX ) + R
,
+

(28)

and
′′
Brc
(R, Rb , QU X , τ )
def

=

min
(QU XY ,QU XY ):QU X =QU X , QU Y =QU Y , IQ (U ;Y )>Rb

+ |IQ (X; Y |U ) − H(QX ) + R + Rb |+
+ τ · IQ (X; Y |U ) − H(QX ) + R + Rb

+

(

τ · D(QY |U X ||PY |X |QU X ) + D(QY |U X ||P Y |X |QU X )

)

,

(29)

as well as
 ′
def
′′
Brc (R, Rb , QU X , τ ) = min Brc
(R, Rb , QU X , τ ), Brc
(R, Rb , QU X , τ ) ,

(30)

12

which are all related to a random-coding based bound on the reliability function. We also denote
def

Bex (R, QX , τ ) = (τ + 1) ·

min
QX X̃ : QX =QX̃ , HQ (X|X̃)≥R

n

o
dτ (QX X̃ ) + R − HQ (X|X̃) ,

which is related to an expurgated based bound on the reliability function. Finally, we also denote
)
(
def

B(R, QX , τ ) = max

sup

sup

QU |X Rb : Rb ≥|IQ (U ;X)−R|+

Brc (R, Rb , QU X , τ ), Bex (R, QX , τ ) .

(31)

(32)

For brevity, arguments such as (R, Rb , QU X , τ ) will sometimes be omitted henceforth.
Theorem 2. The infimum DHT reliability function bounded as
E2− (R, E1 ; PXY , P XY )
"

#
o
≥ min sup − τ · E1 + D(QX ||P X ) + τ · D(QX ||PX ) + min (τ + 1) · dτ (QX ), B(R, QX , τ ) . (33)
n

QX τ ≥0

As hinted by (32), the best of a random-coding bound and an expurgated bound can be chosen for any given
input type QX . In the case of a random-coding bound, the achieving scheme is based on quantization and binning.
In this respect, for such QX (with H(QX ) > R), the conditional type QU |X is the test channel for quantizing
.
|Tn (QX )|= enH(QX ) source vectors into one of enRq possible reproduction vectors, where the quantization rate Rq

satisfies Rq > R. Then, these reproduction vectors are grouped to bins of size (at most) enRb each, the binning
rate Rb satisfies Rb = Rq − R. Both QU |X and Rb may be optimized, separately for any given QX , to obtain the
best type 2 exponent. In case the expurgated bound is better than the random-coding bound for QX , the scheme
which achieves it is based on binning at rate Rb = |H(QX ) − R|+ , without quantization.
We next discuss several implications of Theorem 2. First, simpler bounds, perhaps at the cost of worse exponents,
can be obtained by considering two extermal choices. To obtain a binning-based scheme, without quantization, we
choose U to be a degenerated random variable (deterministic, i.e., |U |= 1) and Rb = H(QX ) − R. We then get

′ dominates the minimization in (30), and
that Brc

Brc (R, H(QX ) − R, QU X , τ ) = Brc,b (R, QX , τ )
def

=

min
(QXY ,QXY ):QX =QX , QY =QY

(34)
(

τ · D(QY |X ||PY |X |QX ) + D(QY |X ||P Y |X |QX )

+ |R − HQ (X|Y )|+ + τ · R − HQ (X|Y )

+

)

.

(35)

To obtain a quantization-based scheme, without binning, we choose Rb = 0, and limit QU |X to satisfy R ≥
IQ (U ; X).

Second, if the rate is large enough then no loss is expected in the reliability function of DHT. We can deduce
from Theorem 2 an upper bound on this no-loss rate, as follows.

13

Corollary 3. Suppose that R is sufficiently large such that
B(R, QX , τ ) ≥ dτ (QX )

(36)

E2− (R, E1 ) = E2− (∞, E1 )

(37)

for all QX ∈ S(X ) and τ ≥ 0. Then,

= D2 (E1 ).

(38)

The proof of this corollary appears in Appendix A.
Third, by setting E1 = 0, Theorem 2 yields an achievable bound on Stein’s exponent, as follows.
Corollary 4. Stein’s exponent is bounded as
E2− (R, 0)
≥ D(PX ||P X ) + sup min {(τ + 1) · dτ (PX ), B(R, PX , τ )}
τ ≥0



≥ min D(PXY ||PX × P Y |X ), D(PX ||P X ) + sup
sup

QU |X R : R ≥ I

b
b
PX ×QU |X (U ;X)−R

+

(39)



lim Brc (R, Rb , PX × QU |X , τ ) .
τ →∞


(40)

The first term in (40) can be identified as Stein’s exponent when the rate is not constrained at all. The proof of
this corollary also appears in Appendix A, and it seems that no further significant simplifications are possible. It
is worth to note, however, that the resulting bound is quite different from the best known bound by Shimokawa,
Han and Amari [10, Th. 4.3], [13] (and its refinement in [32], [33]).
Fourth, it is interesting to examine the case R = 0. Using analysis similar to the proof of Corollary 4, it is easy
to verify that using a binning-based scheme [i.e., substituting (35) in (33) for B(R, QX , τ )] achieves the lower
bound
E2− (R = 0, E1 ) ≥

min
(QXY ,QXY ):QX =QX , QY =QY , D(QXY ||PXY )≤E1

D(QXY ||P XY ).

(41)

As expected, this is the same type 2 error exponent obtained when y n is also encoded at zero rate, as obtained
in [10, Th. 5.4], [11, Th. 6]. For this bound, a matching converse is known [10, Th. 5.5]. When E1 = 0 then
QXY = PXY , and then Stein’s exponent is given by
E2− (R = 0, E1 = 0) ≥

min
QXY :QX =PX , QY =PY

D(QXY ||P XY ).

(42)

In [15, Th. 2] it was determined that this exponent is optimal (even when y n is not encoded and given as sideinformation to the detector).
The rest of the paper is mainly devoted to the proof of Theorem 2, and is based on the following methodology,
comprised of two steps. We will introduce CD codes, which, in a nutshell, correspond to a single bin of a DHT

14

system. The first step of the proof is the reduction of the DHT reliability problem to the CD reliability problem
which will be considered in Section IV. The second step is derivation of single-letter achievable bounds on the
reliability of CD codes, and this will be considered in Section V. The bound of Theorem 2 on the DHT reliability
function then follow as easy corollary to these results.
IV. F ROM D ISTRIBUTED H YPOTHESIS -T ESTING

TO

C HANNEL -D ETECTION C ODES

In this section, we formulate CD codes, and then use them to characterize the reliability of DHT systems. CD
codes were considered in [42] for the problem of joint detection and decoding. For this purpose, the code has to
be chosen to allow the receiver to detect the channel conditional probability, as well as for transmitting messages,
just like an ordinary channel code. In this paper, each quantization cell of a DHT system will be considered and
analyzed as a CD code. Since a DHT system is only required to decide on the hypothesis but not on the actual
source vector, the error probability of CD codes (for transmitting messages) is irrelevant in this paper. However,
this does not imply that all the codewords of CD code can be chosen to be identical (which is optimal in terms
of detection performance), since by definition, the members of a quantization cell are different from one another.
Hence, in what follows we will define CD codes of a given cardinality, and enforce their codewords to be different
from one another. Here too, for brevity, we will denote the probability of an event A under H and H by P (A) and
P (A), respectively. The required definitions for CD codes are quite similar to the ones required for DHT systems,

but as some differences do exist, we explicitly outline them in what follows.
A CD code for a type class QX ∈ Pn (X ) is given by Cn ⊆ Tn (QX ) (where all codewords must be different). An

input X n ∈ Cn to the channel is chosen with a uniform distribution over Cn , and sent over n uses of a DMC which

may be either PY |X when H is active or P Y |X when H is. The random channel output is given by Y n ∈ Y n . The
detector has to decide based on y n whether the DMC conditional probability distribution is PY |X or P Y |X . As for

the DHT problem, we assume that PY |X ≪ P Y |X and PY |X ≫ P Y |X . A detector (possibly randomized) for Cn is
given by
φn : Y n → {H, H}.

(43)

In accordance, two error probabilities can be defined, to wit, the type 1 error probability

and the type 2 error probability



def
p1 (Cn , φn ) = P φn (Y n ) = H ,
def

p2 (Cn , φn ) = P [φn (Y n ) = H] .

As for the DHT problem, the Neyman-Pearson lemma implies that the optimal detector is given by
)
(
X
X
n n
n n
nT
∗
n def
P Y |X (y |x ) ,
PY |X (y |x ) < e ·
φn,T (y ) = I
xn ∈Cn

xn ∈Cn

(44)

(45)

(46)

15

for some threshold T ∈ R.

Let QX ∈ P(X ) be a given type, and let {nl }∞
l=1 be the subsequence of blocklengths such that Pn (QX ) is
def

not empty. As for a DHT sequence of systems H, a sequence of CD codes C = {Cnl }∞
l=1 is associated with two
exponents. The infimum type 1 exponent of a sequence of codes C and detector {φnl }∞
l=1 is defined as
lim inf −
l→∞

1
log p1 (Cnl , φnl ),
nl

(47)

and the supremum type 1 exponent is similarly defined, albeit with a lim sup. Analogous exponents are defined
for the type 2 error probability. In the sequel, we will construct DHT systems whose bins are good CD codes, for
each QX ∈ P(X ). Since to obtain an achievability bound for a DHT system, good performance of CD codes of
all types of the source vectors will be simultaneously required, the blocklengths of the components CD codes must
match. Thus, the limit inferior definition of exponents must be used, as it assures convergence for all sufficiently
large blocklength. For the converse bound, we will use the limit superior definition.
For a given type QX ∈ P(X ), rate ρ ∈ [0, H(QX )), and type 1 constraint F1 > 0, we define the infimum CD
reliability function as
F2− (ρ, QX , F1 ; PY |X , P Y |X )


1
def
nl ρ
−nl ·F1
lim inf − log p2 (Cnl , φnl ) : ∀l, Cnl ⊆ Tnl (QX ), |Cnl |≥ e , p1 (Cnl , φnl ) ≤ e
=
sup
, (48)
l→∞
nl
C,{φnl }∞
l=1

and the supremum CD reliability function F2+ (ρ, QX , F1 ; PY |X , P Y |X ) is analogously defined, albeit with a lim sup.
For brevity, the dependence on PY |X , P Y |X will be omitted whenever it is understood from context. Thus, the only
difference in the reliability function of CD codes from ordinary HT, is that in CD codes the distributions are
to be optimally designed under the rate constraint |Cn |≥ enρ . Indeed, for |Cn |= 1 symmetry implies that any

xn ∈ Tn (QX ) is an optimal CD code. The detector in this case has no ambiguity regarding the transmitted symbol

at any given time point. This, however, does not hold when |Cn |> 1, and ambiguity exists at at least a single time
point. This additional uncertainty complicates the operation of the detector, and reduces the reliability function.
Basic properties of F2± (ρ, QX , F1 ) are given as follows.
Proposition 5. As a function of F1 , F2± (ρ, QX , F1 ) are non-increasing and have both limit from the right and from
the left at every point. They have no discontinuities of the second kind and the set of first kind discontinuities (i.e.,
jump discontinuity points) is at most countable. Similar properties hold as a function of ρ ∈ [0, H(QX ))
Proof: It follows from their definition that F2± (ρ, QX , F1 ) are non-increasing in F1 . The continuity statements
follow from properties of monotonic functions [45, Th. 4.29 and its Corollary, Th. 4.30] (Darboux-Froda’s theorem).

With the above, we can state the main result of this section, which is a characterization of the reliability of DHT
systems using the reliability of CD codes.

16

Theorem 6. The DHT reliability functions E2± (R, E1 ) satisfy:
•

Achievability part:
E2− (R, E1 ) ≥ lim


D(QX ||P X ) + F2− (H(QX ) − R, QX , E1 − D(QX ||PX ) + δ) .

(49)


D(QX ||P X ) + F2+ (H(QX ) − R + δ, QX , E1 − D(QX ||PX ) − δ) .

(50)

inf

δ↓0 QX ∈P(X )

•

Converse part:
E2+ (R, E1 ) ≤ lim

inf

δ↓0 QX ∈P(X )

The achievability and converse part match up to two discrepancies. First, in the achievability (respectively,
converse) part the infimum (supremum) reliability function appears. This seems unavoidable, as it is not known
if the infimum and supremum reliability functions are equal even for ordinary channel codes [4, Problem 10.7].
Second, the bounds include left and right limits of E2+ (R, E1 ) at rate R and exponent E1 . Nonetheless, due
to monotonicity, E2+ (R, E1 ) is continuous function of R and E1 for all rates and exponents, perhaps excluding
a countable set (Proposition 5). Thus, for any given (R, E1 ) there exists an arbitrarily close (R̃, Ẽ1 ) such that
Theorem 6 holds with δ = 0.
The proof of Theorem 6 appears in Appendix B. The achievability part (Appendix B-A) is proved by first
constructing a DHT system for source vectors from a a single type class of the source. The bins are generated by
permutations of a “good” CD code. The fact that the two hypotheses are memoryless implies that bins generated
this way have approximately the same exponents as the original CD code. Furthermore, since type classes are
closed under permutations, they can be covered using permutations of a CD code. A covering lemma by Ahlswede
[41, Section 6, Covering Lemma 2] shows that in fact such covering method can be effective, in the sense that
the required number of permutations is close to minimal number possible (up to the first order in the exponent).
This allows to prove that the encoding rate is as required. Ideas from this spirit were used for the DHT problem
in [7], as well as for distributed compression [39], [40], and secure lossy compression [46]. Afterwards, all types
of the source are considered simultaneously to generate a DHT system for any possible type of the source vector.
This requires proving the uniform convergence of the error probabilities to their asymptotic exponential behavior,
uniformly over all possible types.
The proof of the converse part (Appendix B-B) is based upon identifying a sequence of bins whose size and
conditional exponents are close to typical values of the entire DHT system. Such a bin corresponds to a CD code,
and thus clearly cannot have better exponents than the ones dictated by the reliability function of CD codes. This
restriction is then translated back to bound the reliability of DHT systems.
This theorem parallels a similar result of [39], [40] for the reliability functions of distributed compression.
By analogy, the reliability function of distributed compression can be characterized by the reliability function of
ordinary channel codes (see Fig. 1). The latter can be bounded using well-known classic bounds, such as the
random-coding and expurgated achievability bounds, and the sphere-packing, zero-rate, and straight-line converse

17

bounds [4, Ch. 10]. The characterization of Theorem 6 articulates the fact that the reliability of DHT systems is
directly connected to the problem of determining the reliability of CD codes. However, even this apparently simpler
problem is challenging to solve exactly, and just as in the case of ordinary channel coding, perhaps only lower and
upper bounds are at reach. Hence, even though DHT is a source coding problem in nature, for the such reliability
functions are known (e.g., Marton’s exponent [47]), Theorem 6 reveals that the reliability of DHT systems depends
on the reliability of a channel coding problem, for the such optimal exponents are typically not entirely known,
even for the most basic settings. This might manifest the intrinsic difficulty of the DHT problem. Nonetheless, in
the next section, we derive concrete bounds on the reliability of CD codes, which, using Theorem 6, lead directly
to bounds on the reliability of the DHT problem of Theorem 2.
V. B OUNDS

ON THE

R ELIABILITY

OF

CD C ODES

In the previous section, we have shown that the reliability function of DHT can be directly obtained by the
reliability of CD codes. In this section, we derive bounds on the latter, using random-coding arguments. A naive
approach would be to randomly draw the codewords independently from some distribution. However, as discussed in
the introduction, the best known achievable bounds for DHT systems are obtained using quantization-and-binningbased schemes. As CD codes correspond to a single bin of a DHT system,13 it follows that CD codes can also
benefit from adding dependence between the randomly drawn codewords. In more detail, a bin of a DHT system
which was constructed by the quantization-and-binning method corresponds to a superposition code. To wit, it will
contain a set of reproduction vectors which are sufficiently different from one another, so that the side-information
vector y n enables to decide on the true reproduction vector with high reliability, and each reproduction vector is
surrounded by a quantization cell, which correspond to all source vectors which are mapped to it in the quantization
process. The quantization cell should be sufficiently “small”, such that as long as the detector correctly decodes
the reproduction vector, the detection reliability given the reproduction vector is close to the detection reliability
given the true vector. A CD code which corresponds to a binning-based scheme will contain source vectors which
correspond to a good channel code for the channels PY |X and P Y |X , so that the side-information vector y n can be
used to decode the true vector with high reliability. A CD code which corresponds to a quantization-based scheme
will look like a quantization cell of a single reproduction vector. The various types of CD codes are depicted in
Fig. 3.
Since a single bin of a quantization-and-binning DHT system corresponds to a superposition code, it should be
drawn from an hierarchical ensemble, which we next define:
Definition 7. A fixed-composition hierarchical ensemble for a type QX ∈ Pn (X ) and rate ρ is defined by a
conditional type QU |X ∈ Pn (U , QX ), where U is an auxiliary random variable from a finite alphabet U , a cloudcenter rate ρc , and a satellite rate ρs such that ρ = ρc + ρs . A codebook Cn from this ensemble is drawn in
13
Strictly speaking, this is true only when the type of the source vectors is constant within each bin. Since sending the type class of the
source vector requires negligible rate, it can be assumed w.l.o.g. that this is indeed the case, as otherwise, one can further partition the bin
into type-classes.

18

Quantization and Binning

Quantization

Binning

Figure 3. An illustration of various types of CD codes which pertain to a bin of a DHT system. The grey dots within the large circle represent
the members of Tn (QX ). In a quantization based scheme, a bin corresponds to a single reproduction cell of the quantization scheme, and
thus all the codewords of the CD code share a common “center” (reproduction vector). In a binning-based scheme, the codewords of the CD
code are scattered over the type class with no particular structure. In a quantization-and-binning scheme, the codewords are partitioned to
“distant” clouds, where the black dots within one of the small circles represent the satellite codebook pertaining to one of the cloud centers.

two stages. First, enρc cloud centers Cc,n are drawn, independently and uniformly over Tn (QU ). Second, for each
of the cloud centers un ∈ Cc,n , enρs satellites are drawn independently and uniformly over Tn (QX|U , un ). When

considered a random entity, the codebook will be denoted by Cn .
Evidently, codewords which pertain to the same cloud are dependent, whereas codewords from different clouds
are independent. Further, the ordinary ensemble, in which each codeword is drawn uniformly over Tn (QX ),
independently of all other codewords, can be obtained as a special case by choosing U = X and ρc = ρ. On
the other hand, when ρs = ρ, then a single14 cloud center is drawn, and all codewords are satellites of this center.
This corresponds to the bin of a DHT system which is based only on quantization, without binning. More generally,
for source vectors of type QX , a quantization-and-binning scheme of rate R, binning rate Rb , and quantization
rate Rq = R + Rb , leads to CD codes of rate ρ = H(QX ) − R, cloud-center rate ρc = Rb and satellite rate
ρs = H(QX ) − Rq . When used for a DHT system, the cloud centers Cc,n are the reproduction vectors. The joint

distribution of any source vector and its reproduction vector is exactly QU X , and the choice of the test channel
QU |X is used to control the distortion of the quantization.15
def

In this section, it will be more convenient to use the parameter λ =

1
τ +1

(so that τ =

1−λ
λ ).

Using this convention,

we will use, e.g., dλ instead of dτ for the Chernoff distance. Note also that λ ∈ [0, 1].
To state a random-coding bound on the reliability of CD codes, we denote
A′rc (ρ, ρc , QU X , λ)
def

=

min
(QU XY ,QU XY ):QU |X =QU |X , QY =QY

14



(1 − λ) · D(QY |U X ||PY |X |QU X ) + λ · D(QY |U X ||P Y |X |QU X ),

Or a sub-exponential number of cloud centers.
Usually in rate-distortion theory, the test channel is used to control the average distortion EQ [d(X, U )] for some additive distortion
measure d : X × U → R+ . Here, xn is always chosen from Tn (QX|U , un ) and therefore the distortion between un and xn is constant
depending on QU X .
15

19


+ λ · max |IQ (U ; Y ) − ρc |+ , IQ (U, X; Y ) − ρ + (1 − λ) · max



IQ (U ; Y ) − ρc

+

, IQ (U, X; Y ) − ρ



,

(51)

and
A′′rc (ρ, ρc , QU X , λ)
def

=

min
(QU XY ,QU XY ):QU |X =QU |X , QU Y =QU Y , IQ (U ;Y )>ρc



(1 − λ) · D(QY |U X ||PY |X |QU X ) + λ · D(QY |U X ||P Y |X |QU X ),

+ λ · |IQ (X; Y |U ) − ρ + ρc |+ + (1 − λ) · IQ (X; Y |U ) − ρ + ρc

+



,

(52)

as well as

def
Arc (ρ, ρc , QU X , λ) = min A′rc (ρ, ρc , QU X , λ), A′′rc (ρ, ρc , QU X , λ) .

(53)

For brevity, when can be understood from context, the dependency on (ρ, ρc , QU X , λ) will be omitted. Our randomcoding bound is as follows.
Theorem 8. The infimum CD reliability function is bounded as
(
"
#)
1−λ
1
−
F2 (ρ, QX , F1 ) ≥ max −
· F1 + · min dλ (QX ), sup
Arc (ρ, ρc , QU X , λ)
.
sup
0≤λ≤1
λ
λ
QU |X ρc : ρc ≥|ρ−HQ (X|U )|+
(54)
The proof of Theorem 8 appears entirely in Appendix C, and here we provide a brief outline. The main idea of
the proof is that when a CD code is used, the output distribution under H is given by the induced distribution
(C )

def

PY nn (y n ) =

1 X
PY |X (y n |xn ).
|Cn | n

(55)

x ∈Cn

(C )

(Cn )

(C )

(Cn )

Based on the output vector y n , the detector should distinguish between two distributions PY nn and P Y n [the
latter defined similarly to (55)]. This corresponds to an ordinary HT problem between the PY nn and P Y n , and
therefore the exponents of this HT problem are simply given by (7) and (8) (when letting Z = Y n ). In turn, using
(C )

the characterization (11), the reliability function can be expressed using the Chernoff distance between PY nn and
(Cn )

P Y n . As the CD code which maximizes this Chernoff distance is difficult to find, we turn to a random-coding

approach, and evaluate its ensemble average, namely


 X h
i1−λ h
iλ 
(Cn )
(C )
PY nn (y n )
· P Y n (y n )
E
.
 n n


(56)

y ∈Y

In the same spirit, we will evaluate the number of unique codewords of a randomly chosen CD code. In fact, we will
show that under proper conditions, it is asymptotically equal to the number of drawn codewords, i.e., enρ . Then, a
sequence of codebooks, such that each codebook has effectively enρ unique codewords, and the Chernoff distance

is typical to the ensemble average will be considered. For this sequence, it will then be shown that removing

20

duplicates, i.e., keeping only a single instance of codewords which were drawn more than once (thus making
it a valid CD code), may only cause a negligible loss in the achieved exponent. This will prove a single-letter
random-coding bound on the reliability function.
We make the following comments:
1) Loosely speaking, in (53), the exponent A′rc corresponds to the contribution to the error probability from
codewords which belong to different cloud centers, whereas the exponent A′′rc corresponds to the contribution
to the error probability from codewords which belong to the same cloud center as the transmitted codeword.
Thus, for a given rate ρ, A′rc is monotonically non-increasing with ρc , while A′′rc is monotonically nondecreasing with ρc (or, monotonically non-increasing with ρs ). The cloud-center rate ρc and the test channel
QU |X therefore should be chosen to optimally balance between these two contributions to the error probability.

2) For a given QU |X , the random-coding analysis of the ensemble average of the Chernoff distance is based on the
type-enumeration method [48, Sec. 6.3], which leads to ensemble-tight bounds in many problems. While we
cannot rigorously claim ensemble-tightness here, our analysis still avoids any use of bounds such as Jensen’s
inequality. Thus, we conjecture that our bounds are ensemble-tight, and cannot be improved.
3) In comparison to [42], we have generalized the random-coding analysis of the detection error exponents to
hierarchical ensembles, and also obtained simpler expressions using the ensemble average of the exponent of
the Chernoff distance.
4) In fact, a stronger claim than the one appears in Theorem 8 can be made. It can be shown that there exists a
single sequence of CD codes {Cn∗l }∞
l=1 such that
lim inf −
l→∞

1
log
min
p2 (Cn∗ l , φ∗nl ,T )
nl
T : p1 (Cn∗ l ,φ∗nl ,T )≤e−nF1
(
#)
"
1−λ
1
≥ max −
, (57)
Arc
· F1 + · min dλ (QX ), sup
sup
0≤λ≤1
λ
λ
QU |X ρc : ρc ≥[ρ−HQ (X|U )]+

simultaneously for all F1 . Thus, when using such a CD code, the operating point along the trade-off curve
between the two exponents can be determined solely by the detector, and can be arbitrarily changed from
block to block. For details regarding the proof of this claim, see Remark 18.
Next, we state our expurgated exponent, and to this end we denote
def

Aex (ρ, QX , λ) =

min
QX X̃ : QX =QX̃ , IQ (X;X̃)≤ρ

n

o
dλ (QX X̃ ) + IQ (X; X̃) − ρ .

Theorem 9. The infimum CD reliability function is bounded as


1
1−λ
−
· F1 + · min {dλ (QX ), Aex (ρ, QX , λ)} .
F2 (ρ, QX , F1 ) ≤ max −
0≤λ≤1
λ
λ

(58)

(59)

Proof of Theorem 9: As was shown in [42, Appendix E], for any δ > 0 and all n sufficiently large, there

21

exists a CD code Cn∗ (of rate ρ) such that
i1−λ h
iλ
X h (C ∗ )
(C ∗ )
n
n
PY n (y )
P Y nn (y n ) ≤ exp [−n · min {dλ (QX ), Aex (ρ, QX , λ)}] .

(60)

y n ∈Y n

Substituting this bound to the characterization (11), taking n → ∞ and δ ↓ 0 completes the proof of the theorem.
We conclude with two comments:
1) A similar expurgated bound can be derived for hierarchical ensembles. However, when optimizing the rates
(ρs , ρc ) for this expurgated bound, it turns out that choosing ρs = 0 is optimal. Thus, the resulting bound

exactly equals the bound of Theorem 9, which corresponds to an ordinary ensemble.
2) Since the expurgated exponent only improves the random-coding exponent of the ordinary ensemble (which
is inferior in performance to the hierarchical ensemble), it is anticipated that expurgation does not play a
significant role in this problem, compared to the channel coding problem. This might be due to the fact that
the aim of expurgation is to remove codewords which have “close” neighbors, while this is not actually required
in the DHT problem. This can also be attributed to the bounding technique of the expurgated bound, which
is based on pairwise Chernoff distances.
After deriving the bounds on the reliability of CD codes, we return to the DHT problem, and conclude the section
with a short proof of Theorem 2.
Proof: Up to the arbitrariness of δ > 0, in Theorem 6 we have obtained
E2− (R, E1 ) =

inf

QX ∈P(X )



D(QX ||P X ) + F2− (H(QX ) − R, QX , E1 − D(QX ||PX )) .

(61)

Further, the random-coding bound of Theorem 8 and the expurgated bound of Theorem 9 both imply that
F2− (H(QX ) − R, QX , E1 − D(QX ||PX ))
(
"
1−λ
1−λ
· E1 +
· D(QX ||PX )
≥ max max −
0≤λ≤1
λ
λ
)#
(
1
+ · min dλ (QX ), sup
Arc (H(QX ) − R, Rb , QU X , λ)
,
sup
λ
QU |X Rb : Rb ≥|IQ (U ;X)−R|+
"
1−λ
1−λ
max −
· E1 +
· D(QX ||PX )+
0≤λ≤1
λ
λ
#)
1
+ · min {dλ (QX ), Aex (H(QX ) − R, QX , λ)}
λ
(
1−λ
1−λ
max −
= sup
sup
· E1 +
· D(QX ||PX )
λ
λ
QU |X Rb : Rb ≥|IQ (U ;X)−R|+ 0≤λ≤1

)
1
.
+ · min dλ (QX ), max {Arc (H(QX ) − R, Rb , QU X , λ) , Aex (H(QX ) − R, QX , λ)}
λ

(62)

(63)

22
def 1−λ
λ

The bound of Theorem 2 is obtained by substituting in (63) in (61), while changing variables from λ to τ =
and from ρc to Rb , as well as using the definitions of Brc (30) and Bex (31) and B (32).
VI. C OMPUTATIONAL A SPECTS

AND A

N UMERICAL E XAMPLE

The bound of Theorem 2 is rather involved, and therefore it is of interest to discuss how to compute it efficiently.
′ and B ′′ for a given (R, R , Q
Evidently, the main computational task is the computation of Brc
U X , τ ). To this end,
b
rc
′ and B ′′ are strictly convex functions of (Q
it can be seen that the objective functions of both Brc
Y |U X , QY |U X ) (as
rc
′ is a convex set (only has linear constraints)
PY |X ≪≫ P Y |X was assumed).16 Furthermore, the feasible set of Brc

′ is a convex optimization problem, which can be solved efficiently [49]. However,
and thus the computation of Brc
′′ is not convex, due to the additional constraint I (U ; Y ) > R beyond the linear constraints.
the feasible set of Brc
Q
b

Nevertheless, the value of Brc can be computed efficiently, by solving only convex optimization problems, in the
following algorithm:
′ , and let the optimal value be v ′ .
1) Solve the optimization problem (28) defining Brc
′′ , but without the constraint I (U ; Y ) > R (this is a convex
2) Solve the optimization problem (29) defining Brc
Q
b
∗

optimization problem). Let the solution be (Q∗U XY , QU XY ) and the optimal value be v ′′ . If IQ∗ (U ; Y ) > Rb
′′ = v ′′ , and otherwise, set B ′′ = ∞.
then set Brc
rc

3) The result is Brc = min{v ′ , v ′′ }.

This algorithm is correct due to the following argument. It is easily verified that if IQ∗ (U ; Y ) > Rb then the
′′ = v ′′ . However, if this
constraint IQ (U ; Y ) > Rb is inactive, and therefore can be omitted. Thus, in this case Brc

is not the case, then the solution must be on the boundary, i.e., must satisfy IQ (U ; Y ) = Rb . This is because the
′′ is a strictly convex function. In the latter case, it can be easily seen that B ′ ≤ B ′′ , and as B is
objective in Brc
rc
rc
rc

′′ = ∞ can be set. Computing B (R, Q , τ ) of (31) is a convex optimization
the minimum between the two, Brc
ex
X

problem, over QX̃|X .
Given the value of Brc , the next step is to optimize over QU |X and ρc . While this should be done exhaustively,17
any specific choice of QU |X and ρc (or a restricted optimization set for them) leads to an achievable bound on
E2− (R, E1 ). It should be mentioned, however, that it is not clear to us how to apply standard cardinality-bounding

techniques (based on the support lemma [4, p. 310]) to bound |U | in this problem. Thus, in principle, the cardinality
of U is unrestricted, improved bounds are possible.
Finally, both τ and QX should be optimized, which is feasible when X is not very large and exhausting the
simplex S(X ) in search of the minimizer QX is possible. Furthermore, as we have seen in Corollary 4, when only
Stein’s exponent is of interest, i.e., E1 = 0, the minimal value in (33) must be attained for QX = PX . Thus, there is
no need to minimize over QX ∈ S(X ), but rather only on QX = PX . We can also set τ → ∞ if the weak version
16

Indeed, the divergence terms and I(U, X; Y ) are convex in QY |U X . The term I(U ; Y ) is also convex in QY |U X , as a composition of
a linear function which maps QY |U X to QY |U and the mutual information I(U ; Y ). The pointwise maximum of two convex functions is
also a convex function (note that |f (t)|+ = max{0, f (t)}).
17
Or by any other general-purpose global optimization algorithm.

23

0.07
0.06
0.05
0.04
0.03
0.02
0.01
0
0

0.02

0.04

0.06

0.08

0.1

0.12

0.14

Figure 4. A binary example.

(40) of Corollary 4 is used as a bound. More generally, the minimizer of QX must satisfy D(QX ||PX ) ≤ E1 , and
this can decrease the size of the feasible set of QX whenever the required E1 is not very large.
A simple example for using the above methods to compute bounds on the DHT reliability function is given as
follows.
Example 10. Consider the case X = Y = {0, 1}, and PX = P X = (1/2, 1/2), where PY |X and P Y |X are binary

symmetric channels with crossover probabilities 10−1 and 10−2 , respectively. We have used an auxiliary alphabet
of size |U |= |X |+1 = 3 since this cardinality suffices for the best known bounds [13], and due to the symmetry
in the problem, we have only optimized over symmetric QU |X . Achievable bounds on the reliability of the DHT
are shown in Fig. 4 for two different rates.
VII. C ONCLUSION

AND

F URTHER R ESEARCH

In this paper, we have considered the trade-off between the two types of error exponents of a DHT system, with
full side-information. We have shown that its reliability is intimately related to the reliability of CD codes, and thus
the latter simpler problem should be considered. Achievable bounds on the reliability of CD codes were derived,
under the optimal Neyman-Pearson detector.
There are multiple directions in which our understanding of the problem can be broadened:
1) Variable-rate coding: As was noted in the past, the reliability of compression systems can be increased when
variable-rate is allowed, either with an average rate constraint [39], or under excess-rate exponent constraint
[40]. It is straightforward to use the techniques developed there to the DHT problem studied here (see also
the informal discussion in [46, Appendix]).

24

2) Computation of the bounds: As discussed in the paper, the main challenge in computing the random-coding
bound computation is the optimization over the test channel QU |X . First, deriving cardinality bounds on the
auxiliary random variable alphabet U is of interest. Second, finding an efficient algorithm to optimize the
test channel, perhaps an alternating-maximization algorithm in the spirit of the Csiszár-Tusnády [50] and the
Blahut-Arimoto algorithms [51], [52], [53], could be developed for this problem. As was noted in [16], [21], the
Stein exponent of the DHT problem of testing against independence is identical to the information bottleneck
problem [54], for which such alternating-maximization algorithm was developed.
3) Converse bounds: While we have shown that to obtain converse bounds on the reliability of DHT systems, it
suffices to obtain converse bounds on the reliability of CD codes, no concrete bounds were derived. To obtain
converse bounds which explicitly depend on the rate (in contrast to Proposition 1), two challenges are visible.
First, it is tempting to conjecture that the Chernoff characterization (11) characterizes the reliability of CD
codes, in the sense that18
F2+ (ρ, QX , F1 ; PY |X , P Y |X ) = lim sup
sup
max
n ρ
l→∞ Cnl ⊆Tnl (QX ): |Cnl |≥e l τ ≥0





i
h
i
h
1/1+τ 
τ/1+τ
X
1
(Cn )
(Cn )
, (64)
−τ · F1 − (τ + 1) · log
PY nll (y nl )
· P Y nll (y nl )


 nl nl
nl
y

∈Y

just as a similar quantity was used to derive the random-coding and expurgated bounds. Second, even if this
conjecture holds, the value of

 X h


y nl ∈Y nl


iτ/1+τ h
i1/1+τ 
(Cn )
(Cn )
PY nll (y nl )
· P Y nll (y nl )


(65)

should be lower bounded for all CD codes whose size is larger than enρ . As this term can be identified as a
Rényi divergence [55], [56], the problem of bounding its value is a Rényi divergence characterization. This
problem seems formidable, as the methods developed in [8] for the entropy characterization problem rely
heavily on the chain rule of mutual information; a property which is not naturally satisfied by Rényi entropies
and divergences. Hence, the problem of obtaining a non-trivial converse bound for the reliability of DHT
systems with general hypotheses and a positive encoding rate remains an elusive open problem.
4) Rate constraint on the side-information: The reliability of a DHT systems in which the side-information vector
y n is also encoded at a limited rate should be studied under optimal detection. Such systems will naturally lead

to multiple-access CD codes, as studied for ordinary channel coding (see [57], [58] and references therein).
However, for such a scenario, it was shown in [33] that the use of linear codes (a-la Körner-Marton coding)
dramatically improves performance. Thus, it is of interest to analyze DHT systems with both linear codes and
optimal detection. However, it is not yet known how to apply the type-enumeration method, used here for
analysis of optimal detection, to linear codes. Hence, either the type-enumeration method should be refined,
18

As usual {nl }∞
l=1 is the subsequence of blocklength such that Tn (QX ) is not empty.

25

or an alternative approach should be sought after.
5) Generalized hypotheses: Hypotheses regarding the distributions of continuous random variables, or regarding
the distributions of sources with memory can be considered. Furthermore, the case of composite hypotheses,
in which the distribution under each hypotheses is not exactly known (e.g., belongs to a subset of a given
parametric family), and finding universal detectors which operate as well as the for simple hypotheses can
also be considered. For preliminary results along this line see [15], [42].
ACKNOWLEDGMENT
Discussions with N. Merhav are acknowledged with thanks.
A PPENDIX A
P ROOFS

OF

C OROLLARIES

TO

T HEOREM 2

Proof of Corollary 3: Suppose that in the bound of Theorem 2, the inner minimization is dominated by
(τ + 1) · dτ (QX ) for all QX . Then, the bound (33) reads
E2− (R, E1 ; PXY , P XY )

≥ min sup −τ · E1 + D(QX ||P X ) + τ · D(QX ||PX ) + (τ + 1) · dτ (QX )
QX τ ≥0

(A.1)

(a)

= min sup min { − τ · E1 + D(QX ||P X ) + τ · D(QX ||PX )
QX τ ≥0 QY |X

+ τ · D(QY |X ||PY |X |QU X ) + D(QY |U X ||P Y |X |QU X )}

= min sup min −τ · E1 + D(QX ||P X ) + τ · D(QXY ||PXY ) + D(QXY ||P XY )
QX τ ≥0 QY |X

(b)


= min sup τ · [D(QXY ||PXY ) − E1 ] + D(QXY ||P XY )
QXY τ ≥0

=

min

QXY :D(QXY ||PXY )≤E1

D(QXY ||P XY ),

(A.2)
(A.3)
(A.4)
(A.5)

where (a) follows since as can be easily shown that (see (C.31) in the proof of Lemma 16 and the discussion
surrounding it)


(τ + 1) · dτ (QX ) = min τ · D(QY |U X ||PY |X |QU X ) + D(QY |U X ||P Y |X |QU X )
QY |U X



= min τ · D(QY |X ||PY |X |QX ) + D(QY |X ||P Y |X |QX ) ,
QY |X

(A.6)
(A.7)

and (b) follows since the objective function is linear in τ (and hence concave) and convex in QY |X , and therefore
the minimization and maximization order can be interchanged [59]. Thus, the achievability bound of Theorem 2
coincides with the converse bound of Proposition 1, the latter obtained when the rate of the DHT system is not
constrained at all and given by the reliability function of ordinary HT problem between PXY and P XY .
Proof of Corollary 4: It can be seen that the outermost minimum in (33) must be attained for QX = PX .
Intuitively, since we are only interested in negligible type 1 exponent, any event with QX 6= PX has exponentially

26

decaying probability exp[−nD(QX ||PX )], and does not affect the exponent. More rigorously, if QX 6= PX then by
taking τ → ∞ the objective function becomes unbounded. Hence (39) immediately follows. Further simplifications
are possible if the bound is weakened by ignoring the expurgated term, i.e., setting Bex (R, QX , τ ) = 0 in (32). In
this case, since


(τ + 1) · dτ (PX ) = min τ · D(QY |X ||PY |X |PX ) + D(QY |X ||P Y |X |PX ) ,
QY |X

(A.8)

′ , B ′′ [see (28) and (29)], it
[see (A.7)], and since τ only multiplies positive terms in the objective functions of Brc
rc

is evident that the supremum in (39) is obtained as τ → ∞. Hence, the supremum and minimum in (39) can be
interchanged to yield the bound
E2− (R, 0)
≥ D(PX ||P X ) + min





lim (τ + 1) · dτ (PX ), sup
sup

QU |X R : R ≥ I
τ →∞
PX ×QU |X (U ;X)−R
b
b




(a)
= min D(PXY ||PX × P Y |X , D(PX ||P X ) + sup
sup

QU |X R : R ≥ I

b
b
PX ×QU |X (U ;X)−R

+

+




lim Brc (R, Rb , PX × QU |X , τ )
τ →∞



(A.9)



lim Brc (R, Rb , PX × QU |X , τ ) ,
τ →∞


(A.10)

where (a) follows since


sup(τ + 1) · dτ (PX ) = sup min τ · D(QY |X ||PY |X |PX ) + D(QY |X ||P Y |X |PX )
τ ≥0

τ ≥0 QY |X



= sup min sup τ · D(QY |X ||PY |X |PX ) + D(QY |X ||P Y |X |PX )
τ ≥0 QY |X τ ≥0

= D(PY |X ||P Y |X |PX ).

(A.11)
(A.12)
(A.13)

A PPENDIX B
P ROOF

OF

T HEOREM 6

A. Proof of the Achievability Part
We begin by showing that an asymptotically good CD code must have a large subcode, such that the error
probabilities of any of the subcodes of the latter are not much worse than the corresponding probabilities of the
entire code.
Lemma 11. Let Cn be a CD code, and φn be a detector. Then, there exists a CD code C˜n with |C˜n |≥ |Cn |/3 which

27

satisfies the following: For any subcode C n ⊆ C˜n , there exists a of detector φn such that
pi (C n , φn ) ≤ 3 · pi (Cn , φn )

(B.1)

holds for both i = 1, 2.
Proof: Note that the error probabilities in (44) and (45) are averaged over the transmitted codeword X n ∈ Cn .
We first prove that by expurgating enough codewords from a codebook with good average error probabilities, a
codebook with maximal (over the codewords) error probabilities can be obtained (for both types of error). The proof
follows the standard expurgation argument from average error probability to maximal error probability (which in
turn follows from Markov’s inequality). Denoting the conditional type 1 error probability by19

we may write



def
p1 (Cn , φn |X n = xn ) = P φn (Y n ) = H|X n = xn ,

p1 (Cn , φn ) =

X

xn ∈Cn

=

(B.2)

P (X n = xn ) · p1 (Cn , φn |X n = xn )

1 X
p1 (Cn , φn |X n = xn ) .
|Cn | n

(B.3)
(B.4)

x ∈Cn

Thus, at least 2/3 of the codewords in xn ∈ Cn satisfy
p1 (Cn , φn |X n = xn ) ≤ 3 · p1 (Cn , φn ).

(B.5)

Using a similar notation for the conditional type 2 error probability, and repeating the same argument, we deduce
that there exists C˜n ⊂ Cn such that |C˜n |≥ |Cn |/3 and both (B.5) as well as
p2 (Cn , φn |X n = xn ) ≤ 3 · p2 (Cn , φn ),

(B.6)

hold for any xn ∈ C˜n . Let us now consider any C n ⊆ C˜n . For the code C n , the detector φn is possibly sub-optimal,
and thus might be improved. Using the standard Neyman-Pearson lemma [1, Prop. II.D.1], one can find a detector
φn (perhaps randomized) to match any prescribed type 1 error probability value, which is optimal in the sense that

if any other detector φ̂n satisfies p1 (C n , φ̂n ) ≤ p1 (C n , φn ) then p2 (C n , φ̂n ) ≥ p2 (C n , φn ). Specifically, let us require
that
p1 (C n , φn ) = 3 · p1 (Cn , φn ),

(B.7)

and choose φ̂n = φn . Then, as (B.5) holds for any xn ∈ C n ,
p1 (C n , φn ) =

X

xn ∈C

n

P (X n = xn ) · p1 C n , φn |X n = xn



(B.8)

19
Note that conditioned on X n = xn , p1 (Cn , φn |X n = xn ) depends on the code Cn only if the detector φn depends on the code. In this
lemma, the detector φn is arbitrary, and the use of this notation is therefore just for the sake of consistency.

28

≤ 3 · p1 (Cn , φn )

(B.9)

= p1 (C n , φn ),

(B.10)

and as φn is optimal in the Neyman-Pearson sense, (B.6) implies that
p2 (C n , φn ) ≤ p2 (C n , φn )
X
P (X n = xn ) · p2 (Cn , φn |X n = xn )
=
xn ∈C

(B.11)
(B.12)

n

≤ 3 · p2 (Cn , φn ).

(B.13)

The result follows from (B.7) and (B.13). Note that C n = C˜n is a valid choice.
Next, we construct optimal DHT systems for a single type class of the source.
Lemma 12. Let δ > 0 and QX ∈ P(X ) be given, and let {nl } the subsequence of blocklengths such that Tn (QX )

is not empty. Further, let C be a sequence of CD codes of type QX and rate ρ, and {φnl }∞
l=1 be a sequence of
detectors. Then, there exist a sequence of DHT systems H of rate H(QX ) − ρ such that
lim inf −
l→∞

1
1
log pi [Hnl |X nl ∈ Tnl (QX )] ≥ lim inf − log pi (Cnl , φnl ) − δ,
l→∞
nl
nl

(B.14)

holds for both i = 1, 2.
Proof: We only need to focus on of xn ∈ Tn (QX ). For notational simplicity, let us assume that n is always

such that Tn (QX ) is not empty. Let us first extract from C the sequence of CD codes C˜ whose existence is assured

by Lemma 11. The rate of C˜ is chosen to be larger than ρ − δ (for all sufficiently large n), and for any given
codeword, the error probability of each type is assured to be up to a factor of 3 of its average error probability.
Now, for a given permutation π of [n], we define the permutation of xn = (x1 , x2 , . . . , xn ) as

def


def
π(xn ) = xπ(1) , xπ(2) , . . . , xπ(n) ,

(B.15)

and for a set Dn = {xn (0), . . . , xn (|Dn |−1)}, we define
def

π(Dn ) = {π(xn (0)), . . . , π(xn (|Dn |−1))} .

(B.16)

n
As C˜n ∈ Tn (QX ), clearly so is π(C˜n ) ∈ Tn (QX ). Thus, there exists a set of permutations {πn,i }κi=i
such that

κn
[

i=1

πn,i (C˜n ) = Tn (QX ).

By a simple counting argument, the minimal number of permutations required κn is at least

(B.17)
|Tn (QX )|/|C˜n |.

This is

achieved when the permuted sets are pairwise disjoint, i.e., πn,i (C˜n ) ∩ πn,i′ (C˜n ) = φ, for all i 6= i′ . While this
property is difficult to assure, Ahlswede’s covering lemma [41, Section 6, Covering Lemma 2] implies that up to
the first order in the exponent, this minimal number can be achieved. To wit, there exists a set of permutations

29
κ∗

∗ } n such that
{πn,i
i=1

κ∗n ≤

|Tn (QX )| nδ
en[H(QX )+δ] nδ
·e ≤
· e = en[H(QX )−ρ+3δ] ,
en(ρ−δ)
|C˜n |

(B.18)

∗ is the identity permutation, and thus C ∗ = C˜ . Further,
for all n sufficiently large. W.l.o.g., we assume that πn,1
n
n,1

for 2 ≤ i ≤ κ∗n , let

∗
Cn,i




 i−1
[
def ∗
∗
πn,j
(C˜n ) .
= πn,i (C˜n )\



(B.19)

j=1

∗ is the permutation π ∗ of the code C˜ , excluding codewords which belong to a permutation
In words, the code Cn,i
n
n,i
∗

∗ }κn forms a disjoint partition of T (Q ). Moreover, recall that from Lemma
of C˜n with smaller index. Thus, {Cn,i
n
X
i=1

11, for any given
def

∗ −1 ∗
C n,i = [πn,i
] (Cn,i ) ⊆ C˜n

(B.20)

(where π −1 is the inverse permutation of π ), one can find a detector φn,i such that
p1 (C n,i , φn,i ) = 3 · p1 (Cn , φn ),

(B.21)

p2 (C n,i , φn,i ) ≤ 3 · p2 (Cn , φn ).

(B.22)

 ∗ −1 n 
def
φ∗n,i (y n ) = φn,i [πn,i
] (y ) .

(B.23)

and

Now, let

Due to the memoryless nature of the hypotheses, the permutation does not change the probability distributions.
Indeed, for an arbitrary CD code Cn′ , a detector φ′n and a permutation π ,
p1 (Cn′ , φ′n ) =

X

P (X n = xn ) · p1 (xn , φ′n )

X

P (X n = xn ) ·

xn ∈Cn′

=

xn ∈Cn′

1 X
= ′
|Cn | n ′

x ∈Cn

1 X
= ′
|Cn | n ′

x ∈Cn

1
= ′
|Cn |

yn :

yn :

X

X

(B.24)

y n : φ′n (y n )=H

P (Y n = y n |X n = xn )

(B.25)

X

P (Y n = y n |X n = xn )

(B.26)

X

P [Y n = π(y n )|X n = π(xn )]

(B.27)

φ′n (y n )=H

φ′n (y n )=H

xn ∈π −1 (Cn′ )

yn :

X

φ′n [π −1 (y n )]=H


= p1 π −1 (Cn′ ), φ′n,π .

P (Y n = y n |X n = xn )

(B.28)
(B.29)

30
def

where φ′n,π (y n ) = φ′n [π −1 (y n )]. Hence,
∗
p1 (C n,i , φn,i ) = p1 (Cn,i
, φ∗n,i ),

(B.30)

∗
, φ∗n,i ).
p2 (C n,i , φn,i ) = p2 (Cn,i

(B.31)

and

κ∗

∗ } n will serve as the bins of f , and detectors
We thus construct Hn = (fn , ϕn ) as follows. The codes {Cn,i
n
i=1
κ∗

n
as the decision function, given that the bin index is i. As said above, only xn ∈ Tn (QX ) will be encoded.
{φ∗n,i }i=1

∗ , and by f (xn ) = 0
More rigorously, the encoding of xn ∈ Tn (QX ) is given by fn (xn ) = i whenever xn ∈ Cn,i
n

whenever xn 6∈ Tn (QX ). Clearly, the rate of the code is less than

1
log κ∗n ≤ H(QX ) − ρ + 3δ,
n

(B.32)

for all n sufficiently large. The detector ϕn is given by ϕn (i, y n ) = φ∗n,i (y n ). The conditional type 1 error probability
of this DHT system is given by
κ∗

n
 X


P ϕn (fn (X ), Y ) = H|X ∈ Tn (QX ) =
P [fn (X n ) = i] · P ϕn (fn (X n ), Y n ) = H|fn (X n ) = i (B.33)



n

n

n

i=1
∗

=
(a)

=

(b)

=

κn
X
i=1
κ∗n

(B.34)

X

∗
P [fn (X n ) = i] · p1 (Cn,i
, φ∗n,i )

(B.35)

X

P [fn (X n ) = i] · p1 (C n,i , φn,i )

(B.36)

i=1
κ∗n

i=1

(c)



P [fn (X n ) = i] · P φ∗n,i (Y n ) = H|fn (X n ) = i

≤ 3 · p1 (Cn , φn ),

(B.37)

∗ , (b) follows
where (a) follows because given fn (X n ) = i the source vector X n is distributed uniformly over Cn,i

from (B.30), and (c) follows from (B.21). Similarly, the conditional type 2 error probability is upper bounded as
P [ϕn (fn (X n ), Y n ) = H|X n ∈ Tn (QX )] ≤ 3 · p2 (Cn , φn ).

(B.38)

The factor 3 in the error probabilities is negligible asymptotically.
The prove the achievability part of Theorem 6, the DHT system of Lemma 12 can be used to encode a single
type class. It still remains, however, to assure convergence of the error probabilities to their exponential bounds,
uniformly over all types. In other words, the DHT system of Lemma 12 is designed for a given QX , and as such,
the minimal blocklength for which the error probabilities are close to their exponential bounds may depend on QX .
However, as the blocklength n gets larger, source vectors types which did not exist at smaller blocklengths are also
emitted by the source. For such type class, the blocklength required to achieve good error exponents may be much

31

larger. It may be that these types dominate the type 1 error probability, and thus prevent convergence. The method
to solve this problem (see also [40], [46]) is to define a finite grid of types. CD codes are constructed only for types
in the grid, and as the grid is finite, uniform convergence is assured (by taking the maximum required blocklength
over all types within the grid). Now, if the type of xn belongs to the grid, it can be encoded using the CD which
pertains to its type. Otherwise, xn is slightly modified to a different vector X̃ n , where the type of the latter does
belong to the grid. Then, X̃ n is encoded using the CD code which pertain to its type. Since the CD codes are
designed for the pair (X n , Y n ), rather than for (X̃ n , Y n ), the side-information vector Y n is also modified to a
vector Ỹ n , using additional information sent from the encoder. To analyze the effect of this modification on the
error probabilities, we will need the following partial mismatch lemma.
def

n ) is
Lemma 13. Let Cn be a CD code, and φn a detector. For d = δn ∈ [n], assume that Ỹ n = (Ỹ1d , Ỹd+1

drawn as follows: Given xn ∈ Cn , under the hypothesis H , Ỹ n = Y n ∼ PY |X (·|xn ), and under the hypothesis H ,
n ∼P
n
Ỹ1d ∼ PY |X (·|xd1 ) and Ỹd+1
Y |X (·|xd+1 ). Then,

i
h
P φn (Ỹ n ) = H = p1 (Cn , φn ),

(B.39)

h
i
P φn (Ỹ n ) = H ≤ enΩδ · p2 (Cn , φn )

(B.40)

and

where
def

Ω =

max

x∈X , y∈Y

log

PY |X (y|x)
P Y |X (y|x)

< ∞.

(B.41)

Proof: Fix some blocklength n. The statement regarding the type 1 error probability is trivial. As for the type
2 error probability, we will show that the “wrong” distribution of Y n in the first d coordinates does not change
likelihoods and probabilities significantly. Indeed, conditioning on Y1d = y1d
i
i
h
h
P φn (Ỹ n ) = H|Ỹ1d = y1d = P φn (Y n ) = H|Y1d = y1d .

(B.42)

Then, since,


1 X
P Ỹ1d = y1d =
P Y |X (y1d |xd1 )
|Cn | n
x ∈Cn
1 X
PY |X (y1d |xd1 )
≤ edΩ ·
|Cn | n
x ∈Cn


dΩ
= e · P Y1d = y1d ,

(B.43)
(B.44)
(B.45)

we obtain
i

h
i

h
X
P φn (Ỹ n ) = H =
P Ỹ1d = y1d · P φn (Ỹ n ) = H|Ỹ1d = y1d
y1d ∈Y d

(B.46)

32

≤

X

y1d ∈Y d


i

h
edΩ · P Y1d = y1d · P φn (Y n ) = H|Y1d = y1d

= edΩ · p2 (Cn , φn ).

(B.47)
(B.48)

We will also use the following simple lemma:
Lemma 14. Let QX , Q̃X ∈ Pn (X ) and assume that ||QX − Q̃X ||=
min
x̃n ∈Tn (Q̃X )

2d
n

where d > 0. If xn ∈ Tn (QX ) then

dH (x̃n , xn ) ≤ d.

(B.49)

We are now ready to prove the achievability part. Since a similar method was applied in [40, Appendix A, proof
of Th. 5][46, Sec. VI.C], we will shorten the details of some of the arguments.
Proof of the achievability part of the Theorem 6: The encoded message begins with a description of the type
QX of X n . Then, to encode a given X n ∈ Tn (QX ), a DHT system which is based on good CD codes, as in

Lemma 12, will be used.
Given ǫ > 0 (to be specified later), we choose the grid as Pn0 (X ), and denote20
def

Φǫ (QX ) = arg min ||QX − Q̃X ||.

(B.50)

Q̃X ∈Pn0 (X )

The blocklength n0 is chosen to be sufficiently large, such that Φǫ (QX ) ≤

ǫ
2

for any QX ∈ P(X ). Note that

Φǫ (QX ) = QX whenever QX ∈ Pn0 (X ). We shall only consider blocklength of the form n = kn0 for some

k ∈ N+ . For n = kn0 + k0 with 1 ≤ k0 < n0 , the last k0 symbols of (X n , Y n ) can be simply ignored by both the

encoder and detector. The loss in exponents is a factor

n
kn0 ,

which is negligible for sufficiently large k.21

For n = kn0 , Pn0 (X ) ⊂ Pn (X ), and thus if QX is the type of the source vector xn , then either QX ∈ Pn0 (X )

or QX ∈ Pn (X )\Pn0 (X ). In the former case, (X n , Y n ) remains unchanged, and in the latter case, it is modified
as follows. First, the encoder will randomly generate X̃ n ∈ Tn (Φǫ (QX )) with a uniform distribution over the set
n

x̃n ∈ Tn (Φǫ (QX )) : dH (xn , x̃n ) =

nǫ o
.
4

(B.51)

Lemma 14 assures that this set is not empty. Further, due to the permutation symmetry of type classes, if X n is
distributed uniformly over Tn (QX ) then X̃ n is distributed uniformly over Tn (Φǫ (QX )). Now, as xn is altered to

X̃ n = x̃n , a similar change has to be made to the side-information vector. Indeed, given xn , the actual distribution of

Y n is either PY |X (·|xn ) or P Y |X (·|xn ) rather than either PY |X (·|x̃n ) or P Y |X (·|x̃n ). To account for this discrepancy,

the encoder will send the location of the

nǫ
4

coordinates in which xn and x̃n differ, and the values of x̃n at those

coordinates. Given this knowledge, the detector draws a new side-information vector Ỹ n in the following way.
If xi = x̃i then Ỹi = Yi , and if xi 6= x̃i then Ỹi ∼ PY |X (·|x̃i ). Note that if the hypothesis PY |X is active then
20
21

If the minimizer is not unique, one of the minimizers can be arbitrarily and consistently chosen.
As PXY ≪≫ P XY the exponents achieved by the DHT system are always finite.

33

n are
Ỹ n ∼ PY |X (·|x̃n ) as required. If, however, the hypothesis P Y |X is active, then n − ⌈ nǫ
4 ⌉ coordinates of Ỹ

drawn “correctly” according to Yi ∼ P Y |X (·|xi ), whereas

nǫ
4

coordinates are drawn according to the “wrong”

distribution Ỹi ∼ PY |X (·|x̃i ). As we will see, Lemma 13 assures that this mismatch has small effect on the type 1

error probability. At this point, the pair (X̃ n , Ỹ n ) can be encoded and detected using a DHT for the type Φǫ (QX ).
For the sake of the brevity of next derivations, let us assume that (X̃ n , Ỹ n ) are fictitiously generated even when
QX ∈ Pn0 (X ). Thus, the encoded vector is always x̃n , and the detector always uses the side-information vector
ỹ n .

We next turn to discuss the encoding of the modified source vector. We construct DHT subsystems Hn,Q̃X =
(fn,Q̃X , ϕn,Q̃X ) for all Q̃X ∈ Pn0 (X ), according to Lemma 12. Each DHT subsystem is constructed from a

constituent CD code whose type 1 error exponent is tuned to meet a constraint of E1 − D(Q̃X ||PX ). Now, as
|Pn0 (X )| is finite, uniform convergence over Pn0 (X ) is assured, to wit, there exists subsystems Hn,Q̃X and k

sufficiently large such that
h

i
p1 (fn,Q̃X , ϕn,Q̃X ) ≤ exp −n · E1 − D(Q̃X ||PX ) − δ ,

(B.52)

n
h
io
p2 (fn,Q̃X , ϕn,Q̃X ) ≤ exp −n · E2− (R, Q̃X , E1 − D(Q̃X ||PX )) − δ ,

(B.53)

and

for all Q̃X ∈ Pn0 (X ). A vector x̃n of type Q̃X ∈ Pn0 (X ) is encoded using a DHT subsystem Hn,Q̃X . Let us

denote the constructed system by Hn = (fn , ϕn ) which includes both the randomly generated (X̃ n , Ỹ n ) and the
subsystems Hn,Q̃X . It is required to analyze its asymptotic rate and both types of error exponent.
To analyze the rate, let us now summarize the different parts of the encoded message:
•

An index of the type class within [|Pn (X )|]. As |Pn (X )|≤ (n + 1)|X | , it can be encoded in no more than
⌈|X |· log(n + 1)⌉ nats.

•

The location of the

nǫ
4

coordinates in which x̃n (might) differ from xn . The number of sets of possible

nǫ
4

coordinates satisfies


n
nǫ
4



ǫ

≤ enhb ( 4 ) ,

(B.54)

and thus can be encoded in no more than nhb ( 4ǫ ) nats.
•
•

The value of xn in the possibly changed d coordinates. Each letter can be encoded using ⌈log|X |⌉ nats.
The nR encoded nats of the DHT system for x̃n .

Hence, the required rate is upper bounded by
ǫ ǫ
1
+ ⌈log|X |⌉ + R.
⌈|X |· log(n + 1)⌉ + hb
n
4
4

(B.55)

By choosing ǫ > 0 sufficiently small, the required rate can be made less than R + δ for all n sufficiently large.

34

For the type 1 error exponent, note that for all n = kn0 sufficiently large
X



P [X n ∈ Tn (QX )] · P ϕn (Y n ) = H|X n ∈ Tn (QX )

(B.56)



e−nD(QX ||PX ) · P ϕn (Y n ) = H|X n ∈ Tn (QX )
QX ∈Pn (X )
h
i
(b) nδ
= e · max e−nD(QX ||PX ) · P ϕn,Φǫ (QX ) (Ỹ n ) = H|X̃ n ∈ Tn (Φǫ (QX ))

(B.57)

p1 (Hn ) =

QX ∈Pn (X )
(a)

≤ enδ ·

max

QX ∈Pn (X )

(c)



e−nD(QX ||PX ) · P ϕn,Φǫ (QX ) (Y n ) = H|X n ∈ Tn (Φǫ (QX ))
QX ∈Pn (X )


max exp −n · min [D(QX ||PX ) + E1 − D (Φǫ (QX )||PX ) − δ]

= enδ ·

(d)

≤

max

QX ∈Pn (X )

(e)

QX ∈Pn (X )

≤ exp [−n · (E1 − 2δ)] ,

(B.58)
(B.59)
(B.60)
(B.61)

where (a) follows since |Pn (X )|≤ (n + 1)|X | ≤ enδ and P[X n ∈ Tn (QX )] ≤ exp[−n · D(QX ||PX )], (b) follows
from the definition of the system Hn , (c) follows from Lemma 13 (the trivial part regarding the type 1 error
exponent), (d) follows from (B.52), and (e) follows from the fact that D(QX ||PX ) is a continuous function of QX
in S(X ), and thus uniformly continuous.
To analyze the type 2 error exponent, first note that, as for the type 1 error probability,
p2 (Hn )
X
=

QX ∈Pn (X )

P [X n ∈ Tn (QX )] · P [ϕn (Y n ) = H|X n ∈ Tn (QX )]


≤ exp −n ·

(B.62)



h
i
1
n
n
min
D(QX ||PX ) − log P ϕn,Φǫ (QX ) (Ỹ ) = H|X̃ ∈ Tn (Φǫ (QX )) − δ
.
n
QX ∈Pn (X )

(B.63)

Now, recalling that n = kn0
lim inf −
k→∞

1
log p2 (Hn )
kn0


h
i
1
n
n
= lim inf min
D(QX ||PX ) − log P ϕn,Φǫ (QX ) (Ỹ ) = H|X̃ ∈ Tn (Φǫ (QX )) − δ
k→∞ QX ∈Pn (X )
n


(a)


ǫΩ
1
n
≥ lim inf min
D(QX ||PX ) − log p2 Hn,Φǫ(QX ) |X ∈ Tn (Φǫ (QX )) − δ −
k→∞ QX ∈Pn (X )
n
4
(b)

D(QX ||PX ) + F2− [H(Φǫ (QX )) − R, Φǫ (QX ), E1 − D(QX ||PX )]
≥ lim inf min

(B.64)
(B.65)

k→∞ QX ∈Pn (X )

−

ǫΩ
− 2δ
4

(c)

≥ lim inf

min

k→∞ QX ∈Pn (X )

− 2δ −
= min

QX ∈Pn0

ǫΩ
− δ1
4


(B.66)


D (Φǫ (QX )||PX ) + F2− [H(Φǫ (QX )) − R, Φǫ (QX ), E1 − D (Φǫ (QX )||PX ) + δ1 ]

D(QX ||PX ) + F2− [H(QX ) − R, QX , E1 − D(QX ||PX ) + δ1 ] − 2δ −

(B.67)

ǫΩ
− δ1
4



(B.68)

35

≥

inf

(

QX ∈Pn (X )

D (QX ||PX ) +

F2−

)
ǫΩ
− δ1 ,
[H(QX ) − R, QX , E1 − D(QX ||PX ) + δ1 ] − 2δ −
4

(B.69)

where (a) follows from Lemma 13 (and the way Ỹ n was defined), (b) follows from the uniform convergence of
the type 1 error exponents of the DHT systems for Φ(QX ) ∈ Pn0 (X ) [see (B.53)]. Passage (c) holds for some
δ1 > 0 that satisfies δ1 ↓ 0 as ǫ ↓ 0, and follows from the fact that D(QX ||PX ) is a continuous function of QX

in S(X ), and thus uniformly continuous. Finally, by choosing ǫ > 0 sufficiently small, and then δ > 0 sufficiently
small, the loss in exponents can be made arbitrarily small.
B. Proof of the Converse Part
Proof of the converse part of Theorem 6: For a given DHT system Hn , let us denote the (random) bin index
def

by In = fn (X n ). We will show that the converse hold even if the detector of the DHT systems Hn is aware of

the type of xn . Consequently, as an optimal Neyman-Pearson detector will only average the likelihoods of source
vectors from the true type class, it can be assumed w.l.o.g. that each bin contains only sequences from a unique
type class.
Recall that mn is the number of possible bins, and let mn,QX be the number of bins associated with a specific
def

type class QX , i.e., mn,QX = |Mn,QX | where
def


i ∈ [mn ] : fn−1 (i) ∩ Tn (QX ) = fn−1 (i) .

(B.70)

h
i
−1
def
µQX = E fn−1 (In )
|X n ∈ Tn (QX )
X
−1
=
fn−1 (i)
· P [In = i|X n ∈ Tn (QX )]

(B.71)

Mn,QX =

Further, conditioned on the type class QX (note that In is a function of X n ),

(B.72)

i∈Mn,QX

=

X

fn−1 (i)

i∈Mn,QX

−1

·

fn−1 (i)
|Tn (QX )|

(B.73)

mn,QX
|Tn (QX )|
en(R+δ)
≤ n[H(Q )−δ] ,
X
e
=

(B.74)
(B.75)

as for all n sufficiently large, mn ≤ en(R+δ) , and thus clearly mn,QX ≤ en(R+δ) . Hence, for any γ > 1, Markov’s
inequality implies
"
P In :

fn−1 (In )

#
h
1
n
X ∈ Tn (QX ) = P In : fn−1 (In )
≥
γ · µQ X
≥1−

1
.
γ

−1

i
≤ γ · µQX X n ∈ Tn (QX )

(B.76)
(B.77)

36

Thus, using (B.75), conditioned on X n ∈ Tn (QX )
fn−1 (In ) ≥

with probability larger than 1 −

1
γ

1
1
≥ · en·[H(QX )−R−2δ] ,
γ · µQ X
γ

(B.78)

> 0. Now, assume by contradiction that the statement of the theorem does not

hold. This implies that there exists an increasing subsequence of blocklengths {nk }∞
k=1 and δ > 0 such that
p1 (Hnk ) ≤ exp {−nk · [E1 − δ]} ,

(B.79)




p2 (Hk ) ≤ exp −nk · E2+ (R − 3δ, E1 − 3δ) + 5δ ,

(B.80)

and

for all k sufficiently large. For brevity of notation, we assume w.l.o.g. that these bounds hold for all n sufficiently
large, and thus omit the subscript k. Let δ > 0 be given. Then, for all n sufficiently large [which only depends on
(δ, |X |)],

p1 [Hn |X n ∈ Tn (QX )] ≤ exp {−n · [E1 − D(QX ||PX ) − 2δ]} ,

(B.81)

for all QX such that Tn (QX ) is not empty. Indeed, for all n sufficiently large, it holds that
exp [−n · (E1 − δ)] ≥ p1 (Hn )
X
=

P [X n ∈ Tn (QX )] · p1 [Hn |X n ∈ Tn (QX )]

(B.83)

X

e−n·[D(QX ||PX )+δ] · p1 [Hn |X n ∈ Tn (QX )]

(B.84)

max

e−n·[D(QX ||PX )+δ] · p1 [Hn |X n ∈ Tn (QX )] ,

(B.85)

QX ∈Pn (X )

≥
≥

(B.82)

QX ∈Pn (X )

QX ∈Pn (X )

and (B.81) is obtained by rearranging. Writing
p1 [Hn |X n ∈ Tn (QX )] =

X

i∈Mn,QX

P [In = i|X n ∈ Tn (QX )] · p1 (Hn |In = i) ,

(B.86)

Markov’s inequality implies
n
o
P In : p1 (Hn |In ) ≥ enδ · p1 [Hn |X n ∈ Tn (QX )]
≤

=

E [p1 (Hn |In )]
· p1 [Hn |X n ∈ Tn (QX )]
P
n
i∈Mn,Q P [In = i|X ∈ Tn (QX )] · p1 (Hn |In = i)
enδ

= e−nδ .

X

enδ · p1 [Hn |X n ∈ Tn (QX )]

(B.87)
(B.88)
(B.89)

The same arguments can be applied for the type 2 exponent. Thus, from the above and (B.78), with probability

37

larger than 1 − γ −1 − 2 · e−nδ , which is strictly positive for all sufficiently large n, the bin index satisfies (B.78),
p1 (Hn |In ) ≤ enδ · p1 [Hn |X n ∈ Tn (QX )]
≤ exp {−n · [E1 − D(QX ||PX ) − 3δ]} ,

(B.90)
(B.91)

as well as



p2 (Hn |In ) ≤ exp −n · E2+ (R + 3δ, E1 − 3δ) − D(QX ||P X ) + 3δ .

(B.92)

Now, let Q∗X ∈ P(X ) be chosen to achieve E2+ (R + 3δ, E1 − 3δ) up to δ, i.e., to be chosen such that
E2+ (R + 3δ, E1 − 3δ) − D(Q∗X ||P X ) ≥ F2+ (H(Q∗X ) − R − 3δ, Q∗X , E1 − D(Q∗X ||PX ) − 3δ) − δ,

(B.93)

∗
and let {nl }∞
l=1 be the subsequence of blocklengths such that Tn (QX ) is not empty. From the above discussion,

∗
there a sequence of bin indices {i∗nl }∞
l=1 such that (B.78), (B.91) and (B.92) hold for QX . Consider the sequence

(i∗nl ) to be a sequence of CD codes, whose rate is larger than H(QX ) − R − 3δ, its detectors
of bins Cn∗l = fn−1
l

are induced by the DHT system detector as φ∗nl (y nl ) = ϕnl (i∗nl , y nl ), and such that


p1 Cn∗ l , φ∗nl ≤ exp {−nl · [E1 − D(Q∗X ||PX ) − 3δ]} ,

and





p2 Cn∗ l , φ∗nl ≤ exp −nl · E2+ (R + 3δ, E1 − 3δ) − D(Q∗X ||P X ) + 3δ



≤ exp −nl · F2+ (H(Q∗X ) − R − 3δ, Q∗X , E1 − D(Q∗X ||PX ) − 3δ) + 2δ ,

(B.94)

(B.95)
(B.96)

where the last inequality follows from (B.93). However, this is a contradiction, since whenever (B.94) holds the
definition of CD reliability function implies that




p2 Cn∗ l , φ∗nl ≥ exp −nl · F2+ (H(Q∗X ) − R − 3δ, Q∗X , E1 − D(Q∗X ||PX ) − 3δ) + δ

(B.97)

for all l sufficiently large.

A PPENDIX C
P ROOF

OF

T HEOREM 8

We will follow the outline which appears right after the statement of the theorem. We will consider CD codes
drawn from the fixed-composition hierarchical ensemble defined in Definition 7, with conditional distribution QU |X ,
cloud-center rate ρc , and satellite rate ρs (which satisfy ρ = ρc + ρs ). In the course of the proof, we shall consider
various types of the form QU XY and QU XY . All of them are assume to have (U, X) marginal QU X = QU X even if
it is not explicitly stated. Furthermore, we shall assume that the blocklength n is such that Tn (QU X ) is not empty.

38

In this case, the notation for exponential equality (or inequality) needs to be clarified as follows. We will say that
.
an = bn if
1
an
lim
(C.1)
log l = 1,
l→∞ nl
bn l
where {nl }∞
l=1 is the subsequence of blocklengths such that Tn (QU X ) is not empty.
The proof of Theorem 8 relies on the following result, which is stated and proved by means of the typeenumeration method (see [48, Sec. 6.3]). Specifically, for a given y n , we define type-class enumerators for a
random CD code Cn by
def

Myn (QU XY ) = |{xn ∈ Cn : ∃un such that xn ∈ Cn,s (un ), (un , xn , y n ) ∈ Tn (QU XY )}| .

(C.2)

To wit, Myn (QU XY ) counts the random number of codewords which have joint type QU XY ∈ Pn (U × X × Y)

with their cloud center un and y n . To derive a random-coding bound on the achievable CD exponents, we will
(QU XY )Myλn (QU XY )] for an arbitrary sequence of {y n } taken
need to evaluate the exponential order of E[My1−λ
n

from Tn (QY ) = Tn (QY ).
The result is summarized in the following proposition, which is interesting on its own right. To this end, it will
be convenient to denote

def
∆λ (QU XY , QU XY ) = (1 − λ) · [ρ − IQ (U, X; Y )] − λ · max |IQ (U ; Y ) − ρc |+ , IQ (U, X; Y ) − ρ


i
h
+ λ ρ − IQ (U, X; Y ) − (1 − λ) · max IQ (U ; Y ) − ρc , IQ (U, X; Y ) − ρ .
+

(C.3)

Proposition 15. Let QU XY , QU XY ∈ Pn0 (U × X × Y) be given for some n0 , with QU X = QU X and QY = QY .
Also let {nl } be the subsequence of blocklengths such that Tnl (QU XY ) and Tnl (QU XY ) are both non-empty, and

nl
let {y nl }∞
l=1 satisfy y ∈ Tnl (QY ) for all l. Then, for any λ ∈ (0, 1)

h
i
1
λ
log E My1−λ
)
nl (QU XY )M nl (Q
y
U XY
nl →∞ nl




ρ − IQ (U, X; Y ),



= ∆λ (QU XY , QU XY ),





∆λ (QU XY , QU XY ) − |IQ (U ; Y ) − ρc |+ ,
lim

QU XY = QU XY
QU Y 6= QU Y and QU XY 6= QU XY

. (C.4)

QU Y = QU Y (and QU XY 6= QU XY )

It is interesting to note that the expression (C.4) is not continuous, as, say, QU XY → QU XY . The proof of
Proposition 15 is of technical nature, and thus relegated to Appendix D. For the rest of the proof, no knowledge
of the type-enumeration method is required.
Equipped with this result we proceed to analyze typical properties of randomly generated codes. As the CD
(Cn )

(C )

problem corresponds to an HT problem between P Y n and PY nn , and the performance of the latter is determined
by the Chernoff distance [see (11)], we next analyze the average exponent of the Chernoff distance over a random
choice of CD codes.

39

Lemma 16. Let Cn be drawn randomly from the hierarchical ensemble of Definition 7, with conditional distribution
QU |X , cloud-center rate ρc , and satellite rate ρs (which satisfy ρ = ρc + ρs ). Then,


 X h
i1−λ h
iλ 
(Cn )
(C )
˙ exp [−n · min {dλ (QX ), Arc }] .
E
P nn (y n )
· P Y n (y n )
≤
 n n Y


(C.5)

y ∈Y

where dλ (QX ) is defined in (27) when setting τ =

1−λ
λ ,

and Arc is defined in (53).

Proof: For (xn , y n ) ∈ Tn (QXY ), let us denote the log-likelihood of PY |X by
1
def
L(QXY ) = − log PY |X (y n |xn )
n
X
=−
QXY (x, y) log P (y|x),

(C.6)
(C.7)

x∈X , y∈Y

and the log-likelihood of P Y |X by L(QXY ) (with P Y |X replacing PY |X ). For any given n,


 X h
i1−λ h
iλ 
(Cn )
(C )
E
PY nn (y n )
· P Y n (y n )
 n n

y ∈Y
"
#λ 
#1−λ "


X
X
X
1
P Y |X (y n |xn )
(C.8)
= nρ
PY |X (y n |xn )
E
·

 n
e
xn ∈Cn
x ∈Cn
y n ∈Y n
"
#1−λ "
#λ 
 X

X
X
X
1
PY |X (y n |xn )
E
·
= nρ
P Y |X (y n |xn )
(C.9)
 n

e
n
n
x ∈Cn
x ∈Cn
QY ∈Pn (Y) y ∈Tn (QY )

1−λ 
λ 


 X

X
X
(a) 1
−nL(Q
)
−nL(Q
XY ) 
XY



|Tn (QY )| · E
Myn (QU XY )e
·
Myn (QU XY )e
= nρ


e
 QU XY

QY ∈Pn (Y)
Q
U XY

(C.10)

1−λ 
λ 


 X

X
−nL(Q
n[H(QY )−ρ]
−nL(Q
)
)
XY
XY 

Myn (QU XY )e
≤ |Pn (Y)| · max e
·E 
Myn (QU XY )e
·


QY ∈Pn (Y)
 QU XY

Q
U XY

(C.11)

≤ |Pn (Y)| |Pn (U × X × Y)|2
"
×

max

QY ∈Pn (Y)

(QU XY )e−n(1−λ)·L(QXY ) · max Myλn (QU XY )e−nλL(QXY )
en[H(QY )−ρ] · E max My1−λ
n
QU XY

≤ |Pn (Y)| |Pn (U × X × Y)|2

×

max

QY ∈Pn (Y)

en[H(QY )−ρ] · E 

X

QU XY

QU XY

My1−λ
(QU XY )e−n(1−λ)·L(QXY ) ·
n

X

QU XY

#

(C.12)



(C.13)

Myλn (QU XY )e−nλL(QXY ) 

= |Pn (Y)| |Pn (U × X × Y)|2
i
X X h
E My1−λ
(QU XY ) · Myλn (QU XY ) · e−n[(1−λ)·L(QXY )+λL(QXY )]
× max en[H(QY )−ρ]
n
QY ∈Pn (Y)

QU XY QU XY

(C.14)

40

≤ |Pn (Y)| |Pn (U × X × Y)|4

i
h
× max max en[H(QY )−ρ] · E My1−λ
(QU XY ) · Myλn (QU XY ) · e−n[(1−λ)·L(QXY )+λL(QXY )]
n
QU XY QU XY

def

= cn ·

max
(QU XY ,QU XY )∈Qn

ζn (QU XY , QU XY ),

(C.15)
(C.16)

where (a) follows since by symmetry, the expectation only depends on the type of y n , and by using the definitions
of the enumerators in (C.2), and the log-likelihood in (C.6). After passage (a) and onward, y n is an arbitrary
member of Tn (QY ), and the sums and maximization operators are over (QU XY , QU XY ) restricted to the set
def

Qn =


(QU XY , QU XY ) ∈ Pn2 (U × X × Y) : QY = QY , QXU = QXU .

(C.17)


(QU XY , QU XY ) ∈ S 2 (U × X × Y) : QY = QY , QXU = QXU ,

(C.18)

In the last equality we have implicitly defined cn and ζn (QU XY , QU XY ). By defining
def

Q =

and using standard arguments (e.g., as in the proof of Sanov’s theorem [3, Theorem 11.4.1]) we get



i
h
h
i
X
1−λ
λ
1
1
(Cn )
(C )
lim inf − log ζn (QU XY , QU XY ).
PY nn (y n )
· P Y n (y n )
lim inf − log E
≥
min
n→∞
 n n
 (QU XY ,QU XY )∈Q n→∞ n
n
y ∈Y

(C.19)

Hence, to obtain the exponential upper bound required (C.5), we may minimize over (QU XY , QU XY ) the exponential
order of ζn (·), denoted as
1
def
Λλ (QU XY , QU XY ) = lim inf − log ζn (QU XY , QU XY )
n→∞
n
h
i
1
= −H(QY ) + ρ − lim inf − log E My1−λ
(QU XY )Myλn (QU XY )
n
n→∞
n


+ (1 − λ) · L(QXY ) + λL(QXY ) .

(C.20)

(C.21)

We now evaluate this expression in three cases, which correspond to the three cases of Proposition 15. In each one,
we substitute for lim inf n→∞ − n1 log E[My1−λ
(QU XY )Myλn (QU XY )] the appropriate result,22 as follows:
n
Case 1.

For QU XY = QU XY ,
Λλ (QU XY , QU XY )
= −H(QY ) + ρ − [ρ − IQ (U, X; Y )] + (1 − λ) · L(QXY ) + λ · L(QXY )


= (1 − λ) · [−HQ (Y |X, U ) + L(QXY )] + λ · −HQ (Y |X, U ) + L(QXY )
(a)

= (1 − λ) · D(QY |U X ||PY |X |QU X ) + λ · D(QY |U X ||P Y |X |QU X ),

22

In fact, Proposition 15 implies that the limit inferior of this sequence is a proper limit.

(C.22)
(C.23)
(C.24)

41

where (a) follows from the identity
− HQ (Y |X, U ) + L(QXY ) = D(QY |U X ||PY |X |QU X ).

(C.25)

By defining the distribution
λ

def
(λ,x)
PY (y) =

PY1−λ
|X (y|x)P Y |X (y|x)

P

y ′ ∈Y

and observing that

λ

′
′
PY1−λ
|X (y |x)P Y |X (y |x)



min (1 − λ) · D(QY |U X ||PY |X |QU X ) + λ · D(QY |U X ||P Y |X |QU X )
QY |U X





X
X
λ
(λ,x)

(y|x)
(y|x)P
PY1−λ
QX (x) log 
= min D(QY |X ||PY |QX ) −
Y |X
|X

QY |X 
y∈Y
x∈X


X
X
λ

=−
QX (x) log 
PY1−λ
|X (y|x)P Y |X (y|x) ,
x∈X

(C.26)

(C.27)

(C.28)

y∈Y

it is evident that



Λλ,1 (QU XY , QU XY ) = min (1 − λ) · D(QY |U X ||PY |X |QU X ) + λ · D(QY |U X ||P Y |X |QU X ) (C.29)
QY |X


X
X
λ
(C.30)
(y|x)P Y |X (y|x)
PY1−λ
=−
QX (x) log 
|X
x∈X

y∈Y

= dλ (QX ).

Case 2.

(C.31)

For QU XY 6= QU XY and QU Y 6= QU Y
Λλ (QU XY , QU XY )
= −H(QY ) + ρ + (1 − λ) · L(QXY ) + λ · L(QXY )

− (1 − λ) · [ρ − IQ (U, X; Y )] + λ · max |IQ (U ; Y ) − ρc |+ , IQ (U, X; Y ) − ρ


i
h
− λ ρ − IQ (U, X; Y ) + (1 − λ) · max IQ (U ; Y ) − ρc , IQ (U, X; Y ) − ρ
+

(C.32)

(C.33)

(a)

= (1 − λ) · D(QY |U X ||PY |X |QU X ) + λ · D(QY |U X ||P Y |X |QU X )

+ λ · max |IQ (U ; Y ) − ρc |+ , IQ (U, X; Y ) − ρ


+ (1 − λ) · max IQ (U ; Y ) − ρc , IQ (U, X; Y ) − ρ
+

def

= Λλ,2 (QU XY , QU XY ),

where (a) follows from (C.25) again and rearranging.

(C.34)
(C.35)

42

Case 3.

For QU XY 6= QU XY and QU Y = QU Y
Λλ (QU XY , QU XY )
= Λλ,2 (QU XY , QU XY ) − |IQ (U ; Y ) − ρc |+

(C.36)

def

= Λλ,3 (QU XY , QU XY ).

(C.37)

Hence, the required bound on the Chernoff distance is given by
min
(

(QU XY ,QU XY )∈Q

Λλ (QU XY , QU XY )

= min dλ (QX ),

min
(QU XY ,QU XY )∈Q:QU Y 6=QU Y

Λλ,2 (QU XY , QU XY ),

min
(QU XY ,QU XY )∈Q:QU Y =QU Y

)

Λλ,3 (QU XY , QU XY ) .

(C.38)
Observing (C.37), we note that the third term in (C.38) satisfies
min
(QU XY ,QU XY )∈Q:QU Y =QU Y

= min

(

Λλ,3 (QU XY , QU XY )
min

(QU XY ,QU XY )∈Q:QU Y =QU Y , IQ (U ;Y )≤ρc

min
(QU XY ,QU XY )∈Q:QU Y =QU Y , IQ (U ;Y )>ρc
(a)

= min

(

min
(QU XY ,QU XY )∈Q:QU Y =QU Y ,



Λλ,2 (QU XY , QU XY ),

Λλ,2 (QU XY , QU XY ) − IQ (U ; Y ) + ρc

)

(C.39)

Λλ,2 (QU XY , QU XY ),

min
(QU XY ,QU XY )∈Q:QU Y =QU Y , IQ (U ;Y )>ρc



Λλ,2 (QU XY , QU XY ) − IQ (U ; Y ) + ρc

)

,

(C.40)

where in (a) we have removed the constraint IQ (U ; Y ) ≤ ρc in the first term of the outer minimization, since for
QU Y with IQ (U ; Y ) > ρc the second term will dominate the minimization. Thus, the first term in (C.40) may be

unified with the second term of (C.38). Doing so, the constraint QU Y 6= QU Y may be removed in the second term
of (C.38). Consequently, the required bound on the Chernoff distance is given by
(

min dλ (QX ),

min
(QU XY ,QU XY )∈Q

Λ2 (QU XY , QU XY ),
min

(QU XY ,QU XY )∈Q:QU Y =QU Y , IQ (U ;Y )>ρc


Λ2 (QU XY , QU XY ) − IQ (U ; Y ) + ρc

)

. (C.41)

The second term in (C.41) corresponds to A′rc defined in (51). The third term corresponds to A′′rc defined in (52),
when using ρs = ρ − ρc , and noting that when IQ (U ; Y ) > ρc , it is equal to
Λλ,2 (QU XY , QU XY ) − IQ (U ; Y ) + ρc

43

= (1 − λ) · D(QY |U X ||PY |X |QU X ) + λ · D(QY |U X ||P Y |X |QU X )
+ λ · |IQ (X; Y |U ) − ρs |+ + (1 − λ) · IQ (X; Y |U ) − ρs

+

.

(C.42)

Using the definition (53) of Arc as the minimum of the last two cases, (C.5) is obtained.
Next, recall that by its definition, a valid CD code of rate ρ is comprised of at least enρ distinct codewords.
However, when the codewords are independently drawn, some of them might be identical. Nonetheless, the next
lemma shows that the average number of distinct codewords is asymptotically close to enρ .
Lemma 17. Let Cn be drawn randomly from the hierarchical ensemble of Definition 7, with conditional distribution
QU |X , cloud-center rate ρc , and satellite rate ρs (which satisfy ρ = ρc + ρs ). If ρc + HQ (X|U ) ≥ ρ then
˙ enρ .
E [|Cn |] ≥

(C.43)
nρc

Proof: Let us enumerate the random cloud centers as {U n (i)}ei=1 and the random satellite codebooks as
nρc

{Cn,s (U n (i))}ei=1 . When a random satellite codebook Cn,s (un ) is drawn, then for any given (un , xn ) ∈ Tn (QU X )
n

n

P [x ∈ Cn,s (u )] = 1 −

using 1 − (1 − t)K ≥

1
2

1−

1
Tn (QU |X , un )

!enρs

(
)
enρs
1
≥ · min 1,
2
Tn (QX|U , un )


≥ exp −n · |HQ (X|U ) − ρs |+ + δ ,

(C.44)
(C.45)
(C.46)

· min {1, tK} [60, Lemma 1]. Further, for a random cloud center U n and xn ∈ Tn (QX )

P [xn ∈ Cn,s (U n )] = P [(xn , U n ) ∈ Tn (QU X )] · P [xn ∈ Cn,s (U n )|(xn , U n ) ∈ Tn (QU X )]
(a)

(C.47)

= P [(xn , U n ) ∈ Tn (QU X )] · P [xn ∈ Cn,s (un )]

(C.48)

≥

(C.49)



Tn (QU |X , xn )
· exp −n · |HQ (X|U ) − ρs |+ + δ
|Tn (QU )|


≥ exp −n · IQ (U ; X) + |HQ (X|U ) − ρs |+ + 2δ
def

= e−n(ξ+2δ) ,

(C.50)
(C.51)

where (a) is due to symmetry, and the definition
def

ξ = IQ (U ; X) + |HQ (U |X) − ρs |+
= max {IQ (U ; X), H(QX ) − ρs } .

Therefore, the average number of distinct codewords in the random CD code Cn is lower bounded as


X
I (xn ∈ Cn )
E [|Cn |] = E 
xn ∈T

n (QX )

(C.52)
(C.53)

(C.54)

44

=

X

P (xn ∈ Cn )

X

P

xn ∈Tn (QX )

=

xn ∈Tn (QX )
(a)

≥

X

xn ∈T

n (QX )

(enρc
[
i=1

(C.55)

[xn ∈ Cn,s (U n (i))]

)

1
· min {enρc · P [xn ∈ Cn,s (U n (1))] , 1}
2

(C.56)

(C.57)

≥ exp {n · [min {H(QX ) + ρc − ξ, H(QX )} − 3δ]}

(C.58)

= exp {n · [min {H(QX ) + ρc − IQ (U ; X), ρc + ρs , H(QX )} − 3δ]}

(C.59)

= en(ρ−3δ) ,

(C.60)

(b)

where (a) holds since for a given set of K pairwise independent events {Ak }K
k=1 [61, Lemma A.2]
"K
( K
)
#
X
[
1
P
P (Ak ) .
Ak ≥ min 1,
2
k=1

(C.61)

k=1

The passage (b) follows from the assumptions ρ < H(QX ) and ρc + HQ (X|U ) ≥ ρ. Thus, on the average, a

randomly chosen Cn has more than en(ρ−3δ) distinct codewords.
We are now ready to prove Theorem 8.

Proof of Theorem 8: As noted in Section IV, given a CD code Cn , the detector faces an ordinary HT problem
(C )

(Cn )

between the distributions PY nn and P Y n , and thus the bounds of Section II-B can be used. Specifically, using (11)
(with τ =

1−λ
λ ),

the type 2 error exponent under a type 1 error exponent constraint of F1 , can be lower bounded

for any given n by



 1−λ


i
i
h
h
X
λ
1−λ
1 1
(Cn ) n
(Cn ) n
max
max −
(y
)
P n (y )
· PYn
.
· F1 − · log

 n n Y
λ
λ n
Cn ⊆Tn (QX ): |Cn |≥enρ 0≤λ≤1 

(C.62)

y ∈Y

Instead of maximizing over Cn , we use ensemble averages. To this end, note that up to this point, we have obtained
(Lemma 16)



 X h
iλ 
i1−λ h
(Cn )
.
(C )
E
= exp [−n · min {dλ (QX ), Arc }] ,
P nn (y n )
· P Y n (y n )

 n n Y

(C.63)

y ∈Y

.
and showed that the average number of distinct codewords in a randomly chosen codebook is |Cn |= enρ (Lemma

17). It remains to prove the existence of a CD code, whose codewords are all distinct, and its Chernoff distance
exponent is close to the ensemble average. To this end, let δ > 0 be given, and consider the events


1
def
A1 = |Cn | ≥ E [|Cn |] ,
2

(C.64)

and


 X h
i1−λ h
iλ
oi
h
n
(Cn )
def
(C )
P nn (y n )
· P Y n (y n ) ≤ e4nδ · exp −n · min dλ (QX ), Ãrc
A2 (λ) =
.
 n n Y

y ∈Y

(C.65)

45

Note that since P(|Cn |≤ enδ · E[|Cn |]) = P(|Cn |≤ enρ ) = 1, for all n sufficiently large, the reverse Markov
inequality23 [62, Section 9.3, p. 159] implies that
P [A1 ] ≥

1 − 1/2
≥ e−2nδ .
enδ − 1/2

(C.66)

Further, for any given λ ∈ [0, 1], Markov’s inequality implies that for all n sufficiently large
P [A2 (λ)] ≥ 1 − e−n3δ .

(C.67)

P [A1 ∩ A2 (λ)] ≥ 1 − P[Ac1 ] − P [Ac2 (λ)]


≥ 1 − e−3nδ − 1 − e−2nδ

(C.68)

Then, we note that

(C.69)

= e−2nδ − e−3nδ

(C.70)

> 0,

(C.71)

ad thus deduce that there exists a CD code Cn∗ (λ) such that |Cn∗ (λ)|≥ 41 en(ρ−δ) ≥ en(ρ−2δ) and A2 (λ) holds for all

n sufficiently large. Let the CD code obtained after keeping only the unique codewords of Cn∗ (λ) be denoted as
Cn∗∗ (λ). It remains to show that the exponent of the Chernoff distance of Cn∗∗ (λ) is asymptotically equal to that of
Cn∗ (λ). Indeed,

i1−λ h
iλ
X h (C ∗ (λ))
(C ∗ (λ))
PY nn (y n )
· P Y nn (y n )

y n ∈Y n



1−λ 

λ

1
1
P
(y n |xn )
PY |X (y n |xn )
·
nρ
nρ Y |X
e
e
y n ∈Y n xn ∈Cn∗ (λ)
xn ∈Cn∗ (λ)

λ
1−λ 
X
X
(a) X
1
1

≥
P
(y n |xn )
P
(y n |xn )
·
nρ Y |X
nρ Y |X
e
e
y n ∈Y n xn ∈Cn∗∗ (λ)
xn ∈Cn∗∗ (λ)
1−λ 

λ
X
X
X
(b)
1
1

P
(y n |xn )
·
≥ e−2nδ ·
P
(y n |xn ) ,
∗∗ (λ)| Y |X
∗∗ (λ)| Y |X
|C
|C
n
n
n
n
n
n
∗∗
∗∗

=

X



X

y ∈Y

x ∈Cn (λ)

X

(C.72)

(C.73)

(C.74)

x ∈Cn (λ)

where (a) follows since Cn∗∗ (λ) ⊆ Cn∗ (λ), and (b) follows since |Cn∗∗ (λ)|≥ en(ρ−2δ) , and therefore
X h

y n ∈Y n

(C ∗∗ (λ))

PY nn

i1−λ h
i
h
n
oi
(C ∗∗ (λ)) n λ
(y n )
· P Y nn
(y ) ≤ e6nδ · exp −n · min dλ (QX ), Ãrc (ρ, ρc , QU X , λ) .

As all the above holds for any λ ∈ [0, 1], (C.62) implies





 1−λ
i
i
h
h
X
λ
1−λ
1 1
(Cn )
(C )
· F1 − · log
PY nn (y n )
· P Y n (y n )
−
max
max

 n n
0≤λ≤1 Cn ⊆Tn (QX ): |Cn |≥enρ 
λ
λ n

(C.75)

y ∈Y

23

The reverse Markov inequality states that if P(0 ≤ X ≤ αE[X]) = 1 for some α > 1. Then, for any β < 1,P (X > βE[X]) ≥

1−β
.
α−β

46





i
h
h
i
X
1−λ
1 1
(C ∗∗ (λ)) n λ
(C ∗∗ (λ)) n 1−λ
≥ max −
(y )
PY nn
· P Y nn
· F1 − · log
(y )
 n n

0≤λ≤1
λ
λ n
y ∈Y


1
1−λ
· F1 + · [min {dλ (QX ), Arc (ρ, ρc , QU X , λ)} − 6δ] .
≥ max −
0≤λ≤1
λ
λ

(C.76)
(C.77)

Now, due to the continuity of Arc (ρ, ρc , QU X , λ) in QU X , for any given QU X ∈ S(U × X ), one can find a
blocklength n0 such that for all n ≥ n0 with Tn (QX ) not empty, there exists Q̃U X ∈ Pn (U × X ) with QX = Q̃X
such that
Arc (ρ, ρc , QU X , λ) − Arc (ρ, ρc , Q̃U X , λ) ≤ δ.

With this, we have proved the existence of a CD code such that



 1
i
h
h
i
X
1−λ
λ
1 1
(Cn ) n
(Cn ) n
− · log
P n (y )
· P Y n (y )
≥ · [min {dλ (QX ), Arc } − 3δ]
 n n Y
 λ
λ n

(C.78)

(C.79)

y ∈Y

can be established for any blocklength such that Tn (QX ) is not empty. The proof is completed by taking n → ∞
and δ ↓ 0, and allowing to maximize Arc (ρ, ρc , QU X , λ) over QU |X and ρc (with a constraint set dictated by Lemma
17).
Remark 18. As mentioned after Theorem 8, the random-coding bound can be achieved by a single sequence of
CD codes, simultaneously for all type 1 error exponent constraint F1 . This can be proved by showing that there
exists a CD code such that the event A2 (λ) defined in (C.67) holds for all λ ∈ [0, 1]. To show the latter, we
uniformly quantize the interval [0, 1] to {λi }K
i=0 with λi =

i
K

and a fixed K . Then, using the union bound, for all

n sufficiently large

P

"K
\

i=0

#

A2 (λi ) ≥ 1 −

K
X

P [Ac2 (λi )]

(C.80)

i=0

≥ 1 − (K + 1) · e−3nδ

(C.81)

≥ 1 − e−2nδ ,

(C.82)

and this bound can be used in lieu of (C.67) in the proof. This will prove the simultaneous achievability of A2 (λi )
for all 0 ≤ i ≤ K . Then, utilizing the continuity of Arc (ρ, ρc , QU X , λ), by taking K to increase sub-exponentially
in n the same result can be established to the entire [0, 1] interval.
A PPENDIX D
T HE T YPE -E NUMERATION M ETHOD

AND THE

P ROOF

OF

P ROPOSITION 15

We begin with a short review of the type-enumeration method [48, Sec. 6.3]. To begin, let us define type-class
enumerators for the cloud centers by
def

Nyn (QU Y ) = |{un ∈ Cc,n : (un , y n ) ∈ Tn (QU Y )}| .

(D.1)

47

To wit, Nyn (QU Y ) counts the random number of cloud centers which have joint type QU Y ∈ Pn (U × Y) with y n .
While Myn (QU XY ) defined in (C.2) is an enumerator of an hierarchical ensemble, Nyn (QU Y ) is an enumerator
of an ordinary ensemble, and thus simpler to analyze. Furthermore, the analysis of Myn (QU XY ) depends on the
properties of Nyn (QU Y ), and thus we begin by analyzing the latter.
As the cloud centers in the ensemble are drawn independently, Nyn (QU Y ) is a binomial random variable. It
pertains to enρc trials and probability of success of the exponential order of exp[−n · IQ (U ; Y )], and consequently,
.
E[Nyn (QU Y )] = exp{n · [ρc − IQ (U ; Y )]}. In the sequel, we will need refined properties of the enumerator, and
specifically, its large-deviations behavior and the moments E[Nyλn (QU Y )]. To this end, we note that as Nyn (QU Y )

is just an enumerator for a code drawn from an ordinary ensemble, the analysis of [48, Sec. 6.3] [63, Appendix A.2]
holds. As was shown there, when IQ (U ; Y ) ≤ ρc , E[Nyn (QU Y )] increases exponentially with n as exp{n · [ρc −
IQ (U ; Y )]}, and Nyn (QU Y ) concentrates double-exponentially rapidly around this average. Specifically, letting
def

Bn (QU Y , δ) =

n
o
e−nδ · E [Nyn (QU Y )] ≤ Nyn (QU Y ) ≤ enδ · E [Nyn (QU Y )] ,

(D.2)

then for any δ > 0 sufficiently small
i
h
P [Bnc (QU Y , δ)] ≤ exp −enδ .

(D.3)

When IQ (U ; Y ) > ρc holds, E[Nyn (QU Y )] decreases exponentially with n as exp{−n · [IQ (U ; Y ) − ρc ]}, and
Nyn (QU Y ) = 0 almost surely. Furthermore, the probability that even a single codeword has joint type QU Y with
y n is exponentially small, and the probability that there is an exponential number of such codewords is double-

exponentially small. Specifically, for all sufficiently large n
P {Nyn (QU Y ) ≥ 1} ≤ exp {−n · [IQ (U ; Y ) − ρc ]} ,

(D.4)

i
o
h
n
P Nyn (QU Y ) ≥ e2nδ ≤ exp −enδ .

(D.5)

and for any given δ > 0

Using the properties above, it can be easily deduced that


i 
h
. exp {nλ · [ρc − IQ (U ; Y )]} ,
E Nyλn (QU Y ) =

exp {−n · [IQ (U ; Y ) − ρc ]} ,

IQ (U ; Y ) ≤ ρc

,

(D.6)

IQ (U ; Y ) > ρc

or, in an equivalent and more compact form,

h
i


.
E Nyλn (QU Y ) = exp n · λ [ρc − IQ (U ; Y )] − (1 − λ) · |IQ (U ; Y ) − ρc |+ .

(D.7)

We can now turn to analyze the behavior of the more complicated enumerator Myn (QU XY ). To this end, note that
conditioned on the event Nyn (QU Y ) = enν , Myn (QU XY ) is a binomial random variable pertaining to exp[n(ν +ρs )]

48

trials and probability of success of the exponential order of exp[−n · IQ (X; Y |U )]. Thus,


i 
h
. exp {nλ · [ν + ρs − IQ (X; Y |U )]} , IQ (X; Y |U ) ≤ ν + ρs
E Myλn (QU XY ) Nyn (QU Y ) = enν =
,

exp {−n · [IQ (X; Y |U ) − ν − ρs ]} , IQ (X; Y |U ) > ν + ρs

(D.8)

and the conditional large-deviations behavior of Myn (QU XY ) is identical to the large-deviations behavior of
Nyn (QU Y ), with ν + ρs and IQ (X; Y |U ) replacing ρc and IQ (U ; Y ), respectively. The next lemma provides an

asymptotic expression for the unconditional moments of Myn (QU XY ). It can be easily seen that (D.7) is obtained
as a special case, when setting U = X and ρ = ρc .
Lemma 19. For λ > 0
h
i



.
E Myλn (QU XY ) = exp n · λ [ρ − IQ (U, X; Y )] − (1 − λ) · max |IQ (U ; Y ) − ρc |+ , IQ (U, X; Y ) − ρ
.

(D.9)

Proof: Let


1
δ ∈ 0, lim inf log E[Nyn (QU Y )] ,
n→∞ n

(D.10)

define the events
def

A=0
n (QU Y ) = {Ny n (QU Y ) = 0} ,
def

A=1
n (QU Y , δ) =

n

def

A≥1
n (QU Y , δ) =

o
1 ≤ Nyn (QU Y ) ≤ e2nδ ,
n

o
Nyn (QU Y ) ≥ e2nδ ,

(D.11)
(D.12)
(D.13)

and recall the definition of the event Bn (QU Y , δ) in (D.2). We will consider four cases depending on the relations
between the rates and mutual information values. For the sake of brevity, only the first case will be analyzed with a
strictly positive δ > 0 and then the limit δ ↓ 0 will be taken. In all other three cases, we shall derive the expressions
for the moments assuming δ = 0, with the understanding that upper and lower bounds can be derived in a similar
manner to the first case. For notational convenience, when the expressions are derived assuming δ = 0 we will
omit δ from the notation of the events defined above [e.g., A=1
n (QU Y )]. We will use the moments (D.6), the strong
concentration relation (D.3) and the large-deviations bound (D.4), for both Nyn (QU Y ) and Myn (QU XY ) [when the
latter is conditioned on the value of Nyn (QU Y )].
Case 1.

If IQ (U ; Y ) > ρc and IQ (X; Y |U ) > ρs , then for all δ > 0 sufficiently small, IQ (U ; Y ) > ρc + δ and
IQ (X; Y |U ) > ρs + δ and thus,

i
h
E Myλn (QU XY )
i
h


 =1

=1
λ
≤ P A=0
n (QU Y ) · 0 + P An (QU Y , δ) · E My n (QU XY )|An (QU Y , δ)

 nλρ
+ P A≥1
n (QU Y , δ) · e

(D.14)

49

i
h
˙ 0 + exp {−n · [IQ (U ; Y ) − ρc − δ]} · exp {−n · [IQ (X; Y |U ) − ρs − 2δ]} + exp −enδ · enλρ
≤

(D.15)

.
= exp {n · [ρ − IQ (U, X; Y ) + 3δ]} .

(D.16)

Similarly, it can be shown that
i
h
˙ exp {n · [ρ − IQ (U, X; Y ) − 3δ]} .
E Myλn (QU XY ) ≥

(D.17)

As δ ≥ 0 is arbitrary, we obtain
h
i
.
E Myλn (QU XY ) = exp {n · [ρ − IQ (U, X; Y )]} .
Case 2.

If IQ (U ; Y ) > ρc and IQ (X; Y |U ) < ρs then
i
h
E Myλn (QU XY )
i
h


 =1

=1
λ
(Q
)|A
(Q
)
≤ P A=0
(Q
)
·
0
+
P
A
(Q
)
·
E
M
n
U
XY
U
Y
U
Y
U
Y
n
n
n
y
 ≥1
 nλρ
+ P An (QU Y ) · e

Case 3.

(D.18)

(D.19)

.
= 0 + exp {−n · [IQ (U ; Y ) − ρc ]} · exp {n · λ · [ρs − IQ (X; Y |U )]} + 0

(D.20)

= exp {n · [ρc − IQ (U ; Y ) + λ · (ρs − IQ (X; Y |U ))]}

(D.21)

= exp {n · [ρc − IQ (U ; Y ) + ρs − IQ (X; Y |U ) − (1 − λ) · (ρs − IQ (X; Y |U ))]}

(D.22)

= exp {n · [ρ − IQ (U, X; Y ) − (1 − λ) (ρs − IQ (X; Y |U ))]} .

(D.23)

If IQ (U ; Y ) < ρc and IQ (X; Y |U ) > ρc − IQ (U ; Y ) + ρs then
i
h
E Myλn (QU XY )

h
i
= P {Bn (QU Y )} · E Myλn (QU XY )|Bn (QU Y )
h
i
+ P {Bnc (QU Y )} · E Myλn (QU XY )|Bnc (QU Y )

Case 4.

(D.24)

.
= 1 · exp {n · [ρc − IQ (U ; Y ) + ρs − IQ (X; Y |U )]} + 0

(D.25)

= exp {n · [ρ − IQ (U, X; Y )]} .

(D.26)

If IQ (U ; Y ) < ρc and IQ (X; Y |U ) < ρc − IQ (U ; Y ) + ρs then
h
i
E Myλn (QU XY )

i
h
= P {Bn (QU Y )} · E Myλn (QU XY )|Bn (QU Y )
i
h
+ P {Bnc (QU Y )} · E Myλn (QU XY )|Bnc (QU Y )

.
= 1 · exp {n · λ · [ρc − IQ (U ; Y ) + ρs − IQ (X; Y |U )]} + 0

(D.27)
(D.28)

50

= exp {n · λ · [ρ − IQ (U, X; Y )]}

(D.29)

= exp {n · [ρ − IQ (U, X; Y ) − (1 − λ) [ρ − IQ (U, X; Y )]]} .

(D.30)

Noting that IQ (X; Y |U ) > ρc − IQ (U ; Y ) + ρs is equivalent to IQ (U, X; Y ) > ρ, it is easy to verify that
i
h
 n
.
E Myλn (QU XY ) = exp n · ρ − IQ (U, X; Y ) − (1 − λ) ρs − IQ (X; Y |U ) + |ρc − IQ (U ; Y )|+

+

o

(D.31)

matches all four cases. The final expression is obtained from the identities
ρ − IQ (U, X; Y ) − (1 − λ) · ρs − IQ (X; Y |U ) + |ρc − IQ (U ; Y )|+

+

(a)

= ρ − IQ (U, X; Y ) − (1 − λ) ρ − IQ (U, X; Y ) + |IQ (U ; Y ) − ρc |+

(D.32)

+

(b)

= λ [ρ − IQ (U, X; Y )] − (1 − λ) |IQ (U ; Y ) − ρc |+ − (1 − λ) IQ (U, X; Y ) − ρ − |IQ (U ; Y ) − ρc |+

(c)
= λ [ρ − IQ (U, X; Y )] − (1 − λ) · max |IQ (U ; Y ) − ρc |+ , IQ (U, X; Y ) − ρ ,

+

(D.33)
(D.34)

where (a) follows from the identity |t|+ = t+|−t|+ with t = ρc −IQ (U ; Y ), (b) follows from the same identity with
t = ρ−IQ (U, X; Y )+|IQ (U ; Y )−ρc |+ , and (c) follows from t+|s − t|+ = max {t, s} with t = |IQ (U ; Y )−ρc |+

and s = IQ (U, X; Y ) − ρ.
To continue, we will need to separate the analysis according to whether QU Y 6= QU Y (Lemma 22) or QU Y = QU Y
(Lemma 25). In the former case Myn (QU XY ) and Myn (QU XY ) count codewords which pertain to different cloud
(QU XY ) and Myλn (QU XY ) are asymptotically uncorrelated. In the later
centers, and as we shall next see, My1−λ
n

case, these enumerators may count codewords which pertain to the same cloud center, and correlation between
(QU XY ) and Myλn (QU XY ) is possible. We will need two auxiliary lemmas.
My1−λ
n

Lemma 20. Let f (t) be a monotonically non-decreasing function, let B ∼ Binomial(N, p) and B̃ ∼ Binomial(Ñ , p)
with Ñ > N . Then,

def

h
i
E [f (B)] ≤ E f (B̃) .

(D.35)

Proof: Let L = N − Ñ and A ∼ Binomial(L, p), independent of B . As the sum of independent binomial
random variables with the same success probability is also binomially distributed, we have B + A is equal in
distribution to B̃ ∼ Binomial(Ñ , p). Thus,
h
i
E f (B̃) = E [f (B + A)]
≥ E [f (B)] ,

(D.36)
(D.37)

where the inequality holds pointwise for any given A = a, and thus also under expectation.
.
As is well known from the method of types, P[(U n , y n ) ∈ Tn (QU Y )] = exp[−nIQ (U ; Y )]. The next lemma
shows that this probability can be upper bounded asymptotically even when IQ (U ; Y ) = 0, and the large-deviations
behavior does not hold.

51

Lemma 21. Let QU Y ∈ P(U × Y) be given such that supp(QU ) ≥ 2 and supp(QY ) ≥ 2. Also let y n ∈ Tn (QY )

and assume that U n is distributed uniformly over Tn (QU ). Then, for any given ǫ > 0 there exists n0 (QU , QY )
such that for all n ≥ n0 (QU , QY )

P [(U n , y n ) ∈ Tn (QU Y )] ≤ ǫ.

(D.38)

Proof: Using Robbins’ sharpening of Stirling’s formula (e.g., [4, Problem 2.2]), it can be shown that the size
of a type class satisfies






1
supp(Q
)
−
1
log
n
X
|Tn (QX )| ∼
n− 2 [supp(QX )−1] .
= exp n · H(QX ) −
2
n

(D.39)

Hence,
P [(U n , y n ) ∈ Tn (QU Y )]
(a)

= P [(U n , Y n ) ∈ Tn (QU Y )]

(D.40)

=

(D.41)

|Tn (QU Y )|
|Tn (QU )| |Tn (QY )|

1
∼
= e−n·IQ (U ;Y ) · n− 2 ·[supp(QU Y )−supp(QU )−supp(QY )+1] ,

(D.42)

where (a) holds by symmetry [assuming that Y n is drawn uniformly over Tn (QY )].
Now, by the Kullback-Csiszár-Kemperman-Pinsker inequality [3, Lemma 11.6.1][4, Exercise 3.18]
IQ (U ; Y ) = D(QU Y ||QU × QY )
1
kQU Y − QU × QY k2 ,
≥
2 log 2

(D.43)
(D.44)

and thus for any given δ > 0
n

o
Q̃U Y : Q̃U = QU , Q̃Y = QY , IQ̃ (U ; Y ) ≤ δ
n
⊆ Q̃U Y : Q̃U = QU , Q̃Y = QY , Q̃U Y − QU × QY

def

= J (η, QU , QY ),

def

where η =

≤η

o

(D.45)
(D.46)

√
2δ log 2. Choose η(QU, QY ) such that supp(Q̃U Y ) = supp(QU × QY ) = supp(QU ) · supp(QY ) for

all Q̃U Y ∈ J (δ0 , QU , QY ). We consider two cases:
Case 1.

If QU Y ∈ J (δ, QU , QY ) then it is elementary to verify that in this event, as supp(QU ) ≥ 2 and
supp(QY ) ≥ 2 was assumed,
supp(QU Y ) − supp(QU ) − supp(QY )
= supp(QU ) · supp(QY ) − supp(QU ) − supp(QY )

(D.47)

≥ 0,

(D.48)

52

and thus (D.42) implies that
1
P [(U n , y n ) ∈ Tn (QU Y )] ≤ √ .
n

Case 2.

If QU Y 6∈ J (δ, QU , QY ) then IQ (U ; Y ) ≥ δ =

1
2
2 log 2 η

(D.49)

and
1

2

P [(U n , y n ) ∈ Tn (QU Y )] ≤ e−n 2 log 2 η .

(D.50)

This completes the proof.
We are now ready to state and prove the asymptotic uncorrelation lemma for QU Y 6= QU Y .
Lemma 22. Let (QU XY , QU XY ) be given such that QU Y 6= QU Y . Then,
i
i
i
h
h
h
.
λ
1−λ
λ
1−λ
E Myn (QU XY )Myn (QU XY ) = E Myn (QU XY ) · E Myn (QU XY ) .

(D.51)

Proof: We begin by lower bounding the correlation. To this end, let us decompose
Myn (QU XY ) = Myn (QU XY , 1) + Myn (QU XY , 2),

(D.52)

where Myn (QU XY , 1) is the enumerator of to the subcode of Cn of codewords which pertain to half of the cloud
centers (say, for cloud centers with odd indices) and Myn (QU XY , 2) is the enumerator pertaining to the rest of the
codewords. Note that Myn (QU XY , 1) and Myn (QU XY , 2) are independent for any given (QU XY , QU XY ). Hence,
i
h
(QU XY )Myλn (QU XY )
E My1−λ
n
n
λ o

= E [Myn (QU XY , 1) + Myn (QU XY , 2)]1−λ · Myn (QU XY , 1) + Myn (QU XY , 2)
h
i
(a)
≥ E My1−λ
(QU XY , 1) · Myλn (QU XY , 2)
n
i
h
h
i
(b)
(QU XY , 1) · E Myλn (QU XY , 2)
= E My1−λ
n

(D.53)
(D.54)
(D.55)

(c)

i
i
h
h
.
(QU XY ) · E Myλn (QU XY ) ,
= E My1−λ
n

(D.56)

where (a) follows since enumerators are positive, and (b) follows since Myn (QU XY , 1) and Myn (QU XY , 2) are
independent for any given (QU XY , QU XY ). (c) holds true since Myn (QU XY , i) (i = 1, 2) pertain to codebooks of
.
.
cloud-center size 21 enρc = enρc and satellite rate ρs , and thus clearly E[Myλn (QU XY , i)] = E[Myλn (QU XY )].
To derive an upper bound on the correlation, we first note two properties. First, as the codewords enumerated by
Myn (QU XY ) necessarily correspond to different cloud centers from the codewords enumerated by Myn (QU XY ),

the following Markov relation holds:
Myn (QU XY ) − Nyn (QU Y ) − Nyn (QU Y ) − Myn (QU XY ).

(D.57)

Second, conditioned on Nyn (QU Y ), Nyn (QU Y ) is a binomial random variable pertaining to enρc −Nyn (QU Y ) ≤ enρc

53

trials with a probability of success given by
h
i
P (U n , y n ) ∈ Tn (QU Y ) (U n , y n ) 6∈ Tn (QU Y ) .

(D.58)

However, this probability is not significantly different than the unconditional probability. More rigorously, for any
ǫ ∈ (0, 1), and all n > n0 (QU , QY ) sufficiently large

h
i
P [(U n , y n ) ∈ Tn (QU Y )] ≤ P (U n , y n ) ∈ Tn (QU Y ) (U n , y n ) 6∈ Tn (QU Y ) ≤

1
· P [(U n , y n ) ∈ Tn (QU Y )] .
1−ǫ
(D.59)

To see this, note that since QU Y 6= QU Y we must have supp(QY ) ≥ 2, and thus Lemma 21 implies that for any
ǫ ∈ (0, 1), and all n sufficiently large

h
i
P (U n , y n ) ∈ Tn (QU Y ) (U n , y n ) 6∈ Tn (QU Y )


P (U n , y n ) ∈ Tn (QU Y ) ∩ (U n , y n ) 6∈ Tn (QU Y )


=
P (U n , y n ) 6∈ Tn (QU Y )
P [(U n , y n ) ∈ Tn (QU Y )]
≤
1−ǫ
1
· P [(U n , y n ) ∈ Tn (QU Y )] ,
≤
1−ǫ

(D.60)
(D.61)
(D.62)

and, similarly,
h
i
P (U n , y n ) ∈ Tn (QU XY ) (U n , X n , y n ) 6∈ Tn (QU XY ) ≥ P [(U n , X n , y n ) ∈ Tn (QU XY )] .

(D.63)

Equipped with the Markov relation (D.57) and the bound on the conditional probability (D.59), we can derive an
upper bound on the correlation that asymptotically matches the lower bound (D.56), and thus prove the lemma.
Indeed,
i
h
(QU XY ) · Myλn (QU XY )
E My1−λ
n
 

(a)
1−λ
λ
= E E Myn (QU XY ) · Myn (QU XY ) Nyn (QU Y ), Nyn (QU Y )

 


(b)
= E E My1−λ
(QU XY ) Nyn (QU Y ) · E Myλn (QU XY ) Nyn (QU Y )
n
"





(D.64)
(D.65)
!#

(D.66)

" 
!#



(QU XY ) Nyn (QU Y ) · E E Myλn (QU XY ) Nyn (QU Y ) Nyn (QU Y )
= E E My1−λ
n

(D.67)

(c)

= E E E My1−λ
(QU XY ) Nyn (QU Y ) · E Myλn (QU XY ) Nyn (QU Y )
n

Nyn (QU Y )

(d)

 


 
λ
n
n
n
≤ E E My1−λ
(Q
)
)
),
N
(Q
)
=
0
N
(Q
)
·
E
E
M
(Q
N
(Q
n
U XY
y
UY
y
UY
y
U XY
UY
yn
!


h
i
1−λ
λ
,
= E Myn (QU XY ) · E E Myn (QU XY ) Nyn (QU Y ), Nyn (QU Y ) = 0

(D.68)
(D.69)

54

where (a) and (c) follows from the law of total expectation, and (b) follows from the Markov relation (D.57). To see
(d) note that E[Myλn (QU XY )|Nyn (QU Y ) = s] is a non-decreasing function of s [see (D.8)]. In addition, conditioned

on Nyn (QU Y ) = s, Nyn (QU Y ) is a binomial random variable pertaining to less enρc − Nyn (QU Y ) ≤ enρc trials.
Thus, (d) follows from Lemma 20. We now note that
 

λ
n
n
E E Myn (QU XY ) Ny (QU Y ), Ny (QU Y ) = 0

(D.70)

and

 
h
i
λ
= E Myλn (QU XY )
E E Myn (QU XY ) Nyn (QU Y )

(D.71)

are both moments of binomial random variables with the same number of trials, but the former has a success
probability
.
P [(U n , y n ) ∈ Tn (QU Y )] = e−nIQ (U ;Y ) ,

(D.72)

and the latter has a success probability


P (U n , y n ) ∈ Tn (QU Y )| (U n , y n ) 6∈ Tn (QU Y ) .

(D.73)

However, (D.59) shows that the latter success probability has the same exponential order. In turn, the proof of
Lemma 19 shows that the exponential order of this expectation only depends on the exponential order of the
success probability. Consequently,

 
λ
E E Myn (QU XY ) Nyn (QU Y ), Nyn (QU Y ) = 0
 !

.
λ
= E E Myn (QU XY ) Nyn (QU Y )
h
i
= E Myλn (QU XY ) .

(D.74)
(D.75)

Using this in (D.69) completes the proof.
Next, we move to the case where the cloud centers may be the same, i.e., QU Y = QU Y . In this case, correlation
(QU XY ) and Myλn (QU XY ) is possible even asymptotically. Apparently, this is due to the fact
between My1−λ
n

that Nyn (QU Y ) = 0 with high probability whenever IQ (U ; Y ) > ρc , and thus, in this case, Myn (QU XY ) =
(QU XY ) and Myλn (QU XY ) are
Myn (QU XY ) = 0 with high probability. However, as we will next show, My1−λ
n

asymptotically uncorrelated when conditioned on Nyn (QU Y ).
To show this, we first need a result analogous to Lemma 21. To this end, we first need to exclude possible QU Y
from the discussion. Let us say that (QU X , QU Y ) is a joint-distribution-dictator (JDD) pair if it determines QU XY
unambiguously. For example, when |U |= |X |= |Y|= 2, QX|U corresponds to a Z-channel and QY |U corresponds to
an S-channel,24 (QU X , QU Y ) is a JDD pair. Clearly, in this case no QU XY 6= QU XY exists with the same (U, X)
24

That is QY |U (0|1) = QX|U (1|0) = 0 and all other transition probabilities are non-zero.

55

and (U, Y ) marginals, and thus such QU Y are of no interest to the current discussion.
By carefully observing the Z-channel/S-channel example above, it is easy to verify if for all u ∈ U either
supp(QX|U =u∗ ) < 2 or supp(QY |U =u∗ ) < 2 then (QU X , QU Y ) is a JDD pair. Therefore, if (QU X , QU Y ) is not a

JDD pair then there must exist u∗ ∈ U such that both supp(QX|U =u∗ ) ≥ 2 and supp(QY |U =u∗ ) ≥ 2. This property
will be used in the proof of the following lemma.
Lemma 23. Let QU XY ∈ P(U × X × Y) be given such that supp(QX ) ≥ 2, supp(QY ) ≥ 2, and (QU X , QU Y )

is not a JDD pair. Also, let (un , y n ) ∈ Tn (QU Y ) and assume that X n is distributed uniformly over Tn (QX|U , un ).
Then, for any given ǫ > 0 there exists n0 (QU X , QU Y ) such that for all n ≥ n0 (QU X , QU Y )
P [(un , X n , y n ) ∈ Tn (QU XY )] ≤ ǫ.

(D.76)

Proof: Had X n been distributed uniformly over Tn (QX ), the claim would follow directly from Lemma 21,

where y n and U n there are replaced by (un , y n ) and X n , respectively. However, since X n is distributed uniformly

over Tn (QX|U , un ) the proof is not immediate. Nonetheless, it follows the same lines, and thus we will only
highlight the required modifications.
Just as in (D.39), the size of a conditional type class can be shown to satisfy
Tn (QX|U , un ) ∼
=

1

Y

u∈supp(QU )

exp {nQU (u) · HQ (X|U = u)} · [nQU (u)]− 2 [supp(QX|U =u )−1]

(D.77)

and thus
P [(un , X n , y n ) ∈ Tn (QU XY )]
=
(a)

∼
=

Tn (QX|U Y , un , y n )

Q

(D.78)

Tn (QX|U , un )

(u,y)∈supp(QU Y ) exp {nQU Y (u, y)

1

· HQ (X|U = u, Y = Y )} · [nQU Y (u, y)]− 2 [supp(QX|U =u,Y =y )−1]
1

− 2 [supp(QX|U =u )−1]
u∈supp(QU ) exp {nQU (u) · HQ (X|U = u)} · [nQU (u)]

Q

1

= e−n·IQ (X;Y |U ) · n 2

P

1
u∈supp(QU ) [supp(QX|U =u )−1]− 2

where
def

c(QU Y ) =

Q

X

u∈supp(QU )

(a)

=

1
2

X



Q

u∈supp(QU )

1

X

(u,y)∈supp(QU Y )

 1
supp(QX|U =u ) − 1 −
2

· c(QU Y ),

(D.80)

.

(D.81)

1

(u, y)− 2 [supp(QX|U =u,Y =y )−1]

− 2 [supp(QX|U =u )−1]
u∈supp(QU ) QU (u)

 1
supp(QX|U =u ) − 1 −
2


(u,y)∈supp(QU Y ) [supp(QX|U =u,Y =y )−1]

(u,y)∈supp(QU Y ) QU Y

Now, suppose that IQ (X; Y |U ) = 0. Then,
1
2

P

(D.79)

X




supp(QX|U =u,Y =y ) − 1

(u,y)∈supp(QU Y )




supp(QX|U =u ) − 1

(D.82)

56

=

1
2

1
=
2

X




X



u∈supp(QU )

(b)

u∈supp(QU )

1
≤− ,
2




supp(QX|U =u ) − 1 −

X

y∈supp(QY |U =u )




supp(QX|U =u ) − 1




1 − supp(QY |U =u ) supp(QX|U =u ) − 1

(D.83)
(D.84)
(D.85)

where (a) follows since QX|U =u = QX|U =u,Y =y for all u ∈ supp(QU ), and (b) follows since (QU X , QU Y ) is not

a JDD pair, and thus there must exist u∗ ∈ supp(QU ) such that both supp(QX|U =u∗ ) ≥ 2 and supp(QX|U =u∗ ) ≥ 2
(as noted before the statement of the lemma). Thus, when IQ (X; Y |U ) = 0 we get
P [(un , X n , y n ) ∈ Tn (QU XY )] ≤

c(QU Y )
√
.
n

(D.86)

The proof then may continue as the proof of Lemma 21. One can find η > 0 sufficiently small such that any
n
o
Q̃U XY ∈ Q̃U XY : kQ̃U XY − QU × QX|U × QY |U k1 ≤ η has the same support as QU × QX|U × QY |U (at least

conditioned on u∗ ). Further, one can find δ(η, QU X , QU Y ) > 0 such that
n

o n
o
Q̃U XY : IQ̃ (X; Y |U ) ≤ δ ⊆ Q̃U XY : kQ̃U XY − QU × QX|U × QY |U k1 ≤ η ,

(D.87)

and the two cases considered in Lemma 21 can be considered here as well. In the first case, IQ (X; Y |U ) may
vanish, but supp(QU XY ) = supp(QU × QX|U × QY |U ) and thus (D.86) holds. In the second case IQ (X; Y |U ) ≥ δ,
and thus for any given ǫ > 0 there exists n0 (QU X , QU Y ) such that
P [(un , X n , y n ) ∈ Tn (QU XY )] ≤ e−nIQ (X;Y |U ) · n|U ||X | · c(QU Y ) ≤ ǫ

(D.88)

for all n ≥ n0 (QU X , QU Y ).
Lemma 24. Let (QU XY , QU XY ) be given such that QU Y = QU Y . Then,






.
1−λ
λ
1−λ
λ
E Myn (QU XY )Myn (QU XY ) Nyn (QU Y ) = E Myn (QU XY ) Nyn (QU Y ) · E Myn (QU XY ) Nyn (QU Y ) .

(D.89)

Proof: The proof follows the same lines of the proof of Lemma 22, and so we only provide a brief outline.
For a lower bound on the conditional correlation, one can decompose
Myn (QU XY ) = Myn (QU XY , 1) + Myn (QU XY , 2)

(D.90)

where Myn (QU XY , 1) [respectively, Myn (QU XY , 2)] corresponds to codewords of odd (even) satellite indices (say).
For a asymptotically matching upper bound on the correlation, we note that similarly to (D.59), when X n is
drawn uniformly over Tn (QX|U , un ),
h
i
P (un , X n , y n ) ∈ Tn (QU XY ) (un , X n , y n ) 6∈ Tn (QU XY )

(D.91)

57

is close to the unconditional probability, in the sense that for any given ǫ > 0,
h
i
P [(un , X n , y n ) ∈ Tn (QU XY )] ≤ P (U n , y n ) ∈ Tn (QU Y ) (U n , y n ) 6∈ Tn (QU Y )
≤

1
· P [(un , X n , y n ) ∈ Tn (QU XY )] . (D.92)
1−ǫ

To prove this, a derivation similar to (D.62) can be used, while noting that (QU X , QU Y ) is not a JDD pair, and so
according to Lemma 23


P (un , X n , y n ) ∈ Tn (QU XY ) ≤ ǫ

for all n sufficiently large. Equipped with these results, we get


λ
1−λ
E Myn (QU XY )Myn (QU XY ) Nyn (QU Y )




(a)
1−λ
λ
= E Myn (QU XY ) · E Myn (QU XY ) Nyn (QU Y ), Myn (QU XY ) Nyn (QU Y )




(b)
λ
1−λ
≤ E Myn (QU XY ) · E Myn (QU XY ) Nyn (QU Y ), Myn (QU XY ) = 0 Nyn (QU Y )

(D.93)

(D.94)
(D.95)

(c)





.
λ
1−λ
= E Myn (QU XY ) Nyn (QU Y ) · E Myn (QU XY ) Myn (QU XY ) ,

(D.96)

where (a) follows from the law of total expectation. For (b) note that conditioned on both Nyn (QU Y ), Myn (QU XY ),
Myn (QU XY ) is a binomial random variable pertaining to Nyn (QU Y )enρs − Myn (QU XY ) ≤ Nyn (QU Y )enρs trials.

(QU XY )|Nyn (QU Y ), Myn (QU XY ) = s] is a non-increasing function of s [see (D.8)], and (b) follows
Thus, E[My1−λ
n

from Lemma 20. For (c), we note that from (D.92), the conditioning on Myn (QU XY ) = 0 does not change the
exponential order of the success probability of Myn (QU XY ). As evident from (D.8), this conditioning can be
removed without changing the exponential order of the expression.
Proceeding with the case of QU Y = QU Y , we next evaluate the expectation over Nyn (QU Y ). We show that the
asymptotic uncorrelation result of Lemma 22 holds, albeit with a correction term required when IQ (U ; Y ) > ρc .
Lemma 25. Let δ > 0, and (QU XY , QU XY ) be given such that QU Y = QU Y . Then,
i
i
h
i
h
h
.
1−λ
λ
λ
)
)
· en|IQ (U ;Y )−ρc |+ .
=
E
M
(Q
)
·
E
M
(Q
E My1−λ
(Q
)M
(Q
n
U XY
U XY
U XY
U XY
yn
yn
yn

(D.97)

Proof: We consider two cases separately. First suppose that IQ (U ; Y ) ≤ ρc . In this case, Nyn (QU Y ) concentrates double-exponentially fast around its expected value, where the latter equals exp[n(ρc − IQ (U ; Y ))] up to the
first order in the exponent. Thus, the conditional expectation and the unconditional expectation are equal up to the
first order in the exponent. More rigorously, let δ > 0 be given and recall the definition of the event Bn (QU Y , δ)
in (D.2). Then,


h
i
1−λ
1−λ
E Myn (QU XY ) = P [Nyn (QU Y ) ∈ Bn (QU Y , δ)] · E Myn (QU XY ) Nyn (QU Y ) ∈ Bn (QU Y , δ)

58



c
n
N
(Q
)
∈
B
(Q
,
δ)
(Q
)
+ P [Nyn (QU Y ) ∈ Bnc (QU Y , δ)] · E My1−λ
n
y
UY
UY
U XY
n

(D.98)

(a)



.
1−λ
n
= E Myn (QU XY ) Ny (QU Y ) ∈ Bn (QU Y , δ)


(b)
−nδ
1−λ
≥e
· E Myn (QU XY ) Nyn (QU Y ) = E [Nyn (QU Y )] ,

(D.99)
(D.100)

where (a) follows from the fact P[Bn (QU Y , δ)] decays double-exponentially [see (D.3)], and (b) follows from
(D.8). Similarly


h
i
λ
−nδ
λ
˙
E Myn (QU XY ) ≥ e
· E Myn (QU XY ) Nyn (QU Y ) = E [Nyn (QU Y )] .

(D.101)

Thus,
h
i
(QU XY )Myλn (QU XY )
E My1−λ
n



1−λ
λ
= P [Nyn (QU Y ) ∈ Bn (QU Y , δ)] · E Myn (QU XY )Myn (QU XY ) Nyn (QU Y ) ∈ Bn (QU Y , δ)


+ P [Nyn (QU Y ) ∈ Bnc (QU Y , δ)] · E My1−λ
(QU XY )Myλn (QU XY ) Nyn (QU Y ) ∈ Bnc (QU Y , δ)
n

(D.102)

(a)



.
λ
n
= E My1−λ
(Q
)M
(Q
)
N
(Q
)
∈
B
(Q
,
δ)
n
U XY
y
UY
n
UY
U XY
yn


X
λ
1−λ
=
P [Nyn (QU Y ) = s] · E Myn (QU XY )Myn (QU XY ) Nyn (QU Y ) = s

(D.103)
(D.104)

s∈Bn (QU Y ,δ)

(b)

.
=

X

s∈Bn (QU Y ,δ)

P [Nyn (QU Y ) = s] · E



(QU XY
My1−λ
n



) Nyn (QU Y ) = s · E



Myλn (QU XY

) Nyn (QU Y ) = s



(D.105)
(c)

≤ e2nδ · P [Nyn (QU Y ) ∈ Bn (QU Y , δ)]




1−λ
λ
× E Myn (QU XY ) Nyn (QU Y ) = E [Nyn (QU Y )] · E Myn (QU XY ) Nyn (QU Y ) = E [Nyn (QU Y )]

(D.106)




(d)
.
λ
n
n
n
n
= e2nδ · E My1−λ
(Q
)
N
(Q
)
=
E
[N
(Q
)]
·
E
M
(Q
)
N
(Q
)
=
E
[N
(Q
)]
n
U XY
y
UY
y
UY
y
UY
y
UY
U XY
yn

(D.107)

(e)

o
n
n
o
˙ e4nδ · E My1−λ
(QU XY ) · E Myλn (QU XY ) ,
≤
n

(D.108)

where (a) and (d) follow from (D.3), (b) follows from Lemma 24, (c) from (D.8), and (e) from (D.100) and
(D.101).
We next address the case IQ (U ; Y ) > ρc . In this case, Nyn (QU Y ) = 0 with high probability, 1 ≤ Nyn (QU Y ) ≤

e2nδ with probability exp{−n[IQ (U ; Y ) − ρc ]}, and Nyn (QU Y ) ≥ e2nδ with probability double-exponentially small

=1
≥1
[see (D.4) and (D.5)]. For brevity, we will use the definitions of A=0
n (QU Y ), An (QU Y ) and An (QU Y , δ) in

59

(D.11)-(D.13). Then,


i
h
 =0

=0
1−λ
1−λ
E Myn (QU XY ) = P An (QU Y ) · E Myn (QU XY ) An (QU Y )


 =1

=1
1−λ
+ P An (QU Y , δ) · E Myn (QU XY ) An (QU Y , δ)




≥1
1−λ
A
(Q
,
δ)
(Q
)
+ P A≥1
(Q
,
δ)
·
E
M
n
UY
U XY
UY
n
n
y

(D.109)

(a)





.
1−λ
=1
= 0 + P A=1
(Q
,
δ)
·
E
M
(Q
)
A
(Q
,
δ)
UY
U XY
UY
yn
n
n


(b)
 =1

1−λ
nδ
≤ e · P An (QU Y , δ) · E Myn (QU XY ) Nyn (QU Y ) = 1 ,

where for (a) and (b) we apply (D.5) and (D.8), respectively. Similarly,


h
i
 =1

λ
nδ
λ
˙
E Myn (QU XY ) ≤ e · P An (QU Y , δ) · E Myn (QU XY ) Nyn (QU Y ) = 1 .

(D.110)
(D.111)

(D.112)

Then,

i
h
E My1−λ
(QU XY )Myλn (QU XY )
n




(a)
 =1

2nδ
1−λ
λ
˙
≤e
· P An (QU Y , δ) · E Myn (QU XY ) Nyn (QU Y ) = 1 · E Myn (QU XY ) Nyn (QU Y ) = 1
i
h
i
h
1
1−λ
λ
˙ e4nδ ·
)
·
E
M
(Q
)
·
E
M
(Q
≤
n
n
U
XY
U XY
y
y
P [A=1
n (QU Y , δ)]
i
h
h
i
(b)
.
(QU XY ) · E Myλn (QU XY ) ,
= e4nδ · en[IQ (U ;Y )−ρc ] · E My1−λ
n

(D.113)
(D.114)
(D.115)

where (a) follows from a derivation similar to (D.108), and (b) follows from (D.4).
(QU XY )Myλn (QU XY )] for both cases can be obtained in the
Analogous asymptotic lower bounds on E[My1−λ
n

same manner, when δ is replaced by (−δ). The proof is then completed by taking δ ↓ 0.
Using all the above, we are now ready to prove Proposition 15.
Proof of Prop. 15: For the first case of (C.4)
h
i
(QU XY )Myλn (QU XY ) = E [Myn (QU XY )] ,
E My1−λ
n

(D.116)

and the result follows from Lemma 19 with λ = 1. For the second case, using Lemma 22
i
i
h
i
h
h
.
(QU XY ) · E Myλn (QU XY ) ,
E My1−λ
(QU XY )Myλn (QU XY ) = E My1−λ
n
n

(D.117)

and the result follows from Lemma 19. Similarly, the third case follows from Lemmas 25 and 19. Specifically,
the result is just as in the second case, except for the correction term |IQ (U ; Y ) − ρc |+ to the exponent. Standard
manipulations lead to the expression shown in the third case.

60

R EFERENCES
[1] H. V. Poor, An Introduction to Signal Detection and Estimation, 2nd ed.

Springer-Verlag, 1994.

[2] R. E. Blahut, “Hypothesis testing and information theory,” IEEE Transactions on Information Theory, vol. 20, no. 4, pp. 405–417, July
1974.
[3] T. M. Cover and J. A. Thomas, Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing). WileyInterscience, 2006.
[4] I. Csiszár and J. Körner, Information Theory: Coding Theorems for Discrete Memoryless Systems. Cambridge University Press, 2011.
[5] I. Csiszár and P. C. Shields, Information Theory and Statistics: A Tutorial, ser. Foundations and Trends in Communications and
Information Theory.

Now Publishers Inc, 2004.

[6] T. Berger, “Decentralized estimation and decision theory,” in IEEE Seven Springs Workshop on Information Theory, Mt. Kisco, NY,
1979.
[7] R. Ahlswede and I. Csiszár, “Hypothesis testing with communication constraints,” IEEE Transactions on Information Theory, vol. 32,
no. 4, pp. 533–542, July 1986.
[8] R. Ahlswede, P. Gács, and J. Körner, “Bounds on conditional probabilities with applications in multi-user communication,” Probability
Theory and Related Fields, vol. 34, no. 2, pp. 157–177, 1976.
[9] R. Ahlswede and J. Körner, “Source coding with side information and a converse for degraded broadcast channels,” IEEE Transactions
on Information Theory, vol. 21, no. 6, pp. 629–637, November 1975.
[10] T. S. Han and S. Amari, “Statistical inference under multiterminal data compression,” IEEE Transactions on Information Theory,
vol. 44, no. 6, pp. 2300–2324, October 1998.
[11] T. S. Han, “Hypothesis testing with multiterminal data compression,” IEEE Transactions on Information Theory, vol. 33, no. 6, pp.
759–772, November 1987.
[12] T. S. Han and K. Kobayashi, “Exponential-type error probabilities for multiterminal hypothesis testing,” IEEE Transactions on
Information Theory, vol. 35, no. 1, pp. 2–14, January 1989.
[13] H. Shimokawa, T. S. Han, and S. Amari, “Error bound of hypothesis testing with data compression,” in Proc. IEEE International
Symposium Information Theory (ISIT), June 1994, pp. 114–.
[14] Y. Polyanskiy, “Hypothesis testing via a comparator,” in Proc. IEEE International Symposium Information Theory (ISIT), July 2012,
pp. 2206–2210, extended version available online: http://people.lids.mit.edu/yp/homepage/data/htstruct_journal.pdf.
[15] H. M. H. Shalaby and A. Papamarcou, “Multiterminal detection with zero-rate data compression,” IEEE Transactions on Information
Theory, vol. 38, no. 2, pp. 254–267, March 1992.
[16] C. Tian and J. J. Chen, “Successive refinement for hypothesis testing and lossless one-helper problem,” IEEE Transactions on Information
Theory, vol. 54, no. 10, pp. 4666–4681, October 2008.
[17] M. S. Rahman and A. B. Wagner, “On the optimality of binning for distributed hypothesis testing,” IEEE Transactions on Information
Theory, vol. 58, no. 10, pp. 6282–6303, October 2012.
[18] G. Katz, P. Piantanida, and M. Debbah, “Collaborative distributed hypothesis testing,” arXiv preprint, April 2016, available online:
http://arxiv.org/pdf/1604.01292.pdf.
[19] Y. Xiang and Y. H. Kim, “Interactive hypothesis testing against independence,” in Proc. IEEE International Symposium Information
Theory (ISIT), July 2013, pp. 2840–2844.
[20] M. Mhanna and P. Piantanida, “On secure distributed hypothesis testing,” in Proc. IEEE International Symposium Information Theory
(ISIT), June 2015, pp. 1605–1609.
[21] G. Katz, P. Piantanida, and M. Debbah, “Distributed binary detection with lossy data compression,” IEEE Transactions on Information
Theory, 2017.
[22] S. Sreekumar and D. Gündüz, “Distributed hypothesis testing over noisy channels,” in Proc. IEEE International Symposium Information
Theory (ISIT), June 2017, pp. 983–987.

61

[23] E. Tuncel, “On error exponents in hypothesis testing,” IEEE Transactions on Information Theory, vol. 51, no. 8, pp. 2945–2950, August
2005.
[24] S. Salehkalaibar, M. Wigger, and R. Timo, “On hypothesis testing against independence with multiple decision centers,” arXiv preprint,
August 2017, available online: http://arxiv.org/pdf/1708.03941.pdf.
[25] S. Salehkalaibar, M. Wigger, and L. Wang, “Hypothesis testing in multi-hop networks,” arXiv preprint, August 2017, available online:
http://arxiv.org/pdf/1708.05198.pdf.
[26] W. Zhao and L. Lai, “Distributed testing with zero-rate compression,” in Proc. IEEE International Symposium Information Theory
(ISIT), June 2015, pp. 2792–2796.
[27] S. Watanabe, “Neyman-Pearson test for zero-rate multiterminal hypothesis testing,” arXiv preprint, November 2016, available online:
http://arxiv.org/pdf/1611.08175.pdf.
[28] A. El Gamal and Y. Kim, Network information theory.

Cambridge university press, 2011.

[29] A. Wyner and J. Ziv, “The rate-distortion function for source coding with side information at the decoder,” IEEE Transactions on
Information Theory, vol. 22, no. 1, pp. 1–10, January 1976.
[30] S. I. Gel’fand and M. S. Pinsker, “Coding of sources on the basis of observations with incomplete information,” Problemy Peredachi
Informatsii, vol. 15, no. 2, pp. 45–57, 1979.
[31] G. Katz, R. Couillet, P. Piantanida, and M. Debbah, “On the necessity of binning for the distributed hypothesis testing problem,” in
Proc. IEEE International Symposium Information Theory (ISIT), June 2015, pp. 2797–2801.
[32] E. Haim and Y. Kochman, “Binary distributed hypothesis testing via Körner-Marton coding,” in Proc. IEEE Information Theory
Workshop (ITW), Septmber 2016, pp. 146–150.
[33] ——, “On binary distributed hypothesis testing,” Submitted to IEEE Transactions on Information Theory, December 2017, available
online: http://arxiv.org/pdf/1801.00310.pdf.
[34] J. Körner and K. Marton, “How to encode the modulo-two sum of binary sources (corresp.),” IEEE Transactions on Information Theory,
vol. 25, no. 2, pp. 219–221, March 1979.
[35] G. Katz, P. Piantanida, and M. Debbah, “A new approach to distributed hypothesis testing,” in Proc. Asilomar Conference on Signals,
Systems and Computers, November 2016, pp. 1365–1369.
[36] W. Hoeffding, “Asymptotically optimal tests for multinomial distributions,” The Annals of Mathematical Statistics, pp. 369–401, 1965.
[37] D. Slepian and J. K. Wolf, “Noiseless coding of correlated information sources,” IEEE Transactions on Information Theory, vol. 19,
no. 4, pp. 471–480, July 1973.
[38] R. Ahlswede and G. Dueck, “Good codes can be produced by a few permutations,” IEEE Transactions on Information Theory, vol. 28,
no. 3, pp. 430–443, May 1982.
[39] J. Chen, D. He, A. Jagmohan, and L. A. Lastras-Montaño, “On the reliability function of variable-rate Slepian-Wolf coding,” in Proc.
of 45th Annual Allerton Conference Communication, Control, and Computing, September 2007, extended version available online:
http://www.ece.mcmaster.ca/~junchen/IT_variableSW.pdf.
[40] N. Weinberger and N. Merhav, “Optimum trade-offs between the error exponent and the excess-rate exponent of variable-rate SlepianWolf coding,” IEEE Transactions on Information Theory, vol. 61, no. 4, pp. 2165–2190, April 2015, extended version available online:
http://arxiv.org/pdf/1401.0892v3.pdf.
[41] R. Ahlswede, “Coloring hypergraphs: A new approach to multi-user source coding, part II,” Journal of Combinatorics, vol. 5, pp.
220–268, 1980.
[42] N. Weinberger and N. Merhav, “Channel detection in coded communication,” IEEE Transactions on Information Theory, vol. 63, no. 10,
pp. 6364–6392, October 2017.
[43] P. Bergmans, “Random coding theorem for broadcast channels with degraded components,” IEEE Transactions on Information Theory,
vol. 19, no. 2, pp. 197–207, March 1973.
[44] I. Csiszár, “The method of types,” IEEE Transactions on Information Theory, vol. 44, no. 6, pp. 2505–2523, October 1998.
[45] W. Rudin, Principles of mathematical analysis, 3rd ed.

McGraw-Hill New York, 1976.

62

[46] N. Weinberger and N. Merhav, “A large deviations approach to secure lossy compression,” IEEE Transactions on Information Theory,
vol. 63, no. 4, pp. 2533–2559, April 2017.
[47] K. Marton, “Error exponent for source coding with a fidelity criterion,” IEEE Transactions on Information Theory, vol. 20, no. 2, pp.
197–199, March 1974.
[48] N. Merhav, “Statistical physics and information theory,” Foundations and Trends in Communications and Information Theory, vol. 6,
no. 1-2, pp. 1–212, 2009.
[49] S. P. Boyd and L. Vandenberghe, Convex Optimization.

Cambridge university press, 2004.

[50] I. Csiszár and G. Tusnády, “Information Geometry and Alternating Minimization Procedures,” Statistics and Decisions, vol. Supplement
Issue 1, 1984.
[51] S. Arimoto, “An algorithm for computing the capacity of arbitrary discrete memoryless channels,” IEEE Transactions on Information
Theory, vol. 18, no. 1, pp. 14–20, 1972.
[52] ——, “Computation of random coding exponent functions,” IEEE Transactions on Information Theory, vol. 22, no. 6, pp. 665–671,
November 1976.
[53] R. E. Blahut, “Computation of channel capacity and rate-distortion functions,” IEEE Transactions on Information Theory, vol. 18, no. 4,
pp. 460–473, 1972.
[54] N. Tishby, F. C. Pereira, and W. Bialek, “The information bottleneck method,” in Proc. of 37th Annual Allerton Conference
Communication, Control, and Computing, September 1999.
[55] A. Rényi, “On measures of entropy and information,” in Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics
and Probability, Volume 1: Contributions to the Theory of Statistics.

The Regents of the University of California, 1961.

[56] T. Van Erven and P. Harremos, “Rényi divergence and Kullback-Leibler divergence,” IEEE Transactions on Information Theory, vol. 60,
no. 7, pp. 3797–3820, 2014.
[57] A. Nazari, A. Anastasopoulos, and S. S. Pradhan, “Error exponent for multiple-access channels: Lower bounds,” IEEE Transactions
on Information Theory, vol. 60, no. 9, pp. 5095–5115, September 2014.
[58] A. Nazari, S. S. Pradhan, and A. Anastasopoulos, “Error exponent for multiple-access channels: Upper bounds,” IEEE Transactions on
Information Theory, vol. 61, no. 7, pp. 3605–3621, July 2015.
[59] M. Sion, “On general minimax theorems,” Pacific Journal of Mathematics, vol. 8, no. 1, pp. 171–176, 1958.
[60] A. Somekh-Baruch and N. Merhav, “Achievable error exponents for the private fingerprinting game,” IEEE Transactions on Information
Theory, vol. 53, no. 5, pp. 1827–1838, May 2007.
[61] N. Shulman, “Communication over an unknown channel via common broadcasting,” Ph.D. dissertation, Dept. Electrical Engineering,
Tel Aviv University, Tel Aviv, Israel, 2003, http://www.eng.tau.ac.il/~shulman/papers/Nadav_PhD.pdf.
[62] M. Loève, Probability Theory I. Springer, 1977.
[63] N. Merhav, “Relations between random coding exponents and the statistical physics of random codes,” IEEE Transactions on Information
Theory, vol. 55, no. 1, pp. 83–92, January 2009.

