1999/10/12 by Ioannis Kontoyiannis, Kontoyiannis, Ioannis · 1 citation
Computer Science · Engineering · Mathematics · #28A35 (primary) #60E15 #60F10 (secondary) #94A15 #FOS: Computer and information sciences #FOS: Mathematics #Functional Analysis (math.FA) #Information Theory (cs.IT) #Mathematical Analysis and Transform Methods #Probability (math.PR) #Sparse and Compressive Sensing Techniques #Wireless Communication Security Techniques #cs.IT #math.FA #math.IT #math.PR #msc:28A35 #msc:60E15 #msc:60F10 #msc:94A15
paper · pdf · doi:10.48550/arxiv.math/9910062
29 pages. See also http://www.stat.purdue.edu/~yiannis/
openalex publication_date 1999/10/12 · arxiv created 2000/09/27 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Suppose A is a finite set equipped with a probability measure P and let M be a ``mass'' function on A. We give a probabilistic characterization of the most efficient way in which An can be almost-covered using spheres of a fixed radius. An almost-covering is a subset Cn of An, such that the union of the spheres centered at the points of Cn has probability close to one with respect to the product measure Pn. An efficient covering is one with small mass Mn(Cn); n is typically large. With different choices for M and the geometry on A our results give various corollaries as special cases, including Shannon's data compression 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 non-product measures.