Bounding the variance of a sum of independent random variables

Question

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!

Answer 1

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).

Answer 2

You have the exact expression, $Var[\bar X_n] = (1/n)^2 \sum_{i=1}^n Var[X_i]$.

So each $X_i\in[0,1]$, the bound $Var[X_i]\le 1$ holds (easy), and actually the sharper bound $Var[X_i]\le E[X_i](1-E[X_i])\le 1/4$ holds too.

So the upper bound $Var[X_n]\le 1/(4n)$ holds. If $X_1,...,X_n$ are iid Bernoulli($1/2$) then $Var[X_n] = 1/(4n)$ so the bound is unimprovable.