Approximating probability distributions using small sample spaces
type: Item
instance of: scholarly article
title: Approximating probability distributions using small sample spaces
zbMATH Open document ID: 0917.60014
DOI: 10.1007/PL00009813
author: Yossi Azar
author: Joseph (Seffi) Naor
author: Rajeev Motwani
published in: Combinatorica
publication date: 1999-05-18T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 60C05
Mathematics Subject Classification ID: 20K01
Mathematics Subject Classification ID: 42C99
zbMATH DE Number: 1288337
zbMATH Keywords: biased probability distribution
zbMATH Keywords: Fourier transform of a probability distribution
zbMATH Keywords: good approximation to a probability distribution
zbMATH Keywords: probability distributions on Abelian groups
reviewed by: Gregory Loren McColm
MaRDI profile type: Publication
full work available at URL: pl00009813
OpenAlex ID: W2069690626
description: scientific article; zbMATH DE number 1288337