8
$\begingroup$

I came across a presentation by Ryan O'Donnell regarding invariance principles. After proving the Berry-Esseen theorem, there is a slide that discusses extensions of the theorem and one that is mentioned there is a so-called "derandomized version'':

If $X_{1},\ldots,X_{m}$ $C$-nice (that is, has bounded third moment), 3-wise independent., then $X_{1}+\ldots+X_{m}$ is $O(C)$-nice.

I am not sure whether the above is a statement regarding the third moment of the sum of 3-wise independent random variables, or there is indeed some variant of the Berry-Esseen theorem in the case of bounded independence.

Inspecting the proof, I see how 3-wise comes into play, however I could not find any source that discusses bounded-independence variants of this theorem. Are there any?

$\endgroup$
8
$\begingroup$

There are variants of Berry-Esseen for bounded independence, although I have not seen one which is as general as the original theorem. For example Theorem 5.1. in Diakonikolas, Kane, Nelson implies a Berry-Esseen theorem for weighted sums of Bernoulli random variables with bounded independence, as long as none of the weights is too large. If you want error $\varepsilon$ (i.e. Kolmogorov distance from the Gaussian distribution), then $\Theta(1/\varepsilon^2)$-wise independence is necessary and sufficient.

$\endgroup$

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.