The complexity of stochastic sequences

摘要

We review and slightly strengthen known results on the Kolmogorov complexity of prefixes of effectively random sequences. First, there are recursively random sequences such that for any computable, non-decreasing and unbounded function f and for almost all n, the uniform complexity of the length n prefix of the sequence is bounded by f(n). Second, a similar result with bounds of the form f(n)logn holds for partial-recursively random sequences.Furthermore, we demonstrate that there is no Mises–Wald–Church stochastic sequence such that all non-empty prefixes of the sequence have Kolmogorov complexity O(logn). This implies a sharp bound for the complexity of the prefixes of Mises–Wald–Church stochastic and of partial-recursively random sequences. As an immediate corollary to these results, we obtain the known separation of the classes of recursively random and of Mises–Wald–Church stochastic sequences.