5
$\begingroup$

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!

$\endgroup$
1
  • $\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, 2016 at 23:12

2 Answers 2

1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .