<p>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 <a href="http://www.iliasdiakonikolas.org/papers/bifdeg2.pdf">Diakonikolas, Kane, Nelson</a> 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.</p>

CC BY-SA 3.0
2015-07-15T23:54:23.443Z
2015-07-15T23:54:23.443Z
Sasho Nikolov
<p>I came across a <a href="http://www.cs.cmu.edu/~odonnell/slides/invariance.pps">presentation</a> 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'':</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>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.</p>

<p>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?</p>

<reference-request><pr.probability><limited-independence><k-wise-independence>
A bounded-independence variant of the Berry-Esseen theorem
Dean
# A bounded-independence variant of the Berry-Esseen theorem

(Asked by: username_0 on 2015-07-15)

I came across a [presentation](http://www.cs.cmu.edu/~odonnell/slides/invariance.pps) 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?

**Tags:** reference-request, pr.probability, limited-independence, k-wise-independence


---

## 1 answers

### Answer by username_1 on 2015-07-15. Score: 8 | Accepted answer

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](http://www.iliasdiakonikolas.org/papers/bifdeg2.pdf) 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.


---

