A STRONG VERSION OF THE REDUNDANCY-CAPACITY THEOREM OF UNIVERSAL CODING

The capacity of the channel induced by a given class of sources is wel l known to be an attainable lower bound on the redundancy of universal codes with respect to this class, both in the minimax sense and in th e Bayesian (maximin)sense. We show that this capacity is essentially a lower bound also in a stronger sense, that is, for ''most'' sources i n the class. This result extends Rissanen's lower bound for parametric families. We demonstrate the applicability of this result in several examples, e.g., parametric families with growing dimensionality, piece wise-fixed sources, arbitrarily varying sources, and noisy samples of learnable functions. Finally, we discuss implications of our results t o statistical inference.