Universal predictions of the next outcome of a binary sequence drawn from a Markov source with unknown parameters is considered. For a given source, the predictability is defined as the least attainable expected fraction of prediction errors. A lower bound is derived on the maximum rate at which the predictability is asymptotically approached uniformly over all sources in the Markov class. This bound is achieved by a simple majority predictor. For Bernoulli sources, bounds on the large deviations performance are investigated. A lower bound is derived for the probability that the fraction of errors will exceed the predictability by a prescribed amount Delta >0. This bound is achieved by the same predictor if Delta is sufficiently small.>

A practical suboptimal universal block source coding scheme, subject to a fidelity criterion, is proposed. The algorithm is an extension of the Lempel-Ziv algorithm and is based on string matching with distortion. It is shown that given average distortion D>0, the algorithm achieves a rate of exceeding R(D/2) for a large class of sources and distortion measures. Tighter bounds on the rate are derived for discrete memoryless sources and for memoryless Gaussian sources.>

The contents of error-protected frames can be intentionally altered as the frames traverse through a digital network. The check bits must be recomputed to conform with the altered text. A method is described for updating the check bits of a cyclic redundancy check (CRC) code, based on knowledge of the altered bits and their position in the frame. Unlike previous methods, its complexity is independent of the frame size.>

The problem of predicting the next outcome of an individual binary sequence using finite memory is considered. The finite-state predictability of an infinite sequence is defined as the minimum fraction of prediction errors that can be made by any finite-state (FS) predictor. It is proven that this FS predictability can be achieved by universal sequential prediction schemes. An efficient prediction procedure based on the incremental parsing procedure of the Lempel-Ziv data compression algorithm is shown to achieve asymptotically the FS predictability. Some relations between compressibility and predictability are discussed, and the predictability is proposed as an additional measure of the complexity of a sequence.>

A prototype problem in hypotheses testing is discussed. The problem of deciding whether an i.i.d. sequence of random variables has originated from a known source P/sub 1/ or an unknown source P/sub 2/ is considered. The exponential rate of decrease in type II probability of error under a constraint on the minimal rate of decrease in type I probability of error is chosen for a criterion of optimality. Using large deviations estimates, a decision rule that is based on the relative entropy of the empirical measure with respect to P/sub 1/ is proposed. In the case of discrete random variables, this approach yields weaker results than the combinatorial approach used by Hoeffding (1965). However, it enables the analysis to be extended to the general case of R/sup n/-valued random variables. Finally, the results are extended to the case where P/sub 1/ is an unknown parameter-dependent distribution that is known to belong to a set of distributions (P/sup 0//sub 1/, theta in Theta ).>

Various source coding schemes encode the set of integers using a binary representation of the integers to be encoded, prefixed by some information about the length of that representation. In the context of recency rank encoding, these can be regarded as attempts to assign codewords with lengths close to the logarithm of the integer to be encoded, or as attempts to construct a code for a distribution function Q(*) on the integers, where Q(k)=(1/k)/ Sigma /sub i/(1/i), i in I, and I is a finite set of positive integers to be encoded. It is shown that fixed-prefix encoding is equivalent to Huffman coding for the distribution Q(*).>

The decision problem of testing M hypotheses when the source is Kth-order Markov and there are M (or fewer) training sequences of length N and a single test sequence of length n is considered. K, M, n, N are all given. It is shown what the requirements are on M, n, N to achieve vanishing (exponential) error probabilities and how to determine or bound the exponent. A likelihood ratio test that is allowed to produce a no-match decision is shown to provide asymptotically optimal error probabilities and minimum no-match decisions. As an important serial case, the binary hypotheses problem without rejection is discussed. It is shown that, for this configuration, only one training sequence is needed to achieve an asymptotically optimal test.>

The authors estimate the order of a finite Markov source based on empirically observed statistics. The performance criterion adopted is to minimize the probability of underestimating the model order while keeping the overestimation probability exponent at a prescribed level. A universal asymptotically optimal test, in the sense just defined, is proposed for the case where a given integer is known to be the upper bound of the true order. For the case where such a bound is unavailable, an alternative rule based on the Lempel-Ziv data compression algorithm is shown to be asymptotically optimal also and computationally more efficient.>

Upper bounds are presented for the difference in entropy between that of a uniform scalar quantizer and that of anyN-dimensional quantizer. The bounds are universal in the sense that they suit every input density and every value of distortion. Bounds were found for some common distortion criteria.