A distributed binary hypothesis testing (HT) problem over a noisy (discrete and memoryless) channel studied previously by the authors is investigated from the perspective of the strong converse property. It was shown by Ahlswede and Csiszar that a strong converse holds in the above setting when the channel is rate-limited and noiseless. Motivated by this observation, we show that the strong converse continues to hold in the noisy channel setting for a special case of HT known as testing against independence (TAI), under the assumption that the channel transition matrix has non-zero elements. The proof utilizes the blowing up lemma and the recent change of measure technique of Tyagi and Watanabe as the key tools.
We study a variant of the many-help one hypothesis testing against independence problem in which the source, not necessarily Gaussian, has finite differential entropy and the observation noises under the null hypothesis are Gaussian. Under the criterion that stipulates minimization of the Type II error exponent subject to a (constant) bound $\epsilon$ on the Type I error rate, we derive an upper bound on the exponent-rates function. The bound is shown to mirror a corresponding explicit lower bound, except that the lower bound involves the source power (variance) whereas the upper bound has the source entropy power. Part of the utility of the established bound is for investigating asymptotic exponent/rates and losses incurred by distributed detection as function of the number of observations.
We consider the classical sequential binary hypothesis testing problem in which there are two hypotheses governed respectively by distributions P 0 and P 1 and we would like to decide which hypothesis is true using a sequential test. It is known from the work of Wald and Wolfowitz that as the expectation of the length of the test grows, the optimal typeI and type-II error exponents approach the relative entropies D(P 1 ∥ P 0 ) and D(P 0 ∥ P 1 ). We reﬁne this result by considering the optimal backoff from the corner point of the achievable exponent region (D(P 1 ∥ P 0 ), D(P 0 ∥ P 1 )) under the expectation constraint on the length of the test (or the sample size). We consider the expectation constraint in which the expectation of the sample size is bounded by n, and under mild conditions, characterize the backoff, also coined second-order asymptotics, precisely. Examples are provided to illustrate our results.
From the design of a data-driven partition, this paper addresses the problem of testing independence between two multidimensional random variables from i.i.d. samples. The empirical log-likelihood statistics is adopted with the objective of approximating the sufficient statistics of a test against independence that knows the two distributions (the oracle test). It is shown that approximating the sufficient statistics of the oracle test (asymptotically) offers a connection with the problem of estimating mutual information. Applying these ideas in the context of a data-dependent tree-structured partition (TSP), we derive concrete sufficient conditions on the parameters of the TSP scheme to obtain a strongly consistent test of independence distribution-free over the family of joint probabilities equipped with densities.
This paper considers a noisy data structure recovery problem. Specifically, the goal is to investigate the following question: Given a noisy observation of the data, according to which permutation was the original data sorted? The main focus is on scenarios where data is generated according to an isotropic Gaussian distribution, and the perturbation consists of adding Gaussian noise with diagonal scalar covariance matrix. This problem is posed within a hypothesis testing framework. First, the optimal decision criterion is characterized and shown to be identical to the hypothesis of the observation. Then, by leveraging the structure of the optimal decision criterion, the probability of error is characterized. Finally, the logarithmic behavior (i.e., the exponent) of the probability of error is derived in the regime where the dimension of the data goes to infinity.
We consider the problem of detecting one of M signals corrupted with white Gaussian noise. Conventionally, to minimize the probability of error, one uses matched filters to obtain a set of M sufficient statistics. In practice, M may be prohibitively large; this motivates the design and analysis of a reduced set of statistics which we term approximate sufficient statistics. By considering a sequence of sensing matrices that possesses suitable coherence and orthogonality properties, we bound the error exponent of the approximate sufficient statistics and compare it to that of the sufficient statistics. Additionally, we show that lower bound on the error exponent increases linearly for small compression rates.