# Convergence Rate of Sample Average Estimator

Let $$X_1, X_2,\cdots$$ be i.i.d. random variables with $$E(X_1) = \mu, Var(X_1) = σ^2> 0$$ and let $$\bar{X}_n = {X_1 + X_2 + \cdots + X_n \over n}$$ be the sample average estimator.

Is there a way to calculate how many samples are needed to obtain a solution that is "$$\epsilon$$ accurate"? From Chebyshev's inequality I can get

\begin{align} P(|\bar{X}_n - \mu| \geq \epsilon) \leq \frac{Var(\overline{X}_n)}{\epsilon^2} = \frac{σ^2}{n\epsilon^2} \end{align} and can conclude that the convergence rate is linear in $$n$$.

Are there better bounds for the sample average estimator?

You may have a look at the large deviations theory.

In this case, when the distribution is regular enough, the Cramer theorem states:

$$\frac 1n\log P\left(\frac 1n [X_1 + \dots + X_n] > \mu + \epsilon\right) \to -\left[\sup_{t\in \Bbb R} (\mu + \epsilon)t - \log Ee^{tX} \right]$$

The condition being in that case that $Ee^{tX}$ exists. So the good rate of convergence is $$P\left(\left|\frac 1n [X_1 + \dots + X_n] - \mu\right| \ge \epsilon\right) \simeq e^{-\alpha n}$$with $\alpha$ given by the right hand side of the preceding equality.

• Thanks! Does this hold for all $n$ or just for $n\to\infty$? Oct 28, 2014 at 15:28
• only when $n\to \infty$. Oct 28, 2014 at 16:27
• @mookid do you know math.stackexchange.com/questions/2087429/…? Jan 8, 2017 at 23:26

With a finite variance, you have the Central Limit Theorem which broadly speaking tells you that for large $n$ the mean is approximately normally distributed with mean $\mu$ and variance $\frac{\sigma^2}{n}$. So for large $n$ $$P(|\bar{X}_n - \mu| \geq \epsilon) \approx 2\Phi\left(-\frac{\epsilon \sqrt{n}}{\sigma}\right)$$

As an illustration, with $\sigma^2=1$ and $\epsilon=0.01$, the probability suggested by the Central Limit Theorem and your Chebyshev bound for various values of $n$ are about

       n   CLT      Chebyshev bound
10  0.975     1000
100  0.920      100
1000  0.752       10
10000  0.317        1
100000  0.0016       0.1
1000000  1.5e-23      0.01
10000000  1.8e-219     0.001


with the Chebyshev bound being extremely loose for large $n$ and giving an upper bound as a probability greater than $1$ for smaller $n$.

• Thanks. I would like to mark both answers as correct. @mookid answers seems to fit better to my special problem. Oct 29, 2014 at 6:28
• Sorry but the asymptotics stated after "So for large n" is quite wrong. Recall that CLT yields the limit of the probability of deviations of $\bar X_n$ from its expectation $\mu$ of order $1/\sqrt{n}$ but that it says nothing about the probability of so-called "large" deviations of $\bar X_n$ from its expectation $\mu$, that is, deviations of order $1$.
– Did
Oct 29, 2014 at 17:50
• @ManuelSchmidt as the name indicates, the CLT takes care of the most probable values of the sum ("the central region") whereas the large deviation theory takes care of the extreme events. Oct 29, 2014 at 20:48