Approximating probability distributions using small sample spaces (Q1288906): Difference between revisions

This paper presents a notion approximating of a probability distribution with another distribution, measuring the approximation by the \(l_1\) norm between the two distributions, or the \(l_{\infty}\) norm of their Fourier transforms. Let \(\mathbb G\) be a finite Abelian group, and \(\mathcal D\) be a probability distribution on \(\mathbb G\). There exists a small subset \(\Omega \subset \mathbb G\) and a probability distribution \(\mathcal F\) on \(\Omega\) such that \(\mathcal F\) approximates \(\mathcal D\) in the following sense. If \(\widehat {\mathcal D}\) is the Fourier transform of \(\mathcal D\) (and similarly \(\widehat {\mathcal F}\) for \(\mathcal F\)), \(\| \widehat {\mathcal F} - \widehat {\mathcal D} \| _{\infty}\) is small. In addition, this paper looks into a notion of `variational distance', and finds that for any distributions \(\mathcal D\) and \(\mathcal F\) on \(\mathbb G\), if \(\| \widehat {\mathcal F} - \widehat {\mathcal D} \| _{\infty}\) is small, so is \(\| \mathcal F - \mathcal D \| _1\). These and similar results are used to investigate the properties of a notion of `bias', which is roughly a measure of the variation of a sum of random variables versus the uniform distribution. This bias is used to get an upper bound on \(\| {\mathcal D} - {\mathcal U} \| _1\), where \(\mathcal U\) is the uniform distribution. The paper concludes by using Weil's character sums for applications to the random sampling algorithm and to linear codes.