Fractal Dimension and Logarithmic Loss Unpredictability

John M. Hitchcock

Abstract:
We 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 (2002), we have a tight relationship between prediction with respect to logarithmic loss and prediction with respect to absolute loss.