An optimal (ϵ, δ)‐randomized approximation scheme for the mean of random variables with bounded relative variance. Issue 2 (15th January 2019)

• Record Type: Journal Article
• Authors: Huber, Mark
• Is Part Of: Random structures & algorithms. Volume 55:Issue 2(2019)
• Page Start: 356
• Page End: 370
• Publication Date: 2019-01-15
• Subjects: exponential convergence -- Monte Carlo -- robust; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20839
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : 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 ) ) ϵ − 2 c 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.