Strong Converses Using Typical Changes of Measures and Asymptotic Markov Chains

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 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 new exponentially-strong converses for the K -hop hypothesis testing against independence problem with certain Markov chains and for the two-terminal L -round interactive compression problem with Jgeq 1 distortion constraints that depend on both sources and both reconstructions. For this latter problem, the exponentially-strong converse result states that whenever the rates lie outside the vanishing-excess-distortion-probability rate-region, then the sum of the J excess distortion probabilities asymptotically exceeds 1 or tends to 1 exponentially fast in the blocklength. (When the sum of the excess distortion probabilities exceeds 1, then a larger rate-distortion region is shown to be achievable.) The considered L -round J -distortion interactive source coding problem includes as special cases the Wyner-Ziv problem, the interactive function computation problem, and the compression with lossy common reconstruction problem. The new strong converse proofs for lossy compression and distributed hypothesis testing are derived using similar change of measure arguments as mentioned earlier and by additionally proving that certain Markov chains involving auxiliary random variables hold in the asymptotic regime of infinite blocklengths.