| 0xDE ( @ 2006-03-06 17:29:00 |
| Entry tags: | central limits, exponential algorithms, mathematics, statistics, unsolved |
A local central limit theorem?
More mathematics in which I'm undereducated: local central limit theorems. That is, if we add together a bunch of independent identically distributed random variables, the central limit theorem tells us the distribution of the sum will look Gaussian on a large scale. A local central limit theorem will tell us that the distribution will look Gaussian on a small scale, in small neighborhoods.
The reason I care is because this came up while revising my paper quasiconvex analysis of backtracking algorithms — I needed a result of this sort to complete a random walk argument lower bounding the value of certain multivariate recurrences. In the conference version of the paper, I said it followed from standard methods, and the referees rightly called me on it and wanted either a proof or a specific citation. The result I would like to cite goes something like this:
Let F be a distribution over Rd with bounded support and zero mean, and let Xi be a sequence of i.i.d. draws from F. Then there exists a constant K such that, for any n, P[|&Sigma0≤i<nXi| ≤ K] = Ω(n-d/2).
Probably the bounded support assumption should be weakened to some number of bounded moments. What I was actually able to prove (which turned out to be sufficient for my paper) was the case where F is a discrete distribution over d+1 vectors, in which case it follows easily via Stirling's approximation for factorials. It can also be proven in the case where the coordinates of Xi are independent of each other, by applying the Berry-Esséen Theorem to each coordinate. But now I'm wondering about what's known for more general F. It seems to me the sort of thing that is likely too straightforward (if one only knows the right tools) to be an interesting research topic, but too specialized to be in the standard texts; if so, that would explain why I had trouble finding anything like it in the searches I tried.