# Chebyshev's Inequality and Sampling

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?

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