Following a growing number of studies that, over the past 15 years, have established entropy inequalities via ideas and tools from additive combinatorics, in this work we obtain a number of new bounds for the differential entropy of sums, products, and sum-product combinations of continuous random variables. Partly motivated by recent work by Goh on the discrete entropic version of the notion of “additive energy”, we introduce the additive energy of pairs of continuous random variables and prove various versions of the statement that “the additive energy is large if and only if the entropy of the sum is small”, along with a version of the Balog–Szemerédi–Gowers theorem for differential entropy. Then, motivated in part by recent work by M´athé and O’Regan, we establish a series of new differential entropy inequalities for products and sum-product combinations of continuous random variables. In particular, we prove a new, general, ring Plüunnecke–Ruzsa entropy inequality. We briefly return to the case of discrete entropy and provide a characterization of discrete random variables with “large doubling”, analogous to Tao’s Freiman-type inverse sumset theory for the case of small doubling. Finally, we consider the natural entropic analog of the Erdős–Szemerédi sum-product phenomenon for integer-valued random variables. We show that, if it does hold, then the range of parameters for which it does would necessarily be significantly more restricted than its anticipated combinatorial counterpart.

The problem of variable-rate lossless data compression is considered, for codes with and without prefix constraints. Sharp bounds are derived for the best achievable compression rate of memoryless sources, when the excess-rate probability is required to be exponentially small in the blocklength. Accurate nonasymptotic expansions with explicit constants are obtained for the optimal rate, using tools from large deviations and Gaussian approximation. When the source distribution is unknown, a universal achievability result is obtained with an explicit “price for universality” term. This is based on a fine combinatorial estimate on the number of sequences with small empirical entropy, which might be of independent interest. Examples are shown indicating that, in the small excess-rate-probability regime, the approximation to the fundamental limit of the compression rate suggested by these bounds is significantly more accurate than the approximations provided by either normal approximation or error exponents. The new bounds reinforce the crucial operational conclusion that, in applications where the blocklength is relatively short and where stringent guarantees are required on the excess-rate probability, the best achievable rate is no longer close to the entropy. Rather, it is an appropriate, morepragmaticrate, determined via the inverse error exponent function and the blocklength.

The problem of variable-rate lossless data compression is considered, for codes with and without prefix constraints. Sharp bounds are derived for the best achievable compression rate of memoryless sources, when the excess-rate probability is required to be exponentially small in the blocklength. Accurate nonasymptotic expansions with explicit constants are obtained for the optimal rate, using tools from large deviations and Gaussian approximation. Examples are shown indicating that, in the small excess-rate-probability regime, the approximation to the fundamental limit of the compression rate suggested by these bounds is significantly more accurate than the approximations provided by either normal approximation or error exponents. The new bounds reinforce the crucial operational conclusion that, in applications where the blocklength is relatively short and where stringent guarantees are required on the rate, the best achievable rate is no longer close to the entropy. Rather, it is an appropriate, more pragmatic rate, determined via the inverse error exponent function and the blocklength.

A new finite form of de Finetti's representation theorem is established using elementary information-theoretic tools. The distribution of the first$k$random variables in an exchangeable vector of$n\geq k$random variables is close to a mixture of product distributions. Closeness is measured in terms of the relative entropy and an explicit bound is provided. This bound is tighter than those obtained via earlier information-theoretic proofs, and its utility extends to random variables taking values in general spaces. The core argument employed has its origins in the quantum information-theoretic literature.

Sharp, nonasymptotic bounds are derived for the best achievable error probability in binary hypothesis testing between two probability distributions with independent and identically distributed observations. The asymmetric version of the problem is considered, where different requirements are placed on the two error probabilities. Using techniques from large deviations theory and normal approximation, accurate nonasymptotic expansions are obtained with explicit constants. Examples are shown indicating that, in the asymmetric regime, the approximations suggested by the new bounds are significantly more accurate than the approximations provided by either of the two main earlier approaches - normal approximation and error exponents.

Directed information has been used in information theory and in statistics as a functional that quantifies causal influences present in signals and empirical data. In this work, the causally conditional directed information (CCDI) rate is identified as a statistic for detecting causal relationships between discrete time series, in the presence of potential confounders. A hypothesis test is introduced for identifying the temporally causal influence of$(x_{n})$on$(y_{\mathrm{Y}})$, causally conditioned on a possibly confounding third time series$(z_{n})$. Under natural assumptions it is shown that the absence of temporally causal influence is equivalent to the CCDI rate being zero. The plug-in estimator for this functional is identified with the log-likelihood ratio test statistic for the desired test. This statistic is shown to be asymptotically normal under the alternative hypothesis and asymptotically$\chi^{2}$distributed under the null, facilitating the computation of p-values from empirical data. The resulting hypothesis test is employed in the analysis of spike train data recorded from neurons in the V4 and FEF brain regions of behaving animals during a visual attention task. The test results are seen to identify interesting and biologically relevant information.

Entropy comparison inequalities are obtained for the differential entropy$h(X+Y)$of the sum of two independent random vectors$X,Y$, when one is replaced by a Gaussian. For identically distributed random vectors$X,Y$, these are closely related to bounds on the entropic doubling constant, which quantifies the entropy increase when adding an independent copy of a random vector to itself. Consequences of both large and small doubling are explored. For the former, lower bounds are deduced on the entropy increase when adding an independent Gaussian, while for the latter, a qualitative stability result for the entropy power inequality is obtained. In the more general case of non-identically distributed random vectors$X,Y$, a Gaussian comparison inequality with interesting implications for channel coding is established: For additive-noise channels with a power constraint, Gaussian codebooks come within a$\frac {\mathsf { snr}}{3{\mathsf { snr}}+2}$factor of capacity. In the low-SNR regime this improves the half-a-bit additive bound of Zamir and Erez. Analogous results are obtained for additive-noise multiple access channels, and for linear, additive-noise

The Bayesian Context Trees (BCT) framework is a recently introduced, general collection of statistical and algorithmic tools for modelling, analysis and inference with discrete-valued time series. The foundation of this development is built in part on some well-known information-theoretic ideas and techniques, including Rissanen’s tree sources and Willems et al.’s context-tree weighting algorithm. This paper presents a collection of theoretical results that provide mathematical justifications and further insight into the BCT modelling framework and the associated practical tools. It is shown that the BCT prior predictive likelihood (the probability of a time series of observations averaged over all models and parameters) is both pointwise and minimax optimal, in agreement with the MDL principle and the BIC criterion. The posterior distribution is shown to be asymptotically consistent with probability one (over both models and parameters), and asymptotically Gaussian (over the parameters). And the posterior predictive distribution is also shown to be asymptotically consistent with probability one.

The Bayesian Context Trees (BCT) framework is a recently introduced, general collection of statistical and algorithmic tools for modelling, analysis and inference with discrete-valued time series. The foundation of this development is built in part on some well-known information-theoretic ideas and techniques, including Rissanen’s tree sources and Willems et al.’s context-tree weighting (CTW) algorithm. This paper presents a collection of theoretical results that provide mathematical justifications and further insight into the BCT modelling framework and the associated practical tools, including the CTW algorithm. It is shown that the BCT prior predictive likelihood (the probability of a time series of observations averaged over all models and parameters) is both pointwise and minimax optimal, in agreement with the MDL principle and the BIC criterion. The posterior distribution is shown to be asymptotically consistent with probability one (over both models and parameters), and asymptotically Gaussian (over the parameters). And the posterior predictive distribution is also shown to be asymptotically consistent with probability one.

Real-valued time series are ubiquitous in the sciences and engineering. In this work, a general, hierarchical Bayesian modelling framework is developed for building mixture models for times series. This development is based, in part, on the use of context trees, and it includes a collection of effective algorithmic tools for learning and inference. A discrete context (or ‘state’) is extracted for each sample, consisting of a discretised version of some of the most recent observations preceding it. The set of all relevant contexts are represented as a discrete context tree. At the bottom level, a different real-valued time series model is associated with each context-state, i.e., with each leaf of the tree. This defines a very general framework that can be used in conjunction with any existing model class to build flexible and interpretable mixture models. Extending the idea of context-tree weighting leads to algorithms that allow for efficient, exact Bayesian inference in this setting. The utility of the general framework is illustrated in detail when autoregressive (AR) models are used at the bottom level, resulting in a nonlinear AR mixture model. The associated methods are found to outperform several state-of-the-art techniques on simulated and real-world experiments.

Estimating the entropy rate of discrete time series is a challenging problem with important applications in numerous areas including neuroscience, genomics, image processing and natural language processing. A number of approaches have been developed for this task, typically based either on universal data compression algorithms, or on statistical estimators of the underlying process distribution. In this work, we propose a fully-Bayesian approach for entropy estimation. Building on the recently introduced Bayesian Context Trees (BCT) framework for modelling discrete time series as variable-memory Markov chains, we show that it is possible to sample directly from the induced posterior on the entropy rate. This can be used to estimate the entire posterior distribution, providing much richer information than point estimates. We develop theoretical results for the posterior distribution of the entropy rate, including proofs of consistency and asymptotic normality. The practical utility of the method is illustrated on both simulated and real-world data, where it is found to outperform state-of-the-art alternatives.

An information-theoretic proof of a strengthened version of the classical discrete central limit theorem is presented. Using only information-theoretic and elementary arguments, convergence to zero of the relative entropy between the standardised sum of n independent and identically distributed lattice random variables and an appropriately discretised Gaussian is established.

The Context-Tree Weighting (CTW) algorithm and the accompanying collection of ideas and techniques have a long history of statistical applications in discrete time series analysis. CTW was recently revisited from a principled Bayesian statistics point of view, and a general modelling framework called Bayesian Context Trees (BCT) was introduced and found to be very effective in numerous core statistical tasks. In this work, a novel representation of the induced BCT posterior distribution on model space is derived in terms of a simple branching process, and several consequences of this are explored in theory and in practice. First, it is shown that it leads to a simple variable-dimensional Monte Carlo sampler for the joint posterior on models and parameters, which is found to be more efficient than earlier MCMC samplers for the same tasks. Then the branching process representation is used to establish the asymptotic consistency of the BCT posterior, including the derivation of an almost-sure convergence rate.

We review information-theoretic approaches to obtaining simple probabilistic representations for sequences of exchangeable random variables. Specifically, we examine information-theoretic proofs of finite versions of de Finetti’s celebrated representation theorem. Such results state, in a quantitative manner, that the joint distribution of the first k of n > k exchangeable random variables is close to a mixture of product distributions. Closeness is measured in terms of the relative entropy and explicit bounds are typically provided. First we review a recent information-theoretic proof a finite de Finetti theorem for binary random variables, and then we give a different, new proof for the case of arbitrary finite alphabets. This second proof is nicely motivated by the Gibbs conditioning principle in connection with statistical mechanics, and it follows along an appealing sequence of steps. The technical estimates required for these steps are obtained via the method of types.A full version of this paper is available online as [23].

Change-point detection for discrete time series is an important task with numerous applications. We develop a new hierarchical Bayesian framework for modelling inhomogeneous discrete time series with change-points. The distributions of different segments are modelled as variable-memory Markov chains, defining piece-wise homogeneous variable-memory chains. Building on the recently introduced Bayesian Context Trees framework, it is shown that the Context-Tree Weighting algorithm can be employed to compute the prior predictive likelihood of each segment, with all models and parameters integrated out. This is then used to develop a new class of effective Markov chain Monte Carlo algorithms for the posterior of the number and locations of change-points. These not only identify the most likely change-points, but also provide access to their entire posterior distribution. Estimates of the actual models in each segment can be obtained at negligible cost. Results on both synthetic and real-world data sets indicate that the proposed methodology performs better or as well as state-of-the-art techniques.

Graphical data and the network structures that support them are becoming increasingly common and important in engineering and scientific applications. In the context of data compression, such data can be examined at three levels. The structure of a graph can be described as its unlabeled version; the labeling of this structure can be added; and finally, given then structure and labeling, the contents of the labels can be described. In quantifying the amount of information present at each level, and in examining the relationships between them, the notions of symmetry, graph automorphism, and entropy, arise naturally. In this work we consider a class of small-world graphs, where vertices are first connected to their nearest neighbors on a circle and then pairs of non-neighbors are connected according to a distance-dependent distribution. We first determine the degree distribution of this model, and then use it to prove that the model is asymmetric in an appropriate range of parameters. Returning to graph compression, our main results are the computation of the entropy and of the structural entropy of these random graph models.

We revisit the statistical foundation of the celebrated context tree weighting (CTW) algorithm, and we develop a Bayesian modelling framework for the class of higher-order, variable-memory Markov chains, along with an associated collection of methodological tools for exact inference for discrete time series. In addition to deterministic algorithms that learn the a posteriori most likely models and compute their posterior probabilities, we introduce a family of variable-dimension Markov chain Monte Carlo samplers, facilitating further exploration of the posterior. The performance of the proposed methods in model selection, Markov order estimation and prediction is illustrated through simulation experiments and real-world applications.

The problem of lossless data compression with side information available to both the encoder and the decoder is considered. The finite-blocklength fundamental limits of the best achievable performance are defined, in two different versions of the problem: Reference-based compression, when a single side information string is used repeatedly in compressing different source messages, and pair-based compression, where a different side information string is used for each source message. General achievability and converse theorems are established for arbitrary source-side information pairs. Nonasymptotic normal approximation expansions are proved for the optimal rate in both the reference-based and pair-based settings, for memoryless sources. These are stated in terms of explicit, finite-blocklength bounds, that are tight up to third-order terms. Extensions that go significantly beyond the class of memoryless sources are obtained. The relevant source dispersion is identified and its relationship with the conditional varentropy rate is established. Interestingly, the dispersion is different in reference-based and pair-based compression, and it is proved that the reference-based dispersion is in general smaller.

The problem of lossless data compression with side information available to both the encoder and the decoder is considered. The finite-blocklength fundamental limits of the best achievable performance are defined, in two different versions of the problem: Reference-based compression, when a single side information string is used repeatedly in compressing different source messages, and pair-based compression, where a different side information string is used for each source message. General achievability and converse theorems are established. Nonasymptotic normal approximation expansions are proved for the optimal rate with memoryless sources, in both the reference-based and pair-based settings. These are stated in terms of explicit, finite-blocklength bounds, that are tight up to third-order terms. Extensions that go significantly beyond the class of memoryless sources are obtained. The relevant source dispersion is identified and its relationship with the conditional varentropy rate is established. Interestingly, the dispersion is different in reference-based and pair-based compression, and it is proved that the reference-based dispersion is in general smaller.

A mobile wireless delay-tolerant network (DTN) model is proposed and analyzed, in which infinitely many nodes are initially placed on R2according to a uniform Poisson point process (PPP) and subsequently travel, independently of each other, along trajectories comprised of line segments, changing travel direction at time instances that form a Poisson process, each time selecting a new travel direction from an arbitrary distribution; all nodes maintain constant speed. A single information packet is traveling towards a given direction using both wireless transmissions and sojourns on node buffers, according to a member of a class of utility-based routing rules. For this model, we compute the long-term averages of the speed with which the packet travels towards its destination and the rate with which the wireless transmission cost accumulates. Because of the complexity of the problem, we employ two intuitive, simplifying approximations; simulations show that the approximation error is typically small. Our results provide intuition on the fundamental trade-off that exists in mobile wireless DTNs between the packet speed and the packet delivery cost. The framework developed here is both general and versatile, and can be used as a starting point for further investigation.

The results of a series of theoretical studies are reported, examining the convergence rate for different approximate representations of α-stable distributions. Although they play a key role in modelling random processes with jumps and discontinuities, the use of α-stable distributions in inference often leads to analytically intractable problems. The LePage series, which is a probabilistic representation employed in this work, is used to transform an intractable, infinite-dimensional inference problem into a finite-dimensional (conditionally Gaussian) parametric problem. A major component of our approach is the approximation of the tail of this series by a Gaussian random variable. Standard statistical techniques, such as ExpectationMaximization (EM), Markov chain Monte Carlo, and Particle Filtering, can then be readily applied. In addition to the asymptotic normality of the tail of this series, we establish explicit, nonasymptotic bounds on the approximation error. Their proofs follow classical Fourier-analytic arguments, using Esséen's smoothing lemma. Specifically, we consider the distance between the distributions of: (i) the tail of the series and an appropriate Gaussian; (ii) the full series and the truncated series; and (iii) the full series and the truncated series with an added Gaussian term. In all three cases, sharp bounds are established, and the theoretical results are compared with the actual distances (computed numerically) in specific examples of symmetric αstable distributions. This analysis facilitates the selection of appropriate truncations in practice and offers theoretical guarantees for the accuracy of resulting estimates. One of the main conclusions obtained is that, for the purposes of inference, the use of a truncated series together with an approximately Gaussian error term has superior statistical properties and is likely a preferable choice in practice.

An infinite number of nodes move in ℝ2according to a random waypoint model; a single packet is traveling towards a destination (located at an infinite distance away) using combinations of wireless transmissions and physical transport on the buffers of nodes. In earlier work [1] we defined two performance metrics, namely, the long-term average speed with which the packet travels towards its destination, and the rate with which transmission cost accumulates with distance covered. Explicit expressions were derived for these metrics, under specific ergodicity assumptions. In this paper we give a precise description of the induced Markov process, we show that it is indeed (uniformly) geometrically ergodic, and that the law of large numbers holds for the random variables of interest. In particular, we show that the two performance metrics are well-defined and asymptotically constant with probability one.

We report the results of several theoretical studies into the convergence rate for certain random series representations of α -stable random variables, which are motivated by and find application in modelling heavy-tailed noise in time series analysis, inference, and stochastic processes. The use of α -stable noise distributions generally leads to analytically intractable inference problems. The particular version of the Poisson series representation invoked here implies that the resulting distributions are “conditionally Gaussian,” for which inference is relatively straightforward, although an infinite series is still involved. Our approach is to approximate the residual (or “tail”) part of the series from some point, c > 0, say, to ∞, as a Gaussian random variable. Empirically, this approximation has been found to be very accurate for large c. We study the rate of convergence, as c → ∞, of this Gaussian approximation. This allows the selection of appropriate truncation parameters, so that a desired level of accuracy for the approximate model can be achieved. Explicit, nonasymptotic bounds are obtained for the Kolmogorov distance between the relevant distribution functions, through the application of probability-theoretic tools. The theoretical results obtained are found to be in very close agreement with numerical results obtained in earlier work.

Over the past few years, a family of interesting new inequalities for the entropies of sums and differences of random variables has been developed by Ruzsa, Tao, and others, motivated by analogous results in additive combinatorics. This paper extends these earlier results to the case of random variables taking values in Rn or, more generally, in arbitrary locally compact and Polish abelian groups. We isolate and study a key quantity, the Ruzsa divergence between two probability distributions, and we show that its properties can be used to extend the earlier inequalities to the present general setting. The new results established include several variations on the theme that the entropies of the sum and the difference of two independent random variables severely constrain each other. Although the setting is quite general, the results are already of interest (and new) for random vectors in Rn. In that special case, we discuss quantitative bounds for the stability of the equality conditions in the entropy power inequality, a reverse entropy power inequality for log-concave random vectors, an information-theoretic analog of the Rogers-Shephard inequality for convex bodies, and consequences of some of our results to determinant inequalities for sums of positive-definite matrices. Moreover, by considering various multiplicative subgroups of the complex plane, one obtains new inequalities for the differential entropies of products and ratios of nonzero, complex-valued random variables.

We study a simple one-dimensional, discrete-time network model that consists of two nodes moving on a discrete circle, changing their direction of movement randomly, and a single packet travelling in the clockwise direction, using combinations of transmissions between the two nodes (when they are co-located) and physical transports on their buffers. In this setting, we provide exact, explicit expressions for the long-term averages of the packet speed and the wireless transmission cost. Our work is a first step towards providing simple and exact results for more realistic wireless delay-tolerant network models.

The problem of estimating the directed information rate between two discrete processes (Xn) and (Yn) via the plug-in (or maximum-likelihood) estimator is considered. When the joint process ((Xn, Yn)) is a Markov chain of a given memory length, the plug-in estimator is shown to be asymptotically Gaussian and to converge at the optimal rate O(1/√n) under appropriate conditions; this is the first estimator that has been shown to achieve this rate. An important connection is drawn between the problem of estimating the directed information rate and that of performing a hypothesis test for the presence of causal influence between the two processes. Under fairly general conditions, the null hypothesis, which corresponds to the absence of causal influence, is equivalent to the requirement that the directed information rate be equal to zero. In that case, a finer result is established, showing that the plug-in converges at the faster rate O(1/n) and that it is asymptotically χ2-distributed. This is proved by showing that this estimator is equal to (a scalar multiple of) the classical likelihood ratio statistic for the above hypothesis test. Finally, it is noted that these results facilitate the design of an actual likelihood ratio test for the presence or absence of causal influence.

The sumset and inverse sumset theories of Freiman, Plünnecke, and Ruzsa, give bounds connecting the cardinality of the sumset A + B = {a + b; a ∈ A, b ∈ B} of two discrete sets A, B, to the cardinalities (or the finer structure) of the original sets A, B. For example, the sum-difference bound of Ruzsa states that, |A + B| |A| |B| |A - B|3, where the difference set A - B = {a - b; a ∈ A, b ∈ B}. Interpreting the differential entropy h(X) of a continuous random variable X as (the logarithm of) the size of the effective support of X, the main contribution of this paper is a series of natural information-theoretic analogs for these results. For example, the Ruzsa sum-difference bound becomes the new inequality, h(X+Y)+h(X)+h(Y) ≤ 3h(X-Y), for any pair of independent continuous random variables X and Y. Our results include differential-entropy versions of Ruzsa's triangle inequality, the Plünnecke-Ruzsa inequality, and the Balog-Szemerédi-Gowers lemma. In addition, we give a differential entropy version of a Freiman-type inverse-sumset theorem, which can be seen as a quantitative converse to the entropy power inequality. Versions of most of these results for the discrete entropy H(X) were recently proved by Tao, relying heavily on a strong, functional form of the submodularity property of H(X). Since differential entropy is not functionally submodular, in the continuous case many of the corresponding discrete proofs fail, in many cases requiring substantially new proof strategies. We find that the basic property that naturally replaces the discrete functional submodularity, is the data processing property of mutual information.

This paper provides an extensive study of the behavior of the best achievable rate (and other related fundamental limits) in variable-length strictly lossless compression. In the non-asymptotic regime, the fundamental limits of fixed-to-variable lossless compression with and without prefix constraints are shown to be tightly coupled. Several precise, quantitative bounds are derived, connecting the distribution of the optimal code lengths to the source information spectrum, and an exact analysis of the best achievable rate for arbitrary sources is given. Fine asymptotic results are proved for arbitrary (not necessarily prefix) compressors on general mixing sources. Nonasymptotic, explicit Gaussian approximation bounds are established for the best achievable rate on Markov sources. The source dispersion and the source varentropy rate are defined and characterized. Together with the entropy rate, the varentropy rate serves to tightly approximate the fundamental nonasymptotic limits of fixed-to-variable compression for all but very small block lengths.

For the problem of lossless compression of a memoryless source, we give a detailed, precise characterization of the best achievable error probability, in the “moderate error probability” regime. This is the asymptotic setting where the probability of error decays to zero while at the same time the rate converges to the entropy at a speed no faster than 1/√N. These results combine some of the essential benefits of earlier analyses in terms of error exponents and of Gaussian approximation. Analogous results for the problem of hypothesis testing are also established.

This work1deals with the fundamental limits of strictly-lossless variable-length compression of known sources without prefix constraints. The source dispersion characterizes the time-horizon over which it is necessary to code in order to approach the entropy rate within a pre-specified tolerance. We show that for a large class of sources, the dispersion of the source is equal to the varentropy rate, defined as the asymptotic per-symbol variance of the information random variables. We focus on ergodic Markov chains, whose optimal encodings are shown to be asymptotically normal and to satisfy an appropriate laws of the iterated logarithm.

Motivated by a series of recently discovered inequalities for the sum and difference of discrete or continuous random variables [3], [5], [9], [10], we argue that the most natural, general form of these results is in terms of a special case of a mutual information, which we call the Ruzsa divergence between two probability distributions. This can be defined for arbitrary pairs of random variables taking values in any discrete (countable) set, on Rn, or in fact on any locally compact Hausdorff abelian group. We study the basic properties of the Rusza divergence and derive numerous consequences. In particular, we show that many of the inequalities in [3], [5], [9], [10] can be stated and proved in a unified way, extending their validity to the present general setting. For example, consequences of the basic properties of the Ruzsa divergence developed here include the fact that the entropies of the sum and the difference of two independent random vectors severely constrain each other, as well as entropy analogues of a number of results in additive combinatorics. Although the setting is quite general, the results are already of interest (and new) in the case of random vectors in Rn. For instance, another consequence in Rnis an entropic analogue (in the setting of log-concave distributions) of the Rogers-Shephard inequality for convex bodies.

The Plünnecke-Ruzsa sumset theory gives bounds connecting the cardinality of the sumset A + B defined as {a + b; a ϵ A, b ϵ B} with the cardinalities of the original sets A, B. For example, the sum-difference bound states that, |A+B| |A| |B| ≤ |A-B|3, where A-B = {a-b; a ϵ A, b ϵ B}. Interpreting the differential entropy h(X) as (the logarithm of) the size of the effective support of X, the main results here are a series of natural information-theoretic analogs for these bounds. For example, the sum-difference bound becomes the new inequality, h(X + Y) + h(X) + h(Y) ≤ 3h(X - Y), for independent X, Y. Our results include differential-entropy versions of Ruzsa's triangle inequality, the Plünnecke-Ruzsa inequality, and the Balog-Szemerédi-Gowers lemma. Versions of most of these results for the discrete entropy H(X) were recently proved by Tao, relying heavily on a strong, functional form of the submodularity property of H(X). Since differential entropy is not functionally submodular, in the continuous case many of the corresponding discrete proofs fail, in several cases requiring substantially new proof strategies. The basic property that naturally replaces functional submodularity is the data processing property of mutual information.

Consider the entropy increase h(Y + Y') - h(Y) of the sum of two continuous i.i.d. random variables Y, Y', and the corresponding entropy increase h(Y - Y') - h(Y) of their difference. We show that the ratio between these two quantities always lies between 1/2 and 2. This complements a recent result of Lapidoth and Pete, showing that the difference h(Y + Y') - h(Y - Y') may be arbitrarily large. Corresponding results are discussed for the discrete entropy, and connections are drawn with exciting recent mathematical work in the area of additive combinatorics.

Rényi'sthinningoperation on a discrete random variable is a natural discrete analog of the scaling operation for continuous random variables. The properties of thinning are investigated in an information-theoretic context, especially in connection with information-theoretic inequalities related to Poisson approximation results. The classical Binomial-to-Poisson convergence (sometimes referred to as the “law of small numbers”) is seen to be a special case of a thinning limit theorem for convolutions of discrete distributions. A rate of convergence is provided for this limit, and nonasymptotic bounds are also established. This development parallels, in part, the development of Gaussian inequalities leading to the information-theoretic version of the central limit theorem. In particular, a “thinning Markov chain” is introduced, and it is shown to play a role analogous to that of the Ornstein-Uhlenbeck process in connection to the entropy power inequality.

The Poisson distribution is known to have maximal entropy among all distributions (on the nonnegative integers) within a natural class. Interestingly, straightforward attempts to generalize this result to general compound Poisson distributions fail because the analogous result is not true in general. However, we show that the compound Poisson does indeed have a natural maximum entropy characterization when the distributions under consideration are log-concave. This complements the recent development by the same authors of an information-theoretic foundation for compound Poisson approximation inequalities and limit theorems.

We examine the compression-complexity trade-off of lossy compression algorithms that are based on a random code-book or a random database. Motivated, in part, by some recent results of Gupta-Verdu-Weissman (GVW) and their underlying connections with the pattern-matching scheme of Kontoyiannis' lossy Lempel-Ziv algorithm, we introduce a non-universal version of the lossy Lempel-Ziv method (termed LLZ), we prove its optimality for memoryless sources, and we compare its performance to that of the GVW divide-and-conquer approach. Experimental results indicate that the GVW approach often yields better compression than LLZ, but at the price of much higher memory requirements. To combine the advantages of both, we introduce a hybrid algorithm (HYB) that utilizes both the divide-and-conquer idea of GVW and the single-database structure of LLZ. We show that HYB shares with GVW the exact same rate-distortion performance and implementation complexity, while, like LLZ, requiring much less memory, typically by at least one or two orders of magnitude. Experimental results are also presented, illustrating the performance of all three methods on data generated by simple discrete memoryless sources. In particular, the HYB scheme is shown to outperform existing schemes for the compression of some simple discrete sources with respect to the Hamming distortion criterion.

The law of thin numbers is a Poisson approximation theorem related to the thinning operation. We use information projections to derive lower bounds on the information divergence from a thinned distribution to a Poisson distribution. Conditions for the existence of projections are given. If an information projection exists it must be an element of the associated exponential family. Exponential families are used to derive lower bounds on information divergence and lower bounds on the rate of convergence in the law of thin numbers. A method of translating results related to Poisson distributions into results related to Gaussian distributions is developed and used to prove a new non-trivial result related to the central limit theorem.

How many bits of information about an integer do we learn from each of its prime factors? Trying to answer that question in a precise manner leads to an elementary information-theoretic proof of a well-known, there is a given nontrivial result in number theory, namely that Sigmaplesn log p/p ~ log n as n rarr infin where the sum is over all primes p not exceeding n. In fact, we obtain finite-n bounds that refine this limit. This result, originally proved by Chebyshev in 1852, is closely related to the celebrated prime number theorem. Our main goal is to show that basic information-theoretic arguments combined with elementary computations can be used to give a new proof [2] for Chebyshev's classical result (1). The proof follows, in part, along the lines of a heuristic argument due to Billingsley [1]. We briefly outline the connection between Chebyshev's result and Gauss' prime number theorem, and also give a brief survey of other instances where information-theoretic ideas have been employed in the context of number theory.

Motivated by questions in lossy data compression and by theoretical considerations, the problem of estimating the rate–distortion function of an unknown (not necessarily discrete-valued) source from empirical data is examined. The focus is the behavior of the so-called “plug-in” estimator, which is simply the rate–distortion function of the empirical distribution of the observed data. Sufficient conditions are given for its consistency, and examples are provided demonstrating that in certain cases it fails to converge to the true rate–distortion function. The analysis of its performance is complicated by the fact that the rate–distortion function is not continuous in the source distribution; the underlying mathematical problem is closely related to the classical problem of establishing the consistency of maximum-likelihood estimators (MLEs). General consistency results are given for the plug-in estimator applied to a broad class of sources, including all stationary and ergodic ones. A more general class of estimation problems is also considered, arising in the context of lossy data compression when the allowed class of coding distributions is restricted; analogous results are developed for the plug-in estimator in that case. Finally, consistency theorems are formulated for modified (e.g., penalized) versions of the plug-in, and for estimating the optimal reproduction distribution.

We demonstrate the use of information-theoretic tools for the task of identifying segments of biomolecules (DNA or RNA) that are statistically correlated. We develop a precise and reliable methodology, based on the notion of mutual information, for finding and extracting statistical as well as structural dependencies. A simple threshold function is defined, and its use in quantifying the level of significance of dependencies between biological segments is explored. These tools are used in two specific applications. First, for the identification of correlations between different parts of the maize zmSRp32 gene. There, we find significant dependencies between the 5' untranslated region and its alternatively spliced exons. This observation may indicate the presence of as-yet unknown alternative splicing mechanisms or structural scaffolds. Second, using data from CODIS, we demonstrate that our approach is well suited for the problem of discovering short tandem repeats (STRs).

The "thinning" operation on a discrete random variable is the natural discrete analog of scaling a continuous variable, i.e., multiplying it by a constant. We examine the role and properties of thinning in the context of information-theoretic inequalities for Poisson approximation. The classical Binomial-to-Poisson convergence, often referred to as the "law of small numbers," is seen to be a special case of a thinning limit theorem for convolutions of discrete distributions. A rate of convergence is also provided for this limit. A Nash equilibrium is established for a channel game, where Poisson noise and a Poisson input are optimal strategies. Our development partly parallels the development of Gaussian inequalities leading to the information- theoretic version of the central limit theorem.

Fisher information plays a fundamental role in the analysis of Gaussian noise channels and in the study of Gaussian approximations in probability and statistics. For discrete random variables, the scaled Fisher information plays an analogous role in the context of Poisson approximation. Our first results show that it also admits a minimum mean squared error characterization with respect to the Poisson channel, and that it satisfies a monotonicity property that parallels the monotonicity recently established for the central limit theorem in terms of Fisher information. We next turn to the more general case of compound Poisson distributions on the nonnegative integers, and we introduce two new "local information quantities" to play the role of Fisher information in this context. We show that they satisfy subadditivity properties similar to those of classical Fisher information, we derive a minimum mean squared error characterization, and we explore their utility for obtaining compound Poisson approximation bounds.

We use statistical estimates of the entropy rate of spike train data in order to make inferences about the underlying structure of the spike train itself. We first examine a number of different parametric and nonparametric estimators (some known and some new), including the "plug-in" method, several versions of Lempel-Ziv-based compression algorithms, a maximum likelihood estimator tailored to renewal processes, and the natural estimator derived from the context-tree weighting method (CTW). The theoretical properties of these estimators are examined, several new theoretical results are developed, and all estimators are systematically applied to various types of synthetic data and under different conditions. Our main focus is on the performance of these entropy estimators on the (binary) spike trains of 28 neurons recorded simultaneously for a one-hour period from the primary motor and dorsal premotor cortices of a monkey. We show how the entropy estimates can be used to test for the existence of long-term structure in the data, and we construct a hypothesis test for whether the renewal process model is appropriate for these spike trains. Further, by applying the CTW algorithm we derive the maximum a posterior (MAP) tree model of our empirical data, and comment on the underlying structure it reveals

Suppose a string XEn1= (X1, X2, ..., Xn) is generated by a stationary memoryless source (Xn)nges1with unknown distribution P. When the source is finite-valued, the problem of estimating the entropy H(P) using the data XEn1has received a lot of attention. Perhaps the simplest method is the so-called plug-in estimator H(PXn), where PXEn1is the empirical distribution of the data XEn1. This estimator is always strongly consistent, that is, H(PXEn1)rarrH(P) with probability one, as nrarrinfin. In this work we consider the natural generalization of estimating the rate-distortion function R(D, P). Our motivation comes from questions in lossy data compression and from cases where the data under consideration do not take values in a discrete alphabet. Our primary focus is the asymptotic behavior of the plug-in estimator R(PXEn1, D). This estimator need not be consistent, but in many cases it is. Several extensions are also considered, including stationary ergodic sources, and instances where the rate-distortion function is defined over a restricted class of coding distributions

We consider the statistical problem of estimating the entropy of finite-alphabet data generated from an unknown stationary process. We examine a series of estimators, including: (1) The standard maximum-likelihood or "plug-in" estimator; (2) Four different estimators based on the family of Lempel-Ziv compression algorithms; (3) A different plug-in estimator especially tailored to renewal processes; and (4) The natural estimator derived from the Context-Tree Weighting method (CTW). Some of these estimators are well-known, and some are new. We first summarize numerous theoretical properties of these estimators: Conditions for consistency, estimates of their bias and variance, methods for approximating the estimation error and for obtaining confidence intervals. Several new theoretical results are developed. We show how the theory offers preliminary indications results offer guidelines for tuning the parameters involved in the estimation process. Then we present an extensive simulation study on various types of synthetic data and under various conditions. We compare their performance and comment on the strengths and weaknesses of the various methods. For each estimator, we develop a precise method for calculating the estimation error based on any specific data set. Finally we report the performance of these entropy estimators on the (binary) spike trains of 28 neurons recorded simultaneously for a one-hour period from the primary motor and dorsal premotor cortices of a quietly seated monkey not engaged in a task behavior. Based on joint work with Yun Gao and Elie Bienenstock.

We introduce a universal quantization scheme based on random coding, and we analyze its performance. This scheme consists of a source-independent random codebook (typically mismatched to the source distribution), followed by optimal entropy coding that is matched to the quantized codeword distribution. A single-letter formula is derived for the rate achieved by this scheme at a given distortion, in the limit of large codebook dimension. The rate reduction due to entropy coding is quantified, and it is shown that it can be arbitrarily large. In the special case of "almost uniform" codebooks (e.g., an independent and identically distributed (i.i.d.) Gaussian codebook with large variance) and difference distortion measures, a novel connection is drawn between the compression achieved by the present scheme and the performance of "universal" entropy-coded dithered lattice quantizers. This connection generalizes the "half-a-bit" bound on the redundancy of dithered lattice quantizers. Moreover, it demonstrates a strong notion of universality where a single "almost uniform" codebook is near optimal for any source and any difference distortion measure. The proofs are based on the fact that the limiting empirical distribution of the first matching codeword in a random codebook can be precisely identified. This is done using elaborate large deviations techniques, that allow the derivation of a new "almost sure" version of the conditional limit theorem.

Suppose we are allowed to observe two equally noisy versions of some signal X, where the level of the noise is fixed. We are given a choice: we can either observe two independent noisy versions of X, or two correlated ones. We show that, contrary to what classical statistical intuition suggests, it is often the case that correlated data is more valuable than independent data. We investigate this phenomenon in a variety of contexts, we give numerous examples for standard families of channels, and we present general sufficient conditions for deciding this dilemma. One of these conditions draws an interesting connection with the information-theoretic notion of "synergy," which has received a lot of attention in the neuroscience literature recently

We develop explicit, general bounds for the probability that the normalized partial sums of a function of a Markov chain on a general alphabet would exceed the steady-state mean of that function by a given amount. Our bounds combine simple information-theoretic ideas together with techniques from optimization and some fairly elementary tools from analysis. In one direction, we obtain a general bound for the important class of Doeblin chains; this bound is optimal, in the sense that in the special case of independent and identically distributed random variables it essentially reduces to the classical Hoeffding bound. In another direction, motivated by important problems in simulation, we develop a series of bounds in a form which is particularly suited to these problems, and which apply to the more general class of "geometrically ergodic" Markov chains

Using a simple inequality about the relative entropy, its so-called "tensorization property," we give a simple proof of a functional inequality which is satisfied by any compound Poisson distribution. This functional inequality belongs to the class of modified logarithmic Sobolev inequalities. We use it to obtain measure concentration bounds for compound Poisson distributions under a variety of assumptions on their tail behavior. In particular, we show how the celebrated "Herbst argument" can be modified to yield sub-exponential concentration bounds. For example, suppose Z is a compound Poisson random variable with values on the nonnegative integers, and let f be a function such that |f(k+1) - f(k)| les 1 for all k. Then, if the base distribution of Z does not have a finite moment-generating function but has finite moments up to some order L > 1, we show that the probability that f(Z) exceeds its mean by a positive amount t or more decays approximately like (const)middott-L, where the constant is explicitly identified. This appears to be one of the very first examples of concentration bounds with power-law decay

Suppose there is some discrete variable X of interest, which can only be observed after passing through 2 channels (Q and R). You are limited to n noisy observations of X and then must estimate the value of X. Your one control is a parameter k which determines the level of correlation in your observed data. Specifically, X is first transmitted through the channel Q n/k times to yield variables Y/sub 1/,..., Y/sub n/k/ and then each Y/sub i/ is transmitted through channel R k times to yield variables Z/sub i/,/sub 1/,..., Z/sub I,k/. How should k be chosen to maximize the probability of successfully guessing the correct value of X? While k /spl equiv/ 1 yields data points Z/sub i,1/ which are conditionally independent given the value of X, we find that this does not always mean that k /spl equiv/ 1 is the optimal choice. In fact, many simple situations yield cases where the optimal value of k is greater than 1. We explore this phenomenon and present both theoretical and empirical results.

Two new information-theoretic methods are introduced for establishing Poisson approximation inequalities. First, using only elementary information-theoretic techniques it is shown that, when S/sub n/=/spl Sigma//sub i=1//sup n/X/sub i/ is the sum of the (possibly dependent) binary random variables X/sub 1/,X/sub 2/,...,X/sub n/, with E(X/sub i/)=p/sub i/ and E(S/sub n/)=/spl lambda/, then D(P(S/sub n/)/spl par/Po(/spl lambda/)) /spl les//spl Sigma//sub i=1//sup n/p/sub i//sup 2/+[/spl Sigma//sub i=1//sup n/H(X/sub i/)-H(X/sub 1/,X/sub 2/,...,X/sub n/)] where D(P(S/sub n/)/spl par/Po(/spl lambda/)) is the relative entropy between the distribution of S/sub n/ and the Poisson (/spl lambda/) distribution. The first term in this bound measures the individual smallness of the X/sub i/ and the second term measures their dependence. A general method is outlined for obtaining corresponding bounds when approximating the distribution of a sum of general discrete random variables by an infinitely divisible distribution. Second, in the particular case when the X/sub i/ are independent, the following sharper bound is established: D(P(S/sub n/)/spl par/Po(/spl lambda/))/spl les/1//spl lambda/ /spl Sigma//sub i=1//sup n/ ((p/sub i//sup 3/)/(1-p/sub i/)) and it is also generalized to the case when the X/sub i/ are general integer-valued random variables. Its proof is based on the derivation of a subadditivity property for a new discrete version of the Fisher information, and uses a recent logarithmic Sobolev inequality for the Poisson distribution.

This paper describes the minimum description length principle in maximum likelihood estimate(MLE) in lossy data compression. In the lossless case the problem of optimal compression is theoretically equivalent to finding a probability distributions and minimizes the code-lengths.

The problem of approximating the distribution of a sum S/sub n/ = /spl Sigma//sub i=1//sup n/ Y/sub i/ of n discrete random variables Y/sub i/ by a Poisson or a compound Poisson distribution arises naturally in many classical and current applications, such as statistical genetics, dynamical systems, the recurrence properties of Markov processes and reliability theory. Using information-theoretic ideas and techniques, we derive a family of new bounds for compound Poisson approximation. We take an approach similar to that of Kontoyiannis, Harremoes and Johnson (2003), and we generalize some of their Poisson approximation bounds to the compound Poisson case. Partly motivated by these results, we derive a new logarithmic Sobolev inequality for the compound Poisson measure and use it to prove measure-concentration bounds for a large class of discrete distributions.

We consider the problem of lossy data compression for data arranged on two-dimensional arrays (such as images), or more generally on higher dimensional arrays (such as video sequences). Several of the most commonly used algorithms are based on pattern matching: Given a distortion level D and a block of data to be compressed, the encoder first finds a D-close match of this block into some database, and then describes the data by describing the position of the match. We consider two idealized versions of this scenario. In the first, the database is taken to be a collection of independent realizations of the same size and from the same distribution as the original data. In the second, the database is assumed to be a single long realization from the same source as the data. We show that the compression rate achieved (in either version) is no worse than R(D/2) bits per symbol, where R(D) is the rate-distortion function. This is proved under the assumptions that (1) the data is generated by a Gibbs distribution, and (2) the distortion measure is a metric, generalizing the corresponding one-dimensional bound of Steinberg and Gutman (1993). Using large deviations results by Dembo and Kontoyiannis (see ibid., vol.48, p.1590-15, 2000) and by Chi (2001), we are able to give short proofs for the present results.

Fundamental limits on the source coding exponents (or large deviations performance) of zero-delay finite-memory (ZDFM) lossy source codes are studied. Our main results are the following. For any memoryless source, a suitably designed encoder that time-shares (at most two) memoryless scalar quantizers is as good as any time-varying fixed-rate ZDFM code, in that it can achieve the fastest exponential rate of decay for the probability of excess distortion. A dual result is shown to apply to the probability of excess code length, among all fixed-distortion ZDFM codes with variable rate. Finally, it is shown that if the scope is broadened to ZDFM codes with variable rate and variable distortion, then a time-invariant entropy-coded memoryless quantizer (without time sharing) is asymptotically optimal under a "fixed-slope" large-deviations criterion (introduced and motivated here in detail) corresponding to a linear combination of the code length and the distortion. These results also lead to single-letter characterizations for the source coding error exponents of ZDFM codes.

We present a development of parts of rate-distortion theory and pattern-matching algorithms for lossy data compression, centered around a lossy version of the asymptotic equipartition property (AEP). This treatment closely parallels the corresponding development in lossless compression, a point of view that was advanced in an important paper of Wyner and Ziv in 1989. In the lossless case, we review how the AEP underlies the analysis of the Lempel-Ziv algorithm by viewing it as a random code and reducing it to the idealized Shannon code. This also provides information about the redundancy of the Lempel-Ziv algorithm and about the asymptotic behavior of several relevant quantities. In the lossy case, we give various versions of the statement of the generalized AEP and we outline the general methodology of its proof via large deviations. Its relationship with Barron (1985) and Orey's (1985, 1986) generalized AEP is also discussed. The lossy AEP is applied to (i) prove strengthened versions, of Shannon's(1948, 1974) direct source-coding theorem and universal coding theorems; (ii) characterize the performance of "mismatched" codebooks in lossy data compression; ( iii) analyze the performance of pattern-matching algorithms for lossy compression (including Lempel-Ziv schemes); and (iv) determine the first-order asymptotic of waiting times between stationary processes. A refinement to the lossy AEP is then presented, and it is used to (i) prove second-order (direct and converse) lossy source-coding theorems, including universal coding theorems; (ii) characterize which sources are quantitatively easier to compress; (iii) determine the second-order asymptotic of waiting times between stationary processes; and (iv) determine the precise asymptotic behavior of longest match-lengths between stationary processes. Finally, we discuss extensions of the above framework and results to random fields.

We characterize the best achievable performance of lossy compression algorithms operating on arbitrary random sources, and with respect to general distortion measures. Direct and converse coding theorems are given for variable-rate codes operating at a fixed distortion level, emphasizing: (a) nonasymptotic results, (b) optimal or near-optimal redundancy bounds, and (c) results with probability one. This development is based in part on the observation that there is a precise correspondence between compression algorithms and probability measures on the reproduction alphabet. This is analogous to the Kraft inequality in lossless data compression. In the case of stationary ergodic sources our results reduce to the classical coding theorems. As an application of these general results, we examine the performance of codes based on mixture codebooks for discrete memoryless sources. A mixture codebook (or Bayesian codebook) is a random codebook generated from a mixture over some class of reproduction distributions. We demonstrate the existence of universal mixture codebooks, and show that it is possible to universally encode memoryless sources with redundancy of approximately (d/2) log n bits, where d is the dimension of the simplex of probability distributions on the reproduction alphabet.

In a mobile wireless system, fading effects can be classified into large-scale (long-term) effects and small-scale (short-term) effects. We use transmission power control to compensate for large-scale fading and exploit receiver antenna (space) diversity to combat small-scale fading. We show that the interferences across the antennas are jointly Gaussian in a large system, and then characterize the signal-to-interference ratio for both independent and correlated (across the antennas) small-scale fading cases. Our results show that when each user's small-scale fading effects are independent across the antennas, there is a clear separation between the gains of transmission power control and diversity combining, and the two gains are additive (in decibels). When each user's small-scale fading effects are correlated across the antennas, we observe that, in general, the gains of transmission power control and diversity combining are coupled. However, when the noise level diminishes to zero, using maximum ratio combining "decouples" the gains and achieves the same diversity gain as in the independent case. We then characterize the Pareto-optimal (minimum) transmission power allocation for the cases of perfect and noisy knowledge of the desired user's large-scale fading effects. We find that using antenna diversity leads to significant gains for the transmission power.

The following critical phenomenon was recently discovered. When a memoryless source is compressed using a variable-length fixed-distortion code, the fastest convergence rate of the (pointwise) compression ratio to R(D) is either O(/spl radic/n) or O(log n). We show it is always O(/spl radic/n), except for discrete, uniformly distributed sources.

Suppose A is a finite set, let P be a discrete distribution on A, and let M be an arbitrary "mass" function on A. We give a precise characterization of the most efficient way in which A/sup n/ can be almost-covered using spheres of a fixed radius. An almost-covering is a subset C/sub n/ of A/sup n/, such that the union of the spheres centered at the points of C/sub n/ has probability close to one with respect to the product distribution P/sup n/. Spheres are defined in terms of a single-letter distortion measure on A/sup n/, and an efficient covering is one with small mass M/sup n/(C/sub n/). In information-theoretic terms, the sets C/sub n/ are rate-distortion codebooks, but instead of minimizing their size we seek to minimize their mass. With different choices for M and the distortion measure on A our results give various corollaries as special cases, including Shannon's classical rate-distortion theorem, a version of Stein's lemma (in hypothesis testing), and a new converse to some measure-concentration inequalities on discrete spaces. Under mild conditions, we generalize our results to abstract spaces and nonproduct measures.

In a wireless system, fading effects can be classified into large-scale effects and small-scale effects. We use power control to compensate for large-scale fading and exploit spatial diversity to combat small-scale fading. We characterize the SIR and our results show that when each user's small-scale fading effects are independent across the antennas, there is a clear separation between the gains of power control and diversity combining, and the two gains are additive (in decibels). We then characterise the Pareto-optimal transmission power allocation.

We characterize the achievable pointwise redundancy rates for lossy data compression at a fixed distortion level. "Pointwise redundancy" refers to the difference between the description length achieved by an nth-order block code and the optimal nR(D) bits. For memoryless sources, we show that the best achievable redundancy rate is of order O(/spl radic/n) in probability. This follows from a second-order refinement to the classical source coding theorem, in the form of a "one-sided central limit theorem". Moreover, we show that, along (almost) any source realization, the description lengths of any sequence of block codes operating at distortion level D exceed nR(D) by at least as much as C/spl radic/(nloglogn), infinitely often. Corresponding direct coding theorems are also given, showing that these rates are essentially achievable. The above rates are in sharp contrast with the expected redundancy rates of order O(log n) reported by various authors. Our approach is based on showing that the compression performance of an arbitrary sequence of codes is essentially bounded below by the performance of Shannon's random code. We obtain partial generalizations of the above results for arbitrary sources with memory, and we prove lossy analogs of "Barron's Lemma" (Barron 1985).

A new lossy variant of the fixed-database Lempel-Ziv coding algorithm for encoding at a fixed distortion level is proposed, and its asymptotic optimality and universality for memoryless sources (with respect to bounded single-letter distortion measures) is demonstrated: as the database size m increases to infinity, the expected compression ratio approaches the rate-distortion function. The complexity and redundancy characteristics of the algorithm are comparable to those of its lossless counterpart. A heuristic argument suggests that the redundancy is of order (log log m)/log m, and this is also confirmed experimentally; simulation results are presented that agree well with this rate. Also, the complexity of the algorithm is seen to be comparable to that of the corresponding lossless scheme. We show that there is a tradeoff between compression performance and encoding complexity, and we discuss how the relevant parameters can be chosen to balance this tradeoff in practice. We also discuss the performance of the algorithm when applied to sources with memory, and extensions to the cases of unbounded distortion measures and infinite reproduction alphabets.

We discuss a family of estimators for the entropy rate of a stationary ergodic process and prove their pointwise and mean consistency under a Doeblin-type mixing condition. The estimators are Cesaro averages of longest match-lengths, and their consistency follows from a generalized ergodic theorem due to Maker (1940). We provide examples of their performance on English text, and we generalize our results to countable alphabet processes and to random fields.

Shannon's celebrated source coding theorem can be viewed as a "one-sided law of large numbers". We formulate second-order noiseless source coding theorems for the deviation of the codeword lengths from the entropy. For a class of sources that includes Markov chains we prove a "one-sided central limit theorem" and a law of the iterated logarithm.

We prove an asymptotic relationship between certain longest match-lengths along a single realization of a stationary process and its entropy rate: Given a process X={X/sub n/;n/spl isin/Z} and a realization x from X, we define A/sub i//sup N/(x) as the length of the shortest substring, starting at x/sub i/, that does not appear as a contiguous substring of (x/sub i-N/,x/sub i-N+1/,...,x/sub i-1/). We consider stationary, ergodic processes that have a discrete (finite or infinite) alphabet and also satisfy the Doeblin condition (Kontoyiannis and Suhov, 1994).

We introduce a new framework for classifying large images (in the EOS; Earth Observing System) that is more accurate and less computationally expensive than the classical pixel-by-pixel approach. This approach, called progressive classification, is well suited for analyzing large images, such as multispectral satellite scenes, compressed with wavelet-based or block-transform-based transformations. These transformations produce a multiresolution pyramid representation of the data. A progressive classifier analyses the image at the coarsest resolution level, and it decides whether each coefficient corresponds to a homogeneous block of pixels in the original image or to a heterogeneous block. In the first case it labels the block, in the second case it recursively analyzes the region of the image at the immediately finer resolution level. Computational efficiency, compared to the classical approach, results from examining a much smaller number of coefficients than the number of pixels in the original image. Thus, progressive classification is a prime candidate as a content-based search operator for remotely-sensed data.