Read on Twitter
Answers and discussion for yesterday's quiz on CLTs, Gaussians, and a bit of Invariance Principle.Let's start: Q1 on the Central Limit Theorem was a trap
! 1/16 https://twitter.com/ccanonne_/status/1296331541614755840
Technically, the right answer was "Nothing" (21.5% of you), while "morally" the right answer was Sₙ≈N(0,√n) (40.5%).
Why? Because I didn't mention anything about the variance of X₁,...,Xₙ, not even that it was finite! For the CLT to apply...
2/16 https://twitter.com/ccanonne_/status/1296331544718581760
Why? Because I didn't mention anything about the variance of X₁,...,Xₙ, not even that it was finite! For the CLT to apply...
2/16 https://twitter.com/ccanonne_/status/1296331544718581760
... that's necessary—for things to converge or even make sense (as a fun exercise, try coming up with counterexamples! See below for pointers).
When it does hold, however, the "right" normalization for Sₙ will indeed be √n.
https://stats.stackexchange.com/questions/348972/are-there-any-examples-of-where-the-central-limit-theorem-does-not-hold
https://math.stackexchange.com/questions/164456/some-case-when-the-central-limit-theorem-fails
3/16
When it does hold, however, the "right" normalization for Sₙ will indeed be √n.
https://stats.stackexchange.com/questions/348972/are-there-any-examples-of-where-the-central-limit-theorem-does-not-hold
https://math.stackexchange.com/questions/164456/some-case-when-the-central-limit-theorem-fails
3/16
At this point, I should mention that there are various CLTs, going from "basic" (strong assumptions on X₁,...,Xₙ) to "involved" (weaker assumptions, maybe not even fully independent, etc), and generalizations (convergence to something else than Gaussian). It's really...
4/16
4/16
... a whole landscape, and several interesting proof techniques (based on the characteristic function, or the "replacement" (hybrid) method—crypto people may find that one familiar, or Stein's method... With applications all over the place! Including in TCS, including....
5/16
5/16
... complexity theory (works by e.g., O'Donnell ( @BooleanAnalysis), Tan, and Servedio), property testing (lower bounds for monotonicity testing), distribution learning (see e.g., @thegautamkamath's thesis), testing (Valiant and Valiant's results on entropy estimation...)
6/16
6/16
... Ping me if you want a list of references for those at the end of this thread! In any case, CLTs are great. Let's make those asymptotic results quantitative, though, shall we?
Q2: The [r|t]ight answer was indeed a 1/√n rate, as 47.1% answered...
https://twitter.com/ccanonne_/status/1296331547436396546
7/16
Q2: The [r|t]ight answer was indeed a 1/√n rate, as 47.1% answered...
https://twitter.com/ccanonne_/status/1296331547436396546
7/16
... and yes, there WAS a trap. Some mild conditions on the X₁,...,Xₙ are needed (essentially, bound on higher moments). This is Berry—Esseen 
, and there are again several refinements: below is a convenient and clean statement taken from @BooleanAnalysis's book.
8/??
, and there are again several refinements: below is a convenient and clean statement taken from @BooleanAnalysis's book.8/??
tl;dr: it's like the CLT, but better, stronger, and berry-ier!
(also, I still don't know w/ certainty if it's Esseen or Esséen, though it's most likely the former.)
To sum up: well-behaved things become Gaussian "in the limit." Actually, even "before the limit." So...
9/16
(also, I still don't know w/ certainty if it's Esseen or Esséen, though it's most likely the former.)
To sum up: well-behaved things become Gaussian "in the limit." Actually, even "before the limit." So...
9/16
... can I just replace functions of random stuff with functions of Gaussians and rejoice? 
Can I approximate 𝔼[f(X₁,...,Xₙ)]≈𝔼[f(G₁,...,Gₙ)] for all f?
This is what Q3 asked. Sadly, we can't: as 37% answered, it fails for say f(x)=x₈₁₄.
https://twitter.com/ccanonne_/status/1296331560816242688
10/16
Can I approximate 𝔼[f(X₁,...,Xₙ)]≈𝔼[f(G₁,...,Gₙ)] for all f?This is what Q3 asked. Sadly, we can't: as 37% answered, it fails for say f(x)=x₈₁₄.
https://twitter.com/ccanonne_/status/1296331560816242688
10/16
Intuitively, the reason here is that there is no "averaging" in f(X)=X₈₁₄, no CLT behavior: it's just a single r.v., it doesn't "tend to Gaussian" all by itself.
Now if f were not to put too much "influence" on any particular input... it'd be true. We simply need to...
11/??
Now if f were not to put too much "influence" on any particular input... it'd be true. We simply need to...
11/??
... rule out all "dictator-like" functions which puts way too much weight on any single Xₖ. One can of course formalize this, and this leads to the so-called "Invariance Principle" and its variants.
Conceptually great, technically appealing, and so many applications!
12/16
Conceptually great, technically appealing, and so many applications!
12/16
It's Friday, and this is 13/, so time to wrap up: last question, seemingly unrelated.
Q4: what if Z is such that 𝔼[f(Z)]≈𝔼[Zf'(Z)] for all nice functions f? Then, no trap. As 48.3% answered, and for the right def'n of ≈... Z is ≈Gaussian!
https://twitter.com/ccanonne_/status/1296331563043401729
13/16
Q4: what if Z is such that 𝔼[f(Z)]≈𝔼[Zf'(Z)] for all nice functions f? Then, no trap. As 48.3% answered, and for the right def'n of ≈... Z is ≈Gaussian!
https://twitter.com/ccanonne_/status/1296331563043401729
13/16
It's very powerful, and I find that really neat. First, one can check that this is indeed true if Z is exactly Gaussian.
Then sweat to show the ≈ statement.
Then... use that to prove (strong) versions of the CLT.
Then... generalize in various ways!
14/16
Then sweat to show the ≈ statement.
Then... use that to prove (strong) versions of the CLT.
Then... generalize in various ways!
14/16
It's called "Stein's method," after Charles Stein, and it's a very versatile and neat technique. Check it out! (No, really.)
https://en.wikipedia.org/wiki/Stein%27s_method
I would suggest starting with this, by Greg Valiant.
https://theorydish.blog/2017/10/26/a-glimpse-at-steins-method-in-memory-of-charles-stein/
And also this:
http://theory.stanford.edu/~valiant/teaching/CS362/cs362_steins.pdf
15/16
https://en.wikipedia.org/wiki/Stein%27s_method
I would suggest starting with this, by Greg Valiant.
https://theorydish.blog/2017/10/26/a-glimpse-at-steins-method-in-memory-of-charles-stein/
And also this:
http://theory.stanford.edu/~valiant/teaching/CS362/cs362_steins.pdf
15/16
That's all for today! As mentioned in 7/, please comment below if you want pointers to some of the applications I mentioned. ↴
I don't have a comprehensive ref for CLTs+-Esseen+Invariance Principle, but Ryan O'Donnell's book is a great start: http://analysisofbooleanfunctions.net
16/end
I don't have a comprehensive ref for CLTs+
-Esseen+Invariance Principle, but Ryan O'Donnell's book is a great start: http://analysisofbooleanfunctions.net 16/end
