  In classical statistics and distribution testing, it is often assumed that
elements can be sampled from some distribution $P$, and that when an element
$x$ is sampled, the probability $P$ of sampling $x$ is also known. Recent work
in distribution testing has shown that many algorithms are robust in the sense
that they still produce correct output if the elements are drawn from any
distribution $Q$ that is sufficiently close to $P$. This phenomenon raises
interesting questions: under what conditions is a "noisy" distribution $Q$
sufficient, and what is the algorithmic cost of coping with this noise?
  We investigate these questions for the problem of estimating the sum of a
multiset of $N$ real values $x_1, \ldots, x_N$. This problem is well-studied in
the statistical literature in the case $P = Q$, where the Hansen-Hurwitz
estimator is frequently used. We assume that for some known distribution $P$,
values are sampled from a distribution $Q$ that is pointwise close to $P$. For
every positive integer $k$ we define an estimator $\zeta_k$ for $\mu = \sum_i
x_i$ whose bias is proportional to $\gamma^k$ (where our $\zeta_1$ reduces to
the classical Hansen-Hurwitz estimator). As a special case, we show that if $Q$
is pointwise $\gamma$-close to uniform and all $x_i \in \{0, 1\}$, for any
$\epsilon > 0$, we can estimate $\mu$ to within additive error $\epsilon N$
using $m = \Theta({N^{1-\frac{1}{k}} / \epsilon^{2/k}})$ samples, where $k =
\left\lceil (\log \epsilon)/(\log \gamma)\right\rceil$. We show that this
sample complexity is essentially optimal. Our bounds show that the sample
complexity need not vary uniformly with the desired error parameter $\epsilon$:
for some values of $\epsilon$, perturbations in its value have no asymptotic
effect on the sample complexity, while for other values, any decrease in its
value results in an asymptotically larger sample complexity.
