The problem of optimal rate universal coding is considered in the context of rate-distortion theory. A D-semifaithful universal coding scheme for discrete memoryless sources is given. The main result is a refined covering lemma based on the random coding argument and the method of types. The average codelength of the code is shown to approach its lower bound, the rate-distortion function, at a rate O(n/sup -1/log n), and this is conjectured to be optimal based on a result of A.J. Pilc (1968). Issues of constructiveness and universality are addressed.>

The results by P. Hall and E.J. Hannan (1988) on optimization of histogram density estimators with equal bin widths by minimization of the stochastic complexity are extended and sharpened in two separate ways. As the first contribution, two generalized histogram estimators are constructed. The first has unequal bin widths which, together with the number of the bins, are determined by minimization of the stochastic complexity using dynamic programming. The other estimator consists of a mixture of equal bin width estimators, each of which is defined by the associated stochastic complexity. As the main contribution in the present work, two theorems are proved, which together extend the universal coding theorems to a large class of data generating densities. The first gives an asymptotic upper bound for the code redundancy in the order of magnitude, achieved with a special predictive type of histogram estimator, which sharpens a related bound. The second theorem states that this bound cannot be improved upon by any code whatsoever.>