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?
Best Answer
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.