Given training sequences generated by two distinct, but unknown, distributions on a common alphabet, we study the problem of determining whether a third sequence was generated according to the first or second distribution. To model sources such as natural language, for which the underlying distributions are difficult to learn from realistic amounts of data, we allow the alphabet size to grow and therefore the probability distributions to change with the block length. Our primary focus is the situation in which the underlying probabilities are all of the same order, and in this regime, we show that consistent classification is possible if and only if the alphabet grows subquadratically with the block length. We also show that some commonly used statistical tests are suboptimal in that they are consistent only if the alphabet grows sublinearly.

We study error exponents for source coding with side information. Both achievable exponents and converse bounds are obtained for the following two cases: lossless source coding with coded information and lossy source coding with full side information (Wyner-Ziv). These results recover and extend several existing results on source-coding error exponents and are tight in some circumstances. Our bounds have a natural interpretation as a two-player game between nature and the code designer, with nature seeking to minimize the exponent and the code designer seeking to maximize it. In the Wyner-Ziv problem, our analysis exposes a tension in the choice of test channel with the optimal test channel balancing two competing error events. The Gaussian and binary-erasure cases are examined in detail.

We provide a novel upper-bound on Witsenhausen's rate, the rate required in the zero-error analogue of the Slepian-Wolf problem. Our bound is given in terms of a new information-theoretic functional defined on a certain graph and is derived by upper bounding complementary graph entropy. We use the functional, along with graph entropy, to give a single letter lower-bound on the error exponent for the Slepian-Wolf problem under the vanishing error probability criterion, where the decoder has full (i.e., unencoded) side information. We demonstrate that our error exponent can beat the “expurgated” source-coding exponent of Csiszár and Körner for some sources that have zeroes in the “channel” matrix connecting the source with the side information. An extension of our scheme to the lossy case (i.e., Wyner-Ziv) is given. For the case in which the side information is a deterministic function of the source, the exponent of our improved scheme agrees with the sphere-packing bound exactly (thus determining the reliability function). An application of our functional to zero-error channel capacity is also given.

We describe a scheme for rate-distortion with distributed encoding in which the sources to be compressed contain a common component. We show that this scheme is optimal in some situations and that it strictly improves upon existing schemes, which do not make full use of common components. This establishes that independent quantization followed by independent binning is not optimal for the two-encoder problem with a distortion constraint on one source. We also show that independent quantization and binning is suboptimal for the three-encoder problem in which the goal is to reproduce one of the sources losslessly. This provides a counterexample that is fundamentally different from one provided earlier by Körner and Marton. The proofs rely on the binary analogue of the entropy power inequality and the existence of a rate loss for the binary symmetric Wyner-Ziv problem.

Given training sequences generated by two distinct, but unknown distributions sharing a common alphabet, we seek a classifier that can correctly decide whether a third test sequence is generated by the first or second distribution using only the training data. To model `limited learning' we allow the alphabet size to grow and therefore probability distributions to change with the blocklength. We prove that a natural choice, namely a generalized likelihood ratio test, is universally consistent (has a probability of error tending to zero with the blocklength for all underlying distributions) when the alphabet size is sub-linear in the blocklength, but inconsistent for linear alphabet growth. For up-to quadratic alphabet growth, in a regime where all probabilities are of the same order, we prove the universally consistency of a new test and show there are no such tests when the alphabet grows quadratically or faster.

We provide new achievable error exponents for the problem of source coding with full side information at the decoder. In some instances our exponent strictly improves upon the previous applicable results of Csiszar; Oohama and Han; and the ldquoexpurgatedrdquo exponent of Csiszar and Korner. Our improvement follows from studying the growth rate of the chromatic number of strong (and) product graphs via a new information-theoretic functional on a graph. We also give an upper bound on Witsenhausen's rate, i.e. the zero error rate for the problem of source coding with full side information at the decoder. An application of our functional to zero-error channel capacity is also given.

We consider the quadratic Gaussian Wyner-Ziv problem, i.e., the problem of lossy compression of a Gaussian source with Gaussian side information at the decoder and a quadratic distortion measure. Motivated by applications in video coding, we study how to minimize the probability that the distortion exceeds a given threshold, as opposed to the conventional approach of minimizing the average distortion. We obtain an achievable exponent for this problem, which is positive above the rate distortion function, and expose a tension in the choice of the test channel; the optimal test channel balances two competing error events.