Universal coding and prediction on ergodic random points

Bulletin of Symbolic Logic 28 (3):387-412 (2022)
  Copy   BIBTEX

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öf 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 measure satisfies this requirement with a large reserve.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,616

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Ergodic theorems and the basis of science.Karl Petersen - 1996 - Synthese 108 (2):171 - 183.
Computability of the ergodic decomposition.Mathieu Hoyrup - 2013 - Annals of Pure and Applied Logic 164 (5):542-549.
A Constructive View on Ergodic Theorems.Bas Spitters - 2006 - Journal of Symbolic Logic 71 (2):611 - 623.
Słabe łamanie ergodyczności vs. determinizm.Andrzej Fuliński - 2015 - Zagadnienia Filozoficzne W Nauce 59:83-100.
The ergodic hierarchy, randomness and Hamiltonian chaos.Joseph Berkovitz, Roman Frigg & Fred Kronz - 2006 - Studies in History and Philosophy of Modern Physics 37 (4):661-691.
Prediction and estimation of a random fluctuation.Wayne Lee & W. R. Garner - 1966 - Journal of Experimental Psychology 71 (4):516.
Prediction, embodiment, and representation.István Aranyosi - 2019 - Behavioral and Brain Sciences 42.

Analytics

Added to PP
2022-05-04

Downloads
4 (#1,426,245)

6 months
2 (#668,348)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Tomasz Steifer
Polish Academy of Sciences

Citations of this work

No citations found.

Add more citations

References found in this work

Effectively closed sets of measures and randomness.Jan Reimann - 2008 - Annals of Pure and Applied Logic 156 (1):170-182.
Recognizing strong random reals.Daniel Osherson - 2008 - Review of Symbolic Logic 1 (1):56-63.

Add more references