A simple randomized algorithm for sequential prediction of ergodic time series

DOI10.1109/18.796420MaRDI QIDQ4503433zbMATH OpenOpenAlexFDO

Authors László Györfi, Gusztáv Morvai, Gábor Lugosi

Publication date 7 September 2000

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0805.3091

zbMATH Keywords

ergodic processesMarkov processeson-line learningsequential predictionuniversal prediction

Mathematics Subject Classification ID

Prediction theory (aspects of stochastic processes) (60G25) Sequential statistical methods (62L99) Inference from stochastic processes and prediction (62M20) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: We present a simple randomized procedure for the prediction of a binary sequence. The algorithm uses ideas from recent developments of the theory of the prediction of individual sequences. We show that if the sequence is a realization of a stationary and ergodic random process then the average number of mistakes converges, almost surely, to that of the optimum, given by the Bayes predictor. The desirable finite-sample properties of the predictor are illustrated by its performance for Markov processes. In such cases the predictor exhibits near optimal behavior even without knowing the order of the Markov process. Prediction with side information is also considered.

Recommendations

• Sequential Prediction of Unbounded Stationary Time Series
• Nonparametric sequential prediction of stationary time series
• On prediction of individual sequences
• Some properties of sequential predictors for binary Markov sources
• Randomized prediction of individual sequences

Cited in

(29)

• Universal prediction of random binary sequences in a noisy environment
• On prediction of individual sequences
• Randomized prediction of individual sequences
• On universal algorithms for classifying and predicting stationary processes
• Intermittent estimation of stationary time series
• Nonparametric sequential prediction of stationary time series
• Blackwell prediction for categorical data
• Some Stochastic Properties of Memoryless Individual Sequences
• Sequential Prediction of Unbounded Stationary Time Series
• scientific article; zbMATH DE number 3934270 (Why is no real title available?)
• scientific article; zbMATH DE number 4048837 (Why is no real title available?)
• Weakly universally consistent static forecasting of stationary and ergodic time series via local averaging and least squares estimates
• scientific article; zbMATH DE number 524376 (Why is no real title available?)
• On delayed prediction of individual sequences
• Universal coding and prediction on ergodic random points
• Long‐term prediction intervals with many covariates
• On unstable and unoptimal prediction
• Learning whenever learning is possible: universal learning under general stochastic processes
• Prediction with a short memory
• Nonparametric sequential prediction for stationary processes
• NONPARAMETRIC KERNEL‐BASED SEQUENTIAL INVESTMENT STRATEGIES
• High-confidence predictions under adversarial uncertainty
• High-confidence predictions under adversarial uncertainty
• Universal regression with adversarial responses
• Universally consistent online learning with arbitrarily dependent responses
• Universal online learning with unbounded losses: memory is all you need
• An empirical study of the complexity and randomness of prediction error sequences
• Sensor networks: from dependence analysis via matroid bases to online synthesis
• On universal estimates for binary renewal processes

This page was built for publication: A simple randomized algorithm for sequential prediction of ergodic time series

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4503433)