# Central Limit Theorem Tails

I'm trying to compute some p-values for samples from a distribution of sums of ~1000 random variables. The exact distribution of these random variables isn't known, but I have empirical estimates that I think are pretty accurate.

So far I've been using the central limit theorem to produce a normal approximation for this sum, which does OK since n is relatively large, but not great. Computing the exact distribution of the sum via convolutions is too slow, but I only really care about having high accuracy in the tails; everywhere else a rough approximation is fine.

Are there any methods that will allow me to improve my estimates in the tails (or just one tail) without having to compute the entire convolutions? I'm not sure if this would be a variant on the CLT implementation or something completely different. My gut feeling is that there isn't any way to do this, so I'd be open to any kind of solution at all!

• Where do the empirical estimates come from and in what form are they? (In a brief test Mathematica computed the convolution of 1000 discrete RVs, each specified by ten parameters, in just a few seconds, so I don't understand why computing the exact distribution is so slow.) – whuber Nov 30 '10 at 16:42
• @whuber They're stored as histograms, i.e. lists of frequencies. My problem is that I have to ~20000 of these computations in a reasonable time, so a few seconds is unfortunately not fast enough. – bnaul Nov 30 '10 at 18:40
• Summarize each histogram with a low-order truncation of its cumulant generating function and add those functions to obtain an Edgeworth-type expansion of the sum (en.wikipedia.org/wiki/Edgeworth_series ). The computational effort is proportional to the total number of bars in all those histograms. – whuber Nov 30 '10 at 19:21
• Have you considered calculating the convolution by using (fast) Fourier transform (and its inverse) ? – Andre Holzner Dec 1 '10 at 20:36

$n=1000$ gets you actually extremely close to normal if you do not go to the extreme tails ($n=10$ is often close enough to normal in the central region), but if you need to go there, estimating a PDF might well be impossible.