Generative models have shown impressive capabilities in synthesizing high-quality outputs across various domains. However, a persistent challenge is the occurrence of "hallucinations," where the model produces outputs that are not grounded in the underlying facts. While empirical strategies have been explored to mitigate this issue, a rigorous theoretical understanding remains elusive. In this paper, we develop a theoretical framework to analyze the *learnability* of non-hallucinating generative models from a learning-theoretic perspective. Our results reveal that non-hallucinating learning is statistically *impossible* when relying solely on the training dataset, even for a hypothesis class of size two and when the entire training set is truthful. To overcome these limitations, we show that incorporating *inductive biases* aligned with the actual facts into the learning process is essential. We provide a systematic approach to achieve this by restricting the fact set to a concept class of finite VC-dimension and demonstrate its effectiveness under various learning paradigms. Although our findings are primarily conceptual, they represent a first step towards a principled approach to addressing hallucinations in learning generative models.

We study the problem of learning from expert advice in the presence of perturbed noisy losses. Unlike existing work that assumes stochastic perturbations, we consider the case where the perturbation occurs arbitrarily, subject to a budget$C$on each expert—an approach we term “nasty” experts. The learner's performance is evaluated on the underlying true losses while only observing the perturbed noisy losses. Assuming the existence of an expert that incurs zero true losses, we show that the minimax risk equals$\Theta(C\log K)$for an expert class of size$K$. Remarkably, this risk cannot be achieved by the standard Exponentially Weighted Average (EWA) algorithm with constant learning rates, for which we establish a lower bound of$\Omega(C^{2}/\log K)$. We further demonstrate a nearly matching upper bound of$\overline{O}(C^{2}+C\log K)$for the EWA algorithm. Our main proof technique is based on a novel potential-based analysis that is of independent interest. Finally, we demonstrate the effectiveness of our nasty expert model in the context of binary classification with Massart's noise, without knowing the noise upper bound.

We study agnostic online learning from continuous-time data streams, a setting that naturally arises in applications such as environmental monitoring, personalized recommendation, and high-frequency trading. Unlike classical discrete-time models, learners in this setting must interact with a continually evolving data stream while making queries and updating models only at sparse, strategically selected times. We develop a general theoretical framework for learning from both *oblivious* and *adaptive* data streams, which may be noisy and non-stationary. For oblivious streams, we present a black-box reduction to classical online learning that yields a regret bound of $T \cdot R(S)/S$ for any class with discrete-time regret $R(S)$, where $T$ is the time horizon and $S$ is the *query budget*. For adaptive streams, which can evolve in response to learner actions, we design a dynamic query strategy in conjunction with a novel importance weighting scheme that enables unbiased loss estimation. In particular, for hypothesis class $\mathcal{H}$ with a finite Littlestone dimension, we establish a tight regret bound of $\tilde{\Theta}(T \cdot \sqrt{\mathsf{Ldim}(\mathcal{H})/S})$ that holds in both settings. Our results provide the first *quantitative* characterization of agnostic learning in continuous-time online environments with limited interaction.

Gradient estimation is a central challenge in training parameterized quantum circuits ( PQCs) for hybrid quantum-classical optimization and learning problems. This difficulty arises from several factors, including the exponential dimensionality of the Hilbert spaces and the information loss in quantum measurements. Existing estimators, such as finite difference and the parameter shift rule, often fail to adequately address these challenges for certain classes of PQCs. In this work, we propose a novel gradient estimation framework that leverages the underlying Lie algebraic structure of PQCs, combined with the Hadamard test. By analyzing the differential of the matrix exponential in Lie algebras, we derive an expression for the gradient as a linear combination of expectation values obtained via Hadamard tests. The coefficients in this decomposition depend solely on the circuit's parameterization and can be computed efficiently. Also, these expectation values can be estimated using state-of-the-art shadow tomography techniques. Our approach enables efficient gradient estimation, requiring a number of measurement shots that scales logarithmically with the number of parameters, and with polynomial classical and quantum time. This is an exponential reduction in the measurement cost and a polynomial speed-up in time compared to existing works.

We propose a novel gradient-based framework for learning parameterized quantum circuits (PQCs) in the presence of Pauli noise in gate operation. The key innovation in our framework is the simultaneous optimization of model parameters and learning of an inverse noise channel, specifically designed to mitigate Pauli noise. Our parametrized inverse noise model utilizes the Pauli-Lindblad equation and relies on the principle underlying the Probabilistic Error Cancellation (PEC) protocol to learn an effective and scalable mechanism for noise mitigation. In contrast to conventional approaches that apply predetermined inverse noise models during execution, our method systematically mitigates Pauli noise by dynamically updating the inverse noise parameters in conjunction with the model parameters, facilitating task-specific noise adaptation throughout the learning process. We employ proximal stochastic gradient descent (proximal SGD) to ensure that updates are bounded within a feasible range to ensure stability. This approach allows the model to converge efficiently to a stationary point, balancing the trade-off between noise mitigation and computational overhead, resulting in a highly adaptable quantum model that performs robustly in noisy quantum environments. Our framework is well-suited to near-term quantum devices in the noisy intermediate-scale quantum (NISQ) era, where noise is a significant challenge.

In online learning, a learner receives data in rounds and, at each round, predicts a label that is then compared to the true label, incurring a loss. The total loss overTrounds, when compared to the loss of the best expert from a class of experts or forecasters, is called the regret. In this paper, we focus on logarithmic loss for logistic-like experts withunbounded d-dimensional weights, a scenario that has been largely unexplored. To address the irregularities introduced by the unbounded weight norm, we introduce aregularizedversion of the average (fixed design) minimax regret by imposing asoft constrainton the weight norm. We demonstrate that the regularized minimax regret is fully characterized by a complexity measure we term the regularized Shtarkov sum. We also show how the behavior of the standard regret can be inferred from the regularized regret. Our main results provide aprecisecharacterization of the regularized Shtarkov sum and, consequently, the regularized regret with unbounded weights up to second-order asymptotics. Notably, unlike thed/2 logTregret growth known for bounded weights, our results imply that the regularized regret grows as (1/2+α/4)dlogTwhen the regularization parameter is of order Θ(T−α) for α ≤ 1/2. We achieve this using tools from analytic combinatorics, including multidimensional Fourier analysis, the saddle point method, and the Mellin transform.

We study the problem of online conditional distribution estimation with \emph{unbounded} label sets under local differential privacy. The problem may be succinctly stated as follows. Let $\mathcal{F}$ be a distribution-valued function class with an unbounded label set. Our aim is to estimate an \emph{unknown} function $f\in \mathcal{F}$ in an online fashion. More precisely, at time $t$, given a sample ${\mathbf{x}}_t$, we generate an estimate of $f({\mathbf{x}}_t)$ using only a \emph{privatized} version of the true \emph{labels} sampled from $f({\mathbf{x}}_t)$. The objective is to minimize the cumulative KL-risk of a finite horizon $T$. We show that under $(\epsilon,0)$-local differential privacy for the labels, the KL-risk equals $\tilde{\Theta}(\frac{1}{\epsilon}\sqrt{KT}),$ up to poly-logarithmic factors, where $K=|\mathcal{F}|$. This result significantly differs from the $\tilde{\Theta}(\sqrt{T\log K})$ bound derived in Wu et al., (2023a) for \emph{bounded} label sets. As a side-result, our approach recovers a nearly tight upper bound for the hypothesis selection problem of Gopi et al., (2020), which has only been established for the \emph{batch} setting.

We study the problem of oracle-efficient hybrid online learning when the features are generated by an unknown i.i.d. process and the labels are generated adversarially. Assuming access to an (offline) ERM oracle, we show that there exists a computationally efficient online predictor that achieves a regret upper bounded by $\tilde{O}(T^{\frac{3}{4}})$ for a finite-VC class, and upper bounded by $\tilde{O}(T^{\frac{p+1}{p+2}})$ for a class with $\alpha$ fat-shattering dimension $\alpha^{-p}$. This provides the first known oracle-efficient sublinear regret bounds for hybrid online learning with an unknown feature generation process. In particular, it confirms a conjecture of Lazaric and Munos (2012). We then extend our result to the scenario of shifting distributions with $K$ changes, yielding a regret of order $\tilde{O}(T^{\frac{4}{5}}K^{\frac{1}{5}})$. Finally, we establish a regret of $\tilde{O}((K^{\frac{2}{3}}(\log|\mathcal{H}|)^{\frac{1}{3}}+K)\cdot T^{\frac{4}{5}})$ for the contextual $K$-armed bandits with a finite policy set $\mathcal{H}$, i.i.d. generated contexts from an unknown distribution, and adversarially generated costs.

In online learning, a learner receives data in rounds 1$t T$and at each round predicts a label which is then compared to the true label resulting in a loss. The total loss over$T$rounds, when compared to a loss over the best expert from a class of experts, is called the regret. This paper focuses on logarithmic loss over a class of experts represented by a probability distribution$p$and parameterized by addimensional weight vector w. Unlike previous work that studied bounded weights, we assume that the norm of the weights can be unbounded. This unboundedness poses a challenging problem that leads to unexpected results. For such a class of weighted experts we analyze the (fixed design) minimax regret for the best predictor and worst label sequence. Such a minimax regret turns out to be a universal lower bound for most regrets analyzed in the literature. For bounded weights it is known that the minimax regret can grow like where$R$is an upper bound on the weight norm. In contrast, we show in this paper that for unbounded norm with$R$the minimax regret is asymptotically (d - 1) for a logistic-like expert class which we also extend to$R$We prove our findings by introducing the so called splittable label sequences that partition the weight space into regions with maximum sequence probability equal to 1. Finally, for a general class of monotone experts we present an upper bound 2d log$T$for the regret.

This paper studies quantum supervised learning for classical inference from quantum states. In this model, a learner has access to a set of labeled quantum samples as the training set. The objective is to find a quantum measurement that predicts the label of the unseen samples. The hardness of learning is measured via sample complexity under a quantum counterpart of the well-known probably approximately correct (PAC). Quantum sample complexity is expected to be higher than classical one, because of the measurement incompatibility and state collapse. Recent efforts showed that the sample complexity of learning a finite quantum concept class$\mathcal{C}$scales as$O(\vert \mathcal{C}\vert)$. This is significantly higher than the classical sample complexity that grows logarithmically with the class size. This work improves the sample complexity bound to$O\left(V_{\mathcal{C}^*} \log \left\vert\mathcal{C}^*\right\vert\right)$, where$\mathcal{C}^*$is the set of extreme points of the convex closure of$\mathcal{C}$and$V_{\mathcal{C}^*}$is the shadow-norm of this set. We show the tightness of our bound for the class of bounded Hilbert-Schmidt norm, scaling as$O\left(\log \left\vert\mathcal{C}^*\right\vert\right)$. Our approach is based on a new quantum empirical risk minimization (ERM) algorithm equipped with a shadow tomography method.

Theoretical results show that Bayesian methods can achieve lower bounds on regret for online logistic regression. In practice, however, such techniques may not be feasible especially for very large feature sets. Various approximations that, for huge sparse feature sets, diminish the theoretical advantages, must be used. Often, stochastic gradient methods is used with hyper-parameters that must be tuned on some surrogate loss, defeating theoretical advantages of Bayesian methods. The surrogate loss, defined to approximate the mixture, requires techniques as Monte Carlo sampling, increasing computations per example. We propose low complexity algorithm for sparse online logistic and probit regressions that runs linearly in time horizon. Unlike variational inference and other methods, our methods use analytical closed forms, substantially lowering computations. Unlike dense solutions, as Gaussian Mixtures, our methods allow for sparse problems with huge feature sets without increasing complexity. With the analytical closed forms, there is also no need for applying stochastic gradient methods on surrogate losses, and for tuning and balancing learning and regularization hyper-parameters. Empirical results top the performance of the more computationally involved methods.

We study online classification with general hypothesis classes where the true labels are determined by some function within the class, but are corrupted by *unknown* stochastic noise, and the features are generated adversarially. Predictions are made using observed *noisy* labels and noiseless features, while the performance is measured via minimax risk when comparing against *true* labels. The noisy mechanism is modeled via a general noisy kernel that specifies, for any individual data point, a set of distributions from which the actual noisy label distribution is chosen. We show that minimax risk is *tightly* characterized (up to a logarithmic factor of the hypothesis class size) by the *Hellinger gap* of the noisy label distributions induced by the kernel, *independent* of other properties such as the means and variances of the noise. Our main technique is based on a novel reduction to an online comparison scheme of two hypotheses, along with a new *conditional* version of Le Cam-Birgé testing suitable for online settings. Our work provides the first comprehensive characterization of noisy online classification with guarantees that apply to the *ground truth* while addressing *general* noisy observations.

Abstract. We present a rigorous and precise analysis of the maximum degree and the average degree in a dynamic duplication-divergence graph model introduced by Solé et al. [ Adv. Complex Syst., 5 (2002), pp. 43–54] in which the graph grows according to a duplication-divergence mechanism, i.e., by iteratively creating a copy of some node and then randomly alternating the neighborhood of a new node with probability [Formula: see text]. This model captures the growth of some real-world processes, e.g., biological or social networks. In this paper, we prove that for some [Formula: see text], the maximum degree and the average degree of a duplication-divergence graph on [Formula: see text] vertices are asymptotically concentrated with high probability around [Formula: see text] and [Formula: see text], respectively, i.e., they are within at most a polylogarithmic factor from these values with probability at least [Formula: see text] for any constant [Formula: see text].

Motivated by the limited qubit capacity of current quantum systems, we study the quantum sample complexity of k-qubit quantum operators, i.e., operations applicable on only k out of d qubits. The problem is studied according to the quantum probably approximately correct (QPAC) model abiding by quantum mechanical laws such as no-cloning, state collapse, and measurement incompatibility. With the delicacy of quantum samples and the richness of quantum operations, one expects a significantly larger quantum sample complexity. This paper proves the contrary. We show that the quantum sample complexity of k-qubit quantum operations is comparable to the classical sample complexity of their counterparts (juntas), at least when $\frac{k}{d}\ll 1$. This is surprising, especially since sample duplication is prohibited, and measurement incompatibility would lead to an exponentially larger sample complexity with standard methods. Our approach is based on the Pauli decomposition of quantum operators and a technique called Quantum Shadow Sampling (QSS) to reduce the sample complexity exponentially. The results are proved by developing (i) a connection between the learning loss and the Pauli decomposition; (ii) a scalable QSS circuit for estimating the Pauli coefficients; and (iii) a quantum algorithm for learning $k$-qubit operators with sample complexity $O(\frac{k4^k}{\epsilon^2}\log d)$.

Many conventional learning algorithms rely on loss functions other than the natural 0-1 loss for computational efficiency and theoretical tractability. Among them are approaches based on absolute loss (L1 regression) and square loss (L2 regression). The first is proved to be an agnostic PAC learner for various important concept classes such as juntas, and half-spaces. On the other hand, the second is preferable because of its computational efficiency which is linear in the sample size. However, PAC learnability is still unknown as guarantees have been proved only under distributional restrictions. The question of whether L2 regression is an agnostic PAC learner for 0-1 loss has been open since 1993 and yet has to be answered. This paper resolves this problem for the junta class on the Boolean cube — proving agnostic PAC learning of k-juntas using L2 polynomial regression. Moreover, we present a new PAC learning algorithm based on the Boolean Fourier expansion with lower computational complexity. Fourier-based algorithms, such as Linial et al. (1993), have been used under distributional restrictions, such as uniform distribution. We show that with an appropriate change one can apply those algorithms in agnostic settings without any distributional assumption. We prove our results by connecting the PAC learning with 0-1 loss to the minimum mean square estimation (MMSE) problem. We derive an elegant upper bound on the 0-1 loss in terms of the MMSE error based on that, we show that the sign of the MMSE is a PAC learner for any concept class containing it.

We study the problem of online learning and online regret minimization when samples are drawn from a general unknown \emph{non-stationary} process. We introduce the concept of a \emph{dynamic changing process} with cost $K$, where the \emph{conditional} marginals of the process can vary arbitrarily, but that the number of different conditional marginals is bounded by $K$ over $T$ rounds. For such processes we prove a tight (upto $\sqrt{\log T}$ factor) bound $O(\sqrt{KT\cdot\vch\log T})$ for the \emph{expected worst case} regret of any finite VC-dimensional class $\mathcal{H}$ under absolute loss (i.e., the expected miss-classification loss). We then improve this bound for general mixable losses, by establishing a tight (up to $\log^3 T$ factor) regret bound $O(K\cdot\vch\log^3 T)$. We extend these results to general \emph{smooth adversary} processes with \emph{unknown} reference measure by showing a sub-linear regret bound for $1$-dimensional threshold functions under a general bounded convex loss. Our results can be viewed as a first step towards regret analysis with non-stationary samples in the \emph{distribution blind} (universal) regime. This also brings a new viewpoint that shifts the study of complexity of the hypothesis classes to the study of the complexity of processes generating data.

We study the problem of learning functional distributions in the presence of noise. A functional is a map from the space of features to *distributions* over a set of labels, and is often assumed to belong to a known class of hypotheses $\mathcal{F}$. Features are generated by a general random process and labels are sampled independently from feature-dependent distributions. In privacy sensitive applications, labels are passed through a noisy kernel. We consider *online learning*, where at each time step, a predictor attempts to predict the *actual* (label) distribution given only the features and *noisy* labels in prior steps. The performance of the predictor is measured by the expected KL-risk that compares the predicted distributions to the underlying truth. We show that the *minimax* expected KL-risk is of order $\tilde{\Theta}(\sqrt{T\log|\mathcal{F}|})$ for finite hypothesis class $\mathcal{F}$ and *any* non-trivial noise level. We then extend this result to general infinite classes via the concept of *stochastic sequential covering* and provide matching lower and upper bounds for a wide range of natural classes.

We study sequential probability assignment in the context of online learning under logarithmic loss and obtain tight lower and upper bounds for sequential minimax regret. Sequential minimax regret is defined as the minimum excess loss over data horizon$T$that a predictor incurs over the best expert in a class, when the samples are presented sequentially and adversarially. Our upper bounds are established by applying Bayesian averaging over a novel “smooth truncated covering” of the expert class. This allows us to obtain tight (minimax) upper bounds that subsume the best known non-constructive bounds in an algorithmic fashion. For lower bounds, we reduce the problem to analyzing the fixed design regret via a novel application of Shtarkov sum adapted to online learning. We demonstrate the effectiveness of our approach by establishing tight regret bounds for a wide range of expert classes. In particular, we fully characterize the regret of generalized linear function with worst Lipschitz transform functions when the parameters are restricted to a unit norm$\ell _{s}$($s\ge 2$) ball of dimension$d$. We show that the regret grows as$\Theta (d\log T)$when$d\le O(T^{s/(s+1)-\epsilon })$for all$\epsilon >0$(with precise constant 1 when$d\le e^{o(\log T)}$) and$\tilde {O}(T^{s/(s+1)})$when$d\ge \Omega (T^{s/(s+1)})$. Finally, we show that the Bayesian approach may not always be optimal if the support of the prior is included in the reference class itself.

There has been significant recent interest in quantum neural networks (QNNs), along with their applications in diverse domains. Current solutions for QNNs pose significant challenges concerning their scalability, ensuring that the postulates of quantum mechanics are satisfied and that the networks are physically realizable. The exponential state space of QNNs poses challenges for the scalability of training procedures. The no-cloning principle prohibits making multiple copies of training samples, and the measurement postulates lead to non-deterministic loss functions. Consequently, the physical realizability and efficiency of existing approaches that rely on repeated measurement of several copies of each sample for training QNNs are unclear. This paper presents a new model for QNNs that relies on band-limited Fourier expansions of transfer functions of quantum perceptrons (QPs) to design scalable training procedures. This training procedure is augmented with a randomized quantum stochastic gradient descent technique that eliminates the need for sample replication. We show that this training procedure converges to the true minima in expectation, even in the presence of non-determinism due to quantum measurement. Our solution has a number of important benefits: (i) using QPs with concentrated Fourier power spectrum, we show that the training procedure for QNNs can be made scalable; (ii) it eliminates the need for resampling, thus staying consistent with the no-cloning rule; and (iii) enhanced data efficiency for the overall training process since each data sample is processed once per epoch. We present a detailed theoretical foundation for our models and methods' scalability, accuracy, and data efficiency. We also validate the utility of our approach through a series of numerical experiments.

In this work, we consider the problem of recovery a planted k-densest sub-hypergraph on d-uniform hypergraphs. This fundamental problem appears in different contexts, e.g., community detection, average-case complexity, and neuroscience applications as a structural variant of tensor-PCA problem. We provide tight information-theoretic upper and lower bounds for the exact recovery threshold by the maximum-likelihood estimator, as well as algorithmic bounds based on approximate message passing algorithms. The problem exhibits a typical statistical-to-computational gap observed in analogous sparse settings that widen with increasing sparsity of the problem. The bounds show that the signal structure impacts the location of the statistical and computational phase transition that the known existing bounds for the tensor-PCA model do not capture. This effect is due to the generic planted signal prior that this latter model addresses.

We study online logistic regression with binary labels and general feature values in which a learner tries to predict an outcome/ label based on data/ features received in rounds. Our goal is to evaluate precisely the (maximal) minimax regret which we analyze using a unique and novel combination of information-theoretic and analytic combinatorics tools such as Fourier transform, saddle point method, and Mellin transform in the multi-dimensional settings. To be more precise, the pointwise regret of an online algorithm is defined as the (excess) loss it incurs over a constant comparator which is used for prediction. In the minimax scenario we seek the best learning distribution for the worst label sequence. For dimension d = o(T1/3) we show that the maximal minimax regret grows as $d/2 \cdot \log (2T/\pi ) + {C_d} + O\left({{d^{3/2}}/\sqrt T }\right)$ where T is the number of rounds of running a training algorithm and Cdis explicitly computable constant that depends on dimension d and feature values. We compute explicitly the constant Cdfor features uniformly distributed on a d-dimensional sphere or ball.

In source coding since Davisson’s seminal paper [1] various redundancy and regrets were thoroughly analyzed, from pointwise redundancy, to average and maximal minimax and maxmin regrets. Similarly, in online learning, there are various formulations of regrets that are grouped into fixed-design (when data is known in advance) and sequential. This position paper gives a brief overview of current formulations of regrets, and provides a thorough comparison of the sequential and fixed design formulations. Moreover, inspired by the source coding literature, new classes of regrets, from average to worst case minimax, are introduced. In particular, it is shown that the fixed design and sequential regrets are equal in the worst case and average sense when data is known in advance; but, in maximal sense (when maximizing over data), the former can be significantly smaller than the latter. Specifically, this paper proves that under logarithmic loss (i) for linear predictors the two maximal formulations are of the same order; and (ii) for linear threshold predictors, fixed design maximal regret is logarithmically smaller than the sequential one.

We study sequential general online regression, known also as sequential probability assignments, under logarithmic loss when compared against a broad class of experts. We obtain tight, often matching, lower and upper bounds for sequential minimax regret, which is defined as the excess loss incurred by the predictor over the best expert in the class. After proving a general upper bound we consider some specific classes of experts from Lipschitz class to bounded Hessian class and derive matching lower and upper bounds with provably optimal constants. Our bounds work for a wide range of values of the data dimension and the number of rounds. To derive lower bounds, we use tools from information theory (e.g., Shtarkov sum) and for upper bounds, we resort to new "smooth truncated covering" of the class of experts. This allows us to find constructive proofs by applying a simple and novel truncated Bayesian algorithm. Our proofs are substantially simpler than the existing ones and yet provide tighter (and often optimal) bounds.

Many current applications in data science need rich model classes to adequately represent the statistics that may be driving the observations. Such rich model classes may be too complex to admit uniformly consistent estimators. In such cases, it is conventional to settle for estimators with guarantees on convergence rate where the performance can be bounded in a model-dependent way, i.e. pointwise consistent estimators. But this viewpoint has the practical drawback that estimator performance is a function of the unknown model within the model class that is being estimated. Even if an estimator is consistent, how well it is doing at any given time may not be clear, no matter what the sample size of the observations. In these cases, a line of analysis favors sample dependent guarantees. We explore this framework by studying rich model classes that may only admit pointwise consistency guarantees, yet enough information about the unknown model driving the observations needed to gauge estimator accuracy can be inferred from the sample at hand. In this paper we obtain a novel characterization of lossless compression problems over a countable alphabet in the data-derived framework in terms of what we term deceptive distributions. We also show that the ability to estimate the redundancy of compressing memoryless sources is equivalent to learning the underlying single-letter marginal in a data-derived fashion. We expect that the methodology underlying such characterizations in a data-derived estimation framework will be broadly applicable to a wide range of estimation problems, enabling a more systematic approach to data-derived guarantees.

A fundamental challenge in learning is the presence of nonlinear redundancies and dependencies in the data. To address this, we propose a Fourier-based approach to characterize feature redundancies, in unsupervised learning, and feature-label dependencies, in the supervised variant of the problem. We first develop a novel Fourier expansion for functions (more generally stochastic mappings) of correlated binary random variables. This is a generalization of the standard Fourier expansion on the Boolean cube beyond product probability spaces. As an important application of this analysis, we investigate learning with feature subset selection. In the unsupervised variant of this problem, we characterize feature redundancies via the Shannon entropy and group the features into sufficiently informative and redundant. Then, we make a connection to the proposed Fourier expansion and derive an upper bound on the joint entropy. Based on that, we propose a measure to quantify feature redundancies and present an unsupervised learning algorithm. We test our method on various real-world and synthetic datasets and demonstrate improvements on conventional unsupervised feature selection techniques. Then, we investigate the supervised feature subset selection and reformulate it in the Fourier domain. Bridging the Bayesian error rate with the Fourier coefficients, we demonstrate that the Fourier expansion provides a powerful tool to characterize nonlinear feature-label dependencies. Further, we introduce a computationally efficient measure for selecting relevant features. Via a theoretical analysis, we show that our proposed measure finds provablyasymptotically optimalfeature subsets. Lastly, we present an algorithm based on this measure and via numerical experiments demonstrate its improvements on various supervised feature selection algorithms.

We study logistic regression with binary labels and categorical (discrete) feature values. Our goal is to evaluate precisely the (maximal) minimax regret. We express it as the so called Shtarkov sum known in information theory. To the best of our knowledge such a sum was never computed in the context of logistic regression. To be more precise, the pointwise regret of an online algorithm is defined as the (excess) loss it incurs over some value of a constant comparator (weight vector) that is used for prediction. It depends on the feature values, label sequence, and the learning algorithm. In the maximal minimax scenario we seek the best weights for the worst label sequence over all possible learning algorithms/ distributions, therefore it constitutes a lower bound for the pointwise regret. For finite dimension $d$ and $N$ distinct feature vectors we show that the maximal minimax regret grows as $$ \frac{d}{2} \log (T/2\pi)+C_d + O(N/\sqrt{T}) $$ where $T$ is the number of rounds of running a training algorithm and $C_d$ is explicitly computable constant that depends on the feature values and dimension $d$. We also extend these results to non-binary labels. The {\it precise} maximal minimax regret presented here is the first result of this kind. Our findings are obtained using tools of analytic combinatorics and information theory.

A fundamental obstacle in learning information from data is the presence of nonlinear redundancies and dependencies in it. To address this, we propose a Fourier-based approach to extract relevant information in the supervised setting. We first develop a novel Fourier expansion for functions of correlated binary random variables. This expansion is a generalization of the standard Fourier analysis on the Boolean cube beyond product probability spaces. We further extend our Fourier analysis to stochastic mappings. As an important application of this analysis, we investigate learning with feature subset selection. We reformulate this problem in the Fourier domain and introduce a computationally efficient measure for selecting features. Bridging the Bayesian error rate with the Fourier coefficients, we demonstrate that the Fourier expansion provides a powerful tool to characterize nonlinear dependencies in the features-label relation. Via theoretical analysis, we show that our proposed measure finds provably asymptotically optimal feature subsets. Lastly, we present an algorithm based on our measure and verify our findings via numerical experiments on various datasets.

We study the problem of estimating a rank-1additive deformation of a Gaussian tensor according to the maximum-likelihood estimator (MLE). The analysis is carried out in the sparse setting, where the underlying signal has a support that scales sublinearly with the total number of dimensions. We show that for Bernoulli distributed signals, the MLE undergoes an all-or-nothing (AoN) phase transition, already established for the minimum mean-square-error estimator (MMSE) in the same problem. The result follows from two main technical points: (i) the connection established between the MLE and the MMSE, using the first and second-moment methods in the constrained signal space, (ii) a recovery regime for the MMSE stricter than the simple error vanishing characterization given in the standard AoN, that is here proved as a general result. A full version of this paper is accessible at: https://arxiv.org/pdf/2101.09994.pdf

Over decades traditional information theory of source and channel coding advances toward learning and effective extraction of information from data. We propose to go one step further and offer a theoretical foundation for learning classical patterns from quantum data. However, there are several roadblocks to lay the groundwork for such a generalization. First, classical data must be replaced by a density operator over a Hilbert space. Hence, deviated from problems such as state tomography, our samples are i.i.d density operators. The second challenge is even more profound since we must realize that our only interaction with a quantum state is through a measurement which - due to no-cloning quantum postulate - loses information after measuring it. With this in mind, we present a quantum counterpart of the well-known probably approximately correct (PAC) framework. Based on that, we propose a quantum analogous of the Empirical Risk Minimization (ERM) algorithm for learning measurement hypothesis classes. Then, we establish upper bounds on the quantum sample complexity quantum concept classes.

We take an information-theoretic approach to identify nonlinear feature redundancies in unsupervised learning. We define a subset of features as sufficiently-informative when the joint entropy of all the input features equals that of the chosen subset. We argue that the rest of the features are redundant as all the accessible information about the data can be captured from sufficiently-informative features. Next, instead of directly estimating the entropy, we propose a Fourier-based characterization. For that, we develop a novel Fourier expansion on the Boolean cube incorporating correlated random variables. This generalization of the standard Fourier analysis is beyond product probability spaces. Based on our Fourier framework, we propose a measure of redundancy for features in the unsupervised settings. We then consider a variant of this measure with a search algorithm to reduce its computational complexity as low as$O$(nd) with$n$being the number of samples and$d$the number of features. Besides the theoretical justifications, we test our method on various real-world and synthetic datasets. Our numerical results demonstrate that the proposed method outperforms state-of-the-art feature selection 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 study logistic regression with binary features in which the number (or degree) of occurring features determines the label probability. This model fits one of social networks, where the number of friends determines the likelihood of outcomes instead of the identity of the friends, or more generally, a graph model, where the degree of a node can determine its structure. It includes the case in which weights can be viewed as i.i.d. (e.g., in Bayesian modeling). For such a model, we introduce the maximal minimax regret that we analyze using a unique combination of analytic combinatorics and information theory. More importantly, the resulting regret is a general lower bound for the pointwise regret of a general logistic regression over all algorithms (learning distributions). We show that the introduced worst case (maximum over feature sequences) maximal minimax regret grows asymptotically as$(d/2)\log(T/d)+(d/2)\log(\pi/2)+O(d/\sqrt{T})$for dimensionality$d=o(\sqrt{T})$, which is a lower bound for a regret of a general logistic regression. We extend our results to loss functions other than logistic loss and non-binary labels.

Graph models often give us a deeper understanding of real-world networks. In the case of biological networks they help in predicting the evolution and history of biomolecule interactions, provided we map properly real networks into the corresponding graph models. In this paper, we show that for biological graph models many of the existing parameter estimation techniques overlook the critical property of graph symmetry (also known formally as graph automorphisms), thus the estimated parameters give statistically insignificant results concerning the observed network. To demonstrate it and to develop accurate estimation procedures, we focus on the biologically inspired duplication-divergence model, and the up-to-date data of protein-protein interactions of seven species including human and yeast. Using exact recurrence relations of some prominent graph statistics, we devise a parameter estimation technique that provides the right order of symmetries and uses phylogenetically old proteins as the choice of seed graph nodes. We also find that our results are consistent with the ones obtained from maximum likelihood estimation (MLE). However, the MLE approach is significantly slower than our methods in practice.

Numerous networks in the real world change over time, in the sense that nodes and edges enter and leave the networks. Various dynamic random graph models have been proposed to explain the macroscopic properties of these systems and to provide a foundation for statistical inferences and predictions. It is of interest to have a rigorous way to determine how well these models match observed networks. We thus ask the following goodness of fit question: given a sequence of observations/snapshots of a growing random graph, along with a candidate model $M$, can we determine whether the snapshots came from $M$ or from some arbitrary alternative model that is well-separated from $M$ in some natural metric? We formulate this problem precisely and boil it down to goodness of fit testing for graph-valued, infinite-state Markov processes and exhibit and analyze a universal test based on non-stationary sampling for a natural class of models.

Lempel-Ziv'78 is one of the most popular data compression algorithms. Over the last few decades fascinating properties of LZ78 were uncovered. Among others, in 1995 we settled the Ziv conjecture by proving that for a memoryless source the number of LZ78 phrases satisfies the Central Limit Theorem (CLT). Since then the quest commenced to extend it to Markov sources. However, despite several attempts this problem is still open. The 1995 proof of the Ziv conjecture was based on two models: In the DST-model, the associated digital search tree (DST) is built over m independent strings. In the LZ-model a single string of length n is partitioned into variable length phrases such that the next phrase is not seen in the past as a phrase. The Ziv conjecture for memoryless source was settled by proving that both DST-model and the LZ-model are asymptotically equivalent. The main result of this paper shows that this is not the case for the LZ78 algorithm over Markov sources. In addition, we develop here a large deviation for the number of phrases in the LZ78 and give a precise asymptotic expression for the redundancy which is the excess of LZ78 code over the entropy of the source. We establish these findings using a combination of combinatorial and analytic tools. In particular, to handle the strong dependency between Markov phrases, we introduce and precisely analyze the so called tail symbol which is the first symbol of the next phrase in the LZ78 parsing.

We study the partial duplication dynamic graph model, introduced by Bhan et al. in [Bhan et al., 2002] in which a newly arrived node selects randomly an existing node and connects with probability p to its neighbors. Such a dynamic network is widely considered to be a good model for various biological networks such as protein-protein interaction networks. This model is discussed in numerous publications with only a few recent rigorous results, especially for the degree distribution. Recently Jordan [Jordan, 2018] proved that for 0 < p < 1/e the degree distribution of the connected component is stationary with approximately a power law. In this paper we rigorously prove that the tail is indeed a true power law, that is, we show that the degree of a randomly selected node in the connected component decays like C/k^β where C an explicit constant and β ≠ 2 is a non-trivial solution of p^(β-2) + β - 3 = 0. This holds regardless of the structure of the initial graph, as long as it is connected and has at least two vertices. To establish this finding we apply analytic combinatorics tools, in particular Mellin transform and singularity analysis.

Given a single snapshot of a dynamic network in which nodes arrived at distinct time instants along with edges, we aim at inferring a partial order σ between the node pairs such that uσv indicates node u arrived earlier than node v in the graph. The inferred partial order can be deduced to a natural clustering of the nodes into K ordered clusters C1Ksuch that for iijoined the network before nodes in cluster Cj, with K being a data-driven parameter and not known upfront. We first formulate our problem for a general dynamic graph, and propose an integer programming framework that finds the optimal partial order, achieving the best precision (i.e., fraction of successfully ordered node pairs) for a fixed density (i.e., fraction of comparable node pairs). We then design algorithms to find temporal ordered clusters that efficiently approximate the optimal solution. To illustrate our techniques, we apply our methods to the vertex copying model (also known as the duplication-divergence model).

Abstract We continue building up the information theory of non-sequential data structures such as trees, sets, and graphs. In this paper, we consider dynamic graphs generated by a full duplication model in which a new vertex selects an existing vertex and copies all of its neighbors. We ask how many bits are needed to describe the labeled and unlabeled versions of such graphs. We first estimate entropies of both versions and then present asymptotically optimal compression algorithms up to two bits. Interestingly, for the full duplication model the labeled version needs $$\Theta (n)$$ Θ(n) bits while its unlabeled version (structure) can be described by $$\Theta (\log n)$$ Θ(logn) bits due to significant amount of symmetry (i.e. large average size of the automorphism group of sample graphs).

As an increasing amount of data is gathered nowadays and stored in databases, the question arises of how to protect the privacy of individual records in a database even while providing accurate answers to queries on the database. Differential Privacy (DP) has gained acceptance as a framework to quantify vulnerability of algorithms to privacy breaches. We consider the problem of how to sanitize an entire database via a DP mechanism, on which unlimited further querying is performed. While protecting privacy, it is important that the sanitized database still provide accurate responses to queries. The central contribution of this work is to characterize the amount of information preserved in an optimal DP database sanitizing mechanism (DSM). We precisely characterize the utility-privacy trade-off of mechanisms that sanitize databases in the asymptotic regime of large databases. We study this in an information-theoretic framework by modeling a generic distribution on the data, and a measure of fidelity between the histograms of the original and sanitized databases. We consider the popular L1-distortion metric, i.e., the total variation norm that leads to the formulation as a linear program (LP). This optimization problem is prohibitive in complexity with the number of constraints growing exponentially in the parameters of the problem. Our focus on the asymptotic regime enables us characterize precisely, the limit of the sequence of solutions to this optimization problem. Leveraging tools from discrete geometry, analytic combinatorics, and duality theorems of optimization, we fully characterize this limit in terms of a power series whose coefficients are the number of integer points on a multidimensional convex crosspolytope studied by Ehrhart in 1967. Employing Ehrhart theory, we determine a simple closed form computable expression for the asymptotic growth of the optimal privacy-fidelity trade-off to infinite precision. At the heart of the findings is a deep connection between the minimum expected distortion and a fundamental construct in Ehrhart theory - Ehrhart series of an integral convex polytope.

We study structural properties of preferential attachment graphs (with parameter m ≥ 1 giving the number of attachment choices that each new vertex makes) which intervene in two complementary algorithmic/statistical/information-theoretic problems involving the information shared between a random graph's labels and its structure: in structural compression, we seek to compactly describe a graph's structure by a bit string, throwing away its label information; in node arrival order recovery, we seek to recover node labels, given only a graph structure. In particular, we study the typical size of the automorphism group, as well as some shape parameters (such as the number of linear extensions and height) of the directed version of the graph, which in turn allows us to estimate the typical number of admissible labeled representatives of a given graph structure. Our result on the automorphism group positively settles a conjecture to the effect that, provided that m ≥ 3, preferential attachment graphs are asymmetric with high probability, and completes the characterization of the number of symmetries for a broad range of parameters of the model (i.e., for all fixed m). These results allow us to give an algorithmically efficient, asymptotically optimal algorithm for compression of unlabeled preferential attachment graphs. To show the optimality of our scheme, we also derive new, precise estimates of the Shannon entropy of both the unlabeled and labeled version of the model. Our results also imply inapproximability results for the problem of node arrival order recovery.

Dirichlet distribution and multinomial distribution play important role in information theory and statistics. They find applications in estimation, average minimax redundancy in source coding, Pólya urn model, and graph compression. Dirichlet-multinomial distribution is a multinomial distribution in which parameters are distributed according to the Dirichlet distribution. In this paper, we present some characteristics of the Dirichlet-multinomial distribution, including a precise asymptotic for the entropy. It should be point out that such a characterization turns out to be technically quite challenging requiring analytic tools including analytic continuation of hypergeometric series.

We continue developing the information theory of structured data. In this article, we study models generating d -ary trees ( d ≥ 2) and trees with unrestricted degree. We first compute the entropy which gives us the fundamental lower bound on compression of such trees. Then we present efficient compression algorithms based on arithmetic encoding that achieve the entropy within a constant number of bits. A naïve implementation of these algorithms has a prohibitive time complexity of O ( n d ) elementary arithmetic operations (each corresponding to a number f ( n , d ) of bit operations), but our efficient algorithms run in O ( n 2 ) of these operations, where n is the number of nodes. It turns out that extending source coding (i.e., compression) from sequences to advanced data structures such as degree-unconstrained trees is mathematically quite challenging and leads to recurrences that find ample applications in the information theory of general structures (e.g., to analyze the information content of degree-unconstrained non-plane trees).

Information theoretic properties of large combinatorial systems enable us in better understanding their solution structure and provide insights how to optimize them in a robust manner. In this paper, we revisit the idea of characterizing structural information in solutions for combinatorial problems by information theoretic properties. We provide theorems on analytic expressions of the asymptotic free energy and entropy of solutions with weak dependencies for strongly disordered combinatorial optimization problems, e.g. the sparse Minimum Bisection Problem (sMBP). We prove that the free energy of sMBP with random edge weights exhibits phase transitions equivalent to Derrida's Random Energy Model (REM). Specifically, we analyze the dependency structure between two arbitrary solutions and prove that the influence of correlations on the free energy and the relative entropy vanishes.

, named after John von Neumann, is an extension of the classical concept of entropy to the field of quantum mechanics. From a numerical perspective, von Neumann entropy can be computed simply by computing all eigenvalues of a density matrix, an operation that could be prohibitively expensive for large-scale density matrices. We present and analyze three randomized algorithms to approximate von Neumann entropy of real density matrices: our algorithms leverage recent developments in the Randomized Numerical Linear Algebra (RandNLA) literature, such as randomized trace estimators, provable bounds for the power method, and the use of random projections to approximate the eigenvalues of a matrix. All three algorithms come with provable accuracy guarantees and our experimental evaluations support our theoretical findings showing considerable speedup with small loss in accuracy.

We consider the problem of designing a database sanitization mechanism (DSM) that minimizes, in the expected sense, the L1-distortion between the histograms of original and sanitized databases, while being θ-differentially private (DP). The expected L1-distortion of a corresponding optimal θ-DP DSM provides for an important utility-privacy trade-off. This problem reduces to a prohibitively complex linear program (LP). Using tools from Ehrhart theory, analytic combinatorics and LP theory, we solve this problem and thereby provide a simple closed form computable expression characterizing this trade-off.

Inferring the node arrival sequence from a snapshot of a dynamic network is an important problem, with applications ranging from identifying sources of contagion to flow of capital in financial transaction networks. Variants of this problem have received significant recent research attention, including results on infeasibility of solution for prior formulations. We present a new formulation of the problem that admits probabilistic solutions for broad classes of dynamic network models. Instantiating our framework for a preferential attachment model, we present effectively computable and practically tight bounds on the tradeoff curve between optimal achievable precision and density/recall. We also present efficient algorithms for partial recovery of node arrival orders and derive theoretical and empirical performance bounds on the precision and density/recall of our methods in comparison to the best possible. We validate our methods through experiments on both synthetic and real networks to show that their performance is robust to model changes, and that they yield excellent results in practice. We also demonstrate their utility in the context of a novel application in analysis of the human brain connectome to draw new insights into the functional and structural organization and evolution of the human brain.

Most real world combinatorial optimization problems are affected by noise in the input data, thus behaving in the high noise limit like large disordered particle systems, e.g. spin glasses or random networks. Due to uncertainty in the input, optimization of such disordered instances should infer stable posterior distributions of solutions conditioned on the noisy input instance. The maximum entropy principle states that the most stable distribution given the noise influence is defined by the Gibbs distribution and it is characterized by the free energy. In this paper, we first provide rigorous asymptotics of the difficult problem to compute the free energy for two combinatorial optimization problems, namely the sparse Minimum Bisection Problem (sMBP) and Lawler's Quadratic Assignment Problem (LQAP). We prove that both problems exhibit phase transitions equivalent to the discontinuous behavior of Derrida's Random Energy Model (REM). Furthermore, the derived free energy asymptotics lead to a theoretical justification of a recently introduced concept [3] of Gibbs posterior agreement that measures stability of the Gibbs distributions when the cost function fluctuates due to randomness in the input. This relatively new stability concept may potentially provide a new method to select robust solutions for a large class of optimization problems.

Compression schemes for advanced data structures have become a central modern challenge. Information theory has traditionally dealt with conventional data such as text, images, or video. In contrast, most data available today is multitype and context-dependent. To meet this challenge, we have recently initiated a systematic study of advanced data structures such as unlabeled graphs [8]. In this paper, we continue this program by considering trees with statistically correlated vertex names. Trees come in many forms, but here we deal with binary plane trees (where order of subtrees matters) and their non-plane version (where order of subtrees doesn't matter). Furthermore, we assume that each name is generated by a known memoryless source (horizontal independence), but a symbol of a vertex name depends in a Markovian sense on the corresponding symbol of the parent vertex name (vertical Markovian dependency). Such a model is closely connected to models of phylogenetic trees. While in general the problem of multimodal compression and associated analysis can be extremely complicated, we find that in this natural setting, both the entropy analysis and optimal compression are analytically tractable. We evaluate the entropy for both types of trees. For the plane case, with or without vertex names, we find that a simple two-stage compression scheme is both efficient and optimal. We then present efficient and optimal compression algorithms for the more complicated non-plane case.

We continue developing the information theory of advanced data structures. In our previous work, we introduced structural entropy of unlabeled graphs and designed lossless compression algorithms for binary trees (with structure-correlated vertex names). In this paper, we consider d-ary trees (d ≥ 2) and trees with unrestricted degree for which we compute the entropy (the first step to design optimal compression algorithms). It turns out that extending from binary trees to general trees is mathematically quite challenging and leads to new recurrences that find ample applications in the information theory of structures.

Many networks in the real world are dynamic in nature: nodes enter, exit, and make and break connections with one another as time passes. Several random graph models of these networks are such that nodes have well-defined arrival times. It is natural to ask if, for a given random graph model, we can recover the arrival order of nodes, given information about the structure of the graph. In this work, we give a rigorous formulation of the problem in a statistical learning framework and tie its feasibility, for a broad class of models, to several sets of permutations associated with the symmetries of the random graph model and graphs generated by it. Moreover, we show how the same quantities are fundamental to the study of the information content of graph structures. We then apply our general results to the special cases of the Erdoos-Renyi and preferential attachment models to derive strong inapproximability results.

We rigorously study a channel that maps sequences from a finite alphabet to self-avoiding walks in the two-dimensional grid, inspired by a model of protein folding from statistical physics and studied empirically by biophysicists. This channel, which we call the Boltzmann sequence-structure channel, is characterized by a Boltzmann/Gibbs distribution with a free parameter corresponding to temperature. In our previous work, we verified empirically that the channel capacity appears to have a phase transition for small temperature and decays to zero for high temperature. In this paper, we make some progress toward theoretically explaining these phenomena. We first estimate the conditional entropy between the input sequence and the output fold, giving an upper bound which exhibits a phase transition with respect to temperature. Next, we formulate a class of parameter settings under which the dependence between walk energies is governed by their number of shared contacts. In this setting, we derive a lower bound on the conditional entropy. This lower bound allows us to conclude that the mutual information tends to zero in a nontrivial regime of high temperature, giving some support to the empirical fact regarding capacity. Finally, we construct an example setting of the parameters of the model for which the conditional entropy is exactly calculable and which does not exhibit a phase transition.

We rigorously study a channel that maps binary sequences to self-avoiding walks in the two-dimensional grid, inspired by a model of protein statistics. This channel, which we also call the Boltzmann sequence-structure channel, is characterized by a Boltzmann/Gibbs distribution with a free parameter corresponding to temperature. In our previous work, we verified experimentally that the channel capacity has a phase transition for small temperature and decays to zero for high temperature. In this paper, we make some progress towards explaining these phenomena. We first upper bound the conditional entropy between the input sequence and the output which exhibits a phase transition with respect to temperature. Then we derive a lower bound on the conditional entropy for some specific set of parameters. This lower bound allows us to conclude that the mutual information tends to zero for high temperature.

Compression schemes for advanced data structures have become the challenge of today. Information theory has traditionally dealt with conventional data such as text, image, or video. In contrast, most data available today is multi-type and context dependent. To meet this challenge, we have recently initiated a systematic study of advanced data structures such as unlabeled graphs [1]. In this paper, we continue this program by considering trees with statistically correlated vertex names. Trees come in many forms, but here we deal with binary plane trees (where order of subtrees matters) and their non-plane version. Furthermore, we assume that each symbol of a vertex name depends in a Markovian sense on the corresponding symbol of the parent vertex name. We first evaluate the entropy for both types of trees. Then we propose for known sources two compression schemes COMPRESSPTREE for plane trees with correlated names, and COMPRESSNPTREE for non-plane trees. We show that these schemes achieve the lower bound within two bits.

The method of types is one of the most popular techniques in information theory and combinatorics. However, thus far the method has been mostly applied to 1-D Markov processes, and it has not been thoroughly studied for general Markov fields. Markov fields over a finite alphabet of size m ≥ 2 can be viewed as models for multidimensional systems with local interactions. The locality of these interactions is represented by a shape S while its marking by symbols of the underlying alphabet is called a tile. Two assignments in a Markov field have the same type if they have the same empirical distribution, i.e., if they have the same number of tiles of a given type. Our goal is to study the growth of the number of possible Markov field types in either a d-dimensional box of lengths n1, .. . ,ndor its cyclic counterpart, a d-dimensional torus. We relate this question to the enumeration of nonnegative integer solutions of a large system of Diophantine linear equations called the conservation laws. We view a Markov type as a vector in a D =m|S| dimensional space and count the number of such vectors satisfying the conservation laws, which turns out to be the number of integer points in a certain polytope. For the torus, this polytope is of dimension μ = D - 1 - rk(C), where rk(C) is the number of linearly independent conservation laws C. This provides an upper bound on the number of types. Then, we construct a matching lower bound leading to the conclusion that the number of types in the torus Markov field is θ(Nμ), where N = n1. . . nd. These results are derived by geometric tools, including ideas of discrete and convex multidimensional geometry.

The method of types is one of the most popular technique in information theory and combinatorics. However, it was never thoroughly studied for Markov fields. Markov fields can be viewed as models for systems involving a large number of variables with local dependencies and interactions. These local dependencies can be captured by a shape of interactions (locations that contribute the next probability transition). Shapes marked by symbols from a finite alphabet are called tiles. Two assignments in a Markov filed have the same type if they have the same empirical distribution or they can be tiled by the same number of tile types. Our goal is to study the growth of the number of Markov field types or the number of tile types. This intricate and important problem was left open for too long.

In applications involving estimation, the relevant model classes of probability distributions are often too complex to admit estimators that converge to the truth with convergence rates that can be uniformly bounded over the entire model class as the sample size increases (uniform consistency). While it is often possible to get pointwise guarantees, so that the convergence rate of the estimator can be bounded in a model-dependent way, such pointwise gaurantees are unsatisfactory - estimator performance is a function of the very unknown quantity that is being estimated. Therefore, even if an estimator is consistent, how well it is doing may not be clear no matter what the sample size. Departing from this traditional uniform/pointwise dichotomy, a new analysis framework is explored by characterizing model classes of probability distributions that may only admit pointwise guarantees, yet where all the information about the unknown model needed to gauge estimator accuracy can be inferred from the sample at hand. To provide a focus to this suggested broad new paradigm, we analyze the universal compression problem in this data-driven pointwise consistency framework.

We study the Lempel-Ziv'78 algorithm and show that its (normalized) redundancy rate tends to a Gaussian distribution for memoryless sources. We accomplish it by extending findings from our 1995 paper, in particular, by presenting a new simplified proof of the central limit theorem (CLT) for the number of phrases in the LZ'78 algorithm. We first analyze the asymptotic behavior of the total path length in the associated digital search tree built from independent sequences. Then, a renewal theory type argument yields CLT for LZ'78 scheme. Here, we extend our analysis of LZ'78 algorithm to present new results on the convergence of moments, moderate and large deviations, and CLT for the (normalized) redundancy. In particular, we confirm that the average redundancy rate decays as 1/log n, and we find that the variance is of order 1/n, where n is the length of the text.

We propose a classification test to discriminate Markov sources based on the joint string complexity. String complexity is defined as the cardinality of a set of all distinct words (factors) of a given string. For two strings, we define the joint string complexity as the cardinality of the set of words which both strings have in common. In this paper we analyze the average joint complexity when both strings are generated by two Markov sources. We provide fast converging asymptotic expansions and present some experimental results showing usefulness of the joint complexity to text discrimination.

It is known that for memoryless sources, the average and maximal redundancy of fixed-to-variable length codes, such as the Shannon and Huffman codes, exhibit two modes of behavior for long blocks. It either converges to a limit or it has an oscillatory pattern, depending on the irrationality or rationality, respectively, of certain parameters that depend on the source. Here, we extend these findings for the Shannon code to the case of a Markov source, which is considerably more involved. We provide a precise characterization of the redundancy of the Shannon code redundancy for a class of irreducible, periodic and aperiodic Markov sources.

Information theory traditionally deals with the problem of transmitting sequences over a communication channel and finding the maximum number of messages that a transmitter can send so that the receiver recovers these messages with arbitrarily small probability of error. However, databases of various sorts have come into existence in recent years that require the transmission of new sources of data (e.g., graphs and sets) over communication channels. Here, we investigate a communication model transmitting Erdos-Rényi (unlabeled) graphs to a destination over a Binary Symmetric Channel (BSC). We find the capacity of such a channel - called the Structural Binary Symmetric Channel (SBSC) - to be C = 1 - h(ε) where h(ε) is the binary entropy of the error bit rate ε.

Tries are among the most versatile and widely used data structures on words. They are pertinent to the (internal) structure of (stored) words and several splitting procedures used in diverse contexts ranging from document taxonomy to IP addresses lookup, from data compression (i.e., Lempel-Ziv'77 scheme) to dynamic hashing, from partial-match queries to speech recognition, from leader election algorithms to distributed hashing tables and graph compression. While the performance of tries under a realistic probabilistic model is of significant importance, its analysis, even for simplest memoryless sources, has proved difficult. Rigorous findings about inherently complex parameters were rarely analyzed (with a few notable exceptions) under more realistic models of string generations. In this paper we meet these challenges: By a novel use of the contraction method combined with analytic techniques we prove a central limit theorem for the external path length of a trie under a general Markov source. In particular, our results apply to the Lempel-Ziv'77 code. We envision that the methods described here will have further applications to other trie parameters and data structures.

Divide-and-conquer recurrences are one of the most studied equations in computer science. Yet, discrete versions of these recurrences, namely for some known sequence a n and given b j , b j , p j and δ j , δ j , present some challenges. The discrete nature of this recurrence (represented by the floor and ceiling functions) introduces certain oscillations not captured by the traditional Master Theorem, for example due to Akra and Bazzi [1998] who primary studied the continuous version of the recurrence. We apply powerful techniques such as Dirichlet series, Mellin-Perron formula, and (extended) Tauberian theorems of Wiener-Ikehara to provide a complete and precise solution to this basic computer science recurrence. We illustrate applicability of our results on several examples including a popular and fast arithmetic coding algorithm due to Boncelet for which we estimate its average redundancy and prove the Central Limit Theorem for the phrase length. To the best of our knowledge, discrete divide and conquer recurrences were not studied in this generality and such detail; in particular, this allows us to compare the redundancy of Boncelet’s algorithm to the (asymptotically) optimal Tunstall scheme.

It is known that for memoryless sources, the average and maximal redundancy of fixed-to-variable length codes, such as the Shannon and Huffman codes, exhibit two modes of behavior for long blocks. It either converges to a limit or it has an oscillatory pattern, depending on the irrationality or rationality, respectively, of certain parameters that depend on the source. In this paper, we extend these findings, concerning the Shannon code, to the case of a Markov source. We provide a precise characterization of the convergent versus oscillatory behavior of the Shannon code redundancy for a class of irreducible, periodic, and aperiodic, Markov sources. These findings are obtained by analytic methods, such as Fourier/Fejér series analysis and spectral analysis of matrices.

We study the binary deletion channel where each input bit is independently deleted according to a fixed probability. We relate the conditional probability distribution of the output of the deletion channel given the input to the hidden pattern matching problem. This yields a new characterization of the mutual information between the input and output of the deletion channel. Through this characterization we are able to comment on the the deletion channel capacity, in particular for deletion probabilities approaching 0 and 1.

Efficient cardinality estimation is a common requirement for many wireless sensor network (WSN) applications. The task must be accomplished at extremely low overhead due to severe sensor resource limitation. This poses an interesting challenge for large-scale WSNs. In this paper we present a two-phase probabilistic algorithm based on order statistics and Bernoulli scheme, which effectively estimates the cardinality of WSNs. We thoroughly examine properties of estimators used in each phase as well as the precision of the whole procedure. The algorithm discussed in this paper is a modification of a recently published idea - the modification enables us to obtain a provable precision.

Information theory traditionally deals with “conventional data,” be it textual data, image, or video data. However, databases of various sorts have come into existence in recent years for storing “unconventional data” including biological data, social data, web data, topographical maps, and medical data. In compressing such data, one must consider two types of information: the information conveyed by the structure itself, and the information conveyed by the data labels implanted in the structure. In this paper, we attempt to address the former problem by studying information of graphical structures (i.e., unlabeled graphs). As the first step, we consider the Erdös-Rényi graphs G(n,p) over n vertices in which edges are added independently and randomly with probability p. We prove that the structural entropy of G(n,p) is (n;2)h(p)-logn!+o(1)=(n;2)h(p)-nlog+O(n), where h(p)=-plogp-(1-p)log(1-p) is the entropy rate of a conventional memoryless binary source. Then, we propose a two-stage compression algorithm that asymptotically achieves the structural entropy up to the nlog term (i.e., the first two leading terms) of the structural entropy. Our algorithm runs either in time O(n2) in the worst case for any graph or in time O(n+e) on average for graphs generated by G(n,p), where e is the average number of edges. To the best of our knowledge, this is the first provable (asymptotically) optimal graph compressor for Erdös-Rényi graph models. We use combinatorial and analytic techniques such as generating functions, Mellin transform, and poissonization to establish these findings. Our experiments confirm the theoretical results and also show the usefulness of our algorithm for some real-world graphs such as the Internet, biological networks, and social networks.

The method of types is one of the most popular techniques in information theory and combinatorics. Two sequences of equal length have the same type if they have identical empirical distributions. In this paper, we focus on Markov types, that is, sequences generated by a Markov source (of order one). We note that sequences having the same Markov type share the same so-called balanced frequency matrix that counts the number of distinct pairs of symbols. We enumerate the number of Markov types for sequences of length over an alphabet of size . This turns out to be asymptotically equivalent to estimating the number of the balanced frequency matrices, the number of integer solutions of a system of linear Diophantine equations, and the number of connected Eulerian multigraphs. For fixed , we prove that the number of Markov types is asymptotically equal to d(m) nm2-m/(m2-m)! where we give an integral representation for d(m). For m →∞, we conclude that asymptotically the number of types is equivalent to √2m3m/2em2/m2m22mπm/2nm2-m provided that m = o(n1/4). These findings are derived by analytical techniques ranging from analytic combinatorics, to multidimensional generating functions, to the saddle point method.

We study the problem of deinterleaving a set of finite-memory (Markov) processes over disjoint finite alphabets, which have been randomly interleaved by a finite-memory switch. The deinterleaver has access to a sample of the resulting interleaved process, but no knowledge of the number or structure of the component Markov processes, or of the switch. We study conditions for uniqueness of the interleaved representation of a process, showing that certain switch configurations, as well as memoryless component processes, can cause ambiguities in the representation. We show that a deinterleaving scheme based on minimizing a penalized maximum-likelihood cost function is strongly consistent, in the sense of reconstructing, almost surely as the observed sequence length tends to infinity, a set of component and switch Markov processes compatible with the original interleaved process. Furthermore, under certain conditions on the structure of the switch (including the special case of a memoryless switch), we show that the scheme recovers all possible interleaved representations of the original process. Experimental results are presented demonstrating that the proposed scheme performs well in practice, even for relatively short input samples.

We study the minimax pointwise redundancy of universal coding for memoryless models over large alphabets and present two main results. We first complete studies initiated in Orlitsky and Santhanam deriving precise asymptotics of the minimax pointwise redundancy for all ranges of the alphabet size relative to the sequence length. Second, we consider the minimax pointwise redundancy for a family of models in which some symbol probabilities are fixed. The latter problem leads to a binomial sum for functions with superpolynomial growth. Our findings can be used to approximate numerically the minimax pointwise redundancy for various ranges of the sequence length and the alphabet size. These results are obtained by analytic techniques such as tree-like generating functions and the saddle point method.

In 1993 Boncelet introduced a block arithmetic scheme for entropy coding that combines advantages of stream arithmetic coding with algorithmic simplicity. It is a variable-to-fixed length encoding in which the source sequence is partitioned into variable length phrases that are encoded by a fixed length dictionary pointer. The parsing is accomplished through a complete parsing tree whose leaves represent phrases. This tree, in its suboptimal heuristic version, is constructed by a simple divide and conquer algorithm, whose analysis is the subject of this paper. For a memoryless source, we first derive the average redundancy and compare it to the (asymptotically) optimal Tunstall's algorithm. Then we prove a central limit theorem for the phrase length. To establish these results, we apply powerful techniques such as Dirichlet series, Mellin-Perron formula, and (extended) Tauberian theorems of Wiener-Ikehara.

We show that the Lempel Ziv'78 redundancy rate tends to a Gaussian distribution for memoryless sources. We accomplish it by extending findings from our 1995 paper [3]. We present a new simplified proof of the Central Limit Theorem for the number of phrases in the LZ'78 algorithm. As in our 1995 paper, here we first analyze the asymptotic behavior of the total path length in a digital search tree (a DST) built from independent sequences. Then we present simplified proofs and extend our analysis of LZ'78 algorithm to include new results on the convergence of moments, moderate and large deviations, and redundancy analysis.

We study the problem of deinterleaving a set of finite-memory (Markov) processes over disjoint finite alphabets, which have been randomly interleaved by a finite-memory switch, extending previous results obtained for the case of a memoryless switch [1]. The deinterleaver has access to a sample of the resulting interleaved process, but no knowledge of the number or structure of the Markov processes, or of the switch. We study conditions for uniqueness of the interleaved representation of a process, showing that certain switch configurations can cause ambiguities in the representation, in addition to those caused by memoryless component processes, which were known in the memoryless switch case. We show that a deinterleaving scheme based on minimizing a penalized maximum-likelihood cost function is strongly consistent also in the finite-memory switch case, in the sense of reconstructing, almost surely as the observed sequence length tends to infinity, a set of component and switch Markov processes compatible with the original interleaved process. Furthermore, under certain conditions on the structure of the switch, we show that the scheme recovers all possible interleaved representations of the original process. Experimental results are presented demonstrating that the proposed scheme performs well in practice, even for relatively short input samples.

Divide-and-conquer recurrences are one of the most studied equations in computer science. Yet, discrete versions of these recurrences, namely for some known sequence an and given bj, pj and δj, present some challenges. The discrete nature of this recurrence (represented by the floor function) introduces certain oscillations not captured by the traditional Master Theorem, for example due to Akra and Bazzi who primary studied the continuous version of the recurrence. We apply powerful techniques such as Dirichlet series, Mellin-Perron formula, and (extended) Tauberian theorems of Wiener-Ikehara to provide a complete and precise solution to this basic computer science recurrence. We illustrate applicability of our results on several examples including a popular and fast arithmetic coding algorithm due to Boncelet for which we estimate its average redundancy. To the best of our knowledge, discrete divide and conquer recurrences were not studied in this generality and such detail; in particular, this allows us to compare the redundancy of Boncelet's algorithm to the (asymptotically) optimal Tunstall scheme.

Constrained sequences are strings satisfying certain additional structural restrictions (e.g., some patterns are forbidden). They find applications in communication, digital recording, and biology. In this article, we restrict our attention to the so-called ( d , k ) constrained binary sequences in which any run of zeros must be of length at least d and at most k , where 0≤ d < k . In many applications, one needs to know the number of occurrences of a given pattern w in such sequences, for which we coin the term constrained pattern matching . For a given word w , we first estimate the mean and the variance of the number of occurrences of w in a ( d , k ) sequence generated by a memoryless source. Then we present the central limit theorem and large deviations results. As a by-product, we enumerate asymptotically the number of ( d , k ) sequences with exactly r occurrences of w , and compute Shannon entropy of ( d , k ) sequences with a given number of occurrences of w . We also apply our results to detect under- and overrepresented patterns in neuronal data (spike trains), which satisfy structural constraints that match the framework of ( d , k ) binary sequences. Throughout this article we use techniques of analytic combinatorics such as combinatorial calculus, generating functions, and complex asymptotics.

The minimum expected length for fixed-to-variable length encoding of an n-block memoryless source with entropy H grows as nH + O(1), where the term O(1) lies between 0 and 1. However, this well-known performance is obtained under the implicit constraint that the code assigned to the whole n-block is a prefix code. Dropping the prefix constraint, which is rarely necessary at the block level, we show that the minimum expected length for a finite-alphabet memoryless source with known distribution grows as nH-1/2 log n + O(1) unless the source is equiprobable. We also refine this result up to o(1) for those memoryless sources whose log probabilities do not reside on a lattice.

We study the minimax redundancy of universal coding for large alphabets over memoryless sources and present two main results: We first complete studies initiated in Orlitsky and Santhanam deriving precise asymptotics of the minimax redundancy for all ranges of the alphabet sizes. Second, we consider the minimax redundancy of a source model in which some symbol probabilities are fixed. The latter model leads to an interesting binomial sum asymptotics with super-exponential growth functions. Our findings could be used to approximate numerically the minimax redundancy for various ranges of the sequence length and the alphabet size. These results are obtained by analytic techniques such as tree-like generating functions and the saddle point method.

A variable-to-fixed length encoder partitions the source string into variable-length phrases that belong to a given and fixed dictionary. Tunstall, and independently Khodak, designed variable-to-fixed length codes for memoryless sources that are optimal under certain constraints. In this paper, we study the Tunstall and Khodak codes using variety of techniques ranging from stopping times for sums of independent random variables to Tauberian theorems and Mellin transform. After proposing an algebraic characterization of the Tunstall and Khodak codes, we present new results on the variance and a central limit theorem for dictionary phrase lengths. This analysis also provides a new argument for obtaining asymptotic results about the mean dictionary phrase length and average redundancy rates.

We study the classical problem of noisy constrained capacity in the case of the binary symmetric channel (BSC), namely, the capacity of a BSC whose input is a sequence from a constrained set. As stated by Fan , “... while calculation of the noise-free capacity of constrained sequences is well known, the computation of the capacity of a constraint in the presence of noise ... has been an unsolved problem in the half-century since Shannon's landmark paper.” We first express the constrained capacity of a binary symmetric channel with (d,k)-constrained input as a limit of the top Lyapunov exponents of certain matrix random processes. Then, we compute asymptotic approximations of the noisy constrained capacity for cases where the noise parameter ε is small. In particular, we show that whenk≤ 2d, the error term (excess of capacity beyond the noise-free capacity) isO(ε) , whereas it isO(εlogε) whenk> 2d. In both cases, we compute the coefficient of the error term. In the course of establishing these findings, we also extend our previous results on the entropy of a hidden Markov process to higher-order finite memory processes. These conclusions are proved by a combination of analytic and combinatorial methods.

Information theory--a field at the intersection of applied mathematics and electrical engineering--was primarily developed for the purpose of addressing problems arising in data storage and data transmission over (noisy) communication media. Consequently, information theory provides the formal basis for much of today’s storage and communication infrastructure.

F. Brooks argues in [3] there is “no theory that gives us a metric for information embodied in structure” Shannon himself alluded to it fifty years earlier in his little known 1953 paper [14]. Indeed, in the past information theory dealt mostly with “conventional data,” be it textual data, image, or video data. However, databases of various sorts have come into existence in recent years for storing “unconventional data” including biological data, web data, topographical maps, and medical data. In compressing such data structures, one must consider two types of information: the information conveyed by the structure itself, and the information conveyed by the data labels implanted in the structure. In this paper, we attempt to address the former problem by studying information of graphical structures (i.e., unlabeled graphs). In particular, we consider the Erdös-Rényi graphs G(n; p) over n vertices in which edges are added randomly with probability p. We prove that the structural entropy of G(n; p) is (2nh(p) − log n! + o(1) = (2nh(p) − n log n + O(n); where h(p) = −p log p − (1 − p) log(1 − p) is the entropy rate of a conventional memoryless binary source. Then, we design a two-stage encoding that optimally compresses unlabeled graphs up to the first two leading terms of the structural entropy.

For each positive integer n, let Tnbe a random rooted full binary tree having 2n-1 vertices. We can view H(Tn), the entropy of Tn, as a measure of the structural complexity of tree Tnin the sense that approximately H(Tn) bits suffice to construct Tn. We analyze some random binary tree sequences (Tn: n = 1,2...) for which the normalized entropies H(Tn)/n converge to a limit as n rarr infin, as well as some other sequences (Tn) in which the normalized entropies fail to converge.

We study the problem of deinterleaving a set of finite memory (Markov) processes over disjoint finite alphabets, which have been randomly interleaved by a memoryless random switch. The deinterleaver has access to a sample of the resulting interleaved process, but no knowledge of the number or structure of the Markov processes, or the parameters of the switch. We present a deinterleaving scheme based on minimizing a penalized maximum-likelihood cost function, and show it to be strongly consistent, in the sense of reconstructing, almost surely as the observed sequence length tends to infinity, the original Markov and switch processes. Solutions are described for the case where a bound on the order of the Markov processes is available, and for the case where it is not. We demonstrate that the proposed scheme performs well in practice, requiring much shorter input sequences for reliable deinterleaving than previous solutions.

Conventional wisdom states that the minimum expected length for fixed-to-variable length encoding of an n-block memoryless source with entropy H grows as nH+O(1). However, this performance is obtained under the constraint that the code assigned to the whole n-block is a prefix code. Dropping this unnecessary constraint we show that the minimum expected length grows as nH - 1/2 log n + O(1) unless the source is equiprobable.

A digital search tree (DST) – one of the most fundamental data structures on words – is a digital tree in which keys (strings, words) are stored directly in (internal) nodes. Such trees find myriad of applications from the popular Lempel-Ziv'78 data compression scheme to distributed hash tables. The profile of a DST measures the number of nodes at the same distance from the root; it is a function of the number of stored strings and the distance from the root. Most parameters of DST (e.g., height, fill-up) can be expressed in terms of the profile. However, from the inception of DST, the analysis of the profile has been elusive and it has become a prominent open problem in the area of analysis of algorithms. We make here the first, but decisive, step towards solving this problem. We present a precise analysis of the average profile when stored strings are generated by a biased memoryless source. The main technical difficulty of analyzing the profile lies in solving a sophisticated recurrence equation. We present such a solution for the Poissonized version of the problem (i.e., when the number of stored strings is generated by a Poisson distribution) in the Mellin transform domain. To accomplish it, we introduce a novel functional operator that allows us to express the solution in an explicit form, and then using analytic algorithmics tools to extract the asymptotic behavior of the profile. This analysis is surprisingly demanding but once it is carried out it reveals unusually intriguing and interesting behavior. The average profile undergoes several phase transitions when moving from the root to the longest path. At first, it resembles a full tree until it abruptly starts growing polynomially and it oscillates in this range. Our results are derived by methods of analytic algorithmics such as generating functions, Mellin transform, Poissonization and de-Poissonization, the saddle-point method, singularity analysis and uniform asymptotic analysis. Index Terms: Digital search trees, trees profile, analytic combinatorics, analysis of algorithms, generating functions, Mellin transform.

Tries (from retrieval) are one of the most popular data structures on words. They are pertinent to the (internal) structure of stored words and several splitting procedures used in diverse contexts. The profile of a trie is a parameter that represents the number of nodes (either internal or external) with the same distance from the root. It is a function of the number of strings stored in a trie and the distance from the root. Several, if not all, trie parameters such as height, size, depth, shortest path, and fill-up level can be uniformly analyzed through the (external and internal) profiles. Although profiles represent one of the most fundamental parameters of tries, they have hardly been studied in the past. The analysis of profiles is surprisingly arduous, but once it is carried out it reveals unusually intriguing and interesting behavior. We present a detailed study of the distribution of the profiles in a trie built over random strings generated by a memoryless source. We first derive recurrences satisfied by the expected profiles and solve them asymptotically for all possible ranges of the distance from the root. It appears that profiles of tries exhibit several fascinating phenomena. When moving from the root to the leaves of a trie, the growth of the expected profiles varies. Near the root, the external profiles tend to zero at an exponential rate, and then the rate gradually rises to being logarithmic; the external profiles then abruptly tend to infinity, first logarithmically and then polynomially; they then tend polynomially to zero again. Furthermore, the expected profiles of asymmetric tries are oscillating in a range where profiles grow polynomially, while symmetric tries are nonoscillating, in contrast to most shape parameters of random tries studied previously. Such a periodic behavior for asymmetric tries implies that the depth satisfies a central limit theorem but not a local limit theorem of the usual form. Also the widest levels in symmetric tries contain a linear number of nodes, differing from the order $n/\sqrt{\log n}$ for asymmetric tries, n being the size of the trees. Finally, it is observed that profiles satisfy central limit theorems when the variance goes unbounded, while near the height they are distributed according to Poisson laws. As a consequence of these results we find typical behaviors of the height, shortest path, fill-up level, and depth. These results are derived here by methods of analytic algorithmics such as generating functions, Mellin transform, Poissonization and de-Poissonization, the saddle-point method, singularity analysis, and uniform asymptotic analysis.

In the constrained pattern matching one searches for a given pattern in a constrained sequence, which finds applications in communication, magnetic recording, and biology. We concentrate on the so-called (d, k) constrained binary sequences in which any run of zeros must be of length at least d and at most k, where 0 ≤ d ≪ k. In our previous paper [2] we established the central limit theorem (CLT) for the number of occurrences of a given pattern in such sequences. Here, we present precise large deviations results, often used in diverse applications. In particular, we apply our results to detect under- and over-represented patterns in neuronal data (spike trains), which satisfy structural constraints that match the framework of (d, k) binary sequences. Among others, we obtain justifiably accurate statistical inferences about their biological properties and functions. Throughout, we use techniques of analytic information theory such as combinatorial calculus, generating functions, and complex asymptotics.

The notion of information has so far been quantified mostly in statistical terms, giving rise to Shannonpsilas information theory and the principles of digital data transmission. Modern systems involving complex, intelligent, and autonomous agents call for a new look at the measures of information, where context, semantics, structures, and rationality are of paramount importance, especially for applications to biology, chemistry, physics, and economics. In this essay we propose a framework for measuring information inspired by the event-driven approach. We then illustrate our definition on some examples ranging from distributed systems to biology and economics.

Variable-to-variable (VV) codes are very attractive yet not well understood data compression schemes. In 1972, Khodak claimed to provide upper and lower bounds for the achievable redundancy rate, however, he did not offer explicit construction of such codes. In this paper, we first present a constructive and transparent proof of Khodak's result showing that for memoryless sources there exists a code with the average redundancy bounded byD-5/3, whereDis the average delay (e.g., the average length of a dictionary entry). We also describe an algorithm that constructs a VV length code with a small redundancy rate for largeD. Then, we discuss several generalizations. We prove that the worst case redundancy does not exceedD-4/3. Furthermore, we provide similar upper bound for Markov sources (of order 1). Finally, we consider bounds that are valid foralmostallmemoryless and Markov sources for which the set of exceptional source parameters has zero measure. In particular, for all memoryless sources outside this exceptional class, we prove there exists a VV code with the average redundancy rate bounded byD-1-m/3+epsivand the worst case redundancy rate bounded byD-1-m/3+epsiv, wheremis the cardinality of the alphabet. We complete our analysis with a lower bound showing that for all VV codes the average and the worst case redundancy rates are at leastD-2m-1-epsivfor almost all memoryless sources in the sense that the set of exceptional source parameters has zero measure. We prove these results using techniques of Diophantine approximations.

One-to-one codes are ldquoone-shotrdquo codes that assign a distinct codeword to source symbols and are not necessarily prefix codes (more generally, uniquely decodable). Interestingly, as Wyner proved in 1972, for such codes the average code length can besmallerthan the source entropy. By how much? We call this difference theanti-redundancy. Various authors over the years have shown that the anti-redundancy can be as big as minus the logarithm of the source entropy. However, to the best of our knowledge precise estimates do not exist. In this note, we consider a block code of lengthngenerated for a binary memoryless source, and prove that the average anti-redundancy is -1/2 log2n+C+F(n)+o(1) whereCis a constant and eitherF(n) = 0 if log2(1-p)/pis irrational (wherepis the probability of generating a ldquo0rdquo) orF(n) is a fluctuating function as the code length increases. This relatively simple finding requires a combination of analytic tools such as precise evaluation of Bernoulli sums, the saddle point method, and theory of distribution of sequences modulo 1.

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).

Constrained sequences find applications in communication, magnetic recording, and biology. In this paper, we restrict our attention to the so-called (d, k) constrained binary sequences in which any run of zeros must be of length at least d and at most k, where 0lesd

We study the classical problem of noisy constrained capacity in the case of the binary symmetric channel (BSC), namely, the capacity of a BSC whose input is a sequence from a constrained set. As stated in [4] "... while calculation of the noise-free capacity of constrained sequences is well known, the computation of the capacity of a constraint in the presence of noise ... has been an unsolved problem in the half-century since Shannon's landmark paper ...." We express the constrained capacity of a binary symmetric channel with (d, k)-constrained input as a limit of the top Lyapunov exponents of certain matrix random processes. We compute asymptotic approximations of the noisy constrained capacity for cases where the noise parameter epsiv is small. In particular, we show that when kles2d, the error term with respect to the constraint capacity is O(epsiv), whereas it is O(epsiv log epsiv) when k > 2d. In both cases, we compute the coefficient of the error term. We also extend previous results on the entropy of a hidden Markov process to higher-order finite memory processes.

Andersson and Nilsson introduced in 1993 a level-compressed trie (for short, LC trie) in which a full subtree of a node is compressed to a single node of degree being the size of the subtree. Recent experimental results indicated a “dramatic improvement” when full subtrees are replaced by “partially filled subtrees.” In this article, we provide a theoretical justification of these experimental results, showing, among others, a rather moderate improvement in search time over the original LC tries. For such an analysis, we assume that n strings are generated independently by a binary memoryless source, with p denoting the probability of emitting a “1” (and q = 1 − p ). We first prove that the so-called α-fillup level F n (α) (i.e., the largest level in a trie with α fraction of nodes present at this level) is concentrated on two values with high probability: either F n (α) = k n or F n (α) = k n + 1, where k n = log 1/√ pq n − |ln ( p/q )|/2 ln 3/2 (1√ pq ) Φ −1 (α) √ ln n + O (1) is an integer and Φ( x ) denotes the normal distribution function. This result directly yields the typical depth (search time) D n (α) in the α-LC tries, namely, we show that with high probability D n (α) ∼ C 2 log log n , where C 2 = 1/|log(1 − h /log(1/√ pq ))| for p ≠ q and h = − p log p − q log q is the Shannon entropy rate. This should be compared with recently found typical depth in the original LC tries, which is C 1 log log n , where C 1 = 1/|log(1− h /log(1/min{ p , 1− p }))|. In conclusion, we observe that α affects only the lower term of the α-fillup level F n (α), and the search time in α-LC tries is of the same order as in the original LC tries.

We propose a joint source-channel coding algorithm capable of correcting some errors in the popular Lempel-Ziv'77 (LZ'77) scheme without introducing any measurable degradation in the compression performance. This can be achieved because the LZ'77 encoder does not completely eliminate the redundancy present in the input sequence. One source of redundancy can be observed when an LZ'77 phrase has multiple matches. In this case, LZ'77 can issue a pointer to any of those matches, and a particular choice carries some additional bits of information. We call a scheme with embedded redundant information the LZS'77 algorithm. We analyze the number of longest matches in such a scheme and prove that it follows the logarithmic series distribution with mean 1/h (plus some fluctuations), where h is the source entropy. Thus, the distribution associated with the number of redundant bits is well concentrated around its mean, a highly desirable property for error correction. These analytic results are proved by a combination of combinatorial, probabilistic, and analytic methods (e.g., Mellin transform, depoissonization, combinatorics on words). In fact, we analyze LZS'77 by studying the multiplicity matching parameter in a suffix tree, which in turn is analyzed via comparison to its independent version, called trie. Finally, we present an algorithm in which a channel coder (e.g., Reed-Solomon (RS) coder) succinctly uses the inherent additional redundancy left by the LZS'77 encoder to detect and correct a limited number of errors. We call such a scheme the LZRS'77 algorithm. LZRS'77 is perfectly backward-compatible with LZ'77, that is, a file compressed with our error-resistant LZRS'77 can still be decompressed by a generic LZ'77 decoder

Lossless data compression systems are typically regarded as very brittle to transmission errors. This limits their applicability to domains like noisy tetherless channels or file systems that can possibly get corrupted. Here we show how a popular lossless data compression scheme used in file formats GIF, PDF, and TIFF, among others, can be made error-resilient in such a way that the compression performance is minimally affected. The new scheme is designed to be backward-compatible, that is, a file compressed with our error-resilient algorithm can be still decompressed by the original decoder. In this preliminary report, we present our scheme, collect some experimental data supporting our claims, and provide some theoretical justifications.

We study the Tunstall code using the machinery from the analysis of algorithms literature. In particular, we propose an algebraic characterization of the Tunstall code which, together with tools like the Mellin transform and the Tauberian theorems, leads to new results on the variance and a central limit theorem for dictionary phrase lengths. This analysis also provides a new argument for obtaining asymptotic results about the mean dictionary phrase length and average redundancy rates

A sequence of zeros and ones is called a (d,k)-sequence if it does not contain runs of zeros of length either less than d or greater than k, where d and k are arbitrary, but feed, positive integers and d < k. For a given pattern w, we enumerate exactly and asymptotically (d,k) sequences of length n that do not contain a given word w. We use techniques of analytic algorithms such as generating functions, combinatorial calculus, and complex asymptotics

We consider the sequence comparison problem, also known as “ hidden ” pattern problem, where one searches for a given subsequence in a text (rather than a string understood as a sequence of consecutive symbols). A characteristic parameter is the number of occurrences of a given pattern w of length m as a subsequence in a random text of length n generated by a memoryless source. Spacings between letters of the pattern may either be constrained or not in order to define valid occurrences. We determine the mean and the variance of the number of occurrences, and establish a Gaussian limit law and large deviations. These results are obtained via combinatorics on words, formal language techniques, and methods of analytic combinatorics based on generating functions. The motivations to study this problem come from an attempt at finding a reliable threshold for intrusion detections, from textual data processing applications, and from molecular biology.

In this paper, we investigate structural properties of multicast trees that give rise to the so-called multicast power law. The law asserts that the ratio R(n) of the average number of links in a multicast tree connecting the source to n destinations to the average number of links in a unicast path, satisfies asymptotically R(n)/spl ap/cn/sup /spl phi//, 0</spl phi/<1. In order to obtain a better insight, we first analyze some simple multicast tree topologies, which under appropriately chosen parameters give rise to the multicast power law. The asymptotic analysis of R(n) in this case indicates that it is very difficult to infer the validity of power law by observing graphs of R(n) alone. Next we introduce a new metric, "reachability degree," which is easy to measure and applicable to general networks where multicast trees are constructed as subtrees of a given spanning tree which we call Global Multicast Tree. The reachability degree is indicative of the structure of the Global Multicast Tree. We show that this metric provides a more reliable means for inferring the validity of the power law. Finally, we perform experiments on real and simulated networks to demonstrate the use of the new metric.

We present a universal algorithm for the classical online problem of caching or demand paging. We consider the caching problem when the page request sequence is drawn from an unknown probability distribution and the goal is to devise an efficient algorithm whose performance is close to the optimal online algorithm which has full knowledge of the underlying distribution. Most previous works have devised such algorithms for specific classes of distributions with the assumption that the algorithm has full knowledge of the source. In this paper, we present a universal and simple algorithm based on pattern matching for mixing sources (includes Markov sources). The expected performance of our algorithm is within 4 + o(1) times the optimal online algorithm (which has full knowledge of the input model and can use unbounded resources)

One-to-one codes are "one shot" codes that assign a distinct codeword to source symbols and are not necessarily prefix codes (more generally, uniquely decodable). For example, such codes arise when there exists an "end of message" channel symbol. Interestingly, as Wyner proved in 1972, for such codes the average code length can be smaller than the source entropy. By how much? We call this difference the anti-redundancy. Various authors over the years have shown that the anti-redundancy can be as big as minus the logarithm of the source entropy. However, to the best of our knowledge precise estimates do not exist. In this note, we consider a block code of length n generated by a binary memoryless source, and prove that the average anti-redundancy is -(1/2)log2n + C + F(n) + o(1) where C is a constant and either F(n) = O if log2(1 - p)/p is irrational (where p is the probability of generating a "0") or otherwise F(ri) is a fluctuating function as the code length increases. This relatively simple finding requires a combination of quite sophisticated analytic tools such as precise evaluation of Bernoulli sums, the saddle point method, and theory of distribution of sequences modulo 1

Analytic information theory aims at studying problems of information theory using analytic techniques of computer science and combinatorics. Following Hadamard's and Knuth's precept, we tackle these problems by complex analysis methods such as generating functions, Mellin transform, Fourier series, saddle point method, analytic poissonization and de-poissonization, and singularity analysis. This approach lies at the crossroad of computer science and information theory. In this talk, we concentrate on one facet of information theory (i.e., source coding better known as data compression), namely the redundancy rate problem and types. The redundancy rate problem for a class of sources is the determination of how far the actual code length exceeds the optimal (ideal) code length. The method of types is a powerful technique in information theory, large deviations, and analysis of algorithms. It reduces calculations of the probability of rare events to a combinatorial analysis. Two sequences are of the same type if they have the same empirical distribution. We shall argue that counting types can be accomplished efficiently by enumerating Eulerian paths (Markov types) or binary trees with a given path length (universal types). On the other hand, analysis of the redundancy rate problem for memoryless and Markov sources leads us to tree generating functions (e.g., arising in counting labeled rooted trees) studied extensively in computer science.

We propose a new method for a reliable identification of significant sequential episodes occurring within a window of size w in an event sequence modeled by a Markov source. As a measure of significance we use Ω∃(n, w), the number of windows containing the episode as a subsequence. We prove that Ω∃(n, w) is a sum of a φ-mixing sequence of random variables and therefore obeys the central limit theorem. This leads us to a computational formula for a threshold to identify significant episodes. The novelty of our method for Markov source stems from the fact that, instead of scoring the whole sequence using a Markov model, we compute the expected value of Ω∃(n, w) and its variance in order to estimate the threshold and compare it to the observed Ω∃(n, w). Since performance of the method critically depends on the model structure and parameters, we argue that variable-length Markov models of event streams are superior to fixed-length Markov models. We chose DNA sequences as event sources in experiments, and compared the performance of fixed-length Markov models with interpolated Markov models. This paper is an extension of our previous work in [8, 1] where we considered the problem of the reliable detection of significant episodes for memoryless sources.

In this paper the entropy rate of a binary hidden Markov process (HMP) defined by observing the output of a binary symmetric channel whose input is a first-order binary Markov process is studied. Despite the simplicity of the models involved, the characterization of this entropy is a long standing open problem. By presenting the probability of a sequence under the model as a product of random matrices, and show that the entropy rate sought is a top Lyapunov exponent of the product, which explains the difficulty in its explicit computation. The same product of random matrices to derive an explicit expression for a first order Taylor approximation of the entropy rate with respect to the parameter of the binary symmetric channel is applied. The accuracy of the approximation is validated against empirical simulation results and also extends the results to Renyi's entropy of any order.

This paper discusses the measure of complexity of a sequence called the complexity index. The complexity index captures the "richness of the language" used in a sequence. The measure is simple but quite intuitive. Sequences with low complexity index contain a large number of repeated substrings and they eventually become periodic (e.g., tandem repeats in a DNA sequence). The complexity index is used to characterize the sequence statistically and has a long history of applications in several fields, such as data compression, computational biology, data mining, computational linguistics, among others.

We present a method for a reliable detection of "unusual" sets of episodes in the form of many pattern sequences, scanned simultaneously for an occurrence as a subsequence in a large event stream within a window of size w. We also investigate the important special case of all permutations of the same sequence, which models the situation where the order of events in an episode does not matter, e.g., when events correspond to purchased market basket items. In order to build a reliable monitoring system, we compare obtained measurements to a reference model which in our case is a probabilistic model (Bernoulli or Markov). We first present a precise analysis that leads to a construction of a threshold. The difficulties of carrying out a probabilistic analysis for an arbitrary set of patterns, stems from the possible simultaneous occurrence of many members of the set as subsequences in the same window, the fact that the different patterns typically do have common symbols or common subsequences or possibly common prefixes, and that they may have different lengths. We also report on extensive experimental results, carried out on the Wal-Mart transactions database, that show a remarkable agreement with our theoretical analysis. This paper is an extension of our previous work where we laid out foundation for the problem of the reliable detection of an "unusual" episodes, but did not consider more than one episode scanned simultaneously for an occurrence.

There are three major classes of lossless compression: fixed-to-variable (FV) length codes, variable-to-fixed (VF) length codes, and finally variable-to-variable (VV) length codes. This paper presents the construction and analysis of a VV-code with small average and maximal redundancy that decays to zero as the average code length increases. A variable-to-variable (VV) code is a concatenation of variable-to-fixed and fixed-to-variable codes.

In this paper, the entropy rate of a hidden Markov process (HMP) is computed. The HMP entropy is expressed in terms of a measure Q, which solves an integral equation dependent on the parameters of the process. The measure is hard to extract from the equation in any explicit way. The study focuses on the regime where the channel parameter (noise) /spl epsiv/ is small.

The devastating effect of errors in adaptive data compression is a long-standing open problem. In this paper LZ'77 is changed theoretically and experimentally observed, such that in a significant proportion of LZ'77 phrases, there is more than one copy of the longest prefix in the compressed file. Once the redundant bits of LZ'77 have been identified, it is exploited for channel coding. For error correction and detection RS (255,255-2e) Reed-Solomon codes are used.

Recent years have seen a resurgence of interest in redundancy of lossless coding. The redundancy (regret) of universal fixed-to-variable length coding for a class of sources determines by how much the actual code length exceeds the optimal (ideal over the class) code length. In a minimax scenario one finds the best code for the worst source either in the worst case (called also maximal minimax) or on average. We first study the worst case minimax redundancy over a class of stationary ergodic sources and replace Shtarkov's bound by an exact formula. Among others, we prove that a generalized Shannon code minimizes the worst case redundancy, derive asymptotically its redundancy, and establish some general properties. This allows us to obtain precise redundancy for memoryless, Markov, and renewal sources. For example, we present the exact constant of the redundancy for memoryless and Markov sources by showing that the integer nature of coding contributes log(logm/(m-1))/logm+o(1) where m is the size of the alphabet. Then we deal with the average minimax redundancy and regret. Our approach here is orthogonal to most recent research in this area since we aspire to show that asymptotically the average minimax redundancy is equivalent to the worst case minimax redundancy for some classes of sources. After formulating some general bounds relating these two redundancies, we prove our assertion for memoryless and Markov sources. Nevertheless, we provide evidence that maximal redundancy of renewal processes does not have the same leading term as the average minimax redundancy (however, our general results show that maximal and average regrets are asymptotically equivalent).

Redundancy of universal codes for a class of sources determines by how much the actual code length exceeds the optimal code length. In the minimax scenario, one designs the best code for the worst source within the class. Such minimax redundancy comes in two flavors: average minimax or worst case minimax. We study the worst case minimax redundancy of universal block codes for Markovian sources of any order. We prove that the maximal minimax redundancy for Markov sources of order r is asymptotically equal to 1/2m/sup r/(m-1)log/sub 2/n+log/sub 2/A/sub m//sup r/-(lnlnm/sup 1/(m-1)/)/lnm+o(1), where n is the length of a source sequence, m is the size of the alphabet, and A/sub m//sup r/ is an explicit constant (e.g., we find that for a binary alphabet m=2 and Markov of order r=1 the constant A/sub 2//sup 1/=16/spl middot/G/spl ap/14.655449504 where G is the Catalan number). Unlike previous attempts, we view the redundancy problem as an asymptotic evaluation of certain sums over a set of matrices representing Markov types. The enumeration of Markov types is accomplished by reducing it to counting Eulerian paths in a multigraph. In particular, we propose exact and asymptotic formulas for the number of strings of a given Markov type. All of these findings are obtained by analytic and combinatorial tools of analysis of algorithms.

Limited memory and bounded communication resources require powerful data compression techniques, but at the same time noisy tetherless channels and/or corrupted file systems need error correction capabilities. Joint source-channel coding has emerged as a viable solution to this problem. The first practical joint source-channel coding algorithm was presented capable of correcting errors in the popular Lempel-Ziv'77 scheme without practically losing any compression power. This is possible since the LZ'77 (as well as gzip) encoder does not completely remove all redundancy. The inherent additional redundancy left by LZ'77 encoder was used succinctly by a channel coder (e.g., Reed Solomon coder) to protect against a limited number of errors. In addition to these, the scheme proposed is perfectly backward-compatible that is, a file compressed with error-resilient LZ'77 can still be decompressed by a common LZ'77 decoder. Algorithms and supporting experimental data were presented to support the system's claims and theoretical justifications.

Suppose one wants to detect "bad" or "suspicious" subsequences in event sequences. Whether an observed pattern of activity (in the form of a particular subsequence) is significant and should be a cause for alarm, depends on how likely it is to occur fortuitously. A long enough sequence of observed events will almost certainly contain any subsequence, and setting thresholds for alarm is an important issue in a monitoring system that seeks to avoid false alarms. Suppose a long sequence T of observed events contains a suspicious subsequence pattern S within it, where the suspicious subsequence S consists of m events and spans a window of size w within T. We address the fundamental problem: is a certain number of occurrences of a particular subsequence unlikely to be fortuitous (i.e., indicative of suspicious activity)? If the probability of fortuitous occurrences is high and an automated monitoring system flags it as suspicious anyway, then such a system will suffer from generating too many false alarms. We quantify the probability of such an S occurring in T within a window of size w, the number of distinct windows containing S as a subsequence, the expected number of such occurrences, its variance, and establishes its limiting distribution that allows to set up an alarm threshold so that the probability of false alarms is very small. We report on experiments confirming the theory and showing that we can detect bad subsequences with low false alarm rate.

Redundancy is defined as the excess of the code length over the optimal (ideal) code length. We study the average redundancy of an idealized arithmetic coding (for memoryless sources with unknown distributions) in which the Krichevsky and Trofimov (1981) estimator is followed by the Shannon-Fano code. We shall ignore here important practical implementation issues such as finite precisions and finite buffer sizes. In fact, our idealized arithmetic code can be viewed as an adaptive infinite precision implementation of arithmetic encoder that resembles Elias coding. However, we provide very precise results for the average redundancy that takes into account integer-length constraints. These findings are obtained by analytic methods of analysis of algorithms such as theory of distribution of sequences modulo 1 and Fourier series. These estimates can be used to study the average redundancy of codes for tree sources, and ultimately the context-tree weighting algorithms.

In this paper, we propose and study a pre-processing technique for improving performance of digital tree (trie)-based search algorithms under asymmetric memoryless sources. This technique (which we call a symmetrization of the source) bijectively maps the sequences of symbols from the original (asymmetric) source into symbols of an output alphabet resulting in a more uniform distribution. We introduce a criterion of efficiency for such a mapping, and demonstrate that a problem of finding an optimal construction for a given source (or universal) symmetrization transform is equivalent to a problem of constructing a minimum redundancy variable-length-to-block code for this source (or class of sources). Based on this result, we propose search algorithms that incorporate known (optimal for a given source and universal) variable-length-to-block codes and study their asymptotic behaviour. We complement our analysis with a description of an efficient algorithm for universal symmetrization of binary memoryless sources, and compare the performance of the resulting search structure with the standard tries.

Summary form only given. A wide variety of matrix transforms have been used for compression of image and video data. Transforms have also been used for motion estimation and quantization. One such transform is the singular-value decomposition (SVD) that relies on low rank approximations of the matrix for computational and storage efficiency. In this study, we describe the use of a variant of SVD in image and video compression. This variant, first proposed by Peleg and O'Leary, called semidiscrete decomposition (SDD), restricts the elements of the outer product vectors to 0/1/-1. Thus approximations of much higher rank can be stored for the same amount of storage. We demonstrate the superiority of SDD over SVD for a variety of compression schemes. We also show that DCT-based compression is still superior to SDD-based compression. We also demonstrate that SDD facilitates fast and accurate pattern matching and motion estimation; thus presenting excellent opportunities for improved compression.

In this paper, we propose a lossy data compression framework based on an approximate two-dimensional (2D) pattern matching (2D-PMC) extension of the Lempel-Ziv (1977, 1978) lossless scheme. This framework forms the basis upon which higher level schemes relying on differential coding, frequency domain techniques, prediction, and other methods can be built. We apply our pattern matching framework to image and video compression and report on theoretical and experimental results. Theoretically, we show that the fixed database model used for video compression leads to suboptimal but computationally efficient performance. The compression ratio of this model is shown to tend to the generalized entropy. For image compression, we use a growing database model for which we provide an approximate analysis. The implementation of 2D-PMC is a challenging problem from the algorithmic point of view. We use a range of techniques and data structures such as k-d trees, generalized run length coding, adaptive arithmetic coding, and variable and adaptive maximum distortion level to achieve good compression ratios at high compression speeds. We demonstrate bit rates in the range of 0.25-0.5 bpp for high-quality images and data rates in the range of 0.15-0.5 Mbps for a baseline video compression scheme that does not use any prediction or interpolation. We also demonstrate that this asymmetric compression scheme is capable of extremely fast decompression making it particularly suitable for networked multimedia applications.

: Csisz'ar and Shields have recently proved that the minimax redundancy for a class of renewal processes is \\Theta( p n) where n is the block length. This interesting result provides a first non-trivial bound on redundancy for a non-parametric family of processes. The present paper provides a precise estimate up to the constant term of the redundancy rate for such sources. The asymptotic expansion is derived by complex--analytic methods that include generating function representations, Mellin transforms, singularity analysis and saddle point estimates. This work places itself within the framework of analytic information theory. Keywords. Analytic information theory, redundancy, Mellin transform, saddle point method, singularity analysis. Unit'e de recherche INRIA Rocquencourt Domaine de Voluceau, Rocquencourt, BP 105, 78153 LE CHESNAY Cedex (France) T'el'ephone : (33) 01 39 63 55 11 -- T'el'ecopie : (33) 01 39 63 53 Variations analytiques sur le taux de redondance des processus de...

We consider a universal predictor based on pattern matching. Given a sequence X/sub 1/, ..., X/sub n/ drawn from a stationary mixing source, it predicts the next symbol X/sub n+1/ based on selecting a context of X/sub n+1/. The predictor, called the sampled pattern matching (SPM), is a modification of the Ehrenfeucht-Mycielski (1992) pseudorandom generator algorithm. It predicts the value of the most frequent symbol appearing at the so-called sampled positions. These positions follow the occurrences of a fraction of the longest suffix of the original sequence that has another copy inside X/sub 1/X/sub 2//spl middot//spl middot//spl middot/X/sub n/; that is, in SPM, the context selection consists of taking certain fraction of the longest match. The study of the longest match for lossless data compression was initiated by Wyner and Ziv in their 1989 seminal paper. Here, we estimate the redundancy of the SPM universal predictor, that is, we prove that the probability the SPM predictor makes worse decisions than the optimal predictor is O(n/sup -/spl nu//) for some 0</spl nu/< 1/2 as n/spl rarr//spl infin/. As a matter of fact, we show that we can predict K=O(1) symbols with the same probability of error.

We consider the search problem in which one finds a binary word among m words chosen randomly from the set of all words of fixed length n. It is well known that the optimal search is equivalent to the Huffman coding that requires on average log/sub 2/ m bits to be checked plus a small additional cost called the average redundancy. The latter is an oscillating function of m and is bounded between zero and 1-(1+lnln2)/In2/spl ap/0.0860713320. As a matter of fact, it is known that finding the optimal strategy for this problem is NP-hard. We propose here several simple randomized search strategies leading, respectively, to the following average redundancies: 1.332746177, 0.6113986565,0.4310617764, and 0.332746177, plus some small oscillations that we precisely characterize. These results should be compared to the optimal, but NP-hard, search algorithm. Our findings extend and make more precise results of Fedotov and Ryabko (2001).

In this paper we examine the average redundancy rate of a Lempel-Ziv 78 code with the k-error protocol. Storer and Reif (1997) have studied this modification of the Lempel-Ziv scheme and shown that it provides an efficient protection against error propagation while preserving the asymptotic optimality of the code. We refine this result by providing an asymptotic expression for the average redundancy rate of this code for memoryless sources. We have established our result by exploiting a relationship between a parsing scheme of the Lempel-Ziv encoder with the k-error protocol and a generalization of the digital search tree structure, and by using analytical techniques of the analysis of algorithms. We accompany our analysis with a number of experiments that test the validity of our theoretical result and demonstrate the effects of various additional modifications of the Lempel-Ziv algorithm.

As large-scale databases become commonplace, there has been significant interest in mining them for commercial purposes. One of the basic tasks that underlies many of these mining operations is querying of transaction sets for frequencies of specified attribute values. The size of these databases makes it important to develop summary structures capable of high compression ratios as well as supporting fast frequency queries. The nature of the problem and its differences with respect to traditional text compression allows very high compression ratios. In this paper, we propose a binary trie-based summary structure for representing transaction sets. We demonstrate that this trie structure, when augmented with an appropriate set of horizontal pointers, can support frequency queries several orders of magnitude faster than raw transaction data. We improve the memory characteristics of our scheme by compressing the trie into a Patricia trie and demonstrate that this does not have a significant adverse effect on frequency query time. We further reduce the size of this trie by selectively pruning branches to compute a "dominant" trie that is capable of approximate frequency querying. The complement trie called the "deviant" trie is also useful in many data mining applications. Recompressing the "dominant" trie into a Patricia trie results in further compression of the trie. Finally, we demonstrate that our binary compressed trie structure has better memory (compression) characteristics compared to related schemes. We support our claims with experimental results on datasets from the IBM synthetic association data generator.

We study the height of a digital search tree (DST) built from n random strings generated by an unbiased memoryless source (i.e., all symbols are equally likely). We shall argue that the height of such a tree is equivalent to the length of the longest phrase in the Lempel--Ziv parsing scheme that partitions a random sequence into n phrases. We also analyze the longest phrase in the Lempel--Ziv scheme in which a string of fixed length m is parsed into a random number of phrases. In the course of our analysis, we shall identify four natural regions of the height distribution and characterize them asymptotically for large n. In particular, for the region where most of the probability mass is concentrated, the asymptotic distribution of the height exhibits an exponential of a Gaussian distribution (with an oscillating term) around the most probable value $k_1 = \lfloor \log_2 n + \sqrt{2\log_2 n} - \log_2 ( \sqrt{2 \log_2 n} ) + \frac{1}{\log 2} - \frac{1}{2} \rfloor +1$. More precisely, we shall prove that the asymptotic distribution of a DST is concentrated on either the one point k 1 or the two points k 1 -1 and k 1 , which actually proves (slightly modified) Kesten's conjecture quoted in [Probab. Theory Related Fields, 79 (1988), pp. 509--542]. Finally, we compare our findings for DST with the asymptotic distributions of the height for other digital trees such as tries and PATRICIA tries. We derive these results by a combination of analytic methods such as generating functions, Laplace transform, the saddle point method, and ideas of applied mathematics such as linearization, asymptotic matching, and the WKB method. Our analysis makes certain assumptions about the forms of some of the asymptotic expansions as well as their asymptotic matching. We also present detailed numerical verification of our results.

We study asymptotically the redundancy of Huffman (and other) codes. It has been known from the inception of the Huffman (1952) code that in the worst case its redundancy-defined as the excess of the code length over the optimal (ideal) code length-is not more than one. However, to the best of our knowledge no precise asymptotic results have been reported in literature thus far. We consider here a memoryless binary source generating a sequence of length n distributed as binomial (n, p) with p being the probability of emitting 0. Based on the results of Stubley (1994), we prove that for p/M/); (+O(/spl rho//sup n/), /spl alpha/=N/M rational); where /spl alpha/=log/sub 2/(1-p)/p and /spl beta/=-log/sub 2/(1-p), /spl rho/<1, M, N are integers such that gcd (N, M)=1, and=x-[x] is the fractional part of x. The appearance of the fractal-like function explains the erratic behavior of the Huffman redundancy, and its "resistance" to succumb to a precise analysis. As a side result, we prove that the average redundancy of the Shannon block code is as n/spl rarr//spl infin/: R~/sub n//sup S/{( 1/2 +o(1), /spl alpha/ irrational); ( 1/2 -1/M (- 1/2 )); (+O(/spl rho//sup n/), /spl alpha/=N/M rational); where /spl rho/<1. Finally, we derive the redundancy of the Golomb (1966) code (for the geometric distribution) which can be viewed as a special case of the Huffman and Shannon codes, Golomb's code redundancy has only oscillating behavior (i.e., there is not convergent mode). These findings are obtained by analytic methods such as theory of distribution of sequences modulo 1 and Fourier series.

We propose a lossy data compression scheme based on an approximate two-dimensional pattern matching (2D-PMC) extension of the Lempel-Ziv lossless scheme. We apply the scheme to image and video compression and report on our theoretical and experimental results. Theoretically, we show that the so-called fixed database model leads to suboptimal compression. Furthermore, the compression ratio of this model is as low as the generalized entropy that we define. We use this model for our video compression scheme and present experimental results. For image compression we use a growing database model. The implementation of PD-PMC is a challenging problem from the algorithmic point of view. We use a range of novel techniques and data structures such as k-d trees, generalized run length coding, adaptive arithmetic coding, and variable and adaptive maximum distortion level to achieve good compression ratios at high compression speeds. We demonstrate bit rates in the range of 0.25-0.5 bpp for high-quality images and data rates in the range of 0.15-0.4 Mbit/s for video compression.

We propose a non-transform image compression scheme based on approximate 1D pattern matching, called pattern matching image compression (PMIC). The main idea behind it is a lossy extension of the Lempel-Ziv data compression scheme in which one searches for the longest prefix of an uncompressed image that approximately occurs in the already processed image. This main algorithm is enhanced with several new features such as searching for reverse approximate matching, recognizing sub-strings in images that are additively shifted versions of each other, introducing a variable and adaptive maximum distortion level D, and so forth. These enhancements are crucial to the overall quality of our scheme and their efficient implementation leads to algorithmic issues of interest in their own right. Both algorithmic and experimental results are presented. Our scheme turns out to be competitive with JPEG and wavelet compression for good quality graphical images. We also review related theoretical results.

The goal of this research is threefold: (i) to analyze generalized digital search trees, (ii) to derive the average profile (i.e., phrase length) of a generalization of the well-known parsing algorithm due to Lempel and Ziv, and (iii) to provide analytic tools to analyze asymptotically certain partial differential functional equations often arising in the analysis of digital trees. In the generalized Lempel--Ziv parsing scheme, one partitions a sequence of symbols from a finite alphabet into phrases such that the new phrase is the shortest substring seen in the past by at most b-1 phrases (b=1 corresponds to the original Lempel--Ziv scheme). Such a scheme can be analyzed through a generalized digital search tree in which every node is capable of storing up to b strings. In this paper, we investigate the depth of a randomly selected node in such a tree and the length of a randomly selected phrase in the generalized Lempel--Ziv scheme. These findings and some recent results allow us to compute the average redundancy of the generalized Lempel--Ziv code and compare it to the ordinary Lempel--Ziv code, leading to an optimal value of b. Analytic techniques of (precise) analyses of algorithms are used to establish most of these conclusions.

We investigate the basic question of information theory, namely, evaluation of Shannon entropy, and a more general Renyi (1961) entropy, for some discrete distributions (e.g., binomial, negative binomial, etc.). We aim at establishing analytic methods (i.e., those in which complex analysis plays a pivotal role) for such computations which often yield estimates of unparalleled precision. The main analytic tool used here is that of analytic poissonization and depoissonization. We illustrate our approach on the entropy evaluation of the binomial distribution, that is, we prove that for binomial (n, p) distribution Shannon's h/sub n/ becomes h/sub n//spl ap/ 1/2 ln n+ 1/2 +ln/spl radic/(2/spl pi/p(1-p))+/spl Sigma//sub k/spl ges/1/a/sub k/n/sup -k/ where a/sub k/ are explicitly computable constants. Moreover, we argue that analytic methods (e.g., complex asymptotics such as Rice's method and singularity analysis, Mellin transforms, poissonization, and depoissonization) can offer new tools for information theory, especially for studying second-order asymptotics (e.g., redundancy). In fact, there has been a resurgence of interest and a few successful applications of analytic methods to a variety of problems of information theory, therefore, we propose to name such investigations as analytic information theory.

We consider a slotted ring that allows simultaneous transmissions of messages by different nodes, known as ring with spatial reuse. To alleviate fairness problems that arise in such networks, policies have been proposed that operate in cycles and guarantee that a certain number of packets, not exceeding a given number called a quota, will be transmitted by every node in every cycle. We provide sufficient and necessary stability conditions that implicitly characterize the stability region for such rings. These conditions are derived by extending a technique developed for some networks of queues satisfying a monotonicity property. Our approach to instability is novel and its peculiar property is that it is derived from the instability of a dominant system. Interestingly, the stability region depends on the entire distribution of the message arrival process and the steady-state average cycle lengths of lower dimensional systems, leading to a region with nonlinear boundaries, the exact computation of which is in general intractable. Next, we introduce the notions of essential and absolute stability region. An arrival rate vector belongs to the former region if the system is stable under any arrival distribution with this arrival vector, while it belongs to the latter if there exists some distribution with this rate vector for which the system is stable. Using a linear programming approach, we derive bounds for these stability regions that depend only on conditional average cycle lengths. For the case of two nodes, we provide closed-form expressions for the essential stability region.

In this paper, we settle a long-standing open problem concerning the average redundancy r/sub n/ of the Lempel-Ziv'78 (LZ78) code. We prove that for a memoryless source the average redundancy rate attains asymptotically Er/sub n/=(A+/spl delta/(n))/log n+ O(log log n/log/sup 2/ n), where A is an explicitly given constant that depends on source characteristics, and /spl delta/(x) is a fluctuating function with a small amplitude. We also derive the leading term for the kth moment of the number of phrases. We conclude by conjecturing a precise formula on the expected redundancy for a Markovian source. The main result of this paper is a consequence of the second-order properties of the Lempel-Ziv algorithm obtained by Jacquet and Szpankowski (1995). These findings have been established by analytical techniques of the precise analysis of algorithms. We give a brief survey of these results since they are interesting in their own right, and shed some light on the probabilistic behavior of pattern matching based data compression.

A practical suboptimal (variable source coding) algorithm for lossy data compression is presented. This scheme is based on approximate string matching, and it naturally extends the lossless Lempel-Ziv (1977) data compression scheme. Among others we consider the typical length of an approximately repeated pattern within the first n positions of a stationary mixing sequence where D percent of mismatches is allowed. We prove that there exists a constant r/sub 0/(D) such that the length of such an approximately repeated pattern converges in probability to 1/r/sub 0/(D) log n (pr.) but it almost surely oscillates between 1/r/sub -/spl infin//(D) log n and 2/r/sub 1/(D) log n, where r/sub -/spl infin//(D)>r/sub 0/(D)>r/sub 1/(D)/2 are some constants. These constants are natural generalizations of Renyi entropies to the lossy environment. More importantly, we show that the compression ratio of a lossy data compression scheme based on such an approximate pattern matching is asymptotically equal to r/sub 0/(D). We also establish the asymptotic behavior of the so-called approximate waiting time N/sub l/ which is defined as the time until a pattern of length C repeats approximately for the first time. We prove that log N/sub l//l/spl rarr/r/sub 0/(D) (pr.) as l/spl rarr//spl infin/. In general, r/sub 0/(D)>R(D) where R(D) is the rate distortion function. Thus for stationary mixing sequences we settle in the negative the problem investigated by Steinberg and Gutman by showing that a lossy extension of the Wyner-Ziv (1989) scheme cannot be optimal.

We propose a non-transform image compression scheme based on approximate pattern matching, that we name pattern matching linage compression (PMIC). The main idea behind it is a lossy extension of the Lempel-Ziv data compression scheme in which one searches for the longest prefix of an uncompressed image that approximately occurs in the already processed image. We consider both the Hamming distance and the square error distortion. The theoretical basis for such a scheme was laid out by Luczak and Szpankowski [1994, 1995]. A straightforward implementation of the basic scheme described in Luczak and Szpankowski on real images (structured data) seems not to be attractive from a practical point of view. The main algorithm is therefore enhanced with several new features such as searching for reverse approximate matching, recognizing substrings in images that are additively shifted versions of each other, introducing a variable and adaptive maximum distortion level D, and so forth. These enhancements are crucial to the overall quality of our scheme.

We propose an image compression scheme based on approximate pattern matching, that we name pattern matching image compression (PMIC). We give new, efficient algorithms for performing computations motivated by this scheme, and describe the compression ratios experimentally obtained. The main idea is a lossy extension of the Lempel-Ziv (1977) data compression scheme in which one searches for the longest prefix of an uncompressed image that approximately occurs in the already processed image. It is enhanced with several new features such as searching for reverse approximate matching, recognizing substrings in images that are additively shifted versions of each other, introducing a variable and adaptive maximum distortion level, and so forth. Our scheme is competitive with JPEG and wavelet compression for graphical and photographical images, and it is provably suboptimal under some probabilistic assumptions concerning an image.

The goal of this contribution is twofold: (i) to introduce a generalized Lempel-Ziv parsing scheme, and (ii) to analyze second-order properties of some compression schemes based on the above parsing scheme. We consider a generalized Lempel-Ziv parsing scheme that partitions a sequence of length n into variable phrases (blocks) such that a new block is the longest substring seen in the past by at most b-1 phrases. The case b=1 corresponds to the original Lempel-Ziv scheme. In this paper, we investigate the size of a randomly selected phrase, and the average number of phrases of a given size through analyzing the so called b-digital search tree (b-DST) representation. For a memoryless source, we prove that the size of a typical phrase is asymptotically normally distributed. This result is new even for b=1, and b>1 is a non-trivial extension.

Consider the parsing algorithm developed by Lempel and Ziv (1978) that partitions a sequence of length n into variable phrases (blocks) such that a new block is the shortest substring not seen in the past as a phrase. In practice, the following parameters are of interest: number of phrases, the size of a phrase, the number of phrases of given size, and so forth. In this paper, we focus on the size of a randomly selected phrase, and the average number of phrases of a given size (the so-called average profile of phrase sizes). These parameters can be efficiently analyzed through a digital search tree representation. For a memoryless source with unequal probabilities of symbols generation (the so-called asymmetric Bernoulli model), we prove that the size of a typical phrase is asymptotically normally distributed with mean and variance explicitly computed. In terms of digital search trees, we prove the normal limiting distribution of the typical depth (i.e., the length of a path from the root to a randomly selected node). The latter finding is proved by a technique that belongs to the toolkit of the "analytical analysis of algorithms", and it seems to be novel in the context of data compression.>

T. Klove (see ibid., vol.41, p.298-300, 1995) analyzed the average worst case probability of undetected error for linear [n, k; q] codes of length n and dimension k over an alphabet of size q. The following sum: S/sub n/=/spl Sigma//sub i=1//sup n/(/sub i//sup n/)(/sup i///sub n/)/sup i/((1-i)/n)/sup n-i/ arose, which also has applications in coding theory, average case analysis of algorithms, and combinatorics. Klove conjectured an asymptotic expansion of this sum, and we prove its enhanced version. Furthermore, we consider a more challenging sum arising in the upper bound of the average worst case probability of undetected error over systematic codes derived by Massey (1978). Namely S/sub n,k/=/spl Sigma//sub i=1//sup n/(/sub i//sup n-k/)(/sup i///sub n/)/sup i/((1-i)/n)/sup n-i/ for k/spl ges/0. We obtain an asymptotic expansion of S/sub n,k/, and this leads to a conclusion that Massey's bound on the average worst case probability over all systematic codes is better for every k than the corresponding Klove's bound over all codes [n, k; q]. The technique used belongs to the analytical analysis of algorithms and is based on some enumeration of trees, singularity analysis, Lagrange's inversion formula, and Ramanujan's identities. In fact, S/sub n/, turns out to be related to the so-called Ramanujan's Q-function which finds many applications (e.g. hashing with linear probing, the birthday paradox problem, random mappings, caching, memory conflicts, etc.).

We consider a functional-differential equation of the form ah~(z, u)+,8h(z, u) = ~(zap, u).h(zuq, a)+ a(.z, u) with h(O, ti) = 1 where p + q = 1, cz,~are nonnegative constants, h~(.,.) denotes the partial derivative with respect to z, and a and z are complex numbers, This equation arises in numerous problems in combinatorics, computer science, data compression and molecular biology (e.g., complexity

This paper studies the asymptotics of the variance for the internal path length in a symmetric digital search tree under the Bernoulli model. This problem has been open until now. It is proved that the variance is asymptotically equal to $N \cdot 0.26600 + N \cdot \delta (\log _2 N)$, where N is the number of stored records and $\delta (x)$ is a periodic function of mean zero and a very small amplitude. This result completes a series of studies devoted to the asymptotic analysis of the variances of digital tree parameters in the symmetric case. In order to prove the previous result a number of nontrivial problems concerning analytic continuations and some others of a numerical nature had to be solved. In fact, some of these techniques are motivated by the methodology introduced in an influential paper by Flajolet and Sedgewick.

Suffix trees find several applications in computer science and telecommunications, most notably in algorithms on strings, data compressions, and codes. Despite this, very little is known about their typical behaviors. In a probabilistic framework, a family of suffix trees—further called b-suffix trees—built from the first n suffixes of a random word is considered. In this family a noncompact suffix tree (i.e., such that every edge is labeled by a single symbol) is represented by $b = 1$, and a compact suffix tree (i.e., without unary nodes) is asymptotically equivalent to $b \to \infty $ as $n \to \infty $. Several parameters of b-suffix trees are studied, namely, the depth of a given suffix, the depth of insertion, the height and the shortest feasible path. Some new results concerning typical (i.e., almost sure) behaviors of these parameters are established. These findings are used to obtain several insights into certain algorithms on words, molecular biology, and universal data compression schemes.

Digital tries occur in a variety of computer and communication algorithms, including symbolic manipulations, compiling, comparison-based searching and sorting, digital retrieval techniques, algorithms on strings, file systems, codes, and communication protocols. The depth of the PATRICIA trie in a probabilistic framework is studied. The PATRICIA trie is a digital tree in which nodes that would otherwise have only one branch have been collapsed into nodes having more than one branch. Because of this characteristic, the depth of the PATRICIA trie provides a measure on the compression of the keys stored in the trie. Here, n independent keys that are random strings of symbols from a V-ary alphabet are considered. This model is known as the Bernoulli model. This paper shows that the depth in the asymmetric case (i.e., symbols from the alphabet do not occur with the same probability) is asymptotically normally distributed. In the symmetric case, which surprisingly proved to be more difficult, the limiting generating function and the limiting distribution are presented. In either case, the results point to the conclusion that the PATRICIA trie is with high probability a well-balanced tree.

Recently, Wyner and Ziv (see ibid., vol.35, p.1250-8, 1989) have proved that the typical length of a repeated subword found within the first n positions of a stationary ergodic sequence is (1/h) log n in probability where h is the entropy of the alphabet. This finding was used to obtain several insights into certain universal data compression schemes, most notably the Lempel-Ziv data compression algorithm. Wyner and Ziv have also conjectured that their result can be extended to a stronger almost sure convergence. In this paper, we settle this conjecture in the negative in the so called right domain asymptotic, that is, during a dynamic phase of expanding the data base. We prove-under an additional assumption involving mixing conditions-that the length of a typical repeated subword oscillates almost surely (a.s.) between (1/h/sub 1/)log n and (1/h/sub 2/)log n where D>

The dynamic data structure management technique called hashing with lazy deletion (HwLD) is studied. A table managed under HwLD is built by a sequence of insertions and deletions of items. When hashing with lazy deletions, one does not delete items as soon as possible but keeps more items in the data structure than would be the case with immediate-deletion strategies. This deferral allows the use of a simpler deletion algorithm, leading to a lower overhead—in space and time—for the HwLD implementation. It is of interest to know how much extra space is used by HwLD. This paper investigates the maximum size and the excess space used by HwLD, under general probabilistic assumptions, by using the methodology of queueing theory. In particular, for the Poisson arrivals and general lifetime distribution of items, the excess space does not exceed the number of buckets in HwLD. As a byproduct of the analysis, the limiting distribution of the maximum queue length in an $M|G|\infty $ queueing system is also derived. The results generalize previous work in this area.

Consider a random word in which the individual symbols are drawn from a finite or infinite alphabet with symbol probabilities $p_i $ , and let $H_n $ be the height of the suffix tree constructed from the first n suffixes of this word. It is shown that $H_n $ is asymptotically close to $2\log n/\log (1/\sum_i p_i^2 )$ in many respects: the difference is $O(\log \log n)$ in probability, and the ratio tends to one almost surely and in the mean.

Wyner and Ziv (IEEE Trans. vol.IT-35, p.1250-8 of 1989) have proved that the typical length of a repeated subword found within the first n positions of a stationary sequence is (1/h) log n in probability where h is the entropy of the alphabet. They used this finding to obtain insights into certain universal data compression schemes, most notably the Lempel-Ziv algorithm. They have also conjectured that their result can be extended to a stronger almost sure convergence. This paper settles this conjecture in the negative. It proves, under some additional assumption regarding mixing conditions, that the length of a repeated subword oscillates with probability one between (1/h/sub 1/) log n and (1/h/sub 2/) log n where h/sub 2/>

A complete characterization of a digital tree, also called a trie, is presented from the depth viewpoint in a Markovian framework, that is, under the assumption that symbols in a key are Markov-dependent. The main findings show that asymptotically, as the number of keys n tends to infinity, the average depth becomes ED/sub n/ approximately (1/h/sub 1/) log N+c', and the variance is var D/sub n/ approximately alpha log n+c", where h/sub 1/ is the entropy of the (Markovian-dependent) alphabet, alpha is a parameter of the probabilistic model and c' and c" are constants. The symmetric independent model has alpha =0, hence in this case var D/sub n/=O(1). Limiting distribution is also derived for the depth D/sub n/, and in particular, it is shown that D/sub n/ tends to the normal distribution in all cases except the symmetric independent model. These results extend all previous analyses since most of them have been limited to independent models.>

The Patricia trie is a simple modification of a regular trie. By eliminating unary branching nodes, the Patricia achieves better performance than regular tries. However, the question is: how much on the average is the Patricia better? This paper offers a thorough answer to this question by considering some statistics of the number of nodes examined in a successful search and an unsuccessful search in the Patricia tries. It is shown that for the Patricia containing n records the average of the successful search length S n asymptotically becomes 1/ h 1 · ln n + O (1), and the variance of S n is either var S n = c · ln n + 0 (1) for an asymmetric Patricia or var S n = 0 (1) for a symmetric Patricia, where h 1 is the entropy of the alphabet over which the Patricia is built and c is an explicit constant. Higher moments of S n are also assessed. The number of nodes examined in an unsuccessful search U n is studied only for binary symmetric Patricia tries. We prove that the m th moment of the unsuccessful search length EU m n satisfies lim n →∞ EU m n /log m 2 n = 1, and the variance of U n is var U n = 0.87907. These results suggest that Patricia tries are very well balanced trees in the sense that a random shape of Patriciatries resembles the shape of complete trees that are ultimately balanced trees.

The interval searching algorithm for broadcast communications of Gallager and Tsybakov and Mikhailov is analyzed. Ultimate characterizations of the burst response of the algorithm, that is, when the number of collided packets becomes large is presented. Three quantities are of interest: the conflict resolution interval (CRI); the fraction of the resolved interval (RI); and the number of resolved packets (RP). If n is the multiplicity of a conflict, then it is proved that the mth moments of CRI, RI, and RP are $O(\log ^m n)$, $O(n^{ - m} )$ and $O(1)$, respectively. In addition, for the first two moments of these parameters precise asymptotic approximations are presented. The methodology proposed in this paper is applicable to asymptotic analysis of any problem that can be reduced to a solution of the functional equation$f(x) = 2^s \cdot f({x / 2}) \cdot a(x) + b(x)$ , where s is an integer and $a(x),b(x)$ are given functions.

A finite number of users communicating through a broadcast channel is considered. Each user has a buffer of infinite capacity, and a user randomly accesses the channel (ALOHA-type protocol). Moreover, only one packet per user might be sent in an access time. Both symmetric and asymmetric models are considered; that is, we assume either indistinguishable or distinguishable users. An exact analysis of the queue lengths in that type of system is not now available, and therefore, based on some algebraic studies, we shall present some lower and some upper bounds for the average queue lengths. These bounds are quite tight for a small number of users and acceptable for a wide range of input parameters in the symmetric case. In the asymmetric case the bounds are acceptable only for light input traffic and a small number of users.

This paper considers the reservation ALOHA scheme proposed by Roberts. Two random access disciplines for reservation packets are analyzed, random access without retransmission discrimination (ORD) and with retransmission discrimination (WRD). Previous analyses have been approximate. This paper provides an exact numerical analysis of the two-dimension state process and usable computable formulas for delay and throughput in terms of state probabilities, describes the range of parameters for which the system is stable, and presents numerical results.