Sphere-covering, measure concentration, and source coding

Suppose A is a finite set, let P be a discrete distribution on A, and let M be an arbitrary "mass" function on A. We give a precise characterization of the most efficient way in which A/sup n/ can be almost-covered using spheres of a fixed radius. An almost-covering is a subset C/sub n/ of A/sup n/, such that the union of the spheres centered at the points of C/sub n/ has probability close to one with respect to the product distribution P/sup n/. Spheres are defined in terms of a single-letter distortion measure on A/sup n/, and an efficient covering is one with small mass M/sup n/(C/sub n/). In information-theoretic terms, the sets C/sub n/ are rate-distortion codebooks, but instead of minimizing their size we seek to minimize their mass. With different choices for M and the distortion measure on A our results give various corollaries as special cases, including Shannon's classical rate-distortion theorem, a version of Stein's lemma (in hypothesis testing), and a new converse to some measure-concentration inequalities on discrete spaces. Under mild conditions, we generalize our results to abstract spaces and nonproduct measures.