Lecture 3: Inclusion-Exclusion

Quick Overview

The lecture introduces the Inclusion-Exclusion Principle as the crucial tool to solve the challenging probability problem of determining the probability that none of $n$ students receive their own graded pset back after random redistribution, ultimately showing this probability converges to $1/e$ as $n$ increases.

Key Points: The main motivating problem involves finding the probability that no student receives their correct pset back when $n$ psets are randomly redistributed, which requires the Inclusion-Exclusion Principle. For $n=2$ students, the probability of the union $P(A1 ext{ union } A2)$ is calculated as $P(A1) + P(A2) - P(A1 ext{ intersect } A2)$, illustrating the core concept of overcounting correction. The general Inclusion-Exclusion formula for the probability of the union of events $A1, ext{ldots}, An$ is an alternating sum starting with the sum of individual probabilities, subtracting pairwise intersections, adding triple intersections, and so on. In the pset problem, the probability of $r$ specific students getting their correct pset back, $P(A{i1} ext{ intersect } ext{ldots} ext{ intersect } A{ir})$, simplifies to $\frac{1}{n(n-1)\text{ldots}(n-r+1)}$, and there are $\binom{n}{r}$ such terms. Plugging these values into the Inclusion-Exclusion formula for the pset problem yields the result $1 - 1/2! + 1/3! - 1/4! + \text{ldots}$, which sums to $1/e$. Linearity of expectation provides a much simpler method to find the expected number of students who get their correct pset back, calculating it as the sum of expectations of indicator variables, resulting in an expected value of 1. The lecture concludes by defining independence for random variables $f$ and $g$ as the requirement that $P(f=a \text{ intersect } g=b) = P(f=a)P(g=b)$ for all $\alpha$ and $\beta$, which implies $E[fg] = E[f]E[g]$ when independent.

Context: This lecture focuses on developing tools for finer-grained control over random variables, specifically introducing the Inclusion-Exclusion Principle and contrasting it with the simpler Linearity of Expectation. The primary context is a probability puzzle where $n$ students submit psets which are then randomly redistributed, leading to the calculation of the probability that no student gets their own work back (a derangement problem). The lecture also transitions into defining independence for random variables and exploring the consequences for expectation.