Fractal dimension and logarithmic loss unpredictability

AbstractWe show that the Hausdorff dimension equals the logarithmic loss unpredictability for any set of infinite sequences over a finite alphabet. Using computable, feasible, and finite-state predictors, this equivalence also holds for the computable, feasible, and finite-state dimensions. Combining this with recent results of Fortnow and Lutz (Proc. 15th Ann. Conf. on Comput. Learning Theory (2002) 380), we have a tight relationship between prediction with respect to logarithmic loss and prediction with respect to absolute loss