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?
 A: 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.
A: 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$.  
