Suppose $\{X_i\}_{i=1}^n$ is a sequence of independently distributed random variables that take values in $[0,1]$.
Let $\bar{X}_n = \frac{1}{n}\sum_{i=1}^n X_i$ denote the average of the sequence.
I'd like to find an upper bound for $\text{Var}(\bar{X})$.
My strategy was to use Hoeffding's inequality, which states that
$$
\Pr(|\bar X_n – E\bar X_n| \geq t) \leq e^{-2nt^2}
$$
We therefore have
\begin{align}
E\left(|\bar X_n – E\bar X_n|^2\right) &= \int_{x \in [0,1]:\, \left(x – E\bar X_n\right)^2 \geq t}|\bar X_n – E\bar X_n|^2dP + \int_{x \in [0,1]:\, \left(x – E\bar X_n\right)^2 < t}|\bar X_n – E\bar X_n|^2dP \\
&\leq e^{-2nt^2} + t(1-e^{-2nt^2})
\end{align}
for all $t$.
Minimizing the right-hand side with respect to $t$ gives a bound for any $n$.
Is it possible to provide a tighter bound than this?
Thanks!
Best Answer
Try Bernstein's inequality? http://www.cs.cornell.edu/~sridharan/concentration.pdf
That or the Efron Stein inequality (which is the tightest bound I know), although it can be difficult to understand how to implement correctly (imo).