Suppose that we can obtain independent samples X1, X2, . . . of a random

variable X and that we want to use these samples to estimate E[X]. Using t samples,

we use ti=1 Xi/t for our estimate of E[X]. We want the estimate to be within E[X]

from the true value of E[X] with probability at least 1 - . We may not be able to

use Chernoff's bound directly to bound how good our estimate is if X is not a 0-1

random variable, and we do not know its moment generating function. We develop

an alternative approach that requires only having a bound on the variance of X. Let

r = Var[X]/E[X].

(a) Show using Chebyshev's inequality that O(r2/2) samples are suficient to solve

the problem.

(b) Suppose that we need only a weak estimate that is within E[X] of E[X] with

probability at least 3/4. Argue that O(r2/2) samples are enough for this weak

estimate.

(c) Show that, by taking the median of O(log(1/)) weak estimates, we can obtain an

estimate within E[X] of E[X] with probability at least 1 - . Conclude that we

need only O((r2 log(1/))/2) samples.