%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Universal Convergence of Semimeasures %% %% on Individual Random Sequences %% %% Marcus Hutter: Start: 18.11.03 %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newif\ifconf\conftrue % conference style versus no-style %-------------------------------% % Document-Style % %-------------------------------% \ifconf % envcountsame for correct numbering of Theorems! \documentclass[oribibl,envcountsame]{llncs} \usepackage{latexsym} \pagestyle{headings} \sloppy \else \documentclass[12pt,twoside]{article} \usepackage{latexsym} \def\contentsname{\centering Contents} \pagestyle{myheadings} \markboth{\sc Marcus Hutter \& Andrej Muchnik, IDSIA-14-04 }{\sc On the Convergence of Universal Semimeasures} \setcounter{tocdepth}{4} \setcounter{secnumdepth}{2} \topmargin=0mm \oddsidemargin=5mm \evensidemargin=5mm \textwidth=15cm \textheight=22cm \sloppy \fi %-------------------------------% % My Math-Spacings % %-------------------------------% \def\,{\mskip 3mu} \def\>{\mskip 4mu plus 2mu minus 4mu} \def\;{\mskip 5mu plus 5mu} \def\!{\mskip-3mu} \def\dispmuskip{\thinmuskip= 3mu plus 0mu minus 2mu \medmuskip= 4mu plus 2mu minus 2mu \thickmuskip=5mu plus 5mu minus 2mu} \def\textmuskip{\thinmuskip= 0mu \medmuskip= 1mu plus 1mu minus 1mu \thickmuskip=2mu plus 3mu minus 1mu} \textmuskip \def\eqsp{\vspace{0ex}} \def\beq{\dispmuskip\eqsp\begin{equation}} \def\eeq{\eqsp\end{equation}\textmuskip} \def\beqn{\dispmuskip\eqsp\begin{displaymath}}\def\eeqn{\eqsp\end{displaymath}\textmuskip} \def\bqa{\dispmuskip\eqsp\begin{eqnarray}} \def\eqa{\eqsp\end{eqnarray}\textmuskip} \def\bqan{\dispmuskip\eqsp\begin{eqnarray*}} \def\eqan{\eqsp\end{eqnarray*}\textmuskip} %-------------------------------% % Macro-Definitions % %-------------------------------% \ifconf\else \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{definition}[theorem]{Definition} \newtheorem{proposition}[theorem]{Proposition} \newenvironment{keywords}{\centerline{\bf\small Keywords}\vspace{-1ex}\begin{quote}\small}{\par\end{quote}\vskip 1ex} \fi \def\ftheorem#1#2#3{\begin{theorem}[#2]\label{#1} #3 \end{theorem} } \def\fcorollary#1#2#3{\begin{corollary}[#2]\label{#1} #3 \end{corollary} } \def\flemma#1#2#3{\begin{lemma}[#2]\label{#1} #3 \end{lemma} } \def\fdefinition#1#2#3{\begin{definition}[#2]\label{#1} #3 \end{definition} } \def\fproposition#1#2#3{\begin{proposition}[#2]\label{#1} #3 \end{proposition} } \def\ftablex#1#2#3{\begin{tablex}[#2]\label{#1} #3 \end{tablex} } \def\ffigurex#1#2#3#4{{#4}\begin{figurex}[#2]\label{#1}#3\end{figurex}} \def\paragraph#1{\vspace{1ex}\noindent{\bf{#1.}}} \def\paradot#1{\vspace{1ex}\noindent{\bf{#1.}}} \def\paranodot#1{\vspace{1ex}\noindent{\bf{#1}}} \def\myparskip{\vspace{1.5ex plus 1ex minus 1ex}\noindent} \def\toinfty#1{\stackrel{#1\to\infty}{\longrightarrow}} \def\nq{\hspace{-1em}} \def\qed{\hspace*{\fill}$\Box\quad$\vspace{1ex plus 0.5ex minus 0.5ex}} \def\odt{{\textstyle{1\over 2}}} \def\eps{\varepsilon} % for small positive number \def\epstr{\epsilon} % for empty string \def\qmbox#1{{\quad\mbox{#1}\quad}} \def\argmax{\mathop{\rm arg\,max}} % maxarg \def\argmin{\mathop{\rm arg\,min}} % minarg \def\equa{\stackrel+=} % don't put around another braces, messes up spacings \def\leqa{\tabcolsep=0.5ex \begin{tabular}{c} \\[-4ex] $\scriptstyle\hspace{-0.2ex}+$ \\[-1.3ex] $\leq$ \end{tabular}} \def\geqa{\tabcolsep=0.5ex \begin{tabular}{c} \\[-4ex] $\scriptstyle\hspace{0.1ex}+$ \\[-1.3ex] $\geq$ \end{tabular}} \def\eqm{\stackrel\times=} % for some reason \def\leqm{\tabcolsep=0.5ex \begin{tabular}{c} \\[-4ex] $\scriptstyle\hspace{-0.2ex}\times$ \\[-1.3ex] $\leq$ \end{tabular}} \def\geqm{\tabcolsep=0.5ex \begin{tabular}{c} \\[-4ex] $\scriptstyle\hspace{0.1ex}\times$ \\[-1.3ex] $\geq$ \end{tabular}} \def\v{} \def\l{{\ell}} % length of string or program \def\M{{\cal M}} % Set of prob. distributions \def\X{{\cal X}} % input/perception set/alphabet \def\Y{{\cal Y}} % output/action set/alphabet \def\S{{\cal S}} % some set \def\Q{{\cal Q}} \def\E{{\bf E}} % Expectation value \def\P{{\bf P}} % Expectation value \def\B{\{0,1\}} % Binary set (or \set{B}) \def\Km{K\!m} \def\MM{M} % Solomonoff's prior \def\e{{\rm e}} % natural e \def\a{\alpha} \def\o{\omega} \ifconf\def\Set#1{{\if#1Q{I\:\!\!\!\!#1}\else\if#1Z{Z\!\!\!Z}\else{I\!\!#1}\fi\fi}} \else\def\Set#1{{\if#1Q{I\;\!\!\!\!\!#1}\else\if#1Z{Z\!\!\!Z}\else{I\!\!#1}\fi\fi}} \fi \def\lb{\log} \def\sumprime{\mathop{{\sum\nolimits'}}} \def\mrcp{the chain rule} \def\text#1{\mbox{\scriptsize{#1}}} \begin{document} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % T i t l e - P a g e % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \ifconf \title{Universal Convergence of Semimeasures \\ on Individual Random Sequences} \author{Marcus Hutter\inst{1} \and Andrej Muchnik\inst{2}} % \authorrunning{Marcus Hutter and Andrej Muchnik} \institute{IDSIA, Galleria 2, CH-6928 Manno-Lugano, Switzerland% \footnote[0]{This work was partially supported by the Swiss National Science Foundation (SNF grant 2100-67712.02) and the Russian Foundation for Basic Research (RFBR grants N04-01-00427 and N02-01-22001).} \\ \email{\hspace{1.3ex}marcus@idsia.ch, \hspace{4.2ex} http://www.idsia.ch/$^{_{_\sim}}\!$marcus} \and Institute of New Technologies, 10 Nizhnyaya Radischewskaya \\ \hspace{2ex}Moscow 109004, Russia, \hspace{7.5ex} \email{muchnik@lpcs.math.msu.ru} } \maketitle \else \title{\vskip -25mm\normalsize\sc Technical Report \hfill IDSIA-14-04 \vskip 2mm\bf\LARGE\hrule height5pt \vskip 3mm \sc\centerline{Universal Convergence of Semimeasures} on Individual Random Sequences% \thanks{This work was partially supported by the Swiss National Science Foundation (SNF grant 2100-67712.02) and the Russian Foundation for Basic Research (RFBR grants N04-01-00427 and N02-01-22001).} \vskip 4mm \hrule height2pt \vskip 0mm} \author{ {\bf Marcus Hutter}\\[3mm] \normalsize IDSIA, Galleria 2, CH-6928\ Manno-Lugano, Switzerland\\ \normalsize marcus@idsia.ch \hspace{8.5ex} http://www.idsia.ch/$^{_{_\sim}}\!$marcus\\[5mm] {\bf Andrej Muchnik}\\[3mm] \normalsize Institute of New Technologies, 10 Nizhnyaya Radischewskaya\\ \normalsize Moscow 109004, Russia \hfill \normalsize muchnik@lpcs.math.msu.ru %\\[5mm] } %\date{30 November 2002} \maketitle \fi \ifconf\else\vspace{-5mm}\fi \begin{abstract} Solomonoff's central result on induction is that the posterior of a universal semimeasure $\MM$ converges rapidly and with probability 1 to the true sequence generating posterior $\mu$, if the latter is computable. Hence, $M$ is eligible as a universal sequence predictor in case of unknown $\mu$. Despite some nearby results and proofs in the literature, the stronger result of convergence for all (Martin-L{\"o}f) random sequences remained open. Such a convergence result would be particularly interesting and natural, since randomness can be defined in terms of $\MM$ itself. We show that there are universal semimeasures $M$ which do not converge for all random sequences, i.e.\ we give a partial negative answer to the open problem. We also provide a positive answer for some non-universal semimeasures. We define the incomputable measure $D$ as a mixture over all computable measures and the enumerable semimeasure $W$ as a mixture over all enumerable nearly-measures. We show that $W$ converges to $D$ and $D$ to $\mu$ on all random sequences. The Hellinger distance measuring closeness of two distributions plays a central role. \end{abstract} \ifconf\else \begin{keywords} Sequence prediction; Algorithmic Information Theory; universal enumerable semimeasure; mixture distributions; posterior convergence; Martin-L{\"o}f randomness; quasimeasures. \end{keywords} \fi \iffalse ACM class: I.2.6. Learning F. Theory of Computation F.1.3. Complexity Measures and Classes E.4. Coding and Information Theory G.3. Probability and Statistics Abstract without Macro-Definitions: Solomonoff's central result on induction is that the posterior of a universal semimeasure M converges rapidly and with probability 1 to the true sequence generating posterior mu, if the latter is computable. Hence, M is eligible as a universal sequence predictor in case of unknown mu. Despite some nearby results and proofs in the literature, the stronger result of convergence for all (Martin-Loef) random sequences remained open. Such a convergence result would be particularly interesting and natural, since randomness can be defined in terms of M itself. We show that there are universal semimeasures M which do not converge for all random sequences, i.e. we give a partial negative answer to the open problem. We also provide a positive answer for some non-universal semimeasures. We define the incomputable measure D as a mixture over all computable measures and the enumerable semimeasure W as a mixture over all enumerable nearly-measures. We show that W converges to D and D to mu on all random sequences. The Hellinger distance measuring closeness of two distributions plays a central role. \end{abstract} \fi %false \ifconf\else\pagebreak\fi %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction}\label{secIntro} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %------------------------------% %\paradot{Universal induction} %------------------------------% A sequence prediction task is defined as to predict the next symbol $x_n$ from an observed sequence $x=x_1...x_{n-1}$. The key concept to attack general prediction problems is Occam's razor, and to a less extent Epicurus' principle of multiple explanations. The former/latter may be interpreted as to keep the simplest/all theories consistent with the observations $x_1...x_{n-1}$ and to use these theories to predict $x_n$. Solomonoff \cite{Solomonoff:64,Solomonoff:78} formalized and combined both principles in his universal prior $M$ which assigns high/low probability to simple/complex environments $x$, hence implementing Occam and Epicurus. Formally it is a mixture of all enumerable semimeasures. An abstract characterization of $M$ by Levin \cite{Zvonkin:70} is that $M$ is a universal enumerable semimeasure in the sense that it multiplicatively dominates all enumerable semimeasures. %------------------------------% %\paradot{Posterior convergence} %------------------------------% Solomonoff's \cite{Solomonoff:78} central result is that if the probability $\mu(x_n|x_1...x_{n-1})$ of observing $x_n$ at time $n$, given past observations $x_1...x_{n-1}$ is a computable function, then the universal posterior $M_n:=M(x_n|x_1...x_{n-1})$ converges (rapidly!) {\em with $\mu$-probability 1} (w.p.1) for $n\to\infty$ to the true posterior $\mu_n:=\mu(x_n|x_1...x_{n-1})$, hence $M$ represents a universal predictor in case of unknown ``true'' distribution $\mu$. Convergence of $M_n$ to $\mu_n$ w.p.1 tells us that $M_n$ is close to $\mu_n$ for sufficiently large $n$ for almost all sequences $x_1x_2...$. It says nothing about whether convergence is true for any {\em particular} sequence (of measure 0). %------------------------------% %\paranodot{Martin-L{\"o}f randomness and convergence} %------------------------------% Martin-L{\"o}f (M.L.) randomness is the standard notion for randomness of individual sequences \cite{MartinLoef:66,Li:97}. A M.L.-random sequence passes {\em all} thinkable effective randomness tests, e.g.\ the law of large numbers, the law of the iterated logarithm, etc. In particular, the set of all $\mu$-random sequences has $\mu$-measure 1. It is natural to ask whether $M_n$ converges to $\mu_n$ (in difference or ratio) individually for all M.L.-random sequences. Clearly, Solomonoff's result shows that convergence may at most fail for a set of sequences with $\mu$-measure zero. A convergence result for M.L.-random sequences would be particularly interesting and natural in this context, since M.L.-randomness can be defined in terms of $M$ itself \cite{Levin:73random}. Despite several attempts to solve this problem \cite{Vovk:87,Vitanyi:00,Hutter:03unipriors}, it remained open \cite{Hutter:03mlconv}. %------------------------------% %\paranodot{What's new?} %------------------------------% In this paper we construct an M.L.-random sequence and show the existence of a universal semimeasure which does not converge on this sequence, hence answering the open question negatively for some $M$. It remains open whether there exist (other) universal semimeasures, probably with particularly interesting additional structure and properties, for which M.L.-convergence holds. The main positive contribution of this work is the construction of a non-universal enumerable semimeasure $W$ which M.L.-converges to $\mu$ as desired. As an intermediate step we consider the incomputable measure $\hat D$, defined as a mixture over all computable measures. We show posterior M.L.-convergence of $W$ to $\hat D$ and of $\hat D$ to $\mu$. The Hellinger distance measuring closeness of two posterior distributions plays a central role in this work. %------------------------------% %\paragraph{Contents} %------------------------------% The paper is organized as follows: In Section~\ref{secUniM} we give basic notation and results (for strings, numbers, sets, functions, asymptotics, computability concepts, prefix Kolmogorov complexity), and define and discuss the concepts of (universal) (enumerable) (semi)measures. % Section~\ref{secConv} summarizes Solomonoff's and G\'acs' results on posterior convergence of $M$ to $\mu$ with probability 1. Both results can be derived from a bound on the expected Hellinger sum. We present an improved bound on the expected exponentiated Hellinger sum, which implies very strong assertions on the convergence rate. % In Section~\ref{secMLNconv} we investigate whether convergence for all Martin-L{\"o}f random sequences hold. We construct a universal semimeasure $M$ and an $\mu$-M.L.-random sequence on which $M$ does not converge to $\mu$ for some computable $\mu$. % In Section~\ref{secMLconv} we present our main positive result. We derive a finite bound on the Hellinger sum between $\mu$ and $\hat D$, which is exponential in the randomness deficiency of the sequence and double exponential in the complexity of $\mu$. This implies that the posterior of $\hat D$ M.L.-converges to $\mu$. % Finally, in Section~\ref{secNUESW} we show that $W$ is non-universal and asymptotically M.L.-converges to $\hat D$. % Section~\ref{secDisc} contains discussion and outlook. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Notation \& Universal Semimeasures $\MM$}\label{secUniM} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %------------------------------% \noindent {\bf Strings.} %------------------------------% Let $i,k,n,t\in\Set N=\{1,2,3,...\}$ be natural numbers, $x,y,z\in\X^*=\bigcup_{n=0}^\infty\X^n$ be finite strings of symbols over finite alphabet $\X\ni a,b$. We denote strings $x$ of length $\l(x)=n$ by $x=x_1x_2...x_n\in\X^n$ with $x_t\in\X$ and further abbreviate $x_{k:n}:=x_k x_{k+1}...x_{n-1}x_n$ for $k\leq n$, and $x_{0 : \MM(x)\geq w_\nu\!\cdot\!\nu(x)\;\forall x\in\X^*$.} \eeqn }%------------------------------% % From now on we consider the (in a sense) largest class $\M$ which is relevant from a constructive point of view (but see \cite{Schmidhuber:02gtm,Hutter:03unipriors} for even larger constructive classes), namely the class of {\em all} semimeasures, which can be enumerated (=effectively be approximated) from below: \beq\label{Mclassdef} \M:= \;\mbox{class of all enumerable semimeasures}. \eeq Solomonoff \cite[Eq.(7)]{Solomonoff:64} defined the universal posterior $\MM(x|y)=M(xy)/M(y)$ with $M(x)$ defined as the probability that the output of a universal monotone Turing machine starts with $x$ when provided with fair coin flips on the input tape. % Levin \cite{Zvonkin:70} has shown that this $M$ is a universal enumerable semimeasure. % Another possible definition of $M$ is as a (Bayes) mixture \cite{Solomonoff:64,Zvonkin:70,Solomonoff:78,Li:97,Hutter:03unipriors}: $\tilde M(x)=\sum_{\nu\in\M}2^{-K(\nu)}\nu(x)$, where $K(\nu)$ is the length of the shortest program computing function $\nu$. % Levin \cite{Zvonkin:70} has shown that the class of {\em all} enumerable semimeasures is enumerable (with repetitions), hence $\tilde M$ is enumerable, since $K$ is co-enumerable. Hence $\tilde\MM\in\M$, which implies \beq\label{Mdom} M(x) \;\geq\; w_{\tilde M} \tilde M(x) \;\geq\; w_{\tilde M} 2^{-K(\nu)}\nu(x) \;=\; w'_\nu\nu(x), \qmbox{where} w'_\nu\eqm 2^{-K(\nu)}. % \quad \forall x\in\X^*, \forall\nu\in\M \eeq Up to a multiplicative constant, $\MM$ assigns higher probability to all $x$ than any other enumerable semimeasure. All $M$ have the same very slowly decreasing (in $\nu$) domination constants $w'_\nu$, essentially because $\MM\in\M$. We drop the prime from $w'_\nu$ in the following. % The mixture definition $\tilde M$ immediately generalizes to arbitrary weighted sums of (semi)measures over other countable classes than $\M$, but the class may not contain the mixture, and the domination constants may be rapidly decreasing. We will exploit this for the construction of the non-universal semimeasure $W$ in Sections~\ref{secMLconv} and \ref{secNUESW}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Posterior Convergence with Probability 1}\label{secConv} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% The following convergence results for $M$ are well-known \cite{Solomonoff:78,Li:97,Hutter:02spupper}. %------------------------------% \ftheorem{thConv}{Convergence of $M$ to $\mu$ w.p.1}{ %------------------------------% For any universal semimeasure $M$ and any computable measure $\mu$ it holds: \beqn \mbox{$M(x'_n|x_{0$, i.e.\ $0_{1:\infty}$ is $\mu$-random. On the other hand, one can show that $M(0_{1$ makes the expression infinite for some (Bernoulli) distribution $\mu$ (however we choose $\nu$). For $\nu=M$ the expression can become already infinite for $\alpha>\odt$ and some computable measure $\mu$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Non-Convergence in Martin-L{\"o}f Sense}\label{secMLNconv} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Convergence of $M(x_n|x_{t \\ \nu^t(x0)\!+\!\nu^t(x1) & \mbox{if} & \l(x)\a_{1:\l(x)}^t \eeqn On-sequence, i.e.\ for $x=\a_{1:n}$, $\nu^t$ is somewhere in-between $0$ and $2^{-\l(x)}$. Since sequence $\a:=\lim_t\a^t$ is $\lambda$.M.L.-random it contains $01$ infinitely often, actually $\a_n\a_{n+1}=01$ for a non-vanishing fraction of $n$. In the following we fix such an $n$. For $t\geq n$ we get \beqn \nu^t(\a_{\a_{1:n}\geq\a_{1:n}^t,\text{ since }\a_n=0\nq\nq\nq}) = \nu^t(\a_{n$ large enough such that $\a_{1:n+1}^t=\a_{1:n+1}$ we get: \beqn \nu^t(\a_{1:n}) = \nu^t(\a_{1:n}^t) \geq \nu^t(\underbrace{\a_{1:n}^t 0}_{\nq\nq\nq<\a_{1:n+1}^t,\text{ since }\a_{n+1}=1\nq\nq\nq}) = 2^{-n-1} \quad\Rightarrow\quad \nu(\a_{1:n})\geq 2^{-n-1} \eeqn This ensures $\nu(\a_{1:n})\geq 2^{-n-1}\geq\odt M(\a_{1:n})$ by (\ref{arand}). Let $M$ be any universal semimeasure and $0<\gamma<{1\over 5}$. Then $M'(x):=(1-\gamma)\nu(x)+\gamma M(x)\,\forall x$ is also a universal semimeasure with \bqan M'(\a_n|\a_{\;\; {1\over 2}. \eqan For instance for $\gamma={1\over 9}$ we have $M'(\a_n|\a_{0 \\ ii) & \mbox{for}\; \v p^1,...,\v p^m \in\Set R_+^N & h(\v p^1,\v p^m) & \leq & \displaystyle 3\sum_{k=2}^m k^2\,h(\v p^{k-1},\v p^k) \end{array} \eeqn }%------------------------------% \paragraph{Proof} $(i)$ For any $x,y\in\Set R$ and $\beta>0$ we have $(x+y)^2\leq (1+\beta)x^2+(1+\beta^{-1})y^2$. Inserting $x=\sqrt{p_i}-\sqrt{r_i}$ and $y=\sqrt{r_i}-\sqrt{q_i}$ and summing over $i$ proves $(i)$. $(ii)$ Apply $(i)$ for the triples $(\v p^k,\v p^{k+1},\v p^m)$ for and in order of $k=1,2,...,m-2$ with $\beta=\beta_k=k(k+1)$ and finally use $\prod_{j=1}^{k-2}(1+\beta_j^{-1})\leq \e \leq 3$. \qed %------------------------------% %\paragraph{Expected to individual bound} %------------------------------% % Integral test -> submartingale -> universal submartingale -> randomness deficiency We need a way to convert expected bounds to bounds on individual M.L.\ random sequences, sort of a converse of ``M.L.\ implies w.p.1''. Consider for instance the Hellinger sum $H(\o):=\sum_{t=1}^\infty h_t(\mu,\rho)/\ln w^{-1}$ between two computable measures $\rho\geq w\!\cdot\!\mu$. Then $H$ is an enumerable function and Lemma~\ref{lemHBounds} implies $\E[H]\leq 1$, hence $H$ is an integral $\mu$-test. $H$ can be increased to an enumerable $\mu$-submartingale $\bar H$. The universal $\mu$-submartingale $M/\mu$ multiplicatively dominates all enumerable submartingales (and hence $\bar H$). Since $M/\mu\leq 2^{d_\mu(\o)}$, this implies the desired bound $H(\o) \leqm 2^{d_\mu(\o)}$ for individual $\o$. We give a self-contained direct proof, explicating all important constants. %------------------------------% \flemma{lemE2I}{Expected to Individual Bound}{ %------------------------------% Let $F(\o)\geq 0$ be an enumerable function and $\mu$ be an enumerable measure and $\eps>0$ be co-enumerable. Then: \beqn \qmbox{If} \E_\mu[F] \;\leq\; \eps \qmbox{then} F(\o) \;\leqm\; \eps\!\cdot\! 2^{K(\mu,F,\,^1\!/\eps)+d_\mu(\o)} \quad \forall\o \eeqn where $d_\mu(\o)$ is the $\mu$-randomness deficiency of $\o$ and $K(\mu,F,\,^1\!/\eps)$ is the length of the shortest program for $\mu$, $F$, and $^1\!/\eps$. }%------------------------------% Lemma~\ref{lemE2I} roughly says that for $\mu$, $F$, and $\eps\eqm\E_\mu[F]$ with short program ($K(\mu,F,^1\!/\eps)=O(1)$) and $\mu$-random $\o$ ($d_\mu(\o)=O(1)$) we have $F(\o)\leqm \E_\mu[F]$. \paragraph{Proof} Let $F(\o)=\lim_{n\to\infty}F_n(\o)=\sup_n F_n(\o)$ be enumerated by an increasing sequence of computable functions $F_n(\o)$. $F_n(\o)$ can be chosen to depend on $\o_{1:n}$ only, i.e.\ $F_n(\o)=F_n(\o_{1:n})$ is independent of $\o_{n+1:\infty}$. Let $\eps_n\!\!\searrow\eps$ co-enumerate $\eps$. We define \beqn \bar\mu_n(\o_{1:k}) \;:=\; \eps_n^{-1} \nq\ifconf\nq\;\fi \sum_{\o_{k+1:n}\in\X^{n-k}}\nq \mu(\o_{1:n})F_n(\o_{1:n}) \;\;\mbox{for}\;\; k\leq n, \qmbox{and} \bar\mu_n(\o_{1:k})=0 \;\;\mbox{for}\;\; k>n. \eeqn $\bar\mu_n$ is a computable semimeasure for each $n$ (due to $\E_\mu[F_n]\leq\eps$) and increasing in $n$, since \bqan \bar\mu_n(\o_{1:k}) & \!\!\geq\!\! & 0 \;=\; \bar\mu_{n-1}(\o_{1:k}) \qmbox{for} k\geq n \qmbox{and} \\ \bar\mu_n(\o_{k_0$. $\delta_{k-1}\leq\delta_k$ implies \beqn {\hat\delta_{k-1}(x)\over\hat\delta_k(x)} \;\leq\; {\delta_k(\epstr)\over\delta_{k-1}(\epstr)} \;\leq\; {\delta_{k-1}(\epstr)+\eps_k\over\delta_{k-1}(\epstr)} \;=\; 1+{\eps_k\over\delta_{k-1}(\epstr)} \;\leq\; 1+{\eps_k\over\eps_O}, \eeqn where $O:=\min\{i\in J_{k-1}\}=O(1)$. Note that $J_{k-1}\ni k_0$ is not empty. Since $\hat\delta_{k-1}$ and $\hat\delta_k$ are measures, Lemma~\ref{lemHBounds} applies and shows $\E_{\hat\delta_{k-1}}[H^k]\leq \ln(1+{\eps_k\over\eps_O})\leq {\eps_k\over\eps_O}$. Exploiting $\eps_{k_0}\mu\leq\hat\delta_{k-1}$, this implies $\E_\mu[H^k]\leq {\eps_k\over\eps_O\eps_{k_0}}$. Lemma \ref{lemE2I} then implies $H^k(\o)\leqm {\eps_k\over\eps_O\eps_{k_0}}\cdot 2^{K(\mu,H^k,\eps_O\eps_{k_0}/\eps_k)+d_\mu(\o)}$. Similarly as in $(i)$ we can bound \beqn K(\mu,H^k,\eps_{k_0}/\eps_O\eps_k) \leqa K(J_k|k)+K(k)+K(k_0) \leqa k+2\lb k+2\lb k_0, \qmbox{hence} \eeqn\vspace{-3ex} \beqn\textstyle H^k(\o) \;\leqm\; {\eps_k\over\eps_O\eps_{k_0}}\!\cdot\!k_0^2 k^2 2^k c_\o \;\eqm\; k_0^8 2^{k_0}k^{-4}c_\o, \qmbox{where} c_\o:=2^{d_\mu(\o)}. \eeqn Chaining this bound via Lemma~\ref{lemHChain}$(ii)$ we get for $k_1>k_0$: \bqan \sum_{t=1}^n h_t(\hat\delta_{k_0},\hat\delta_{k_1}) &\leq& \sum_{t=1}^n 3 \!\!\sum_{k=k_0+1}^{k_1}\!\! (k\!-\!k_0\!+\!1)^2 h_t(\hat\delta_{k-1},\hat\delta_k) \\ &\leq& 3 \!\!\sum_{k=k_0+1}^{k_1}\!\! k^2 H^k(\o) \;\leqm\; 3k_0^8 2^{k_0}c_\o \!\!\sum_{k=k_0+1}^{k_1}\!\! k^{-2} \;\leq\; 3k_0^7 2^{k_0}c_\o \eqan If we now take $k_1\to\infty$ we get $\sum_{t=1}^n h_t(\hat\delta_{k_0},\hat D) \leqm 3k_0^7 2^{k_0+d_\mu(\o)}$. Finally let $n\to\infty$. \qed The main properties allowing for proving $\hat D\to\mu$ were that $\hat D$ is a measure with approximations $\hat\delta_k$, which are computable in a certain sense. $\hat D$ is a mixture over all enumerable/computable measures and hence incomputable. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{M.L.-Converging Enumerable Semimeasure $W$}\label{secNUESW} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% The next step is to enlarge the class of computable measures to an enumerable class of semimeasures, which are still sufficiently close to measures in order not to spoil the convergence result. For convergence w.p.1.\ we could include {\em all} semimeasures (Theorem~\ref{thConv}). M.L.-convergence seems to require a more restricted class. Included non-measures need to be zero on long strings. We convert semimeasures $\nu$ to ``quasimeasures'' $\tilde\nu$ as follows: \beqn \tilde\nu(x_{1:n}):=\nu(x_{1:n}) \qmbox{if} \sum_{y_{1:n}}\nu(y_{1:n}) \;>\; 1- {1\over n} \qmbox{and} \nu(x_{1:n}):=0 \qmbox{else.} \eeqn If the condition is violated for some $n$ it is also violated for all larger $n$, hence with $\nu$ also $\tilde\nu$ is a semimeasure. $\tilde\nu$ is enumerable if $\nu$ is enumerable. So if $\nu_1,\nu_2,...$ is an enumeration of all enumerable semimeasures, then $\tilde\nu_1,\tilde\nu_2,...$ is an enumeration of all enumerable quasimeasures. The for us important properties are that $\tilde\nu_i\leq\nu_i$ -and- if $\nu_i$ is a measure, then $\tilde\nu_i\equiv\nu_i$, else $\nu_i(x)=0$ for sufficiently long $x$. We define the enumerable semimeasure \beqn W(x):=\sum_{i=1}^\infty\eps_i\tilde\nu_i(x), \qmbox{and\ifconf\else note that\fi} D(x)=\sum_{i\in J} \eps_i\tilde\nu_i(x) \;\;\mbox{with}\;\; J:=\{i:\tilde\nu_i\mbox{ is measure}\} \eeqn with $\eps_i=i^{-6}2^{-i}$ as before. %------------------------------% \fproposition{proWtoD}{Convergence of enumerable $W$ to incomputable $D$}{ %------------------------------% For every computable measure $\mu$ and for $\o$ being $\mu$-random, the following holds for $t\to\infty$: \beqn (i) \;\; {W(\o_{1:t})\over D(\o_{1:t})}\to 1, \ifconf\quad\else\qquad\fi (ii) \;\; {W(\o_t|\o_{