1

On Binary Distributed Hypothesis Testing
Eli Haim and Yuval Kochman

arXiv:1801.00310v1 [] 31 Dec 2017

Abstract
We consider the problem of distributed binary hypothesis testing of two sequences that are generated by an i.i.d.
doubly-binary symmetric source. Each sequence is observed by a different terminal. The two hypotheses correspond
to different levels of correlation between the two source components, i.e., the crossover probability between the two.
The terminals communicate with a decision function via rate-limited noiseless links. We analyze the tradeoff between
the exponential decay of the two error probabilities associated with the hypothesis test and the communication rates.
We first consider the side-information setting where one encoder is allowed to send the full sequence. For this setting,
previous work exploits the fact that a decoding error of the source does not necessarily lead to an erroneous decision
upon the hypothesis. We provide improved achievability results by carrying out a tighter analysis of the effect of
binning error; the results are also more complete as they cover the full exponent tradeoff and all possible correlations.
We then turn to the setting of symmetric rates for which we utilize Körner-Marton coding to generalize the results,
with little degradation with respect to the performance with a one-sided constraint (side-information setting).

I. I NTRODUCTION
We consider the distributed hypothesis testing (DHT) problem, where there are two distributed sources, X and
Y , and the hypotheses are given by
(0)

H0 : (X, Y ) ∼ PX,Y
(1)

H1 : (X, Y ) ∼ PX,Y ,
(0)

(1a)
(1b)

(1)

where PX,Y and PX,Y are different joint distributions of X and Y . The test is performed based on information
sent from two distributed terminals (over noiseless links), each observing n i.i.d. realizations of a different source,
where the rate of the information sent from each terminal is constrained. This setup, introduced in [1, 2], introduces
a tradeoff between the information rates and the probabilities of the two types of error events. In this work we
focus on the exponents of these error probabilities, with respect to the number of observations n.
When at least one of the marginal distributions depends on the hypothesis, a test can be constructed based only on
the type of the corresponding sequence. Although this test may not be optimal, it results in non-trivial performance
(positive error exponents) with zero rate. In contrast, when the marginal distributions are the same under both
hypotheses, a positive exponent cannot be achieved using a zero-rate scheme, see [3].
One may achieve positive exponents while maintaining low rates, by effectively compressing the sources and then
basing the decision upon their compressed versions. Indeed, many of the works that have considered the distributed
hypothesis testing problem bear close relation to the distributed compression problem.

January 3, 2018

DRAFT

2

Ahlswede and Csiszár [4] have suggested a scheme based on compression without taking advantage of the
correlation between the sources; Han [5] proposed an improved scheme along the same lines. Correlation between
the sources is exploited by Shimokawa et al. [6, 7] to further reduce the coding rate, incorporating random binning
following the Slepian-Wolf [8] and Wyner-Ziv [9] schemes. Rahman and Wagner [10] generalized this setting and
also derived an outer bound. They also give a “quantize and bin” interpretation to the results of [6]. Other related
works include [11–15]. See [16, 10] for further references.
We note that in spite of considerable efforts over the years, the problem remains open. In many cases, the gap
between the achievability results and the few known outer bounds is still large. Specifically, some of the stronger
results are specific to testing against independence (i.e., under one of the hypotheses X and Y are independent),
or specific to the case where one of the error exponents is zero (“Stein’s-Lemma” setting). The present work
significantly goes beyond previous works, extending and improving the achievability bounds. Nonetheless, the
refined analysis comes at a price. Namely, in order to facilitate analysis, we choose to restrict attention to a simple
source model.
To that end, we consider the case where (X, Y ) is a doubly symmetric binary source (DSBS). That is, X and Y
△

are each binary and symmetric. Let Z = Y ⊖ X be the modulo-two difference between the sources.1 We consider
the following two hypotheses:
H0 : Z ∼ Ber (p0 )

(2a)

H1 : Z ∼ Ber (p1 ) ,

(2b)

where we assume throughout that p0 ≤ p1 ≤ 1/2. Note that a sufficient statistic for hypothesis testing in this case
is the weight (which is equivalent to the type) of the noise sequence Z. Under communication rate constraints,
a plausible approach would be to use a distributed compression scheme that allows lossy reconstruction of the
sequence Z, and then base the decision upon that sequence.
We first consider a one-sided rate constraint. That is, the Y -encoder is allocated the full rate of one bit per source
sample, so that the Y sequence is available as side information at the decision function. In this case, compression
of Z amounts to compression of X; a random binning scheme is optimal for this task of compression, lossless or
lossy.2 Indeed, in this case, the best known achievability result is due to [6], which basically employs a random
binning scheme.3
A natural question that arises when using binning as part of the distributed hypothesis testing scheme is the effect
of a “bin decoding error” on the decision error between the hypotheses. The connection between these two errors
is non-trivial as a bin decoding error inherently results in a “large” noise reconstruction error, much in common
with errors in channel coding (in the context of syndrome decoding). Specifically, when a binning error occurs,
1 Notice
2 More

that in this binary case, the uniform marginals mean that Z is necessarily independent of X.

precisely, it gives the optimal coding rates, as well as the best known error exponents when the rate is not too high.

3 Interestingly,

when p1 = 1/2 (testing against independence), the simple scheme of [4] which ignores the side-information altogether is

optimal.

January 3, 2018

DRAFT

3

the reconstruction of the noise sequence Z is roughly consistent with an i.i.d. Bernoulli 1/2 distribution. Thus, if
one feeds the weight of this reconstructed sequence to a simple threshold test, it would typically result in deciding
that the noise was distributed according to p1 , regardless of whether that is the true distribution or not. This effect
causes an asymmetry between the two error probabilities associated with the hypothesis test. Indeed, as the Stein
exponent corresponds to highly asymmetric error probabilities, the exponent derived in [6] may be interpreted as
taking advantage of this effect.4
The contribution of the present work is twofold. First we extend and strengthen the results of [6]. By explicitly
considering and leveraging the properties of good codes, we bound the probability that the sequence Z happens
to be such that Y ⊖ Z is very close to some wrong yet “legitimate” X, much like an undetected error event in
erasure decoding [17]. This allows us to derive achievability results for the full tradeoff region, namely the tradeoff
between the error exponents corresponding to the two types of hypothesis testing errors.
The second contribution is in considering a symmetric-rate constraint. For this case, the optimal distributed
compression scheme for Z is the Körner-Marton scheme [18], which requires each of the users to communicate at
a rate H (Z); hence, the sum-rate is strictly smaller than the one of Slepian-Wolf, unless Z is symmetric. Thus,
the Körner-Marton scheme is a natural candidate for this setting. Indeed, it was observed in [4, 16] that a standard
information-theoretic solution such as Slepian-Wolf coding may not always be the way to go, and [16] mentions the
the Körner-Marton scheme in this respect. Further, Shimokawa and Amari [19] point out the possible application
of the Körner-Marton scheme to distributed parameter estimation in a similar setting and a similar observation is
made in [20]. However, to the best of our knowledge, the present work is the first to propose an actual KörnerMarton-based scheme for distributed hypothesis testing and to analyze its performance. Notably, the performance
tradeoff obtained recovers the achievable tradeoff derived for a one-sided constraint.
The rest of this paper is organized as follows. In Section II we formally state the problem, define notations and
present some basic results. Section III and IV provide necessary background: the first surveys known results for
the case of a one-sided rate constraint while the latter provides definitions and properties of good linear codes. In
Section V we present the derivation of a new achievable exponents tradeoff region. Then, in Section VI we present
our results for a symmetric-rate constraint. Numerical results and comparisons appear in Section VII. Finally,
Section VIII concludes the paper.
II. P ROBLEM S TATEMENT AND N OTATIONS
A. Problem Statement
Consider the setup depicted in Figure 1. X and Y are random vectors of blocklength n, drawn from the (finite)
source alphabets X and Y, respectively. Recalling the hypothesis testing problem (1), we have two possible i.i.d.
distributions. In the sequel we will take a less standard notational approach, and define the hypotheses by random
variable H which takes the values 0, 1, and assume a probability distribution function PX,Y |H ; Therefore H = i
4 Another interesting direction, not pursued in this work, is to change the problem formulation to allow declaring an “erasure” when the
probability of a bin decoding error exceeds a certain threshold.

January 3, 2018

DRAFT

4

φX

X

iX ∈ MX

ψ

φY

Y

Fig. 1.

Ĥ

iY ∈ MY

Problem setup.

(i)

refers to Hi of (1) and (2).5 We still use for the distribution PX,Y |H=i (for i = 0, 1) the shortened notation PX,Y .
Namely, for any x ∈ X n and y ∈ Y n , and for i ∈ {0, 1},
P (X = x, Y = y|H = i) =

n
Y

(i)

PX,Y (xj , yj ).

j=1

A scheme for the problem is defined as follows.
△

Definition 1: A scheme Υ = (φX , φY , ψ) consists of encoders φX and φY which are mappings from the set of
length-n source vectors to the messages sets MX and MY :
φX : X n 7→ MX

(3a)

φY : Y n 7→ MY .

(3b)

and a decision function, which is a mapping from the set of possible message pairs to one of the hypotheses:
ψ : MX × MY 7→ {0, 1}.

(4)

Definition 2: For a given scheme Υ, denote the decision given the pair (X, Y) by
△

Ĥ = ψ (φX (X), φY (Y)) .

(5)

The decision error probabilities of Υ are given by


△
ǫi = P Ĥ 6= H H = i ,

i = 0, 1.

(6a)

Definition 3: For any E0 > 0 and E1 > 0, the exponent pair (E0 , E1 ) is said to be achievable at rates (RX , RY )
if there exists a sequence of schemes


△
(n)
(n)
Υ(n) = φX , φY , ψ (n) ,
5 We

n = 1, 2, . . .

(7)

do not assume any given distribution over H, as we are always interested in probabilities given the hypotheses.

January 3, 2018

DRAFT

5

(n)

(n)

with corresponding sequences of message sets MX and MY

(n)

and error probabilities ǫi , i ∈ {0, 1}, such that6

1
(n)
log MX ≤ RX
n
1
(n)
lim sup log MY ≤ RY ,
n→∞ n

lim sup

(8a)

n→∞

(8b)

and
lim inf −
n→∞

1
(n)
log ǫi ≥ Ei ,
n

i = 0, 1.

(8c)

The achievable exponent region C (RX , RY ) is the closure of the set of all achievable exponent pairs.7
The case where only one of the error probabilities decays exponentially is of special interest; we call the resulting
(n)

quantity the Stein exponent after Stein’s Lemma (see, e.g., [21, Chapter 12]). When ǫ1

is exponential, the Stein

exponent is defined as:
△

σ1 (RX , RY ) = sup {E1 : ∃(E0 , E1 ) ∈ C (RX , RY )} .

(9)

E0 >0

σ0 (RX , RY ) is defined similarly.
We will concentrate on this work on two special cases of rate constraints, where for simplicity we can make the
notation more concise.
1) One-sided constraint where RY = ∞. We shall denote the achievable region and Stein exponents as CX (RX ),
σX,0 (RX ) and σX,1 (RX ).
2) Symmetric constraint where RX = RY = R. We shall denote the achievable region and Stein exponents as
C (R), σ0 (R) and σ1 (R).
Note that for any R we have that C (R) ⊆ CX (R).
Whenever considering a specific source distribution, we will take (X, Y ) to be a DSBS. Recalling (2), that means
△

that X and Y are binary symmetric, and the “noise” Z = Y ⊖ X satisfies:
P (Z = 1|H = i) = pi ,

i = 0, 1

(10)

for some parameters 0 ≤ p0 ≤ p1 ≤ 1/2 (note that there is loss of generality in assuming that both probabilities
are on the same side of 1/2).
B. Further Notations
The following notations of probability distribution functions are demonstrated for random variables X, Y and Z
over alphabets X , Y and Z, respectively. The probability distribution function of a random variable X is denoted
by PX , and the conditional probability distribution function of a random variable Y given a random variable X is
6 All

logarithms are taken to the base 2, and all rates are in units of bits per sample.

7 For

simplicity of the notation we omit here and in subsequent definitions the explicit dependence on the distributions (P (0) , P (1) ).

January 3, 2018

DRAFT

6

denoted by PY |X . A composition PX and PY |X is denoted by PX PY |X , leading to the following joint probability
distribution function PX,Y of X and Y :

△
PX PY |X (x, y) = PX (x)PY |X (y|x),

(11)

for any pair x ∈ X and y ∈ Y.
The Shannon entropy of a random variable X is denoted by H (PX ), and the Kullback-Leibler divergence of
a pair of probability distribution functions (P, Q) is denoted by D (P kQ). The mutual information of a pair of

random variables (X, Y ) is denoted by I PX , PY |X . The similar conditional functionals of the entropy, divergence

and mutual information are defined by an expectation over the a-priori distribution: the conditional entropy of a
random variable X given a random variable Z is denoted by
X
△ X
H PX|Z PZ =
PX (x)
PY |X (y|x) log
x∈X

y∈Y

1
.
PY |X (y|x)

(12)

The divergence of a pair of conditional probability distribution functions PX|Z and PY |Z is denoted by

D PX|Z kPY |Z PZ .
The conditional mutual information of a pair of random variables (X, Y ) given a random variable Z is denoted by

I PX|Z , PY |X,Z PZ ,
and notice that it is equal to


H PX|Z PZ − H PX|Y,Z PZ PX|Z .
If there is a Markov chain Z ↔ X ↔ Y , then we can omit the Z from PY |X,Z and the expression becomes

I PX|Z , PY |X PZ .
Since we concentrate on a binary case, we need the following. Denote the binary divergence of a pair (p, q),
where p, q ∈ (0, 1), by
△

Db (pkq) = p log

1−p
p
+ (1 − p) log
,
q
1−q

(13)

which is the Kullback-Leibler divergence of the pair of probability distributions ((p, 1 − p), (q, 1 − q)). Denote the
binary entropy of p ∈ (0, 1) by
△

Hb (p) = p log

1
1
+ (1 − p) log
,
p
1−p

(14)

which is the entropy function of the probability distribution (p, 1 − p). Denote the Gilbert-Varshamov relative

January 3, 2018

DRAFT

7

distance of a code of rate R, δGV : [0, 1] 7→ [0, 1/2] by
△

δGV (R) = Hb−1 (1 − R).

(15)

The operator ⊕ denotes addition over the binary field. The operator ⊖ is equivalent to the ⊕ operator over the
binary field, but nevertheless, we keep them for the sake of consistency.
The Hamming weight of a vector u = (u1 , . . . , un ) ∈ {0, 1}n is denoted by
wH (u) =

n
X

1{ui =1} ,

(16)

k=1

where 1{·} denotes the indicator function, and the sum is over the reals. The normalized Hamming weight of this
vector is denoted by
δH (u) =

1
wH (u).
n

(17)

Denote the n dimensional Hamming ball with center c and normalized radius r ∈ [0, 1] by
△

Bn (c, r) = {x ∈ {0, 1}n|δH (x ⊖ c) ≤ r} ,

(18)

The binary convolution of p, q ∈ [0, 1] is defined by
△

p ∗ q = (1 − p)q + p(1 − q).

(19)

Definition 4 (Bernoulli Noise): A Bernoulli random variable Z with P (Z = 1) = p is denoted by Z ∼ Ber (p).
An n dimensional random vector Z with i.i.d. entries Zi ∼ Ber (p) for i = 1, . . . , n is called a Bernoulli noise, and
denoted by
Z ∼ BerV (n, p)

(20)

Definition 5 (Fixed-Type Noise): Denote the set of vectors with type a ∈ [0, 1] by
△

Tn (a) = {x ∈ {0, 1}n : δH (x) = a}.

(21a)

N ∼ Uniform (Tn (a))

(21b)

A noise

is called an n-dimensional fixed-type noise of type a ∈ [0, 1].
.
−1
∞
log(an /bn ) = 0. We write
For any two sequences, {an }∞
n=1 and {bn }n=1 , we write an = bn if limn→∞ n


an ≤ bn if limn→∞ n−1 log(an /bn ) ≤ 0.
For any two sequences of random vectors Xn , Yn ∈ X n (n = 1, 2, . . .), we write
Xn = Yn


D

January 3, 2018

(22)

DRAFT

8

if
.
P (Xn = xn ) = P (Y = xn )

(23)

uniformly over xn ∈ X n , that is,
lim

n→∞

1
PX (xn )
log n
=0
n
PYn (xn )

(24)

PX (xn )
1
log n
≤0
n
PYn (xn )

(25)



uniformly over xn ∈ X n . We write Xn 6 Yn if
D

lim

n→∞

uniformly over xn ∈ X n .
The set of non-negative integers are denoted by Z+ , and the set of natural numbers, i.e., 1, 2, . . ., by N.
C. Some Basic Results
When the rate is not constrained, the decision function has access to the full source sequences. The optimal
tradeoff of the two types of errors is given by the following decision function, depending on the parameter T ≥ 0
(Neyman-Pearson [22]),8

 0, P (0) (x, y) ≥ T · P (1) (x, y)
X,Y
X,Y
ϕ(x, y) =
 1, otherwise.

(26)

Proposition 1 (Unconstrained Case): Consider the hypothesis testing problem as defined in Section II-A, where
there is no rate constraint, i.e. RX = RY = ∞, then (E0 , E1 ) ∈ C (∞) if and only if there exists a distribution
(∗)

function PX,Y over the pair (X , Y) such that


(i)
(∗)
Ei ≤ D PX,Y PX,Y , for i = 0, 1.

(27)

For proof, see e.g. [21]. Note that in fact rates equal to the logarithms of the alphabet sizes suffice.
For the DSBS, the Neyman-Pearson decision function is a threshold on the weight of the noise sequence. We
denote it (with some abuse of notations) by
△

ϕt (x, y) = ϕt (δH (x ⊕ y)) ,
where ϕt : R 7→ {0, 1} is a threshold test,

 0, w ≤ t
ϕt (w) =
 1, w > t.

(28)

8 In order to achieve the full Neyman-Pearson tradeoff, special treatment of the case of equality is needed. As this issue has no effect on error
exponents, we ignore it.

January 3, 2018

DRAFT

9

It leads to the following performance:
Corollary 1 (Unconstrained Case, DSBS): For the DSBS, CX (1) = C (1), and they consist of all pairs (E0 , E1 )
satisfying that for some t ∈ (p0 , p1 ),
Ei ≤ Db (tkpi ), for i = 0, 1.

(29)

We now note a time-sharing result, which is general to any given achievable set.
Proposition 2 (time-sharing): Suppose that (E0 , E1 ) ∈ C (RX , RY ). Then ∀α ∈ [0, 1] :
(αE0 , αE1 ) ∈ C (αRX , αRY ).

(30)

The proof is standard, by noting that any scheme may be applied to an α-portion of the source blocks, ignoring
the additional samples. Applying this technique to Corollary 1, we have a simple scheme where each encoder sends
only a fraction of its observed vector.
Corollary 2: Consider the DSBS hypothesis testing problem as defined in Section II-A. For any rate constraint
R ∈ [0, 1], for any t ∈ (p0 , p1 )
(R · Db (tkp0 ), R · Db (tkp1 )) ∈ C (R)

(31)

Specializing to Stein’s exponents, we have:
σ0 (R) ≥ R · Db (p1 kp0 )

(32a)

σ1 (R) ≥ R · Db (p0 kp1 ),

(32b)

Of course we may apply the same result to the one-sided constrained case, i.e., CX and the corresponding Stein
exponents.
III. O NE -S IDED C ONSTRAINT: P REVIOUS R ESULTS
In this section we review previous results for the one-sided constraint case RY = ∞. We first present them for
(0)

(1)

general distributions PX,Y , PX,Y and then specialize to the DSBS.
A. General Sources
Ahlswede and Csiszár have established the following achievable Stein’s exponent.
Proposition 3 ([4, Theorem 5]): For any RX > 0,


(0)
(1)
σX,1 (R) ≥ D PX PX
+

max

PV |X :



(0)
I PX ,PV |X ≤RX

January 3, 2018



(0)
(∗)
D PV,Y PV,Y ,

(33)

DRAFT

10

(∗)

(0)

where PV,Y and PV,Y are the marginals of
(0)

△

(0)

(0)

(∗)

△

(0)

(1)

PV,X,Y = PV |X PX PY |X
and
PV,X,Y = PV |X PX PY |X ,
respectively.
The first term of (33) reflects the contribution of the type of X (which can be conveyed with zero rate), while the
second reflects the contribution of the lossy version of X sent with rate RX . Interestingly, this exponent is optimal
(1)

(1)

for case PY |X = PY , known as test against independence.
Han has improved upon this exponent by conveying the joint type of the source sequence X and its quantized
version (represented by V ) to the decision function.9
Proposition 4 ([5, Theorems 2,3]): For any RX ≥ 0,


(1)
(0)
σX,1 (RX ) ≥ D PX PX +

max

PV |X :


(0)
I PX ,PV |X ≤RX ,

σHAN (V ),

(34a)

|V|≤|X |+1

where
△

σHAN (V ) =



(0)
(1)
(∗)
D PY |X,V kPY |X PX PV |X

min
(∗)

PY |V,X :
(∗)

(34b)

(0)

PV,Y =PV,Y
(0)

(∗)

and where PV,Y and PV,Y are the marginals of
(0)

△

(0)

(0)

PV,X,Y = PV |X PX PY |X

(35a)

and
(∗)

△

(0)

(∗)

PV,X,Y = PV |X PX PY |V,X ,

(35b)

respectively.
The following result by Shimokawa et al., gives a tighter achievable bound by using the side information Y when
encoding X.
Proposition 5 ([6, Corollary III.2],[16, Theorem 4.3]): Define


△
(0)
(0)
σSHA (V ) = −I PX|Y , PV |X PY
9 Han’s

result also extends to any rate pair (RX , RY ); however, we only state it for the single-sided constraint.

January 3, 2018

DRAFT

11

+



(0)
(1)
(∗)
D PY |X,V kPY |X PX PV |X ,

min
(∗)

PY |V,X :
(∗)

H
(0)



(∗)
PV |Y

(36a)

(0)

PY =PY ,



(0)
(0)
PỸ ≥H PV |Y PY

(∗)

where PV,Y and PV,Y are the marginals of the distributions defined in (35a) and (35b), respectively. Then, for any
RX > 0,


(0)
(1)
σX,1 (RX ) ≥ D PX PX
+

max

PV |X :


(0)
(0)
I PX|Y ,PV |X PY
≤RX ,

min {σHAN (V ), RX + σSHA (V )} .

(36b)

|V|≤|X |+1

Notice that for PV |X



(0)
such that I PX , PV |X ≤ RX , the bound of the last proposition will be not greater than

the bound of Proposition 4. Therefore the overall bound yields by taking the maximal one.

It is worth pointing out that for distributed rate-distortion problem, the bound in Proposition 5 is in general
suboptimal [23].
A non-trivial outer bound derived by Rahman and Wagner [10] using an additional information at the decoder,
which does not exist in the original problem.
Proposition 6 ([10, Corollary 5]): Suppose that
(1)

(0)

PX = PX .

(37a)

(1)

(0)

Consider a pair of conditional distributions PZ|X,Y and PZ|X,Y such that
(1)

(0)

PZ|X = PZ|X

(37b)

and such that X ↔ Z ↔ Y under the distribution
(1)

△

(1)

(1)

PX,Y,Z = PX,Z PZ|X,Y .

(37c)

Then, for any RX > 0,


(1)
(0)
σX,1 (RX ) ≤ D PY |Z kPY |Z PZ


(0)
(0)
I PY |Z , PX|Y,Z PV |X PZ .
+
max
PV |X :


(0)
(0)
≤RX ,
I PX|Y ,PV |X PY

(37d)

|V|≤|X |+1

B. Specializing to the DSBS
We now specialize the results of Section III-A to the DSBS. Throughout, we choose the auxiliary variable V to
be connected to X by a binary symmetric channel with crossover probability a; with some abuse of notation, we
write e.g. σ(a) for the specialization of σ(V ). Due to symmetry, we conjecture that this choice of V is optimal,

January 3, 2018

DRAFT

12

up to time sharing that can be applied according to Proposition 2; we do not explicitly write the time-sharing
expressions.
The connection between the general and DSBS-specific results can be shown;.However, we follow a direction
that is more relevant to this work, providing for each result a direct interpretation, explaining how it can be obtained
for the DSBS; in doing that, we follow the interpretations of Rahman and Wagner [10].
The Ahlswede-Csiszár scheme of Proposition 3 amounts to quantization of the source X, without using Y as side
information.
Corollary 3 (Proposition 3, DSBS with symmetric auxiliary): For any RX > 0,
σX,1 (RX ) ≥ σAC (δGV (RX )),

(38a)

where
△

σAC (a) = Db (a ∗ p0 ka ∗ p1 ).

(38b)

This performance can be obtained as follows. The encoder quantizes X using a code that is rate-distortion optimal under the Hamming distortion measure; specifically, averaging over the random quantizer, the source and
reconstruction are jointly distributed according to the RDF-achieving test channel, that is, the reconstruction X̂ is
obtained from the source X by a BSC with crossover probability a that satisfies the RDF, namely a = δGV (RX ).
The decision function is φt (X̂, Y) which can be seen as two-stage: first the source difference sequence is estimated
as Ẑ = Y ⊖ X̂, and then a threshold is applied to the weight of that sequence, as if it were the true noise. Notice
that given H = i, Ẑ ∼ BerV (n, a ∗ pi ); the exponents are thus the probabilities of such a vector to fall inside
or outside a Hamming sphere of radius nt around the origin. As Proposition 3 relates to a Stein exponent, the
threshold t is set arbitrarily close to a ∗ p0 , resulting in the following; one can easily generalize to an achievable
exponent region.
The Han scheme of Proposition 4 amounts (for the DSBS) to a similar approach, using a more favorable
quantization scheme. In order to express its performance, we use the following exponent, which is explicitly
evaluated in Appendix A. While it is a bit more general than what we need at this point, this definition will allow
us to present later results in a unified manner.
Definition 6: Fix some parameters p, a, t, w ∈ [0, 1]. Let cn ∈ {0, 1}n, n = 1, 2, . . . be a sequence of vectors
such that limn→∞ δH (cn ) = w. Let Z ∼ BerV (n, p) and let U ∼ Uniform (Tn (a)). Then:
EBT (p, a, w, t) , lim −
n→∞

1
log P (Z ⊕ U ∈ Bn (cn , t)) .
n

(39)

Corollary 4 (Proposition 4, DSBS with symmetric auxiliary): For any RX > 0,
σX,1 (RX ) ≥ σHAN (δGV (RX )),

January 3, 2018

(40a)

DRAFT

13

where
△

σHAN (a) = EBT (p1 , a, 0, a ∗ p0 ) .

(40b)

One can show that σHAN (a) ≥ σAC (a), where the inequality is strict for all p1 < 1/2 (recall that for p1 = 1/2,
“testing against independence”, the Alswhede-Csiszár scheme is already optimal). The improvement comes from
having quantization error that is fixed-type a (recall Definition 5) rather than Bernoulli. Thus, Ẑ is “mixed” uniformBernoulli; the probability of that noise to enter a ball around the origin is reduced with respect to that of the Bernoulli
Ẑ of Corollary 3.
The Shimokawa et al. scheme of Proposition 5 is similar in the DSBS case, except that the compression of X
now uses side-information. Namely, Wyner-Ziv style binning is used. When the bin is not correctly decoded, a
decision error may occur. The resulting performance is given in the following.
Corollary 5 (Proposition 5, DSBS with symmetric auxiliary): For any RX > 0,
σX,1 (RX ) ≥

max

0≤a≤δGV (RX )

min {σHAN (a), σSHA (RX , a)} ,

(41a)

where
△

σSHA (R, a) = R − Hb (a ∗ p0 ) + Hb (a)

(41b)

This exponent can be thought of as follows. The encoder performs fixed-type quantization as in Han’s scheme,
except that the quantization type a is now smaller than δGV (RX ). The indices thus have rate 1 − Hb (a). Now these
indices are distributed to bins; as the rate of the bin index is RX , each bin is of rate 1 − Hb (a) − RX . The decision
function decodes the bin index using the side information Y, and then proceeds as in Han’s scheme.
The two terms in the minimization (41a) represent the sum of the events of decision error combined with bindecoding success and error, respectively. The first is as before, hence the use of σSHA . For the second, it can be
shown that as a worst-case assumption, X̂ resulting from a decoding error is uniformly distributed over all binary
sequences. By considering volumes, the exponent of the probability of the reconstruction to fall inside an nt-sphere
is thus at most 1 − Hb (t); a union bound over the bin gives σSHA .
Remark 1: It may be better not to use binning altogether (thus avoiding binning errors), i.e., the exponent of
Corollary 5 is not always higher than that of Corollary 4.
Remark 2: An important special case of this scheme is when lossless compression is used, and Wyner-Ziv
coding reduces to a side-information case of Slepian-Wolf coding. This amounts to forcing a = 0. If no binning
error occurred, we are in the same situation as in the unconstrained case. Thus, we have the exponent:
min (Db (p0 kp1 ), σSHA (RX )) ,

(42a)

where
△

σSHA (R) = σSHA (R, 0) = R − Hb (p0 ).
January 3, 2018

(42b)
DRAFT

14

Coding component
Oblivious to Y
Using side-information Y

Lossless
TS
Bin + TS

TABLE I
S UMMARY OF POSSIBLE SCHEMES . TS STANDS FOR TIME - SHARING , Q

Lossy
Q + TS [4, 5]
Q + Bin + TS [6]

STANDS FOR QUANTIZATION , B IN STANDS FOR BINNING .

We have seen thus that various combinations of quantization and binning; Table III-B summarizes the different
possible schemes.
An upper bound is obtained by specializing the Rahman-Wagner outer bound of Proposition 6 to the DSBS.
Corollary 6 (Proposition 6, DSBS with symmetric additional information):
△

σRW (R, ζ, a) = min min max
0≤ζ≤p0 0≤b1 ≤1 0≤a≤1/2


b1 · ζ · (1 − a) + b0 · (1 − ζ) · a
Hb (γ) − ζ ∗ aHb
ζ ∗a


b1 · ζ · a + b0 · (1 − ζ) · (1 − a)
+ (1 − ζ ∗ a)Hb
1−ζ ∗a


p0 − a
Db b0 · (1 − a) + b1 · a
,
1 − 2a

(43)

△ p1 −a·(1−b1 )
.
1−a

where b0 =

We note that it seems plausible that the exponent for p1 = 1/2, given by Corollary 4, is an upper to general p1 ,
i.e.,
σX,1 (RX ) ≤ 1 − Hb (p0 ∗ δGV (R)).

(44)

Next we compare the performance of these coding schemes in order to understand the effect of each of the
different components of the coding schemes on the performance.
IV. BACKGROUND : L INEAR C ODES

AND

E RROR E XPONENTS

In this section we define code ensembles that will be used in the sequel, and present their properties. Although
the specific properties of linear codes are not required until Section VI, we put an emphasis on such codes already;
this simplifies the proofs of some properties we need to show, and also helps to present the different results in a
more unified manner.
A. Linear Codes
Definition 7 (Linear Code): We define a linear code via a k × n generating matrix G over the binary field. This
induces the linear codebook:
C = {c : c = uG, u ∈ {0, 1}k },

January 3, 2018

(45)

DRAFT

15

where u ∈ {0, 1}k is a row vector.
Assuming that all rows of G are linearly independent, there are 2k codewords in C, so the code rate is
R=

k
.
n

(46)

Clearly, for any rate (up to 1), there exists a linear code of this rate asymptotically as n → ∞.
A linear code is also called a parity-check code, and may be specified by a (n − k) × n (binary) parity-check
matrix H. The code C contains all the n-length binary row vectors c whose syndrome
△

s = cHT

(47)

is equal to the n − k all zero row vector, i.e.,
△ 
C = c ∈ {0, 1}n : cHT = 0 .

(48)

Given some general syndrome s ∈ {0, 1}n−k , denote the coset of s by
△

Cs = {x ∈ {0, 1}n : xHT = s}.

(49)

The minimum Hamming distance quantizer of a vector x ∈ {0, 1}n with respect to a code C ⊆ {0, 1}n is given
by
△

QC (x) = arg min δH (x ⊖ c).
c∈C

(50)

For any syndrome s with respect to the code C, the decoding function fC (s) : {0, 1}n−k 7→ {0, 1}n gives the
coset leader, the minimum Hamming weight vector within the coset of s:
△

fC (s) = arg min δH (z).
z∈Cs

(51)

Maximum-likelihood decoding of a parity-check code, over a BSC Y = X ⊕ Z, amounts to syndrome decoding
x̂ = y ⊖ fC (y) [24, Theorem 6.1.1]. The basic “Voronoi” set is given by
△ 
Ω0 = z : z ⊖ fC (zHT ) = 0 .

(52)

The ML decision region of any codeword c ∈ C is equal to a translate of Ω0 , i.e.,
△ 
Ωc = y : y ⊖ fC (yHT ) = c

= Ω0 + c.

(53)
(54)

B. Properties of Linear Codes
Definition 8 (Normalized Distance Distribution): The normalized distance (or weight) distribution of a linear
code C for a parameter 0 ≤ w ≤ 1 is defined to be the fraction of codewords c 6= 0, with normalized weight at

January 3, 2018

DRAFT

16

most w, i.e.,
△

ΓC (w) =

1
|C|

X

1{δH (c)≤w} ,

(55)

c∈C\{0}

where 1{·} is the indicator function.
Definition 9 (Normalized Minimum Distance): The normalized minimum distance of a linear code C is defined
as
△

δmin (C) = min δH (c)
c∈C\{0}

(56)

Definition 10 (Normalized Covering Radius): The normalized covering radius of a code C ∈ {0, 1}n is the
smallest integer such that every vector x ∈ {0, 1}n is covered by a Hamming ball with radius r and center at some
c ∈ C, normalized by the blocklength, i.e.:
△

ρcover (C) = max n min δH (x ⊖ c).
x∈{0,1}

c∈C

(57)

Definition 11 (Normalized Packing Radius): The normalized packing radius of a linear code C is defined to be
half the normalized minimal distance of its codewords, i.e.,
△

ρpack (C) =

1
δmin (C).
2

(58)

C. Good Linear Codes
We need two notions of goodness of codes, as follows.
Definition 12 (Spectrum-Good Codes): A sequence of codes C (n) ⊆ {0, 1}n, n = 1, 2, . . . with rate R is said to
be spectrum-good if for any w ≥ 0,
. (n)
ΓC (n) (w) = ΓR (w)
where
(n)
ΓR (w)


 2−nDb (wk1/2) , w > δ (R)
GV
=
.
 0,
otherwise

(59)

Definition 13 (Covering-Good): A sequence of codes C (n) ⊆ {0, 1}n, n = 1, 2, . . . with rate R is said to be
covering-good if
ρcover (C (n) ) −→ δGV (R)
n→∞

(60)

The existence of linear codes satisfying these properties is well known. Specifically, consider the ensemble of
constructed by random generating matrices, where each entry of the matrix is drawn uniformly and statistically
independent with all other entries, then almost all members have a spectrum close to (59), see e.g. [24, Chapter
5.6-5.7]; in addition, for almost all members, a process of appending rows to the generating matrix (with vanishing

January 3, 2018

DRAFT

17

rate) results in a normalized covering radius close to δGV [25, Theorem 12.3.5]. These existence arguments are
detailed in Appendix C. We need the following properties of good codes.
Spectrum-good codes obtain the best known error exponent for the BSC. Namely, for a BSC with crossover
probability p, they achieve E BSC (p, R), given by
△

E BSC (p, R) = max {Er (p, R), Eex (p, R)} ,

(61a)


 1
1
△
Er (p, R) = max ρ − (1 + ρ) log p 1+ρ + (1 − p) 1+ρ − ρR

(61b)

where

ρ∈[0,1]

is the random-coding exponent, and
△

Eex (p, R) = max −ρ log
ρ≥1



i ρ1 
1 1h p
− ρR.
2 p(1 − p)
+
2 2

(61c)

is the expurgated exponent. Notice that as the achievability depends only upon the spectrum, it is universal in p.
As for covering-good codes, we need the following result, shown that the quantization noise induced by coveringgood codes is no worse than a noise that is uniform over an nδGV -Hamming ball.
Lemma 1: Consider a covering-good sequence of codes C (n) ⊆ {0, 1}n, n = 1, 2, . . . of rate R. Then,


X ⊖ QC (n) (X) 6 N,

(62a)

X ∼ Uniform ({0, 1}n)
 

N∼ Uniform Bn 0, ρcover (C (n) ) .

(62b)

D

for

(62c)

Furthermore, the same holds when adding any random vector to both sides, i.e., for any Z:


X ⊖ QC (n) (X) ⊕ Z 6 N ⊕ Z,

(63)

D

The proof appears in Appendix B.
D. Nested Linear Codes
We briefly recall some basic definitions and properties related to nested linear codes. The reader is referred to
[26] for further details.
Definition 14 (Nested Linear Code): A nested linear code with rate pair (R1 , R2 ) is a pair of linear codes (C1 , C2 )
with these rates, satisfying
C2 ⊆ C1 ,

January 3, 2018

(64)

DRAFT

18

i.e., each codeword of C2 is also a codeword of C1 (see [26]). We call C1 and C2 fine code and coarse code,
respectively.
If a pair {(n, k1 ), (n, k2 )} of parity-check codes, k1 ≥ k2 , satisfies condition (64), then the corresponding paritycheck matrices H1 and H2 are interrelated as
HT2
|{z}

=[

(n−k2 )×n

HT1 ,
|{z}

∆HT ],
| {z }

(65)

(n−k1 )×n (k1 −k2 )×n

where H1 is an (n − k1 ) × n matrix, H2 is an (n − k2 ) × n matrix, and ∆H is a (k1 − k2 ) × n matrix. This implies
that the syndromes s1 = xHT1 and s2 = xHT2 associated with some n-vector x are related as s2 = [s1 , ∆s], where
the length of ∆s is k1 − k2 bits. In particular, if x ∈ C1 , then s2 = [0, . . . , 0, ∆s]. We may, therefore, partition C1
into 2k1 −k2 cosets of C2 by setting s1 = 0, and varying ∆s, i.e.,
[

C1 =

C2,s2 ,

where s2 = [0, ∆s].

(66)

∆s∈{0,1}k1 −k2

Finally, for a given pair of nested codes, the “syndrome increment” ∆s is given by the function
∆s = x · ∆HT .

(67)

Proposition 7: Let the syndrome increment ∆s be computed for c ∈ C1 . Then, the coset leader corresponding to
the syndrome of c with respect to C2 is given by
fC2 (cHT1 ) = fC2 ([0, ∆s]),

(68)

where 0 is a zero row vector of length n − k1 .
For a proof, see, e.g., [26].
Definition 15 (Good Nested Linear Code): A sequence of nested linear codes with rate pair (R1 , R2 ) is said to
be good if the induced sequences of fine and coarse codes are covering-good and spectrum-good, respectively.
The existence of good nested linear codes follows naturally from the procedures used for constructing spectrumgood and covering-good codes; see Appendix C for a proof.
We need the following property of good nested codes.
(n)

(n)

Corollary 7: Consider a sequence of good nested codes (C1 , C2 ), n = 1, 2, . . . with a rate pair (R1 , R2 ). Let
△

X ∼ Uniform ({0, 1}n) and Z ∼ BerV (n, p) be statistically independent. Denote U = QC (n) (X), where quantization
1

with respect to a code is defined in (50). Then,

  


P QC (n) (X ⊕ Z) 6= U ≤ P QC (n) U ⊕ N′ ⊕ Z 6= U
2,S

(69)

2,S

△

where N′ ∼ Uniform (Bn (0, δGV (R1 ))) is statistically independent of (U, Z), where S = UHT2 , and where H2 is a
(n)

parity check matrix of the coarse code C2 .

January 3, 2018

DRAFT

19

The proof, which relies upon Lemma 1, is given in Appendix B.
E. Connection to Distributed Source Coding
As the elements used for the schemes presented (quantization and binning) are closely related to distributed
compression, we present here some material regarding the connection of the ensembles presented to such problems.
A covering-good code achieves the rate-distortion function of a binary symmetric source with respect to the
Hamming distortion measure, which amounts to a distortion of δGV (R). Furthermore, it does so with a zero error
probability.
A spectrum-good code is directly applicable to the Slepian-Wolf (SW) problem [8], where the source is DSBS.
Specifically, a partition of all the binary sequences into bins of rate Rbin can be performed by a code of rate
R = 1 − Rbin (which can be alternatively be seen as a nested code with R + Rbin = 1), and the SW decoder can
be seen as a channel decoder where the input codebook is the collection of sequences in the bin and the channel
output is Y n , see [27]. Thus, it achieves the exponent
E BSC (p, Rbin ) = E BSC (p, 1 − R)
As in channel coding, this error exponent is achievable universally in p.
The achievability of the random-coding and expurgated exponents for the general discrete SW problem was
established by Csiszár et al. [28] and [29],10 Indeed, the connection between channel coding and SW coding is
fundamental (as already noted in [27]), and the optimal error exponents (if they exist) are related, see [31–33].
Nested codes are directly applicable to the Wyner-Ziv (WZ) problem [9], where the source is DSBS and under
the Hamming distortion measure, see [26]. When a good ensemble is used, the exponent of a binning error event is
at least E BSC (p, Rbin ). As the end goal of the scheme is to achieve low distortion with high probability, the designer
has the freedom to choose Rbin that strikes a good balance between binning errors and other excess-distortion events,
see [34].
V. O NE -S IDED C ONSTRAINT: N EW R ESULT
In this section we present new achievable exponent tradeoffs for the same one-sided case considered in the
previous section. To that end, we will employ the same binning strategy of Corollary 5. However, our analysis
technique allows to improve the exponent, and to extend it from the Stein setting to the full tradeoff.
For our exponent region, we need the following exponent. It is a variation upon EBT (Definition 6), where the
fixed-type noise is replaced by a noise uniform over a Hamming ball.
10 Indeed, Csiszár has already established the expurgated exponent for a class of additive source-pairs which includes the DSBS in [29].
However, as the derivation was for general rate pairs rather than for the side-information case, it faced inherent difficulty in expurgation in a
distributed setting. This was solved by using linear codes; see [30] for a detailed account in a channel-coding setting.

January 3, 2018

DRAFT

20

Definition 16: Fix some parameters p, a, t, w ∈ [0, 1/2]. Let cn ∈ {0, 1}n, n = 1, 2, . . . be a sequence of vectors
such that limn→∞ δH (cn ) = w. Let Z ∼ BerV (n, p) and let N∼ Uniform (Bn (0, a)). Define
EBB (p, a, w, t) , lim −
n→∞

1
log P (N ⊕ Z ∈ Bn (cn , t)) .
n

(70)

The following can be shown using standard type considerations.
Lemma 2:
EBB (p, a, w, t) = −Hb (a) + min [Hb (r) + EBT (p, r, w, t)]
0≤r≤a

(71)

We are now ready to state the main result of this section.
Theorem 1 (Binary Hypothesis Testing with One-Sided Constraint): Consider the hypothesis testing problem as
defined in Section II-A for the DSBS, with a rate constraint RX ∈ [0, 1]. For any parameters a ∈ [0, δGV (RX )] and
t ∈ [a ∗ p0 , a ∗ p1 ],



(SI)
(a,
t;
p
,
R
),
E
(a,
t;
p
,
R
)
∈ CX (RX ),
E (SI)
0
X
1
X
0
1

(72)

where



(a, t; p0 , RX ) = min EBB (p0 , a, 1, 1 − t) , E BSC (a ∗ p0 , Rbin )


△
(a,
t;
p
,
R
)
=
min
E
(p
,
a,
0,
t)
,
E
(p
,
a,
t,
R
)
,
E (SI)
1
X
BB
1
c
1
bin
1
△

E (SI)
0

(73a)
(73b)

where
△

Ec (p1 , a, t, Rbin ) = max

n

− Rbin +

min

δGV (Rbin )<w≤1

o
Db (wk1/2) + EBB (p1 , a, w, t) , E BSC (a ∗ p1 , Rbin ) ,

(74)

and where
△

Rbin = 1 − Hb (a) − RX

(75)

and EBB (p, a, w, t) is defined in Definition 16.
We prove this theorem using a quantize-and-bin strategy similar to that of Corollary 5, implemented with good
nested codes as defined in Section IV-D. In each of the two minimizations in (73), the first term is a bound on
the exponent of a decision error resulting from a bin-decoding success, while the second is associated with a bindecoding error, similar to the minimization in (41a). Using the properties of good codes, we provide a tighter and
more general (not only a Stein exponent) bound; the key part is the derivation of Ec , the error exponent given H1 ,
and given a bin-decoding error: we replace the worst-case assumption that the “channel output” is uniform over
all binary sequences by the true distribution, centered around the origin; in particular, it means that given an error,
points close to the decision region of the correct codeword, thus not very close to any other codeword, are more
likely.

January 3, 2018

DRAFT

21

After the proof, we remark on the tightness of this result.
Proof: For a chosen a, denote
△

RQ = δGV −1 (a)

(76a)

= 1 − Hb (a)

(76b)

= RX + Rbin .

(76c)

(n)

(n)

Consider a sequence of linear nested codes (C1 , C2 ), n = 1, 2, . . . with rate pair (RQ , Rbin ), which is good
in the sense of Definition 15. For convenience, the superscript of the code index in the sequence will be omitted.
The scheme we consider uses structured quantization and binning. Specifically, given a vector X, we denote its
quantization by
△

U = QC1 (X).

(77)

Note that we can decompose Y as follows:
Y= X⊕Z
= U ⊕ N ⊕ Z,

(78a)
(78b)

where the quantization noise N = X ⊖ U is independent of U (and of course also of Z) since X is uniformly
distributed.
For sake of facilitating the analysis of the scheme, we also define
Y′ = U ⊕ N′ ⊕ Z,

(79a)

N′ ∼ Uniform (Bn (0, a))

(79b)

where

is independent of the pair (U, Z). That is, Y′ satisfies the same relations with U as Y, except that the quantization
noise N is replaced by a spherical noise with the same circumradius.
The encoded message is the syndrome increment (recall (67)) of U, i.e.,
φX (X) = ∆S
= U · ∆H T .

(80a)
(80b)

Since the rates of C1 and C2 are RQ and Rbin , respectively, the encoding rate is indeed RX .
Let
△

S = UH2T .

January 3, 2018

DRAFT

22

By Proposition 7, since U ∈ C1 , the decoder can recover from ∆S the coset C2,S of syndrome S.
The reconstructed vector at the decoder is given by
△

Û = QC2,S (Y),

(81)



△
Ŵ = δH Y ⊖ Û .

(82)

Denote

After computing Ŵ , given a threshold t ∈ [a ∗ p0 , a ∗ p1 ], the decision function is given by
△

ψ(φX (X), Y) = ϕt (Ŵ ),

(83a)

where ϕt (w) is the threshold function (28).
Denote
△

W = δH (Y ⊖ U).

(84)

△

Denote the decoding error event by EC = {Û 6= U} and the complementary event by Ec . Using elementary
probability laws, we can bound the error events given the two hypotheses as follows:


ǫ0 = P Ŵ > t H = 0




= P Ec , Ŵ > t H = 0 + P E c , Ŵ > t H = 0


≤ P Ec , Ŵ > t H = 0 + P (W > t|H = 0)
≤ P (Ec |H = 0) + P (W ≥ t|H = 0) .

(85a)
(85b)
(85c)
(85d)

And similarly,



ǫ1 = P Ŵ ≤ t H = 1




= P Ec , Ŵ ≤ t H = 1 + P E c , Ŵ ≤ t H = 1


≤ P Ec , Ŵ ≤ t H = 1 + P (W ≤ t|H = 1) .

(86a)
(86b)
(86c)

Comparing with the required exponents (73), it suffices to show the following four exponential inequalities.


(87a)



(87b)



(87c)

P (W ≥ t|H = 0) ≤ EBB (p0 , a, 1, 1 − t)
P (Ec |H = 0) ≤ E BSC (a ∗ p0 , Rbin )
P (W ≤ t|H = 1) ≤ EBB (p1 , a, 0, t)

 
P Ec , Ŵ ≤ t H = 1 ≤ Ec (p1 , a, t, Rbin )
January 3, 2018

(87d)

DRAFT

23

In the rest of the proof we show these. For (87a), we have:
P (W ≥ t|H = 0)

(88a)

= P (δH (Y ⊖ U) ≥ t|H = 0)

(88b)

= P (N ⊕ Z ∈
/ Bn (0, t)|H = 0)

(88c)

= P (N ⊕ Z ∈ Bn (1, 1 − t)|H = 0)

(88d)



≤ P N′ ⊕ Z ∈ Bn (1, 1 − t) H = 0
.
= 2−nEBB(p0 ,a,1,1−t) ,



(88e)
(88f)

where 1 is the all-ones vector, (88c) follows by substituting (77), the transition (88e) is due to Lemma 1 and the
last asymptotic equality is due to Definition 16. The proof of (87c) is very similar and is thus omitted.
For (87b), we have:
P (EC |H = 0)


= P Û 6= U H = 0

(89a)
(89b)

= P QC2,S (X ⊕ Z) 6= QC1 (X) H = 0






≤ P QC2,S QC1 (X) ⊕ N′ ⊕ Z 6= QC1 (X) H = 0


= P QC2,S U ⊕ N′ ⊕ Z 6= U H = 0

= P QC2,S (Y′ ) 6= U H = 0


≤ 2−nE BSC (a∗p0 ,Rbin ) ,

(89c)
(89d)
(89e)
(89f)
(89g)

where (89d) is due to Corollary 7, the last inequality follows from the spectrum-goodness of the coarse code C2
and Y′ was defined in (79a). Notice that the channel exponent is with respect to an i.i.d. noise, but it is easy to
show that the exponent of a mixed noise can only be better.
Lastly, For (87d) we have:


P EC , Ŵ ≤ t H = 1


= P Û 6= U, Ŵ ≤ t H = 1




= P Û 6= U, Y ∈ Bn Û, t H = 1


o
n
[
= P
Û = c, Y ∈ Bn (c, t) H = 1

(90a)
(90b)
(90c)
(90d)

c∈C2,S \{U}



= P Û 6= U, Y ∈

January 3, 2018

[

c∈C2,S \{U}



Bn (c, t) H = 1

(90e)

DRAFT

24



≤ max







P (EC |H = 1) , P Y ∈



Bn (c, t) H = 1 .


[

c∈C2,S \{U}

(90f)

Due to the spectrum-goodness of the coarse code C2 , the first term in the maximization is exponentially upperbounded by
2−nE BSC (a∗p1 ,Rbin ) .
For the second term, we proceed as follows.


[
Bn (c, t) H = 1
P Y ∈

(91a)

c∈C2,S \{U}





≤ P Y′ ∈


[

c∈C2,S \{U}

= P Y ⊖ U ∈


= P Y′ ⊖ U ∈


= P N′ ⊕ Z ∈
≤

X

Bn (c, t) H = 1

[

′



c∈C2,S \{U}

[

c∈C2 \{0}

[

c∈C2 \{0}



Bn (c ⊖ U, t) H = 1

Bn (c, t) H = 1

(91d)



Bn (c, t) H = 1

(91e)

P N′ ⊕ Z ∈ Bn (c, t) H = 1



X

X

P N′ ⊕ Z ∈ Bn (c, t) H = 1

X

X

2−nEBB(p1 ,a,j/n,t)

nδGV (Rbin )≤j≤n c∈C2 :nδH (c)=j

.
=

(91c)



c∈C2 \{0}

=

(91b)

(91f)


(91g)
(91h)

nδGV (Rbin )≤j≤n c∈C2 :nδH (c)=j

=

X

|C2 | · ΓC0 (w) · 2−nEBB (p1 ,a,j/n,t)

(91i)

X

2nRbin · 2−nDb (j/nk1/2) · 2−nEBB (p1 ,a,j/n,t)

(91j)

nδGV (Rbin )≤j≤n


≤

nδGV (Rbin )≤j≤n

.
= 2−n[−Rbin +minδGV (Rbin )<w≤1 Db (wk1/2)+EBB (p1 ,a,w,t)]

(91k)

= 2−nEc (p1 ,a,t,Rbin ) ,

(91l)

where (91b) is due to Lemma 1, (91f) is due to the union bound, the lower limit in the outer summation in (91g) is
valid since spectrum-good codes have no non-zero codewords of lower weight, in (91j) we substituted the spectrum
of a spectrum-good code, and in (91k) we substitute w = j/n and use Laplace’s method.

At this point we remark on the tightness of the analysis above.
January 3, 2018

DRAFT

25

Remark 3: There are two points where our error-probability analysis can be improved.
1) For the exponent of the probability of bin-decoding error (under both hypotheses) we used E BSC (a ∗ pi , Rbin ).
However, one may use the fact the quantization noise is not Bernoulli but rater bounded by a sphere to derive
a larger exponent.
2) In (90e) we have the probability of a Bernoulli noise to fall within a Hamming ball around some non-zero
codeword, and also outside the basic Voronoi cell. In the transition to (90f) we bound this by the maximum
between the probabilities of being in the Hamming balls and being outside the basic Voronoi cell.
While solving the first point is straightforward (though cumbersome), the second point (exponentially tight evaluation
of (90e)) is an interesting open problem, currently under investigation. We conjecture that except for these two points,
our analysis of this specific scheme is exponentially tight.
Remark 4: In order to see that the encoder can be improved, consider the Stein-exponent bound, obtained by
setting t = a ∗ p0 in (73b):



σX,1 (RX ) ≥ min EBB (p1 , a, 0, a ∗ p0 ) , Ec (p1 , a, a ∗ p0 , RX ) ,

(92)

cf. the corresponding expression of the scheme by Shimokawa et al. (41a),


min EBT (p1 , a, 0, a ∗ p0 ) , σSHA (RX , a) .
Now, one can show that we have an improvement of the second term. However, clearly by (71), EBB (p1 , a, 0, a ∗ p0 ) ≤
EBT (p1 , a, 0, a ∗ p0 ). That is, quite counterintuitively, a quantization noise that has always weight a is better than
one that may be smaller. The reason is that a “too good” quantization noise may be confused by the decision
function with a low crossover probability between X and Y , favoring Ĥ = 0. In the Stein case, where we do not
care at all about the exponent of ǫ0 , this is a negative effect. We can amend the situation by a simple tweak: the
encoder will be the same, except that when it detects a quantization error that is not around a it will send a special
symbol forcing Ĥ = 1. It is not difficult to verify that this will yield the more favorable bound


σX,1 (RX ) ≥ min EBT (p1 , a, 0, a ∗ p0 ) , Ec (p1 , a, a ∗ p0 , RX ) .

(93)

A similar process, where if the quantization noise is below some threshold Ĥ = 1 is declared, may also somewhat
extend the exponent region in the regime “close” to Stein (low E0 ), but we do not pursue this direction.
Remark 5: Of course, the two-stage decision process where Ĥ is a function of Ŵ is sub-optimal. It differs from
the Neyman-Pearson test that takes into account the probability of all possible values of W .
Remark 6: Using time sharing on top of the scheme, we can obtain improved performance according to Proposition 2.
Remark 7: In the special case a = 0 the scheme amounts to binning without quantization, and the nested code
maybe replaced by a single spectrum-good code. In this case the expressions simplify considerably, and we have

January 3, 2018

DRAFT

26

the pair:


(0,
t;
R
)
=
min
D
(tkp
),
E
(p
,
R
)
E (SI)
X
b
0
0
bin
BSC
0


△
(SI)
E 1 (0, t; RX ) = min Db (tkp1 ), Ec (p1 , 0, t, Rbin ) ,

(94a)
(94b)

where
Ec (p1 , 0, t, Rbin ) = max

n

− Rbin +

min

δGV (RX )<w≤1

o
Db (wk1/2) + EBB (p1 , 0, w, t) , E BSC (p1 , Rbin ) ,

(95)

and where EBB (p1 , 0, w, t) is defined in (70).
VI. S YMMETRIC C ONSTRAINT
In this section we proceed to a symmetric rate constraint RX = RY = R. In this part our analysis specifically
hinges on the linearity of codes, and specifically builds on the Körner-Marton coding scheme [18]. Adding this
ingredient to the analysis, we get an achievable exponent region for the symmetric constraint in the same spirit of
the achievable region in Theorem 1, where the only loss due to constraining RY is an additional spherical noise
component. Before stating our result, we give some background on the new ingredient.
A. Körner-Marton Compression
The Körner-Marton problem has the same structure as our DHT problem for the DSBS, except that the crossover
probability is known (say p), and the decision function is replaced by a decoder, whose goal is to reproduce the
difference sequence Z = Y ⊖ X with high probability. By considering the two corresponding one-sided constrained
problems, which amount to SI versions of the SW problem, it is clear that any rate R < Hb (p) is not achievable.
The Körner-Marton scheme allows to achieve any rate R > Hb (p) in the following manner.
Assume that the two encoders use the same linear codebook, with parity-check matrix H. Further, both of them
send the syndrome of their observed sequence:
φX (X) = XHT

(96a)

φY (Y) = YHT .

(96b)

In the first stage of the decoder, the two encoded vectors are summed up, leading to
φY (Y) ⊖ φX (X) = YHT ⊖ XHT
= ZHT ,

(97a)
(97b)

which is but the syndrome of the difference sequence. This is indistinguishable from the situation of a decoder for
the SI SW problem,
The decoder is now in the exact same situation as an optimal decoder for a BSC with crossover probability p,
and code rate 1 − R. By the fact that linear codes allow to approach the capacity 1 − Hb (p), the optimal rate
January 3, 2018

DRAFT

27

follows. Further, if spectrum-good codes are used, the exponent E BSC (p, 1 − R) is achievable, i.e., there is no loss
in the exponent w.r.t. the corresponding side-information SW problem.
B. A New Bound
We now present an achievability result that relies upon a very simple principle:as in the Körner-Marton decoder,
after performing the XOR (97) the situation is indistinguishable from that of the input to a SW decoder, also in
DHT we can
Theorem 2 (Binary Hypothesis Testing with Symmetric Constraint): Consider the hypothesis testing problem as
defined in Section II-A for the DSBS, with a symmetric rate constraint R ∈ [0, 1]. For any parameter t ∈ [p0 , p1 ],



(KM)
(t;
R),
E
(t;
R)
∈ C (R),
E (KM)
0
1

(98)

where
E (KM)
(t; R) = E (SI)
0
0 (0, t; R)

(99a)

(t; R) = E (SI)
E (KM)
1
1 (0, t; R),

(99b)

where the one-sided constraint exponents with a = 0 are given in (94).
Proof: Let the codebook be taken from a spectrum-good sequence. Let the encoders be the Körner-Marton
encoders (96). The decision function first obtains ZH T as in the Körner-Marton decoder (97), and then evaluates
Ẑ = QC (ZH T )
and applies the threshold function to
 
△
W ′ = δH Ẑ .
Noticing that W ′ is equal in distribution to Ŵ in the proof of Theorem 1 when a = 0, and that all error events
only functions of that variable, the proof is completed.
It is natural to ask, why we restrict ourselves under a symmetric rate constraint to a binning-only scheme. Indeed,
lossy versions of the Körner-Marton problem have been studied in [35, 36]. One can construct a scheme based on
nested codes, obtain a lossy reconstruction of the noise sequence Z and then test its weight. However, unlike the
reconstruction in the single-sided case which includes a Bernoulli component (Z) and a quantization noise bounded
by a Hamming ball (N), in the symmetric-rate case we will have a combination of a Bernoulli component with two
quantization noises. This makes the analysis considerably more involved. An idea that comes to mind, is to obtain
a bound by replacing at least one of the quantization noises with a Bernoulli one; however, we do not see a clear
way to do that. Thus, improving Theorem 2 by introducing quantization is left for future research.
VII. P ERFORMANCE C OMPARISON
In this section we provide a numerical comparison of the different bounds for the DSBS.
January 3, 2018

DRAFT

28

We start with the Stein setting, where we can compare with the previously-known results. Our achievable performance for the one-sided constrained case is given by (93) (which coincides with (92) for the parameters we checked).
We compare it against the unconstrained performance, and against the previously best-known achievable exponent,
namely the maximum between Corollaries 4 and 5.11 To both, we also apply time sharing as in Proposition 2. It can
be seen that the new exponent is at least as good, with slight improvement for some parameters. As reference, we
show the unconstrained performance, given by Corollary 1. Also shown on the plots, is the performance obtained
under a symmetric rate constraint, found by constraining the quantization parameter to a = 0. It can be seen that
for low p1 the symmetric constraint yields no loss with respect to the one-sided constraint.
0.4

0.14

0.35
0.12

0.3
0.1

0.25
0.08

0.2
0.06

0.15
0.04

0.1

0.02

0.05

0

0

0.02

0.04

0.06

0.08

0.1
p0

0.12

0.14

(a) p1 = 0.25

0.16

0.18

0.2

0

0

0.01

0.02

0.03

0.04

0.05
p

0.06

0.07

0.08

0.09

0

(b) p1 = 0.1. The three top curves coincide.

Fig. 2. Stein exponent comparison. The rate is 0.3 bits, the X axis is p0 . From top to bottom: unconstrained performance, new exponent,
previously known exponent, new exponent without quantization (achievable with symmetric rate).

Beyond the Stein setting, we plot the full exponent tradeoff, achievable by Theorems 1 and 2. In this case we are
not aware of any previous results we can compare to. We thus only add the unconstrained tradeoff of Corollary 1,
and the simple strategy of Corollary 2. Also here it can be seen that the symmetric constraint imposes a loss for
high p1 , but not for a lower one.
VIII. C ONCLUSIONS
In this work we introduced new achievable error exponents for binary distributed hypothesis testing for binary
symmetric i.i.d sources. One may wonder, naturally, regarding the extension beyond the binary symmetric case.
In that respect, a distinction should be made between two parts of the work. Under a one-sided rate constraint,
linear codes were used merely for concreteness and for convenience of extension to the symmetric constraint; the
same results should hold for a random code ensemble. Thus, there is no fundamental problem in extending our
analysis to any discrete memoryless model.
11 In [7], the performance is evaluated using an asymmetric choice of the auxiliary variable. We have verified that the symmetric choice we
use performs better.

January 3, 2018

DRAFT

29

0.35
0.1

0.09

0.3

0.08
0.25
0.07

0.06
E1

E1

0.2

0.05

0.15
0.04

0.03

0.1

0.02
0.05
0.01

0

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0

0.8

0

0.02

0.04

0.06

0.08

E0

0.1
E0

0.12

0.14

0.16

0.18

0.2

(b) p1 = 0.1. The new tradeoff curves with and without quantization
coincide.

(a) p1 = 0.25

Fig. 3. Exponent tradeoff comparison. The rate is 0.3 bits, p0 = 0.01. From top to bottom: unconstrained tradeoff, new tradeoff, new tradeoff
without quantization (achievable with symmetric rate), time-sharing only tradeoff.

In contrast, in the setting of a symmetric rate constraint, we explicitly use the “matching” between the closedness
under addition of linear codes, and the additivity of the relation between the sources. Thus, our approach which
has almost no loss with respect to the single-sided constraint, cannot be extended beyond (nearly) additive cases.
The question whether a different approach can achieve that, remains open.
Finally, we stress again the lack of tight outer bounds for the problem, except for cases where the communication
constraints do not limit the exponents.
ACKNOWLEDGMENT
The authors thank Uri Erez for sharing insights throughout the work. They also thank Vincent Y. F. Tan for
introducing them the distributed hypothesis testing problem, and Nir Weinberger for helpful discussions.
A PPENDIX A
E XPONENT OF

A

H AMMING BALL

In this appendix we evaluate the exponent of the event of a mixed noise entering a Hamming ball, namely
EBT (p, a, w, t) of Definition 6.
Lemma 3:
EBT (p, a, w, t) =

min

Hb (a) − wHb

γ∈[max(0,a+w−1),min(w,a)]

γ 
w

− (1 − w)Hb



a−γ
1−w



+ Ew (p, 1 − (w + a − 2γ), w + a − 2γ, t − (w + a − 2γ))

(100)

where
△

Ew (p, α, β, t) =

January 3, 2018

min

x∈[max(0,t),min(α,β+t)]

αDb

x

α



p + βDb



x−t
p
β



(101)

DRAFT

30

The proof follows from the lemmas below.
Lemma 4 (Difference of weights): Let Z1 and Z2 be two random vectors. Assume that Zi ∼ BerV (ki , p) and
let Wi = wH (Zi ) for i = 1, 2. If ki grow with n such that
k1
= α,
n
k2
= β,
lim
n→∞ n
lim

n→∞

and further let a sequence t grow with n such that
lim

n→∞

t
=τ
n

where τ ∈ (−β, α). Then,
lim −

n→∞

1
log P (W1 − W2 = t) = Ebb (p, α, β, τ ),
n

where Ew (p, α, β, τ ) is given by (101).
Proof:
P (W1 − W2 = t) =

k1
X

P (W1 = w) P (W2 = w − t)

(102a)

w=0
min(k1 ,k2 +t)

X

=

P (W1 = w) P (W2 = w − t)

(102b)

w=max(0,t)

.
=

min(k1 ,k2 +t)

X

2

−k1 Db






p −k2 Db w−t
p
k

w
k1

2

(102c)

2

w=max(0,t)

.
=
.
=

max

w∈[max(0,t),...,min(k1 ,k2 +t)]

2

−k1 Db

x∈[max(0,τ ),min(α,β+τ )]

w
k1




p −k2 Db w−t
p
k

2

2−n[αDb ( α kp)+βDb (
x

max



x−τ
β

2

(102d)

kp)] ,

(102e)

where (102c) follows by the exponent of the probability of a type class.
The following lemma will assist in proving Lemma 6 which follows.
Lemma 5 (Mixed noise, fixed dimension): Let n ∈ N, and consider a noise that is a mixture of a noise U ∼
Uniform (Tn (a)) (uniform over a fixed type) and a Bernoulli vector Z ∼ BerV (n, p), where a ∈ 1/n · {0, . . . , n}
and p ∈ [0, 1]. Further let c ∈ {0, 1}n where w = δH (c) ∈ 1/n · {0, . . . , n}, be the center of a “distant” sphere.
Then, for a sphere radius with normalized radius t ∈ 1/n · {0, . . . , n},
n·min(w,a)

P (wH (c ⊕ U ⊕ Z) = nt) =

X

m=n·max(0,a+w−1)

nw
m





n−nw
na−m

n
na

P (W1,m − W2,m = nt − nw − na + 2m)

(103)

where W1,m ∼ Binomial (n − (nw + na − 2m), p) and W2,m ∼ Binomial (nw + na − 2m, p).

January 3, 2018

DRAFT

31

Proof: Define the following sets of indices I, M1 , M2 :
△

I = {i : ci = 1}

(104a)

△

M1 = {i : UI,i = 1}
n
o
△
M2 = i : UI,i = 1 .

(104b)
(104c)

In words, I is the set of indices where c contains ones; M1 is the subset (within I) where U contains ones and
M2 is defined similarly over the complement of I.
Then,
P (wH (c ⊕ U ⊕ Z = nt)) = P (wH (cI ⊕ UI ⊕ ZI ) + wH (cI ⊕ UI ⊕ ZI ) = nt)

(105a)

= P (nw − wH (UI ⊕ ZI ) + wH (UI ⊕ ZI ) = nt)


h
i
= P nw − wH (UI,M1 ⊕ ZI,M1 ) + wH UI,M1 ⊕ ZI,M1


i

h 
+ wH UI,M2 ⊕ ZI,M2 + wH UI,M2 ⊕ ZI,M2 = nt


h


i h

i

= P nw − M1 − wH (ZI,M1 ) + wH ZI,M1 + M2 − wH ZI,M2 + wH ZI,M2 = nt








= P wH (ZI,M1 ) − wH ZI,M1 − wH ZI,M2 + wH ZI,M2 = n(t − w) + M1 − M2








= P wH (ZI,M1 ) − wH ZI,M1 − wH ZI,M2 + wH ZI,M2 = n(t − w − a) + 2M1

(105b)

(105c)
(105d)
(105e)
(105f)

n·min(w,a)

X

=

P (M1 = m)

m=n·max(0,a+w−1)









· P wH (ZI,M1 ) − wH ZI,M1 − wH ZI,M2 + wH ZI,M2 = n(t − w − a) + 2m M1 = m


n·min(w,a)
nw n−nw
X
m
na−m

P (W1,m − W2,m = n(t − w − a) + 2m)
=
n

(105g)
(105h)

na

m=n·max(0,a+w−1)

△

△

where (105f) follows since |I| = nw, by denoting M1 = |M1 |, M2 = |M2 | and noting that M1 + M2 = na;
equality (105g) follows since M1 ≤ na and M1 ≤ nw, and since M2 ≤ na and M2 ≤ n(1 − w) (therefore
M1 ≥ n(a + w − 1)); and equality (105h) follows by denoting W1,m ∼ Binomial (n − (nw + na − 2m), p) and
W2,m ∼ Binomial (nw + na − 2m, p).
Lemma 6 (Mixed noise, asymptotic dimension): Consider a sequence of problems as in Lemma 5 indexed by the
blocklebgth n, with parameters an → a, wn → w and tn → t. Then:
1
lim − P (wH (cn ⊕ Un ⊕ Zn ) = ntn ) = EBT (p, a, w, t) .
n

n→∞

(106)

Proof: A straightforward calculation shows that
P (wH (cn ⊕ Un ⊕ Zn ) = ntn )

January 3, 2018

(107a)

DRAFT

32

.
=

n·min(wn ,an )

X

2nwn Hb (

m/n
wn

−m/n
) 2n(1−wn )Hb ( an1−w
) 2−nHb (an )
n

m=n·max(0,an +wn −1)

· 2−nEw (p,1−(wn +an −2m/n),wn +an −2m/n,tn −(wn +an −2m/n))
.
=

max

a−m

2−n[−wHb ( w )−(1−w)Hb ( 1−w )+Hb (a)] · 2−nEw (p,1−(w+a−2m),w+a−2m,t−(w+a−2m)).
m

m∈[max(0,a+w−1),min(w,a)]

(107b)

(107c)

The proof of Lemma 3 now follows:
P (wH (cn ⊕ Un ⊕ Zn ) ≤ tn ) =

tn
X

P (wH (cn ⊕ Un ⊕ Zn ) = nτ )

(108a)

τ =0
ntn

. X −nEBT (p,a,w,τ /n)
=
2

(108b)

.
= max 2−nEBT (p,a,w,τ )

(108c)

= 2−n minτ ∈[0,t] EBT (p,a,w,τ )

(108d)

τ =0

τ ∈[0,t]

A PPENDIX B
Q UANTIZATION -N OISE P ROPERTIES

OF

G OOD C ODES

In this section we prove Lemma 1 and Corollary 7, which contain the properties of good codes that we need for
deriving our achievable exponents.
First we define the covering efficiency of a code C as:
△

η(C) =

|Bn (0, ρcover (C))|
.
|Ω0 |

(109)

Lemma 7: Consider a covering-good sequence of codes C (n) ⊆ {0, 1}n, n = 1, 2, . . . of rate R. Then,
.
η(C (n) ) = 1

(110)

Proof: Since for all c ∈ C (n) we have that |Ωc | = |Ω0 |, it follows that
.
|Ω0 | = 2n(1−R) .

(111)

Therefore,
.
η(C (n) ) =
.
=

2−n(1−R)

Bn 0, ρcover (C (n) )

2−n(1−R)
(n)
2−nHb (ρcover (C ))

= 2n[Hb (ρcover (C

January 3, 2018

−1

(n)

))−(1−R)]

(112a)
(112b)
(112c)

DRAFT

33

= 2n[Hb (ρcover (C

(n)

))−Hb (δGV (R))]

.
= 1,

(112d)
(112e)

where the last asymptotic equality is due to (60) and due to the continuity of the entropy.
Proof of Lemma 1: Since for any v ∈
/ Ω0
P (X ⊖ QC (n) (X) = v) = 0

(113a)

≤ P (N = v) ,

(113b)

it is left to consider points v ∈ Ω0 . To that end, since the code is linear, due to symmetry
X ⊖ QC (n) (X) ∼ Uniform (Ω0 ) .

(114)

Thus, for v ∈ Ω0 ,
P (X ⊖ QC (n) (X) = v)
P (N = v)
=

|Ω0 |

(115a)

−1


Bn 0, ρcover (C (n) )

−1

(115b)

= η(C (n) )

(115c)

.
= 1,

(115d)

where the last (asymptotic) equality is due to Lemma 7. This completes the last part (Note that the rate of convergence
is independent of v, and therefore the convergence is uniform over v ∈ Ω0 ). The second part follows by the linearity
of convolution: For any v ∈ {0, 1}n,
P (X ⊖ QC (n) (X) ⊕ Z = v)
X
PZ (z)P (X ⊖ QC (n) (X) ⊕ z = v)
=

(116a)
(116b)

z∈{0,1}n

=

X

PZ (z)P (X ⊖ QC (n) (X) = v ⊖ z)

(116c)

X

PZ (z)P (N = v ⊖ z)

(116d)

z∈{0,1}n


≤

z∈{0,1}n

= P (N ⊕ Z = v) ,

(116e)

where the (asymptotic) inequality is due to the first part of the lemma.
Proof of Corollary 7: Let N = X ⊖ U. Note that since the code is linear and X is uniform over {0, 1}n, it
follows that N is independent of the pair (U, Z). Thus,


P QC (n) (X ⊕ Z) 6= U

(117a)

2,S

January 3, 2018

DRAFT

34



= P QC (n) (U ⊕ [X ⊖ U] ⊕ Z) 6= U
2,S


= P QC (n) (U ⊕ N ⊕ Z) 6= U .

(117b)
(117c)

2,S

Recalling the definition of N′ in (79b), we have


P QC (n) (U ⊕ N ⊕ Z) 6= U
2,S


= P QC (n) (U ⊕ N ⊕ Z) 6= U
2,S


= EU P QC (n) (u ⊕ N ⊕ Z) 6= u U = u
2,S




≤ EU P QC (n) u ⊕ N′ ⊕ Z 6= u U = u
2,S



= P QC (n) U ⊕ N′ ⊕ Z 6= U ,

(118a)
(118b)
(118c)
(118d)
(118e)

2,S

where (118d) follows by applying Lemma 1 for each u.
A PPENDIX C
E XISTENCE

OF

G OOD N ESTED C ODES

In this appendix we prove the existence of a sequence of good nested codes, as defined in Definition 15. To that
end, we first state known results on the existence of spectrum-good and covering-good codes.
By [24], random linear codes are spectrum-good with high probability. That is, let C (n) be a linear code of
blocklength n and rate R, with a generating matrix G(n) drawn i.i.d. Bernoulli-1/2. Then there exist some sequences
(n)

ǫS

(n)

and δS

approaching zero, such that for all w,


(n)
(n)
(n)
P ΓC (n) (w) > (1 + δS )ΓR (w) ≤ ǫS .

(119)

As for covering-good codes, a construction based upon random linear codes is given in [25]. For a generating
(n)

matrix G(n) at blocklength n, a procedure is given to generate a new matrix GI

(n)

(n) △

= GI (G(n) ), with kI

= ⌈log n⌉

rows. The matrices are combined in the following way:



(n)
(n)

G
×
n
k
I
I

k ′(n) × n
G′(n) = 
(n)
(n)

k
×
n
G

(120)

Clearly, adding GI does not effect the rate of a sequence of codes. Let C (n) be constructed by this procedure, with
(n)

G(n) drawn i.i.,d. Bernoulli-1/2. It is shown in [25, Theorem 12.3.5], that there exists sequences ǫC

(n)

and δC

approaching zero, such that


(n)
(n)
P ρcover (C (n) ) > (1 + δC )δGV (R) ≤ ǫC .

January 3, 2018

(121)

DRAFT

35

A nested code of blocklength n and rates (R, Rbin ) has a generating matrix



(n)

(n)
G̃
k̃
×
n

G(n) = 
k (n) × n
(n)
(n)
kbin × n 
Gbin

(122)

(n)

That is, G(n) and Gbin are the generating matrices of the fine and coarse codes, respectively.
We can now construct good nested codes in the following way. We start with random nested codes of rate
(n)

(R, Rbin ). We interpret the random matrix G(n) as consisting of matrices G̃(n) and Gbin as above, both i.i.d.
(n)

Bernoulli-1/2. We now add GI

(n)

= GI (G(n) ) as in the procedure of [25], to obtain the following generating

matrix:


(n)

GI


 (n)
G′(n) =  G̃

(n)
Gbin







(n)
kI



×n 



k̃ (n) × n

k ′(n) × n




(n)
kbin × n 

(123)

(n)

Now we construct the fine and coarse codes using the matrices G′(n) and Gbin , respectively; the rate pair does not
change due to the added matrices. By construction, the fine and coarse codes satisfy (121) and (119), respectively.
(n)

Thus, by the union bound, the covering property is satisfied with δC
(n)

(n)

and the spectrum property with δS ,

(n)

simultaneously, with probability 1 − ǫC − ǫS . We can thus construct a sequence of good nested codes as desired.
R EFERENCES
[1] T. Berger, “Decentralized estimation and decision theory,” in The IEEE 7th Spring Workshop Inf. Theory, Mt.
Kisco, NY, Sep. 1979.
[2] R. Ahlswede and I. Csiszár, “To get a bit of information may be as hard as to get full information,” IEEE
Trans. Information Theory, vol. 27, no. 4, pp. 398–408, July 1981.
[3] H. M. H. Shalaby and A. Papamarcou, “Multiterminal detection with zero-rate data compression,” IEEE Trans.
Information Theory, vol. 38, no. 2, pp. 254–267, Mar. 1992.
[4] R. Ahlswede and I. Csiszár, “Hypothesis testing with communication constraints,” IEEE Trans. Information
Theory, vol. 32, no. 4, pp. 533–542, July 1986.
[5] T. S. Han, “Hypothesis testing with multiterminal data compression,” IEEE Trans. Information Theory, vol. 33,
no. 6, pp. 759–772, Nov. 1987.
[6] H. Shimokawa, T. S. Han, and S. Amari, “Error bound of hypothesis testing with data compression,” in Proc.
Int. Symp. Info. Theory (ISIT), June 1994, p. 114.
[7] H. Shimokawa, “Hypothesis testing with multiterminal data compression,” Master’s thesis, Feb. 1994.
[8] D. Slepian and J. K. Wolf, “Noiseless coding of correlated information sources,” IEEE Trans. Information
Theory, vol. 19, pp. 471–480, July 1973.
[9] A. D. Wyner and J. Ziv, “The rate-distortion function for source coding with side information at the decoder,”
IEEE Trans. Information Theory, vol. 22, pp. 1–10, Jan. 1976.

January 3, 2018

DRAFT

36

[10] M. Rahman and A. Wagner, “On the optimality of binning for distributed hypothesis testing,” IEEE Trans.
Information Theory, vol. 58, no. 10, pp. 6282–6303, Oct. 2012.
[11] T. S. Han and K. Kobayashi, “Exponential-type error probabilities for multiterminal hypothesis testing,” IEEE
Trans. Information Theory, vol. 35, no. 1, pp. 2–14, Jan. 1989.
[12] S. Amari, “On optimal data compression in multiterminal statistical inference,” IEEE Trans. Information
Theory, vol. 57, no. 9, pp. 5577–5587, Sep. 2011.
[13] Y. Polyanskiy, “Hypothesis testing via a comparator,” in Proc. Int. Symp. Info. Theory (ISIT), July 2012, pp.
2206–2210.
[14] G. Katz, P. Piantanida, and M. Debbah, “Distributed binary detection with lossy data compression,” IEEE
Trans. Information Theory, vol. 63, no. 8, pp. 5207–5227, Aug 2017.
[15] ——, “A new approach to distributed hypothesis testing,” in 2016 50th Asilomar Conference on Signals,
Systems and Computers, Nov. 2016, pp. 1365–1369.
[16] T. S. Han and S. Amari, “Statistical inference under multiterminal data compression,” IEEE Trans. Information
Theory, vol. 44, no. 6, pp. 2300–2324, Oct. 1998.
[17] G. D. Forney, Jr., “Exponential error bounds for erasure, list, and detection feedback schemes,” IEEE Trans.
Information Theory, vol. 14, pp. 206–220, Mar. 1968.
[18] J. Körner and K. Marton, “How to encode the modulo-two sum of binary sources,” IEEE Trans. Information
Theory, vol. 25, pp. 219–221, Mar. 1979.
[19] H. Shimokawa and S. Amari, “Multiterminal estimation theory with binary symmetric source,” in Proc. Int.
Symp. Info. Theory (ISIT), Sep. 1995, p. 447.
[20] M. El Gamal and L. Lai, “Are Slepian-Wolf rates necessary for distributed parameter estimation?” CoRR,
vol. abs/1508.02765, 2015. [Online]. Available: http://arxiv.org/abs/1508.02765
[21] T. M. Cover and J. A. Thomas, Elements of Information Theory. New York: Wiley, 1991.
[22] J. Neyman and E. S. Pearson, “The testing of statistical hypotheses in relation to probabilities a priori,”
Mathematical Proceedings of the Cambridge Philosophical Society, vol. 29, pp. 492–510, 10 1933. [Online].
Available: http://journals.cambridge.org/article S030500410001152X
[23] A. B. Wagner, B. G. Kelly, and Y. Altuğ, “Distributed rate-distortion with common components,” IEEE Trans.
Information Theory, vol. 57, no. 7, pp. 4035–4057, July 2011.
[24] R. G. Gallager, Information Theory and Reliable Communication. John Wiley & Sons, 1968.
[25] G. Cohen, I. Honkala, S. Litsyn, and A. Lobstein, Covering Codes. Elsevier (North Holland Publishing Co.),
1997.
[26] R. Zamir, S. Shamai, and U. Erez, “Nested linear/lattice codes for structured multiterminal binning,” IEEE
Trans. Information Theory, vol. 48, pp. 1250–1276, June 2002.
[27] A. D. Wyner, “Recent results in the Shannon theory,” IEEE Trans. Information Theory, vol. 40, no. 1, pp.
2–10, Jan. 1974.
[28] I. Csiszár and J.Körner, “Towards a general theory of source networks,” IEEE Trans. Information Theory,
January 3, 2018

DRAFT

37

vol. 26, no. 2, pp. 155–165, Mar. 1980.
[29] I. Csiszár, “Linear codes for sources and source networks: Error exponents, universal coding,” IEEE Trans.
Information Theory, vol. 28, no. 4, pp. 585–592, July 1982.
[30] E. Haim, Y. Kochman, and U. Erez, “Distributed structure: Joint expurgation for the multiple-access channel,”
IEEE Trans. Information Theory, vol. 63, no. 1, pp. 5–20, Jan. 2017.
[31] J. Chen, D.-K. He, A. Jagmohan, and L. A. Lastras-Montaño, “On the reliability function
of

variable-rate

Slepian-Wolf

coding,”

Entropy,

vol.

19,

no.

8,

2017.

[Online].

Available:

http://www.mdpi.com/1099-4300/19/8/389
[32] ——, “On the reliability function of variable-rate Slepian-Wolf coding,” in Proceedings of the 45th annual
Allerton Conference on Communication, Control and Computing, Sep. 2007.
[33] N. Weinberger and N. Merhav, “Optimum trade-offs between error exponent and excess-rate exponent of
Slepian-Wolf coding,” in Proc. Int. Symp. Info. Theory (ISIT), June 2015, pp. 1565–1569.
[34] B. G. Kelly and A. B. Wagner, “Reliability in source coding with side information,” IEEE Trans. Information
Theory, vol. 58, no. 8, pp. 5086–5111, Aug. 2012.
[35] D. Krithivasan and S. S. Pradhan, “Distributed source coding using Abelian group codes: A new achievable
rate-distortion region,” IEEE Trans. Information Theory, vol. 57, no. 3, pp. 1495–1519, Mar. 2011.
[36] A. B. Wagner, “On distributed compression of linear functions,” IEEE Trans. Information Theory, vol. 57,
no. 1, pp. 79–94, Jan. 2011.

January 3, 2018

DRAFT

