Universal schemes for sequential decision from individual data sequences
- 1 July 1993
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 39 (4) , 1280-1292
- https://doi.org/10.1109/18.243445
Abstract
Sequential decision algorithms are investigated, under a family of additive performance criteria, for individual data sequences, with various application areas in information theory and signal processing. Simple universal sequential schemes are known, under certain conditions, to approach optimality uniformly as fast as n-1 log n, where n is the sample size. For the case of finite-alphabet observations, the class of schemes that can be implemented by finite-state machines (FSM's), is studied. It is shown that Markovian machines with sufficiently long memory exist that are asymptotically nearly as good as any given FSM (deterministic or randomized) for the purpose of sequential decision. For the continuous-valued observation case, a useful class of parametric schemes is discussed with special attention to the recursive least squares (RLS) algorithm.Keywords
This publication has 41 references indexed in Scilit:
- Markovian Forecast ProcessesJournal of the American Statistical Association, 1987
- Estimating a probability using finite memoryIEEE Transactions on Information Theory, 1986
- Vector quantization in speech codingProceedings of the IEEE, 1985
- The performance of universal encodingIEEE Transactions on Information Theory, 1981
- Universal modeling and codingIEEE Transactions on Information Theory, 1981
- An Algorithm for Vector Quantizer DesignIEEE Transactions on Communications, 1980
- Thek-extended set-compound estimation problem in a nonregular family of distrubutions over [θ, θ+1)Annals of the Institute of Statistical Mathematics, 1979
- Linear Prediction of SpeechPublished by Springer Nature ,1976
- Linear prediction: A tutorial reviewProceedings of the IEEE, 1975
- A new interpretation of information rateIEEE Transactions on Information Theory, 1956