Efficient sphere-covering and converse measure concentration via generalized coding theorems
| dc.creator | Kontoyiannis, Ioannis | |
| dc.date | 1999-10-12 | |
| dc.date | 2000-09-27 | |
| dc.date.accessioned | 2026-07-07T08:18:18Z | |
| dc.date.available | 2026-07-07T08:18:18Z | |
| dc.description | 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 A^n can be almost-covered using spheres of a fixed radius. An almost-covering is a subset C_n of A^n, such that the union of the spheres centered at the points of C_n has probability close to one with respect to the product measure P^n. An efficient covering is one with small mass M^n(C_n); 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. | |
| dc.description | 29 pages. See also http://www.stat.purdue.edu/~yiannis/ | |
| dc.identifier | https://arxiv.org/abs/math/9910062 | |
| dc.identifier | http://arxiv.org/abs/math/9910062 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/134385 | |
| dc.subject | Probability | |
| dc.subject | Information Theory | |
| dc.subject | Functional Analysis | |
| dc.subject | 60E15, 28A35 (primary), 94A15, 60F10 (secondary) | |
| dc.title | Efficient sphere-covering and converse measure concentration via generalized coding theorems | |
| dc.type | text |