Search

A central challenge in hypothesis testing (HT) lies in determining the optimal balance between Type I (false positive) and Type II (non-detection or false negative) error probabilities. Analyzing these errors' exponential rate of convergence, known as error exponents, provides crucial insights into system performance. Error exponents offer a lens through which we can understand how operational restrictions, such as resource constraints and impairments in communications, affect the accuracy of distributed inference in networked systems. This survey presents a comprehensive review of key results in HT, from the foundational Stein's Lemma to recent advancements in distributed HT, all unified through the framework of error exponents. We explore asymptotic and non-asymptotic results, highlighting their implications for designing robust and efficient networked systems, such as event detection through lossy wireless sensor monitoring networks, collective perception-based object detection in vehicular environments, and clock synchronization in distributed environments, among others. We show that understanding the role of error exponents provides a valuable tool for optimizing decision-making and improving the reliability of networked systems. [ABSTRACT FROM AUTHOR]

A central challenge in hypothesis testing (HT) lies in determining the optimal balance between Type I (false positive) and Type II (non-detection or false negative) error probabilities. Analyzing these errors’ exponential rate of convergence, known as error exponents, provides crucial insights into system performance. Error exponents offer a lens through which we can understand how operational restrictions, such as resource constraints and impairments in communications, affect the accuracy of distributed inference in networked systems. This survey presents a comprehensive review of key results in HT, from the foundational Stein’s Lemma to recent advancements in distributed HT, all unified through the framework of error exponents. We explore asymptotic and non-asymptotic results, highlighting their implications for designing robust and efficient networked systems, such as event detection through lossy wireless sensor monitoring networks, collective perception-based object detection in vehicular environments, and clock synchronization in distributed environments, among others. We show that understanding the role of error exponents provides a valuable tool for optimizing decision-making and improving the reliability of networked systems.

The error probability of block codes sent under a non-uniform input distribution over the memoryless binary symmetric channel (BSC) and decoded via the maximum a posteriori (MAP) decoding rule is investigated. It is proved that the ratio of the probability of MAP decoder ties to the probability of error grows most linearly in blocklength when no MAP decoding ties occur, thus showing that decoder ties do not affect the code's error exponent. This result generalizes a similar recent result shown for the case of block codes transmitted over the BSC under a uniform input distribution. [ABSTRACT FROM AUTHOR]

We consider the classical Neymann–Pearson hypothesis testing problem of signal detection, where under the null hypothesis (${\mathcal{ H}}_{0}$), the received signal is white Gaussian noise, and under the alternative hypothesis (${\mathcal{ H}}_{1}$), the received signal includes also an additional non–Gaussian random signal, which in turn can be viewed as a deterministic waveform plus zero–mean, non-Gaussian noise. However, instead of the classical likelihood ratio test detector, which might be difficult to implement, in general, we impose a (mismatched) correlation detector, which is relatively easy to implement, and we characterize the optimal correlator weights in the sense of the best trade-off between the false-alarm error exponent and the missed-detection error exponent. Those optimal correlator weights depend (non-linearly, in general) on the underlying deterministic waveform under ${\mathcal{ H}}_{1}$. We then assume that the deterministic waveform may also be free to be optimized (subject to a power constraint), jointly with the correlator, and show that both the optimal waveform and the optimal correlator weights may take on values in a small finite set of typically no more than two to four levels, depending on the distribution of the non-Gaussian noise component. Finally, we outline an extension of the scope to a wider class of detectors that are based on linear combinations of the correlation and the energy of the received signal. [ABSTRACT FROM AUTHOR]

In this paper, we establish an interesting duality between two different quantum information-processing tasks, namely, classical source coding with quantum side information, and channel coding over classical-quantum channels. The duality relates the optimal error exponents of these two tasks, generalizing the classical results of Ahlswede and Dueck [IEEE Trans. Inf. Theory, 28(3):430–443, 1982]. We establish duality both at the operational level and at the level of the entropic quantities characterizing these exponents. For the latter, the duality is given by an exact relation, whereas for the former, duality manifests itself in the following sense: an optimal coding strategy for one task can be used to construct an optimal coding strategy for the other task. Along the way, we derive a bound on the error exponent for classical-quantum channel coding with constant composition codes which might be of independent interest. Finally, we consider the task of variable-length classical compression with quantum side information, and a duality relation between this task and classical-quantum channel coding can also be established correspondingly. Furthermore, we study the strong converse of this task, and show that the strong converse property does not hold even in the i.i.d. scenario. [ABSTRACT FROM AUTHOR]

The DNA storage channel is considered, in which a codeword is comprised of $M$ unordered DNA molecules. At reading time, $N$ molecules are sampled with replacement, and then each molecule is sequenced. A coded-index concatenated-coding scheme is considered, in which the $m$ th molecule of the codeword is restricted to a subset of all possible molecules (an inner code), which is unique for each $m$. The decoder has low-complexity, and is based on first decoding each molecule separately (the inner code), and then decoding the sequence of molecules (an outer code). Only mild assumptions are made on the sequencing channel, in the form of the existence of an inner code and decoder with vanishing error. The error probability of a random code as well as an expurgated code is analyzed and shown to decay exponentially with $N$. This establishes the importance of increasing the coverage depth $N/M$ in order to obtain low error probability. [ABSTRACT FROM AUTHOR]

We consider the problem of detecting (testing) Gaussian stochastic sequences (signals) with imprecisely known means and covariance matrices. An alternative is independent identically distributed zero-mean Gaussian random variables with unit variances. For a given false alarm (1st-kind error) probability, the quality of minimax detection is given by the best miss probability (2nd-kind error probability) exponent over a growing observation horizon. We study the maximal set of means and covariance matrices (composite hypothesis) such that its minimax testing can be replaced with testing a single particular pair consisting of a mean and a covariance matrix (simple hypothesis) without degrading the detection exponent. We completely describe this maximal set. [ABSTRACT FROM AUTHOR]

We revisit the outlier hypothesis testing framework of Li et al. (TIT 2014) and derive fundamental limits for the optimal test under the generalized Neyman-Pearson criterion. In outlier hypothesis testing, one is given multiple observed sequences, where most sequences are generated i.i.d. from a nominal distribution. The task is to discern the set of outlying sequences that are generated from anomalous distributions. The nominal and anomalous distributions are unknown. We study the tradeoff among the probabilities of misclassification error, false alarm and false reject for tests that satisfy weak conditions on the rate of decrease of these error probabilities as a function of sequence length. Specifically, we propose a threshold-based test that ensures exponential decay of misclassification error and false alarm probabilities. We study two constraints on the false reject probability, with one constraint being that it is a non-vanishing constant and the other being that it has an exponential decay rate. For both cases, we characterize bounds on the false reject probability, as a function of the threshold, for each pair of nominal and anomalous distributions and demonstrate the optimality of our test under the generalized Neyman-Pearson criterion. We first consider the case of at most one outlying sequence and then generalize our results to the case of multiple outlying sequences where the number of outlying sequences is unknown and each outlying sequence can follow a different anomalous distribution. [ABSTRACT FROM AUTHOR]

The generalized Poor-Verdú error lower bound established by Chang et al. (2020) for multihypothesis testing is studied in the classical channel coding context. It is proved that for any sequence of block codes sent over the memoryless binary symmetric channel (BSC), the minimum probability of error (under maximum likelihood decoding) has a relative deviation from the generalized bound that grows at most linearly in blocklength. This result directly implies that for arbitrary codes used over the BSC, decoder ties can only affect the subexponential behavior of the minimum probability of error. [ABSTRACT FROM AUTHOR]

We consider a binary classification problem for a test sequence to determine from which source the sequence is generated. The system classifies the test sequence based on empirically observed (training) sequences obtained from unknown sources P 1 and P 2 . We analyze the asymptotic fundamental limits of statistical classification for sources with multiple subclasses. We investigate the first- and second-order maximum error exponents under the constraint that the type-I error probability for all pairs of distributions decays exponentially fast and the type-II error probability is upper bounded by a small constant. In this paper, we first give a classifier which achieves the asymptotically maximum error exponent in the class of deterministic classifiers for sources with multiple subclasses, and then provide a characterization of the first-order error exponent. We next provide a characterization of the second-order error exponent in the case where only P 2 has multiple subclasses but P 1 does not. We generalize our results to classification in the case that P 1 and P 2 are a stationary and memoryless source and a mixed memoryless source with general mixture, respectively. [ABSTRACT FROM AUTHOR]

In this paper, the error exponent of a polar code generator matrix for data rate enhancement between two users is investigated. A new expression for optimal correlation coefficient between the error probability of the main and eavesdropper channel in Wyner's wiretap channel model introduced. By using this optimal correlation coefficient, a relationship between code length and the error exponent is defined. Moreover, to investigate the performance of the proposed formulation, an optimization based on Arikan and Korda's theory on the maximum value of the error exponent was conducted. It is shown that the new correlation coefficients significantly increase the decoding error probability in the wiretapper side for both of the theories. In addition, the Bhattacharyya parameter was also defined for the wiretap channel. Finally, by applying the optimized values to a binary erasure channel, the error probability for each scenario is calculated. [ABSTRACT FROM AUTHOR]

We consider the problem of (almost) lossless separate encodings and joint decoding of two correlated discrete memoryless sources (DMSs), that is, the well-known Slepian-Wolf (S-W) source coding problem. Traditionally, ensembles of S–W codes are defined such that every bin of each $n$ –vector of each source is randomly drawn under the uniform distribution across the sets $\{0,1,\ldots,2^{nR_{X}}-1\}$ and $\{0,1,\ldots,2^{nR_{Y}}-1\}$ , where $R_{X}$ and $R_{Y}$ are the coding rates of the two sources, $X$ and $Y$ , respectively. In a few more recent works, where only one source, say, $X$ , is compressed and the other one, $Y$ , serves as side information available at the decoder, the scope is extended to variable–rate S–W (VRSW) codes, where the rate is allowed to depend on the type class of the source string, but still, the random–binning distribution is assumed uniform within the corresponding, type–dependent, bin index set. In this expository work, we investigate the role of the uniformity of the random binning distribution from the perspective of the trade-off between the reliability (defined in terms of the error exponent) and the compression performance (measured from the viewpoint of the source coding exponent). To this end, we study a much wider class of random–binning distributions, which includes the ensemble of VRSW codes as a special case, but it also goes considerably beyond. We first show that, with the exception of some pathological cases, the smaller ensemble, of VRSW codes, is as good as the larger ensemble in terms the trade-off between the error exponent and the source coding exponent. Notwithstanding this finding, the wider class of ensembles proposed is motivated in two ways. The first is that it outperforms VRSW codes in the above–mentioned pathological cases, and the second is that it allows robustness: in the event of a system failure that causes unavailability of the compressed bit–stream from one of the sources, it still allows reconstruction of the other source within some controllable distortion. [ABSTRACT FROM AUTHOR]

We consider a point–to–point communication system, where in addition to the encoder and the decoder, there is a helper that observes non–causally the realization of the noise vector and provides a (lossy) rate– $ {R}_{{ \text { h}}}$ description of it to the encoder ($ {R}_{{ \text { h}}} < \infty $). In continuation to Lapidoth and Marti (2020), who derived the capacity of this model, here our focus is on error exponents. We consider both continuous–alphabet, additive white Gaussian channels and finite–alphabet, modulo–additive channels, and for each one of them, we study the cases of both fixed–rate and variable–rate noise descriptions by the helper. Our main finding is that, as long as the channel–coding rate, R, is below the helper–rate, $ {R}_{{ \text { h}}}$ , the achievable error exponent is unlimited (i.e., it can be made arbitrarily large), and in some of the cases, it is even strictly infinite (i.e., the error probability can be made strictly zero). However, in the range of coding rates $({R}_{{ \text { h}}}, {R}_{{ \text { h}}}+ {C}_{0})$ , C0 being the ordinary channel capacity (without help), the best achievable error exponent is finite and strictly positive, although there is a certain gap between our upper bound (converse bound) and lower bound (achievability) on the highest achievable error exponent. This means that the model of encoder–assisted communication is essentially equivalent to a model, where in addition to the noisy channel between the encoder and decoder, there is also a parallel noiseless bit–pipe of capacity $ {R}_{{ \text { h}}}$. We also extend the scope to the Gaussian multiple access channel (MAC) and characterize the rate sub–region, where the achievable error exponent is unlimited or even infinite. [ABSTRACT FROM AUTHOR]

This paper investigates a novel offline change-point detection problem from an information-theoretic perspective. In contrast to most related works, we assume that the knowledge of the underlying pre- and post-change distributions are not known and can only be learned from the training sequences which are available. We further require the probability of the estimation error to decay either exponentially or sub-exponentially fast (corresponding respectively to the large and moderate deviations regimes in information theory parlance). Based on the training sequences as well as the test sequence consisting of a single change-point, we design a change-point estimator and further show that this estimator is optimal by establishing matching (strong) converses. This leads to a full characterization of the optimal confidence width (i.e., half the width of the confidence interval within which the true change-point is located at with high probability) as a function of the undetected error, under both the large and moderate deviations regimes. [ABSTRACT FROM AUTHOR]

The bee identification problem is a problem of properly recognizing a massive amount of data (a numerous amount of bees in a beehive, for example) which have been mixed and corrupted by noise. We derive various error exponents in the bee identification problem under two different decoding rules. Under naïve decoding, which decodes each bee independently of the others, we analyze a general discrete memoryless channel and a relatively wide family of stochastic decoders. Upper and lower bounds to the random coding error exponent are derived and proved to be equal at relatively high coding rates. Then, we propose a lower bound on the error exponent of the typical random code, which improves upon the random coding exponent at low coding rates. We also derive a third bound, which is related to expurgated codes, which turns out to be strictly higher than the other bounds, also at relatively low rates. We show that the universal maximum mutual information decoder is optimal with respect to the typical random code and the expurgated code. Moving further, we derive error exponents under optimal decoding, the relatively wide family of symmetric channels, and the maximum likelihood decoder. We first propose a random coding lower bound, and then, an improved bound which stems from an expurgation process. We show numerically that our second bound strictly improves upon the random coding bound at an intermediate range of coding rates, where a bound derived in a previous work no longer holds. [ABSTRACT FROM AUTHOR]

Motivated by modern applications of light detection and ranging (LIDAR), we study the model of an optical receiver based on an avalanche photo-diode (APD), followed by electronic circuitry for detection of reflected optical signals and estimation of their delay. This model is known to be quite complicated as it consists of at least three different types of noise: thermal noise, shot noise, and multiplicative noise (excess noise) that stems from the random gain associated with the photo-multiplication of the APD. Consequently, the derivation of the optimal likelihood ratio test (LRT) associated with signal detection is a non–trivial task, which has no apparent exact closed–form solution. We consider instead a class of relatively simple detectors, that are based on correlating the noisy received signal with a given deterministic waveform, and our purpose is to characterize the optimal waveform in the sense of the best tradeoff between the false–alarm (FA) error exponent and the missed–detection (MD) error exponent. In the same spirit, we also study the problem of estimating the delay on the basis of maximizing the correlation between the received signal and a time–shifted waveform, as a function of this time shift. We characterize the optimal correlator waveform that minimizes the mean square error (MSE) in the regime of high signal–to–noise ratio (SNR). The optimal correlator waveforms for detection and for estimation turn out to be different, but their limiting behavior is the same: when the thermal Gaussian noise is dominant, the optimal correlator waveform becomes proportional to the clean signal, but when the thermal noise is negligible compared to the other noises, then it becomes a logarithmic function of the clean signal, as expected. [ABSTRACT FROM AUTHOR]

We consider the detection problem for Gaussian stochastic sequences (signals) with unknown covariance matrices in white Gaussian noise. For a given false alarm probability (1st-kind error probability), the quality of minimax detection is given by the best miss probability (2nd-kind error probability) exponent over a growing observation interval. The goal is finding the largest set of covariance matrices (composite hypothesis) such that its minimax testing can be replaced with testing a single particular covariance matrix (simple hypothesis) with no degradation of the detection exponent. We completely describe this maximal set of covariance matrices. We also consider some consequences concerning minimax detection of Gaussian stochastic signals against Gaussian white noise and detection of Gaussian stationary signals. [ABSTRACT FROM AUTHOR]

We consider the problem of (almost) lossless source coding of two correlated memoryless sources using separate encoders and a joint decoder, that is, Slepian-Wolf (S-W) coding. In our setting, the encoding and decoding are asynchronous, i.e., there is a certain relative delay between the two sources. Neither the source parameters nor the relative delay are known to the encoders and the decoder. Since we assume that both encoders implement standard random binning, which does not require such knowledge anyway, the focus of this work is on the decoder. Our main contribution is in proposing a universal decoder, that independent of the unknown source parameters and the relative delay, and at the same time, is asymptotically as good as the optimal maximum a posteriori probability (MAP) decoder in the sense of the random coding error exponent achieved. Consequently, the achievable rate region is also the same as if the source parameters and the delay were known to the decoder. [ABSTRACT FROM AUTHOR]

We characterize the asymptotic performance of nonparametric one- and two-sample testing. The exponential decay rate or error exponent of the type-II error probability is used as the asymptotic performance metric, and an optimal test achieves the maximum rate subject to a constant level constraint on the type-I error probability. With Sanov’s theorem, we derive a sufficient condition for one-sample tests to achieve the optimal error exponent in the universal setting, i.e., for any distribution defining the alternative hypothesis. We then show that two classes of Maximum Mean Discrepancy (MMD) based tests attain the optimal type-II error exponent on $\mathbb R^{d}$ , while the quadratic-time Kernel Stein Discrepancy (KSD) based tests achieve this optimality with an asymptotic level constraint. For general two-sample testing, however, Sanov’s theorem is insufficient to obtain a similar sufficient condition. We proceed to establish an extended version of Sanov’s theorem and derive an exact error exponent for the quadratic-time MMD based two-sample tests. The obtained error exponent is further shown to be optimal among all two-sample tests satisfying a given level constraint. Our work hence provides an achievability result for optimal nonparametric one- and two-sample testing in the universal setting. Application to off-line change detection and related issues are also discussed. [ABSTRACT FROM AUTHOR]

The Hirschfeld-Gebelein–Rényi (HGR) maximal correlation and the corresponding functions have been shown useful in many machine learning scenarios. In this paper, we study the sample complexity of estimating the HGR maximal correlation functions by the alternating conditional expectation (ACE) algorithm using training samples from large datasets. Specifically, we develop a mathematical framework to characterize the learning errors between the maximal correlation functions computed from the true distribution, and the functions estimated from the ACE algorithm. For both supervised and semi-supervised learning scenarios, we establish the analytical expressions for the error exponents of the learning errors. Furthermore, we demonstrate that for large datasets, the upper bounds for the sample complexity of learning the HGR maximal correlation functions by the ACE algorithm can be expressed using the established error exponents. Moreover, with our theoretical results, we investigate the sampling strategy for different types of samples in semi-supervised learning with a total sampling budget constraint, and an optimal sampling strategy is developed to maximize the error exponent of the learning error. Finally, the numerical simulations are presented to support our theoretical results. [ABSTRACT FROM AUTHOR]

We consider a binary classification problem for a test sequence to determine from which source the sequence is generated. The system classifies the test sequence based on empirically observed (training) sequences obtained from unknown sources P1 and P2. We analyze the asymptotic fundamental limits of statistical classification for sources with multiple subclasses. We investigate the first- and second-order maximum error exponents under the constraint that the type-I error probability for all pairs of distributions decays exponentially fast and the type-II error probability is upper bounded by a small constant. In this paper, we first give a classifier which achieves the asymptotically maximum error exponent in the class of deterministic classifiers for sources with multiple subclasses, and then provide a characterization of the first-order error exponent. We next provide a characterization of the second-order error exponent in the case where only P2 has multiple subclasses but P1 does not. We generalize our results to classification in the case that P1 and P2 are a stationary and memoryless source and a mixed memoryless source with general mixture, respectively.

A central problem in Binary Hypothesis Testing (BHT) is to determine the optimal tradeoff between the Type I error (referred to as false alarm) and Type II (referred to as miss) error. In this context, the exponential rate of convergence of the optimal miss error probability — as the sample size tends to infinity — given some (positive) restrictions on the false alarm probabilities is a fundamental question to address in theory. Considering the more realistic context of a BHT with a finite number of observations, this letter presents a new non-asymptotic result for the scenario with monotonic (sub-exponential decreasing) restriction on the Type I error probability, which extends the result presented by Strassen in 2009. Building on the use of concentration inequalities, we offer new upper and lower bounds to the optimal Type II error probability for the case of finite observations. Finally, the derived bounds are evaluated and interpreted numerically (as a function of the number samples) for some vanishing Type I error restrictions. [ABSTRACT FROM AUTHOR]

A single-sensor two-detectors system is considered where the sensor communicates with both detectors and Detector 1 communicates with Detector 2, all over noise-free rate-limited links. The sensor and both detectors observe discrete memoryless source sequences whose joint probability mass function depends on a binary hypothesis. The goal at each detector is to guess the binary hypothesis in a way that, for increasing observation lengths, the probability of error under one of the hypotheses decays to zero with largest possible exponential decay, whereas the probability of error under the other hypothesis can decay to zero or to a small positive number arbitrarily slow. For the setting with positive communication rates from the sensor to the detectors and when both detectors are interested in maximizing the error exponent under the same hypothesis, we characterize the set of all possible exponents in a special case of testing against independence. In this case the cooperation link allows Detector 2 to increase its Type-II error exponent by an amount that is equal to the exponent attained at Detector 1. We also provide a general inner bound on the set of achievable error exponents that shows a tradeoff between the exponents at the two detectors in most cases. When the two detectors aim at maximizing the error exponent under different hypotheses and the distribution at the Sensor is different under the two hypotheses, then we show that such a tradeoff does not exist. We propose a general scheme that allows each detector to attain the same exponent as if it was the only detector in the system. For the setting with zero-rate communication on both links, we exactly characterize the set of possible exponents and the gain brought up by cooperation, in function of the number of bits that are sent over the two links. Notice that, for this setting, tradeoffs between the exponents achieved at the two detectors arise only in few particular cases. In all other cases, each detector achieves the same performance as if it were the only detector in the system. [ABSTRACT FROM AUTHOR]

The “bee-identification problem” was formally defined by Tandon, Tan and Varshney [IEEE Trans. Commun., vol. 67, 2019], and the error exponent was studied. This work extends the results for the “absentee bees” scenario, where a fraction of the bees are absent in the beehive image used for identification. For this setting, we present an exact characterization of the bee-identification error exponent, and show that independent barcode decoding is optimal, i.e., joint decoding of the bee barcodes does not result in a better error exponent relative to independent decoding of each noisy barcode. This is in contrast to the result without absentee bees, where joint barcode decoding results in a significantly higher error exponent than independent barcode decoding. We also define and characterize the ‘capacity’ for the bee-identification problem with absentee bees, and prove a strong converse for the same. [ABSTRACT FROM AUTHOR]

This work studies the deviations of the error exponent of the constant composition code ensemble around its expectation, known as the error exponent of the typical random code (TRC). In particular, it is shown that the probability of randomly drawing a codebook whose error exponent is smaller than the TRC exponent is exponentially small; upper and lower bounds for this exponent are given, which coincide in some cases. In addition, the probability of randomly drawing a codebook whose error exponent is larger than the TRC exponent is shown to be double–exponentially small; upper and lower bounds to the double–exponential exponent are given. The results suggest that codebooks whose error exponent is larger than the error exponent of the TRC are extremely rare. The key ingredient in the proofs is a new large deviations result of type class enumerators with dependent variables. [ABSTRACT FROM AUTHOR]

It is well known that for the discrimination of classical and quantum channels in the finite, non-asymptotic regime, adaptive strategies can give an advantage over non-adaptive strategies. However, Hayashi (IEEE Trans Inf Theory 55(8):3807–3820, 2009. arXiv:0804.0686) showed that in the asymptotic regime, the exponential error rate for the discrimination of classical channels is not improved in the adaptive setting. We extend this result in several ways. First, we establish the strong Stein's lemma for classical–quantum channels by showing that asymptotically the exponential error rate for classical–quantum channel discrimination is not improved by adaptive strategies. Second, we recover many other classes of channels for which adaptive strategies do not lead to an asymptotic advantage. Third, we give various converse bounds on the power of adaptive protocols for general asymptotic quantum channel discrimination. Intriguingly, it remains open whether adaptive protocols can improve the exponential error rate for quantum channel discrimination in the asymmetric Stein setting. Our proofs are based on the concept of amortized distinguishability of quantum channels, which we analyse using data-processing inequalities. [ABSTRACT FROM AUTHOR]

Sphere packing bounds (SPBs)—with prefactors that are polynomial in the block length—are derived for codes on two families of memoryless channels using Augustin's method: (possibly nonstationary) memoryless channels with (possibly multiple) additive cost constraints and stationary memoryless channels with convex constraints on the composition (i.e., empirical distribution, type) of the input codewords. A variant of Gallager's bound is derived in order to show that these sphere packing bounds are tight in terms of the exponential decay rate of the error probability with the block length under mild hypotheses. [ABSTRACT FROM AUTHOR]

A Lagrange–dual (Gallager–style) lower bound is derived for the error exponent function of the typical random code (TRC) pertaining to the i.i.d. random coding ensemble and mismatched stochastic likelihood decoding. While the original expression, derived from the method of types (the Csiszár–style expression) involves minimization over probability distributions defined on the channel input–output alphabets, the new Lagrange–dual formula involves optimization of five parameters, independently of the alphabet sizes. For both stochastic and deterministic mismatched decoding (including maximum likelihood decoding as a special case), we provide a rather comprehensive discussion on the insight behind the various ingredients of this formula and describe how its behavior varies as the coding rate exhausts the relevant range. Among other things, it is demonstrated that this expression simultaneously generalizes both the expurgated error exponent function (at zero rate) and the classical random coding exponent function at high rates, where it also meets the sphere–packing bound. [ABSTRACT FROM AUTHOR]

We study the exact, non-deterministic conversion of multipartite pure quantum states into one-another via local operations and classical communication (LOCC) and asymptotic entanglement transformation under such channels. In particular, we consider the maximal number of copies of any given target state that can be extracted exactly from many copies of any given initial state as a function of the exponential decay in the success probability, known as the converse error exponent. We give a formula for the optimal rate presented as an infimum over the asymptotic spectrum of LOCC conversion. A full understanding of exact asymptotic extraction rates between pure states in the converse regime thus depends on a full understanding of this spectrum. We present a characterization of spectral points and use it to describe the spectrum in the bipartite case. This leads to a full description of the spectrum and thus an explicit formula for the asymptotic extraction rate between pure bipartite states, given a converse error exponent. This extends the result on entanglement concentration in , where the target state is fixed as the Bell state. In the limit of vanishing converse error exponent, the rate formula provides an upper bound on the exact asymptotic extraction rate between two states, when the probability of success goes to 1. In the bipartite case, we prove that this bound holds with equality. [ABSTRACT FROM AUTHOR]

The error exponent of the typical random code is defined as the asymptotic normalized expectation of the logarithm of the probability of error, as opposed to the traditional definition of the random coding exponent as the normalized logarithm of the expectation of the probability of error with respect to a given ensemble of codes. For a certain ensemble of independent codewords, with a given power spectrum, and a generalized stochastic mismatched decoder, we characterize the error exponent of the typical random codes (TRC) for the colored Gaussian channel, with emphasis on the range of low rates, where the TRC error exponent differs in value from the ordinary random coding error exponent. The error exponent formula, which is exponentially tight at some range of low rates, is presented as the maximum of a certain function with respect to one parameter only (in the spirit of Gallager’s formulas) in the case of matched decoding, and two parameters in the case of mismatched decoding. Several aspects of the main results are discussed. These include: general properties, a parametric representation, critical rates, phase transitions, optimal input spectrum (water pouring), and comparison to the random coding exponent. [ABSTRACT FROM AUTHOR]

Consider the problem of identifying a massive number of bees, uniquely labeled with barcodes, using noisy measurements. We formally introduce this “bee-identification problem”, define its error exponent, and derive efficiently computable upper and lower bounds for this exponent. We show that joint decoding of barcodes provides a significantly better exponent compared to separate decoding followed by permutation inference. For low rates, we prove that the lower bound on the bee-identification exponent obtained using typical random codes (TRC) is strictly better than the corresponding bound obtained using a random code ensemble (RCE). Further, as the rate approaches zero, we prove that the upper bound on the bee-identification exponent meets the lower bound obtained using TRC with joint barcode decoding. [ABSTRACT FROM AUTHOR]

Establishing the sphere packing bound for block codes on the discrete stationary product channels with feedback—which are commonly called the discrete memoryless channels with feedback—was considered to be an open problem until recently, notwithstanding the proof sketch provided by Augustin in 1978. A complete proof following Augustin’s proof sketch is presented to demonstrate its adequacy and to draw attention to two novel ideas that it employs. These novel ideas (i.e., the Augustin’s averaging and the use of subblocks) are likely to be applicable in other communication problems for establishing impossibility results. [ABSTRACT FROM AUTHOR]

We explore the fundamental limits of heterogeneous distributed detection in an anonymous sensor network with $n$ sensors and a single fusion center. The fusion center collects the single observation from each of the $n$ sensors to detect a binary parameter. The sensors are clustered into multiple groups, and different groups follow different distributions under a given hypothesis. The key challenge for the fusion center is the anonymity of sensors—although it knows the exact number of sensors and the distribution of observations in each group, it does not know which group each sensor belongs to. It is hence natural to consider it as a composite hypothesis testing problem. First, we propose an optimal test called mixture likelihood ratio test, which is a randomized threshold test based on the ratio of the uniform mixture of all the possible distributions under one hypothesis to that under the other hypothesis. Optimality is shown by first arguing that there exists an optimal test that is symmetric, that is, it does not depend on the order of observations across the sensors, and then proving that the mixture likelihood ratio test is optimal among all symmetric tests. Second, we focus on the Neyman–Pearson setting and characterize the error exponent of the worst-case type-II error probability as $n$ tends to infinity, assuming the number of sensors in each group is proportional to $n$. Finally, we generalize our result to find the collection of all achievable type-I and type-II error exponents, showing that the boundary of the region can be obtained by solving an optimization problem. Our results elucidate the price of anonymity in heterogeneous distributed detection, and can be extended to $M$ -ary hypothesis testing with heterogeneous observations generated according to hidden latent variables. [ABSTRACT FROM AUTHOR]

This paper deals with the specific construction of binary low-density parity-check (LDPC) codes. We derive lower bounds on the error exponents for these codes transmitted over the memoryless binary symmetric channel (BSC) for both the well-known maximum-likelihood (ML) and proposed low-complexity decoding algorithms. We prove the existence of such LDPC codes that the probability of erroneous decoding decreases exponentially with the growth of the code length while keeping coding rates below the corresponding channel capacity. We also show that an obtained error exponent lower bound under ML decoding almost coincide with the error exponents of good linear codes.

Typical random codes (TRCs) in a communication scenario of source coding with side information in the decoder is the main subject of this work. We study the semi-deterministic code ensemble, which is a certain variant of the ordinary random binning code ensemble. In this code ensemble, the relatively small type classes of the source are deterministically partitioned into the available bins in a one-to-one manner. As a consequence, the error probability decreases dramatically. The random binning error exponent and the error exponent of the TRCs are derived and proved to be equal to one another in a few important special cases. We show that the performance under optimal decoding can be attained also by certain universal decoders, e.g., the stochastic likelihood decoder with an empirical entropy metric. Moreover, we discuss the trade-offs between the error exponent and the excess-rate exponent for the typical random semi-deterministic code and characterize its optimal rate function. We show that for any pair of correlated information sources, both error and excess-rate probabilities exponential vanish when the blocklength tends to infinity.

We consider the problem of detecting a random walk on a graph, based on observations of the graph nodes. When visited by the walk, each node of the graph observes a signal of elevated mean, which we assume can be different across different nodes. Outside of the path of the walk, and also in its absence, nodes measure only noise. Assuming the Neyman-Pearson setting, our goal then is to characterize detection performance by computing the error exponent for the probability of a miss, under a constraint on the probability of false alarm. Since the exact computation of the error exponent is known to be difficult, equivalent to the computation of the Lyapunov exponent, we approximate its value by finding a tractable lower bound. The bound reveals an interesting detectability condition: the walk is detectable whenever the entropy of the walk is smaller than one half of the expected signal-to-noise ratio. We derive the bound by extending the notion of Markov types to Gauss-Markov types. These are sequences of the state-observation pairs with a given number of node-to-node transition counts and the same average signal values across nodes, computed from the measurements made during the times the random walk visited each node’s respective location. The lower bound has an intuitive interpretation: among all Gauss-Markov types that are asymptotically feasible in the absence of the walk, the bound finds the most typical one under the presence of the walk. Finally, we show by a sequence of judicious problem reformulations that computing the bound reduces to solving a convex optimization problem, which is a result of in its interest own right. [ABSTRACT FROM AUTHOR]

We consider data transmission across discrete memoryless channels (DMCs) using variable-length codes with feedback. We consider the family of such codes whose rates are $\rho _{N}$ below the channel capacity $C$ , where $\rho _{N}$ is a positive sequence that tends to zero slower than the reciprocal of the square root of the expectation of the (random) blocklength $N$. This is known as the moderate deviations regime, and we establish the optimal moderate deviations constant. We show that in this scenario, the error probability decays sub-exponentially with speed $\exp (-(B/C)N\rho _{N})$ , where $B$ is the maximum relative entropy between output distributions of the DMC. [ABSTRACT FROM AUTHOR]

This paper considers the problem of channel coding over Gaussian intersymbol interference (ISI) channels with a given decoding rule. Specifically, it is assumed that the mismatched decoder has an incorrect assumption on the channel impulse response. The mismatch capacity is the highest achievable rate for a given decoding rule. The existing achievable rates for channels and decoding metrics with memory (as in our model) are currently available only in the form of multi-letter expressions that cannot be calculated. Consequently, they provide little insight on the mismatch problem. In this paper, we derive the computable formulas of achievable rates and discuss some implications of our results. Our achievable rates are based on two ensembles: the ensemble of codewords generated by an autoregressive process and the ensemble of codewords drawn uniformly over a “type class” of real-valued sequences. We provide a few numerical results of our achievable rates, as functions of the mismatched ISI parameters. Finally, we compare our results with universal decoders which are designed outside the true class of channels that we consider in this paper. [ABSTRACT FROM AUTHOR]

This paper contains two main contributions concerning the expurgation of hierarchical ensembles for the asymmetric broadcast channel. The first is an analysis of the optimal maximum likelihood (ML) decoders for the weak and strong user. Two different methods of code expurgation will be used, that will provide two competing error exponents. The second is the derivation of expurgated exponents under the generalized stochastic likelihood decoder (GLD). We prove that the expurgated exponents achieved for the hierarchical ensemble under GLD decoding are at least as good as the maximum between the random coding error exponents derived in an earlier work by Averbuch and Merhav (2018) and one of our ML–based expurgated exponents. [ABSTRACT FROM AUTHOR]

Sparse superposition codes, or sparse regression codes, are a recent class of codes for reliable communication over the AWGN channel at rates approaching the channel capacity. Approximate message passing (AMP) decoding, a computationally efficient technique for decoding SPARCs, has been proven to be asymptotically capacity-achieving for the AWGN channel. In this paper, we refine the asymptotic result by deriving a large deviation bound on the probability of an AMP decoding error. This bound gives insight into the error performance of the AMP decoder for large but finite problem sizes, giving an error exponent as well as guidance on how the code parameters should be chosen at finite block lengths. For an appropriate choice of code parameters, we show that for any fixed rate less than the channel capacity, the decoding error probability decays exponentially in $n/(\log n)^{2T}$ , where $T$ , the number of AMP iterations required for successful decoding, is bounded in terms of the gap from capacity. [ABSTRACT FROM AUTHOR]

We investigate two closely related nonparametric hypothesis testing problems. In the first problem (i.e., the existence problem), we test whether a testing data stream is generated by one of a set of composite distributions. In the second problem (i.e., the association problem), we test which one of the multiple distributions generates a testing data stream. We assume that some distributions in the set are unknown, and instead, only training sequences generated by the corresponding distributions are available. For both problems, we construct the generalized likelihood tests and characterize the error exponents of the maximum error probabilities. For the existence problem, we show that the error exponent is mainly captured by the Chernoff information between the set of composite distributions and alternative distributions. For the association problem, we show that the error exponent is captured by the minimum Chernoff information between each pair of distributions as well as the Kullback-Leibler Divergences between the approximated distributions (via training sequences) and the true distributions. We also show that the ratio between the lengths of training and testing sequences plays an important role in determining the error decay rate. [ABSTRACT FROM AUTHOR]

Abstract: The error exponent of the regular graph-based binary low-density parity-check (LDPC) codes under the maximum likelihood (ML) decoding algorithm in the binary symmetric channel (BSC) is analyzed. Unlike most other papers where error exponents are considered for the case when the length of LDPC codes tends to infinity (asymptotic analysis), the finite length case (finite length analysis) is considered. In this paper, a method of deriving the lower bound on the error exponent for a regular graph-based LDPC code with finite length under ML decoding is described. Also we analyze Dependences of the error exponent on various LDPC code parameters are also analyzed. The numerical results obtained for the considered lower bound are represented and analyzed at the end of the paper. [ABSTRACT FROM AUTHOR]

We study the asymptotic performance of distributed detection in large scale connected sensor networks. Contrasting to the canonical parallel network where a single node has access to local decisions from all other nodes, each node can only exchange information with its direct neighbors in the present setting. We establish that, with each node employing an identical one-bit quantizer for local information exchange, a novel consensus reaching approach can achieve the optimal asymptotic performance of centralized detection as the network size scales. The statement is true under three different detection frameworks: 1) the Bayesian criterion where the maximum a posteriori detector is optimal; 2) the Neyman–Pearson criterion with a constant type-I error probability constraint; and 3) the Neyman–Pearson criterion with an exponential type-I error probability constraint. Leveraging recent development in distributed consensus reaching using bounded quantizers with possibly unbounded data (which are log-likelihood ratios of local observations in the context of distributed detection), we design a one-bit deterministic quantizer with a controllable threshold that leads to desirable consensus error bounds. The obtained bounds are key to establishing the optimal asymptotic detection performance. In addition, we examine the non-asymptotic performance of the proposed approach and show that the type-I and type-II error probabilities at each node can be made arbitrarily close to the centralized ones simultaneously when a continuity condition is satisfied. [ABSTRACT FROM AUTHOR]

In this paper, we consider distributed testing problems with cascaded encoders, which allow cascaded communications among encoders so that each encoder can utilize messages from other encoders for encoding. We first focus on a special case of testing against independence and design a scheme that enables each encoder to take advantage of extra information from other encoders. We also derive a matching upper bound and prove that the designed scheme is optimal. We then investigate the case with general hypotheses and obtain a lower bound on the type 2 error exponent. We further compare the performances that can be achieved by schemes with and without cascaded communications. We show that cascaded communication improves the performance in terms of the type 2 error exponent under positive rate communication constraints. On the other hand, we prove that cascaded communication does not provide performance gain under zero-rate communication constraints. [ABSTRACT FROM AUTHOR]

A distributed binary hypothesis testing (HT) problem involving two parties, a remote observer and a detector, is studied. The remote observer has access to a discrete memoryless source, and communicates its observations to the detector via a rate-limited noiseless channel. The detector observes another discrete memoryless source, and performs a binary hypothesis test on the joint distribution of its own observations with those of the observer. While the goal of the observer is to maximize the type II error exponent of the test for a given type I error probability constraint, it also wants to keep a private part of its observations as oblivious to the detector as possible. Considering both equivocation and average distortion under a causal disclosure assumption as possible measures of privacy, the trade-off between the communication rate from the observer to the detector, the type II error exponent, and privacy is studied. For the general HT problem, we establish single-letter inner bounds on both the rate-error exponent-equivocation and rate-error exponent-distortion trade-offs. Subsequently, single-letter characterizations for both trade-offs are obtained (i) for testing against conditional independence of the observer’s observations from those of the detector, given some additional side information at the detector; and (ii) when the communication rate constraint over the channel is zero. Finally, we show by providing a counter-example where the strong converse which holds for distributed HT without a privacy constraint does not hold when a privacy constraint is imposed. This implies that in general, the rate-error exponent-equivocation and rate-error exponent-distortion trade-offs are not independent of the type I error probability constraint.

We investigate the nonparametric, composite hypothesis testing problem for arbitrary unknown distributions in the asymptotic regime where both the sample size and the number of hypothesis grow exponentially large. Such asymptotic analysis is important in many practical problems, where the number of variations that can exist within a family of distributions can be countably infinite. We introduce the notion of discrimination capacity, which captures the largest exponential growth rate of the number of hypothesis relative to the sample size so that there exists a test with asymptotically vanishing probability of error. Our approach is based on various distributional distance metrics in order to incorporate the generative model of the data. We provide analyses of the error exponent using the maximum mean discrepancy and Kolmogorov–Smirnov distance and characterize the corresponding discrimination rates, i.e., lower bounds on the discrimination capacity, for these tests. Finally, an upper bound on the discrimination capacity based on Fano's inequality is developed. Numerical results are presented to validate the theoretical results. [ABSTRACT FROM AUTHOR]