Central Limit Theorem || @ CMU || Lecture 4a of CS Theory Toolkit

Item: Central Limit Theorem || @ CMU || Lecture 4a of CS Theory Toolkit
Rating: 5
Author: PostSingularity Institute

by Ryan O'Donnell

Formal & Physical Sciences Mathematics PBMathematics PBTProbability and statistics

🎙 Ryan O'Donnell 👥 14K 📅 February 11, 2020 ⏱ 24 min 👁 4K 📄 lecture 🧭 2026-08-17

Available in: English (current) Français

Keywords

Central Limit TheoremiidBernoullivariancestandardizationGaussianRademacherBerry-Esseen

Summary

This lecture, part of the CS Theory Toolkit course at Carnegie Mellon University, introduces the Central Limit Theorem (CLT) and its relevance to theoretical computer science. The instructor, Ryan O’Donnell, begins by setting up a typical scenario: a probabilistic algorithm that succeeds with probability p, run n times independently, and the sum of successes. He reviews key concepts: expectation, variance, and standard deviation, emphasizing the properties of variance (additivity for independent variables, scaling by square of constant). He then introduces the idea of standardizing a random variable to have mean 0 and variance 1. Using the example of n fair coin flips, he derives the mean and variance of the sum, and standardizes it to obtain a sum of Rademacher random variables. He plots the histogram of the standardized sum for increasing n, showing convergence to the bell curve. He states the CLT: for any iid random variables with finite mean and variance, the standardized sum converges in distribution to a standard Gaussian. He notes that the CLT is ‘basically useless’ for TCS because it gives no rate of convergence, and promises to introduce the Berry-Esseen theorem, which provides error bounds. The lecture is rigorous and well-paced, with interactive questions to the audience.

203 words

Critical Evaluation

Value of the Information & Strength of the Argument

The lecture provides a solid foundation in probability theory, with clear explanations and derivations. The instructor emphasizes the practical importance of understanding variance and standardization for analyzing algorithms. He motivates the CLT with a concrete example (coin flips) and illustrates the convergence visually. The argumentation is rigorous, with careful definitions and proofs. The instructor also critically evaluates the CLT, pointing out its limitations for theoretical computer science, which adds depth. The lecture is valuable for students and researchers needing a refresher on these concepts.

Scientific Rigor, Source Quality, Title Accuracy

The lecture is scientifically rigorous, with accurate mathematical statements and derivations. The instructor is a well-known researcher in theoretical computer science. The sources cited in the description include Feller’s classic book and Terry Tao’s blog notes on the CLT, which are reputable. The title accurately reflects the content. The lecture is part of a formal graduate course, ensuring high quality. No comments were provided for analysis.

165 words

Title / Content Match

The title accurately reflects the content: a lecture on the Central Limit Theorem as part of a CS Theory Toolkit course.

Quality & Reliability

9/10

Lecture by a renowned professor at Carnegie Mellon University, part of a graduate course. The content is mathematically rigorous, with clear definitions and derivations. The lecture is well-structured and the instructor demonstrates deep expertise. The video is a formal educational resource, not a popularization, and the mathematical statements are accurate.

Key Moments

Markers derived by PSI from the transcript: the creator did not define chapters.

Cited Sources

Feller's book, 'Introduction to probability theory and its applications' — Referenced as a resource for the lecture.
Terry Tao's blog notes on the Central Limit Theorem — Listed as a resource for the lecture.

Concurring Sources

Terry Tao's blog notes on the Central Limit Theorem — Provides a rigorous treatment of the CLT and related topics, consistent with the lecture.

External References

Contribution & Novelties

This lecture provides a clear and rigorous introduction to the Central Limit Theorem, emphasizing its relevance to theoretical computer science. It bridges the gap between basic probability and advanced topics like Chernoff bounds. The instructor’s critical perspective on the CLT’s limitations is valuable for researchers.

Pour aller plus loin :

Berry-Esseen theorem — Provides quantitative bounds on the error in the CLT, directly addressing the lecture’s critique.
Chernoff bound — A key tool in TCS for tail bounds on sums of independent random variables, mentioned as the next lecture topic.
Rademacher distribution — The distribution of the standardized coin flips, used in the lecture.

104 words

Radar Profile

The radar profile shows high scores in technical level, information quality, and reliability, indicating a rigorous and detailed lecture. The quantity of information is also high, but the lecture is focused and does not cover a broad range of topics, hence a slightly lower score. Overall, it is an excellent educational resource.

Reliability 9/10