Robust estimation of the mean with bounded relative standard deviation

DOI10.1007/978-3-030-43465-6_13MaRDI QIDQ6323681arXivFDO

Authors Mark Huber

Publication date 14 August 2019

Published in arXiv

Full work available at URL https://doi.org/10.1007/978-3-030-43465-6_13

Mathematics Subject Classification ID

Monte Carlo methods (65C05)

arXiv classification

math.PRstat.CO

Abstract: Many randomized approximation algorithms operate by giving a procedure for simulating a random variable $X$ which has mean $mu$ equal to the target answer, and a relative standard deviation bounded above by a known constant $c$. Examples of this type of algorithm includes methods for approximating the number of satisfying assignments to 2-SAT or DNF, the volume of a convex body, and the partition function of a Gibbs distribution. Because the answer is usually exponentially large in the problem input size, it is typical to require an estimate $hatmu$ satisfy $mathbbP(|hatmu/mu-1|>epsilon)leqdelta$, where $epsilon$ and $delta$ are user specified nonnegative parameters. The current best algorithm uses $lceil2c^{2}epsilo{n}^{-2}(1+epsilon{)}^{2}ln(2/delta)ceil$ samples to achieve such an estimate. By modifying the algorithm in order to balance the tails, it is possible to improve this result to $lceil2(c^{2}epsilo{n}^{-2}+1)/(1-epsilo{n}^2)ln(2/delta)ceil$ samples. Aside from the theoretical improvement, we also consider how to best implement this algorithm in practice. Numerical experiments show the behavior of the estimator on distributions where the relative standard deviation is unknown or infinite.

This page was built for publication: Robust estimation of the mean with bounded relative standard deviation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6323681)