2002/10/03 by Ioannis Kontoyiannis, Kontoyiannis, Ioannis, Ali Devin Sezer +1
Mathematics · #FOS: Mathematics #Optimization and Control (math.OC) #Probability (math.PR) #math.OC #math.PR
paper · pdf · doi:10.48550/arxiv.math/0210055
10 pages, 1 figure
arxiv created 2002/10/03 · arxiv updated 2009/11/30
Let A be finite set equipped with a probability distribution P, and let M be a "mass" function on A. A characterization is given for the most efficient way in which An can be covered using spheres of a fixed radius. A covering is a subset Cn of An with the property that most of the elements of An are within some fixed distance from at least one element of Cn, and "most of the elements" means a set whose probability is exponentially close to one (with respect to the product distribution Pn). An efficient covering is one with small mass Mn(Cn). With different choices for the geometry on A, this characterization gives various corollaries as special cases, including Marton's error-exponents theorem in lossy data compression, Hoeffding's optimal hypothesis testing exponents, and a new sharp converse to some measure concentration inequalities on discrete spaces.