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.