Mathematics – Probability
Scientific paper
1999-10-12
Mathematics
Probability
29 pages. See also http://www.stat.purdue.edu/~yiannis/
Scientific paper
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.
No associations
LandOfFree
Efficient sphere-covering and converse measure concentration via generalized coding theorems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Efficient sphere-covering and converse measure concentration via generalized coding theorems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient sphere-covering and converse measure concentration via generalized coding theorems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-675235