Random Structures & Algorithms

An optimal (ϵ,δ)‐randomized approximation scheme for the mean of random variables with bounded relative variance

Early View

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 . We present here an easy to implement (ϵ,δ)‐approximation that uses 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.

Related Topics

Related Publications

Related Content

Site Footer

Address:

This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on StatisticsViews.com are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and StatisticsViews.com express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.