Universal coding and prediction on ergodic random points

DOI10.1017/BSL.2022.18MaRDI QIDQ5044311zbMATH OpenOpenAlexWikidataFDO

Authors Łukasz Dębowski, Tomasz Steifer

Publication date 25 October 2022

Published in The Bulletin of Symbolic Logic (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

algorithmic randomnessprediction by partial matchingstationary ergodic processesuniversal codinguniversal prediction

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Nonparametric estimation (62G05) Inference from stochastic processes and prediction (62M20) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Source coding (94A29)

Abstract: Suppose that we have a method which estimates the conditional probabilities of some unknown stochastic source and we use it to guess which of the outcomes will happen. We want to make a correct guess as often as it is possible. What estimators are good for this? In this work, we consider estimators given by a familiar notion of universal coding for stationary ergodic measures, while working in the framework of algorithmic randomness, i.e, we are particularly interested in prediction of Martin-L"of random points. We outline the general theory and exhibit some counterexamples. Completing a result of Ryabko from 2009 we also show that universal probability measure in the sense of universal coding induces a universal predictor in the prequential sense. Surprisingly, this implication holds true provided the universal measure does not ascribe too low conditional probabilities to individual symbols. As an example, we show that the Prediction by Partial Matching (PPM) measure satisfies this requirement with a large reserve.

Recommendations

• Universal probability-free prediction
• Universal prediction of individual sequences
• scientific article; zbMATH DE number 1552327
• An efficient universal prediction algorithm for unknown sources with limited training data
• A universal predictor based on pattern matching

Cites work

• A constructive version of Birkhoff's ergodic theorem for Martin-Löf random points
• A formal theory of inductive inference. Part II
• A Note on the Ergodic Theorem of Information Theory
• A sandwich proof of the Shannon-McMillan-Breiman theorem
• A simple randomized algorithm for sequential prediction of ergodic time series
• A universal algorithm for sequential data compression
• Algorithmic randomness and complexity.
• Applications of Effective Probability Theory to Martin-Löf Randomness
• Applications of Kolmogorov complexity and universal codes to nonparametric estimation of characteristics of time series
• Compression-Based Methods for Nonparametric Prediction and Estimation of Some Characteristics of Time Series
• Compression-based methods of statistical analysis and prediction of time series
• Computability of probability measures and Martin-Löf randomness over metric spaces
• Effectively closed sets of measures and randomness
• Ergodic theorems for individual random sequences
• Ergodic theory, entropy
• Generalised entropies and asymptotic complexities of languages
• Grammar-based codes: a new class of universal lossless source codes
• Guessing the next output of a stationary process
• scientific article; zbMATH DE number 5485513 (Why is no real title available?)
• scientific article; zbMATH DE number 893887 (Why is no real title available?)
• scientific article; zbMATH DE number 7434519 (Why is no real title available?)
• Information Theory Meets Power Laws
• Information theory. Coding theorems for discrete memoryless systems
• Martin-Löf random points satisfy Birkhoff's ergodic theorem for effectively closed sets
• Measures and their random reals
• On a definition of random sequences with respect to conditional probability
• On finding predictors for arbitrary families of processes
• On the Vocabulary of Grammar-Based Codes and the Logical Consistency of Texts
• On universal algorithms for classifying and predicting stationary processes
• Prediction and dimension
• Prediction of random sequences and universal coding
• Prequential probability: principles and properties
• Randomness and non-ergodic systems
• Randomness conservation inequalities; information and independence in mathematical theories
• Randomness for non-computable measures
• Recognizing strong random reals
• The definition of random sequences
• The dimension of ergodic random sequences
• The Individual Ergodic Theorem of Information Theory
• The Smallest Grammar Problem
• The strong law of large numbers for sequential decisions under uncertainty
• Two inequalities implied by unique decipherability
• Uniform test of algorithmic randomness over a general space
• Upcrossing inequalities for stationary sequences and applications
• Weighted sums of certain dependent random variables

Cited in

(2)

• Universal prediction of random binary sequences in a noisy environment
• scientific article; zbMATH DE number 3496010 (Why is no real title available?)

This page was built for publication: Universal coding and prediction on ergodic random points

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