Given a random variable $X$ and $n$ samples $X_1, \dots, X_n$ chosen i.i.d., let $X^* = \sum\limits_{i=1}^{n} X_i / n$. $\operatorname{Var}[X]$ and $E[X]$ are known.

Using Chebyshev's inequality, I need to show that $\Pr[|X^* - E[X] | \geq \epsilon E[X]] \leq \delta$ when $n = O\left(\dfrac{\operatorname{Var}[X]}{E[x]^2 \epsilon^2\delta}\right)$.

I started by multiplying through by $n$:

$\Pr\left[|S - n E[X]| \geq \epsilon n E[X]\right]$, where $S = \sum\limits_{i=1}^{n} X_i$

Then, ignoring big-$O$ for now, this probability is equal to $\Pr\left[|S-E[S]| \geq \dfrac{\operatorname{Var}[X] \epsilon E[X]}{E[X]^2 \epsilon^2\delta}\right]$.

But here is where I get stuck. I don't see how to apply Chebyshev's inequality without $\operatorname{Var}[S]$. Is there a way to get $\operatorname{Var}[S]$? Am I taking the wrong approach here?

  • 1
    $\begingroup$ The variance of a sum of independent random variables is the sum of the variances. $\endgroup$ – Michael Sep 28 '15 at 5:29
  • 1
    $\begingroup$ Expressing @Michael's comment in mathematical form, $$Var(S)=nVar(X)$$ $\endgroup$ – Samrat Mukhopadhyay Sep 28 '15 at 5:31
  • 1
    $\begingroup$ Aha! After some more manipulation, this allowed me to solve the problem. Thanks! $\endgroup$ – Barnabus Sep 28 '15 at 6:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.