# Bounding the variance of a sum of independent random variables

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!

• Not sure I am following... First, the variance is known, since $$\text{Var}\left(\bar{X_n}\right)=\frac1{n^2}\sum_{k=1}^n\text{Var}(X_k).$$ Second, the optimization of the upper bound in your post does not yield an upper bound going to zero, yes?
– Did
Apr 2, 2016 at 23:12

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.