  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 $\hat \mu$ satisfy $\mathbb{P}(|\hat \mu/\mu - 1| > \epsilon) \leq
\delta$, where $\epsilon$ and $\delta$ are user specified nonnegative
parameters. The current best algorithm uses $\lceil
2c^2\epsilon^{-2}(1+\epsilon)^2 \ln(2/\delta) \rceil$ samples to achieve such
an estimate. By modifying the algorithm in order to balance the tails, it is
possible to improve this result to $\lceil 2(c^2\epsilon^{-2} +
1)/(1-\epsilon^2)\ln(2/\delta) \rceil$ 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.
