
Large Deviations: Chebyshev and Chernoff Bounds, Wrap Up
Brynmor Chapman closes out MIT's 6.1200J, Mathematics for Computer Science, with the course's final probability topic: bounding how far a random variable can stray from its expectation. He develops the Chebyshev bound from variance before moving to the sharper Chernoff bound, which uses moment generating functions to produce exponentially tight tails, the kind of guarantee needed to analyze randomized algorithms with confidence. The lecture works through the derivations step by step on the board, showing where each bound is useful and where it falls short compared to the others. As the semester's last session, it also ties large deviation results back to earlier material on expectation and concentration, giving students a sense of how the probabilistic toolkit built over the term fits together for analyzing algorithms and data structures.