0xDE ([info]11011110) wrote,
@ 2006-03-06 17:29:00
Previous Entry  Add to memories!  Tell a Friend  Next Entry
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.



(3 comments) - (Post a new comment)


[info]geomblog
2006-03-07 02:29 pm UTC (link)
i guess I'm not seeing why this form of the desired theorem is "local" ?

(Reply to this) (Thread)


[info]11011110
2006-03-07 03:17 pm UTC (link)
Because I only case about a constant sized radius of the origin, instead of scaling the whole distribution by 1/sqrt(n) and saying that it has small discrepancy against a Gaussian with respect to a larger family of sets

(Reply to this) (Parent)(Thread)


[info]geomblog
2006-03-07 05:28 pm UTC (link)
i see. that makes sense. reminds of a feige result from stoc where he can show a constant sized tail for an additive error bound with very few assumptions on the random variables.

(Reply to this) (Parent)


(3 comments) - (Post a new comment)

Create an Account
Forgot your login or password?
Login w/ OpenID
English • Español • Deutsch • Русский…