20
$\begingroup$

One naive method for approximating a normal distribution is to add together perhaps $100$ IID random variables uniformly distributed on $[0,1]$, then recenter and rescale, relying on the Central Limit Theorem. (Side note: There are more accurate methods such as the Box–Muller transform.) The sum of IID $U(0,1)$ random variables is known as the uniform sum distribution or Irwin–Hall distribution.

How large is the error in approximating a uniform sum distribution by a normal distribution?

Whenever this type of question comes up for approximating the sum of IID random variables, people (including me) bring up the Berry–Esseen Theorem, which is an effective version of the Central Limit Theorem given that the third moment exists:

$$|F_n(x) - \Phi(x)| \le \frac{C \rho}{\sigma^3 \sqrt n} $$

where $F_n$ is the cumulative distribution function for the rescaled sum of $n$ IID random variables, $\rho$ is the absolute third central moment $E|(X-EX)^3|$, $\sigma$ is the standard deviation, and $C$ is an absolute constant which can be taken to be $1$ or even $1/2$.

This is unsatisfactory. It seems to me that the Berry–Esseen estimate is closest to sharp on binomial distributions which are discrete, with the largest error at $0$ for a symmetric binomial distribution. The largest error comes at the largest jump. However, the uniform sum distribution has no jumps.

Numerical tests suggest that the error shrinks more rapidly than $c/\sqrt n$.

Using $C=1/2$, the Berry–Esseen estimate is $$|F_n(x) - \Phi(x)| \le \frac{\frac12 \frac{1}{32}}{\frac{1}{\sqrt{12}^3} \sqrt n} \approx \frac{0.650}{\sqrt n}$$

which for $n=10,20,40$ is about $0.205$, $0.145$, and $0.103$, respectively. The actual maximum differences for $n=10, 20, 40$ appear to be about $0.00281$, $0.00139$, and $0.000692$, respectively, which are much smaller and appear to fall as $c/n$ instead of $c/\sqrt n$.

$\endgroup$
  • 7
    $\begingroup$ If you expand the distribution of the sum in an Edgeworth expansion, you find that $F_n(x)=\Phi(x)+n^{-1}g(x)+o(n^{-1})$ uniformly in $x$ as $n\rightarrow\infty$ (since the uniform distribution is symmetric), so $c/n$ sounds about right. Because of the $o(n^{-1})$ term, that doesn't give you a bound though... $\endgroup$ – MånsT Jun 14 '12 at 17:39
  • 1
    $\begingroup$ Thanks, that looks like it explains the $c/n$ pattern for many other distributions, too. $\endgroup$ – Douglas Zare Jun 15 '12 at 3:08
17
$\begingroup$

Let $U_1, U_2,\dots$ be iid $\mathcal U(-b,b)$ random variables and consider the normalized sum $$ S_n = \frac{\sqrt{3} \sum_{i=1}^n U_i}{b \sqrt{n}} \>, $$ and the associated $\sup$ norm $$ \delta_n = \sup_{x\in\mathbb R} |F_n(x) - \Phi(x)| \>, $$ where $F_n$ is the distribution of $S_n$.

Lemma 1 (Uspensky): The following bound on $\delta_n$ holds. $$ \delta_n < \frac{1}{7.5 \pi n} + \frac{1}{\pi}\left(\frac{2}{\pi}\right)^n + \frac{12}{\pi^3 n} \exp(-\pi^2 n / 24) \>. $$

Proof. See J. V. Uspensky (1937), Introduction to mathematical probability, New York: McGraw-Hill, p. 305.

This was later improved by R. Sherman to the following.

Lemma 2 (Sherman): The following improvement on the Uspensky bound holds. $$\delta_n < \frac{1}{7.5 \pi n} - \left(\frac{\pi}{180}+\frac{1}{7.5\pi n}\right) e^{-\pi^2 n / 24} + \frac{1}{(n+1)\pi}\left(\frac{2}{\pi}\right)^n + \frac{12}{\pi^3 n} e^{-\pi^2 n / 24} \>.$$

Proof: See R. Sherman, Error of the normal approximation to the sum of N random variables, Biometrika, vol. 58, no. 2, 396–398.

The proof is a pretty straightforward application of the triangle inequality and classical bounds on the tail of the normal distribution and on $(\sin x) / x$ applied to the characteristic functions of each of the two distributions.

$\endgroup$
  • 2
    $\begingroup$ +1 Is $N=n$ in Lemma 2? $\endgroup$ – user10525 Jun 14 '12 at 18:24
  • $\begingroup$ @Procrastinator: Good catch. $\endgroup$ – cardinal Jun 14 '12 at 18:25
  • 1
    $\begingroup$ Thanks! Those references are very helpful. The estimates seem to be within a factor of $2$ of the actual value. $\endgroup$ – Douglas Zare Jun 15 '12 at 2:57

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.