Show simple item record

dc.contributor.authorKontoyiannis, Ioannis
dc.contributor.authorSezer, Ali Devin
dc.date.accessioned2019-01-17T00:31:07Z
dc.date.available2019-01-17T00:31:07Z
dc.date.issued2003
dc.identifier.isbn978-3-0348-9428-9
dc.identifier.urihttps://www.repository.cam.ac.uk/handle/1810/288115
dc.description.abstractLet 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.
dc.publisherSpringer
dc.subjectmath.PR
dc.subjectmath.PR
dc.subjectmath.OC
dc.titleA Remark on Unified Error Exponents: Hypothesis Testing, Data Compression and Measure Concentration
dc.typeBook chapter
prism.endingPage32
prism.publicationDate2003
prism.publicationNameStochastic Inequalities and Applications
prism.startingPage23
prism.volume56
dc.identifier.doi10.17863/CAM.35430
dcterms.dateAccepted2002-01-15
rioxxterms.versionofrecord10.1007/978-3-0348-8069-5_3
rioxxterms.versionAM
rioxxterms.licenseref.urihttp://www.rioxx.net/licenses/all-rights-reserved
rioxxterms.licenseref.startdate2003
dc.contributor.orcidKontoyiannis, Ioannis [0000-0001-7242-6375]
dcterms.isPartOfStochastic Inequalities and Applications
rioxxterms.typeBook chapter
cam.orpheus.counter20
rioxxterms.freetoread.startdate2022-01-16


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record