Strong Converses using Typical Changes of Measures and Asymptotic Markov Chains

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.

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.

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.

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.

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})$:

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

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

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.,

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$.

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

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

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