A Tight Upper Bound on Kolmogorov Complexity and Uniformly Optimal Prediction

This paper links the concepts of Kolmogorov complexity (in complexity theory) and Hausdorff dimension (in fractal geometry) for a class of recursive (computable) ω -languages. It is shown that the complexity of an infinite string contained in a Σ ₂ -definable set of strings is upper bounded by the Hausdorff dimension of this set and that this upper bound is tight. Moreover, we show that there are computable gambling strategies guaranteeing a uniform prediction quality arbitrarily close to the optimal one estimated by Hausdorff dimension and Kolmogorov complexity provided the gambler's adversary plays according to a sequence chosen from a Σ ₂ -definable set of strings. We provide also examples which give evidence that our results do not extend further in the arithmetical hierarchy. Received February 1995, and in revised form February 1997, and in final form October 1997.