1

On Hypothesis Testing Against Independence
with Multiple Decision Centers

arXiv:1708.03941v1 [] 13 Aug 2017

Sadaf Salehkalaibar, Michèle Wigger, and Roy Timo

Abstract
A distributed binary hypothesis testing problem is studied with one observer and two decision
centers. The type-II error exponents region is derived for testing against independence when the observer
communicates with the two decision centers over one common and two individual noise-free bit pipes.
When there is only a common noise-free bit pipe, the type-II error exponents region is derived for testing
against conditional independence. Finally, when the observer can communicate to the two decision
centers over a discrete memoryless broadcast channel, an achievable type-II error exponents region
is derived for testing against conditional independence. The last type-II error exponent is obtained by
splitting the observations into subblocks, having the transmitter apply hybrid joint source-channel coding
with side-information independently to each subblock, and having each receiver apply a Neyman-Pearson
test jointly over the subblocks. This decision approach avoids introducing further error exponents due
to the binning or the decoding procedures.

I. I NTRODUCTION
Consider the distributed hypothesis testing problem in Fig. 1, where a first node (the transmitter) can communicate with two remote nodes (the receivers) and each of the latter two wishes to
S. Salehkalaibar and M. Wigger are with LTCI, Telecom ParisTech, Université Paris-Saclay, 75013 Paris,
michele.wigger@telecom-paristech.fr,
S. Salehkalaibar is also with the Department of Electrical and Computer Engineering, College of Engineering, University of
Tehran, Tehran, Iran, s.saleh@ut.ac.ir,
R. Timo is with Ericsson Research, Stockholm, Sweden, roy.timo@ericsson.com,
Parts of the material in this paper have been presented at IEEE SPCOM Systems (ISWCS), Bangalore, India, June 2016.

March 19, 2018

DRAFT

2

Fig. 1.

Multi-terminal hypothesis testing with side information.

decide on the joint probability distribution underlying the observations X n , Y1n , Y2n at the three
terminals. In the scenario we consider, communication from the transmitter to the receivers either
takes place over one or multiple noise-free bit pipes or over a discrete memoryless broadcast
channel. For simplicity we will restrict attention to a binary hypothesis where either H = 0 or
H = 1. The focus of this paper is on the asymptotic regime where the length of the observed
sequences n tends to infinity and where both the type-I error probability (i.e., the probability
of deciding on hypothesis 1 when H = 0) and the type-II error probability (i.e., the probability
of deciding on hypothesis 0 when H = 1) vanish. We follow the approach in [1], [2], and aim
to quantify the fastest possible exponential decrease of the type-II error probabilities, while we
allow the type-I probabilities of error to vanish arbitrarily slowly. Ahlswede and Csiszar [1], Han
[2], and Shimokawa, Han, and Amari [3] studied the problem with only a single receiver. They
presented general upper and lower bounds on the maximum type-II error exponents, and these
bounds match when under H = 1 the joint distribution of the observations equals the product of
the marginal distributions under H = 0. This problem formulation is widely known as testing
against independence.
Rahman and Wagner [4] and Zhao and Lai [5] found similar results for scenarios with multiple
observers. Interactive observers, interactive multi-round communications between observers and
decision centers, successive refinement and privacy setups were considered in [6]–[9]. Recently,
the optimal type-II error exponent was found for distributed hypothesis testing over a noisy
communication channel [10]. In contrast to previous works, here we consider only a single
observer but multiple decision centers. There are two practical motivations for this assumption.
•

Multiple Decision Centers Interested in the Same Information: The information collected

DRAFT

March 19, 2018

3

at a given sensor is required at multiple decision centers to make a correct guess on their
desired hypotheses. In this sense, the sensor will be interested in sending information about
its observed sequence to multiple decision centers. This work treats the scenario where
communication to the two decision centers takes place over a common network.
•

Single Decision Center with Uncertain Local Observation: There is only a single decision
center, and the probability distribution of the decision center’s observation under each of
the two hypotheses is uncertain a priori. For example, there could be two possible options,
depending on some other phenomenon that the decision center is not interested to detect.
In this case, Y1n and Y2n model the observations at the decision center for each of the two
options.

A main feature of the scenario that we consider, is that the observer is interested in extracting
and transmitting information about its observation X n that is useful to both decision centers.
There can thus be an inherent tradeoff in the problem, in that some information might be
more beneficial for Receiver 1 than for Receiver 2 or vice versa. The goal of this paper is to
shed light on this tradeoff. In fact, we will present two examples, where in the first example
there is no tradeoff between the maximum type-II error exponents that can simultaneously be
achieved at both receivers, whereas in the second example such a tradeoff exists. As will be
explained shortly, in this paper, we consider communications of positive rates. Interestingly, for
zero-rate communication, such a tradeoff never exists. That means, there is a single strategy
at the transmitter that is optimal for both decision centers. This optimal strategy is simply the
strategy from [2], [3] where the transmitter sends a single bit indicating whether its observation
is typical with respect to the distribution under H = 0, irrespective of the distribution of the
receiver observation.
In this paper, we consider the special case of testing against independence or testing against
conditional independence, and we propose coding schemes for three different one-to-two communication scenarios. In the first scenario, communication takes place over a Gray-Wyner source
coding network [11] with three noise-free bit pipes, the first connecting the transmitter with both
receivers and the other two connecting the transmitter with only one of the two receivers. For
March 19, 2018

DRAFT

4

this scenario, the type-II error exponents region achieved by our scheme is optimal when testing
against independence. In the second scenario, communication takes place over a Kaspi/HeegardBerger source coding network [12], [13] with a single common noise-free bit pipe connecting the
transmitter to both receivers. Moreover, here the first decision center has access to an additional
side information Z1n . For this scenario, the type-II error exponents region achieved by our scheme
is optimal when testing against conditional independence given the additional observation Z1n .
In the third scenario, Receiver 1 again observes side-information Z1n , and communication takes
place over a discrete memoryless broadcast channel (BC).
For the second and third scenarios, our coding scheme is based on random binning so
as to exploit the side-information at Receiver 1. The idea of using binning for distributed
hypothesis testing was introduced by Shimokawa, Han, and Amari [3] for a single-receiver setup.
Interestingly, the standard approach to first analyze the probability that the receiver can recover
the correct codeword within the indicated bin and then condition on the successful recovery
of this codeword to analyze the type-II error probability, yields a result with two competing
error exponents. A first exponent that results from the recovery of the correct codeword and
a second one that results from hypothesis testing. Rahman and Wagner [4] showed that when
testing against conditional independence the binning error exponent can be made to disappear
by changing the way the receiver takes its decision and by applying Stein’s lemma to analyze
the performance. A similar approach has been recently proposed also by Sreekuma and Gunduz
[10] for hypothesis testing over noisy multi-access channels.
Inspired by [4] and [10], we propose the following scheme: Each terminal splits its observation
into many subblocks and then applies a Heegard-Berger coding scheme [12], [13] to each
subblock. The receivers collect all the i.i.d. blocks and apply a Neyman-Pearson test over all
these subblocks to decide on the desired hypothesis. The analysis of the scheme is performed
by analysing a related hypothesis testing problem where the code constructions of all blocks are
revealed to all terminals in the form of an additional i.i.d. observation that can be used to test
on the hypothesis. To analyse the error probabilities of this related scenario, similar steps to the
ones indicated in [4] are followed.
DRAFT

March 19, 2018

5

The same coding and analysis approach is also used for the third scenario where the communication link is noisy. That means:
•

Each terminal splits its sequence of observations into subblocks.

•

The transmitter applies hybrid joint source-channel coding with side-information [14] to
each of subblock.

•

Each receiver groups the subblocks and applies a Neyman-Pearson test over these i.i.d.
subblocks.

Following similar analysis steps as in [4] allows to condition on correct decoding of the quantized
sequences without introducing additional error exponents. Notice that in our analysis, hybrid
coding can be replaced by any joint source-channel coding technique that builds on a random
code construction where the receivers’ reconstructions are codewords generated at the transmitter.
We conclude this section with an outline of the paper and some notation.

A. Paper Outline
In Section II, we present our scheme and result for the Gray-Wyner network and evaluate it
for a Gaussian example. In Section III, we present our scheme and result for the Heegard-Berger
network with side information, and evaluate it for a similar Gaussian example. In Section IV,
we present our scheme and result for discrete memoryless BCs. Section V concludes the paper.

B. Notation
Random variables are denoted by capital letters, e.g., X, Y , and their realizations by lower
case letters, e.g., x, y. Script symbols such as X and Y stand for alphabets of random variables
and realizations, and X n and Y n for the corresponding n-fold Cartesian products. Sequences of
random variables (Xi , ..., Xj ) and realizations (xi , . . . , xj ) are abbreviated by Xij and xji . When
i = 1, then we also use the notations X j and xj instead of X1j and xj1 .
The probability mass function (pmf) of a finite random variable X is written as PX ; the
conditional pmf of X given Y is written as PX|Y . Entropy, conditional entropy, and mutual
information of random variables X and Y are denoted by H(X), H(X|Y ), and I(X; Y ).
March 19, 2018

DRAFT

6

Fig. 2.

Hypothesis testing over a Gray-Wyner network.

Differential entropy and conditional differential entropy of continuous random variables X and
Y are indicated by h(X) and h(X|Y ). All entropies and mutual informations in this paper are
meant with respect to the distribution under hypothesis H = 0. The term D(P ||Q) stands for
the Kullback-Leibler divergence between two pmfs P and Q over the same alphabet.
For a given PX and a constant µ > 0, let Tµn (PX ) = {xn : |#{i : xi = x}/n − PX (x)| ≤
µPX (x), ∀x ∈ X } be the set of µ-typical sequences in X n [15]. Similarly, Tµn (PX,Y ) stands for
the set of jointly µ-typical sequences.
The expectation operator is written as E[.]. A Gaussian distribution with mean a and variance
σ 2 is written as N (a, σ 2 ). We abbreviate independent and identically distributed by i.i.d.. Finally,
the log(.)-function is taken with respect to base 2.
II. H YPOTHESIS T ESTING OVER A G RAY-W YNER N ETWORK
A. Setup
Consider the distributed hypothesis testing problem with one transmitter (the observer) and
two receivers (the decision centers) in Fig. 2. The transmitter observes the sequence X n , and
Receivers 1 and 2 observe sequences Y1n and Y2n , where under the null hypothesis
H = 0 : (X n , Y1n , Y2n ) ∼ i.i.d. PXY1 Y2 ,

(1)

and under the alternative hypothesis
H = 1 : (X n , Y1n , Y2n ) ∼ i.i.d. PX PY1 Y2 .

(2)

Here, PXY1 Y2 is a given joint distribution over the finite product alphabet X × Y1 × Y2 , and PX
and PY1 Y2 denote its marginals, i.e.,
PX (x) =

X

PXY1 Y2 (x, y1 , y2 ),

x ∈ X,

y1 ∈Y1 ,y2 ∈Y2
DRAFT

March 19, 2018

7

PY1 Y2 (y1 , y2 ) =

X

PXY1 Y2 (x, y1 , y2 ), (y1 , y2 ) ∈ Y1 × Y2 .

x∈X

The transmitter communicates with the two receivers over 1 common and 2 individual noise-free
bit pipes. Specifically, it computes messages (M0 , M1 , M2 ) = φ(n) (X n ), using a possibly stochastic encoding function φ(n) of the form φ(n) : X n → {0, ..., 2nR0 } × {0, ..., 2nR1 } × {0, ..., 2nR2 },
and sends message M0 over the common pipe and messages M1 and M2 over the two individual
pipes. Receiver 1 observes messages M0 and M1 and decides on the hypothesis H ∈ {0, 1}
(n)

by means of a decoding function g1 : Y1n × {0, ..., 2nR0 } × {0, ..., 2nR1 } → {0, 1}. It produces
(n)

Ĥ1 = g1 (Y1n , M0 , M1 ). Similarly, Receiver 2 observes messages M0 and M2 and decides on the
(n)

hypothesis H by means of a decoding function g2 : Y2n × {0, ..., 2nR0 } × {0, ..., 2nR2 } → {0, 1}.
(n)

It then produces Ĥ2 = g2 (Y2n , M0 , M2 ).
Definition 1: For each  ∈ (0, 1), an exponents-rates tuple (θ1 , θ2 , R0 , R1 , R2 ) is called achievable over the Gray-Wyner network if there exists a sequence of encoding and decoding
(n)

(n)

functions {(φ(n) , g1 , g2 )}∞
n=1 such that for i ∈ {1, 2} and all positive integers n, the corresponding sequences of type-I error probabilities
∆

αi,n = Pr[Ĥi = 1|H = 0],
and type-II error probabilities
∆

βi,n = Pr[Ĥi = 0|H = 1],
satisfy the following inequalities,
αi,n ≤ ,
and
1
log βi,n ≥ θi .
n→∞ n

− lim

Definition 2: Given nonnegative rates (R0 , R1 , R2 ), define the exponents region EGW (R0 , R1 , R2 )
as the closure of all non-negative exponent pairs (θ1 , θ2 ) for which (θ1 , θ2 , R0 , R1 , R2 ) is achievable over the Gray-Wyner network for every  ∈ (0, 1).
Remark 1: The exponents region EGW (R0 , R1 , R2 ) only depends on the marginal distributions
PXY1 and PXY2 under both hypotheses. In particular, EGW (R0 , R1 , R2 ) remains unchanged if
under hypothesis H = 1, we replace PY1 Y2 by PY1 · PY2 .
March 19, 2018

DRAFT

8

B. Coding Scheme

Fix µ > 0, a sufficiently large blocklength n, and a joint conditional distribution PU0 U1 U2 |X .
Consider nonnegative rates (R0 , R1 , R2 ) satisfying the rate constraints
R0 > I(U0 ; X),

(3)

R1 > I(U1 ; X|U0 ),

(4)

R2 > I(U2 ; X|U0 ).

(5)

Codebook Generation: Randomly generate a codebook C0 := {U0n (m0 ) : m0 ∈ {1, ..., 2nR0 }}
by drawing each entry of the n-length codeword U0n (m0 ) in an i.i.d. manner according to the
pmf PU0 . For each index m0 ∈ {1, ..., 2nR0 } and each i ∈ {1, 2}, randomly generate a codebook
Ci (m0 ) := {Uin (mi |m0 ) : mi ∈ {1, ..., 2nRi }} by drawing the j-th entry of each codeword
Uin (mi |m0 ) in a memoryless manner according to the conditional pmf PUi |U0 (.|U0,j (m0 )), where
U0,j (m0 ) denotes the j-th symbol of codeword U0n (m0 ). Reveal the realizations C0 , {C1 (·)}, and
{C2 (·)} of the randomly generate codebooks to all terminals.
Transmitter: Given that it observes the source sequence xn , the transmitter looks for a tuple of
n
indices (m0 , m1 , m2 ) such that (xn , un0 (m0 ), un1 (m1 |m0 ), un2 (m2 |m0 )) ∈ Tµ/2
(PXU0 U1 U2 ), where

un0 (m0 ), un1 (m1 |m0 ), un2 (m2 |m0 ) denote the corresponding codewords in codebooks C0 , C1 (·), and
C2 (·). If this check is successful, the transmitter picks one of these tuples uniformly at random
and sends the corresponding indices m0 , m1 , m2 over the bit pipes: m0 over the common bit pipe,
m1 over the individual bit pipe to Receiver 1, and m2 over the individual bit pipe to Receiver 2.
Otherwise, it sends the value 0 over each of the three bit pipes.
Receiver i ∈ {1, 2}: Assume that Receiver i observes messages M0 = m0 and M1 = m1
and source sequence Yin = yin . If m0 = 0, it declares Ĥi = 1. If m0 6= 0, it checks whether
(yin , un0 (m0 ), uni (mi |m0 )) ∈ Tµn (PYi U0 Ui ). If this test is successful, Receiver i declares Ĥi = 0.
Otherwise, it declares Ĥi = 1.
DRAFT

March 19, 2018

9

C. Exponents Region
The main result of this section is a single-letter characterization of the exponents region
EGW (R0 , R1 , R2 ). It is achieved by the scheme described in the preceeding subsection.
Theorem 1: The exponents region EGW (R0 , R1 , R2 ) is given by the set of all nonnegative pairs
(θ1 , θ2 ) that satisfy
θ1 ≤ I(U0 , U1 ; Y1 ),

(6)

θ2 ≤ I(U0 , U2 ; Y2 ),

(7)

for some auxiliary random variables (U0 , U1 , U2 ) satisfying the Markov chain (U0 , U1 , U2 ) →
X → (Y1 , Y2 ) and the rate constraints
R0 ≥ I(U0 ; X),

(8)

R1 ≥ I(U1 ; X|U0 ),

(9)

R2 ≥ I(U2 ; X|U0 ).

(10)

Proof: See [16].
In the above theorem it suffices to consider auxiliary random variables U0 , U1 , and U2 over
alphabets U0 , U1 , and U2 whose sizes satisfy: |U0 | ≤ |X | + 4, |U1 | ≤ |X | · |U0 | + 1 and |U2 | ≤
|X | · |U0 | + 1. This follows by simple applications of Carathodory’s theorem.

D. Example
We propose an example to investigate the exponents region of Theorem 1. Theorem 1 was
stated and proved for discrete memoryless sources. It can be shown that it remains valid also
when sources are memoryless and jointly Gaussian [15, Chap. 3]. We focus on the regime
R1 = R2 = 0. Consider a setup where under both hypotheses X ∼ N (0, 1). Moreover, under
hypothesis
H = 0:

March 19, 2018

Y1 = X + N1 ,

(11)

Y2 = X + N2 ,

(12)
DRAFT

10

where N1 ∼ N (0, σ12 ) and N2 ∼ N (0, σ22 ) are independent of each other and of X. Under
hypothesis
H = 1:

Y1 = X 0 + N1 ,

(13)

Y2 = X 0 + N2 ,

(14)

where X 0 ∼ N (0, 1) is independent of the triple X, N1 , N2 .
As we show in the following, for this example the exponents region EGW (R0 , 0, 0) evaluates
to the set of all nonnegative exponent pairs (θ1 , θ2 ) that satisfy


1
1 + σi2
θi ≤ log
,
i ∈ {1, 2}.
2
2−2R0 + σi2
That these exponent pairs lie in EGW (R0 , 0, 0) can be seen by evaluating (6)–(8) for an auxiliary
U0 that satisfies X = U0 + W0 with independent zero-mean Gaussians W0 and U0 of variances
2−2R0 and 1 − 2−2R0 . To prove that EGW (R0 , 0, 0) is no larger than the proposed region, notice
that by the Entropy Power Inequality (EPI) [15]:
h(Yi |U0 ) ≥


1
log 22h(X|U0 ) + 22h(Ni ) ,
2

i ∈ {1, 2}.

(15)

Since (8) is equivalent to R0 ≥ h(X)−h(X|U0 ) and since h(X|U0 ) ≤ h(X), the EGW is included
in the set of all pairs (θ1 , θ2 ) that satisfy
θi ≤ h(Yi ) −


1
log 22α + 22h(Ni ) ,
2

i ∈ {1, 2},

(16)

for some α ∈ [h(X) − R0 , h(X)]. The desired inclusion follows then by noting that the righthand side of (16) is decreasing in α and there is thus no loss in optimality when replacing α by
h(X) − R0 , or equivalently replacing 22α by 22h(X) 2−2R0 = 2πe · 2−2R0 .
0.4

R=1

0.35

R=0.75
0.3

R=0.5

θ2

0.25

0.2

0.15

0.1

0.05

0

0

0.05

0.1

0.15

0.2

0.25

0.3

0.35

0.4

θ1

Fig. 3.

DRAFT

Exponents region of Theorem 1 for σ12 = 0.2 and σ22 = 0.3.

March 19, 2018

11

Fig. 4.

Hypothesis testing over a Heegard-Berger network with additional side information at one receiver.

Fig. 3 illustrates this region EGW (R0 , 0, 0) for different rates R0 .

III. H YPOTHESIS T ESTING OVER A H EEGARD -B ERGER N ETWORK WITH
S IDE -I NFORMATION
A. Setup
This section focuses on a related hypothesis testing problem with only a single, common
bit pipe from the transmitter to the receivers, see Fig. 4. As before, the transmitter observes
the sequence X n , and Receivers 1 and 2 observe Y1n and Y2n , respectively. In this new model,
Receiver 1 additionally also observes a side information Z1n whose pairwise distribution with
X n and with Y1n does not depend on the hypothesis H. In fact, under the null hypothesis
H = 0 : (X n , Y1n , Y2n , Z1n ) ∼ i.i.d. PXY1 Y2 Z1 ,

(17)

and under the alternative hypothesis,
H = 1 : (X n , Y1n , Y2n , Z1n ) ∼ i.i.d. PXZ1 PY1 |Z1 PY2 .

(18)

Here PXY1 Y2 Z1 is a given joint distribution over a finite product alphabet X ×Y1 ×Y2 ×Z1 , and
PXZ1 , PY1 |Z1 and PY2 denote its conditional marginals. The test here is “against conditional independence” because Z1 has the same joint distribution with the source X under both hypotheses
and because under H = 1, Y1 is conditionally independent of X given Z1 .
The transmitter communicates with the two receivers over a common noise-free bit pipe.
Specifically, it computes the message M = φ(n) (X n ) using a possibly stochastic encoding
function φ(n) of the form φ(n) : X n → {0, ..., 2nR } and sends message M over the common
pipe. Receiver 1 observes message M and decides on the hypothesis H ∈ {0, 1} by means of a
(n)

(n)

decoding function g1 : Y1n × Z1n × {0, ..., 2nR } → {0, 1}. It produces Ĥ1 = g1 (Y1n , Z1n , M ).
March 19, 2018

DRAFT

12

Similarly, Receiver 2 observes message M and decides on the hypothesis H by means of a
(n)

(n)

decoding function g2 : Y2n × {0, ..., 2nR } → {0, 1}. It then produces Ĥ2 = g2 (Y2n , M ).
Definition 3: For each  ∈ (0, 1), an exponents-rate tuple (θ1 , θ2 , R) is called -achievable
over the Heegard-Berger network if there exists a sequence of encoding and decoding functions
(n)

(n)

{(φ(n) , g1 , g2 )}n such that for i ∈ {1, 2} and for all sufficiently large n, we have αi,n ≤  and
− limn→∞

1
n

log βi,n ≥ θi .

Definition 4: For a given rate R, we define the exponents region EHB (R) as the closure of all
non-negative exponent pairs (θ1 , θ2 ) for which (θ1 , θ2 , R) is -achievable over the Heegard-Berger
network for every  ∈ (0, 1).
Notice that similar to Remark 1, according to the distribution under H = 1, EHB (R) depends
only on the marginal distributions PXZ1 , PXY1 |Z1 and PXY2 .

B. Coding Scheme
Fix µ > 0, sufficiently large positive integers k and B, and a joint conditional distribution
PU0 U1 |X . Consider also nonnegative rates R0 and R1 that satisfy
R0 > I(U0 , X),

(19)

R1 + R10 > I(U1 ; X|U0 ),

(20)

R10 < I(U1 ; Z1 |U0 ).

(21)

Choose rate and blocklength as R = R0 + R1 and n = kB.
Codebook Generation: Let PU0 and PU1 |U0 be the marginal and conditional marginal pmfs
of PX · PU0 U1 |X .
k
For each block b ∈ {1, . . . , B}, randomly generate a codebook C0,b := {U0,b
(m0 ) : m0 ∈
k
{1, ..., 2kR0 }} by drawing each entry of the n-length codeword U0,b
(m0 ) i.i.d. according to the

marginal pmf PU0 . For each block b ∈ {1, . . . , B} and each index m0 , randomly generate a
0

k
codebook C1,b (m0 ) := {U1,b
(s1 |m0 ) : s1 ∈ {1, ..., 2k(R1 +R1 ) }} by drawing each entry of the nk
length codeword U1,b
(s1 |m0 ) i.i.d. according to the conditional marginal pmf PU1 |U0 (.|U0,b,j (m0 )).
k
Here, U0,b,j (m0 ) denotes the j-th symbol of codeword U0,b
(m0 ).
DRAFT

March 19, 2018

13

Reveal the realizations {C0,b } and {C1,b (·)} of the randomly generated codebooks to all
terminals.
0

Randomly assign a bin index m1 ∈ {1, ..., 2kR1 } to each index s1 ∈ {1, ..., 2k(R1 +R1 ) }. Let
0

ν : {1, ..., 2k(R1 +R1 ) } → {1, ..., 2kR1 },
denote the chosen bin assignment, which is revealed to all terminals.
Transmitter: The transmitter observes a source sequence xn and splits it into B blocks,
xn = (xk1 , . . . , xkB ). For each block b ∈ {1, . . . , B}, it considers codebooks C0,b and {C1,b (·)} and
k
(PXU0 U1 ).
looks for a pair of indices (m0,b , s1,b ) such that (xkb , uk0,b (m0,b ), uk1,b (s1,b |m0,b )) ∈ Tµ/2

If there are multiple such pairs, it picks one of them uniformly at random.
If for some block b, the transmitter cannot find a desired pair (m0,b , s1,b ), it sends the message
m = 0 over the common bit pipe. Otherwise, it sends the tuple
m = (m0,1 , . . . , m0,B , m1,1 , . . . , m1,B ),

(22)

where m1,b = ν(s1,b ).
Receiver 1: Assume that Receiver 1 observes message M = m and source sequences Y1n = y1n
and Z1n = z1n . If m = 0, Receiver 1 declares Ĥ1 = 1. Otherwise, it decomposes its observations

 B
k
k
according to the B blocks, m0,b , m1,b , y1,b
, z1,b
, C0,b , {C1,b (·)} b=1 .
It then applies a Neyman-Pearson test1 to decide on H based on these i.i.d. blocks, in a way
that the type-I error probability does not exceed /8.
Receiver 2: If m = 0, Receiver 2 declares Ĥ2 = 1. Otherwise, it decomposes its observations

 B
k
according to the B blocks, m0,b , y2,b
, C0,b b=1 . It then applies a Neyman-Pearson test to decide
on H based on these i.i.d. blocks, so that the type-I error probability does not exceed /8.

C. Results on Exponents Region
in
Let EHB
(R) be the set of all nonnegative pairs (θ1 , θ2 ) that satisfy

θ1 ≤ I(U0 , U1 ; Y1 |Z1 )

1

(23)

Notice that the Neyman Pearson test is designed for the random experiment where the codebooks C0,b and {C1,b (·)} are part

of the observations at the receivers.

March 19, 2018

DRAFT

14

θ2 ≤ I(U0 ; Y2 )

(24)

for some auxiliary random variables U0 , U1 so that the Markov chain (U0 , U1 ) → X → (Y1 , Y2 , Z1 ),
and the following rate constraint hold:
R ≥ I(U0 ; X) + I(U1 ; X|U0 , Z1 ).

(25)

in
Notice that to calculate EHB
(R) it suffices to consider auxiliary random variables U0 , U1 , and

U2 over alphabets U0 , U1 , and U2 whose sizes satisfy: |U0 | ≤ |X | + 2 and |U1 | ≤ |X | · |U0 | + 1.
in
The exponents region EHB
(R) can be achieved by the scheme presented in the preceeding

subsection.
in
in
(R) ⊆ EHB (R).
(R) is achievable, i.e., EHB
Theorem 2: The set EHB

Proof: See Appendix A.
in
The scheme in the preceeding subsection that achieves EHB
performs codeword binning. As

the following Theorem 3 shows, it is optimal in some special cases. Binning has previously
been considered for other distributed hypothesis testing problems [1], [4], [7], [8], [17]–[20]. In
particular, [4], [8] proved that binning is necessary to attain an optimal error exponent.
Definition 5: We say that Z1 is less noisy than Y2 , if for all auxiliary random variables U
satisfying the Markov chain U → X → (Y1 , Y2 , Z1 ) the following inequality holds:
I(U ; Z1 ) ≥ I(U ; Y2 ).

(26)

in
Theorem 3: When Z1 is less noisy than Y2 , EHB
= EHB .

Proof: Achievability follows from Theorem 2. The converse is proved in Appendix B.

D. Example
Theorem 3 was stated and proved for discrete memoryless sources. It can be shown that it
remains valid also when sources are memoryless and jointly Gaussian [15, Chap. 3].
Consider the following scenario. Under both hypotheses, X ∼ N (0, 1) and Z1 = X + Nz ,
where Nz ∼ N (0, σz2 ) is independent of X. Moreover, under hypothesis
H = 0:

DRAFT

Y1 = X + Z1 + N1

(27)

Y2 = Z1 + N2 ,

(28)
March 19, 2018

15

where N1 ∼ N (0, σ12 ) and N2 ∼ N (0, σ22 ) are independent of each other and of (X, Z1 ), and
under hypothesis
Y1 = X 0 +

H = 1:

2 + σz2
· Z1 + N1 ,
1 + σz2

(29)

Y2 = Z10 + N2 ,

(30)

2

σz
2
0
where X 0 ∼ N (0, 1+σ
2 ) and Z1 ∼ N (0, 1 + σz ) are independent of each other and of the tuple
z

(X, Z1 , N1 , N2 ).
The described scenario satisfies the less noisy condition in (26). By Theorem 3, for this
in
example region EHB is thus equal to EHB
. Moreover, the exponents region EHB (R) evaluates to

the set of all nonnegative exponent pairs (θ1 , θ2 ) that satisfy
 2

1
σz + σ12 (1 + σz2 )
θ1 ≤ log
2
22α̃ σz2 + σ12 (1 + σz2 )


1
1 + σz2 + σ22
θ2 ≤ log
,
2
2−2(α̃+R) (1 + σz2 ) + σ22

(31a)
(31b)

for some α̃ ∈ [−R, 0].
That these exponent pairs lie in EHB (R) can be seen by evaluating (6)–(8) for auxiliaries
U0 and U1 that are jointly Gaussian with X and so that X = U1 + W1 and U1 = U0 + W0
for independent zero-mean Gaussians W1 , W0 and U0 that are of variances
1)2−2(α̃+R) − σz2 (1 +

1
)
(σz2 +1)2−2α̃ −1

σz2
,
(σz2 +1)2−2α̃ −1

(σz2 +

and (1 + σz2 )(1 − 2−2(α̃+R) ), respectively.

The proof that EHB (R) is no larger than the proposed region is similar to the converse proof
for the example in Section II-D. Indeed, by the EPI:

1
log 22h(Z1 |U0 ) + 22h(N2 ) ,
2

1
h(Y1 |U0 , U1 , Z1 ) ≥ log 22h(X|U0 ,U1 ,Z1 ) + 22h(N1 ) .
2
h(Y2 |U0 ) ≥

(32)

Moreover, rate-constraint (25) is equivalent to
I(U0 ; X) + I(U1 ; X|U0 , Z1 ) = h(X) − h(X|U0 ) + h(X|U0 , Z1 ) − h(X|U0 , U1 , Z1 )
= h(X) − I(X; Z1 |U0 ) − h(X|U0 , U1 , Z1 )
= h(X) − h(Z1 |U0 ) + h(Z1 |X, U0 ) − h(X|U0 , U1 , Z1 )
= h(X, Z1 ) − h(Z1 |U0 ) − h(X|U0 , U1 , Z1 ),
March 19, 2018

(33)
DRAFT

16
0.35

0.3

0.25

2

0.2

θ

R=1
0.15

R=0.75

0.1

R=0.5
0.05

0

0.2

0.25

0.3

0.35

0.4

0.45

0.5

θ1

Fig. 5.

Exponents region for σz2 = 0.7, σ12 = 0.2 and σ22 = 0.3.

where the last equality follows from the Markov chain U0 → X → Z1 .
Defining now
α := h(X|U0 , U1 , Z1 )

and β := h(Z1 |U0 ),

(34)

above inequalities show that EHB (R) is included in the set of all pairs (θ1 , θ2 ) that satisfy

1
θ1 ≤ h(Y1 |Z1 ) − log 22α + 22h(N1 )
(35)
2

1
θ2 ≤ h(Y2 ) − log 22β + 22h(N2 ) ,
(36)
2
for some choice of parameters α ≤ h(X|Z1 ) and β ≤ h(Z1 ) so that
(α − h(X|Z1 )) + (β − h(Z1 )) ≥ −R.

(37)

Now, since the right-hand sides of (35) and (36) are decreasing in the parameters α and β,
these parameters should be chosen so that the rate-constraint (37) is satisfied with equality. In
other words, for fixed α, the optimal β is obtained by solving (37) under the equality constraint.
Defining α̃ := (α − h(X|Z1 )) ≤ 0 and expressing the optimal β in terms of α̃ then establishes
the desired inclusion of EHB (R) in the set of pairs (θ1 , θ2 ) given in (31).
The boundary of the exponents region EHB (R) is illustrated in Fig. 5 for different values of
the rate R. Generally, on this boundary θ1 > θ2 , because Receiver 1 has the additional sideinformation Z1 . One further observes a trade-off between the two exponents θ1 and θ2 . In other
words, having a larger exponent θ1 comes at the expense of a smaller exponent θ2 , and vice
versa. In the example without side-information in Section II-D, such a tradeoff did not arise.
DRAFT

March 19, 2018

17

E. Extension: Gray-Wyner Network with Side-Information
The exponents regions of Theorems 1 and 2 can be combined to derive an exponents region
that is achievable in a scenario with three bit pipes and the additional side information Z1n at
Receiver 1.
For this extended scenario, we propose to apply the code construction, encoding and decision
at Receiver 2 described in Section II-B and the decision at Receiver 1 described in Section III-B.
in
This strategy achieves the exponents region Egeneral
presented in the following remark.
in
Remark 2: Let Egeneral
(R0 , R1 , R2 ) be the set of all nonnegative pairs (θ1 , θ2 ) that satisfy

θ1 ≤ I(U0 , U1 ; Y1 |Z1 ),

(38)

θ2 ≤ I(U0 , U2 ; Y2 ),

(39)

for some auxiliary random variables (U0 , U1 , U2 ) satisfying the Markov chain (U0 , U1 , U2 ) →
X → (Y1 , Y2 , Z1 ) and
R0 ≥ I(U0 ; X),

(40)

R1 ≥ I(U1 ; X|U0 , Z1 ),

(41)

R2 ≥ I(U2 ; X|U0 ).

(42)

in
The exponents region Egeneral
(R0 , R1 , R2 ) is achievable over the Heegard-Berger network with

side-information when there is an additional noise-free bit pipe of rate Ri from the transmitter
in
to Receiver i, for i ∈ {1, 2}. Moreover, to evaluate Egeneral
(R0 , R1 , R2 ) it suffices to consider

auxiliary random variables U0 , U1 , U2 over alphabets U0 , U1 , and U2 whose sizes satisfy the
following three conditions: |U0 | ≤ |X | + 4, |U1 | ≤ |X | · |U0 | + 2, and |U2 | ≤ |X | · |U0 | + 2.
IV. H YPOTHESIS T ESTING OVER N OISY BC S
A. Setup
This section considers hypothesis testing over a discrete memoryless BC (W, V1 , V2 , PV1 V2 |W ),
where W denotes the finite channel input alphabet, V1 and V2 the finite channel output alphabets
at Receivers 1 and 2, and PV1 V2 |W the BC transition pmf. We assume that the BC is degraded, so
that for each (w, v1 , v2 ) ∈ W ×V1 ×V2 the BC transition pmf decomposes as PV1 V2 |W (v1 , v2 |w) =
March 19, 2018

DRAFT

18

Trans.

Fig. 6.

Hypothesis testing over a noisy BC.

PV1 |W (v1 |w)·PV2 |V1 (v2 |v1 ). The setup is illustrated in Fig. 6. The transmitter observes a sequence
X n and produces its channel inputs W n := (W1 , . . . , Wn ) as W n = Φ(n) (X n ) by means
of a possibly stochastic encoding function Φ(n) : X n → W n . Receivers 1 and 2 observe the
corresponding channel outputs V1n := (V1,1 , . . . , V1,n ) and V2n := (V2,1 , . . . , V2,n ), as well as the
source sequences (Y1n , Z1n ) and Y2n defined in the previous sections. Both receivers guess the
hypothesis H underlying the joint distribution of the source sequences X n , Y1n , Y2n , Z1n . Assume
that under hypothesis
H = 0 : (X n , Y1n , Y2n , Z1n ) ∼ i.i.d. PXY1 Y2 Z1 ,

(43)

H = 1 : (X n , Y1n , Y2n , Z1n ) ∼ i.i.d. PXZ1 PY1 |Z1 PY2 .

(44)

and under hypothesis

Type-I and type-II errors as well as the exponents region are defined in analogy to the previous
two sections. We denote the exponents region for this scenario by Enoisy .

B. Coding Scheme
Fix µ > 0, sufficiently large positive integers k and B, and a joint conditional distribution
PU0 U1 |X over finite auxiliary alphabets U0 and U1 . Consider also nonnegative rates R0 , R1 , R10
that satisfy

DRAFT

R1 ≤ I(U1 ; V1 , Z1 |U0 )

(45)

R0 ≤ I(U0 ; V2 )

(46)

R0 > I(U0 ; X),

(47)

R1 > I(U1 ; X|U0 ).

(48)
March 19, 2018

19

Finally, fix a function f : U0 × U1 × X → W.
Code Construction: For each block b ∈ {1, ..., B}, randomly generate a codebook C0,b =
k
k
{U0,b
(m0 ) : m0 ∈ {1, ..., 2kR0 }} by drawing each entry of the n-length codeword U0,b
(m0 )

i.i.d. according to the pmf PU0 . Moreover, for each index m0 , randomly generate a codebook
k
C1,b (m0 ) := {U1,b
(m1 |m0 ) : m1 ∈ {1, ..., 2kR1 }} by drawing each entry of the k-length codeword
k
U1,b
(m1 |m0 ) i.i.d. according to the conditional pmf PU1 |U0 (.|U0,b,j (m0 )), where U0,b,j (m0 ) denotes
k
the j-th symbol of U0,b
(m0 ). Reveal the realizations {C0,b } and {C1,b (·)} of the randomly

generated codebooks to all terminals.
Transmitter: It observes a source sequence xn and splits it into B subblocks xn = (xk1 , ..., xkB ).
For each block b, it looks for a pair of indices (m0,b , m1,b ) ∈ {1, . . . , 2nR1 } × {1, . . . , 2nR2 } such
k
(PXU0 U1 ). where uk0,b (m0,b ) and uk1,b (m1,b |m0,b ) are
that (xkb , uk0,b (m0,b ), uk1,b (m1,b |m0,b )) ∈ Tµ/2

codewords from the chosen codebooks C0,b and {C1,b (·)} If the typicality test is successful,
the transmitter picks one of the pairs satisfying the test at random. Otherwise, it picks a pair
(m0,b , m1,b ) uniformly at random over {1, . . . , 2nR1 }×{1, . . . , 2nR2 }. It finally sends the k inputs
w(b−1)k+j = f (u0,b,j (m0,b ), u1,b,j (m1,b |m0,b ), x(b−1)k+j ), j ∈ {1, . . . , k}, over the channel.
Receiver 1: Assume that it observes the sequence of channel outputs v1n and the source se k k k
 B
, y1,b , z1,b , C0,b , {C1,b (·)} b=1 .
quences y1n and z1n . It decomposes its observations into B blocks, v1,b
It then applies a Neyman-Pearson test to decide on H based on these i.i.d. blocks, in a way that
the type-I error probability does not exceed /4.
Receiver 2: Assume that it observes the sequence of channel outputs v2n and the source
 k k
 B
sequences y2n . It decomposes its observations according to the B blocks, v2,b
, y2,b , C0,b b=1 .
It then applies a Neyman-Pearson test to decide on H based on the these i.i.d. blocks, so that
the type-I error probability does not exceed /4.
C. Exponents Region
hyb
Let Enoisy
be the set of all nonnegative pairs (θ1 , θ2 ) satisfying

March 19, 2018

θ1 ≤ I(U0 , U1 ; Y1 |Z1 ),

(49)

θ2 ≤ I(U0 ; Y2 ),

(50)
DRAFT

20

for some auxiliary random variables (U0 , U1 ) over finite auxiliary alphabets U0 × U1 satisfying
the Markov chains
(U0 , U1 ) → X → (Z1 , Y1 , Y2 ),

(51)

(Y1 , Y2 , Z1 ) → (U0 , U1 , X) → W → (V1 , V2 ),

(52)

and some function f : U0 × U1 × X → W where W = f (U0 , U1 , X) and
I(U1 ; X|U0 ) ≤ I(U1 ; V1 , Z1 |U0 ),
I(U0 ; X) ≤ I(U0 ; V2 ).

(53)
(54)

hyb
hyb
Theorem 4: The set of Enoisy
is achievable, i.e., Enoisy
⊆ Enoisy .

Proof: See Appendix C.
hyb
To evaluate the region Enoisy
, it sufffices to consider auxiliaries whose alphabets satisfy the
hyb
following two conditions: |U0 | ≤ |X | + 4 and |U1 | ≤ |X | · |U0 | + 2. The exponents region Enoisy
is

achieved by means of hybrid joint source-channel coding with side-information. Constraints (52),
(53), and (54) ensure that the receivers can decode their intended hybrid coding codewords; a U0 codeword is decoded at both receivers and a U1 -codeword at Receiver 1 only. These codewords
are then used at the receivers for testing against conditional independence, see the exponents
expression in (49) and (50). Notice that hybrid joint source-channel coding also includes separate
source-channel coding as a special case [14]. In fact, the separate scheme’s exponents region can
be derived by considering U0 = (W0 , Ũ0 ) and U1 = (W, Ũ1 ) where (Ũ0 , Ũ1 , W0 ) are auxiliary
random variables which satisfy the Markov chains (Ũ0 , Ũ1 ) → X → Z1 and W0 → W →
(V1 , V2 ), and (W0 , W ) are independent of (Ũ0 , Ũ1 , X, Y1 , Z1 , Y2 ).
The analysis steps in Appendix C can be adapted to any joint source-channel coding scheme
based on random coding other than hybrid coding. Combined with Neyman-Pearson testing at
hyb
the receivers, such a scheme can be shown to achieve error exponents as in Enoisy
except that

(52)–(54) have to be replaced by the conditions of the new joint source-channel coding scheme
and U0 and U1 by the random variables associated with the codewords decoded at each of the
two receivers.
DRAFT

March 19, 2018

21

V. C ONCLUSION AND D ISCUSSION

This paper considers a distributed hypothesis testing problem in a one-observer, two-decision
center setup. The type-II error exponents region is derived for testing against independence
when communication from the observer to the decision centers takes place over a common
and two individual noise-free bit pipes. The type-II error exponents region is also derived for
testing against conditional independence when there is only a single noise-free bit pipe and the
additional observation at the first decision center is less noisy than the observation at the other
decision center. An achievable type-II error exponents region is finally derived for the problem
of testing against conditional independence when communication takes place over a discrete
memoryless broadcast channel.
The coding scheme achieving the described type-II error exponents in the last two scenarios
applies the following approach:
•

all terminals split their observations into many subblocks;

•

the transmitter encodes using Heegard-Berger compression with binning or using hybrid
joint source-channel coding;

•

the receiver applies a Neyman-Pearson test over the multiple subblocks of channel and
source observations.

In above approach, the “multi-letter” decision over subblocks avoids introducing a competing
error exponent due to the binning or the channel decoding procedure. Closely related schemes
were also proposed in [4] and [10] for noise-free or noisy multi-access channels. The analysis
introduced here is easily adapted to any desired joint source-channel coding scheme that is based
on random coding arguments.

VI. ACKNOWLEDGEMENT

M. Wigger wishes to thank O. Shayevitz for helpful discussions.
March 19, 2018

DRAFT

22

A PPENDIX A
P ROOF OF T HEOREM 2
We analyze the probability of error of the scheme in Section III-B, but assuming that the
code construction is random and independent across blocks. We treat the realization of this
construction as an additional observation at all terminals. Notice that the codebook observation is
independent of the source observations X n , Y1n , Y2n , Z1n . The type-I and type-II error probabilities
of this random experiment represent expected values of the corresponding error probabilities
achieved with fixed choices of codebooks. We denote these expected values by ECB0 ,CB1 [αi,n ] and
ECB0 ,CB1 [βi,n ], for i ∈ {1, 2}.
The steps in the following analysis are inspired by the analysis in [4]. We first analyze the
(1)

type-I error probabilities. To this end, define ENP,i to be the event that the Neyman-Pearson test
at Receiver i decides on the hypothesis H = 1. We then have
h
i
(1)
ECB0 ,CB1 [αi,n ] = Pr ENP,i or M = 0 H = 0
h
i


(1)
≤ Pr M = 0|H = 0 + Pr ENP,i H = 0
(a)

≤ /8 + /8 = /4,

(55)

where (a) holds by the covering lemma and by the rate constraints (19) and (20) which imply


that Pr M = 0|H = 0 ≤ /8, and because the Neyman-Pearson test has been designed so that
 (1)

Pr ENP,i |H = 0 ≤ /8.
We now analyze the type-II error probabilities. Recall that each Receiver i only declares
Ĥi = 0 if the applied Neyman-Pearson test produces 0. Notice that the sequence of tuples

B
k
k
k
k
k
M0,b , M1,b , S1,b , U0,b
(M0,b ), U1,b
(S1,b |M0,b ), Xbk , Y1,b
, Y2,b
, Z1,b
, C0,b , {C1,b (·)} b=1
(56)
is i.i.d. according to a pmf PM0 M1 S1 U0k U1k X k Y1k Y2k Z1k C0 C1 .2 The Chernoff-Stein Lemma [21] can
thus be applied to bound the probabilities of type-II error.
Consider first Receiver 1. By the Chernoff-Stein Lemma, for any µ0 > 0 and sufficiently large

2

Here S1,b denotes the index chosen during the encoding of block b. If no such index is chosen, we define S1,b to be uniform
0

over {1, . . . , 2n(R1 +R1 ) }.

DRAFT

March 19, 2018

23

k:

1
1
− log ECB0 ,CB1 [β1,n ] ≥ D PM0 M1 Y1k Z1k C0 C1 |H=0 PM0 M1 Y1k Z1k C0 C1 |H=1 − µ0
n
k

(a) 1
= I M0 , M1 ; Y1k Z1k , C0 , C1 − µ0
k

1
1
= H Y1k Z1k , C0 , C1 ) − H Y1k M0 , M1 , Z1k , C0 , C1 − µ0
k
k
1
(b)
= H(Y1 |Z1 ) − H(Y1k |M0 , M1 , Z1k , C0 , C1 ) − µ0
k
1
(c)
= H(Y1 |Z1 ) − H(Y1k |M0 , S1 , Z1k , C0 , C1 ) − µ0
k
1
− I(Y1k ; S1 |M0 , M1 , Z1k , C0 , C1 ).
k

(57)

Here, (a) holds by the assumptions on the tuples X n , Y1n , Y2n , Z1n under the two hypotheses and
because these tuples are independent of the codebooks C0 , {C1 }. Step (b) holds by the same
independence and because (Y1n , Z1n ) are i.i.d. Step (c) holds by adding and subtracting the term
1
H(Y1k |S1 , M0 , M1 , Z1k , C0 , C1 )
k

and by noting that it is equal to k1 H(Y1k |S1 , M0 , Z1k , C0 , C1 ).

We show that the last term in (57) becomes arbitrarily small for k → ∞. In fact, by the
covering lemma, the Markov lemma, and the packing lemma [15], if the rate constraints in
(19)–(21) hold, there exists a function ζ k such that for any µ1 > 0 and all sufficiently large k
∆

such that pe = Pr[ζ k (M0 , M1 , Z1k , C0 , C1 ) 6= S1 ] ≤ µ1 . Therefore,
I(Y1k ; S1 |M0 , M1 , Z1k , C0 , C1 ) ≤ H(S1 |M0 , M1 , Z1k , C0 , C1 )
≤ H(S1 |ζ k (M0 , M1 , Z1k , C0 , C1 ))
(a)

≤ hb (pe ) + pe · k(R1 + R10 ) ≤ 1 + µ1 · k(R1 + R10 ),

(58)

where (a) holds by Fano’s Inequality. Inserting (58) into (57) yields:
1
1
1
− log ECB0 ,CB1 [β1,n ] ≥ H(Y1 |Z1 ) − H(Y1k |Z1k , M0 , S1 , C0 , C1 ) − − µ1 (R1 + R10 ) − µ0
n
k
k
1
1
≥ H(Y1 |Z1 ) − H(Y1k |Z1k , U0k (M0 ), U1k (S1 |M0 ), C0 , C1 ) − − µ1 (R1 + R10 )
k
k
− µ0
1
1
≥ H(Y1 |Z1 ) − H(Y1k |Z1k , U0k (M0 ), U1k (S1 |M0 )) − − µ1 (R1 + R10 ) − µ0
k
k
(59)
March 19, 2018

DRAFT

24

We continue by defining the event
∆

EV = {(U0k (M0 ), U1k (S1 |M0 ), Y1k , Z1k ) ∈ Tµk (PU0 U1 Y1 Z1 )}.
Let 1V be the indicator function of event EV . By the covering lemma and the Markov lemma,
and the rate-constraints (19) and (20), for any µ2 > 0 and for all sufficiently large k,
Pr[1V = 0] ≤ µ2 .

(60)

For ease of notation, in the following we abbreviate U0k (M0 ) by U0k and U1k (S1 |M0 ) by U1k .
The second term on the RHS of (59) can be upper bounded as follows:
H(Y1k |Z1k , U0k , U1k )
= H(Y1k , 1V |Z1k , U0k , U1k )
= H(Y1k |Z1k , U0k , U1k , 1V ) + H(1V |Z1k U0k , U1k )
(a)

≤ H(Y1k |Z1k , U0k , U1k , 1V ) + 1

(b)

≤ H(Y1k |Z1k , U0k , U1k , 1V = 1) + k log |Y1 | · µ2 + 1

=

X

Pr[Z1k = z1k , U0k = uk0 , U1k = uk1 |1V = 1] · H(Y1k |Z1k = z1k , U0k = uk0 , U1k = uk1 , 1V = 1)

(uk0 ,uk1 ,z1k )∈Tµk

+ k log |Y1 | · µ2 + 1
(c)

≤

X

Pr[Z1k = z1k , U0k = uk0 , U1k = uk1 |1V = 1] · log(|Tµk (Y1k |uk0 , uk1 , z1k )|) + k log |Y1 | · µ2 + 1

(uk0 ,uk1 ,z1k )∈Tµk
(d)

≤

X

Pr[Z1k = z1k , U0k = uk0 , U1k = uk1 |1V = 1] · (kH(Y1 |Z1 , U0 , U1 ) + kδ 0 (µ)) + k log |Y1 | · µ2 + 1

(uk0 ,uk1 ,z1k )∈Tµk

= kH(Y1 |Z1 , U0 , U1 ) + kδ 0 (µ) + k log |Y1 | · µ2 + 1.

(61)

The steps leading to (61) are justified as follows:
•

(a) follows from the fact H(1V |Z1k , M0 , S1 ) ≤ 1 since 1V is a binary random variable,

•

(b) follows from (60), Pr[1V = 1] ≤ 1 and H(Y1k |Z1k , M0 , S1 , 1V = 0) ≤ k log |Y1 |,

•

(c) follows because entropy is maximized by a uniform distribution,

•

(d) follows by bounding the size of the typical set [15] where δ 0 (µ) is a function that goes
to 0 as µ → 0.

DRAFT

March 19, 2018

25

We combine (59) with (61) to obtain that for all µ, µ0 , µ1 , µ2 > 0 and sufficiently large k, B:
2
1
− log ECB0 ,CB1 [β1,n ] ≥ I(U0 , U1 ; Y1 |Z1 ) − log |Y1 | · µ2 − − µ1 · (R1 + R10 ) − µ0 − δ 0 (µ),
n
k
where δ 0 (µ) is a function that tends to 0 as µ → 0. Next, we consider the type-II error probability
at Receiver 2. By the Chernoff-Stein lemma, we have
1
1
− log ECB0 ,CB1 [β2,n ] ≥ D(PM Y2k C0 C1 |H=0 ||PM Y2k C0 C1 |H=1 ) − µ0
n
k
1
= I(M ; Y2k |C0 , C1 ) − µ0
k
1
≥ I(M0 ; Y2k |C0 , C1 ) − µ0
k
1
= I(M0 , U0k ; Y2k |C0 , C1 ) − µ0
k
1
1
= H(Y2k |C0 , C1 ) − H(Y2k |M0 , U0k , C0 , C1 ) − µ0
k
k
1
= H(Y2 ) − H(Y2k |M0 , U0k , C0 , C1 ) − µ0
k
1
≥ H(Y2 ) − H(Y2k |U0k ) − µ0
k
= I(U0 ; Y2 ) − µ0 ,

(62)

where again µ0 can be chosen arbitrarily small as B → ∞. We have thus proved that for
i ∈ {1, 2} and all µ̃ > 0 and sufficiently large k, B, we get
ECB0 ,CB1 [αi,n ] ≤ /4

(63)

ECB0 ,CB1 [β1,n ] ≤ 2−n(I(U0 U1 ;Y1 |Z1 )−µ̃)

(64)

ECB0 ,CB1 [β2,n ] ≤ 2−n(I(U0 ;Y2 )−µ̃) .

(65)

It can be shown that these expectations imply for each µ0 > µ̃ and sufficiently large blocklength
n, there exists a deterministic choice of codebooks so that
αi,n ≤ /4,

(66)
0

β1,n ≤ 2−n(I(U0 U1 ;Y1 |Z1 )−µ ) ,
0

β2,n ≤ 2−n(I(U0 ;Y2 )−µ ) .

(67)
(68)

We first order the sets of codebooks according to α1,n , and then restrict to the subset of codebooks
that have smallest α1,n and total probability at least 1/2. Each of the codebooks in this restricted

March 19, 2018

DRAFT

26

set induces α1,n ≤


.
2

We can repeat this step by ordering the codebooks according to their

values of α2,n and then β1,n , β2,n . This way we construct a nonempty subset of codebooks so
0

0

that for each of them αi,n ≤ , β1,n ≤ 16 · 2−n(I(U0 U1 ;Y1 |Z1 )−µ ) and β2,n ≤ 16 · 2−n(I(U0 ;Y2 )−µ ) .
Introducing µ0 = µ̃ +

4
n

completes the proof.

A PPENDIX B
P ROOF OF T HEOREM 3
(n)

(n)

Fix a sequence of encoding and decoding functions {φ(n) , g1 , g2 } so that the inequalities
in Definition 3 hold for sufficiently large blocklengths n. Fix also such a sufficiently large n.
∆

∆

n
Then, define U0,t = (M, Z1t−1 ) and U1,t = (M, X t−1 , Z1,t+1
, Z1t−1 ). Following similar steps as in

[16], it can be shown that
D(PM,Y1n ,Z1n |H=0 ||PM,Y1n ,Z1n |H=1 ) ≥ −(1 − ) log β1,n .
Therefore, the type-II error probability at Receiver 1 can be upper bounded as
1
1
D(PM,Y1n ,Z1n |H=0 ||PM,Y1n ,Z1n |H=1 )
− log β1,n ≤
n
n(1 − )
1
I(M ; Y1n |Z1n )
n(1 − )
n
X
1
=
I(M ; Y1,t |Y1t−1 , Z1n )
n(1 − ) t=1
(a)

=

(b)

n

X
1
n
≤
I(M, Y1t−1 , Z1t−1 , Z1,t+1
; Y1,t |Z1,t )
n(1 − ) t=1

(c)

n

X
1
n
I(M, X t−1 , Z1t−1 , Z1,t+1
; Y1,t |Z1,t )
≤
n(1 − ) t=1
n

=

X
1
I(U0,t , U1,t ; Y1,t |Z1,t )
n(1 − ) t=1

where (a) follows because under hypothesis H = 1 and given Z1n , the sequence Y1n and message
M are independent; (b) follows from the memoryless property of the sources; (c) follows from
n
the Markov chain (Y1,t , Z1,t ) → (M, X t−1 , Z1t−1 , Z1,t+1
) → Y1t−1 . For the type-II error probability

at Receiver 2, one obtains:
1
1
1
− log β2,n ≤
D(PM Y2n |H=0 ||PM Y2n |H=1 ) =
I(M ; Y2n )
n
n(1 − )
n(1 − )
DRAFT

March 19, 2018

27
n

X
1
n
I(M ; Y2,t |Y2,t+1
)
=
n(1 − ) t=1
n

X

1
n
n
=
I(M, Z1t−1 ; Y2,t |Y2,t+1
) − I(Z1t−1 ; Y2,t |M, Y2,t+1
)
n(1 − ) t=1
(b)

=

(c)

=

n
X


1
n
n
)
; Y2,t ) − I(Z1t−1 ; Y2,t |M, Y2,t+1
I(M, Z1t−1 , Y2,t+1
n(1 − ) t=1
n
X


1
n
n
I(M, Z1t−1 , Y2,t+1
; Y2,t ) − I(Y2,t+1
; Z1,t |M, Z1t−1 )
n(1 − ) t=1

n
X


1
n
n
; Y2,t |M, Z1t−1 )
I(M, Z1t−1 , Y2,t+1
; Y2,t ) − I(Y2,t+1
≤
n(1 − ) t=1

(d)

n

n

X
X
1
1
=
I(M, Z1t−1 ; Y2,t ) =
I(U0,t ; Y2,t )
n(1 − ) t=1
n(1 − ) t=1
where (b) follows from the memoryless property of the sources; (c) follows from Csiszar and
Körner’s sum identity [15]; and (d) follows from the less noisy assumption (see Definition 5)
n
and the Markov chain (M, Y2,t+1
, Z1t−1 ) → Xt → (Y1,t , Y2,t , Z1,t ) which holds by the memoryless

property of the sources and because M is a function of X n . For the rate R, one finds:
nR ≥ H(M ) ≥ I(M ; X n , Z1n )
= I(M ; X n |Z1n ) + I(Z1n ; M )
=

n
X

[I(M ; Xt |X t−1 , Z1n ) + I(M ; Z1,t |Z1t−1 )]

t=1
n
X


n
=
I(M, X t−1 , Z1t−1 , Z1,t+1
; Xt |Z1,t ) + I(M, Z1t−1 ; Z1,t )
t=1
n
X


n
=
I(X t−1 , Z1,t+1
; Xt |M, Z1,t , Z1t−1 ) + I(M, Z1t−1 ; Xt |Z1,t ) + I(M, Z1t−1 ; Z1,t )
t=1
n
X

n
=
I(X t−1 , Z1,t+1
; Xt |M, Z1,t , Z1t−1 ) + I(M, Z1t−1 ; Z1,t , Xt )]
t=1

≥

n
X


n
I(X t−1 , Z1,t+1
; Xt |M, Z1,t , Z1t−1 ) + I(M, Z1t−1 ; Xt )



t=1

=

n
X
[I(U1,t ; Xt |Z1,t , U0,t ) + I(U0,t ; Xt )].
t=1

Notice that by the memoryless property of the sources and because M is a function of X n ,
n
the Markov chain (M, Z1,t+1
, Z1t−1 , X t−1 ) → Xt → (Y1,t , Y2,t , Zt ) holds, and thus (U0,t , U1,t ) →

March 19, 2018

DRAFT

28

Xt → (Y1,t , Y2,t , Zt ). The proof is then concluded by combining these observations with standard
time-sharing arguments which require introducing the auxiliary random variables T ∈ {1, ..., n},
∆

∆

∆

∆

∆

∆

U0 = (U0,T , T ), U1 = U1,T , X = XT , Y1 = Y1,T , Y2 = Y2,T , and Z1 = Z1,T .

A PPENDIX C
P ROOF OF T HEOREM 4
We analyze the probability of error of the scheme in Section IV-B. Consider the random
experiment where the code construction is random and i.i.d. over blocks, and revealed to the
terminals as additional observations. The type-I and type-II error probabilities of this random
experiment coincide with the expected type-I and type-II error probabilities ECB0 ,CB1 [αi,n ] and
ECB0 ,CB1 [βi,n ] for i = 1, 2. Consider first the type-I error probabilities of the mentioned random
experiment. By construction of the Neyman-Pearson tests employed at the two receivers, we get
ECB0 ,CB1 [αi,n ] ≤ /4. Now, consider the analysis of the type-II error at Receiver 1. Notice that
the sequence of tuples

k
k
k
k
k
k
k
M0,b , M1,b , U0,b
(M0,b ), U1,b
(M1,b |M0,b ), Wbk , V1,b
, V2,b
, Xbk , Y1,b
, Y2,b
, Z1,b
, C0,b , {C1,b (·)}

B
b=1

is i.i.d. according to a pmf PM0 M1 U0k U1k W k Z1k V1k V2k X k Y1k Y2k C0 C1 . Thus, by the Chernoff-Stein Lemma,
for any µ0 > 0 and sufficiently large k:

1
1
− log ECB0 ,CB1 [β1,n ] ≥ D PV1k Y1k Z1k C0 C1 |H=0 PV1k Y1k Z1k C0 C1 |H=1 − µ0
n
k

1
= I V1k ; Y1k Z1k , C0 , C1 − µ0
k

1
1
= H Y1k Z1k , C0 , C1 ) − H Y1k V1k , Z1k , C0 , C1 − µ0
k
k
1
= H(Y1 |Z1 ) − H(Y1k |V1k , Z1k , C0 , C1 ) − µ0
k
1
= H(Y1 |Z1 ) − H(Y1k |V1k , M0 , M1 , Z1k , C0 , C1 ) − µ0
k
1
− I(Y1k ; M0 , M1 |V1k , Z1k , C0 , C1 )
k

(69)

We show that the last term in (69) becomes arbitrarily small for k → ∞. In fact, from the rate
constraints (45)–(48) and by the covering, the Markov, and the packing lemmas [15], there
∆

exists a function ζ k such that for any µ1 > 0 and all sufficiently large k, we have pe =
DRAFT

March 19, 2018

29

Pr[ζ k (V1k , Z1k , C0 , C1 ) 6= (M0 , M1 )] ≤ µ1 . Therefore, with similar steps in (58), we get
I(Y1k ; M0 , M1 |V1k , Z1k , C0 , C1 ) ≤ 1 + µ1 · k(R0 + R1 ),

(70)

Inserting (70) into (69) yields:
1
1
1
− log ECB0 ,CB1 [β1,n ] ≥ H(Y1 |Z1 ) − H(Y1k |Z1k , U0k (M0 ), U1k (M1 |M0 ), C0 , C1 ) − − µ1 (R0 + R1 )
n
k
k
− µ0
1
1
≥ H(Y1 |Z1 ) − H(Y1k |Z1k , U0k (M0 ), U1k (M1 |M0 )) − − µ1 (R0 + R1 ) − µ0 .
k
k
(71)
Following similar steps as the ones leading to (59), and considering the rate-constraints (47) and
(48) yields the following inequality for all µ, µ0 , µ1 , µ2 > 0 and all sufficiently large values of
B and k:
2
1
− log ECB0 ,CB1 [β1,n ] ≥ I(U0 , U1 ; Y1 |Z1 ) − log |Y1 | · µ2 − − µ1 · (R0 + R1 ) − µ0 − δ 0 (µ), (72)
n
k
where δ 0 (µ) is a function that tends to 0 as µ → 0.
The analysis of type-II error probability at Receiver 2 follows from the rate constraint (48)
and similar steps to (70). We have thus proved that for i ∈ {1, 2} and all µ̃ > 0 and sufficiently
large k, B, we have
ECB0 ,CB1 [αi,n ] ≤ /4

(73)

ECB0 ,CB1 [β1,n ] ≤ 2−n(I(U0 U1 ;Y1 |Z1 )−µ̃)

(74)

ECB0 ,CB1 [β2,n ] ≤ 2−n(I(U0 ;Y2 )−µ̃) .

(75)

Following similar elimination steps as at the end of Appendix A, one can prove that there must
exist at least one sequence of codebooks with the desired error probabilities. This concludes the
proof of the theorem.

R EFERENCES
[1] A. Ahlswede and I. Csiszar, “Hypothesis testing with communication constraints,” IEEE Trans. on Info. Theory, vol. 32,
no. 4, pp. 533–542, Jul. 1986.
[2] T. S. Han, “Hypothesis testing with multiterminal data compression,” IEEE Trans. on Info. Theory, vol. 33, no. 6, pp.
759–772, Nov. 1987.
March 19, 2018

DRAFT

30

[3] H. Shimokawa, T. Han and S. I. Amari, “Error bound for hypothesis testing with data compression,” in Proc. IEEE Int.
Symp. on Info. Theory, Jul. 1994, p. 114.
[4] M. S. Rahman and A. B. Wagner, “On the Optimality of binning for distributed hypothesis testing,” IEEE Trans. on Info.
Theory, vol. 58, no. 10, pp. 6282–6303, Oct. 2012.
[5] W. Zhao and L. Lai, “Distributed testing against independence with multiple terminals,” in Proc. 52nd Allerton Conf.
Comm, Cont. and Comp., IL, USA, pp. 1246–1251, Oct. 2014.
[6] W. Zhao and L. Lai, “Distributed testing against independence with conferencing encoders,” in Prof. IEEE Inf. Theory
Workshop (ITW), Korea, Oct. 2015.
[7] Y. Xiang and Y. H. Kim, “Interactive hypothesis testing against independence,” in Proc. IEEE Int. Symp. on Info. Theory,
Istanbul, Turkey, pp. 2840–2844, Jun. 2013.
[8] G. Katz, P. Piantanida and M. Debbah, “Collaborative distributed hypothesis testing,” arXiv, 1604.01292, Apr. 2016.
[9] J. Liao, L. Sankar, F. P. Calmon, V. Y. F. Tan, “Hypothesis testing under maximal leakage privacy constraints”, To appear
in Proc. IEEE Int. Symp. on Info. Theory, Aachen, Germany, Jun. 2017.
[10] S.

Sreekuma

and

D.

Gunduz,

“Distributed

hypothesis

testing

over

noisy

channels,”

available

at:

https://arxiv.org/abs/1704.01535.
[11] R. Gray and A. Wyner, “Source coding for a simple network,” Bell System Tech. J., vol. 48, pp. 1681-1721, Nov. 1974.
[12] A. Kaspi and T. Berger, “Rate-distortion for correlated sources with partially separated encoders ,” IEEE Trans. on Info.
Theory, vol. 28, no. 6, pp. 828–840, Nov. 1982.
[13] C. Heegard and T. Berger, “Rate distortion when side information may be absent,” IEEE Trans. on Info. Theory, vol. 31,
no. 6, pp. 727–734, Nov. 1985.
[14] P. Minero, S. H. Lim, and Y. H. Kim, “A unified approach to hybrid coding,” IEEE Transactions on Information Theory,
vol. 61, no. 4, pp. 1509–1523, Apr. 2015.
[15] A. El Gamal and Y. H. Kim, Network information theory, Cambridge Univ. Press, 2011.
[16] M. Wigger and R. Timo, “Testing against independence with multiple decision centers,” in Proc. of SPCOM 2016,
Bangalore, India, June 12-15, 2016. (Invited Paper)
[17] I. Csiszar, “Linear codes for sources and source networks: error exponents, universal coding,” IEEE Trans. on Info. Theory,
vol. 28, no. 4, pp. 585–592, Jul. 1982.
[18] B. G. Kelly and A. B. Wagner, “Improved source coding exponents via Witsenhausen’s rate,” IEEE Trans. on Info. Theory,
vol. 57, no. 9, pp. 5615–5633, Sep. 2011.
[19] I. Csiszar and J. Korner, “Graph decomposition: a new key to coding theorems,” IEEE Trans. on Info. Theory, vol. 27,
no. 1, pp. 5–12, Jan. 1981.
[20] E. Tuncel, “Slepian Wolf coding over broadcast channels,” IEEE Trans. on Info. Theory, vol. 52, no. 4, pp. 1469–1482,
Apr. 2006.
[21] T. M. Cover and J. A. Thomas, Elements of Information Theory, John Wiley, 1991.

DRAFT

March 19, 2018

