LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
Bounded Differences Inequality (Azuma-Hoeffding Inequality)
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

Bounded Differences Inequality (Azuma-Hoeffding Inequality)

20 MIN · EN · STATUS: [ STREAMING ]
RATE THIS
MIT · Probabilistic Methods in Combinatorics · LECTURE 9

Yufei Zhao presents the bounded differences inequality, also known as the Azuma-Hoeffding inequality, in this lecture from MIT's 18.226 Probabilistic Methods in Combinatorics. The core result: a Lipschitz function of independent random inputs concentrates sharply around its mean, even when the function depends on many variables in complicated ways. Zhao develops the martingale-based proof technique behind the bound and then applies it to two classic problems, the coupon collector problem and the chromatic number of a random graph, showing how the same concentration argument yields precise tail estimates in both settings. The lecture assumes familiarity with basic probability and earlier course material on martingales. It is lecture nine of the course, continuing the term's focus on probabilistic tools for combinatorial problems, delivered chalkboard style with worked derivations rather than slides.

At a glance

Lecture facts

Runtime compared with the other 734 Mathematics lectures
Runtime20 m
Compared with MathematicsShorter than 97%
This series

Probabilistic Methods in Combinatorics

Every lecture in order, sized by its length.

  • Earlier lectures
  • This lecture
  • Still to come
Lecture 7 of 91 h 59 m before this · 3 h 13 m in total

More from this course

8 LECTURES
Lower Bounds to Ramsey Numbers

Lower Bounds to Ramsey Numbers

MIT · 43 MIN
Extremal Set Theory: Sperner's Theorem

Extremal Set Theory: Sperner's Theorem

MIT · 13 MIN
Extremal Set Theory: Intersecting Families

Extremal Set Theory: Intersecting Families

MIT · 17 MIN
Linearity of Expectations

Linearity of Expectations

MIT · 13 MIN
Independent Sets and Turán's Theorem

Independent Sets and Turán's Theorem

MIT · 15 MIN
Crossing Number Inequality

Crossing Number Inequality

MIT · 18 MIN
Threshold for a Random Graph to Contain a Triangle

Threshold for a Random Graph to Contain a Triangle

MIT · 29 MIN
Existence of Graphs with High Girth and High Chromatic Number

Existence of Graphs with High Girth and High Chromatic Number

MIT · 25 MIN