Some properties of sequential predictors for binary Markov sources
- 1 May 1993
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 39 (3) , 887-892
- https://doi.org/10.1109/18.256496
Abstract
Universal prediction 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.Keywords
This publication has 8 references indexed in Scilit:
- Optimal prefetching via data compressionPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Universal prediction of individual sequencesIEEE Transactions on Information Theory, 1992
- Entropy and Information TheoryPublished by Springer Nature ,1990
- Estimating a probability using finite memoryIEEE Transactions on Information Theory, 1986
- Universal coding, information, prediction, and estimationIEEE Transactions on Information Theory, 1984
- Compression of individual sequences via variable-rate codingIEEE Transactions on Information Theory, 1978
- Compound Bayes Predictors for Sequences with Apparent Markov StructureIEEE Transactions on Systems, Man, and Cybernetics, 1977
- Principles of Random WalkPublished by Springer Nature ,1976