On Martin-Löf (non-)convergence of Solomonoff's universal mixture

DOI10.1016/J.TCS.2014.12.004MaRDI QIDQ2348255zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Tor Lattimore, Marcus Hutter

Publication date 11 June 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2014.12.004

zbMATH Keywords

Kolmogorov complexitysemi-computable semi-measuresSolomonoff inductiontheory of computation

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Review text

The paper investigates the convergence of Solomonoff\({}^\prime{}\)s universal mixture on individual Martin-Löf random infinite strings. A universal mixture is defined as the infinite sum \(M(x) = \sum_{i=0}^{\infty} w_i\cdot \nu_i(x)\), \(x\in\{0,1\}^*,\) where \((w_i)_{i=0}^{\infty}\) is a lower semi-computable sequence of reals with \(\sum_{i=0}^{\infty} w_i \leq 1\) and \((\nu_i)_{i=0}^{\infty}\) is an enumeration of lower semi-computable semi-measures. The main result is the following. Let \(M\) be a universal mixture and define \(M(b|x) = M(x)^{-1}\sum_{i=0}^{\infty} w_i\cdot \nu_i(xb)\), \(b\in\{0,1\}\). Then there is a Martin-Löf random infinite string \(\alpha\in\{0,1\}^\omega\) and an \(\varepsilon>0\) such that the set \(D =\{ n: |M(\alpha_n|\alpha_1\cdots \alpha_{n-1})- \frac{1}{2}|>\varepsilon\}\) has upper density \(\limsup_{n\to\infty} (D\cap\{1,\dots,n\})/n>0\). This result also extends to the normalisation of universal mixtures. Finally, it is shown that there is a non-random infinite string \(\alpha\in\{0,1\}^\omega\) such that the sum \((U(0|\alpha_1\cdots \alpha_{n})- \frac{1}{2})^2+ (U(1|\alpha_1\cdots \alpha_{n})- \frac{1}{2})^2\) tends to \(0\) for all universal lower semi-computable semi-measures \(U\).

Recommendations

• On Martin-Löf Convergence of Solomonoff’s Mixture
• Algorithmic Learning Theory
• On semimeasures predicting Martin-Löf random sequences
• On generalized computable universal priors and their convergence
• On the existence and convergence of computable universal priors

Cites work

• A formal theory of inductive inference. Part I
• A philosophical treatise of universal induction
• Algorithmic Learning Theory
• An introduction to Kolmogorov complexity and its applications
• Complexity-based induction systems: Comparisons and convergence theorems
• scientific article; zbMATH DE number 4054673 (Why is no real title available?)
• scientific article; zbMATH DE number 1911266 (Why is no real title available?)
• On semimeasures predicting Martin-Löf random sequences
• On universal prediction and Bayesian confirmation
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• The context-tree weighting method: basic properties
• The definition of random sequences

Cited in

(4)

• On Martin-Löf Convergence of Solomonoff’s Mixture
• A NOTE ON THE LEARNING-THEORETIC CHARACTERIZATIONS OF RANDOMNESS AND CONVERGENCE
• Algorithmic Learning Theory
• On the existence and convergence of computable universal priors

This page was built for publication: On Martin-Löf (non-)convergence of Solomonoff's universal mixture

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