A Remark on Unified Error Exponents: Hypothesis Testing, Data Compression and Measure Concentration
View / Open Files
Publication Date
2003Journal Title
Stochastic Inequalities and Applications
ISBN
978-3-0348-9428-9
Publisher
Springer
Volume
56
Pages
23-32
Type
Book chapter
This Version
AM
Metadata
Show full item recordCitation
Kontoyiannis, I., & Sezer, A. D. (2003). A Remark on Unified Error Exponents: Hypothesis Testing, Data Compression and Measure Concentration. Springer, Stochastic Inequalities and Applications. [Book chapter]. https://doi.org/10.1007/978-3-0348-8069-5_3
Abstract
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 A n can be covered using spheres of a fixed radius. A covering is a subset C n of A n with the property that most of the elements of A n are within some fixed distance from at least one element of C n , and “most of the elements” means a set whose probability is exponentially close to one (with respect to the product distribution P n ). An efficient covering is one with small mass M n (C n ). 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.
Keywords
math.PR, math.PR, math.OC
Identifiers
External DOI: https://doi.org/10.1007/978-3-0348-8069-5_3
This record's DOI: https://doi.org/10.17863/CAM.35430
Rights
Licence:
http://www.rioxx.net/licenses/all-rights-reserved
Statistics
Total file downloads (since January 2020). For more information on metrics see the
IRUS guide.