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$J\geq 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.

We study a distributed binary hypothesis testing (HT) problem with communication and security constraints, involving three parties: a remote sensor called Alice, a legitimate decision center called Bob, and an eavesdropper called Eve, all having their own source observations. In this system, Alice conveys a rate-R description of her observations to Bob, and Bob performs a binary hypothesis test on the joint distribution underlying his and Alice’s observations. The goal of Alice and Bob is to maximize the exponential decay of Bob’s miss-detection (type-II error) probability under two constraints: Bob’s false-alarm (type-I error) probability has to stay below a given threshold and Eve’s uncertainty (equivocation) about Alice’s observations should stay above a given security threshold even when Eve learns Alice’s message. For the special case of testing against independence, we characterize the largest possible type-II error exponent under the described type-I error probability and security constraints.

We consider a multi-hop distributed hypothesis testing problem with multiple decision centers (DCs) for testing against independence and where the observations obey some Markov chain. For this system, we characterize the fundamental type-II error exponents region, i.e., the type-II error exponents that the various DCs can achieve simultaneously, under expected rate-constraints. Our results show that this fundamental exponents region is boosted compared to the region under maximum-rate constraints, and that it depends on the permissible type-I error probabilities. When all DCs have equal permissible type-I error probabilities, the exponents region is rectangular and all DCs can simultaneously achieve their optimal type-II error exponents. When the DCs have different permissible type-I error probabilities, a tradeoff between the type-II error exponents at the different DCs arises. New achievability and converse proofs are presented. For the achievability, a new multiplexing and rate-sharing strategy is proposed. The converse proof is based on applying different change of measure arguments in parallel and on proving asymptotic Markov chains. For the special casesK∈ {2, 3}, and for arbitraryK≥ 2 when all permissible type-I error probabilities at the various DCs are equal, we provide simplified expressions for the exponents region; a similar simplification is conjectured for the general case.

We study distributed binary hypothesis testing with a single sensor and two remote decision centers that are also equipped with local sensors. The communication between the sensor and the two decision centers takes place over three links: a shared link to both centers and an individual link to each of the two centers. All communication links are subject to expected rate constraints. This paper characterizes the optimal exponents region of the type-II error for given type-I error thresholds at the two decision centers and further simplifies the expressions in the special case of having only the single shared link. The exponents region illustrates a gain under expected rate constraints compared to equivalent maximum rate constraints. Moreover, it exhibits a tradeoff between the exponents achieved at the two centers.

The main contribution of this paper is a strong converse result for K-hop distributed hypothesis testing against independence with multiple (intermediate) decision centers under a Markov condition. Our result shows that the set of type-II error exponents that can simultaneously be achieved at all the terminals does not depend on the maximum permissible type-I error probabilities. Our strong converse proof is based on a change of measure argument and on the asymptotic proof of specific Markov chains. This proof method seems to be useful also in other applications, and is appealing because it does not require resorting to variational characterizations or blowing-up methods as in previous related proofs.

The paper studies distributed binary hypothesis testing over a two-hop relay network where both the relay and the receiver decide on the hypothesis. Both communication links are subject to expected rate constraints, which differs from the classical assumption of maximum rate constraints. We exactly characterize the set of type-II error exponent pairs at the relay and the receiver when both type-I error probabilities are constrained by the same value$\epsilon > 0$. No tradeoff is observed between the two exponents, i.e., one can simultaneously attain maximum type-II error exponents both at the relay and at the receiver. For$\epsilon_{1}\neq\epsilon_{2}$, we present an achievable exponents region, which we obtain with a scheme that applies different versions of a basic two-hop scheme that is optimal under maximum rate constraints. We use the basic two-hop scheme with two choices of parameters and rates, depending on the transmitter's observed sequence. For$\epsilon_{1}=\epsilon_{2}$, a single choice is shown to be sufficient. Numerical simulations indicate that extending to three or more parameter choices is never beneficial.

Cascaded binary hypothesis testing is studied in this paper with two decision centers at the relay and the receiver. All terminals have their own observations, where we assume that the observations at the transmitter, the relay, and the receiver form a Markov chain in this order. The communication occurs over two hops, from the transmitter to the relay, and from the relay to the receiver. Expected rate constraints are imposed on both communication links. In this work, we characterize the optimal type-II error exponents at the two decision centers under constraints on the allowed type-I error probabilities. Our recent work characterized the optimal type-II error exponents in the special case when the two decision centers have same type-I error constraints and provided an achievability scheme for the general setup. To obtain the exact characterization for the general case, in this paper we provide a new converse proof as well as a new matching achievability scheme. Our results indicate that under unequal type-I error constraints at the relay and the receiver, a tradeoff arises between the maximum type-II error probabilities at these two terminals. Previous results showed that such a tradeoff does not exist under equal type-I error constraints or under general type-I error constraints when a maximum rate constraint is imposed on the communication links.

We investigate the testing-against-independence problem over a cooperative MAC with two sensors and a single detector under an average rate constraint on the sensors-detector links. For this setup, we design a variable-length coding scheme that maximizes the achievable type-II error exponent when the type-I error probability is limited to ϵ. Similarly to the single-link result, we show here that the optimal error exponent depends on ϵ and that variable-length coding allows to increase the rates over the optimal fixed-length coding scheme by the factor (1 − ϵ)−1.