
Linearity of Expectations
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.