# Lecture 3: Inclusion-Exclusion Source: https://www.youtube.com/watch?v=cqPcQ3QqYnE Recap page: https://rapidrecap.app/video/cqPcQ3QqYnE Generated: 2025-12-17T16:36:51.259+00:00 --- ## 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(A_1 ext{ union } A_2)$ is calculated as $P(A_1) + P(A_2) - P(A_1 ext{ intersect } A_2)$, illustrating the core concept of overcounting correction. - The general Inclusion-Exclusion formula for the probability of the union of events $A_1, ext{ldots}, A_n$ 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_{i_1} ext{ intersect } ext{ldots} ext{ intersect } A_{i_r})$, 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. ## Detailed Analysis The lecture centers on the Inclusion-Exclusion Principle, motivated by calculating the probability that none of $n$ students receive their correct homework assignment after random shuffling. The principle is derived intuitively using Venn diagrams for $n=2$ and $n=3$, demonstrating the necessity of successively adding and subtracting probabilities of intersections to correct for overcounting. The general formula is presented: $P(\cup A_i) = \sum P(A_i) - \sum P(A_i \cap A_j) + \sum P(A_i \cap A_j \cap A_k) - \ldots$. The speaker shows that for the pset problem, $P(A_i) = 1/n$, $P(A_i \cap A_j) = \frac{1}{n(n-1)}$, and generally, the probability of $r$ specific events intersecting is $\frac{1}{P(n, r)}$. By multiplying these probabilities by the number of ways to choose $r$ events ($\binom{n}{r}$), the inclusion-exclusion sum simplifies dramatically to the Taylor series expansion for $e^{-1}$, or $1/e$. In sharp contrast, the expected number of students receiving their correct pset back is trivially calculated using linearity of expectation on indicator variables, yielding exactly 1, regardless of the dependencies between events. Finally, the lecture formalizes the definition of independence for two random variables $f$ and $g$ based on the independence of events defined by their values ($\{x: f(x)=\alpha\}$ and $\{x: g(x)=\beta\}$), leading to the powerful result that if $f$ and $g$ are independent, then $E[fg] = E[f]E[g]$. The lecture also briefly covers the Coupon Collector's Problem, solving it using linearity of expectation by decomposing the total time $T$ into a sum of times $T_i$ required to see the $i$-th new distinct birthday, resulting in $n$ times the $n$-th harmonic number, behaving like $n \log n$. ### Inclusion-Exclusion Principle Derivation - $P(A_1 \cup A_2) = P(A_1) + P(A_2) - P(A_1 \cap A_2)$ shown via Venn diagram for $n=2$ - $n=3$ case requires adding back the triple intersection after subtracting pairwise intersections, showing the alternating pattern. ### Pset Problem Solution - The probability that student $i$ gets their correct pset is $P(A_i) = 1/n$ - The probability that $r$ specific students get theirs correct is $\frac{1}{n(n-1)\ldots(n-r+1)}$, occurring $\binom{n}{r}$ times. ### Result of Inclusion-Exclusion for Psets - The probability of no matches is $\sum_{r=0}^{n} (-1)^r \binom{n}{r} \frac{1}{P(n, r)}$, which simplifies to $1 - 1/1! + 1/2! - 1/3! + \ldots + (-1)^n/n!$, converging to $1/e$. ### Linearity of Expectation Contrast - The expected number of correct psets is calculated as $E[\sum \text{Indicator}(A_i)] = \sum E[\text{Indicator}(A_i)] = \sum P(A_i) = n \cdot (1/n) = 1$, highlighting its power over Inclusion-Exclusion for expectations. ### Coupon Collector's Problem - Total time $T$ to collect $n$ coupons is decomposed into $T = \sum T_i$, where $T_i$ is time between $i$-th and $(i+1)$-th distinct coupon - $E[T_i] = 1/P_i$, where $P_i = (n-i)/n$, leading to $E[T] = n \sum_{i=1}^{n} 1/i = n H_n \approx n \log n$. ### Independence of Random Variables - Two random variables $f$ and $g$ are independent if for all $\alpha, \beta$, the events $\{x: f(x) = \alpha\}$ and $\{x: g(x) = \beta\}$ are independent events - This definition recovers event independence when $f$ and $g$ are indicator functions. ### Expectation of Product Lemma - If $f$ and $g$ are independent random variables, then $E[fg] = E[f]E[g]$ - This generalizes the event independence definition, where $E[\text{Indicator}(A) \cdot \text{Indicator}(B)] = P(A \cap B) = P(A)P(B)$ if $A$ and $B$ are independent.