Opening Large Deviations
Large Deviations
- Length
- 1 h 23 min
- Level
- Undergraduate
- Recorded
- MIT2012
Chapter 1 of 10: Before the lecture
Proves the Chernoff bound via Markov's theorem, then applies it to pick-4 lottery winners and server loads.
Large deviation bounds measure how likely a random variable is to stray far from its expected value. Leighton starts with Markov's theorem for non-negative variables, tests it on human weights, exam scores and the Chinese appetizer problem, and gives a variant for variables bounded above. Chebyshev's theorem then uses variance to bound deviations in both directions, with IQ scores showing how much tighter it is than Markov. The Chernoff bound gives exponentially small tails for sums of mutually independent variables, and Leighton proves it for indicator variables by exponentiating and applying Markov. Applications include a pick-4 lottery and randomized load balancing across web servers, as practised at Akamai. Students should know expectation, variance and linearity of expectation.
Large deviation bounds measure how likely a random variable is to stray far from its expected value. Leighton starts with Markov's theorem for non-negative variables, tests it on human weights, exam scores and the Chinese appetizer problem, and gives a variant for variables bounded above. Chebyshev's theorem then uses variance to bound deviations in both directions, with IQ scores showing how much tighter it is than Markov. The Chernoff bound gives exponentially small tails for sums of mutually independent variables, and Leighton proves it for indicator variables by exponentiating and applying Markov. Applications include a pick-4 lottery and randomized load balancing across web servers, as practised at Akamai. Students should know expectation, variance and linearity of expectation.
This lecture
Lecture 24 of 25 of Mathematics for Computer Science.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above.
Press a chosen node again to open it.
Your comment is kept while you sign up.Sign in