2017/06/05 by Mark Huber, Huber, Mark
Mathematics · #62K25 #65C05 #68W25 #Computation (stat.CO) #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods #Point processes and geometric inequalities #Statistical Methods and Inference #msc:62K25 #msc:65C05 #msc:68W25 #stat.CO
paper · pdf · doi:10.48550/arxiv.1706.01478
12 pages, 1 figure
openalex publication_date 2017/06/05 · arxiv created 2017/06/29 · arxiv updated 2017/06/30 · openalex created_date 2024/04/11 · openalex updated_date 2026/07/28
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 X1,X2,… 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 \Xi\ needed to form an (ε,δ)-approximation μ that satisfies ℙ(| μ- μ| > εμ) ≤ δ is at least (2-o(1))ε-2 c2ln(1/δ). We present here an easy to implement (ε,δ)-approximation μ that uses (2+o(1))c2ε-2ln(1/δ) 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.