# Strong Converses using Typical Changes of Measures and Asymptotic Markov
Chains

Mustapha Hamad, Michèle Wigger, Mireille Sarkiss Part of this material was
presented at IEEE Inf. Theory Workshop (ITW) 2022 [1]. M. Hamad used to be
with LTCI, Télécom Paris, Institut Polytechnique de Paris, 91120 Palaiseau,
France. He is now with Huawei Mathematical and Algorithmic Sciences Lab, Paris
Research Center, 92100 Boulogne-Billancourt, France,
<EMAIL_ADDRESS>M. Wigger is with LTCI, Télécom Paris, Institut
Polytechnique de Paris, 91120 Palaiseau, France, michele.wigger@telecom-
paris.fr.M. Sarkiss is with SAMOVAR, Télécom SudParis, Institut Polytechnique
de Paris, 91120 Palaiseau, France<EMAIL_ADDRESS>
###### Abstract

The paper presents exponentially-strong converses for source-coding, channel
coding, and hypothesis testing problems. More specifically, it presents
alternative proofs for the well-known exponentially-strong converse bounds for
almost lossless source-coding with side-information and for channel coding
over a discrete memoryless channel (DMC). These alternative proofs are solely
based on a change of measure argument on the sets of conditionally or jointly
typical sequences that result in a correct decision, and on the analysis of
these measures in the asymptotic regime of infinite blocklengths. The paper
also presents a new exponentially-strong converse for the K-hop hypothesis
testing against independence problem with certain Markov chains and a strong
converse for the two-terminal L-round interactive compression problem with
multiple distortion constraints that depend on both sources and both
reconstructions. This latter problem includes as special cases the Wyner-Ziv
problem, the interactive function computation problem, and the compression
with lossy common reconstruction problem. These new strong converse proofs are
derived using similar change of measure arguments as described above and by
additionally proving that certain Markov chains involving auxiliary random
variables hold in the asymptotic regime of infinite blocklengths. As shown in
related publications, the same method also yields converse bounds under
expected resource constraints.

###### Index Terms:

Strong converse, change of measure, asymptotic Markov chains, source coding,
channel coding, hypothesis testing.

##  I Introduction

_Strong converse_ results have a rich history in information theory. They
refer to proofs showing that the fundamental performance limit (such as
minimum compression rate or maximum rate of communiction) of a specific system
does not depend on its allowed error (or excess) probability, as long as this
probability is not $1$. For example, Wolfowitz’ strong converse [2]
established that the largest rate of communication over a discrete-memoryless
channel (DMC) ensuring a probability of error smaller than $\delta_{n}$ (see
Figure 1) always equals capacity, as long as $\delta_{n}$ does not tend to 1
for increasing blocklengths $n$. Differently stated, for all rates of
communication that exceed capacity, the probability of error of any system
must tend to 1 as the blocklength $n$ tends to infinity. A stronger result,
known as the _exponentially-strong converse_ states that for all rates above
capacity the probability of decoding error tends to 1 exponentially fast in
the blocklength. This result was first established by Csiszár and Körner [3]
who presented lower bounds on the error exponents at rates above capacity.
Since then, various alternative proofs for the strong or exponentially-strong
converse for channel coding over a DMC have been proposed, for example based
on the blowing-up lemma [4, 5], by bounding the decoding error probabilities
at finite blocklengths [6, 7], or by putting forward geometric and typicality
arguments [8]. Various extensions to multi-user communication networks were
also derived, see e.g., [5, 9, 10]. In this paper, we present yet-another
proof, based on a change of measure argument that restricts to output
sequences that are conditionally-typical for one of the possible codewords and
lie in the decoding set of this codeword. Related is the converse proof for
the wiretap channel by Tyagi and Watanabe [11], which is also based on a
similar change of measure argument, but does not restrict to conditionally-
typical output sequences. This restriction is however important in our
converse proof to relate the rate of the code to the capacity of the DMC.

Figure 1: Channel coding over a DMC subject to a constraint on the probability
of error.

For (almost) lossless source coding, the strong converse states that any
discrete-memoryless source (DMS) cannot be compressed with a rate below the
entropy of the source and with reconstruction error probability that stays
below $1$ asymptotically for infinite blocklengths. This result essentially
follows by the asymptotic equipartition property [12, 13]. The exponentially-
strong converse for lossless compression [14] states that for all compression
rates below entropy, the probability of reconstruction error tends to 1
exponentially fast. Strong converse results also extend to lossy compression,
where the limit of compression of DMSs is not entropy but the well-known rate-
distortion function. The strong converse for lossy compression of DMSs was
established by Körner [15], see also the related work by Kieffer [16].

Our focus is on compression scenarios where the decoder has side-information
that is correlated with the source as depicted in Figure 2. For memoryless
sources, the fundamental limits of compression with side-information were
established by Slepian and Wolf [17] for the lossless case and by Wyner and
Ziv [18] for the lossy case. Exponentially-strong converses were established
by Oohama and Han [19] for the lossless case and by Oohama [20] for the lossy
case. Various exponentially-strong converse results were also derived for
compression problems in more complicated networks with and without side-
information, see e.g., [21, 22, 23, 24, 11].

In this paper, we reprove the exponentially-strong converse for lossless
source coding with side-information.

Figure 2: Almost lossless source coding of a DMS subject to a constraint on
the probability of error.

As a new result, we also prove the strong converse for an interactive lossy
compression problem (see Figure 3) where the distortion measures can depend on
the source sequences observed at the two terminals, as well as on the two
terminals’ produced reconstruction sequences. This problem includes as special
cases Kaspi’s two-terminal interactive lossy source-coding problem [25], Ma
and Ishwar’s two-terminal interactive function-computation problem [26], and
Steinberg’s lossy source coding problem with common reconstructions [27], as
well as its extension by Malär et al. [28]. Our proof of the exponentially-
strong converse for lossless source coding with side-information is based on a
change of measure argument that restricts to source sequences that are jointly
typical and result in correct decoding, and on the asymptotic analysis of this
new measure. Our strong converse proof for interactive $L$-round lossy source
coding with generalized distortion measures again relies on a change of
measure argument on the set of typical sequences that result in the desired
distortion and on analysing this new measure asymptotically in the limit of
infinite blocklengths. As part of this analysis, we prove in particular that
certain Markov chains hold in this asymptotic regime of infinite blocklengths.

The change of measure argument for proving exponentially-strong converses for
source coding problems dates back to Gu and Effros [22, 23] and for function
computation problems and channel coding to Tyagi and Watanabe [11]. Our proofs
are similar to [11], however in our changed measures we restrict to typical
sequences, which allows us to circumvent resorting to variational
characterizations of the multi-letter and single-letter problems.

Figure 3: Interactive source coding with multiple distortions depending on the
sources and the reconstructions.

In this paper, we also prove a new exponentially-strong converse result for
the $K$-hop hypothesis testing problem in [29], see Figure 4. In this problem,
all $K-1$ relays as well as the final receiver guess the hypothesis by testing
against independence. The figure of merit is the type-II error exponents that
can be achieved at these $K$ terminals subject to rate constraints on the $K$
links and the constraint that the type-I error probabilities at these
terminals have to stay below predefined thresholds $\delta_{k,n}$.
Specifically, we consider a scenario where $K+1$ terminals observe memoryless
source sequences whose underlying joint distribution depends on a binary
hypothesis $\mathcal{H}\in\\{0,1\\}$. The distribution is
$P_{Y_{0}}\prod_{k=1}^{K}P_{Y_{k}|Y_{k-1}}$ under $\mathcal{H}=0$ and it is
$P_{Y_{0}}\prod_{k=1}^{K}P_{Y_{k}}$ under $\mathcal{H}=1$. Upon observing its
source sequence $Y_{k}^{n}$, each terminal $k=0,\ldots,K-1$ can send a
$nR_{k+1}$-bits message $M_{k+1}$ to the next-following terminal. Terminals
$1,\ldots,K$ have to produce a guess of the hypothesis
$\hat{\mathcal{H}}_{k}\in\\{0,1\\}$ based on their local observations
$Y_{k}^{n}$ and their received message $M_{k}$. The main goal is to maximize
their type-II error probability (the probability of error under
$\mathcal{H}=1$) under the constraint that for each blocklength $n$ the type-I
error probability (the probability of error under the null hypothesis
$\mathcal{H}=0$) stays below a given threshold $\delta_{k,n}$.

For $K=1$, this problem was solved by Ahlswede and Csiszár [30] for type-I
error probabilities $\delta_{1,n}$ that are asymptotically bounded away from
1. In particular, it was shown that the maximum achievable type-II error
exponent does not depend on the values $\delta_{1,n}$ as long as they do not
tend to 1. For arbitrary $K\geq 2$, the problem was studied under the
assumption that all the type-I error probabilities $\delta_{k,n}$ tend to 0 as
$n\to\infty$ [29]. In [31], it was shown that for $K=2$ the result in [29]
applies unchanged for sequences of type-I error probabilities $\delta_{1,n}$
and $\delta_{2,n}$ for which each individual sequence as well as the sum of
the two sequences is asymptotically bounded away from 1. In this work, we
prove the exponentially-strong converse to this result, i.e., we show that for
arbitrary $K\geq 1$ and arbitrary type-I error probabilities $\delta_{k,n}$
not vanishing exponentially fast in the blocklength, the result in [29]
continues to hold. Notice that the proof of the mentioned special cases with
$K=2$ in [31] used the change of measure argument and variational
characterizations proposed by Tyagi and Watanabe [11] and hypercontractivity
arguments as in [32]. The proof of the strong converse for $K=1$ in [30] was
based on the blowing-up lemma [4], same as the proof of the strong converse
for $K=1$ when communication is over a DMC and without any rate constraint
[33]. The latter work also used the Tyagi-Watanabe change of measure argument
combined with variational characterizations. Unlike these works, our general
proof does not require any blowing-up lemma or hypercontractivity arguments,
nor variational characterizations.

Figure 4: $K$-hop hypothesis testing problem.

We summarize the main contributions of our paper:

  * •

We present alternative exponentially-strong converse proofs for the lossless
compression problem with side-information for DMSs and the channel coding
problem over a DMCs. The proofs are rather simple and depend only on a change
of measure argument and the asymptotic analysis of these new measures.

  * •

We derive new strong converse results for the two-terminal $L$-round
interactive lossy source coding problem for DMSs and with multiple distortion
measures that depend on both sources and both reconstructions. This setup
includes as special cases the Wyner-Ziv problem, the interactive function
computation problem, and the lossy source coding problem with (lossy) common
reconstructions. Previous strong converse proofs for the Wyner-Ziv problem and
the interactive function computation problem relied on the method of
variational characterizations and on a change of measure argument. Our proof
also relies on a similar change of measure, which is however restricted to the
typical set. This, combined with the asymptotic proofs of specific Markov
chains allows us to directly prove the desired results without resorting to
variational characterizations.

  * •

We derive new exponentially-strong converse results for a $K$-hop hypothesis
testing problem. Previously, a general weak converse and strong converses in
special cases had been derived for this problem. The previous strong converse
for $K=2$ was based on a change of measure argument combined with variational
characterizations, and on hypercontractivity arguments. The general
exponentially-strong converse proof in this paper relies on a change of
measure argument restricted to the typical set and on an asymptotic analysis
of this new measure including the proof of asymptotic Markov chains.

Outline of the Paper: We end this section with remarks on notation. The
following Section II presents and proofs two key lemmas used in the rest of
the paper. Sections III and IV present our new strong converse proof methods
for the almost lossless source coding with side-information problem and for
communication over a DMC. These strong converse proofs are solely based on
change of measure arguments and on the analysis of these measures in the
asymptotic regime of infinite blocklengths. The converse proofs in the next
two Sections V and VI are also based on similar change of measure arguments
and asymptotic analysis of these measures, but additionally also require
proving that certain Markov chains involving auxiliary random variables hold
in the asymptotic regime of infinite blocklengths. Specifically, Section V
considers the $L$-round interactive compression problem with distortion
functions that can depend on the sources and reconstructions at both
terminals. Section VI considers the $K$-hop hypothesis testing for testing
against independence where the observations at the various terminals obey some
Markov conditions.

Notation: We mostly follow standard notation where upper-case letters are used
for random quantities and lower-case letters for deterministic realizations.
Sets are denoted using calligraphic fonts. All random variables are assumed
finite and discrete. We abbreviate the $n$-tuples $(X_{1},\ldots,X_{n})$ and
$(x_{1},\ldots,x_{n})$ as $X^{n}$ and $x^{n}$ and the $n-t$ tuples
$(X_{t+1},\ldots,X_{n})$ and $(x_{t+1},\ldots,x_{n})$ as $X_{t+1}^{n}$ and
$x_{t+1}^{n}$. We further abbreviate _independent and identically distributed_
as _i.i.d._ and _probability mass function_ as _pmf_.

Entropy, conditional entropy, and mutual information functionals are written
as $H(\cdot)$, $H(\cdot|\cdot)$, and $I(\cdot;\cdot)$, where the arguments of
these functionals are random variables and whenever their probability mass
function (pmf) is not clear from the context, we add it as a subscript to
these functionals. The Kullback-Leibler divergence between two pmfs is denoted
by $D(\cdot\|\cdot)$. We shall use $\mathcal{T}_{\mu}^{(n)}(P_{XY})$ to
indicate the jointly strongly-typical set with respect to the pmf $P_{XY}$ on
the product alphabet $\mathcal{X}\times\mathcal{Y}$ and parameter $\mu$ as
defined in [3, Definition 2.8]. Specifically, denoting by
$n_{x^{n},y^{n}}(a,b)$ the number of occurrences of the pair $(a,b)$ in
sequences $(x^{n},y^{n})$:

$n_{x^{n},y^{n}}(a,b)=\left|\\{t\colon(x_{t},y_{t})=(a,b)\\}\right|,$ (1)

a pair $(x^{n},y^{n})$ lies in $\mathcal{T}_{\mu}^{(n)}(P_{XY})$ if

$\left|\frac{n_{x^{n},y^{n}}(a,b)}{n}-P_{XY}(a,b)\right|\leq\mu,\qquad\forall(a,b)\in\mathcal{X}\times\mathcal{{Y}},$
(2)

and $n_{x^{n},y^{n}}(a,b)=0$ whenever $P_{XY}(a,b)=0$. The conditionally
strongly-typical set with respect to a conditional pmf $P_{Y|X}$ from
$\mathcal{X}$ to $\mathcal{Y}$, parameter $\mu>0$, and sequence
$x^{n}\in\mathcal{X}^{n}$ is denoted $\mathcal{T}_{\mu}^{(n)}(P_{Y|X},x^{n})$
[3, Definition 2.9]. It contains all sequences $y^{n}\in\mathcal{Y}^{n}$
satisfying

$\left|\frac{n_{x^{n},y^{n}}(a,b)}{n}-\frac{n_{x^{n}}(a)}{n}P_{Y|X}(b|a)\right|\leq\mu,\qquad\forall(a,b)\in\mathcal{X}\times\mathcal{{Y}},$
(3)

and $n_{x^{n},y^{n}}(a,b)=0$ whenever $P_{Y|X}(b|a)=0$. Here $n_{x^{n}}(a)$
denotes the number of occurrences of symbol $a$ in $x^{n}$. In this paper, we
denote the joint type of $(x^{n},y^{n})$ by $\pi_{x^{n}y^{n}}$, i.e.,

$\pi_{x^{n}y^{n}}(a,b)\triangleq\frac{n_{x^{n},y^{n}}(a,b)}{n}.$ (4)

Accordingly, the marginal type of $x^{n}$ is written as $\pi_{x^{n}}$.
Finally, we use Landau notation $o(1)$ to indicate any function that tends to
0 for blocklengths $n\to\infty$.

##  II Auxiliary Lemmas

###### Lemma 1

Let $\\{(X_{i},Y_{i})\\}_{i=1}^{\infty}$ be a sequence of pairs of i.i.d.
random variables according to the pmf $P_{XY}$. Further let $\\{\mu_{n}\\}$ be
a sequence of small positive numbers satisfying111Condition (6) ensures that
the probability of the strongly typical set
$\mathcal{T}_{\mu_{n}}^{(n)}(P_{XY})$ under $P_{XY}^{\otimes n}$ tends to 1 as
$n\to\infty$ [3, Remark to Lemma 2.12].

$\displaystyle\lim_{n\to\infty}\mu_{n}$ $\displaystyle=$ $\displaystyle 0$ (5)
$\displaystyle\lim_{n\to\infty}\left(n\cdot\mu_{n}^{2}\right)^{-1}$
$\displaystyle=$ $\displaystyle 0$ (6)

and for each positive integer $n$ let $\mathcal{D}_{n}$ be a subset of the
strongly-typical set $\mathcal{T}_{\mu_{n}}^{(n)}(P_{XY})$ so that its
probability

$\Delta_{n}:=\Pr[(X^{n},Y^{n})\in\mathcal{D}_{n}]$ (7)

satisfies

$\lim_{n\to\infty}\frac{1}{n}\log\Delta_{n}=0.$ (8)

Let further $(\tilde{X}^{n},\tilde{Y}^{n})$ be random variables of joint pmf

$P_{\tilde{X}^{n}\tilde{Y}^{n}}(x^{n},y^{n})=\frac{P_{{X}{Y}}^{\otimes
n}(x^{n},y^{n})}{\Delta_{n}}\cdot\mathds{1}\\{(x^{n},y^{n})\in\mathcal{D}_{n}\\}$
(9)

and $T$ be uniform over $\\{1,\ldots,n\\}$ independent of all other random
variables.

For the distribution in (9), the following limits hold as $n\to\infty$:

$\displaystyle P_{\tilde{X}_{T}\tilde{Y}_{T}}$ $\displaystyle\to$
$\displaystyle P_{XY}$ (10)
$\displaystyle\left|\frac{1}{n}H(\tilde{X}^{n}\tilde{Y}^{n})-H(\tilde{X}_{T}\tilde{Y}_{T})\right|$
$\displaystyle\to$ $\displaystyle 0$ (11)
$\displaystyle\left|\frac{1}{n}H(\tilde{Y}^{n})-H(\tilde{Y}_{T})\right|$
$\displaystyle\to$ $\displaystyle 0$ (12)
$\displaystyle\left|\frac{1}{n}H(\tilde{X}^{n}|\tilde{Y}^{n})-H(\tilde{X}_{T}|\tilde{Y}_{T})\right|$
$\displaystyle\to$ $\displaystyle 0$ (13)
$\displaystyle\left|H(\tilde{X}_{T}\tilde{Y}_{T})-H(XY)\right|$
$\displaystyle\to$ $\displaystyle 0$ (14)
$\displaystyle\left|H(\tilde{Y}_{T})-H(Y)\right|$ $\displaystyle\to$
$\displaystyle 0$ (15)
$\displaystyle\left|H(\tilde{X}_{T}|\tilde{Y}_{T})-H(X|Y)\right|$
$\displaystyle\to$ $\displaystyle 0.$ (16)

###### Proof:

Notice that (14)–(16) follow directly from (10) and continuity of entropy. To
prove (10), notice that

$\displaystyle P_{\tilde{X}_{T}\tilde{Y}_{T}}(x,y)$ $\displaystyle=$
$\displaystyle\frac{1}{n}\sum_{t=1}^{n}P_{\tilde{X}_{t}\tilde{Y}_{t}}(x,y)$
(17) $\displaystyle=$
$\displaystyle\mathbb{E}\left[\frac{1}{n}\sum_{t=1}^{n}\mathbbm{1}\\{\tilde{X}_{t}=x,\tilde{Y}_{t}=y\\}\right]$
(18) $\displaystyle=$
$\displaystyle\mathbb{E}[\pi_{\tilde{X}^{n}\tilde{Y}^{n}}(x,y)],$ (19)

where the expectations are with respect to the tuples $\tilde{X}^{n}$ and
$\tilde{Y}^{n}$. Since by the definition of the typical set,

$|\pi_{\tilde{X}^{n}\tilde{Y}^{n}}(x,y)-P_{XY}(x,y)|\leq\mu_{n},$ (20)

we conclude that as $n\to\infty$ the probability
$P_{\tilde{X}_{T}\tilde{Y}_{T}}(x,y)$ tends to $P_{XY}(x,y)$.

To prove (11), notice first that

$\displaystyle\frac{1}{n}H(\tilde{X}^{n}\tilde{Y}^{n})+\frac{1}{n}D(P_{\tilde{X}^{n}\tilde{Y}^{n}}\|P_{XY}^{\otimes
n})$ (21) $\displaystyle=$
$\displaystyle-\frac{1}{n}\sum_{(x^{n},y^{n})\in\mathcal{D}_{n}}P_{\tilde{X}^{n}\tilde{Y}^{n}}(x^{n},y^{n})\log
P_{XY}^{\otimes n}(x^{n},y^{n})$ $\displaystyle=$
$\displaystyle-\frac{1}{n}\sum_{t=1}^{n}\sum_{(x^{n},y^{n})\in\mathcal{D}_{n}}P_{\tilde{X}^{n}\tilde{Y}^{n}}(x^{n},y^{n})\log
P_{XY}(x_{t},y_{t})$ (22) $\displaystyle=$
$\displaystyle-\frac{1}{n}\sum_{t=1}^{n}\sum_{(x_{t},y_{t})\in\mathcal{X}\times\mathcal{Y}}P_{\tilde{X}_{t}\tilde{Y}_{t}}(x_{t},y_{t})\log
P_{XY}(x_{t},y_{t})$ (23) $\displaystyle=$
$\displaystyle-\sum_{(x,y)\in\mathcal{X}\times\mathcal{Y}}\left(\frac{1}{n}\sum_{t=1}^{n}P_{\tilde{X}_{t}\tilde{Y}_{t}}(x,y)\right)\log
P_{XY}(x,y)$ (24) $\displaystyle=$
$\displaystyle-\sum_{(x,y)\in\mathcal{X}\times\mathcal{Y}}P_{\tilde{X}_{T}\tilde{Y}_{T}}(x,y)\log
P_{XY}(x,y)$ (25) $\displaystyle=$ $\displaystyle
H(\tilde{X}_{T}\tilde{Y}_{T})+D(P_{\tilde{X}_{T}\tilde{Y}_{T}}\|P_{XY}),$ (26)

where (23) holds by the law of total probability applied to the random
variables
$\tilde{X}^{t-1},\tilde{X}_{t+1}^{n},\tilde{Y}^{t-1},\tilde{Y}_{t+1}^{n}$.
Combined with the following two limits (27) and (28) this establishes (11).
The first relevant limit is

$\displaystyle D(P_{\tilde{X}_{T}\tilde{Y}_{T}}\|P_{XY})\to 0,$ (27)

which holds by (10) and because $P_{\tilde{X}_{T}\tilde{Y}_{T}}(x,y)=0$
whenever $P_{XY}(x,y)=0$. The second limit is:

$\frac{1}{n}D(P_{\tilde{X}^{n}\tilde{Y}^{n}}\|P_{XY}^{\otimes n})\to 0,$ (28)

and holds because $\frac{1}{n}\log\Delta_{n}\to 0$ and by the following set of
inequalities:

$\displaystyle 0$ $\displaystyle\leq$
$\displaystyle\frac{1}{n}D(P_{\tilde{X}^{n}\tilde{Y}^{n}}\|P_{XY}^{\otimes
n})$ (29) $\displaystyle=$
$\displaystyle\frac{1}{n}\sum_{(x^{n},y^{n})\in\mathcal{D}_{n}}P_{\tilde{X}^{n}\tilde{Y}^{n}}(x^{n},y^{n})\log\frac{P_{\tilde{X}^{n}\tilde{Y}^{n}}(x^{n},y^{n})}{P_{XY}^{\otimes
n}(x^{n},y^{n})}$ $\displaystyle=$
$\displaystyle-\frac{1}{n}\sum_{(x^{n},y^{n})\in\mathcal{D}_{n}}P_{\tilde{X}^{n}\tilde{Y}^{n}}(x^{n},y^{n})\log\Delta_{n}$
(30) $\displaystyle=$ $\displaystyle-\frac{1}{n}\log\Delta_{n}.$ (31)

To prove (12), notice that by the same arguments as we concluded (26), we also
have

$\displaystyle\frac{1}{n}H(\tilde{Y}^{n})+\frac{1}{n}D(P_{\tilde{Y}^{n}}\|P_{Y}^{\otimes
n})=H(\tilde{Y}_{T})+D(P_{\tilde{Y}_{T}}\|P_{Y}).$ (32)

Moreover, (27) and (28) imply

$\displaystyle\frac{1}{n}D(P_{\tilde{Y}^{n}}\|P_{Y}^{\otimes n})$
$\displaystyle\to$ $\displaystyle 0$ (33) $\displaystyle
D(P_{\tilde{Y}_{T}}\|P_{Y})$ $\displaystyle\to$ $\displaystyle 0,$ (34)

which combined with (32) imply (12).

The last limit (13) follows by the chain rule and limits (11) and (12). This
concludes the proof. ∎

The second lemma dates back to Csiszár and Körner [3].

###### Lemma 2

Let $A^{n}$ and $B^{n}$ be of arbitrary joint distribution and $T$ be uniform
over $\\{1,\ldots,n\\}$ independent of $(A^{n},B^{n})$. Then:

$\displaystyle H(A^{n}|B^{n})-H(B^{n}|A^{n})$ (35) $\displaystyle=$
$\displaystyle
n\left(H(A_{T}|B_{T}A^{T-1}B_{T+1}^{n})-H(B_{T}|A_{T}A^{T-1}B_{T+1}^{n})\right).$

The conditional version follows immediately from the definition of conditional
entropy:

$\displaystyle H(A^{n}|B^{n}S)-H(B^{n}|A^{n}S)$ (36) $\displaystyle=$
$\displaystyle
n\left(H(A_{T}|B_{T}A^{T-1}B_{T+1}^{n}S)-H(B_{T}|A_{T}A^{T-1}B_{T+1}^{n}S\right))$

for any random variable $S$ so that $T$ is independent of $(A^{n},B^{n},S)$.

###### Proof:

Kramer’s simple telescoping sum states:

$0=\sum_{i=1}^{n}\left[I(A^{i};B_{i+1}^{n})-I(A^{i-1};B_{i}^{n})\right],$ (37)

which by the chain rule of mutual information implies Csiszár’s sum-identity
[3]:

$0=\sum_{i=1}^{n}\left[I(A_{i};B_{i+1}^{n}|A^{i-1})-I(A^{i-1};B_{i}|B_{i+1}^{n})\right].$
(38)

where we added and subtracted the mutual informations
$\sum_{i=1}^{n}I(A^{i-1};B_{i+1}^{n})$. Similarly, adding and subtracting the
mutual informations $\sum_{i=1}^{n}I(A_{i};B_{i}|A^{i-1},B_{i+1}^{n})$ yields:

$0=\sum_{i=1}^{n}\left[I(A_{i};B_{i}^{n}|A^{i-1})-I(A^{i};B_{i}|B_{i+1}^{n})\right].$
(39)

The desired equality in (35) follows then immediately from this last equation
(39) and from the chain rule:

$\displaystyle H(A^{n}|B^{n})-H(B^{n}|A^{n})$ (40)
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}$ $\displaystyle
H(A^{n})-H(B^{n})$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{n}\left[H(A_{i}|A^{i-1})-H(B_{i}|B_{i+1}^{n})\right]$
(41) $\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}$
$\displaystyle\sum_{i=1}^{n}\left[H(A_{i}|A^{i-1}B_{i}^{n})-H(B_{i}|A^{i}B_{i+1}^{n})\right]$
(42) $\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}$ $\displaystyle
n(H(A_{T}|B_{T}A^{T-1}B_{T+1}^{n})-H(B_{T}|A_{T}A^{T-1}B_{T+1}^{n})),$ (43)

where $(a)$ is obtained by adding and subtracting $I(A^{n};B^{n})$, $(b)$
holds by (39); and $(c)$ by the definition of $T$.

∎

##  III Lossless Source Coding with Side-Information

This section studies the lossless source coding with side-information setup in
Figure 2.

###  III-A Setup and Result

Consider two terminals, an encoder observing the source sequence $X^{n}$ and a
decoder observing the related side-information sequence $Y^{n}$, where we
assume that

$\displaystyle(X^{n},Y^{n})\textnormal{ i.i.d. }\sim\,P_{XY},$ (44)

for a given probability mass function $P_{XY}$ on the product alphabet
$\mathcal{X}\times\mathcal{Y}$. The encoder uses a function $\phi^{(n)}$ to
compress the sequence $X^{n}$ into a message ${M}\in\\{1,\ldots,2^{nR}\\}$ of
given rate $R>0$:

$\displaystyle{M}$ $\displaystyle=$ $\displaystyle\phi^{(n)}(X^{n}).$ (45)

Based on this message and its own observation $Y^{n}$, the decoder is supposed
to reconstruct the source sequence $X^{n}$ with small probability of error.
Thus, the decoder applies a decoding function $g^{(n)}$ to $({M},Y^{n})$ to
produce the reconstruction sequence $\hat{X}^{n}\in\mathcal{X}^{n}$:

$\hat{X}^{n}=g^{(n)}({M},Y^{n}).$ (46)

###### Definition 1

Given a sequence of error probabilities $\\{\delta_{n}\\}$, the rate $R>0$ is
said $\\{\delta_{n}\\}$-achievable if there exist sequences (in $n$) of
encoding and reconstruction functions $\phi^{(n)}$ and $g^{(n)}$ such that for
each blocklength $n$:

$\Pr\left[X^{n}\neq g^{(n)}(\phi^{(n)}({X}^{n}))\right]\leq\delta_{n}.$ (47)

A standard result in information theory is [19]:

###### Theorem 1

For any sequence $\\{\delta_{n}\\}$ satisfying

$\lim_{n\to\infty}\frac{1}{n}\log(1-\delta_{n})=0,$ (48)

any rate $R<H(X|Y)$ is not $\\{\delta_{n}\\}$-achievable.

Notice that the theorem in particular implies an exponentially-strong
converse, i.e., that for all rates $R<H(X|Y)$ the probability of error
approches $1$ exponentially fast in $n$. The result is well known, but we
provide an alternative proof in the following subsection.

###  III-B Alternative Strong Converse Proof

Fix a sequence of encoding and decoding functions
$\\{\phi^{(n)},g^{(n)}\\}_{n=1}^{\infty}$ satisfying (47). Choose a sequence
of small positive numbers $\\{\mu_{n}\\}$ satisfying

$\displaystyle\lim_{n\to\infty}\mu_{n}$ $\displaystyle=$ $\displaystyle 0$
(49) $\displaystyle\lim_{n\to\infty}\left(n\cdot\mu_{n}^{2}\right)^{-1}$
$\displaystyle=$ $\displaystyle 0,$ (50)

and select for each $n$ a subset

$\mathcal{D}_{n}:=\left\\{(x^{n},y^{n})\in\mathcal{T}_{\mu_{n}}^{(n)}(P_{XY})\colon
g^{(n)}\left(\phi^{(n)}(x^{n}),y^{n}\right)=x^{n}\right\\},$ (51)

i.e., the set of all typical $(x^{n},y^{n})$-sequences for which the
reconstructed sequence $\hat{X}^{n}$ coincides with the source sequence
$X^{n}$. Let

$\Delta_{n}:=\Pr[(X^{n},Y^{n})\in\mathcal{D}_{n}],$ (52)

and notice that by (47) and [3, Remark to Lemma 2.12]:

$\Delta_{n}\geq
1-\delta_{n}-\frac{|\mathcal{X}||\mathcal{Y}|}{4\mu_{n}^{2}n},$ (53)

and thus by (48) and (50):

$\lim_{n\to\infty}\frac{1}{n}\log\Delta_{n}=0.$ (54)

Let further $(\tilde{X}^{n},\tilde{Y}^{n})$ be random variables of joint pmf

$P_{\tilde{X}^{n}\tilde{Y}^{n}}(x^{n},y^{n})=\frac{P_{{X}^{n}{Y}^{n}}(x^{n},y^{n})}{\Delta_{n}}\cdot\mathds{1}\\{(x^{n},y^{n})\in\mathcal{D}_{n}\\}.$
(55)

Let also $\tilde{{M}}=\phi^{(n)}({\tilde{X}^{n}})$ and $T$ be uniform over
$\\{1,\ldots,n\\}$ independent of $(\tilde{X}^{n},\tilde{Y}^{n},\tilde{{M}})$.

The strong converse is then easily obtained as follows. Similar to the weak
converse we have:

$\displaystyle R$ $\displaystyle\geq$
$\displaystyle\frac{1}{n}H(\tilde{{M}})\geq\frac{1}{n}H(\tilde{{M}}|\tilde{Y}^{n})\geq\frac{1}{n}H(\tilde{X}^{n}|\tilde{Y}^{n}),$
(56)

where the last inequality in (56) holds because $\tilde{X}^{n}$ can be
obtained as a function of $\tilde{{M}}$ and $\tilde{Y}^{n}$, see the
definition of the set $\mathcal{D}_{n}$.

Letting $n\to\infty$, we obtain the desired limit by (13) and (16) in Lemma 1.

##  IV Communication over a Memoryless Channel

This section studies communication over a discrete memoryless channel (DMC) as
depicted in Figure 1.

###  IV-A Setup and Results

Consider a transmitter (Tx) that wishes to communicate to a receiver (Rx) over
a DMC parametrized by the finite input and output alphabets $\mathcal{X}$ and
$\mathcal{Y}$ and the transition law $P_{Y|X}$. The goal of the communication
is that the Tx conveys a message $M$ to the Rx, where $M$ is uniformly
distributed over the set $\\{1,\ldots,2^{nR}\\}$ with $R>0$ and $n>0$ denoting
the rate and blocklength of communication, respectively.

For a given blocklength $n$, the Tx thus produces the $n$-length sequence of
channel inputs

$X^{n}=\phi^{(n)}(M)$ (57)

for some choice of the encoding function
$\phi^{(n)}\colon\\{1,\ldots,2^{nR}\\}\to\mathcal{X}^{n}$, and the Rx observes
the sequence of channel outputs $Y^{n}$, where the time-$t$ output $Y_{t}$ is
distributed according to the law $P_{Y|X}(\cdot|x)$ when the time-$t$ input is
$x$, irrespective of the previous and future inputs and outputs.

The receiver attempts to guess message $M$ based on the sequence of channel
outputs $Y^{n}$:

$\hat{M}=g^{(n)}(Y^{n})$ (58)

using a decoding function of the form
$g^{(n)}\colon\mathcal{Y}^{n}\to\\{1,\ldots,2^{nR}\\}$. The goal is to
minimize the maximum decoding error probability

$p^{(n)}(\textnormal{error}):=\max_{m}\Pr[\hat{M}\neq M|M=m].$ (59)

###### Definition 2

The rate $R>0$ is said $\\{\delta_{n}\\}$-achievable over the DMC
$(\mathcal{X},\mathcal{Y},P_{Y|X})$, if there exists a sequence of encoding
and decoding functions $\\{(\phi^{(n)},g^{(n)})\\}$ such that for each
blocklength $n$ the maximum probability of error

$p^{(n)}(\textnormal{error})\leq\delta_{n}.$ (60)

A well-known result in information theory states [3]:

###### Theorem 2

Any rate $R>C$, where $C$ denotes the capacity

$C:=\max_{P_{X}}I(X;Y),$ (61)

is not $\\{\delta_{n}\\}$-achievable for all sequences $\\{\delta_{n}\\}$
satisfying

$\lim_{n\to\infty}\frac{1}{n}\log(1-\delta_{n})=0.$ (62)

Above result implies that for all rates above capacity, the probability of
error converges exponentially fast to 1. This result is well known, here we
present a different converse proof.

###  IV-B Alternative Strong Converse Proof

Fix a sequence of encoding and decoding functions
$\\{(\phi^{(n)},g^{(n)})\\}_{n=1}^{\infty}$ so that (60) holds. Choose a
sequence of small positive numbers $\\{\mu_{n}\\}$ satisfying

$\displaystyle\lim_{n\to\infty}\mu_{n}$ $\displaystyle=$ $\displaystyle 0$
(63) $\displaystyle\lim_{n\to\infty}\left(n\cdot\mu_{n}^{2}\right)^{-1}$
$\displaystyle=$ $\displaystyle 0,$ (64)

and define for each message $M=m$ the set

$\displaystyle\mathcal{D}_{m}$ $\displaystyle:=$
$\displaystyle\left\\{y^{n}\in\mathcal{T}_{\mu_{n}}^{(n)}(P_{Y|X=x^{n}(m)})\colon
g^{(n)}\left(y^{n}\right)=m\right\\}$ (65)

and its probability

$\Delta_{m}:=\Pr[Y^{n}\in\mathcal{D}_{m}|M=m].$ (66)

(For readability we write the sets $\mathcal{D}_{m}$ and its probability
$\Delta_{m}$ without the subscript $n$.) By (60) and [3, Remark to Lemma
2.12]:

$\Delta_{m}\geq
1-\delta_{n}-\frac{|\mathcal{Y}||\mathcal{X}|}{4\mu_{n}^{2}n},$ (67)

and thus by (62) and (64):

$\lim_{n\to\infty}\frac{1}{n}\log\Delta_{m}=0.$ (68)

Let further $(\tilde{M},\tilde{X}^{n},\tilde{Y}^{n})$ be random variables so
that $\tilde{M}$ is uniform over the set $\\{1,\ldots,2^{nR}\\}$ (i.e., it has
the same distribution as $M$),

$\tilde{X}^{n}:=\phi^{(n)}(\tilde{M})$ (69)

and

$\displaystyle P_{\tilde{Y}^{n}|\tilde{M}}(y^{n}|m)$ $\displaystyle=$
$\displaystyle\frac{P_{Y|X}^{\otimes
n}(y^{n}|x^{n}(m))}{\Delta_{m}}\cdot\mathbbm{1}\\{y^{n}\in\mathcal{D}_{m}\\}.$
(70)

Further, let $T$ be independent of $(\tilde{M},\tilde{X}^{n},\tilde{Y}^{n})$
and uniform over $\\{1,\ldots,n\\}$. Notice that since the decoding sets
$\\{\mathcal{D}_{m}\\}$ are disjoint, by the definition of the new measure
$P_{\tilde{Y}^{n}|\tilde{M}}$ it is possible to determine $\tilde{M}$ from
$\tilde{Y}$ with probability $1$.

Following similar steps as in the weak converse, we have:

$\displaystyle R$ $\displaystyle=$ $\displaystyle\frac{1}{n}H(\tilde{M})$ (71)
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}$
$\displaystyle\frac{1}{n}I(\tilde{M};\tilde{Y}^{n})$ (72) $\displaystyle=$
$\displaystyle\frac{1}{n}H(\tilde{Y}^{n})-\frac{1}{n}H(\tilde{Y}^{n}|\tilde{M})$
(73) $\displaystyle\leq$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}H(\tilde{Y}_{i})-\frac{1}{n}H(\tilde{Y}^{n}|\tilde{M})$
(74) $\displaystyle=$ $\displaystyle
H(\tilde{Y}_{T}|T)-\frac{1}{n}H(\tilde{Y}^{n}|\tilde{M})$ (75)
$\displaystyle\leq$ $\displaystyle
H(\tilde{Y}_{T})-\frac{1}{n}H(\tilde{Y}^{n}|\tilde{M}),$ (76)

where $(a)$ holds because $\tilde{M}=g(\tilde{Y}^{n})$ as explained above.

By the following lemma, by considering an appropriate subsequence of
blocklengths, and by the continuity of the entropy function, we deduce that

$R\leq I_{{P}_{X}P_{Y|X}}(X;Y)\leq C,$ (77)

where the subscript indicates that mutual information is with respect to the
joint pmf $P_{X}P_{Y|X}$ with $P_{X}$ denoting the pmf mentioned in the lemma.
This concludes the proof of the strong converse for channel coding.

###### Lemma 3

There exists an increasing subsequence of blocklengths
$\\{n_{i}\\}_{i=1}^{\infty}$ such that for some pmf $P_{X}$:

$\displaystyle\lim_{i\to\infty}P_{\tilde{Y}_{T}}(y)$ $\displaystyle=$
$\displaystyle\sum_{x\in\mathcal{X}}P_{X}(x)P_{Y|X}(y|x)$ (78)
$\displaystyle\lim_{i\to\infty}\frac{1}{n_{i}}H(\tilde{Y}^{n_{i}}|\tilde{M})$
$\displaystyle=$ $\displaystyle H_{P_{X}P_{Y|X}}(Y|X),$ (79)

where $H_{P_{X}P_{Y|X}}(Y|X)$ denotes the conditional entropy of $Y$ given $X$
when the pair $(X,Y)\sim P_{X}P_{Y|X}$.

###### Proof:

For readability, we will also write $x^{n}(m)$ and $x^{n}(\tilde{M})$ to
indicate the (random) codewords $\phi^{(n)}(m)$ and $\phi^{(n)}(\tilde{M})$.
We have:

$\displaystyle{P}_{\tilde{Y}_{T}}(y)$ $\displaystyle=$
$\displaystyle\frac{1}{n}\sum_{t=1}^{n}P_{\tilde{Y}_{t}}(y)$ (80)
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\frac{1}{n}\sum_{t=1}^{n}\mathbbm{1}\\{\tilde{Y}_{t}=y\\}\right]$
(81) $\displaystyle=$
$\displaystyle\mathbb{E}\left[\pi_{\tilde{Y}^{n}}(y)\right]$ (82)
$\displaystyle=$
$\displaystyle\sum_{x\in\mathcal{X}}\mathbb{E}\left[\pi_{{x}^{n}(\tilde{M})\tilde{Y}^{n}}(x,y)\right]$
(83) $\displaystyle=$
$\displaystyle\sum_{x\in\mathcal{X}}\frac{1}{2^{nR}}\sum_{m=1}^{2^{nR}}\mathbb{E}\left[\pi_{{x}^{n}(m)\tilde{Y}^{n}}(x,y)\bigg{|}\tilde{M}=m\right].$
(84)

Since $\mathcal{D}_{m}$ is a subset of the conditional typical set
$\mathcal{T}_{\mu_{n}}^{(n)}(P_{Y|X=x^{n}(m)})$, for all
$m\in\\{1,\ldots,2^{nR}\\}$, all $y^{n}\in\mathcal{D}_{m}$, and all
$(x,y)\in\mathcal{X}\times\mathcal{Y}$:

$\displaystyle\left|\pi_{{x}^{n}(m)y^{n}}(x,y)-\pi_{{x}^{n}(m)}(x)P_{Y|X}(y|x)\right|\leq\mu_{n},$
(85)

and if $P_{Y|X}(y|x)=0$ then $\pi_{{x}^{n}(m)y^{n}}(x,y)=0$. Plugging these
conditions into (84) we obtain

$\displaystyle{P}_{\tilde{Y}_{T}}(y)$ $\displaystyle\leq$
$\displaystyle\sum_{\begin{subarray}{c}x\in\mathcal{X}\colon\\\
P_{Y|X}(y|x)>0\end{subarray}}\frac{1}{2^{nR}}\sum_{m=1}^{2^{nR}}\pi_{{x}^{n}(m)}(x)P_{Y|X}(y|x)+|\mathcal{X}|\mu_{n}$
(86a) and similarly: $\displaystyle{P}_{\tilde{Y}_{T}}(y)$ $\displaystyle\geq$
$\displaystyle\sum_{\begin{subarray}{c}x\in\mathcal{X}\colon\\\
P_{Y|X}(y|x)>0\end{subarray}}\frac{1}{2^{nR}}\sum_{m=1}^{2^{nR}}\pi_{{x}^{n}(m)}(x)P_{Y|X}(y|x)-|\mathcal{X}|\mu_{n}.$
(86b)

Let now $\\{n_{i}\\}$ be an increasing subsequence of blocklengths so that the
sequence of average types
$\frac{1}{2^{nR}}\sum_{m=1}^{2^{nR}}\pi_{{x}^{n}(m)}(x)$ converges for each
$x\in\mathcal{X}$ and denote the convergence point by ${P}_{X}(x)$. Then,
since $\mu_{n}\to 0$ as $n\to\infty$, by (86):

$\displaystyle\lim_{i\to\infty}{P}_{\tilde{Y}_{T}}(y)=\sum_{x\in\mathcal{X}}{P}_{X}(x)P_{Y|X}(y|x),$
(87)

establishing the first part of the lemma.

Notice next that by definition

$\displaystyle\frac{1}{n}H(\tilde{Y}^{n}|\tilde{M}=m)$ (88) $\displaystyle=$
$\displaystyle-\frac{1}{n}\sum_{y^{n}\in\mathcal{D}_{m}}P_{\tilde{Y}^{n}|\tilde{M}=m}(y^{n})\log
P_{\tilde{Y}^{n}|\tilde{M}=m}(y^{n})$ $\displaystyle=$
$\displaystyle-\frac{1}{n}\sum_{y^{n}\in\mathcal{D}_{m}}P_{\tilde{Y}^{n}|\tilde{M}=m}(y^{n})\log\frac{P_{Y|X}^{\otimes
n}(y^{n}|x^{n}(m))}{\Delta_{m}}$ (94) $\displaystyle=$
$\displaystyle-\frac{1}{n}\sum_{t=1}^{n}\sum_{y^{n}\in\mathcal{D}_{m}}P_{\tilde{Y}^{n}|\tilde{M}=m}(y^{n})\log
P_{Y|X}(y_{t}|x_{t}(m))$ $\displaystyle+\frac{1}{n}\log\Delta_{m}$
$\displaystyle=$
$\displaystyle-\frac{1}{n}\sum_{t=1}^{n}\sum_{y_{t}\in\mathcal{Y}}P_{\tilde{Y}_{t}|\tilde{M}=m}(y_{t})\log
P_{Y|X}(y_{t}|x_{t}(m))$ $\displaystyle+\frac{1}{n}\log\Delta_{m}$
$\displaystyle=$
$\displaystyle-\frac{1}{n}\sum_{t=1}^{n}\sum_{y\in\mathcal{Y}}\mathbb{E}\left[\mathbbm{1}\left\\{\tilde{Y}_{t}=y\right\\}\Big{|}\tilde{M}=m\right]\log
P_{Y|X}(y|x_{t}(m))$ $\displaystyle+\frac{1}{n}\log\Delta_{m}$
$\displaystyle=$
$\displaystyle-\sum_{x\in\mathcal{X}}\sum_{y\in\mathcal{Y}}\mathbb{E}\left[\frac{1}{n}\sum_{t=1}^{n}\mathbbm{1}\left\\{x_{t}(m)=x,\tilde{Y}_{t}=y\right\\}\Big{|}\tilde{M}=m\right]$
$\displaystyle\hskip 56.9055pt\cdot\log P_{Y|X}(y|x)$
$\displaystyle+\frac{1}{n}\log\Delta_{m}$ $\displaystyle=$
$\displaystyle-\sum_{x\in\mathcal{X}}\sum_{y\in\mathcal{Y}}\mathbb{E}\left[\pi_{{x}^{n}(m)\tilde{Y}^{n}}(x,y)\Big{|}\tilde{M}=m\right]\log
P_{Y|X}(y|x)$ $\displaystyle+\frac{1}{n}\log\Delta_{m}.$

Averaging over all messages $m\in\\{1,\ldots,2^{nR}\\}$, we obtain

$\displaystyle\frac{1}{n}H(\tilde{Y}^{n}|\tilde{M})$ (96) $\displaystyle=$
$\displaystyle-\sum_{x\in\mathcal{X}}\sum_{y\in\mathcal{Y}}\frac{1}{2^{nR}}\sum_{m=1}^{2^{nR}}\mathbb{E}\left[\pi_{{x}^{n}(m)\tilde{Y}^{n}}(x,y)\Bigg{|}\tilde{M}=m\right]\log
P_{Y|X}(y|x)$ $\displaystyle+\frac{1}{n}\log\Delta_{m}.$

By (85) and by defining $P_{X}$ as the convergence point of
$\frac{1}{2^{nR}}\sum_{m=1}^{2^{nR}}\pi_{{x}^{n}(m)}(x)$ for the sequence of
blocklengths $\\{n_{i}\\}_{i=1}^{\infty}$, one can follow the same bounding
steps as leading to (86) to obtain:

$\displaystyle\lim_{i\to\infty}\frac{1}{n_{i}}H(\tilde{Y}^{n_{i}}|\tilde{M})$
(97) $\displaystyle=$
$\displaystyle-\sum_{x\in\mathcal{X}}{P}_{X}(x)P_{Y|X}(y|x)\log P_{Y|X}(y|x)$
$\displaystyle=$ $\displaystyle H_{P_{X}P_{Y|X}}(Y|X),$

which concludes the second part of the proof. ∎

##  V Interactive Lossy Compression

This section focuses on the interactive lossy compression problem depicted in
Figure 3.

###  V-A Setup

Consider two terminals, observing the related source sequences $X^{n}$ and
$Y^{n}$, where as in the case of source coding with side-information:

$\displaystyle(X^{n},Y^{n})\textnormal{ i.i.d. }\sim\,P_{XY},$ (98)

for a given probability mass function $P_{XY}$ on the product alphabet
$\mathcal{X}\times\mathcal{Y}$. Communication between the two terminals is
over noise-free links and interactive in $L>0$ rounds. The terminal observing
$X^{n}$ starts communication and thus in all _odd rounds_ $\ell=1,3,5,\ldots$,
the message ${M}_{\ell}$ is created as:

$\displaystyle{M}_{\ell}$ $\displaystyle=$
$\displaystyle\phi_{\ell}^{(n)}(X^{n},{M}_{1},\ldots,{M}_{\ell-1}),\qquad\ell=1,3,5,\ldots,$
(99)

for an encoding function $\phi_{\ell}^{(n)}$ on appropriate domains, where
each message ${M}_{\ell}\in\\{1,\ldots,2^{nR_{\ell}}\\}$, for given non-
negative rates $R_{1},\ldots,R_{L}$. (Note that for $\ell=1$,
$M_{1}=\phi_{1}^{(n)}(X^{n})$. ) In _even rounds_ $\ell=2,4,6,\ldots$ , the
message ${M}_{\ell}\in\\{1,\ldots,2^{nR_{\ell}}\\}$ is created as:

$\displaystyle{M}_{\ell}$ $\displaystyle=$
$\displaystyle\phi_{\ell}^{(n)}(Y^{n},{M}_{1},\ldots,{M}_{\ell-1}),\qquad\ell=2,4,6,\ldots.$
(100)

At the end of the $L$ rounds, each terminal produces a reconstruction sequence
on a pre-specified alphabet. The terminal observing ${X}^{n}$ produces

$W^{n}=g_{X}^{(n)}(X^{n},{M}_{1},\ldots,{M}_{L})$ (101)

for $W^{n}$ taking value on the given alphabet ${\mathcal{W}}^{n}$. The
terminal observing ${Y}^{n}$ produces

$Z^{n}=g_{Y}^{(n)}(Y^{n},{M}_{1},\ldots,{M}_{L})$ (102)

for $Z^{n}$ taking value on the given alphabet ${\mathcal{Z}}^{n}$.

The reconstructions are supposed to satisfy a set of $J$ distortion
constraints:

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}d_{j}(X_{i},Y_{i},W_{i},Z_{i})<D_{j},\qquad
j\in\\{1,\ldots,J\\},$ (103)

for given non-negative symbolwise-distortion functions
$d_{j}(\cdot,\cdot,\cdot,\cdot)$.

###### Definition 3

Given sequences $\\{\delta_{j,n}\\}$, a rate-tuple $R_{1},\ldots,R_{L}\geq 0$
is said $\\{\delta_{j,n}\\}$-achievable if there exist sequences (in $n$) of
encoding functions $\\{\phi_{\ell}^{(n)}\\}_{\ell=1}^{L}$ and reconstruction
functions $g_{X}^{(n)}$ and $g_{Y}^{(n)}$ such that the excess distortion
probabilities satisfy

$\displaystyle\Pr\left[\frac{1}{n}\sum_{i=1}^{n}d_{j}(X_{i},Y_{i},W_{i},Z_{i})>D_{j}\right]\leq\delta_{j,n},\quad
j\in\\{1,\ldots,J\\}.$ (104)

###### Remark 1

Our problem formulation includes various previously studied models as special
cases. For example, the Wyner-Ziv problem [18] is included by setting $L=1$
and choosing a distortion function of the form $d_{j}(X_{i},Z_{i})$. Kaspi’s
interactive source-coding problem is included by restricting to two distortion
functions of the form $d_{1}(X_{i},Z_{i})$ and $d_{2}(Y_{i},W_{i})$. Lossy
source coding with side-information and lossy common reconstruction [28, 27]
is included by setting $L=1$. The interactive function computation problem
[26] is obtained by choosing $J=1$, $D_{1}=0$, and distortion function
$d_{1}(X,Y,W,Z)=\mathbbm{1}\\{Z=W=f(X,Y)\\}$ for the desired function $f$.

###### Theorem 3

Given any sequences $\\{\delta_{j,n}\\}$ satisfying

$\displaystyle\sum_{j=1}^{J}\delta_{j,n}$ $\displaystyle<$ $\displaystyle
1,\qquad n=1,2,\ldots,$ (105a)
$\displaystyle\lim_{n\to\infty}\frac{1}{n}\log\left(1-\sum_{j=1}^{J}\delta_{j,n}\right)$
$\displaystyle=$ $\displaystyle 0,\qquad j\in\\{1,\ldots,J\\},$ (105b)

a rate-tuple $(R_{1},\ldots,R_{L})$ can only be
$\\{\delta_{j,n}\\}$-achievable if it satisfies the rate-constraints

$R_{\ell}\geq I(X;U_{\ell}|U_{1}\cdots
U_{\ell-1}),\quad\ell\in\\{1,\ldots,L\\},$ (106a) for some auxiliary random
variables $U_{1},\ldots,U_{L}$ and reconstruction random variables $W$ and $Z$
satisfying the distortion constraints $\displaystyle
d_{j}\big{(}X,Y,W,Z\big{)}$ $\displaystyle<$ $\displaystyle D_{j},\qquad
j\in\\{1,\ldots,J\\},$ (106b) for $(X,Y)\sim P_{XY}$, and the Markov chains
$\displaystyle U_{\ell}\to$ $\displaystyle(X,U_{1},\ldots,U_{\ell-1})\to Y,$
$\displaystyle\quad\ell=1,3,5,\ldots,$ (106c) $\displaystyle U_{\ell}\to$
$\displaystyle(Y,U_{1},\ldots,U_{\ell-1})\to X,$
$\displaystyle\quad\ell=2,4,6,\ldots,$ (106d) $\displaystyle W\to$
$\displaystyle(X,U_{1},\ldots,U_{L})\to Y,$ (106e) $\displaystyle Z\to$
$\displaystyle(Y,U_{1},\ldots,U_{L})\to X,$ (106f)

######  Remark 2 (A single distortion)

For a single distortion constraint $J=1$, the theorem implies that if the
rate-tuple violates the constraints in the theorem, then the probability of
excess distortion tends to 1 exponentially fast.

######  Remark 3 (Vector-valued distortions)

Theorem 3 extends in a straightforward manner to vector-valued distortion
functions and vector distortions

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\boldsymbol{d}_{j}(X_{i},Y_{i},W_{i},Z_{i})<\boldsymbol{D}_{j},\qquad
j\in\\{1,\ldots,J\\},$ (107)

where $\boldsymbol{D}_{j}\in\mathbb{R}^{\nu_{j}}$ for some positive integer
$\nu_{j}$, distortion functions are non-negative and of the form
$\boldsymbol{d}_{j}\colon\mathcal{X}\times\mathcal{Y}\times\mathcal{W}\times\mathcal{Z}\to\mathbb{R}^{\nu_{j}}$,
and inequality (107) is meant component-wise. The difference between $J$
scalar distortion constraints as in (103) and a single $J$-valued vector-
distortion function as in (107) is that the vector-distortion constraint
limits the probability that _any_ of the $J$ constraints is violated whereas
the $J$ scalar distortion constraints individually limit the probability of
each distortion to be violated.

In the following section, we prove the strong converse, i.e., the non-
achievability of any rate-tuple $(R_{1},\ldots,R_{L})$ not satisfying the
above conditions, for any sequences $\\{\delta_{j,n}\\}$ satisfying (105).
Using standard arguments, it can be shown that for any rate-tuple
$(R_{1},\ldots,R_{L})$ satisfying constraints (106) there exist excess
probabilities $\\{\delta_{j,n}\\}$ all tending to 0 as $n\to\infty$ and so
that the the rate-tuple $(R_{1},\ldots,R_{L})$ is
$\\{\delta_{j,n}\\}$-achievable.

###  V-B Strong Converse Proof

Fix a sequence of encoding functions $\\{\phi_{\ell}^{(n)}\\}_{\ell=1}^{L}$
and reconstruction functions $g_{X}^{(n)}$ and $g_{Y}^{(n)}$ satisfying (104).
Choose a sequence of positive real numbers $\\{\mu_{n}\\}$ satisfying

$\displaystyle\lim_{n\to\infty}\mu_{n}$ $\displaystyle=$ $\displaystyle 0$
(108) $\displaystyle\lim_{n\to\infty}\left(n\cdot\mu_{n}^{2}\right)^{-1}$
$\displaystyle=$ $\displaystyle 0,$ (109)

and the set

$\displaystyle\mathcal{D}_{n}:=\Big{\\{}(x^{n},y^{n})\in\mathcal{T}_{\mu_{n}}^{(n)}(P_{XY})\colon$
(110) $\displaystyle d_{j}^{(n)}\left(g_{X}^{(n)}(x^{n},{m}_{1}^{L}),\
g_{Y}^{(n)}\left(y^{n},{m}_{1}^{L}\right)\right)\leq D_{j},$
$\displaystyle\hskip 113.81102pt\quad j\in\\{1,\ldots,J\\}\Big{\\}},$

where ${m}_{1}^{L}:=({m}_{1},\ldots,{m}_{L})$ and for odd values of $\ell$ we
have ${m}_{\ell}=\phi_{\ell}^{(n)}(x^{n},{m}_{1},\ldots,{m}_{\ell-1})$ whereas
for even values of $\ell$ we have
${m}_{\ell}=\phi_{\ell}^{(n)}(y^{n},{m}_{1},\ldots,{m}_{\ell-1})$.

Define also the probability

$\Delta_{n}:=\Pr[(X^{n},Y^{n})\in\mathcal{D}_{n}]$ (111)

and notice that by (104) and [3, Remark to Lemma 2.12]:

$\Delta_{n}\geq
1-\sum_{j=1}^{J}\delta_{j,n}-\frac{|\mathcal{X}||\mathcal{Y}|}{4\mu^{2}n},$
(112)

which by assumptions (105b) and (109) satisfies

$\lim_{n\to\infty}\frac{1}{n}\log\Delta_{n}=0.$ (113)

Let further $(\tilde{X}^{n},\tilde{Y}^{n})$ be random variables of joint pmf

$P_{\tilde{X}^{n}\tilde{Y}^{n}}(x^{n},y^{n})=\frac{P_{{X}{Y}}^{\otimes
n}(x^{n},y^{n})}{\Delta_{n}}\cdot\mathbbm{1}\\{(x^{n},y^{n})\in\mathcal{D}_{n}\\}.$
(114)

Let also $T$ be uniform over $\\{1,\ldots,n\\}$ independent of
$(\tilde{X}^{n},\tilde{Y}^{n})$, and define:

$\displaystyle\tilde{M}_{\ell}$ $\displaystyle=$
$\displaystyle\phi_{\ell}^{(n)}(\tilde{X}^{n},\tilde{M}_{1},\ldots,\tilde{M}_{\ell-1}),\qquad\ell=1,3,5,\ldots,$
(115) $\displaystyle\tilde{M}_{\ell}$ $\displaystyle=$
$\displaystyle\phi_{\ell}^{(n)}(\tilde{Y}^{n},\tilde{M}_{1},\ldots,\tilde{M}_{\ell-1}),\qquad\ell=2,4,6,\ldots.$
(116)

Note that for $\ell=1$, $\tilde{M}_{1}=\phi_{1}^{(n)}(\tilde{X}^{n})$. Define
the auxiliary random variables

$\displaystyle U_{1}$ $\displaystyle:=$
$\displaystyle(\tilde{X}^{T-1},\tilde{Y}_{T+1}^{n},\tilde{{M}}_{1},T)$ (117a)
$\displaystyle U_{\tau}$ $\displaystyle:=$
$\displaystyle\tilde{{M}}_{\tau},\qquad\tau\in\\{2,\ldots,L\\}.$ (117b)

We start with some preliminary observations. For any odd $\ell\geq 1$ observe
the following:

$\displaystyle\frac{1}{n}H(\tilde{X}^{n}|\tilde{Y}^{n}\tilde{{M}}_{1}\cdots\tilde{{M}}_{\ell})$
(121) $\displaystyle\stackrel{{\scriptstyle(d)}}{{=}}$
$\displaystyle\frac{1}{n}\big{[}H(\tilde{X}^{n}|\tilde{Y}^{n}\tilde{{M}}_{1}\cdots\tilde{{M}}_{\ell})$
$\displaystyle\qquad+\sum_{\begin{subarray}{c}\tau\in\\{1,\ldots,\ell\\}\colon\\\
\tau\textnormal{
odd}\end{subarray}}I(\tilde{{M}}_{\tau};\tilde{Y}^{n}|\tilde{X}^{n}\tilde{{M}}_{1}\cdots\tilde{{M}}_{\tau-1})$
$\displaystyle\qquad+\sum_{\begin{subarray}{c}\tau\in\\{2,\ldots,\ell-1\\}\colon\\\
\tau\textnormal{
even}\end{subarray}}I(\tilde{{M}}_{\tau};\tilde{X}^{n}|\tilde{Y}^{n}\tilde{{M}}_{1}\cdots\tilde{{M}}_{\tau-1})\big{]}$
$\displaystyle=$
$\displaystyle\frac{1}{n}\left[H(\tilde{X}^{n}|\tilde{Y}^{n}\tilde{{M}}_{1}\cdots\tilde{{M}}_{\ell})-H(\tilde{Y}^{n}|\tilde{X}^{n}\tilde{{M}}_{1}\cdots\tilde{{M}}_{\ell})\right]$
$\displaystyle+\frac{1}{n}\left[H(\tilde{Y}^{n}|\tilde{X}^{n}\tilde{{M}}_{1}\cdots\tilde{{M}}_{\ell-1})-H(\tilde{X}^{n}|\tilde{Y}^{n}\tilde{{M}}_{1}\cdots\tilde{{M}}_{\ell-1})\right]$
$\displaystyle+\cdots\phantom{\big{[}}$
$\displaystyle+\frac{1}{n}\left[H(\tilde{X}^{n}|\tilde{Y}^{n}\tilde{{M}}_{1})-H(\tilde{Y}^{n}|\tilde{X}^{n}\tilde{{M}}_{1})\right]$
$\displaystyle+\frac{1}{n}H(\tilde{Y}^{n}|\tilde{X}^{n})$
$\displaystyle\stackrel{{\scriptstyle(e)}}{{=}}$ $\displaystyle
H(\tilde{X}_{T}|\tilde{Y}_{T}U_{1}\cdots
U_{\ell})-H(\tilde{Y}_{T}|\tilde{X}_{T}U_{1}\cdots U_{\ell})$
$\displaystyle+H(\tilde{Y}_{T}|\tilde{X}_{T}U_{1}\cdots
U_{\ell-1})-H(\tilde{X}_{T}|\tilde{Y}_{T}U_{1}\cdots U_{\ell-1})$
$\displaystyle+\cdots$
$\displaystyle+H(\tilde{X}_{T}|\tilde{Y}_{T}U_{1})-H(\tilde{Y}_{T}|\tilde{X}_{T}U_{1})$
$\displaystyle+H(\tilde{Y}_{T}|\tilde{X}_{T})+o(1)$
$\displaystyle\stackrel{{\scriptstyle(f)}}{{=}}$ $\displaystyle
H(\tilde{X}_{T}|\tilde{Y}_{T}U_{1}\cdots U_{\ell})$
$\displaystyle+\sum_{\begin{subarray}{c}\tau\in\\{1,\ldots,\ell\\}\colon\\\
\tau\textnormal{
odd}\end{subarray}}I(U_{\tau};\tilde{Y}_{T}|\tilde{X}_{T}U_{1}\cdots
U_{\tau-1})$
$\displaystyle+\sum_{\begin{subarray}{c}\tau\in\\{{2,\ldots,\ell-1}\\}\colon\\\
\tau\textnormal{
even}\end{subarray}}I(U_{\tau};\tilde{X}_{T}|\tilde{Y}_{T}U_{1}\cdots
U_{\tau-1})+o(1)$ $\displaystyle\stackrel{{\scriptstyle{(g)}}}{{\geq}}$
$\displaystyle H(\tilde{X}_{T}|\tilde{Y}_{T}U_{1}\cdots U_{\ell})+o(1),$ (122)

where, $(d)$ holds because for $\tau$ odd, the message $\tilde{{M}}_{\tau}$ is
a function of $(\tilde{X}^{n},\tilde{{M}}_{1},\ldots,\tilde{{M}}_{\tau-1})$
and thus
$I(\tilde{{M}}_{\tau};\tilde{Y}^{n}|\tilde{X}^{n}\tilde{{M}}_{1}\cdots\tilde{{M}}_{\tau-1})=0$
whereas for $\tau$ even the message $\tilde{{M}}_{\tau}$ is a function of
$(\tilde{Y}^{n},\tilde{{M}}_{1},\ldots,\tilde{{M}}_{\tau-1})$ and thus
$I(\tilde{{M}}_{\tau};\tilde{X}^{n}|\tilde{Y}^{n}\tilde{{M}}_{1}\cdots\tilde{{M}}_{\tau-1})=0$;
$(e)$ holds by Lemmas 1 and 2 in Section II and Definitions (117), where for
the application of Lemma 1 we also used Equation (113), and it is worth noting
here that when $\ell=1$, all the terms before and including the sequential
summation “+$\cdots$” do not exist anymore; $(f)$ holds by dividing the
entropy terms between sums for $\tau$ odd and even and by definition of the
mutual information ; and ${(g)}$ holds by the non-negativity of mutual
information.

Following similar steps, we obtain for any even $\ell\geq 2$:

$\displaystyle\frac{1}{n}H(\tilde{Y}^{n}|\tilde{X}^{n}\tilde{{M}}_{1}\cdots\tilde{{M}}_{\ell})\geq
H(\tilde{Y}_{T}|\tilde{X}_{T}U_{1}\cdots U_{\ell})+o(1).$ (123)

We now apply bounds (122) and (123) to obtain the desired bounds on the rates
and prove validity of some desired asymptotic Markov chains. For any odd
$\ell\geq 1$, we have

$\displaystyle R_{\ell}$ $\displaystyle\geq$
$\displaystyle\frac{1}{n}H(\tilde{{M}}_{\ell})\geq\frac{1}{n}H(\tilde{{M}}_{\ell}|\tilde{Y}^{n}\tilde{{M}}_{1}\cdots\tilde{{M}}_{\ell-1})$
(127) $\displaystyle=$
$\displaystyle\frac{1}{n}I(\tilde{{M}}_{\ell};\tilde{X}^{n}|\tilde{Y}^{n}\tilde{{M}}_{1}\cdots\tilde{{M}}_{\ell-1})$
$\displaystyle=$
$\displaystyle\frac{1}{n}\left[H(\tilde{X}^{n}|\tilde{Y}^{n}\tilde{{M}}_{1}\cdots\tilde{{M}}_{\ell-1})-H(\tilde{X}^{n}|\tilde{Y}^{n}\tilde{{M}}_{1}\cdots\tilde{{M}}_{\ell})\right]$
$\displaystyle\stackrel{{\scriptstyle(h)}}{{\geq}}$
$\displaystyle\frac{1}{n}\big{[}H(\tilde{X}^{n}|\tilde{Y}^{n}\tilde{{M}}_{1}\cdots\tilde{{M}}_{\ell-2})$
$\displaystyle\hskip
14.22636pt-\sum_{i=1}^{n}H(\tilde{X}_{i}|\tilde{Y}_{i}\tilde{X}^{i-1}\tilde{Y}_{i+1}^{n}\tilde{{M}}_{1}\cdots\tilde{{M}}_{\ell})\big{]}$
$\displaystyle\stackrel{{\scriptstyle(i)}}{{\geq}}$ $\displaystyle
H(\tilde{X}_{T}|\tilde{Y}_{T}U_{1}\cdots
U_{\ell-2})-H(\tilde{X}_{T}|\tilde{Y}_{T}U_{1}\cdots U_{\ell})$
$\displaystyle+o(1)$ $\displaystyle=$ $\displaystyle
I(U_{\ell-1}U_{\ell};\tilde{X}_{T}|\tilde{Y}_{T}U_{1}\cdots U_{\ell-2})+o(1)$
(128) $\displaystyle\geq$ $\displaystyle
I(U_{\ell};\tilde{X}_{T}|\tilde{Y}_{T}U_{1}\cdots U_{\ell-1})+o(1),$ (129)

where $(h)$ holds because for $\ell$ odd message $\tilde{{M}}_{\ell-1}$ is a
function of the tuple
$(\tilde{Y}^{n},\tilde{{M}}_{1},\ldots,\tilde{{M}}_{\ell-2})$ and because
conditioning can only reduce entropy; and $(i)$ holds by (117) and (122).
Notice that for $\ell=1$:

$\displaystyle R_{1}$ $\displaystyle\geq$ $\displaystyle
I(U_{1};\tilde{X}_{T}|\tilde{Y}_{T})+o(1).$ (130)

For any even $\ell\geq 2$, we have:

$\displaystyle R_{\ell}$ $\displaystyle\geq$
$\displaystyle\frac{1}{n}H(\tilde{{M}}_{\ell})$ (131) $\displaystyle\geq$
$\displaystyle\frac{1}{n}I(\tilde{{M}}_{\ell};\tilde{Y}^{n}|\tilde{X}^{n}\tilde{{M}}_{1}\cdots\tilde{{M}}_{\ell-1})$
(134) $\displaystyle\stackrel{{\scriptstyle(j)}}{{=}}$
$\displaystyle\frac{1}{n}\left[H(\tilde{Y}^{n}|\tilde{X}^{n}\tilde{{M}}_{1}\cdots\tilde{{M}}_{\ell-2})-H(\tilde{Y}^{n}|\tilde{X}^{n}\tilde{{M}}_{1}\cdots\tilde{{M}}_{\ell})\right]$
$\displaystyle\stackrel{{\scriptstyle(k)}}{{\geq}}$ $\displaystyle
H(\tilde{Y}_{T}|\tilde{X}_{T}U_{1}\cdots
U_{\ell-2})-H(\tilde{Y}_{T}|\tilde{X}_{T}U_{1}\cdots U_{\ell})$
$\displaystyle+o(1)$ $\displaystyle\geq$ $\displaystyle
I(U_{\ell};\tilde{Y}_{T}|\tilde{X}_{T}U_{1}\cdots U_{\ell-1})+o(1)$ (135)

where $(j)$ holds because for $\ell$ even $\tilde{M}_{\ell-1}$ is a function
of $(\tilde{X}^{n},\tilde{M}_{1},\ldots,\tilde{M}_{\ell-2})$ and $(k)$ holds
by (117) and (123).

We next notice that for $\ell$ even (because the message $\tilde{{M}}_{\ell}$
is a function of
$(\tilde{Y}^{n},\tilde{{M}}_{1},\ldots,\tilde{{M}}_{\ell-1})$):

$\displaystyle 0$ $\displaystyle=$
$\displaystyle\frac{1}{n}I(\tilde{{M}}_{\ell};\tilde{X}^{n}|\tilde{Y}^{n}\tilde{{M}}_{1}\cdots\tilde{{M}}_{\ell-1})$
(136) $\displaystyle=$
$\displaystyle\frac{1}{n}\left[H(\tilde{X}^{n}|\tilde{Y}^{n}\tilde{{M}}_{1}\cdots\tilde{{M}}_{\ell-1})-H(\tilde{X}^{n}|\tilde{Y}^{n}\tilde{{M}}_{1}\cdots\tilde{{M}}_{\ell})\right]$
$\displaystyle\stackrel{{\scriptstyle(l)}}{{\geq}}$ $\displaystyle
H(\tilde{X}_{T}|\tilde{Y}_{T}U_{1}\cdots U_{\ell-1})+o(1)$
$\displaystyle-\frac{1}{n}\sum_{i=1}^{n}H(\tilde{X}_{i}|\tilde{X}^{i-1}\tilde{Y}_{i}\tilde{Y}_{i+1}^{n}\tilde{{M}}_{1}\cdots\tilde{{M}}_{\ell})$
$\displaystyle=$ $\displaystyle
I(U_{\ell};\tilde{X}_{T}|\tilde{Y}_{T}U_{1}\cdots U_{\ell-1}){+o(1)},$ (137)

where $(l)$ holds by (122) and because conditioning can only reduce entropy.

Similarly, for $\ell\geq 1$ odd (because the message $\tilde{{M}}_{\ell}$ is a
function of $(\tilde{X}^{n},\tilde{{M}}_{1},\ldots,\tilde{{M}}_{\ell-1})$):

$\displaystyle 0$ $\displaystyle=$
$\displaystyle\frac{1}{n}I(\tilde{{M}}_{\ell};\tilde{Y}^{n}|\tilde{X}^{n}\cdots\tilde{{M}}_{\ell-1})$
(138) $\displaystyle=$
$\displaystyle\frac{1}{n}\left[H(\tilde{Y}^{n}|\tilde{X}^{n}\tilde{{M}}_{1}\cdots\tilde{{M}}_{\ell-1})-H(\tilde{Y}^{n}|\tilde{X}^{n}\tilde{{M}}_{1}\cdots\tilde{{M}}_{\ell})\right]$
$\displaystyle\geq$ $\displaystyle
I(U_{\ell};\tilde{Y}_{T}|\tilde{X}_{T}U_{1}\cdots U_{\ell-1})+o(1).$

In particular, for $\ell=1$, message $\tilde{{M}}_{1}$ is a function of
$\tilde{X}^{n}$ and we have:

$\displaystyle 0$ $\displaystyle=$
$\displaystyle\frac{1}{n}I(\tilde{{M}}_{1};\tilde{Y}^{n}|\tilde{X}^{n})\geq
I(U_{1};\tilde{Y}_{T}|\tilde{X}_{T})+o(1).$ (139)

Let now
${\tilde{W}}^{n}:=g_{X}(\tilde{X}^{n},\tilde{{M}}_{1},\ldots,\tilde{{M}}_{L})$
and
${\tilde{Z}}^{n}:=g_{Y}(\tilde{Y}^{n},\tilde{{M}}_{1},\ldots,\tilde{{M}}_{L})$
and notice that by our definition of the set $\mathcal{D}_{n}$, for any
$j\in\\{1,\ldots,J\\}$:

$\displaystyle D_{j}$ $\displaystyle\geq$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}d_{j}\left(\tilde{X}_{i},\tilde{Y}_{i},{\tilde{W}}_{i},{\tilde{Z}}_{i}\right)$
(140) $\displaystyle=$
$\displaystyle\mathbb{E}\left[d_{j}\left(\tilde{X}_{T},\tilde{Y}_{T},{\tilde{W}}_{T},{\tilde{Z}}_{T}\right)\right].$
(141)

For simplicity, in the sequel we assume that $L$ is even; if $L$ is odd the
proof is similar. Similarly to (137) and (138), since
${\tilde{W}}^{n}:=g_{X}(\tilde{X}^{n},\tilde{{M}}_{1},\ldots,\tilde{{M}}_{L})$
and
${\tilde{Z}}^{n}:=g_{Y}(\tilde{Y}^{n},\tilde{{M}}_{1},\ldots,\tilde{{M}}_{L})$,
we have:

$\displaystyle 0$ $\displaystyle=$
$\displaystyle\frac{1}{n}I({\tilde{Z}}^{n};\tilde{X}^{n}|\tilde{Y}^{n}\tilde{{M}}_{1}\cdots\tilde{{M}}_{L})$
$\displaystyle\stackrel{{\scriptstyle(m)}}{{=}}$
$\displaystyle\frac{1}{n}\left[H(\tilde{X}^{n}|\tilde{Y}^{n}\tilde{{M}}_{1}\cdots\tilde{{M}}_{{L-1}})-H(\tilde{X}^{n}|\tilde{Y}^{n}\tilde{{M}}_{1}\cdots\tilde{{M}}_{L}{\tilde{Z}}^{n})\right]$
$\displaystyle\stackrel{{\scriptstyle(n)}}{{\geq}}$ $\displaystyle
H(\tilde{X}_{T}|\tilde{Y}_{T}U_{1}\cdots U_{{L-1}})+o(1)$
$\displaystyle-\frac{1}{n}\sum_{i=1}^{n}H(\tilde{X}_{i}|\tilde{X}^{i-1}\tilde{Y}_{i}\tilde{Y}_{i+1}^{n}\tilde{{M}}_{1}\cdots\tilde{{M}}_{L}{\tilde{Z}}_{i})$
$\displaystyle=$ $\displaystyle
I(U_{L}{\tilde{Z}_{T}};\tilde{X}_{T}|\tilde{Y}_{T}U_{1}\cdots U_{L-1})+o(1)$
$\displaystyle\geq$ $\displaystyle
I({\tilde{Z}}_{T};\tilde{X}_{T}|\tilde{Y}_{T}U_{1}\cdots U_{L})+o(1)$ (143)

and

$\displaystyle 0$ $\displaystyle=$
$\displaystyle\frac{1}{n}I({\tilde{W}}^{n};\tilde{Y}^{n}|\tilde{X}^{n}\tilde{{M}}_{1}\cdots\tilde{{M}}_{L})$
(144) $\displaystyle=$
$\displaystyle\frac{1}{n}\left[H(\tilde{Y}^{n}|\tilde{X}^{n}\tilde{{M}}_{1}\cdots\tilde{{M}}_{L})-H(\tilde{Y}^{n}|\tilde{X}^{n}\tilde{{M}}_{1}\cdots\tilde{{M}}_{L}{\tilde{W}}^{n})\right]$
$\displaystyle\geq$ $\displaystyle
I({\tilde{W}}_{T};\tilde{Y}_{T}|\tilde{X}_{T}U_{1}\cdots U_{L})+o(1),$

where $(m)$ holds since for even $L$, message $\tilde{M}_{L}$ is a function of
$(\tilde{Y}^{n},\tilde{M}_{1},\cdots,\tilde{M}_{L-1})$; and $(n)$ holds by
(122) since $L-1$ is odd and because conditioning can only reduce entropy.

The desired rate constraints are then obtained by combining (129), (130),
(135), (137), (138), (139), (141), (143), and (144) and by taking
$n\to\infty$. Details are as follows. By Carathéodory’s theorem [34, Appendix
C], there exist auxiliary random variables ${U}_{1},\ldots,U_{L}$ of bounded
alphabets satisfying (129), (130), (135), (137), (138), (139), (141), (143),
and (144). We restrict to such auxiliary random variables and invoke the
Bolzano-Weierstrass theorem to conclude the existence of a pmf $P_{U_{1}\cdots
U_{L}{X}{Y}W{Z}}^{*}$, also abbreviated as $P^{*}$, and an increasing
subsequence of blocklengths $\\{n_{i}\\}_{i=1}^{\infty}$ so that

$\displaystyle\lim_{{i\to\infty}}P_{U_{1}\cdots
U_{L}\tilde{X}\tilde{Y}\tilde{W}\tilde{Z};n_{i}}$ $\displaystyle=$
$\displaystyle P_{U_{1}\cdots U_{L}{X}{Y}W{Z}}^{*},$ (145)

where $P_{U_{1}\cdots U_{L}\tilde{X}\tilde{Y}\tilde{W}\tilde{Z};n_{i}}$
denotes the pmf of the tuple $(U_{1}\cdots
U_{L}\tilde{X}_{T}\tilde{Y}_{T}\tilde{W}_{T}\tilde{Z}_{T})$ at blocklength
$n_{i}$.

Notice that for any blocklength $n_{i}$ the pair
$\big{(}\tilde{X}^{n_{i}},\tilde{Y}^{n_{i}}\big{)}$ lies in the jointly
typical set $\mathcal{T}^{(n_{i})}_{\mu_{n_{i}}}(P_{XY})$, i.e.,
$\big{|}P_{\tilde{X}\tilde{Y};n_{i}}-P_{XY}\big{|}\leq\mu_{n_{i}}$, and thus
since $\mu_{n}\to 0$ as $n\to\infty$, by the definition of
$(\tilde{X}_{T},\tilde{Y}_{T})$ and by (145), the limiting pmf satisfies
$P^{*}_{{X}{Y}}=P_{XY}$. We further deduce from (129), (130), (135), (137),
(138), (139), (141), (143), and (144) that:

$\displaystyle R_{\ell}$ $\displaystyle\geq$ $\displaystyle
I_{P^{*}}(X;U_{\ell}|YU_{1}\cdots U_{\ell-1}),\qquad\ell=1,3\ldots$ (146a)
$\displaystyle R_{\ell}$ $\displaystyle\geq$ $\displaystyle
I_{P^{*}}(Y;U_{\ell}|XU_{1}\cdots U_{\ell-1}),\qquad\ell=2,4\ldots$ (146b)
$\displaystyle 0$ $\displaystyle=$ $\displaystyle
I_{P^{*}}(Y;U_{\ell}|XU_{1}\cdots U_{\ell-1}),\qquad\ell=1,3\ldots$ (146c)
$\displaystyle 0$ $\displaystyle=$ $\displaystyle
I_{P^{*}}(X;U_{\ell}|YU_{1}\cdots U_{\ell-1}),\qquad\ell=2,4\ldots$ (146d)
$\displaystyle 0$ $\displaystyle=$ $\displaystyle I_{P^{*}}(Z;X|YU_{1}\cdots
U_{L}),$ (146e) $\displaystyle 0$ $\displaystyle=$ $\displaystyle
I_{P^{*}}(W;Y|XU_{1}\cdots U_{L}),$ (146f)

where the subscript $P^{*}$ indicates that the mutual information quantities
should be computed with respect to $P^{*}$.

Combined with (141), which implies

$\displaystyle D_{j}$ $\displaystyle\geq$
$\displaystyle\mathbb{E}_{P^{*}}[d_{j}(X,Y,{W},{{Z}})],\quad
j\in\\{1,\ldots,J\\},$ (147)

above (in)equalities (146) conclude the desired converse proof.

##  VI Testing Against Independence in a $K$-Hop Network

In this section we focus on the $K$-hop hypothesis testing setup in Figure 4.

###  VI-A Setup

Consider a system with a transmitter T0 observing the source sequence
$Y_{0}^{n}$, $K-1$ relays labelled $\text{R}_{1},\ldots,\text{R}_{K-1}$ and
observing sequences $Y_{1}^{n},\ldots,Y_{K-1}^{n}$, respectively, and a
receiver RK observing sequence $Y_{K}^{n}$.

The source sequences $(Y_{0}^{n},Y_{1}^{n},\ldots,Y_{K}^{n})$ are distributed
according to one of two distributions depending on a binary hypothesis
$\mathcal{H}\in\\{0,1\\}$:

$\displaystyle\textnormal{if
}\mathcal{H}=0:(Y_{0}^{n},Y_{1}^{n},\ldots,Y_{K}^{n})\textnormal{ i.i.d.
}\sim\,P_{Y_{0}Y_{1}}P_{Y_{2}|Y_{1}}\cdots P_{Y_{K}|Y_{K-1}};$ (148a)
$\displaystyle\textnormal{if
}\mathcal{H}=1:(Y_{0}^{n},Y_{1}^{n},\ldots,Y_{K}^{n})\textnormal{ i.i.d.
}\sim\,P_{Y_{0}}\cdot P_{Y_{1}}\cdots P_{Y_{K}}.$

Communication takes place over $K$ hops as illustrated in Figure 4. The
transmitter T0 sends a message ${M}_{1}=\phi_{0}^{(n)}(Y_{0}^{n})$ to the
first relay R1, which sends a message
${M}_{2}=\phi_{1}^{(n)}(Y_{1}^{n},{M}_{1})$ to the second relay and so on. The
communication is thus described by encoding functions

$\displaystyle\phi_{0}^{(n)}$ $\displaystyle\colon$
$\displaystyle\mathcal{Y}_{0}^{n}\to\\{1,\ldots,2^{nR_{1}}\\},$ (149)
$\displaystyle\phi_{k}^{(n)}$ $\displaystyle\colon$
$\displaystyle\mathcal{Y}_{k}^{n}\times\\{1,\ldots,2^{nR_{k}}\\}\to\\{1,\ldots,2^{nR_{k+1}}\\},$
(150) $\displaystyle\hskip 113.81102pt\quad k\in\\{1,\ldots,K-1\\},$

and messages are obtained as:

$\displaystyle{M}_{1}$ $\displaystyle=$
$\displaystyle\phi_{0}^{(n)}({Y}_{0}^{n})$ (151) $\displaystyle{M}_{k+1}$
$\displaystyle=$ $\displaystyle\phi_{k}^{(n)}({Y}_{k}^{n},{M}_{k}),\quad
k\in\\{1,\ldots,K-1\\}.$ (152)

Each relay R1, …, RK-1 as well as the receiver RK, produces a guess of the
hypothesis $\mathcal{H}$. These guesses are described by guessing functions

$g_{k}^{(n)}\colon\mathcal{Y}_{k}^{n}\times\\{1,\ldots,2^{nR_{k}}\\}\to\\{0,1\\},\quad
k\in\\{1,\ldots,K\\},$ (153)

where we request that the guesses

$\displaystyle\hat{\mathcal{H}}_{k}=g_{k}^{(n)}(Y_{k}^{n},{M}_{k}),\quad
k\in\\{1,\ldots,K\\},$ (154)

have type-I error probabilities

$\displaystyle\alpha_{k,n}$ $\displaystyle\triangleq$
$\displaystyle\Pr[\hat{\mathcal{H}}_{k}=1|\mathcal{H}=0],\quad
k\in\\{1,\ldots,K\\},$ (155)

not exceeding given thresholds, and type-II error probabilities

$\displaystyle\beta_{k,n}$ $\displaystyle\triangleq$
$\displaystyle\Pr[\hat{\mathcal{H}}_{k}=0|\mathcal{H}=1],\quad
k\in\\{1,\ldots,K\\},$ (156)

decaying to 0 exponentially fast with largest possible exponents.

###### Definition 4

Given sequences of allowed type-I error probabilities $\\{\delta_{k,n}\\}$ and
rates $R_{1},R_{2},\ldots,R_{K}\geq 0$, the exponent tuple
$(\theta_{1},\theta_{2},\ldots,\theta_{K})$ is called _$\\{\delta_{k,n}\\}$
-achievable_ if there exists a sequence of encoding and decision functions
$\big{\\{}\phi_{0}^{(n)},\phi_{1}^{(n)},\ldots,\phi_{K-1}^{(n)},g_{1}^{(n)},g_{2}^{(n)},\ldots,g_{K}^{(n)}\big{\\}}_{n\geq
1}$ satisfying for each $k\in\\{1,\ldots,K\\}$ and blocklength $n$:

$\displaystyle\alpha_{k,n}$ $\displaystyle\leq$ $\displaystyle\delta_{k,n},$
(157a) $\displaystyle\varliminf_{n\to\infty}{1\over n}\log{1\over\beta_{k,n}}$
$\displaystyle\geq$ $\displaystyle\theta_{k}.$ (157b)

###  VI-B Old and New Results

###### Definition 5

For any $\ell\in\\{1,\ldots,K\\}$, define the function

$\displaystyle\eta_{\ell}\colon\mathbb{R}_{0}^{+}$ $\displaystyle\to$
$\displaystyle\mathbb{R}_{0}^{+}$ (158) $\displaystyle R$
$\displaystyle\mapsto$
$\displaystyle\max_{\begin{subarray}{c}P_{U|Y_{\ell-1}}\colon\\\ R\geq
I\left(U;Y_{\ell-1}\right)\end{subarray}}I\left(U;Y_{\ell}\right).$ (159)

The described setup was previously studied in [29] and [31], and an extension
of the setup under variable-length coding was considered in [35]. While for a
general number of users $K\geq 2$ only achievability results and weak
converses were presented [29], for $K=2$ users a strong converse was derived.

######  Theorem 4 (Theorems 2 and 3 in [31])

Let $K=2$ and consider fixed allowed type-I error probabilities

$\displaystyle\delta_{k,n}=\epsilon_{k},\quad k\in\\{1,2\\},$ (160)

for given $\epsilon_{1},\epsilon_{2}\in[0,1)$ with
$\epsilon_{1}+\epsilon_{2}\neq 1$. An exponent pair $(\theta_{1},\theta_{2})$
is $(\epsilon_{1},\epsilon_{2})$-achievable if, and only if,

$\displaystyle\theta_{k}\leq\sum_{\ell=1}^{k}\eta_{\ell}(R_{\ell}),\qquad
k\in\\{1,2\\}.$ (161)

###### Remark 4

In [31], the presentation of Theorem 4 was split into two separate theorems
depending on the values of $\epsilon_{1}$ and $\epsilon_{2}$. While [31,
Theorem 2] considers the case $\epsilon_{1}+\epsilon_{2}<1$ and coincides with
above formulation, [31, Theorem 3] considers the case
$\epsilon_{1}+\epsilon_{2}>1$ and is formulated as an optimization problem
over three auxiliary random variables $U_{1},U_{2},V$. Without loss in
optimality, this optimization can however be restricted to auxiliaries
$U_{1}=U_{2}$, and [31, Theorem 3] simplifies to the form presented in above
Theorem 4.

###### Remark 5

The set of pairs $(\theta_{1},\theta_{2})$ that are
$(\epsilon_{1},\epsilon_{2})$ achievable according to Theorem 4 does not
depend on the values of $\epsilon_{1}$ and $\epsilon_{2}$ (as long as
$\epsilon_{1}+\epsilon_{2}\neq 1$) and forms a rectangular region. In
particular, each of the two exponents can be maximized without affecting the
other exponent. This result extends to a general number of $K\geq 2$ users, as
shown by the achievability result in [29] and by the strong converse result in
the following Theorem 5.

Our main result in this section (Theorem 5 ahead) generalizes the strong
converse in Theorem 4 to arbitrary $K\geq 2$ and arbitrary
$\epsilon_{1},\ldots,\epsilon_{K}\in[0,1)$. Technically speaking, we prove an
exponentially-strong converse result that is a stronger statement. In fact,
for any $k$, an exponent $\theta_{k}$ violating Condition (163) can only be
achieved with probabilities $\alpha_{k,n}$ that tend to 1 exponentially fast
in the blocklength $n$.

###### Theorem 5

Let $\\{\delta_{k,n}\\}$ be sequences satisfying

$\displaystyle\lim_{n\to\infty}\frac{1}{n}\log(1-\delta_{k,n})$
$\displaystyle=$ $\displaystyle 0,\qquad k\in\\{1,\ldots,K\\}.$ (162)

Given rates $R_{1},\ldots,R_{K}\geq 0$, the exponent-tuple
$(\theta_{1},\ldots,\theta_{K})$ can only be $\\{\delta_{k,n}\\}$-achievable,
if

$\displaystyle\theta_{k}\leq\sum_{\ell=1}^{k}\eta_{\ell}(R_{\ell}),\quad
k\in\\{1,\ldots,K\\}.$ (163)

###### Remark 6

The direct part of this theorem was proved in [29] for some choice of
admissible type-I error probabilities $\delta_{k,n}\to 0$, for all $k$. The
strong converse in this theorem thus establishes the optimal exponents for
arbitrary $K\geq 2$ and all sequences $\\{\delta_{k,n}\\}$ that satisfy (162)
and do not vanish too quickly.

###### Remark 7

For all permissible type-I error probabilities $\\{\delta_{k,n}\\}$ that
satisfy (162) and do not vanish too quickly, the set of achievable exponent-
tuples $(\theta_{1},\ldots,\theta_{K})$ form a hypercube, implying that all
decision centers, i.e., relays R${}_{1},\ldots,$ RK-1 and receiver RK, can
simultaneously achieve their optimal type-II error exponents. To prove the
desired converse result in Theorem 5, it thus suffices to show that the bound
in (163) holds in a setup where only the single decision center Rk takes a
decision.

###### Remark 8

When one allows for variable-length coding and only limits the expected sizes
of the message set but not its maximum sizes, then a tradeoff between the
different exponents $\theta_{1},\ldots,\theta_{K}$ arises [35]. Moreover, as
also shown in [35], in that case the set of all achievable exponent tuples
depends on the asymptotic values of the allowed type-I error probabilities.

###  VI-C Strong Converse Proof to Theorem 5

Let $\\{\delta_{k,n}\\}$ be sequences of allowed type-I error probabilities.
Fix a sequence (in $n$) of encoding and decision functions
$\\{(\phi_{0}^{(n)},\phi_{1}^{(n)},\ldots,\phi_{K-1}^{(n)},g_{1}^{(n)},\ldots,g_{K}^{(n)})\\}_{n\geq
1}$ satisfying (157) for $\\{\delta_{k,n}\\}$ and type-II error exponents
$\theta_{1},\ldots,\theta_{K}$.

Choose a sequence (in $n$) of small positive numbers $\\{\mu_{n}\\}$
satisfying

$\displaystyle\lim_{n\to\infty}\mu_{n}$ $\displaystyle=$ $\displaystyle 0$
(164) $\displaystyle\lim_{n\to\infty}\left(n\cdot\mu_{n}^{2}\right)^{-1}$
$\displaystyle=$ $\displaystyle 0.$ (165)

Fix now an arbitrary $k\in\\{1,\ldots,K\\}$ and a blocklength $n$, and let
$\mathcal{A}_{k}$ denote the acceptance region of Rk, i.e.,

$\mathcal{A}_{k}:=\\{(y_{0}^{n},\ldots,y_{k}^{n})\colon
g_{k}^{(n)}(y_{k}^{n},{m}_{k})=0\\},$ (166)

where we define recursively ${m}_{1}:=\phi_{0}^{(n)}(y_{0}^{n})$ and

${m}_{\ell}:=\phi_{\ell-1}^{(n)}(y_{\ell-1}^{n},{m}_{\ell-1}),\qquad\ell\in\\{2,\ldots,k\\}.$
(167)

Define also the intersection of this acceptance region with the typical set:

$\displaystyle\mathcal{D}_{k}\triangleq\mathcal{A}_{k}\cap\mathcal{T}_{\mu_{n}}^{(n)}(P_{Y_{0}\cdots
Y_{k}}).$ (168)

By [3, Remark to Lemma 2.12], the type-I error probability constraints in
(157a), and the union bound:

$\displaystyle\Delta_{k}:=P_{Y_{0}^{n}Y_{1}^{n}\cdots
Y_{k}^{n}}(\mathcal{D}_{k})$ $\displaystyle\geq$ $\displaystyle
1-\delta_{k,n}-{|{\mathcal{Y}_{0}}|\cdots|{\mathcal{Y}_{k}}|\over{{4\mu_{n}^{2}}n}},$
(169)

and thus

$\lim_{n\to\infty}\frac{1}{n}\log\Delta_{k}=0.$ (170)

Let $(\tilde{Y}_{0}^{n},\tilde{Y}_{1}^{n},\ldots,\tilde{Y}_{k}^{n})$ be random
variables of joint pmf

$\displaystyle
P_{\tilde{Y}_{0}^{n}\tilde{Y}_{1}^{n}\cdots\tilde{Y}_{k}^{n}}({y}_{0}^{n},{y}_{1}^{n},\ldots,{y}_{k}^{n})$
$\displaystyle=$
$\displaystyle\frac{P_{{Y}_{0}^{n}{Y}_{1}^{n}\cdots{Y}_{k}^{n}}({y}_{0}^{n},{y}_{1}^{n},\ldots,{y}_{k}^{n})}{\Delta_{k}}\cdot\mathds{1}\\{({y}_{0}^{n},{y}_{1}^{n},\ldots,{y}_{k}^{n})\in\mathcal{D}_{k}\\}.$

Let also
$\tilde{{M}}_{\ell}=\phi_{\ell-1}^{(n)}(\tilde{{M}}_{\ell-1},\tilde{Y}_{\ell-1}^{n})$
and $T$ be uniform over $\\{1,\ldots,n\\}$ independent of
$(\tilde{Y}_{0}^{n},\tilde{Y}_{1}^{n},\ldots,\tilde{Y}_{k}^{n},\tilde{{M}}_{1},\ldots,\tilde{{M}}_{k})$.

Notice that for any $\ell\in\\{1,\ldots,k\\}$:

$\displaystyle R_{\ell}$ $\displaystyle\geq$
$\displaystyle\frac{1}{n}H(\tilde{{M}}_{\ell})$ (172) $\displaystyle=$
$\displaystyle\frac{1}{n}I(\tilde{{M}}_{\ell};\tilde{Y}_{0}^{n}\cdots\tilde{Y}_{k}^{n})$
(173) $\displaystyle=$
$\displaystyle\frac{1}{n}H(\tilde{Y}_{0}^{n}\cdots\tilde{Y}_{k}^{n})-\frac{1}{n}H(\tilde{Y}_{0}^{n}\cdots\tilde{Y}_{k}^{n}|\tilde{{M}}_{\ell})$
(175) $\displaystyle=$ $\displaystyle
H(\tilde{Y}_{0,T}\cdots\tilde{Y}_{k,T})+o(1)$
$\displaystyle-\frac{1}{n}\sum_{t=1}^{n}H(\tilde{Y}_{0,t}\cdots\tilde{Y}_{k,t}|\tilde{{M}}_{\ell}\tilde{Y}_{0}^{t-1}\cdots\tilde{Y}_{k}^{t-1})$
$\displaystyle=$ $\displaystyle
H(\tilde{Y}_{0,T}\cdots\tilde{Y}_{k,T})+o(1)-H(\tilde{Y}_{0,T}\cdots\tilde{Y}_{k,T}|{U}_{\ell})$
(176) $\displaystyle=$ $\displaystyle
I(\tilde{Y}_{0,T}\cdots\tilde{Y}_{k,T};U_{\ell})+o(1)$ (177)
$\displaystyle\geq$ $\displaystyle I(\tilde{Y}_{\ell-1,T};U_{\ell})+o(1),$
(178)

where we defined
$U_{\ell}\triangleq(\tilde{{M}}_{\ell},\tilde{Y}_{0}^{T-1},\ldots,\tilde{Y}_{k}^{T-1},T)$.
Here, (175) holds by extending (11) to $k$-tuples.

We next upper bound the exponential decay of the type-II error probability.
Define:

$\displaystyle Q_{\tilde{{M}}_{k}}({m}_{k})$ $\displaystyle\triangleq$
$\displaystyle\sum_{y_{0}^{n},y_{1}^{n},\ldots,y_{k-1}^{n}}P_{\tilde{Y}_{0}^{n}}(y_{0}^{n})\cdots
P_{\tilde{Y}_{k-1}^{n}}(y_{k-1}^{n})$
$\displaystyle\quad\cdot\mathds{1}\\{{m}_{k}=\phi_{k}(\phi_{k-1}(\cdots(\phi_{1}(y_{0}^{n})\cdots)),y_{k-1}^{n})\\},$

and

$\displaystyle Q_{{{M}}_{k}}({m}_{k})$ $\displaystyle\triangleq$
$\displaystyle\sum_{y_{0}^{n},y_{1}^{n},\ldots,y_{k-1}^{n}}P_{{Y}_{0}^{n}}(y_{0}^{n})\cdots
P_{{Y}_{k-1}^{n}}(y_{k-1}^{n})$
$\displaystyle\;\;\cdot\mathds{1}\\{{m}_{k}=\phi_{k-1}(\phi_{k-2}(\cdots(\phi_{0}(y_{0}^{n})\cdots)),y_{k-1}^{n})\\},$

and notice that by (LABEL:eq:change):

$\displaystyle
Q_{\tilde{{M}}_{k}}P_{\tilde{Y}_{k}^{n}}\left({\mathcal{A}}_{k}\right)$
$\displaystyle\leq$ $\displaystyle
Q_{{{M}}_{k}}P_{{Y}_{k}^{n}}\left({\mathcal{A}}_{k}\right)\Delta_{k}^{-(k+1)}$
(181) $\displaystyle=$ $\displaystyle\beta_{k,n}\Delta_{k}^{-(k+1)}.$

Moreover, by (166), the probability
$P_{\tilde{{M}}_{k}\tilde{Y}_{k}^{n}}({\mathcal{A}}_{k})=1$, and thus

$D\left(P_{\tilde{{M}}_{k}\tilde{Y}_{k}^{n}}\left({\mathcal{A}}_{k}\right)\|Q_{\tilde{{M}}_{k}}P_{\tilde{Y}_{k}^{n}}\left({\mathcal{A}}_{k}\right)\right)=-\log\left(Q_{\tilde{{M}}_{k}}P_{\tilde{Y}_{k}^{n}}\left({\mathcal{A}}_{k}\right)\right),$
(182)

where on the left-hand side we slightly abused notation and mean the KL
divergence of the two binary pmfs induced by
$P_{\tilde{{M}}_{k}\tilde{Y}_{k}^{n}}\left({\mathcal{A}}_{k}\right)$ and
$1-P_{\tilde{{M}}_{k}\tilde{Y}_{k}^{n}}\left({\mathcal{A}}_{k}\right)$ and by
$Q_{\tilde{{M}}_{k}}P_{\tilde{Y}_{k}^{n}}\left({\mathcal{A}}_{k}\right)$ and
$1-Q_{\tilde{{M}}_{k}}P_{\tilde{Y}_{k}^{n}}\left({\mathcal{A}}_{k}\right)$.
Combined with (170), with (181), and with the data-processing inequality, we
obtain from (182):

$\displaystyle-{1\over n}\log\beta_{k,n}$ $\displaystyle\leq$
$\displaystyle-{1\over
n}\log\left(Q_{\tilde{{M}}_{k}}P_{\tilde{Y}_{k}^{n}}\left({\mathcal{A}}_{k}\right)\right)-\frac{(k+1)}{n}\log\Delta_{k}$
(184) $\displaystyle\leq$ $\displaystyle{1\over
n}D\left(P_{\tilde{{M}}_{k}\tilde{Y}_{k}^{n}}\Big{\|}Q_{\tilde{{M}}_{k}}P_{\tilde{Y}_{k}^{n}}\right)+o(1).$

We continue to upper bound the divergence term as

$\displaystyle{1\over
n}D(P_{\tilde{{M}}_{k}\tilde{Y}_{k}^{n}}||Q_{\tilde{{M}}_{k}}P_{\tilde{Y}_{k}^{n}})$
(185) $\displaystyle=$ $\displaystyle{1\over
n}I(\tilde{{M}}_{k};\tilde{Y}_{k}^{n})+{1\over
n}D(P_{\tilde{{M}}_{k}}||Q_{\tilde{{M}}_{k}})$ $\displaystyle\leq$
$\displaystyle{1\over n}I(\tilde{{M}}_{k};\tilde{Y}_{k}^{n})+{1\over
n}D(P_{\tilde{Y}_{k-1}^{n}\tilde{{M}}_{k-1}}||P_{\tilde{Y}_{k-1}^{n}}Q_{\tilde{{M}}_{k-1}})$
$\displaystyle\leq$ $\displaystyle{1\over
n}I(\tilde{{M}}_{k};\tilde{Y}_{k}^{n})+{1\over
n}I(\tilde{{M}}_{k-1};\tilde{Y}_{k-1}^{n})$
$\displaystyle\qquad\qquad\qquad+{1\over
n}D(P_{\tilde{Y}_{k-2}^{n}\tilde{{M}}_{k-2}}||P_{\tilde{Y}_{k-2}^{n}}Q_{\tilde{{M}}_{k-2}})$
$\displaystyle\vdots$ $\displaystyle\leq$ $\displaystyle{1\over
n}\sum_{\ell=1}^{k}I(\tilde{{M}}_{\ell};\tilde{Y}_{\ell}^{n})$ (188)
$\displaystyle\leq$ $\displaystyle{1\over
n}\sum_{\ell=1}^{k}\sum_{t=1}^{n}I(\tilde{{M}}_{\ell}\tilde{Y}_{0}^{t-1}\cdots\tilde{Y}_{k}^{t-1};\tilde{Y}_{\ell,t})$
(189) $\displaystyle\leq$
$\displaystyle\sum_{\ell=1}^{k}I(U_{\ell};\tilde{Y}_{\ell,T}).$ (190)

Here (VI-C) is obtained by the data processing inequality for KL-divergence
and (190) by the definition of ${U}_{\ell}$ and $T$.

Combined with (184), we obtain

$-{1\over
n}\log\beta_{k,n}\leq\sum_{\ell=1}^{k}I(U_{\ell};\tilde{Y}_{\ell,T})+o(1).$
(191)

Finally, we proceed to prove that for any $\ell\in\\{1,\ldots,k\\}$ the Markov
chain $U_{\ell}\to\tilde{Y}_{\ell-1,T}\to\tilde{Y}_{\ell,T}$ holds in the
limit as $n\to\infty$. We start by noticing the Markov chain
$\tilde{{M}}_{1}\to\tilde{Y}_{0}^{n}\to(\tilde{Y}_{1}^{n},\cdots,\tilde{Y}_{k}^{n})$,
and thus:

$\displaystyle 0$ $\displaystyle=$ $\displaystyle{1\over
n}I(\tilde{{M}}_{1};\tilde{Y}_{1}^{n}\cdots\tilde{Y}_{k}^{n}|\tilde{Y}_{0}^{n})$
(192) $\displaystyle=$ $\displaystyle{1\over
n}H(\tilde{Y}_{1}^{n}\cdots\tilde{Y}_{k}^{n}|\tilde{Y}_{0}^{n})-{1\over
n}H(\tilde{Y}_{1}^{n}\cdots\tilde{Y}_{k}^{n}|\tilde{Y}_{0}^{n}\tilde{{M}}_{1})$
(195) $\displaystyle=$ $\displaystyle
H(\tilde{Y}_{1,T}\cdots\tilde{Y}_{k,T}|\tilde{Y}_{0,T})+o(1)-{1\over
n}H(\tilde{Y}_{1}^{n}\cdots\tilde{Y}_{k}^{n}|\tilde{Y}_{0}^{n}\tilde{{M}}_{1})$
$\displaystyle\geq$ $\displaystyle
H(\tilde{Y}_{1,T}\cdots\tilde{Y}_{k,T}|\tilde{Y}_{0,T})+o(1)$
$\displaystyle-H(\tilde{Y}_{1,T}\cdots\tilde{Y}_{k,T}|\tilde{Y}_{0,T}\tilde{Y}_{0}^{T-1}\cdots\tilde{Y}_{k}^{T-1}\tilde{Y}_{0,T+1}^{n}\tilde{{M}}_{1}T)$
$\displaystyle\geq$ $\displaystyle
I(\tilde{Y}_{1,T}\cdots\tilde{Y}_{k,T};U_{1}|\tilde{Y}_{0,T})+o(1)\geq 0,$
(196)

where (LABEL:MC1proofstep2KHop) is obtained by extending (13) to multiple
random variables. We thus conclude that

$\lim_{n\to\infty}I(\tilde{Y}_{1,T}\cdots\tilde{Y}_{k,T};U_{1}|\tilde{Y}_{0,T})=0.$
(197)

Notice next that for any $\ell\in\\{2,\ldots,k\\}$:

$\displaystyle I(U_{\ell};\tilde{Y}_{\ell,T}|\tilde{Y}_{\ell-1,T})$
$\displaystyle\leq$ $\displaystyle
I(U_{\ell}\tilde{Y}_{0,T}\cdots\tilde{Y}_{\ell-2,T};\tilde{Y}_{\ell,T}|\tilde{Y}_{\ell-1,T})$
(199) $\displaystyle=$ $\displaystyle
I(U_{\ell};\tilde{Y}_{\ell,T}|\tilde{Y}_{0,T}\cdots\tilde{Y}_{\ell-1,T})$
$\displaystyle+I(\tilde{Y}_{0,T}\cdots\tilde{Y}_{\ell-2,T};\tilde{Y}_{\ell,T}|\tilde{Y}_{\ell-1,T})$
$\displaystyle=$ $\displaystyle
I(U_{\ell};\tilde{Y}_{\ell,T}|\tilde{Y}_{0,T}\cdots\tilde{Y}_{\ell-1,T})+o(1),$
(200)

where the last equality can be proved by extending (11) and (13) to multiple
random variables and by noting the factorization
$P_{Y_{0}}P_{Y_{1}|Y_{0}}\cdots P_{Y_{K}|Y_{K-1}}$.

Following similar steps to (192)–(196), we further obtain:

$\displaystyle 0$ $\displaystyle=$ $\displaystyle{1\over
n}I(\tilde{{M}}_{\ell};\tilde{Y}_{\ell}^{n}\cdots\tilde{Y}_{k}^{n}|\tilde{Y}_{0}^{n}\cdots\tilde{Y}_{\ell-1}^{n})$
$\displaystyle=$ $\displaystyle{1\over
n}H(\tilde{Y}_{\ell}^{n}\cdots\tilde{Y}_{k}^{n}|\tilde{Y}_{0}^{n}\cdots\tilde{Y}_{\ell-1}^{n})$
$\displaystyle-{1\over
n}H(\tilde{Y}_{\ell}^{n}\cdots\tilde{Y}_{k}^{n}|\tilde{Y}_{0}^{n}\cdots\tilde{Y}_{\ell-1}^{n}\tilde{{M}}_{\ell})$
$\displaystyle=$ $\displaystyle
H(\tilde{Y}_{\ell,T}\cdots\tilde{Y}_{k,T}|\tilde{Y}_{0,T}\cdots\tilde{Y}_{\ell-1,T})+o(1)$
$\displaystyle-{1\over
n}H(\tilde{Y}_{\ell}^{n}\cdots\tilde{Y}_{k}^{n}|\tilde{Y}_{0}^{n}\cdots\tilde{Y}_{\ell-1}^{n}\tilde{{M}}_{\ell})$
$\displaystyle\geq$ $\displaystyle
H(\tilde{Y}_{\ell,T}\cdots\tilde{Y}_{k,T}|\tilde{Y}_{0,T}\cdots\tilde{Y}_{\ell-1,T})+o(1)$
$\displaystyle-{1\over
n}\sum_{t=1}^{n}H(\tilde{Y}_{\ell,t}\cdots\tilde{Y}_{k,t}|\tilde{Y}_{0,t}\cdots\tilde{Y}_{\ell-1,t}\tilde{Y}_{0}^{t-1}\cdots\tilde{Y}_{k}^{t-1}\tilde{{M}}_{\ell})$
$\displaystyle=$ $\displaystyle
H(\tilde{Y}_{\ell,T}\cdots\tilde{Y}_{k,T}|\tilde{Y}_{0,T}\cdots\tilde{Y}_{\ell-1,T})+o(1)$
$\displaystyle-H(\tilde{Y}_{\ell,T}\cdots\tilde{Y}_{k,T}|\tilde{Y}_{0,T}\cdots\tilde{Y}_{\ell-1,T}\tilde{Y}_{0}^{T-1}\cdots\tilde{Y}_{k}^{T-1}\tilde{{M}}_{\ell}T)$
$\displaystyle=$ $\displaystyle
I(\tilde{Y}_{\ell,T}\cdots\tilde{Y}_{k,T};U_{\ell}|\tilde{Y}_{0,T}\cdots\tilde{Y}_{\ell-1,T})+o(1)$
(206) $\displaystyle\geq$ $\displaystyle
I(\tilde{Y}_{\ell,T};U_{\ell}|\tilde{Y}_{0,T}\cdots\tilde{Y}_{\ell-1,T})+o(1)\geq
0.$ (207)

We thus conclude that

$I(U_{\ell};\tilde{Y}_{\ell,T}|\tilde{Y}_{0,T}\cdots\tilde{Y}_{\ell-1,T})=o(1),$
(208)

which combined with (200) proves

$I(U_{\ell};\tilde{Y}_{\ell,T}|\tilde{Y}_{\ell-1,T})=o(1).$ (209)

The converse is then concluded by taking $n\to\infty$, as we explain in the
following. By Carathéodory’s theorem [34, Appendix C], for each $n$ there must
exist random variables ${U}_{1},\ldots,U_{k}$ satisfying (209), (191), and
(178) over alphabets of sizes

$\displaystyle|{\mathcal{U}}_{\ell}|$
$\displaystyle\leq|\mathcal{Y}_{\ell-1}|\cdot|\mathcal{Y}_{\ell}|+2,\qquad\ell\in\\{1,\ldots,k\\}.$
(210)

We thus restrict to random variables of above (bounded) supports and invoke
the Bolzano-Weierstrass theorem to conclude for each $\ell\in\\{1,\ldots,k\\}$
the existence of pmfs $P^{(\ell)}_{Y_{\ell-1}Y_{\ell}{U_{\ell}}}$ over
$\mathcal{Y}_{\ell-1}\times\mathcal{Y}_{\ell}\times{\mathcal{U}_{\ell}}$, also
abbreviated as $P^{(\ell)}$, and an increasing subsequence of positive numbers
$\\{n_{i}\\}_{i=1}^{\infty}$ satisfying

$\displaystyle\lim_{i\to\infty}P_{\tilde{Y}_{\ell-1}\tilde{Y}_{\ell}{U}_{\ell};n_{i}}$
$\displaystyle=$ $\displaystyle
P^{(\ell)}_{Y_{\ell-1}Y_{\ell}{U_{\ell}}},\quad\ell\in\\{1,\ldots,k\\},$ (211)

where $P_{\tilde{Y}_{\ell-1}\tilde{Y}_{\ell}{U}_{\ell};n_{i}}$ denotes the pmf
at blocklength $n_{i}$.

By the monotone continuity of mutual information for discrete random
variables, we can then deduce that

$\displaystyle R_{\ell}$ $\displaystyle\geq$ $\displaystyle
I_{P^{(\ell)}}({U}_{\ell};{Y}_{\ell-1}),\quad\ell\in\\{1,\ldots,k\\},$ (212)
$\displaystyle\theta_{k}$ $\displaystyle\leq$
$\displaystyle\sum_{\ell=1}^{k}I_{P^{(\ell)}}({U}_{\ell};{Y}_{\ell}),$ (213)

where the subscripts indicate that mutual informations should be computed
according to the indicated pmfs.

Since for any blocklength $n_{i}$ the pair
$\big{(}\tilde{Y}_{\ell-1}^{n_{i}},\tilde{Y}_{\ell}^{n_{i}}\big{)}$ lies in
the jointly typical set
$\mathcal{T}^{(n_{i})}_{\mu_{n_{i}}}(P_{Y_{\ell-1}Y_{\ell}})$, we have
$\big{|}P_{{Y}_{\ell-1}{Y}_{\ell};n_{i}}-P_{{Y_{\ell-1}}Y_{\ell}}\big{|}\leq\mu_{n_{i}}$
and thus the limiting pmfs satisfy
$P^{(\ell)}_{Y_{\ell-1}Y_{\ell}}=P_{Y_{\ell-1}Y_{\ell}}$. By similar
continuity considerations and by (209), for all $\ell\in\\{1,\ldots,k\\}$ the
Markov chain

$\displaystyle U_{\ell}\to Y_{\ell-1}\to Y_{\ell},$ (214)

holds under $P_{Y_{\ell-1}Y_{\ell}U_{\ell}}^{(\ell)}$. This concludes the
proof.

##  VII Conclusions and Outlook

This paper presented new strong converse proofs for source and channel coding
setups and for hypothesis testing. Most of the presented converses are
exponentially-strong converses and allow to conclude that the error
probabilities tend to 1 exponentially fast whenever the rates (or exponents)
violate certain conditions. The proofs for the standard almost lossless source
coding with side-information problem and for communication over discrete
memoryless channels (DMC) are solely based on change of measure arguments as
inspired by [22, 23, 11] and by asymptotic analysis of the distributions
implied by these changes of measure. Notice in particular that the restriction
to strongly-typical and conditionally strongly-typical sets allows to simplify
the proofs and circumvent additional arguments based on variational
characterizations as in [11]. The converse results for almost lossless source
coding and communication over DMC have been known for long, and our
contribution here is to present a simple alternative proof.

In contrast, our converse proofs for the $L$-round interactive compression and
the $K$-hop hypothesis testing setups are novel contributions in this article.
Only special cases had been reported previously. Our proofs for these setups
use similar change of measure arguments as in almost lossless source coding,
but additionally also rely on the proofs of Markov chains that hold in the
asymptotic regime of infinite blocklengths. These Markov chains are required
to conclude existence of the desired auxiliary random variables. Strong
converses of several special cases of our $L$-round interactive compression
had been reported previously, in particular see [11]. A strong converse proof
for the $2$-hop hypothesis testing setup was already presented in [31]; the
proof in [31] however does not apply to the case $\epsilon_{1}+\epsilon_{2}=1$
and seems more complex since it is based on the blowing-up lemma and
hypercontractivity arguments.

In related publications we have used the presented proof method to derive
fundamental limits of hypothesis testing systems under expected rate
constraints [35, 36] and (expected) secrecy constraints [37]. In contrast to
the results presented in this paper, the fundamental limits of distributed
hypothesis testing under these expectation constraints depend on the allowed
type-I error probabilities. It turns out that the proof technique based on
change of measure arguments as proposed in the present paper naturally
captures this dependence.

## Acknowledgement

The authors would like to thank R. Graczyk for useful discussions on the
strong converse proof for channel coding.

## References

  * [1] M. Hamad, M. Wigger, and M. Sarkiss, “Strong converses using change of measure and asymptotic Markov chains.” [Online]. Available: https://arxiv.org/, May 2022.
  * [2] J. Wolfowitz, “The coding of messages subject to chance errors,” Illinois Journal of Mathematics, vol. 1, no. 4, pp. 591 – 606, 1957.
  * [3] I. Csiszár and J. Körner, Information theory: coding theorems for discrete memoryless systems.  Cambridge University Press, 2011.
  * [4] K. Marton, “A simple proof of the blowing-up lemma,” IEEE Trans. Inf. Theory, vol. 32, pp. 445–446, May 1986.
  * [5] G. Dueck, “The strong converse coding theorem for the multiple-access channel,” Journal of Combinatorics, Information & System Sciences, vol. 6, no. 3, pp. 187–196, 1981.
  * [6] V. Strassen, “Asymptotische Abschätzungen in Shannons Informationstheorie,” (Prague, Czech Replublic), pp. 689–723, 962.
  * [7] H. V. P. Y. Polyanskiy and S. Verdú, “Channel coding rate in the finite blocklength regime,” IEEE Transactions on Information Theory, vol. 56, no. 5, pp. 2307–2359, 2010.
  * [8] R. Graczyk, “An elementary proof of the strong converse of the channel coding theorem.” Nov. 2022.
  * [9] S. L. Fong and V. Y. Tan, “A proof of the strong converse theorem for gaussian multiple access channels,” IEEE Transactions on Information Theory, vol. 62, no. 8, pp. 4376–4394, 2016.
  * [10] S. L. Fong and V. Y. Tan, “A proof of the strong converse theorem for gaussian broadcast channels via the gaussian poincaré inequality,” IEEE Transactions on Information Theory, vol. 63, no. 12, pp. 7737–7746, 2017.
  * [11] H. Tyagi and S. Watanabe, “Strong converse using change of measure arguments,” IEEE Trans. Inf. Theory, vol. 66, no. 2, pp. 689–703, 2019\.
  * [12] A. I. Khinchin, “The entropy concept in probability theory,” Usp. Mat. Nay, vol. 8, pp. 3–20, 1953.
  * [13] B. McMillan, “The basic theorems of information theory,” Ann. Math. Stat., vol. 24, pp. 196–219, 1953.
  * [14] I. Csiszár and G. Longo, “On error exponent for source coding and for testing simple statistical hypotheses,” Studia Sci. Math. Hungar., pp. 181–191, 1977.
  * [15] J. Körner, “Coding of an information source having ambiguous alphabet and the entropy of graphs,” in Transactions of the 6th Prague conference on Information Theory, etc., (Prague, Czech Republic), pp. 411–425, 1973.
  * [16] J. Kieffer, “Strong converses in source coding relative to a fidelity criterion,” IEEE Transactions on Information Theory, vol. 37, no. 2, pp. 257–262, 1991.
  * [17] D. Slepian and J. Wolf, “Noiseless coding of correlated information sources,” IEEE Transactions on Information Theory, vol. 19, no. 4, pp. 471–480, 1973\.
  * [18] A. Wyner and J. Ziv, “The rate-distortion function for source coding with side information at the decoder,” IEEE Transactions on Information Theory, vol. 22, no. 1, pp. 1–10, 1976.
  * [19] Y. Oohama and T. S. Han, “Universal coding for the slepian-wolf data compression system and the strong converse theorem,” IEEE Transactions on Information Theory, vol. 40, no. 6, pp. 1908–1919, 1994.
  * [20] Y. Oohama, “Exponential strong converse for source coding with side information at the decoder,” Entropy, vol. 20, no. 5, p. 352, 2018.
  * [21] Y. Oohama, “Exponential strong converse for one helper source coding problem,” Entropy, vol. 21, no. 6, p. 567, 2019.
  * [22] W. Gu and M. Effros, “A strong converse for a collection of network source coding problems,” in 2009 IEEE International Symposium on Information Theory, pp. 2316–2320, 2009.
  * [23] W. Gu and M. Effros, “A strong converse in source coding for super-source networks,” in 2011 IEEE International Symposium on Information Theory Proceedings, pp. 395–399, 2011.
  * [24] O. Kosut and J. Kliewer, “Strong converses are just edge removal properties,” IEEE Transactions on Information Theory, vol. 65, no. 6, pp. 3315–3339, 2018.
  * [25] A. Kaspi, “Two-way source coding with a fidelity criterion,” IEEE Transactions on Information Theory, vol. 31, no. 6, pp. 735–740, 1985.
  * [26] N. Ma and P. Ishwar, “Some results on distributed source coding for interactive function computation,” IEEE Transactions on Information Theory, vol. 57, no. 9, pp. 6180–6195, 2011.
  * [27] Y. Steinberg, “Coding and common reconstruction,” IEEE Transactions on Information Theory, vol. 55, no. 11, pp. 4995–5010, 2009.
  * [28] A. Lapidoth, A. Malär, and M. Wigger, “Constrained source-coding with side information,” IEEE Transactions on Information Theory, vol. 60, no. 6, pp. 3218–3237, 2014.
  * [29] S. Salehkalaibar, M. Wigger, and L. Wang, “Hypothesis testing in multi-hop networks.” [Online]. Available: https://arxiv.org/abs/1708.05198v1, 2017\.
  * [30] R. Ahlswede and I. Csiszár, “Hypothesis testing with communication constraints,” IEEE Trans. Inf. Theory, vol. 32, pp. 533–542, Jul. 1986\.
  * [31] D. Cao, L. Zhou, and V. Y. F. Tan, “Strong converse for hypothesis testing against independence over a two-hop network,” Entropy (Special Issue on Multiuser Information Theory II), vol. 21, Nov. 2019.
  * [32] J. Liu, R. Van Handel, and S. Verdú, “Beyond the blowing-up lemma: Sharp converses via reverse hypercontractivity,” in 2017 IEEE International Symposium on Information Theory (ISIT), pp. 943–947, IEEE, 2017.
  * [33] S. Sreekuma and D. Gündüz, “Strong converse for testing against independence over a noisy channel,” 2020.
  * [34] A. El Gamal and Y. H. Kim, Network Information Theory.  Cambridge University Press, 2011.
  * [35] M. Hamad, M. Wigger, and M. Sarkiss, “Multi-hop network with multiple decision centers under expected-rate constraints,” 2022.
  * [36] M. Hamad, M. Sarkiss, and M. Wigger, “Benefits of rate-sharing for distributed hypothesis testing,” in 2022 IEEE International Symposium on Information Theory (ISIT), pp. 2714–2719, 2022.
  * [37] S. Faour, M. Hamad, M. Sarkiss, and M. Wigger, “Testing against independence with an eavesdropper,” 2022.