LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
Large Deviations: Chebyshev and Chernoff Bounds, Wrap Up
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

Large Deviations: Chebyshev and Chernoff Bounds, Wrap Up

83 MIN · EN · STATUS: [ STREAMING ]
RATE THIS
MIT · Mathematics for Computer Science · LECTURE 24

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.

At a glance

Lecture facts

Runtime compared with the other 507 Mathematics lectures
Runtime1 h 23 m
Compared with MathematicsLonger than 90%
This series

Mathematics for Computer Science

Every lecture in order, sized by its length.

  • Earlier lectures
  • This lecture
  • Still to come
Lecture 22 of 2227 h 40 m before this · 29 h 3 m in total

More from this course

12 LECTURES
Predicates, Sets, and Proofs

Predicates, Sets, and Proofs

MIT · 79 MIN
Contradiction and Induction

Contradiction and Induction

MIT · 80 MIN
State Machines

State Machines

MIT · 81 MIN
Lecture 5: Sums

Lecture 5: Sums

MIT · 82 MIN
Lecture 6: Asymptotics

Lecture 6: Asymptotics

MIT · 78 MIN
Divisibility

Divisibility

MIT · 79 MIN
Modular Arithmetic

Modular Arithmetic

MIT · 80 MIN
Lecture 10: Cryptography

Lecture 10: Cryptography

MIT · 81 MIN
Graphs and Coloring

Graphs and Coloring

MIT · 81 MIN
Lecture 12: Matching

Lecture 12: Matching

MIT · 82 MIN
Lecture 13: Connectivity and Trees

Lecture 13: Connectivity and Trees

MIT · 82 MIN
Digraphs and DAGs

Digraphs and DAGs

MIT · 79 MIN