Approximating probability distributions using small sample spaces
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.
- (De)randomized construction of small sample spaces in \(\mathcal{NC}\)
- Explicit small sets with \(\varepsilon\)-discrepancy on Bohr sets
- Derandomized constructions of \(k\)-wise (almost) independent permutations
- Locating and detecting arrays for interaction faults
- Robust characterizations of k-wise independence over product spaces and related testing results
- Expanding Generating Sets for Solvable Permutation Groups
- Entropy of weight distributions of small-bias spaces and pseudobinomiality
- Sampling to maintain approximate probability distribution under chi-square test
- Constructing Small Sample Spaces Satisfying Given Constraints
- scientific article; zbMATH DE number 7250145 (Why is no real title available?)
- Counting solutions to polynomial systems via reductions
- Binary Covering Arrays and Existentially Closed Graphs
- Optimal -biased sets with just a little randomness
- Entropy of weight distributions of small-bias spaces and pseudobinomiality
- Sampling Boolean functions over Abelian groups and applications
- Improved parallel derandomization via finite automata with applications
- Covering arrays from cyclotomy
This page was built for publication: Approximating probability distributions using small sample spaces
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1288906)
