LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
Linearity of Expectations
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

Linearity of Expectations

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

Yufei Zhao teaches two combinatorial applications of linearity of expectation in this segment from MIT's 18.226 Probabilistic Methods in Combinatorics. He first computes the expected number of fixed points of a random permutation, showing how splitting an indicator variable for each element simplifies what looks like a hard counting problem into a sum of simple expectations. He then turns to tournaments, directed graphs where every pair of vertices has exactly one directed edge, and uses the same technique to argue that a random tournament is expected to contain many Hamilton paths, paths that visit every vertex exactly once. The lecture is brief but dense, moving quickly between the two examples on the board to show how one probabilistic tool handles very different combinatorial questions. Part of MIT OpenCourseWare's graduate course on probabilistic methods.

At a glance

Lecture facts

Runtime compared with the other 734 Mathematics lectures
Runtime13 m
Compared with MathematicsShorter than 99%
This series

Probabilistic Methods in Combinatorics

Every lecture in order, sized by its length.

  • Earlier lectures
  • This lecture
  • Still to come
Lecture 4 of 91 h 13 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
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
Bounded Differences Inequality (Azuma-Hoeffding Inequality)

Bounded Differences Inequality (Azuma-Hoeffding Inequality)

MIT · 20 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