Approximating Probability Distributions Using Small Sample Spaces |
| |
Authors: | Yossi Azar Rajeev Motwani Joseph Naor |
| |
Institution: | (1) Computer Science Department, Tel Aviv University; Tel Aviv 69978, Israel; E-mail: azar@math.tau.ac.il, IL;(2) Computer Science Department, Stanford University; Stanford, CA 94305, USA; E-mail: rajeev@cs.stanford.edu, US;(3) Computer Science Department, Technion; Haifa 32000, Israel; E-mail: naor@cs.technion.ac.il, IL |
| |
Abstract: | We formulate the notion of a "good approximation" to a probability distribution over a finite abelian group ?. The quality
of the approximating distribution is characterized by a parameter ɛ which is a bound on the difference between corresponding
Fourier coefficients of the two distributions. It is also required that the sample space of the approximating distribution
be of size polynomial in and 1/ɛ. Such approximations are useful in reducing or eliminating the use of randomness in certain randomized algorithms.
We demonstrate the existence of such good approximations to arbitrary distributions. In the case of n random variables distributed uniformly and independently over the range , we provide an efficient construction of a good approximation. The approximation constructed has the property that any linear
combination of the random variables (modulo d) has essentially the same behavior under the approximating distribution as it does under the uniform distribution over . Our analysis is based on Weil's character sum estimates. We apply this result to the construction of a non-binary linear
code where the alphabet symbols appear almost uniformly in each non-zero code-word.
Received: September 22, 1990/Revised: First revision November 11, 1990; last revision November 10, 1997 |
| |
Keywords: | AMS Subject Classification (1991) Classes: 60C05 60E15 68Q22 68Q25 68R10 94C12 |
本文献已被 SpringerLink 等数据库收录! |
|