In outlier hypothesis testing, multiple observation sequences are collected, a small subset of which are outliers. Observations in an outlier sequence are generated by a mechanism different from that generating the observations in the majority of sequences. The goal is to best discern all the outlier sequences without any knowledge of the underlying generating mechanisms. A generalized likelihood test is considered in the fixed sample size setting. In the sequential setting, a test based on the Multihypothesis Sequential Probability Ratio Test and the repeated significance test is considered. The sequential test outperforms the generalized likelihood test when the lengths of the observation sequences exceed certain values. Applied to a real data set for spam detection, the performance of the proposed tests is shown to be superior to those based on the maximum mean discrepancy for large sample size.

Quickest outlier detection and isolation is studied in universal settings. Initially, multiple data streams are commonly distributed according to a “typical” distribution. At the change time, an outlier stream emerges and starts to be distributed according to the “outlier” distribution, while the rest of the streams remain to be distributed according to the typical one. Two tests are proposed to quickly isolate the outlier. The first test is shown to be asymptotically optimal universally when only the typical distribution is known, and in the limit of the large number of streams when neither the outlier nor typical distribution is known. The performance of the second test, which is more practical, is also characterized.

Universal outlier hypothesis testing is studied in a sequential setting. Multiple observation sequences are collected, one of which is an outlier. Observations in the outlier sequence are generated by a unique mechanism, different from that generating the observations in all other sequences. The goal is to design a universal test to best discern the outlier sequence with the fewest observations on average. Based on the Multihypothesis Sequential Probability Ratio Test and the generalized likelihood test, a universal test is proposed and shown to be universally exponentially consistent. A lower bound on the achievable error exponents of such a test is derived. The proposed test can be modified to accommodate an additional null hypothesis with no outlier. In particular, it is shown to be consistent under the null hypothesis while retaining universally exponential consistency under all other hypotheses.

Outlier hypothesis testing is studied in a universal setting. Multiple sequences of observations are collected, a small subset of which are outliers. A sequence is considered an outlier if the observations in that sequence are distributed according to an outlier distribution, distinct from the typical distribution governing the observations in all the other sequences. Nothing is known about the outlier and typical distributions except that they are distinct and have full supports. The goal is to design a universal test to best discern the outlier sequence(s). For models with exactly one outlier sequence, the generalized likelihood test is shown to be universally exponentially consistent. A single-letter characterization of the error exponent achievable by the test is derived, and it is shown that the test achieves the optimal error exponent asymptotically as the number of sequences approaches infinity. When the null hypothesis with no outlier is included, a modification of the generalized likelihood test is shown to achieve the same error exponent under each non-null hypothesis, and also consistency under the null hypothesis. Then, models with more than one outlier are studied in the following settings. For the setting with a known number of distinctly distributed outliers, the achievable error exponent of the generalized likelihood test is characterized. The limiting error exponent achieved by such a test is characterized, and the test is shown to be asymptotically exponentially consistent. For the setting with an unknown number of identically distributed outliers, a modification of the generalized likelihood test is shown to achieve a positive error exponent under each non-null hypothesis, and also consistency under the null hypothesis. When the outlier sequences can be distinctly distributed (with their total number being unknown), it is shown that a universally exponentially consistent test cannot exist, even when the typical distribution is known and the null hypothesis is excluded.

The following outlier hypothesis testing problem is studied in a universal setting. Vector observations are collected each with M ≥ 3 coordinates. When a given coordinate is the outlier, the observations in that coordinate are assumed to be distributed according to the “outlier” distribution, distinct from the common “typical” distribution governing the observations in all the other coordinates. Nothing is known about the outlier and the typical distributions except that they are distinct and have full supports. The goal is to design a universal test to best discern the outlier coordinate. A universal test based on the generalized likelihood principle is proposed and is shown to be universally exponentially consistent, and a single-letter characterization of the error exponent achievable by the test is derived. It is shown that as the number of coordinates approaches infinity, our universal test is asymptotically efficient. Specifically, it achieves a limiting error exponent that is equal to the largest achievable error exponent when the outlier and typical distributions are both known.

A new model for controlled sensing for multiphypothesis testing is proposed and studied in both the sequential and fixed sample size settings. This new model, termed a stationary Markov model, exhibits a more complicated memory structure in the controlled observations than the existing stationary memoryless model. In the sequential setting, an asymptotically optimal sequential test using a stationary causal Markov control policy enjoying a strong asymptotic optimality condition is proposed for this new model, and its asymptotic performance is characterized. In the fixed sample size setting, bounds for the optimal error exponent for binary hypothesis testing are derived; it is conjectured that the structure of the asymptotically optimal control for the stationary Markov model will be much more complicated than that for the stationary memoryless model.

We study the capacity region$C_{L}$of an arbitrarily varying multiple-access channel (AVMAC) for deterministic codes with decoding into a list of a fixed size$L$and for the average error probability criterion. Motivated by known results in the study of fixed size list decoding for a point-to-point arbitrarily varying channel, we define for every AVMAC whose capacity region for random codes has a nonempty interior, a nonnegative integer$\Omega$called its symmetrizability. It is shown that for every$L\leq\Omega$,$C_{L}$has an empty interior, and for every$L\geq(\Omega+1)^{2}$,$C_{L}$equals the nondegenerate capacity region of the AVMAC for random codes with a known single-letter characterization. For a binary AVMAC with a nondegenerate random code capacity region, it is shown that the symmetrizability is always finite.

In this paper, the problem of multiple hypothesis testing with observation control is considered. The structure of the optimal controller under various asymptotic regimes is studied. First, a setup with a fixed sample size is considered. In this setup, the asymptotic quantity of interest is the optimal exponent for the maximal error probability. For the case of binary hypothesis testing, it is shown that the optimal error exponent corresponds to the maximum Chernoff information over the choice of controls. It is also shown that a pure stationary control policy, i.e., a fixed policy which does not depend on specific realizations of past measurements and past controls (open-loop), is asymptotically optimal even among the class of all causal control policies. We also derive lower and upper bounds for the optimal error exponent for the case of multiple hypothesis testing. Second, a sequential setup is considered wherein the controller can also decide when to stop taking observations. In this case, the objective is to minimize the expected stopping time subject to the constraints of vanishing error probabilities under each hypothesis. A sequential test is proposed for testing multiple hypotheses and is shown to be asymptotically optimal.

Secret key generation by multiple terminals is considered based on their observations of jointly distributed Gaussian signals, followed by public communication among themselves. Exploiting an inherent connection between secrecy generation and lossy data compression, two main contributions are made. The first is a characterization of strong secret key capacity, and entails a converse proof technique that is valid for real-valued (and not necessarily Gaussian) as well as finite-valued signals. The capacity formula acquires a simple form when the terminals observe “symmetrically correlated” jointly Gaussian signals. For the latter setup with two terminals, considering schemes that involve quantization at one terminal, the best rate of an achievable secret key is characterized as a function of quantization rate; secret key capacity is attained as the quantization rate tends to infinity. Structured codes are shown to attain the optimum tradeoff between secret key rate and quantization rate, constituting our second main contribution.

We prove a computable inner bound for the maximal error capacity region of a Symmetric Gaussian Multiple-Access Channel (SGMAC). The main idea behind our results is successive cancellation in decoding involving decoding of only one message set first while regarding the other message set as interference followed by a cancellation of the effect of the decoded message. Specifically, the inner bound is obtained through a connection between the SGMAC and another point-to-point Gaussian Channel with Interference (GCI) model introduced here. The bound takes the form of a pentagon strictly inside the average error capacity region.

We study the capacity region CLof an arbitrarily varying multiple-access channel (AVMAC) for deterministic codes with decoding into a list of a fixed size L and for the average error probability criterion. Motivated by known results in the study of fixed size list decoding for a point-to-point arbitrarily varying channel, we define for every AVMAC whose capacity region for random codes is nonempty, a nonnegative integer U called its symmetrizability. It is shown that for every L ≤ U, CLhas an empty interior, and for every L ≥ (U +1)2, CLequals the capacity region of the AVMAC for random codes with a known single-letter characterization.

We consider perfect secret key generation for a “pairwise independent network” model in which every pair of terminals share a random binary string, with the strings shared by distinct terminal pairs being mutually independent. The terminals are then allowed to communicate interactively over a public noiseless channel of unlimited capacity. All the terminals as well as an eavesdropper observe this communication. The objective is to generate a perfect secret key shared by a given set of terminals at the largest rate possible, and concealed from the eavesdropper. First, we show how the notion of perfect omniscience plays a central role in characterizing perfect secret key capacity. Second, a multigraph representation of the underlying secrecy model leads us to an efficient algorithm for perfect secret key generation based on maximal Steiner tree packing. This algorithm attains capacity when all the terminals seek to share a key, and, in general, attains at least half the capacity. Our results yield new bounds for the maximum size and rate of Steiner tree packing, and are of independent interest from a graph theoretic viewpoint. Third, when a single “helper” terminal assists the remaining “user” terminals in generating a perfect secret key, we give necessary and sufficient conditions for the optimality of the algorithm; also, a “weak” helper is shown to be sufficient for optimality.

We consider secret key generation for a “pairwise independent network” model in which every pair of terminals observes correlated sources that are independent of sources observed by all other pairs of terminals. The terminals are then allowed to communicate publicly with all such communication being observed by all the terminals. The objective is to generate a secret key shared by a given subset of terminals at the largest rate possible, with the cooperation of any remaining terminals. Secrecy is required from an eavesdropper that has access to the public interterminal communication. A (single-letter) formula for secret key capacity brings out a natural connection between the problem of secret key generation and a combinatorial problem of maximal packing of Steiner trees in an associated multigraph. An explicit algorithm is proposed for secret key generation based on a maximal packing of Steiner trees in a multigraph; the corresponding maximum rate of Steiner tree packing is thus a lower bound for the secret key capacity. When only two of the terminals or when all the terminals seek to share a secret key, the mentioned algorithm achieves secret key capacity in which case the bound is tight.

We investigate perfect secret key generation for a ¿pairwise independent network¿ model in which every pair of terminals observes correlated sources that are independent of sources observed by all other pairs of terminals. The terminals are then allowed to communicate interactively in multiple rounds over a public noiseless channel of unlimited capacity. This communication is observed by all the terminals as well as by an eavesdropper. The objective is to generate a perfect secret key shared by a given set of terminals at the largest rate possible. All the terminals cooperate in generating the secret key, with perfect secrecy being required from the eavesdropper. For this model, we introduce the concept of communication for perfect omniscience using which we first obtain a single-letter characterization of the perfect secret key capacity. Moreover, this perfect secret key capacity is shown to be achieved by linear noninteractive communication, and coincides with the (standard) secret key capacity. Our second contribution, exploiting the notion of communication for perfect omniscience, is a new nonasymptotic and computable upper bound for the combinatorial problem of maximal Steiner tree packing in a multigraph. Thus, our work establishes certain connections among perfect secrecy generation and communication for perfect omniscience for the pairwise independent network model, and Steiner tree packing.

We consider secret key (SK) generation by two terminals, each of which observes an i.i.d. source which is correlated with the other; the two sources are jointly Gaussian with known distribution. The terminals are then allowed to communicate with each other, possibly interactively in many rounds and without rate restrictions, over a noiseless two-way public channel. Randomization is permitted at each terminal. The goal is for the terminals to generate a SK comprising discrete common randomness which is concealed from an eavesdropper that has access to the public interterminal communication. We establish that this maximum rate of SK generation, i.e., SK capacity, is, as expected, the per-symbol mutual information I of the correlated sources. Our main technical contribution is a new scheme for achieving SK capacity using structured codes. In our scheme, vector quantization at rate R nats/source symbol of the source at terminal 1 is performed by employing nested lattice codes with dithering. Then, a SK is generated by the terminals from the quantized random sequence at terminal 1 and the (unquantized) Gaussian source at terminal 2, using both lossy and lossless data compression techniques. Our algorithm, using a rate-R lattice quantizer, achieves a maximum SK rate of 1/2 log 1/(e-2I+(1-e-2I)e-2R), which tends to the SK capacity I with increasing R. Thus, our result also specifies the associated tradeoff between quantization rate R and the maximum achievable SK rate. This tradeoff is shown to be optimum among a certain restricted class of schemes for SK generation that involve quantization at rate R of a Gaussian source at one terminal.

We investigate secret key generation for a ldquopair-wise independent networkrdquo model in which every pair of terminals observes correlated sources which are independent of sources observed by all other pairs of terminals. The terminals are then allowed to communicate interactively in multiple rounds over a public noiseless channel of unlimited capacity, with all such communication being observed by all the terminals. The objective is to generate a secret key shared by a given subset of terminals at the largest rate possible. All the terminals cooperate in generating the secret key, with secrecy being required from an eavesdropper which has access to the public interterminal communication. We provide a (single-letter) formula for the secrecy capacity for this model, and show a natural connection between the problem of secret key generation and the combinatorial problem of maximal packing of Steiner trees in an associated multigraph. In particular, we show that the maximum number of Steiner tree packings in the multigraph is always a lower bound for the secrecy capacity. The bound is tight for the case when all the terminals seek to share a secret key; the mentioned connection yields an explicit capacity-achieving algorithm. This algorithm, which can be executed in polynomial time, extracts a group-wide secret key of the optimum rate from the collection of optimum and mutually independent secret keys for pairs of terminals.