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?


  • $\begingroup$ 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? $\endgroup$ – Did Apr 2 '16 at 23:12

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


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.