I am interested in writing a non-asymptotic rate of convergence for SLLN as a function of number of samples.

From the literature I've read so far, CLT provides an asymptotic convergence rate of $(1/\sqrt N)$ for SLLN.

Also, Berry-Esseen provides a non-asymptotic bound in terms of c.d.f's.

$$|F_N(x) - \Phi(x)| \le \frac{C\mathbb{E}(|X|^3)}{\sigma^3\sqrt N}$$

Is there a Berry-Esseen like statement to bound the difference between sample mean and the expected value of the underlying distribution as a function of N (number of samples)?


First, in the Berry-Esseen theorem, $F_N$ is not just any distributon, but a properly normalized convolutions of N identical distributions.

What you are looking for is the distribution of the sample mean around the true mean as a function of N. You have two very good options already. In fact, the berry esseen appears to be extremely close to what you want, since you can adjust the normal approximation conservatively using the berry-esseen bounds.

A more sophisticated and accurate correction to the CLT comes from using Edgeworth Series, which may be of interest to you.

  • $\begingroup$ would you be able to elaborate on "adjusting the normal approximation conservatively" using the bound? $\endgroup$ – David Alisha Nov 11 '13 at 4:59
  • 1
    $\begingroup$ @user90275: To use Berry-Esseen you correct the mean to be 0, then need to calculate the third absolute moment and the variance of X so you can get the upper bound on the maximum deviation between the two CDFs for a given N (i.e, $\Delta_N$). Now, for given N, you know that the maximum absolute deviation in the normalized distribution and the normal is less than the Berry-Esseen bound i.e, $\\max\{\Phi(x)-\Delta_N,0\}<P(\frac{\bar X_N-E[X]}{\sigma\sqrt{N}}\leq x)<min\{\Phi(x)+\Delta_N,1\}$ $\endgroup$ – user31668 Nov 11 '13 at 15:13
  • $\begingroup$ (cont'd) Therefore, highly skewed distributions (i.e, higher third moment relative to their cubed standard deviation) will reduce the accuracy of the CLT for small N. Also, if you know that the $X_i$ are bounded, then you can truncate the normal $\Phi(x)$ at $(NX_{min},NX_{max})$ which probably won't do much, but at least you dont have bounds out to infinity for the maximum\minimum values. $\endgroup$ – user31668 Nov 11 '13 at 15:14

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.