Premium
An optimal ( ϵ , δ ) ‐randomized approximation scheme for the mean of random variables with bounded relative variance
Author(s) -
Huber Mark
Publication year - 2019
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20839
Subject(s) - mathematics , bounded function , estimator , standard deviation , random variable , regular polygon , partition (number theory) , convex body , variance (accounting) , convex function , combinatorics , statistics , convex optimization , mathematical analysis , geometry , accounting , business
Randomized approximation algorithms for many #P‐complete problems (such as the partition function of a Gibbs distribution, the volume of a convex body, the permanent of a {0,1}‐matrix, and many others) reduce to creating random variables X 1 , X 2 ,… with finite mean μ and standard deviation σ such that μ is the solution for the problem input, and the relative standard deviation | σ / μ | ≤ c for known c . Under these circumstances, it is known that the number of samples from the { X i } needed to form an ( ϵ , δ )‐approximationμ ^ that satisfies P ( | μ ^ − μ | > ϵ μ ) ≤ δ is at least ( 2 − o ( 1 ) ) ϵ − 2c 2 ln ( 1 / [ 2 π δ ] ) . We present here an easy to implement ( ϵ , δ )‐approximationμ ^ that uses ( 2 + o ( 1 ) ) c 2ϵ − 2 ln ( 4 / δ ) samples. This achieves the same optimal running time as other estimators, but without the need for extra conditions such as bounds on third or fourth moments.