Mathematics for Computer Science - MIT 6.1200J

MIT 6.1200J Mathematics for Computer Science, Spring 2024 - YouTube

This course provides a rigorous introduction to the foundational mathematical concepts that underpin modern computer science. The curriculum is structured into four major units: Proofs, Number Theory, Graph Theory, and Probability, equipping students with the essential language and tools for formal reasoning, algorithmic analysis, and modeling complex systems.
The course begins with the fundamentals of mathematical proof. It defines the core components of a proof—propositions, axioms, and logical deductions—and establishes a "cookbook" of standard proof techniques. Students learn to construct direct proofs, proofs by contrapositive, proofs by contradiction, and proofs by cases. A central focus is proof by induction, including the more powerful strong induction, which is motivated and demonstrated through classic problems like the Tromino Tiling puzzle and the analysis of recursive algorithms.
The second unit delves into Number Theory, focusing on properties of integers that are critical for cryptography. Key topics include divisibility, the Greatest Common Divisor (GCD), and Euclid's Algorithm for its efficient computation. These tools are motivated by the Die Hard water pouring puzzle, which is shown to be equivalent to solving linear Diophantine equations. The unit culminates in modular arithmetic, developing the rules for operating with congruences, the concept of multiplicative inverses, and proving foundational theorems like Fermat's Little Theorem and the Chinese Remainder Theorem. These principles are then synthesized to explain the mechanics and security of the RSA public-key cryptosystem.
The third unit introduces Graph Theory, the abstract language for modeling networks and relationships. It covers fundamental concepts for both undirected and directed graphs, including vertex degrees, the Handshake Lemma, walks, paths, and cycles. Connectivity is explored in depth, leading to the concepts of connected components in undirected graphs and strongly connected components (SCCs) in directed graphs. The course examines classic graph problems such as Eulerian tours, bipartite matching, and the stable matching problem, for which the elegant Gale-Shapley algorithm is analyzed. A significant focus is placed on Directed Acyclic Graphs (DAGs), their properties (like the existence of sources and sinks), and their application to scheduling problems via topological sorting.
The final unit covers Discrete Probability, providing the framework for reasoning about uncertainty. The course builds from first principles, starting with sample spaces, events, and the axioms of probability. The tree method is used as a systematic tool for solving problems involving sequential random processes, such as the Monty Hall problem. Key concepts of conditional probability, independence (pairwise vs. mutual), and Bayes' Rule are developed and applied to analyze common statistical paradoxes like the base rate fallacy and Simpson's Paradox. The concept of a random variable is introduced, leading to the study of expectation and variance. The transformative linearity of expectation is highlighted as a powerful problem-solving tool. The course concludes with an analysis of tail bounds—including Markov's, Chebyshev's, and Chernoff's inequalities—which provide powerful methods for bounding the probability that a random variable deviates significantly from its mean.

L1: Predicates, Sets, and Proofs

1. Introduction and Course Logistics
The lecture, led by instructor Zachary Abel, begins by welcoming students and outlining the structure and logistics of the course.

• Schedule: Lectures are on Tuesdays and Thursdays, with mandatory recitations on Wednesdays and Fridays. Recitation attendance is worth 10% of the final grade and is a crucial time for collaborative problem-solving in small groups.
• Warmups: To prepare for recitations, students must complete short, multiple-choice "warmup" problems on Canvas. These are designed to be low-stress, with infinite retries and instant feedback, ensuring students engage with the lecture material beforehand.
• Problem Sets: Weekly problem sets are a core component, released on Tuesdays and due on Mondays at 11:59 PM.
  • Collaboration Policy ("Solve Together, Write Alone"): Collaboration is strongly encouraged for the problem-solving phase. Students can work in groups to figure out the solutions. However, the final write-up must be done independently, with notes set aside, to develop the crucial skill of proof writing. The instructor emphasizes the "P vs. NP fallacy": reading and understanding a proof is much easier than constructing one from scratch.
  • Late Policy: The course has a generous late policy to reduce stress and encourage engagement with the material. Submissions lose 1% of their value per hour for the first 50 hours, after which they are worth 50% for the rest of the term. This allows students to take extra time when needed without a severe penalty.

2. The Nature of Proofs
The central theme of the lecture is introduced: understanding the nature of mathematical proofs.

• What is a proof? A proof is a method of ascertaining truth.
• Methods of Ascertaining Truth: The instructor contrasts mathematical proof with other societal methods for determining truth, such as:
  • Scientific method (experiments, observation)
  • Sampling and statistics
  • Legal proceedings
  • Investigation
  • Asking questions
  • Authority, religion, and inner conviction
• Definition of a Mathematical Proof: A mathematical proof is a verification of a proposition by a chain of logical deductions from a base set of axioms. This definition introduces three key terms that structure the rest of the lecture: proposition, axiom, and logical deduction.

3. Propositions and Predicates

• Proposition: A statement that is definitively true or false.
  • Examples: "2 + 3 = 5" (true), "Today is Thursday" (false), "For all natural numbers n, n² + n + 41 is prime." (a proposition whose truth value needs to be determined).
• Predicate: A proposition whose truth depends on the value of one or more variables.
  • Example: "p is prime." This is not a proposition until a value is supplied for p.
• Example Analysis (n² + n + 41): The lecture tests the proposition about the primality of n² + n + 41. It is shown to be true for n = 0 through n = 39, giving strong empirical evidence. However, in mathematics, a "for all" statement requires proof for every single case. A single counterexample is sufficient to disprove it. For n = 41, the expression becomes 41 * 43, which is not prime, thus proving the proposition false.
• Goldbach's Conjecture: The lecture introduces this famous unsolved problem ("Every even number greater than 2 is the sum of two primes") as an example of a simple-to-state proposition whose truth is unknown to mathematics.

4. Logical Operators and Truth Tables
The lecture explains how to combine propositions using logical operators, defined by truth tables.

• Operators: NOT, AND, OR.
• The Ambiguity of English: A significant portion of the lecture is dedicated to demonstrating how the mathematical meanings of these words differ from their colloquial use in English.
  • "OR": An example dialogue with a waiter shows how "or" can mean exclusive OR ("chicken or pasta"), NAND ("coffee or tea"), or simply list options ("cream or sugar"), none of which match the inclusive mathematical "OR" (where "A or B" is true if A is true, B is true, or both are true).
  • The Takeaway: In mathematics, operators have precise, context-independent definitions. Students should ask for clarification if the English phrasing of a problem is ambiguous.
• Implication (
  • A => B is read as "A implies B" or "If A, then B."
  • Its truth table is defined: A => B is only false when A is true and B is false.
  • Vacuous Truth: A key and often confusing point is that if the premise A is false, the implication is true, regardless of the truth of B. The example "If it's Wednesday, then we wear pink" illustrates this: the rule is not violated on a Tuesday, no matter what color is worn.
• Converse, Inverse, and Contrapositive: The lecture defines these related implications:
  • Statement: A => B
  • Converse: B => A
  • Inverse: (NOT A) => (NOT B)
  • Contrapositive: (NOT B) => (NOT A)
  • A statement is logically equivalent to its contrapositive, but not to its converse or inverse.

5. Set Theory Basics
The lecture provides a brief introduction to the language of sets.

• Set: An unordered collection of objects where repeats do not matter.
• Notation: Curly braces {} for sets, parentheses () for tuples (ordered lists).
• Key Sets: The natural numbers N (including 0), integers Z, rationals Q, reals R, and complex numbers C.
• The Empty Set ( The set containing zero elements. It is a subset of every set.
• Operations:
  • Element of ( x ∈ A means x is an element of set A.
  • Subset ( A ⊆ B means every element of A is also in B.
  • Union ( Elements in A or B or both.
  • Intersection ( Elements in both A and B.
  • Set Difference ( Elements in A that are not in B.
• Set-Builder Notation: A powerful way to define a set using a predicate: {n ∈ N | n is prime} defines the set of all prime numbers.

6. Axioms and the Foundations of Mathematics
The final key term from the definition of a proof is explained.

• Axiom: A proposition that we assume to be true without proof. They are the foundational starting points from which all other theorems are derived.
• Example (Euclid's Parallel Postulate): For centuries, mathematicians tried to prove Euclid's fifth axiom from his first four. It was eventually shown to be independent. By changing this axiom (e.g., assuming no parallel lines or infinitely many), one can derive different but equally consistent geometries (spherical and hyperbolic).
• Properties of Axiomatic Systems:
  • Consistency: A system is consistent if it's impossible to prove a contradiction (i.e., you cannot prove that "false" is true).
  • Completeness: A system is complete if every true proposition can be proved from the axioms.
• Gödel's Incompleteness Theorems: A landmark result in logic stating that any axiomatic system complex enough to do basic arithmetic cannot be both consistent and complete. This implies that there exist mathematical truths that are unprovable within any given consistent system.
• Axioms for 6.1200: For the purpose of the class, students are allowed to assume as axiomatic any mathematical fact that would be considered standard in a high school curriculum.

L2: Contradiction and Induction

1. Logical Deductions and Inference Rules
The lecture, led by instructor Zachary Abel, completes the definition of a mathematical proof by focusing on the third key component: logical deductions.

• Inference Rule: A rule for combining true propositions to form other true propositions.
• Examples of Inference Rules:
  1. Modus Ponens: If we know P is true and we know P => Q is true, we can conclude that Q is true.
  2. Modus Tollens (Proof by Contrapositive): If we know P => Q and NOT Q, we can conclude NOT P.
  3. Proof by Contradiction: If (NOT P) => False, we can conclude P.
• Verification: These rules are not arbitrary; their validity can be verified using truth tables. For example, the truth table for ((NOT P) => False) => P shows that the entire statement is always true, regardless of the truth value of P, making it a valid rule of inference.
• Practical Advice: Students are not expected to formally name these rules in their proofs. The key is to ensure that each step in a proof is clear, logical, and follows from previous statements or established axioms. The instructor advises against using phrases like "clearly" or "obviously," as they can mask errors and be unhelpful to the reader.

2. Standard Proof Outlines
The lecture presents several common "proof outlines" or templates for structuring proofs based on the form of the theorem being proven. These are scaffolds to guide thinking and ensure all necessary components of a proof are addressed.

• Theorem Form: ∃x ∈ S, such that P(x) (There exists an x in set S that has property P).
• Proof Outline (Proof by Construction):
  1. State the specific example x you are proposing.
  2. Prove that your example x is in the set S.
  3. Prove that your example x satisfies the property P(x).
• Example: To prove "There exists a prime number n ≥ 10," the proof is: "Let n = 17. Then 17 ≥ 10 and 17 is prime. QED."
• Theorem Form: ∀x ∈ S, P(x) (For all x in set S, property P holds).
• Proof Outline:
  1. Start with the line: "Suppose x is a generic element of S." (Or "Let x ∈ S be arbitrary.")
  2. Using only the fact that x is in S (and no other specific properties of x), derive that P(x) must be true.
• Example: To prove "For all real numbers x, x² - 6x ≥ -10," the proof starts by assuming x is an arbitrary real number and then uses algebraic manipulation ((x-3)² ≥ 0) to show the inequality holds.

1. Direct Proof:
   • Outline: Assume P is true, and then use a chain of logical deductions to show that Q must also be true.
   • Example: To prove "If n is a multiple of 10, then n is even," we assume n=10k, show that this means n=2(5k), which is the definition of an even number.
2. Proof by Contrapositive:
   • Logic: Relies on the fact that P => Q is logically equivalent to its contrapositive, (NOT Q) => (NOT P).
   • Outline: Assume NOT Q is true, and use a chain of logical deductions to show that NOT P must also be true.
   • Example: To prove "If n² is even, then n is even," we prove the contrapositive: "If n is odd, then n² is odd." We assume n = 2k+1 and show that n² = 2(2k²+2k)+1, which is the definition of an odd number.
3. Proof by Contradiction:
   • Logic: Relies on the inference rule ((NOT P) => False) => P.
   • Outline: To prove a proposition P, first assume NOT P. Then, derive a contradiction (a statement R that is both true and false, e.g., R AND (NOT R)). Since a contradiction is impossible in a consistent logical system, the initial assumption (NOT P) must be false, meaning P must be true.
   • Example: To prove "√2 is irrational," we assume for contradiction that √2 is rational. This means √2 = a/b in lowest terms. Squaring and rearranging leads to a² = 2b², which implies a is even. Substituting a = 2c leads to b² = 2c², which implies b is also even. If both a and b are even, they share a common factor of 2, which contradicts the assumption that the fraction was in lowest terms. Therefore, the initial assumption must be false.

3. The Principle of Induction
The final and most substantial part of the lecture is a deep dive into proof by induction.

• Motivation: The instructor uses the theorem for the sum of the first n integers (Σ_{k=1 to n} k = n(n+1)/2) to motivate the need for induction.
  • It is observed that the formula holds for n=0, 1, 2, ....
  • It is then shown algebraically that if the formula is true for n, it must also be true for n+1, because both sides of the equation increase by n+1 when moving from one row to the next.
  • This "domino effect" (if P(0) is true, and P(n) => P(n+1) for all n, then P(n) must be true for all n) is the core intuition.
• The Principle of Induction: This intuition is formalized. To prove ∀n ≥ 0, P(n), you must prove two things:
  • Base Case: Prove that P(0) is true.
  • Inductive Step: Prove that ∀n ≥ 0, P(n) => P(n+1). To do this, you assume P(n) is true for a generic n (this is the inductive hypothesis) and use it to prove that P(n+1) is true.
• Example (Tromino Tiling Puzzle): A more complex and visual example is used to solidify the concept.
  • Theorem: A 2ⁿ x 2ⁿ grid with one square removed can always be tiled perfectly with L-shaped trominoes.
  • Predicate "A 2ⁿ x 2ⁿ board with one cell missing can be tiled."
  • Base Case A 2x2 board with one square missing is exactly the shape of one L-tromino, so it is tileable.
  • Inductive Step (
    1. Assume (the inductive hypothesis): any 2ⁿ x 2ⁿ board with one square missing can be tiled.
    2. Goal: Prove Consider a 2ⁿ⁺¹ x 2ⁿ⁺¹ board with one square missing.
    3. The Trick: Divide this large board into four 2ⁿ x 2ⁿ quadrants. The single missing square will be in one of these quadrants.
    4. Place a single L-tromino in the very center of the board, such that it covers one square from each of the other three quadrants.
    5. Now, the problem has been reduced to four separate subproblems. Each of the four 2ⁿ x 2ⁿ quadrants now has exactly one square missing.
    6. By the inductive hypothesis, each of these four quadrants can be perfectly tiled.
    7. Since all four quadrants can be tiled, the entire 2ⁿ⁺¹ x 2ⁿ⁺¹ board can be tiled. This completes the inductive step.
  • Since both the base case and the inductive step are proven, the theorem is true for all n by the principle of induction.

L3: Casework and Strong Induction

1. Review of Proof Techniques
The lecture, led by instructor Eric Demaine, begins by reviewing the "cookbook" of proof techniques established in the previous lecture. This serves as a foundation for the new methods to be introduced. The reviewed techniques include:

• Proving Proof by construction/example.
• Proving Assume an arbitrary x and prove P(x).
• Proving
  • Direct Proof: Assume P, prove Q.
  • Proof by Contrapositive: Assume NOT Q, prove NOT P.
• Proof by Contradiction: Assume NOT P, derive a contradiction.
• Proof by (Simple) Induction: Prove a base case P(0) and an inductive step P(n) => P(n+1).

2. Proof by Cases
The first new technique introduced is proof by cases.

• The Logic: The technique is based on the tautology (C OR NOT C). To prove a proposition P, it is equivalent to proving (C OR NOT C) => P. This, in turn, is equivalent to proving two separate implications: (C => P) AND ((NOT C) => P).
• The Proof Outline (for 2 cases):
  • Choose a proposition C.
  • Case 1: Assume C is true, and use this assumption to prove P.
  • Case 2: Assume C is false (i.e., NOT C is true), and use this assumption to prove P.
  • Conclude that since P is true in all exhaustive cases, P must be true.
• The Challenge: The art of this method lies in choosing a useful proposition C that simplifies the proof in each case.
• Example (Ramsey Theory): A more complex example is used to demonstrate the power of nested cases.
  • Theorem: In any group of six people, where every pair are either mutual friends or mutual strangers, there must exist a subgroup of three mutual friends or three mutual strangers.
  • Proof Sketch:
    1. Pick an arbitrary person, P.
    2. Case 1: Let them be Q, R, and S.
       • Case 1a: If any pair among Q, R, S are friends (e.g., Q and R), then P, Q, R form a group of 3 mutual friends.
       • Case 1b: If no pair among Q, R, S are friends, then Q, R, S must all be mutual strangers.
    3. Case 2: Since P is connected to 5 other people, this implies P must have at least 3 strangers. This case then becomes symmetric to Case 1, just swapping the roles of "friend" and "stranger."
  • Since a group of three mutual friends or three mutual strangers is found in all exhaustive cases, the theorem is proven.
• Generalization (k cases): The method can be generalized to k cases by finding a set of propositions C₁, ..., Cₖ such that C₁ OR C₂ OR ... OR Cₖ is a tautology (i.e., they are exhaustive). The proof then requires showing P is true in each of the k cases. The famous Four Color Theorem is mentioned as an example of a proof by cases that required a computer to check thousands of cases.

3. Strong Induction
The second major technique introduced is strong induction, a more powerful (but logically equivalent) version of the induction principle.

• Simple Induction Recap: To prove P(n), the inductive hypothesis allows you to assume only P(n-1).
• Strong Induction Principle: To prove P(n), the inductive hypothesis allows you to assume P(k) is true for all k < n.
  • This is "stronger" because it provides more assumptions to work with.
• Formal Statement: If (∀k < n, P(k)) => P(n) holds for all n ≥ 0, then ∀n ≥ 0, P(n) is true.
• Base Cases: The base case(s) are implicitly handled. When n=0, the premise ∀k < 0, P(k) is vacuously true (there are no natural numbers less than 0), so the implication reduces to True => P(0), which means you must prove P(0) from scratch.
• Proof of Equivalence: The lecture provides a proof that strong induction is a valid inference rule by using simple induction to prove it. The trick is to define a new predicate, IH(n) = "P(k) is true for all k < n", and then use simple induction to prove that IH(n) holds for all n.

4. Examples of Strong Induction
Two detailed examples are used to demonstrate the utility of strong induction, particularly in "divide and conquer" style arguments.

• Game: Start with a stack of n items. A move consists of splitting any stack of size S > 1 into two smaller stacks of size a and b (where a+b=S). The score for this move is a * b. The game ends when all stacks have size 1.
• Theorem: The total score is always n(n-1)/2, regardless of the strategy used.
• Proof by Strong Induction:
  • Inductive Hypothesis The theorem is true for a stack of size n.
  • Goal: Prove P(n), assuming P(k) is true for all k < n.
  • Proof: Consider the first move, which splits the n-stack into stacks of size a and b. The score from this move is a * b. The rest of the game consists of two independent sub-games on stacks of size a and b.
  • Since a < n and b < n, we can apply the strong inductive hypothesis. The score from the a-stack game will be a(a-1)/2, and from the b-stack game will be b(b-1)/2.
  • The total score is the sum of these three parts: ab + a(a-1)/2 + b(b-1)/2.
  • A bit of algebra shows this sum simplifies to (a+b)(a+b-1)/2. Since n = a+b, this is n(n-1)/2.
  • This holds for any valid first split (a, b), proving the theorem for n.
• Setup: In a round-robin tournament with n teams, every pair of teams plays once, and there are no ties.
• Theorem: There always exists a "beat ordering" of the teams T₁, T₂, ..., Tₙ such that T₁ beat T₂, T₂ beat T₃, ..., Tₙ₋₁ beat Tₙ.
• Proof by Strong Induction:
  • Inductive Hypothesis A beat ordering exists for any tournament of size n.
  • Goal: Prove P(n), assuming P(k) is true for all k < n.
  • Proof:
    1. Pick an arbitrary team T.
    2. Partition the other n-1 teams into two sets: W (teams that won against T) and L (teams that lost against T).
    3. The size of W and the size of L are both strictly less than n. Therefore, by the strong inductive hypothesis, there exists a beat ordering for the teams in W and a separate beat ordering for the teams in L.
    4. Construct the final ordering by concatenating: (beat ordering of W), then T, then (beat ordering of L).
    5. This is a valid beat ordering for all n teams because: the teams within W are beat-ordered, the teams within L are beat-ordered, the last team in the W ordering beat T (by definition of W), and T beat the first team in the L ordering (by definition of L).

L4: State Machines

1. Introduction: State Machines and Proofs
The lecture, led by instructor Erik Demaine, introduces state machines as a formal tool for modeling and reasoning about processes that evolve over time, such as algorithms. The primary goal is to use this formalism to prove properties of these processes, particularly their correctness and termination, using a technique called invariants, which is a form of induction.

• Definition of a State Machine: A state machine is defined by three components:
  1. A set of states Q, which captures all possible configurations of the system.
  2. A designated start state q₀ ∈ Q.
  3. A set of transitions T, which are rules of the form q → r indicating that the machine can move from state q to state r.
• Execution and Reachability: An execution is a sequence of states q₀, q₁, q₂, ... where each step qᵢ → qᵢ₊₁ is a valid transition. A state r is reachable if there exists an execution that starts at q₀ and ends at r.

2. Case Study: The 8-Puzzle
To motivate the need for formal proofs about state machines, the lecture introduces the 8-puzzle.

• The Puzzle: A 3x3 grid with tiles numbered 1 through 8 and one blank space. A move consists of sliding a tile adjacent to the blank space into the blank space.
• The Goal: To get from a given starting configuration to the solved state (1, 2, 3, 4, 5, 6, 7, 8, blank).
• The Claim: A key claim is made: it is impossible to reach the solved state from a configuration where only two adjacent tiles (e.g., 5 and 6) are swapped. This impossibility is not obvious and requires a proof.
• Formalizing as a State Machine:
  • States All 9! possible arrangements of the 8 tiles and the blank.
  • Start State The initial configuration of the puzzle.
  • Transitions A move from one configuration to another by sliding a tile.

3. State Predicates, Preservation, and Invariants
To prove properties like the impossibility of solving certain 8-puzzle configurations, the concepts of state predicates and invariants are introduced.

• State Predicate A function that maps each state q to either True or False (e.g., "the number of inverted pairs is odd").
• Preserved Predicate: A predicate P is preserved if, for every valid transition q → r, the implication P(q) => P(r) holds. This means that if P is true in state q, it must also be true in any state r that can be reached from q in one step.
• Invariant Predicate: A predicate P is an invariant if P(q) is true for all reachable states.
• The Invariant Principle: This is the key theorem connecting these concepts. It is a powerful generalization of the principle of induction to general state machines.
  • Theorem: If a predicate P is true at the start state and P is preserved by all transitions, then P is an invariant.
  • Proof: This is proven using induction on the length of the execution. The base case (length 0) is P(q₀), which is given. The inductive step shows that if P is true at the end of all length n-1 executions, it must also be true at the end of all length n executions, because the predicate is preserved across the final transition.

4. Proving the 8-Puzzle Impossibility
The invariant principle is now applied to the 8-puzzle.

1. Define a Predicate: The crucial step is to define a clever predicate. Let P(q) be the proposition: "The number of inverted pairs in state q is even."
   • An inverted pair is a pair of tiles (i, j) such that i > j but i appears before j in the reading order of the grid (ignoring the blank).
2. Prove Preservation: The lecture proves that this predicate is preserved.
   • Case 1 (Horizontal move): A horizontal slide does not change the reading order of the tiles, so the number of inverted pairs remains unchanged. The parity (odd/even) is preserved.
   • Case 2 (Vertical move): A vertical slide is shown to be equivalent to swapping a tile with two others in the reading order. Each adjacent swap changes the number of inversions by ±1 (an odd number). Two such swaps change the total number of inversions by an even number. Therefore, an even number of inversions plus an even number is still even; an odd number plus an even number is still odd. The parity of the number of inverted pairs is always preserved.
3. Apply the Invariant Principle:
   • Consider a starting state like 1, 2, 3, 4, 6, 5, 7, 8, which has one inverted pair (6, 5). The predicate P(q₀) is false (the number of inversions is odd).
   • Since the parity of inversions is a preserved property, it must be an invariant for all states reachable from q₀. This means every reachable state must also have an odd number of inverted pairs.
   • The solved state 1, 2, 3, 4, 5, 6, 7, 8 has zero inverted pairs. The predicate P(q_final) is true (the number of inversions is even).
   • Conclusion: Since the start state has an odd number of inversions and the final state has an even number, and the parity can never change, the final state is unreachable from this starting state.

5. Proving Termination: Derived Variables
The lecture shifts from proving correctness (what states are reachable) to proving termination (that the machine must eventually halt).

• Final States: A state is final if it has no outgoing transitions.
• Termination: A state machine terminates if every possible execution is finite (i.e., eventually reaches a final state).
• The Derived Variable Method: This is the primary tool for proving termination.
  • Define a derived variable x(q), which is a function mapping each state q to a natural number ({0, 1, 2, ...}).
  • Prove that this variable is strictly decreasing across every transition (x(q) > x(r) for all transitions q → r).
• The Termination Theorem: If a strictly decreasing derived variable that maps to the natural numbers exists, the state machine must terminate.
  • Proof: The value of the derived variable starts at x(q₀). Since it is a natural number and decreases by at least 1 at every step, the execution can last for at most x(q₀) steps before the variable would have to become negative, which is impossible.
• Example (Simple Sorter):
  • Algorithm: While there exists an adjacent pair (aᵢ, aᵢ₊₁) that is out of order (aᵢ > aᵢ₊₁), swap them.
  • Derived Variable: Let x(q) be the number of inverted pairs in the current permutation q.
  • Proof of Termination: x(q) is always a natural number. Each valid move in the algorithm is a swap of an out-of-order adjacent pair. This single swap resolves exactly one inversion and creates no new ones. Therefore, the number of inverted pairs x(q) strictly decreases by 1 at every step. By the termination theorem, the algorithm must halt.

L5: Sums

1. Introduction to Algorithmic Analysis and Sums
The lecture, led by instructor Brynmor Chapman, shifts focus from proofs to algorithmic analysis, beginning with the fundamental tool of evaluating sums. Understanding how to find closed-form expressions for or approximate the value of summations is a critical skill for analyzing the runtime and behavior of algorithms.
2. Motivating Example: The Value of an Annuity
The lecture starts with a real-world example to motivate the need for evaluating sums.

• The Problem: What is the present-day value of winning a lottery that pays out in installments (e.g., $50,000 per year for 20 years)?
• The Concept: Due to factors like inflation and investment opportunities (interest), money today is worth more than the same amount of money in the future.
• The Annuity Formula: The present value of receiving m dollars k years in the future, given an annual interest rate p, is m / (1+p)ᵏ.
• The Sum: The total present value of the lottery is the sum of the value of each installment:
  V = Σ_{k=0 to n-1} m * (1 / (1+p))ᵏ
• The Goal: Find a closed form for this sum—an expression without sigma notation or ellipses that can be easily calculated.

3. Method 1: The Perturbation Method
This method is used to discover the closed form for a sum if it is not already known.

• The Geometric Series: The annuity sum is an example of a geometric series. By letting x = 1 / (1+p), the sum becomes S = m * Σ_{k=0 to n-1} xᵏ.
• The "Trick":
  1. Write out the sum S = 1 + x + x² + ... + xⁿ⁻¹ (ignoring the m for now).
  2. Multiply the entire series by x to get xS = x + x² + ... + xⁿ.
  3. Subtract the second equation from the first: S - xS.
  4. Most terms cancel out, leaving S(1-x) = 1 - xⁿ.
  5. Solving for S gives the well-known formula for a finite geometric series: S = (1 - xⁿ) / (1-x).
• Application: Plugging the lottery numbers back into this formula reveals that the $1 million prize paid over 20 years is only worth about $638,000 in today's money. An infinite annuity of $1 per year is only worth about $20.

4. Method 2: The Ansatz (Educated Guess) Method
This method is used when you can make a good "educated guess" (ansatz) about the form of the closed-form solution.

• The Problem: Find a closed form for the sum of the first n squares: S = Σ_{k=1 to n} k².
• The Educated Guess:
  1. Analyze the Order of Growth: The sum involves n terms, the largest of which are around n². This suggests the sum should grow roughly as n³.
  2. Posit a Form: Assume the solution is a cubic polynomial with unknown coefficients: S(n) = an³ + bn² + cn + d.
• Solving for Coefficients:
  1. Since we have four unknown coefficients (a, b, c, d), we need four constraints to solve for them.
  2. We can generate these constraints by plugging in small, known values of n:
     • S(0) = 0 => d = 0
     • S(1) = 1 => a + b + c + d = 1
     • S(2) = 5 => 8a + 4b + 2c + d = 5
     • S(3) = 14 => 27a + 9b + 3c + d = 14
  3. Solving this system of linear equations yields the coefficients: a=1/3, b=1/2, c=1/6, d=0.
• Verification: This process only produces a candidate formula. The final, crucial step is to prove that this formula is correct for all n using proof by induction.

5. Method 3: Handling Double Summations
This section deals with nested sums.

• The Strategy:
  1. Evaluate Inside-Out: The most straightforward approach is to find a closed form for the inner sum first, treating the outer index as a constant. Then, substitute this closed form back in and evaluate the resulting outer sum.
  2. Exchange the Order of Summation: Sometimes, it is easier to evaluate the sum by swapping the order of the sigma notations.
     • To do this, one must carefully determine the new bounds of summation. The original bounds 1 ≤ i ≤ n and i ≤ j ≤ n together define a set of pairs (i,j). The goal is to describe this same set of pairs but by specifying the bounds for j first, and then the bounds for i in terms of j.
     • The new bounds become 1 ≤ j ≤ n and 1 ≤ i ≤ j.
     • Exchanging the order can often simplify the inner sum, making the entire expression easier to evaluate.

6. Method 4: The Integral Method for Approximation
This method is used when a nice closed form for a sum does not exist or is not needed. The goal is to find good upper and lower bounds for the sum.

• The Idea: A sum can be viewed as a Riemann sum approximation of an integral.
• The Bound for Increasing Functions:
  • Consider a sum S = Σ_{i=1 to n} f(i) where f is a weakly increasing function.
  • The integral I = ∫_{1 to n} f(x)dx can be bounded by two step functions.
  • The lower bound for the integral is the sum of left-hand-rule rectangles, which is Σ_{i=1 to n-1} f(i) = S - f(n).
  • The upper bound for the integral is the sum of right-hand-rule rectangles, which is Σ_{i=2 to n} f(i) = S - f(1).
  • Rearranging these inequalities gives a bound on the sum S:
    ∫_{1 to n} f(x)dx + f(1) ≤ S ≤ ∫_{1 to n} f(x)dx + f(n)
• The Bound for Decreasing Functions: A similar bound can be derived for weakly decreasing functions by a simple transformation.
• Application (Infinite Sums): This method is particularly useful for bounding infinite sums. By taking the limit as n → ∞, one can often bound the value of a convergent series. For example, Σ_{i=1 to ∞} 1/i² is shown to be between 1 and 2.
• Improving Precision: To get tighter bounds, one can compute the first few terms of the sum exactly and then apply the integral method only to the tail of the series. This reduces the error term, which is proportional to the first term of the approximated sum.

L6: Asymptotics

1. Introduction: From Summations to Asymptotics
The lecture, led by instructor Zachary Abel, begins by wrapping up the topic of summations and transitioning to a core concept in algorithm analysis: asymptotic notation.

• Motivating Example (Block Stacking): The lecture starts with a physical demonstration of stacking blocks to achieve the maximum possible overhang. This problem is shown to be equivalent to calculating the n-th harmonic number, H_n = Σ_{k=1 to n} 1/k.
• Approximating Sums: Since there is no simple closed form for the harmonic series, the integral method is used to approximate it. The sum H_n is bounded between ln(n) + 1/n and ln(n) + 1.
• Asymptotic Equivalence ( This leads to the first piece of asymptotic notation. Two functions f(n) and g(n) are asymptotically equivalent (f(n) ~ g(n)) if their ratio approaches 1 as n approaches infinity. Using the integral bounds and the Squeeze Theorem, it is shown that H_n ~ ln(n).
• Products via Sums: The lecture shows how to analyze products, like n!, by taking their logarithm, which turns the product into a sum (ln(n!) = Σ ln(k)). The integral method is then applied to this sum to derive bounds on n!. This leads to Stirling's Approximation, a famous and useful asymptotic equivalence for the factorial function.

2. The Motivation for Asymptotic Notation
The core of the lecture is about developing a language to compare the efficiency of algorithms in a way that is robust to implementation details and focuses on fundamental scaling behavior.

• Comparing Algorithms (Swap Sort vs. Merge Sort): Two sorting algorithms are compared based on their worst-case operation counts:
  1. Swap Sort: S(n) = n²/2 - n/2 swaps.
  2. Merge Sort: M(n) = n log₂(n) - n + 1 comparisons.
• The Abstraction Process: To compare these for large n, we want to simplify the functions. The instructor demonstrates an informal process of "stripping away" less important details:
  1. Ignore Lower-Order Terms: For large n, n²/2 dominates -n/2, and n log n dominates -n+1. We only care about the fastest-growing term.
  2. Ignore Constant Factors: The 1/2 in n²/2 is also ignored. This is justified because the actual runtime in seconds depends on many constant factors (machine speed, compiler, specific instruction costs) that are not fundamental to the algorithm itself. We care that the runtime is proportional to n², not the exact constant of proportionality.
• The Goal: To formalize this process of ignoring constant factors and lower-order terms to compare the essential "growth rate" of functions.

3. Big O Notation (O)
Big O notation is the primary tool for providing an asymptotic upper bound on a function's growth.

• Intuition: f(n) ∈ O(g(n)) means that f grows no faster than g, up to a constant factor and for sufficiently large n.
• Formal Definition: f(n) ∈ O(g(n)) if and only if there exist constants c > 0 and n₀ ≥ 0 such that for all n ≥ n₀, f(n) ≤ c * g(n).
  • The ∃c captures "ignoring constant factors."
  • The ∀n ≥ n₀ captures "ignoring small values of n."
• Examples:
  • n ∈ O(n²): True, as n ≤ 1 * n² for n ≥ 1.
  • n² ∈ O(n): False. No matter what constant c is chosen, n² will eventually become larger than c*n.
  • n² + 3n + 7 ∈ O(n²): True. The lower-order terms 3n+7 can be absorbed into the constant c (e.g., n² + 3n + 7 ≤ 11n² for large n).
• Limit Test: A useful theorem for checking Big O: If the limit lim_{n→∞} f(n)/g(n) exists:
  • If the limit is < ∞ (finite, including 0), then f(n) ∈ O(g(n)).
  • If the limit is = ∞, then f(n) ∉ O(g(n)).
  • If the limit does not exist, the test is inconclusive.

4. Related Asymptotic Notations: Ω and Θ
To provide a complete language for asymptotic comparison, two related notations are introduced.

• Big Omega (
  • Intuition: f(n) ∈ Ω(g(n)) means f grows at least as fast as g.
  • Definition: f(n) ∈ Ω(g(n)) if and only if g(n) ∈ O(f(n)).
• Big Theta (
  • Intuition: f(n) ∈ Θ(g(n)) means f grows at the same rate as g.
  • Definition: f(n) ∈ Θ(g(n)) if and only if f(n) ∈ O(g(n)) AND f(n) ∈ Ω(g(n)).
• Comparison with Θ is a looser notion than asymptotic equivalence (~).
  • f(n) ~ g(n) implies f(n) ∈ Θ(g(n)).
  • f(n) ∈ Θ(g(n)) does not imply f(n) ~ g(n). For example, 2n² ∈ Θ(n²), but 2n² is not asymptotically equivalent to n² because their ratio limits to 2, not 1. Θ ignores the leading constant factor, while ~ does not.

5. Little o and Little omega Notation
Two final notations are introduced to capture strict asymptotic inequalities.

• Little o (
  • Definition: f(n) ∈ o(g(n)) if lim_{n→∞} f(n)/g(n) = 0.
  • Intuition: f is a lower-order term compared to g. It grows strictly slower.
  • This formalizes the concept of "ignoring lower-order terms" used to motivate the notation in the first place.
• Little omega (
  • Definition: f(n) ∈ ω(g(n)) if lim_{n→∞} f(n)/g(n) = ∞.
  • Intuition: f grows strictly faster than g.

6. Warning: Asymptotics and Induction Don't Mix
The lecture concludes with a critical warning and a "proof" of a false statement to illustrate a common pitfall.

• The False Theorem: 2ⁿ ∈ O(1) (i.e., an exponential function is bounded by a constant).
• The Flawed "Proof" by Induction:
  • Base Case: For n=0, 2⁰ = 1, and 1 ∈ O(1). True.
  • Inductive Step: Assume 2ⁿ ∈ O(1). Then 2ⁿ⁺¹ = 2 * 2ⁿ = 2ⁿ + 2ⁿ. Since 2ⁿ ∈ O(1), this is O(1) + O(1) = O(1). The induction seems to go through.
• The Error: The error lies in a misunderstanding of what the induction is proving. The statement 2ⁿ ∈ O(1) is a statement about the function f(n)=2ⁿ. The inductive proof, however, does not prove anything about the function as a whole. Instead, for each individual n, it proves that the constant 2ⁿ is in O(1), which is trivially true (any constant is bounded by another constant). The proof fails because the constant c required in the Big O definition depends on n and grows with n, violating the requirement that c must be a fixed constant that works for all sufficiently large n.
• The Takeaway: You cannot use induction on n to prove an asymptotic property of a function of n. Asymptotic statements must be reasoned about holistically, for all large n simultaneously.

L7: Recurrences

1. Introduction: Analyzing Recurrences
The lecture, led by instructor Brynmor Chapman, focuses on recurrences, which are sequences defined inductively. This is a core topic in algorithmic analysis, as the runtimes of recursive algorithms are naturally described by recurrence relations. The goal is to develop techniques for finding closed-form or asymptotic solutions to these recurrences.

• Example (Fibonacci): The Fibonacci sequence (F(n) = F(n-1) + F(n-2)) is a classic recurrence. While it's defined recursively, it also has a surprising closed-form solution (Binet's formula), which is much more useful for understanding its exponential growth rate.

2. Case Study: The Towers of Hanoi
This classic puzzle is used to demonstrate how recurrences arise from recursive algorithms.

• The Puzzle: Move a stack of n disks of decreasing size from a source peg to a destination peg using an auxiliary peg, with the rules that only one disk can be moved at a time and a larger disk can never be placed on a smaller one.
• The Recursive Algorithm: The optimal strategy is a recursive, "divide and conquer" algorithm:
  1. Recursively move the top n-1 disks from the source peg to the auxiliary peg.
  2. Move the largest disk (disk n) from the source to the destination peg (1 move).
  3. Recursively move the n-1 disks from the auxiliary peg to the destination peg.
• The Recurrence Relation: Let T(n) be the number of moves required to solve the puzzle with n disks. The algorithm directly translates into a recurrence relation:
  T(n) = T(n-1) + 1 + T(n-1) = 2 * T(n-1) + 1
  With the base case T(1) = 1.
• Solving the Recurrence (Guess and Check):
  1. Guess: By computing the first few terms (1, 3, 7, 15, 31, ...), we can guess that the closed-form solution is T(n) = 2ⁿ - 1.
  2. Check: This guess can be formally proven correct using a straightforward proof by induction.
• Implication: For the mythical n=64 disks, the solution takes 2⁶⁴ - 1 moves, which at one move per second, would take over half a trillion years.

3. Case Study: Sorting Algorithms
The lecture uses sorting algorithms to further motivate the analysis of recurrences and to set up the introduction of the Master Theorem.

• Algorithm: Repeatedly find the smallest element in the unsorted portion of the list and move it to the end of the sorted portion.
• Analysis: To find the first smallest element requires n-1 comparisons. To find the second requires n-2, and so on. The total number of comparisons is the sum Σ_{k=1 to n-1} k = n(n-1)/2. This is a quadratic runtime, Θ(n²).
• Algorithm: A classic divide and conquer algorithm.
  1. Base Case: If the list has one element, it is already sorted.
  2. Divide: Split the n-element list into two halves of size n/2.
  3. Conquer: Recursively call Merge Sort on each of the two halves.
  4. Combine: Merge the two now-sorted halves back into a single sorted list. The merge step is efficient, taking at most n-1 comparisons.
• Analysis via Recurrence: Let M(n) be the number of comparisons for Merge Sort. The algorithm's structure gives the recurrence:
  M(n) = 2 * M(n/2) + (n-1)
• Solving the Recurrence (Plug and Chug):
  1. The Method: Repeatedly substitute the recurrence relation into itself to expand the expression.
  2. Expansion: M(n) = (n-1) + 2 * M(n/2) = (n-1) + 2 * [(n/2 - 1) + 2*M(n/4)] = (n-1) + (n-2) + 4*M(n/4) = ...
  3. Identify the Pattern: After expanding k times, the pattern M(n) = Σ_{i=0 to k-1} (n - 2ⁱ) + 2ᵏ * M(n/2ᵏ) emerges.
  4. Solve: By setting k = log₂(n) (assuming n is a power of 2), the recursion bottoms out at M(1)=0. The resulting sum can be solved to find the closed form: M(n) = n log₂(n) - n + 1.

4. The Master Theorem
The Master Theorem provides a "cookbook" method for finding asymptotic (Θ) solutions to a large class of divide and conquer recurrences without doing the full plug-and-chug derivation.

• The Recurrence Form: It applies to recurrences of the form:
  T(n) = a * T(n/b) + f(n)
  • a: Number of recursive subproblems.
  • n/b: Size of each subproblem.
  • f(n): Cost of the work done at each step (dividing and combining).
• The Intuition (Recursion Tree): The total work is the sum of the work done at each level of the recursion tree. At level i, there are aⁱ subproblems, each of size n/bⁱ, for a total work of aⁱ * f(n/bⁱ). The total runtime is the sum of this work over all log_b(n) levels.
• The Three Cases: The Master Theorem states that the asymptotic runtime is determined by a competition between the rate of subproblem proliferation (n^{log_b(a)}) and the work done at each node (f(n)).
  • Case 1 (Leaf-Dominated): If f(n) grows slower than n^{log_b(a)}, then the work is dominated by the vast number of leaves at the bottom of the tree. The runtime is Θ(n^{log_b(a)}).
  • Case 2 (Balanced): If f(n) grows at the same rate as n^{log_b(a)}, then the work is spread evenly across all levels of the tree. The runtime is Θ(n^{log_b(a)} * log(n)).
  • Case 3 (Root-Dominated): If f(n) grows faster than n^{log_b(a)}, then the work is dominated by the work f(n) done at the very first (root) step. The runtime is Θ(f(n)).
• Applying to Merge Sort:
  • T(n) = 2 * T(n/2) + (n-1)
  • a=2, b=2, f(n) = n-1.
  • We compare f(n) to n^{log_b(a)} = n^{log₂(2)} = n¹ = n.
  • Since f(n) = n-1 is Θ(n), we are in Case 2.
  • Therefore, the Master Theorem tells us the runtime is Θ(n log n), matching the result from the plug-and-chug method.

The Master Theorem is a powerful tool that simplifies the analysis of many divide and conquer algorithms, providing immediate asymptotic bounds without requiring a full derivation.

L8: Divisibility

1. Introduction to Number Theory
The lecture, led by instructor Erik Demaine, introduces the topic of Number Theory, the study of integers. This ancient branch of mathematics has found critical modern applications in computer science, particularly in cryptography and error correction. The lecture focuses on the foundational concepts of divisibility and the Greatest Common Divisor (GCD).
2. Divisibility

• Definition: An integer a divides an integer b (written a | b) if b = k * a for some integer k. This definition, based on multiplication, is more robust than one based on division as it handles the case where a=0.
• Key Properties:
  • Any integer n divides 0 (because 0 = 0 * n).
  • 2 | n is the formal definition of n being an even number. Since 2 | 0, zero is even.
• Integer Linear Combinations (ILCs): An expression of the form sa + tb, where s and t are integers, is an integer linear combination of a and b.
• Divisibility Fact: If d | a and d | b (i.e., d is a common divisor), then d divides any integer linear combination of a and b. This is a crucial property used throughout the lecture.

3. Case Study: The Water Pouring Puzzle
The famous puzzle from the movie Die Hard 3 is used to motivate the need for GCDs.

• The Problem: Given two jugs of integer capacities a and b, can you measure out a specific target volume x? (e.g., given 5-gallon and 3-gallon jugs, measure exactly 4 gallons).
• Modeling as a State Machine: The problem can be modeled as a state machine where a state (x, y) represents the amount of water in each jug. Transitions include filling a jug, emptying a jug, or pouring from one jug to another.
• Key Lemma and Proof by Invariant: A key lemma is proven using the invariant principle: All reachable amounts of water are integer linear combinations of the jug capacities .
  • Predicate "The amount of water in each jug is an ILC of a and b."
  • Base Case: The start state (0, 0) satisfies the predicate, as 0 = 0a + 0b.
  • Preservation: Each possible transition (filling, emptying, pouring) transforms a state where the amounts are ILCs into a new state where the amounts are also ILCs. For example, if x = s₁a + t₁b and y = s₂a + t₂b, then x+y = (s₁+s₂)a + (t₁+t₂)b, which is also an ILC.
• Solving the Puzzle: This lemma provides a way to determine if a puzzle is solvable. For example, with 6-gallon and 4-gallon jugs, all reachable amounts must be integer linear combinations of 6 and 4. Since both 6 and 4 are even, any ILC of them must also be even. Therefore, it is impossible to measure out an odd number like 3 gallons.

4. The Greatest Common Divisor (GCD)
To formalize the solvability condition, the concept of the Greatest Common Divisor is introduced.

• Definition 1 (Largest Divisor): The GCD of a and b is the largest integer that divides both a and b. (With the special case GCD(0, 0) = 0).
• Definition 2 (Greatest in Divisibility): The GCD of a and b is the unique non-negative common divisor that is divisible by all other common divisors.
• Connecting to the Puzzle: The puzzle of measuring x with jugs a and b is solvable if and only if x is an integer linear combination of a and b. It will be shown that this is equivalent to the condition that divides .

5. Euclid's Algorithm for Computing the GCD
The lecture develops an efficient algorithm for computing the GCD.

• The Subtraction-Based Lemma: The core insight is that GCD(a, b) = GCD(a-b, b). This is proven by showing that the set of common divisors of (a, b) is identical to the set of common divisors of (a-b, b).
• A Slow Algorithm: This lemma leads to a slow algorithm where you repeatedly subtract the smaller number from the larger one until one of the numbers becomes 0.
• The Division Theorem: Division is just repeated subtraction. The Division Theorem states that for any integer n and positive integer d, there exists a unique integer quotient q and remainder r such that n = qd + r and 0 ≤ r < d.
• The Division-Based Lemma: By applying the subtraction lemma q times, we get the more powerful result: GCD(a, b) = GCD(b, a rem b).
• Euclid's Algorithm: This lemma forms the basis of Euclid's algorithm, a very fast method for computing the GCD.
  1. Given a and b (with a ≥ b).
  2. If b=0, the GCD is a.
  3. Otherwise, recursively compute GCD(b, a rem b).
• Termination and Runtime: The algorithm terminates because the second argument (a rem b) is always strictly smaller than the previous second argument b. The runtime is logarithmic in the size of the numbers, making it extremely efficient even for very large integers.

6. Bézout's Lemma and the Pulverizer Algorithm
The lecture circles back to connect the GCD with integer linear combinations.

• Bézout's Lemma: The GCD(a, b) can always be expressed as an integer linear combination of a and b.
  • Proof: This is proven by strong induction using the recurrence from Euclid's algorithm. If GCD(b, a rem b) is an ILC of b and a rem b, and a rem b is itself an ILC of a and b, then GCD(a,b) must also be an ILC of a and b.
• The Pulverizer (Extended Euclidean Algorithm): This is an extension of Euclid's algorithm that not only computes the GCD but also finds the integer coefficients s and t for Bézout's identity (GCD(a,b) = sa + tb). It works by keeping track of how to represent each intermediate remainder as an ILC of the original a and b.
• Solving the Puzzle (Revisited): The Pulverizer provides a constructive way to solve the water pouring puzzle. By finding coefficients s and t such that 1 = s*5 + t*3, we can multiply by 4 to get 4 = (4s)*5 + (4t)*3. This gives an explicit recipe (e.g., add 4s 5-gallon jugs and remove |4t| 3-gallon jugs) for measuring out the target of 4 gallons.

L9: Modular Arithmic

1. Introduction to Modular Arithmetic
The lecture, led by instructor Brynmor Chapman, introduces modular arithmetic, a fundamental concept in number theory with wide-ranging applications in computer science.

• Motivation: The core idea is illustrated with familiar examples:
  • even + odd = odd (arithmetic modulo 2)
  • The last digit of a product (arithmetic modulo 10)
  • Telling time on a clock (arithmetic modulo 12 or 24)
  • Days of the week (arithmetic modulo 7)
• The Theme: In modular arithmetic, we ignore multiples of a given number n (the modulus) and focus only on the remainders.

2. Congruence and Remainders
The lecture formally defines the key concepts.

• Congruence: Two integers a and b are congruent modulo n (written a ≡ b (mod n)) if and only if n divides their difference (n | (a - b)). This means a and b have the same remainder when divided by n.
• Congruence Classes: This congruence relation partitions the integers into n distinct equivalence classes, represented by the possible remainders {0, 1, ..., n-1}.
• The Division Theorem: A review of the division theorem, which states that for any integer a and positive integer n, there exist a unique integer quotient q and remainder r such that a = qn + r and 0 ≤ r < n.
• Notation Warning: The lecture makes a crucial distinction between the congruence relation a ≡ b (mod n) and the remainder function a = (b rem n). The former is a statement of equivalence, while the latter is an assignment of a specific value. To avoid confusion, the course will use rem for the function and ≡ (mod n) for the relation.

3. Rules of Modular Arithmetic
A key property of modular arithmetic is that addition, subtraction, and multiplication behave as expected with respect to congruence.

• The Theorem: If a ≡ b (mod n), then for any integer c:
  • a + c ≡ b + c (mod n)
  • a - c ≡ b - c (mod n)
  • a * c ≡ b * c (mod n)
• The Implication: This means that during a computation modulo n, any number can be replaced by any other number it is congruent to. This is the core principle that simplifies calculations. For example, to compute (7799 * 6) mod 100, we can replace 7799 with -1, making the calculation trivial: (-1 * 6) = -6 ≡ 94 (mod 100).
• Exponentiation:
  • Bases: It is also true that if a ≡ b (mod n), then aᶜ ≡ bᶜ (mod n). This is proven by induction on c. We can replace the base of an exponent.
  • Exponents: However, it is not generally true that a ≡ b (mod n) implies cᵃ ≡ cᵇ (mod n). We cannot simply reduce exponents modulo n. A counterexample is shown: 1 ≡ 6 (mod 5), but (-1)¹ is not congruent to (-1)⁶ modulo 5.

4. Modular Division and Multiplicative Inverses
The lecture then addresses the tricky question of division in modular arithmetic.

• The Problem: We cannot always "cancel" common factors. For example, 3x ≡ 3 (mod 6) does not imply x ≡ 1 (mod 6). A counterexample is x=3, for which 9 ≡ 3 (mod 6) is true, but 3 is not congruent to 1.
• Multiplicative Inverse: Division by a is equivalent to multiplication by its multiplicative inverse, a⁻¹. An integer b is the multiplicative inverse of a modulo n if ab ≡ 1 (mod n).
• Existence of Inverses: A crucial theorem is proven: An integer (i.e., a and n are relatively prime or coprime).
  • Proof: ab ≡ 1 (mod n) is equivalent to ab - 1 = qn for some integer q. Rearranging gives 1 = ab - qn, which is an integer linear combination (ILC) of a and n. By Bézout's identity (from the previous lecture), an ILC of a and n can equal 1 if and only if GCD(a, n) = 1.
• The Implication: We can "divide" by a (i.e., cancel it from both sides of a congruence) if and only if GCD(a, n) = 1.

5. Fermat's Little Theorem
This famous theorem provides a powerful tool for simplifying exponents in modular arithmetic, addressing the issue raised earlier.

• The Theorem: If p is a prime number and a is an integer not divisible by p, then:
  aᵖ⁻¹ ≡ 1 (mod p)
• The Implication: This means that when working with an exponent modulo a prime p, we can reduce the exponent modulo . For example, 7⁹⁵ (mod 13) is equivalent to 7^(95 rem 12) = 7¹¹ (mod 13).
• Proof Sketch:
  1. Consider the set S = {a, 2a, 3a, ..., (p-1)a}.
  2. It is shown that, modulo p, the elements of this set are all distinct and non-zero. Therefore, they must be a permutation of the set {1, 2, ..., p-1}.
  3. Take the product of all elements in each set.
     • Product of {1, ..., p-1} is (p-1)!.
     • Product of {a, ..., (p-1)a} is aᵖ⁻¹ * (p-1)!.
  4. Since the sets are congruent modulo p, their products must also be congruent: aᵖ⁻¹ * (p-1)! ≡ (p-1)! (mod p).
  5. Since p is prime, (p-1)! is not divisible by p, so GCD((p-1)!, p) = 1. This means (p-1)! has a multiplicative inverse, and we can cancel it from both sides, leaving aᵖ⁻¹ ≡ 1 (mod p).

This theorem provides the missing piece for handling exponents and is a cornerstone of many cryptographic algorithms that rely on modular exponentiation.

L10: Cryptography

1. Introduction to Cryptography
The lecture, led by instructor Brynmor Chapman, shifts from pure number theory to one of its most critical applications: cryptography, the science of protecting information.

• The Setup: The standard scenario involves two parties, Alice and Bob, who want to communicate securely over an insecure channel, and an eavesdropper, Eve, who may try to read or alter their messages.
• Core Concepts:
  • Encryption: The process of "garbling" a plaintext message M into a ciphertext C so that it appears as random noise.
  • Decryption: The process of recovering the original message M from the ciphertext C.
  • Secret Key: A piece of shared, secret data that enables both encryption and decryption.

2. A History of Private Key Cryptography
The lecture begins with a historical overview of private key (or symmetric) cryptosystems, where Alice and Bob must share the same secret key for both encryption and decryption.

• Caesar Cipher: A simple substitution cipher where each letter is shifted by 3 positions. It is insecure because the "key" is fixed and public knowledge.
• Caesar Shift: A slight improvement where the shift amount is a secret key k. This is still insecure because the key space is tiny (only 25 possibilities), making it vulnerable to a brute-force attack.
• Substitution Cipher: The key is a full permutation of the alphabet. The key space is much larger (26!), but it is still vulnerable to frequency analysis. By comparing the letter frequencies in the ciphertext to known frequencies in the language (e.g., 'E' is the most common letter in English), an attacker can deduce parts of the key.
• Enigma Cipher (WWII): A more complex system that used a different substitution cipher for each letter in the message. While it defeated simple frequency analysis, it was ultimately broken by the Allies at Bletchley Park using known-plaintext attacks. They could often guess parts of the message (e.g., a weather report or a standard sign-off), which provided enough information to deduce the daily key.

3. Public Key Cryptography
The lecture then introduces the modern paradigm of public key (or asymmetric) cryptography.

• The Idea: Each person has two keys: a public key (, which is shared with everyone, and a secret key (, which is kept private.
  • Encryption: Anyone can encrypt a message for Bob using Bob's public key. C = E(M, k_p_Bob)
  • Decryption: Only Bob can decrypt the message, using his own secret key. M = D(C, k_s_Bob)
• The Advantage: This solves the key distribution problem of private key systems. Alice and Bob do not need to meet in secret beforehand to exchange a key.

4. The RSA Cryptosystem
RSA is the most famous and widely used public key cryptosystem. Its security relies on the computational difficulty of factoring large numbers.

• The Goal: To find an encryption exponent e and a decryption exponent d such that (M^e)^d ≡ M (mod n).
• The Key Insight (Fermat's Little Theorem): Recall from the previous lecture, if p is prime, a^(p-1) ≡ 1 (mod p). This implies a^(k(p-1)+1) ≡ a (mod p).
• A First (Insecure) Attempt:
  1. Let the modulus n be a large prime p.
  2. Choose an encryption key e.
  3. Find a decryption key d such that ed ≡ 1 (mod p-1). This can be done efficiently using the Pulverizer (Extended Euclidean Algorithm) to find the modular inverse of e.
  4. The public key would be (p, e) and the secret key would be (p, d).
  5. The Flaw: This is insecure because if an adversary knows p and e (from the public key), they can use the same Pulverizer algorithm to compute d.
• The Real RSA Algorithm:
  1. Key Generation:
     • Choose two very large, distinct prime numbers, p and q.
     • Compute the modulus n = p * q.
     • Compute φ(n) = (p-1)(q-1) (Euler's totient function).
     • Choose an encryption exponent e that is coprime to φ(n).
     • Compute the decryption exponent d such that ed ≡ 1 (mod φ(n)).
  2. Public Key: (n, e).
  3. Secret Key: (n, d). (Crucially, p and q are also kept secret).
• Correctness: The lecture proves that decryption works. The condition ed ≡ 1 (mod (p-1)(q-1)) implies that ed ≡ 1 (mod p-1) and ed ≡ 1 (mod q-1). By Fermat's Little Theorem, this means M^(ed) ≡ M (mod p) and M^(ed) ≡ M (mod q). Since p and q are distinct primes, if they both divide M^(ed) - M, their product n must also divide it. Therefore, M^(ed) ≡ M (mod n).
• Security: The security of RSA relies on the belief that factoring is computationally hard. An adversary knows n and e. To find d, they would need to know φ(n) = (p-1)(q-1). To find φ(n), they would need to find the prime factors p and q of n. For very large numbers (e.g., hundreds of digits), this is believed to be an intractable problem for classical computers.

5. The Chinese Remainder Theorem (CRT)
The final topic is the Chinese Remainder Theorem, a powerful tool for solving systems of congruences. It is also used to speed up RSA computations in practice.

• The Theorem: If p and q are coprime, then the system of congruences:
  1. x ≡ a (mod p)
  2. x ≡ b (mod q)
     has a unique solution for x modulo p*q.
• Example: To find x such that x ≡ 4 (mod 5) and x ≡ 7 (mod 11):
  1. List the solutions to the second congruence: {7, 18, 29, 40, 51, ...}.
  2. Check which of these is congruent to 4 modulo 5. The number 29 is the unique solution in the range 0 to 54.
• Constructive Proof of CRT: The lecture provides a constructive proof for the general case, showing how to build the solution x from the given parameters. This involves finding modular inverses (using the Pulverizer) and combining solutions to simpler subproblems.
• Uniqueness Proof: The uniqueness of the solution is proven by assuming two solutions x and x' exist and showing that their difference x - x' must be divisible by both p and q. Since p and q are coprime, x - x' must be divisible by their product pq, meaning x ≡ x' (mod pq).

L11: Graphs and Coloring

1. Introduction to Graph Theory
The lecture, led by instructor Zachary Abel, marks the beginning of a new unit on Graph Theory. Graphs are presented as a powerful and versatile mathematical abstraction for modeling pairwise relationships between objects, with applications across computer science and beyond.

• Definition of a Simple Undirected Graph: A graph G is a pair (V, E) where:
  • V is a non-empty set of vertices (or nodes).
  • E is a set of edges, where each edge is a two-element subset of V.
• Conventions for "Simple" Graphs: The graphs in this course will be "simple," meaning they do not have:
  • Self-loops: Edges connecting a vertex to itself.
  • Parallel edges: Multiple edges connecting the same pair of vertices.
• Applications: Graphs are useful for modeling a wide range of real-world scenarios, including:
  • Social networks (people as vertices, friendships as edges).
  • The brain (neurons as vertices, synaptic connections as edges).
  • The internet (servers as vertices, network connections as edges).

2. Fundamental Graph Terminology and the Handshake Lemma
The lecture introduces the basic vocabulary for discussing graphs.

• Adjacency and Incidence:
  • Two vertices are adjacent if they are connected by an edge.
  • An edge is incident to its two endpoint vertices.
• Vertex Degree: The degree of a vertex is the number of edges incident to it.
• The Handshake Lemma: This is a fundamental theorem relating vertex degrees to the number of edges.
  • Theorem: For any graph, the sum of the degrees of all vertices is equal to twice the number of edges. Σ_{v∈V} deg(v) = 2|E|.
  • Proof Intuition: When summing the degrees, we are counting the endpoints of all edges. Since each edge has exactly two endpoints, each edge is counted twice in the sum.
• Corollaries:
  • Odd Degree Vertices: The sum of degrees must be an even number. This implies that the number of vertices with an odd degree must be even. (This was used to show that a graph with degree sequence 2, 2, 1 is impossible).
  • Maximum Edges: The maximum number of edges in a graph with n vertices is n(n-1)/2. This is achieved by the complete graph , where every pair of vertices is connected by an edge.

3. Bipartite Graphs
A special class of graphs is introduced with a real-world example.

• The "Harvard Friends" Problem: Is the average number of Harvard friends for an MIT student greater or smaller than the average number of MIT friends for a Harvard student?
• Bipartite Graph: A graph is bipartite if its vertex set V can be partitioned into two disjoint sets, L and R, such that every edge connects a vertex in L to a vertex in R. There are no edges within L or within R.
• Bipartite Handshake Lemma: In a bipartite graph, the sum of degrees of vertices in L is equal to the number of edges, which is also equal to the sum of degrees of vertices in R. Σ_{v∈L} deg(v) = |E| = Σ_{v∈R} deg(v).
• Solving the Problem: The friendships between MIT and Harvard students form a bipartite graph. The average number of Harvard friends per MIT student is |E| / |MIT|. The average for Harvard students is |E| / |Harvard|. Since |Harvard| > |MIT|, the average MIT student has more Harvard friends than the average Harvard student has MIT friends.

4. Graph Coloring
The lecture introduces a classic problem in graph theory: graph coloring.

• Motivating Example (Exam Scheduling): The problem of scheduling final exams can be modeled as a graph coloring problem.
  • Vertices: MIT classes.
  • Edges: An edge connects two classes if there is at least one student enrolled in both (a conflict).
  • Colors: Final exam time slots.
• Proper k-Coloring: A proper k-coloring of a graph is an assignment of one of k colors to each vertex such that no two adjacent vertices share the same color.
• Chromatic Number ( The chromatic number of a graph G is the minimum number of colors k needed for a proper coloring.
  • To prove χ(G) = k, one must show both an upper bound (by providing a valid k-coloring) and a lower bound (by proving that k-1 colors are insufficient, often by finding a substructure like a triangle that requires 3 colors).
• Computational Hardness: Finding the chromatic number of a graph is an NP-complete problem. This means there is no known efficient (polynomial-time) algorithm to solve it, and it is widely believed that none exists. Even the simpler problem of deciding if a graph is 3-colorable is NP-complete.

5. The Greedy Coloring Algorithm
Since finding the optimal coloring is hard, a simple and fast heuristic algorithm is presented.

• The Algorithm:
  • Fix an arbitrary ordering of the vertices v₁, v₂, ..., vₙ.
  • Fix an ordering of the available colors 1, 2, 3, ....
  • Iterate through the vertices from v₁ to vₙ. For each vertex vᵢ, assign it the smallest-numbered color that has not already been used by any of its already-colored neighbors.
• Performance:
  • The algorithm always produces a proper coloring.
  • The quality of the coloring (how many colors it uses) depends heavily on the chosen vertex ordering. Different orderings can lead to colorings with different numbers of colors.
  • It is not guaranteed to find the optimal (minimum) coloring.
• Performance Guarantee (Theorem): A key result is proven about the greedy algorithm's performance.
  • Theorem: For any graph G, the greedy algorithm will use at most Δ(G) + 1 colors, where Δ(G) is the maximum degree of any vertex in the graph.
  • Proof by Induction on the Number of Vertices:
    1. Predicate The theorem is true for all graphs with n vertices.
    2. Base Case Trivial. A 1-vertex graph has max degree 0 and is 1-colored.
    3. Inductive Step: Assume P(n) is true. Consider an arbitrary (n+1)-vertex graph G with max degree Δ.
    4. When running the greedy algorithm, the first n vertices v₁, ..., vₙ form an n-vertex subgraph. By the inductive hypothesis, these vertices will be colored with at most Δ+1 colors.
    5. Now consider the final vertex, vₙ₊₁. It has at most Δ neighbors among the already-colored vertices.
    6. Since it has at most Δ neighbors, there are at most Δ colors that it cannot use.
    7. Therefore, among the first Δ+1 available colors, there must be at least one color that is available for vₙ₊₁. The greedy algorithm will assign it that color.
    8. Thus, the entire (n+1)-vertex graph is colored with at most Δ+1 colors. This completes the induction.

L12: Matchings

1. Introduction to Matchings
The lecture, led by instructor Zachary Abel, introduces the graph theory concept of a matching, a fundamental tool for modeling problems involving pairing up objects.

• Definition: A matching in a graph is a subset of edges where no two edges share a vertex. In other words, every vertex in the subgraph defined by the matching has a degree of at most 1.
• Applications:
  • Online Dating: Matching users to each other for dates.
  • Resource Allocation: Matching computational tasks to servers.
• Goal: In many applications, the goal is to find a matching that is as large as possible.

2. Maximal vs. Maximum Matchings
A crucial distinction is made between two notions of a "large" matching.

• Maximal Matching: A matching is maximal if it cannot be extended by adding any other edge from the graph. This is a local property. A simple greedy algorithm (keep adding non-conflicting edges) can easily find a maximal matching.
• Maximum Matching: A matching is maximum if it is the largest possible matching in the entire graph (i.e., no other matching has more edges). This is a global property and is generally harder to find.
• Key Point: A maximal matching is not necessarily a maximum matching. The lecture provides an example where a maximal matching of size 2 exists in a graph whose maximum matching has size 3.

3. Perfect Matchings and Bipartite Graphs

• Perfect Matching: A matching is perfect if it includes every vertex in the graph. This means every vertex is paired up. A perfect matching can only exist if the graph has an even number of vertices.
• Bipartite Matchings: Matchings are particularly important in bipartite graphs, where vertices are split into two sets and edges only connect vertices from opposite sets (e.g., applicants and evaluators).
• Weighted Bipartite Matching: In many real-world problems, edges have weights (e.g., the "cost" or "quality" of a pairing). A common goal is to find a perfect matching with the minimum total weight.
• Efficient Algorithms: Unlike graph coloring (which is NP-complete), there exist efficient, polynomial-time algorithms for finding maximum matchings and min-weight perfect matchings.

4. The Stable Matching Problem
The main topic of the lecture is the stable matching problem, a classic problem with significant real-world applications, most famously the National Resident Matching Program for medical school graduates.

• The Setup:
  1. A bipartite graph with n applicants on one side and n evaluators on the other.
  2. Each applicant provides a strict, ranked preference list of all n evaluators.
  3. Each evaluator provides a strict, ranked preference list of all n applicants.
• The Goal: Find a stable matching, which is a perfect matching with no "rogue pairs."
• Rogue Pair: A pair (applicant A, evaluator E) that are not matched to each other is a rogue pair if:
  1. A prefers E over their currently assigned partner.
  2. E prefers A over their currently assigned partner.
     The existence of a rogue pair makes the matching "unstable" because A and E have a mutual incentive to abandon their current partners and pair up with each other.

5. The Gale-Shapley Algorithm
This is a famous algorithm that is guaranteed to find a stable matching.

• The Algorithm (Applicant-Proposing Version): The algorithm proceeds in a series of "days."
  1. Proposal Step: On each day, every unmatched applicant proposes to the next evaluator on their preference list whom they have not yet proposed to.
  2. Decision Step: Each evaluator who receives one or more proposals considers all of them. They tentatively "hold on to" the one they prefer the most and reject all others. An evaluator will also reject their current partner if a new, more preferred applicant proposes.
  3. Termination: The algorithm stops when a day passes with no rejections. The set of tentatively held pairs becomes the final matching.
• Demonstration: The lecture includes a detailed, step-by-step walkthrough of the algorithm on a 5x5 example, showing how applicants are rejected and make new proposals on subsequent days until a stable state is reached.

6. Analysis of the Gale-Shapley Algorithm
The lecture proves that the algorithm has several desirable properties.

• Termination: The algorithm is guaranteed to terminate in at most n² steps. This is because each applicant proposes to each evaluator at most once. Once rejected, an applicant never proposes to that evaluator again. There are n² possible proposals, so the algorithm must halt.
• Returns a Perfect Matching: The algorithm always produces a perfect matching; no applicant is left unmatched.
  • Proof by Contradiction: Assume an applicant A is rejected by all n evaluators. The final rejection must have been because an evaluator E preferred some other applicant A'. By an invariant property, this means E (and every other evaluator) ends up matched with someone they prefer over A. This would require n evaluators to be matched with n distinct applicants, none of whom are A. This is impossible, as there are only n-1 other applicants available.
• Returns a Stable Matching: The resulting matching is guaranteed to be stable (it has no rogue pairs).
  • Proof Sketch: Consider any unmatched pair (A, E).
    • Case 1: . This means A must have been matched with someone they prefer over E (otherwise they would have kept proposing down their list until they reached E). So, A has no incentive to form a rogue pair with E.
    • Case 2: This means E either rejected A immediately for someone better, or was holding A and later rejected them for someone better. In either case, E ends up matched with someone they prefer over A. So, E has no incentive to form a rogue pair with A.
  • Since in all cases, at least one member of any unmatched pair does not want to defect, no rogue pairs can exist.

7. Optimality Properties
A surprising result is that the algorithm is systematically biased depending on which side proposes.

• Feasible Partner: An applicant A and evaluator E are feasible partners if there exists some stable matching that pairs them together.
• Theorems:
  1. The applicant-proposing Gale-Shapley algorithm finds the matching that is best for all applicants and simultaneously worst for all evaluators. Every applicant is matched with their most-preferred feasible partner, while every evaluator is matched with their least-preferred feasible partner.
  2. Conversely, the evaluator-proposing version finds the matching that is best for all evaluators and worst for all applicants.
• Implication: This explains why running the algorithm with the roles swapped generally produces a different stable matching. The proposing side has a distinct advantage.

L13: Connectivity and Trees

1. Introduction to Matchings
The lecture, led by instructor Zachary Abel, introduces the graph theory concept of a matching, a fundamental tool for modeling problems involving pairing up objects.

• Definition: A matching in a graph is a subset of edges where no two edges share a vertex. In other words, every vertex in the subgraph defined by the matching has a degree of at most 1.
• Applications:
  • Online Dating: Matching users to each other for dates.
  • Resource Allocation: Matching computational tasks to servers.
• Goal: In many applications, the goal is to find a matching that is as large as possible.

2. Maximal vs. Maximum Matchings
A crucial distinction is made between two notions of a "large" matching.

• Maximal Matching: A matching is maximal if it cannot be extended by adding any other edge from the graph. This is a local property. A simple greedy algorithm (keep adding non-conflicting edges) can easily find a maximal matching.
• Maximum Matching: A matching is maximum if it is the largest possible matching in the entire graph (i.e., no other matching has more edges). This is a global property and is generally harder to find.
• Key Point: A maximal matching is not necessarily a maximum matching. The lecture provides an example where a maximal matching of size 2 exists in a graph whose maximum matching has size 3.

3. Perfect Matchings and Bipartite Graphs

• Perfect Matching: A matching is perfect if it includes every vertex in the graph. This means every vertex is paired up. A perfect matching can only exist if the graph has an even number of vertices.
• Bipartite Matchings: Matchings are particularly important in bipartite graphs, where vertices are split into two sets and edges only connect vertices from opposite sets (e.g., applicants and evaluators).
• Weighted Bipartite Matching: In many real-world problems, edges have weights (e.g., the "cost" or "quality" of a pairing). A common goal is to find a perfect matching with the minimum total weight.
• Efficient Algorithms: Unlike graph coloring (which is NP-complete), there exist efficient, polynomial-time algorithms for finding maximum matchings and min-weight perfect matchings.

4. The Stable Matching Problem
The main topic of the lecture is the stable matching problem, a classic problem with significant real-world applications, most famously the National Resident Matching Program for medical school graduates.

• The Setup:
  1. A bipartite graph with n applicants on one side and n evaluators on the other.
  2. Each applicant provides a strict, ranked preference list of all n evaluators.
  3. Each evaluator provides a strict, ranked preference list of all n applicants.
• The Goal: Find a stable matching, which is a perfect matching with no "rogue pairs."
• Rogue Pair: A pair (applicant A, evaluator E) that are not matched to each other is a rogue pair if:
  1. A prefers E over their currently assigned partner.
  2. E prefers A over their currently assigned partner.
     The existence of a rogue pair makes the matching "unstable" because A and E have a mutual incentive to abandon their current partners and pair up with each other.

5. The Gale-Shapley Algorithm
This is a famous algorithm that is guaranteed to find a stable matching.

• The Algorithm (Applicant-Proposing Version): The algorithm proceeds in a series of "days."
  1. Proposal Step: On each day, every unmatched applicant proposes to the next evaluator on their preference list whom they have not yet proposed to.
  2. Decision Step: Each evaluator who receives one or more proposals considers all of them. They tentatively "hold on to" the one they prefer the most and reject all others. An evaluator will also reject their current partner if a new, more preferred applicant proposes.
  3. Termination: The algorithm stops when a day passes with no rejections. The set of tentatively held pairs becomes the final matching.
• Demonstration: The lecture includes a detailed, step-by-step walkthrough of the algorithm on a 5x5 example, showing how applicants are rejected and make new proposals on subsequent days until a stable state is reached.

6. Analysis of the Gale-Shapley Algorithm
The lecture proves that the algorithm has several desirable properties.

• Termination: The algorithm is guaranteed to terminate in at most n² steps. This is because each applicant proposes to each evaluator at most once. Once rejected, an applicant never proposes to that evaluator again. There are n² possible proposals, so the algorithm must halt.
• Returns a Perfect Matching: The algorithm always produces a perfect matching; no applicant is left unmatched.
  • Proof by Contradiction: Assume an applicant A is rejected by all n evaluators. The final rejection must have been because an evaluator E preferred some other applicant A'. By an invariant property, this means E (and every other evaluator) ends up matched with someone they prefer over A. This would require n evaluators to be matched with n distinct applicants, none of whom are A. This is impossible, as there are only n-1 other applicants available.
• Returns a Stable Matching: The resulting matching is guaranteed to be stable (it has no rogue pairs).
  • Proof Sketch: Consider any unmatched pair (A, E).
    • Case 1: . This means A must have been matched with someone they prefer over E (otherwise they would have kept proposing down their list until they reached E). So, A has no incentive to form a rogue pair with E.
    • Case 2: This means E either rejected A immediately for someone better, or was holding A and later rejected them for someone better. In either case, E ends up matched with someone they prefer over A. So, E has no incentive to form a rogue pair with A.
  • Since in all cases, at least one member of any unmatched pair does not want to defect, no rogue pairs can exist.

7. Optimality Properties
A surprising result is that the algorithm is systematically biased depending on which side proposes.

• Feasible Partner: An applicant A and evaluator E are feasible partners if there exists some stable matching that pairs them together.
• Theorems:
  1. The applicant-proposing Gale-Shapley algorithm finds the matching that is best for all applicants and simultaneously worst for all evaluators. Every applicant is matched with their most-preferred feasible partner, while every evaluator is matched with their least-preferred feasible partner.
  2. Conversely, the evaluator-proposing version finds the matching that is best for all evaluators and worst for all applicants.
• Implication: This explains why running the algorithm with the roles swapped generally produces a different stable matching. The proposing side has a distinct advantage.

L14: Digraphs and DAGs

1. Introduction to Directed Graphs (Digraphs)
The lecture, led by instructor Erik Demaine, transitions from undirected graphs to directed graphs (digraphs). This shift is motivated by scenarios where relationships are one-way, such as one-way streets, follower relationships on social media, or hyperlinks on the web.

• Definition of a Directed Graph: A digraph G is a pair (V, E) where:
  • V is a set of vertices.
  • E is a set of ordered pairs of vertices, representing directed edges.
• Key Differences from Undirected Graphs:
  • An edge (u, v) is distinct from (v, u).
  • Self-loops (v, v) are allowed.
• In-degree and Out-degree: For a vertex v:
  • In-degree: The number of edges pointing into v.
  • Out-degree: The number of edges pointing out of v.
• Directed Handshake Lemma: The sum of all in-degrees is equal to the number of edges, which is also equal to the sum of all out-degrees. Σ deg⁻(v) = |E| = Σ deg⁺(v).

2. Walks, Paths, and Reachability in Digraphs
The concepts of movement within a graph are adapted for the directed case.

• Directed Walk: A sequence of vertices v₀, v₁, ..., vₖ where each (vᵢ, vᵢ₊₁) is a directed edge in the graph. The arrows must be respected.
• Directed Path: A walk with no repeated vertices or edges.
• Reachability: A vertex v is reachable from a vertex u if there exists a walk from u to v.
  • This relation is reflexive (v can reach v) and transitive (u → v and v → w implies u → w).
  • Crucially, it is not symmetric. The existence of a walk from u to v does not imply the existence of a walk from v to u.

3. Connectivity in Digraphs
The lack of symmetry in reachability leads to a more nuanced definition of connectivity.

• Strongly Connected: Two vertices u and v are strongly connected if u can reach v AND v can reach u.
• Strongly Connected Graph: A graph is strongly connected if every pair of vertices is strongly connected.
• Strongly Connected Components (SCCs): An SCC is a maximal subgraph where all vertices are mutually reachable.
  • The SCCs partition the vertices of a digraph.
  • Unlike in undirected graphs, there can be edges between different SCCs.
• Condensation Graph: A useful abstraction where each SCC is contracted into a single "super-vertex." An edge exists from one super-vertex to another if there was an edge in the original graph between the corresponding components. The condensation graph is always a Directed Acyclic Graph (DAG).

4. Directed Acyclic Graphs (DAGs)
DAGs are a particularly important class of directed graphs that have no directed cycles.

• Applications: DAGs are a natural way to model precedence constraints, such as task dependencies in a project or the order of getting dressed (e.g., "socks before shoes").
• Key Lemma: Every finite DAG has at least one source (a vertex with in-degree 0) and at least one sink (a vertex with out-degree 0).
  • Proof: Consider a longest path in the DAG. The start vertex of this path cannot have any incoming edges (otherwise the path could be extended, contradicting its maximality, or there would be a cycle, contradicting the DAG property). A similar argument holds for the end vertex being a sink.
• Topological Ordering (Topological Sort):
  • Definition: A linear ordering of the vertices of a DAG such that for every directed edge u → v, u comes before v in the ordering.
  • Existence: A topological ordering always exists for any finite DAG.
  • Proof by Induction (and Algorithm): The existence is proven by induction on the number of vertices. The proof also reveals the standard algorithm for finding a topological sort:
    1. Find a source vertex s (guaranteed to exist).
    2. Place s first in the ordering.
    3. Remove s and its outgoing edges from the graph. The remaining graph is still a DAG.
    4. Recursively find a topological sort for the remaining graph and append it.

5. Parallel Task Scheduling and Dilworth's Theorem
The lecture concludes with a practical application of DAGs: scheduling tasks with precedence constraints on a parallel machine.

• The Problem: Given a set of tasks (vertices) and dependencies (edges), what is the minimum time (span) required to complete all tasks, assuming an unlimited number of processors?
• The Schedule: A valid schedule assigns a time step t(v) to each task v such that if u must precede v, then t(u) < t(v). The span is the number of distinct time steps used.
• The Critical Path: The minimum possible span is limited by the longest path in the DAG. A path of k vertices requires at least k time steps.
• The Scheduling Algorithm: A simple and optimal algorithm is to schedule all current sources at each time step.
  • Time 0: Schedule all initial source vertices.
  • Time 1: Schedule all vertices that become sources after the Time 0 tasks are completed.
  • Repeat until all tasks are scheduled.
• Key Theorem: The minimum span of any schedule for a DAG is equal to the number of vertices on the longest path.
  • Proof: The longest path provides a lower bound. The "schedule-the-sources" algorithm provides an upper bound. The lecture proves that the schedule produced by this algorithm has a span equal to the longest path length, showing that both bounds meet and the algorithm is optimal.
• Chains and Antichains (Dilworth's Theorem): This result is recast in the language of partial orders.
  • A chain is a set of vertices that are all pairwise comparable (i.e., they form a path).
  • An antichain is a set of vertices that are all pairwise incomparable (no path exists between any two).
  • The scheduling problem is equivalent to partitioning the DAG into the minimum number of antichains (the sets of tasks done at each time step).
  • The theorem then becomes a famous result in combinatorics, Dilworth's Theorem: In any partial order, the size of the largest antichain is equal to the minimum number of chains needed to cover all elements. (And its dual, which was proven in the lecture: the size of the longest chain is the minimum number of antichains needed to cover all elements).

L15: Relations and Counting

1. Introduction to Relations
The lecture, led by instructor Zachary Abel, introduces the concept of relations, which generalizes the idea of a function and provides a formal language for modeling relationships between objects.

• Definition: A binary relation R from a domain A to a codomain B is a subset of the Cartesian product A x B. It is simply a set of ordered pairs (a, b) where a ∈ A and b ∈ B.
• Visualization: Relations can be visualized as directed graphs, where the vertices are the elements of A and B, and an arrow is drawn from a to b if (a, b) is in the relation.
• Notation: The statement (a, b) ∈ R can be written in several equivalent ways: aRb, R(a,b) is true, or "a relates to b."
• Example: The lecture uses a motivating example of students, classes, and professors.
  • The "learning" relation L is a subset of Students x Classes, where (student, class) ∈ L if the student is taking that class.
  • The "teaching" relation T is a subset of Classes x Professors.

2. Types of Relations: Functions
The lecture formalizes the connection between relations and functions.

• Function: A relation R from A to B is a function if every element in the domain A relates to at most one element in the codomain B (i.e., every vertex in A has at most one outgoing arrow).
• Total Relation: A relation is total if every element in the domain A relates to at least one element in the codomain B (every vertex in A has at least one outgoing arrow).
• Total Function: A relation that is both total and a function. This means every element in A relates to exactly one element in B. This is the standard definition of a function in mathematics.
• Partial Function: A function that is not necessarily total.
• Injective ("One-to-one"): A relation is injective if every element in the codomain B is related to by at most one element from the domain A (every vertex in B has at most one incoming arrow).
• Surjective ("Onto"): A relation is surjective if every element in the codomain B is related to by at least one element from the domain A (every vertex in B has at least one incoming arrow).
• Bijection: A relation that is a total function, injective, and surjective. This means every element in A is paired with exactly one element in B, and vice versa.

3. Counting with Relations: The Bijection Rule
These definitions provide powerful tools for counting and comparing the sizes of sets.

• If there is a total injection from A to B, then |A| ≤ |B|.
• If there is a surjective function from A to B, then |A| ≥ |B|.
• If there is a bijection from A to B, then |A| = |B|.

This last rule, the bijection rule, is a cornerstone of combinatorics. It allows us to count the size of a complex set A by finding a simpler set B of known size and constructing a bijection between them. This is analogized to the "parable of the two shepherds," where a shepherd without number words can verify their flock's size by creating a one-to-one correspondence between sheep and pebbles.
4. Special Relations: Relations on a Set
The lecture then focuses on the special case where the domain and codomain are the same set (R ⊆ A x A). These are equivalent to directed graphs where V=A.

• Properties of Relations on a Set:
  • Reflexive: Every element relates to itself (aRa for all a). (Every vertex has a self-loop).
  • Symmetric: If aRb, then bRa. (If there is an edge a → b, there is also an edge b → a).
  • Transitive: If aRb and bRc, then aRc. (If there is a path of length 2 from a to c, there is a direct edge a → c).
• Equivalence Relation: A relation that is reflexive, symmetric, and transitive. This formalizes the notion of "sameness." A key theorem states that an equivalence relation on a set A partitions A into disjoint equivalence classes. Two elements are related if and only if they belong to the same class (e.g., congruence mod n).
• Weak Partial Order: A relation that is reflexive, antisymmetric, and transitive. This formalizes the notion of "less than or equal to."
  • Antisymmetric: If aRb and bRa, then a=b.
• Total Order: A weak partial order where every pair of elements is comparable (either aRb or bRa).

5. The Rules of Counting
The second half of the lecture introduces the fundamental principles of combinatorial counting.

1. The Product Rule: If a process consists of a sequence of independent choices, the total number of outcomes is the product of the number of options at each stage. The size of a Cartesian product A₁ x ... x Aₙ is |A₁| * ... * |Aₙ|.
   • Example: The number of binary strings of length n is 2 * 2 * ... * 2 = 2ⁿ.
2. The Bijection Rule (revisited): To count a set A, find a bijection to a set B whose size is known.
   • Example: The number of subsets of an n-element set is 2ⁿ. This is proven by constructing a bijection between subsets and binary strings of length n. A string b₁...bₙ corresponds to the subset containing element i if and only if bᵢ = 1.
3. The Sum Rule: If a set A is the disjoint union of sets A₁, ..., Aₙ, then |A| = |A₁| + ... + |Aₙ|.
   • Intuition: "OR means add."
   • Example: The number of passwords of length 6, 7, OR 8 is the sum of the number of passwords of length 6, the number of length 7, and the number of length 8.
4. The Generalized Product Rule: This extends the product rule to cases where the set of choices at a later stage depends on the specific choice made earlier, but the number of choices does not.
   • Example: To count the number of permutations of a 52-card deck:
     • There are 52 choices for the first card.
     • No matter which card was chosen first, there are 51 remaining choices for the second card.
     • No matter which two were chosen, there are 50 choices for the third, and so on.
   • The total number of permutations is 52 * 51 * ... * 1 = 52!.

L16: Counting Techniques

1. Introduction: Counting Principles
The lecture, led by instructor Zachary Abel, continues the unit on counting and combinatorics. The focus is on developing systematic rules and techniques for counting the number of elements in a set, a crucial skill for probability, algorithm analysis, and other areas of computer science.
2. The Generalized Product Rule
The lecture begins by reviewing the Generalized Product Rule.

• The Rule: If a process consists of a sequence of k choices, and at step i there are nᵢ options available, regardless of the specific choices made in previous steps, then the total number of possible sequences is the product n₁ * n₂ * ... * nₖ.
• Key Distinction from Simple Product Rule: The set of available choices can change at each step, but the number of choices must remain constant.
• Example 1 (Serial Numbers):
  • How many 8-digit serial numbers are possible? Since digits can be repeated, there are 10 choices for each of the 8 positions. By the simple product rule, the total is 10 * 10 * ... * 10 = 10⁸.
  • How many have all distinct digits?
    • 1st digit: 10 choices.
    • 2nd digit: 9 choices (any digit except the first).
    • 3rd digit: 8 choices.
    • ...and so on.
    • By the generalized product rule, the total is 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3.

3. The Division Rule
This rule provides a powerful method for counting a set by relating it to another, easier-to-count set.

• The k-to-1 Correspondence: Suppose there is a function f from a set A to a set B. If f is a k-to-1 correspondence—meaning every element in A maps to exactly one element in B, and every element in B is mapped to by exactly k elements from A—then the size of the sets are related by |A| = k * |B|, or |B| = |A| / k.
• The Bijection Rule as a Special Case: The bijection rule is just the division rule where k=1.
• Example (Knights of the Round Table):
  • Problem: How many distinct ways can n knights be seated around a circular table, if rotations are considered the same arrangement?
  • The Strategy: Use the division rule.
    1. Let set A be the set of permutations (linear orderings) of the n knights. We know |A| = n!.
    2. Let set B be the set of cyclic seating arrangements. This is the set we want to count.
    3. Define a function f: A → B that maps a permutation to the cyclic arrangement it creates when the knights are seated in that order.
    4. Show that f is an n-to-1 map. Any given cyclic arrangement (an element of B) can be formed from exactly n different permutations (elements of A), corresponding to the n possible starting points in the linear ordering.
    5. Conclusion: By the division rule, |B| = |A| / n = n! / n = (n-1)!.

4. The Binomial Coefficient: "n choose k"
The lecture uses the division rule to derive one of the most important formulas in combinatorics.

• The Problem: How many subsets of size k can be chosen from a set of n elements?
• The Strategy: Use the division rule.
  • Let set A be the set of permutations of the n elements. |A| = n!.
  • Let set B be the set of subsets of size . This is what we want to count.
  • Define a function g: A → B that maps a permutation to the subset containing its first k elements.
  • Show that g is a k-to-1 map. How many permutations map to a given k-element subset?
    • There are k! ways to arrange the k chosen elements in the first k positions of the permutation.
    • There are (n-k)! ways to arrange the remaining n-k elements in the last n-k positions.
    • By the product rule, the total number of permutations mapping to that subset is k! * (n-k)!. This is our k.
  • Conclusion: By the division rule, the number of k-element subsets is:
    |B| = |A| / (k! * (n-k)!) = n! / (k! * (n-k)!)
• Notation: This quantity is denoted by the binomial coefficient (n choose k): (n k).
• Applications: This formula is ubiquitous.
  • Choosing 3 pizza toppings from 15 options: (15 choose 3).
  • Number of 100-bit binary strings with exactly 50 ones: (100 choose 50).

5. The Recipe Method (Counting with Sequences)
This is a powerful and general problem-solving strategy that combines the previously discussed rules.

• The Idea: To count a complex set B, devise a step-by-step recipe or a sequence of choices that uniquely constructs every element of B.
• The Two Critical Checks: For a recipe to be valid for counting, it must satisfy two conditions, which together ensure it defines a bijection between the set of choice sequences and the set B:
  • Completeness: Can every element in B be constructed by some sequence of choices in the recipe?
  • Uniqueness: Is every element in B constructed by exactly one sequence of choices?
• If the checks pass, the total number of elements in B is simply the number of ways to execute the recipe, which can be counted using the (generalized) product rule.
• Example (Four of a Kind Poker Hand):
  • Recipe: 1. Choose the rank for the four-of-a-kind (13 choices). 2. Choose the fifth "kicker" card from the remaining 48 cards.
  • Checks: This recipe is a bijection. Every four-of-a-kind hand can be constructed in exactly one way.
  • Count: 13 * 48.
• Example of a Flawed Recipe (Hand with at least one pair):
  • Flawed Recipe: 1. Choose the rank for a pair. 2. Choose 2 cards of that rank. 3. Choose 3 other cards.
  • Why it fails: The uniqueness check fails. A hand with two pairs (e.g., two aces and two kings) can be constructed in two different ways by this recipe (by choosing the aces first or by choosing the kings first). A full house (three of one rank, two of another) can be constructed in multiple ways. Because different hands are "overcounted" by different amounts, we cannot simply use the division rule to fix the count. This highlights the importance of carefully designing the recipe to ensure unique construction.

L17: More Counting Techniques

1. Introduction: The Principle of Inclusion-Exclusion (PIE)
The lecture, led by instructor Brynmor Chapman, begins by extending the Sum Rule of counting to handle sets that are not disjoint.

• Motivating Example (Cards):
  • Disjoint Sets: How many kings OR queens are in a deck? Since no card is both a king and a queen, we can use the sum rule: 4 + 4 = 8.
  • Overlapping Sets: How many hearts OR face cards are in a deck? Simply adding 13 (hearts) + 12 (face cards) is incorrect because it double-counts the cards that are both (the King, Queen, and Jack of Hearts).
• The Principle of Inclusion-Exclusion (for 2 sets): To correct for the double-counting, we must subtract the size of the intersection. This is the simplest form of PIE:
  |A ∪ B| = |A| + |B| - |A ∩ B|
• PIE for 3 Sets: The principle is extended to three sets. A simple sum and subtraction is no longer sufficient.
  • Include the sizes of the individual sets: |A| + |B| + |C|.
  • Exclude the sizes of the pairwise intersections: - |A ∩ B| - |A ∩ C| - |B ∩ C|.
  • This process correctly counts elements in only one or two sets, but it subtracts the elements in all three sets three times, leaving them with a total count of zero. We must include them back.
  • The Formula: |A ∪ B ∪ C| = |A|+|B|+|C| - (|A∩B|+|A∩C|+|B∩C|) + |A∩B∩C|.
• General Formula: The pattern continues for n sets. The size of the union is the sum of the sizes of single sets, minus the sum of the sizes of all pairwise intersections, plus the sum of all three-way intersections, and so on, alternating the sign at each step.
• Application (Euler's Totient Function): PIE is used to count the number of integers from 1 to n that are coprime to n.
  • The strategy is to count the complement: the number of integers that are not coprime to n. These are the numbers that share at least one prime factor with n.
  • Let the prime factors of n be p, q, r. Let A_p be the set of multiples of p, A_q be the set of multiples of q, etc.
  • We want to find |A_p ∪ A_q ∪ A_r|. Using PIE, we find this is (n/p + n/q + n/r) - (n/pq + n/pr + n/qr) + n/pqr. This leads to the well-known formula for Euler's totient function.

2. The Pigeonhole Principle
This is another fundamental counting principle, used for proving the existence of certain properties without necessarily constructing an example.

• The Principle: If you place more than n pigeons into n pigeonholes, then at least one pigeonhole must contain more than one pigeon.
• Formal Statement: If f: A → B is a total function and |A| > |B|, then f cannot be injective. (There must be at least two elements in A that map to the same element in B).
• Examples:
  • In a room of 27 people, at least two must share the first letter of their first name (27 pigeons, 26 pigeonholes/letters).
  • To guarantee you pull a matching pair of socks from a drawer with n different colors, you must pull n+1 socks (n+1 pigeons, n pigeonholes/colors).
• The Generalized Pigeonhole Principle: If |A| > k * |B|, then at least one pigeonhole must contain at least k+1 pigeons.
  • Example: The human head has at most ~200,000 hairs. The population of Boston is ~650,000. Since 650,000 > 3 * 200,000, the generalized pigeonhole principle implies there must be at least 3+1 = 4 people in Boston with the exact same number of hairs on their head.
• A More Complex Example (Rooks on a Chessboard):
  • Problem: Prove that if 33 rooks are placed on an 8x8 chessboard, there must exist a subset of 5 rooks, none of which attack each other.
  • The Creative Step: The challenge is to define the pigeons and pigeonholes correctly.
    • Pigeons: The 33 rooks.
    • Pigeonholes: The 8 "diagonals" of the board (wrapping around). Each diagonal k is the set of squares (i, j) such that (i+j) mod 8 = k. Rooks on the same diagonal do not attack each other.
  • The Proof: With 33 rooks (pigeons) and 8 diagonals (pigeonholes), since 33 > 4 * 8, the generalized pigeonhole principle guarantees that at least one diagonal must contain at least 4+1 = 5 rooks. These 5 rooks on the same diagonal do not attack each other.

3. Combinatorial Proofs (Double Counting)
This is a powerful proof technique for establishing combinatorial identities.

• The Idea: To prove that two expressions, A and B, are equal, find a single set S whose size can be counted in two different ways, leading to the expressions A and B respectively. Since both expressions count the same set, they must be equal.
• Example 1:
  • The Set The set of all binary strings of length n.
  • Counting Method 1 (Product Rule): There are n positions, each with 2 choices (0 or 1). The total number of strings is 2ⁿ.
  • Counting Method 2 (Sum Rule): Partition the strings based on the number of 1s they contain. The number of strings with exactly k ones is (n choose k). Summing over all possible values of k (from 0 to n) gives the total number of strings: Σ_{k=0 to n} (n choose k).
  • Conclusion: Since both methods count the same set, the expressions must be equal.
• Example 2: The Binomial Theorem
  • The "Set": Consider the terms generated by expanding the product (x+y)(x+y)...(x+y).
  • Counting Method 1: The expression itself is (x+y)ⁿ.
  • Counting Method 2: Each term in the full expansion is a string of n symbols, where each symbol is either x or y. We can group like terms. A term of the form xᵏyⁿ⁻ᵏ is formed by choosing x from k of the (x+y) factors and y from the remaining n-k factors. The number of ways to do this is (n choose k). Summing over all possible values of k gives the full expansion.
• Example 3: Pascal's Identity
  • The Set The set of all k-element subsets of an n-element set. The size of this set is, by definition, (n choose k).
  • Counting Method 2: Partition the subsets based on whether they contain a specific, distinguished element (say, element n).
    • Case 1 (Subsets containing element We must choose k-1 additional elements from the remaining n-1 elements. There are (n-1 choose k-1) ways to do this.
    • Case 2 (Subsets NOT containing element We must choose all k elements from the remaining n-1 elements. There are (n-1 choose k) ways to do this.
  • Conclusion: By the sum rule, |S| = (n-1 choose k-1) + (n-1 choose k). Since both expressions count the same set, they are equal. This identity is the rule for constructing Pascal's Triangle.

L18: Probability

1. Introduction: The Challenges of Probability
The lecture, led by instructor Brynmor Chapman, begins the final unit of the course on probability. It is framed as a discipline that is both immensely important across science and computer science (used in algorithms, cryptography, machine learning, etc.) and notoriously counter-intuitive. Common sense is often a poor guide, making a rigorous, step-by-step approach essential.
2. Case Study: The Monty Hall Problem
The famous Monty Hall problem is used as the primary motivating example to illustrate the pitfalls of intuition and the power of a formal approach.

• The Problem: You are on a game show and choose one of three doors. One door hides a car; the other two hide goats. After your initial choice, the host, Monty Hall, who knows where the car is, opens one of the other doors to reveal a goat. He then offers you the chance to switch your choice to the remaining closed door. Is it to your advantage to switch?
• The Controversy: This problem is famous for generating widespread debate. An initial poll of the class and a description of the historical controversy (when columnist Marilyn vos Savant was assailed by mathematicians for her correct answer) highlight the common but incorrect intuition that switching makes no difference.
• The Experiment: A live demonstration with student volunteers strongly suggests that switching is the better strategy, providing empirical evidence before the formal analysis.

3. The Tree Method for Analyzing Probability
To solve the Monty Hall problem and other probability puzzles, the lecture introduces a systematic, rigorous procedure called the Tree Method (also known as the four-step method).
Before any analysis, it is critical to precisely define the problem and state all assumptions. The ambiguity in the original letter to Marilyn vos Savant is resolved by establishing a clear set of axioms:

1. The prize is placed behind a random door with equal probability (1/3).
2. The contestant's initial choice of door is also uniform and random (1/3).
3. Monty must open a door that is not the contestant's choice and does not contain the prize.
4. If Monty has a choice between two doors to open (which only happens if the contestant initially picked the car), he chooses between them randomly (1/2 probability).

The first formal step is to define the set of all possible outcomes, known as the sample space, S.

• Probability Space: A probability space consists of a sample space S and a probability function Pr that assigns a non-negative probability to each outcome, such that the sum of all probabilities is 1.
• Tree Diagram: The sample space is constructed using a tree diagram. Each level of the tree represents a stage in the random process.
  1. Level 1 (Prize Location): The root branches into three possibilities for where Monty hides the prize (Door P, G, or S).
  2. Level 2 (Contestant's Pick): Each of those nodes branches into three more possibilities for the contestant's initial choice.
  3. Level 3 (Monty's Reveal): Each of those nodes branches into the possible doors Monty can open, consistent with the rules.
• Outcomes: The leaves of this tree represent the complete set of possible outcomes. Each outcome is a sequence of events (e.g., a tuple like (Prize=P, Pick=G, Reveal=S)).

The next step is to compute the probability of each outcome in the sample space.

• Edge Probabilities: Assign a probability to each edge in the tree, representing the conditional probability of that event occurring, given that the process has reached the edge's parent node.
  • Level 1 edges are all 1/3.
  • Level 2 edges are all 1/3.
  • Level 3 edges are either 1 (if Monty has no choice) or 1/2 (if Monty has a choice).
• Outcome Probability: The probability of a specific outcome (a leaf) is the product of the probabilities along the path from the root to that leaf.
• Example Calculation: The outcome (P, P, G) has probability (1/3) * (1/3) * (1/2) = 1/18. The outcome (P, G, S) has probability (1/3) * (1/3) * 1 = 1/9.

An event is simply a subset of the sample space S. The goal is to calculate the probability of a specific event occurring.

• The Event: For the Monty Hall problem, the event we care about is "Marilyn wins by switching." Let's call this W_switch. An outcome is in this event if the prize location is not the same as the contestant's initial pick.

The probability of an event is the sum of the probabilities of all the outcomes contained within that event.

• Calculation: The event W_switch consists of 6 distinct outcomes. Each of these outcomes can be shown to have a probability of 1/9.
• The Answer: Pr(W_switch) = 6 * (1/9) = 6/9 = 2/3.
• Conclusion: The formal analysis confirms the empirical result: it is advantageous to switch. The probability of winning by switching is 2/3, while the probability of winning by staying is 1/3.

4. Non-Transitive Dice
The lecture concludes with another counter-intuitive example: Efron's non-transitive dice.

• The Setup: A set of three dice (Red, Green, Blue) with non-standard numbers on their faces. A game is played where one player chooses a die, the second player chooses from the remaining two, and the player who rolls the higher number wins.
• The Paradox: Using the same tree-based probability analysis, it is shown that:
  • Red beats Green (with probability 5/9).
  • Green beats Blue (with probability 5/9).
  • Blue beats Red (with probability 5/9).
• Non-Transitivity: The "beats" relation is not transitive (R > G and G > B does not imply R > B). This violates our everyday intuition about ordering.
• The Weirder Paradox: The paradox is extended. What if each player rolls their chosen die twice and sums the results?
  • A more complex tree diagram shows that the winning probabilities reverse. Now, Green beats Red, Blue beats Green, and Red beats Blue.

The lecture concludes by emphasizing that for probability, intuition is an unreliable guide. A rigorous, step-by-step analysis using tools like the tree method is the only way to arrive at correct conclusions.

L19: Conditional Probability

1. Introduction: Building on the Four-Step Method
The lecture, led by instructor Brynmor Chapman, continues the unit on probability. It builds upon the tree method (or four-step method) introduced in the previous lecture and explores more complex scenarios and key theorems like Bayes' Rule.
2. Rules of Probability
The lecture begins by formalizing several fundamental rules for calculating the probabilities of events. An event is a subset of the sample space.

• Sum Rule: For disjoint events A and B, the probability of their union is the sum of their individual probabilities: Pr(A ∪ B) = Pr(A) + Pr(B).
• Complement Rule: The probability of an event not happening is Pr(¬A) = 1 - Pr(A).
• Difference Rule: Pr(A - B) = Pr(A) - Pr(A ∩ B).
• Principle of Inclusion-Exclusion (PIE): For any two events A and B (not necessarily disjoint), the probability of their union is Pr(A ∪ B) = Pr(A) + Pr(B) - Pr(A ∩ B).
• Union Bound: Pr(A ∪ B) ≤ Pr(A) + Pr(B).
• Monotonicity Rule: If A ⊆ B, then Pr(A) ≤ Pr(B).

3. Conditional Probability
The main topic of the lecture is conditional probability, which allows us to update our beliefs based on new information.

• Definition: The probability of event A occurring given that event B has occurred is defined as:
  Pr(A | B) = Pr(A ∩ B) / Pr(B)
• Intuition: This re-scales the probability space, treating the event B as the new, smaller sample space. The probability of A in this new space is the portion of A that overlaps with B.
• The Product Rule: By rearranging the definition, we get a powerful tool for calculating the probability of intersections:
  • Pr(A ∩ B) = Pr(A | B) * Pr(B)
  • This rule can be chained for multiple events: Pr(A ∩ B ∩ C) = Pr(A | B ∩ C) * Pr(B | C) * Pr(C).
• Connection to the Tree Method: The product rule provides the formal justification for the procedure used in the last lecture. The probability of an outcome (a leaf in the tree) is the product of the conditional probabilities (the edge probabilities) along the path from the root.

4. Bayes' Rule
Bayes' Rule is a fundamental theorem that allows us to "invert" conditional probabilities. It's simply a rearrangement of the product rule but has profound implications for inference and reasoning under uncertainty.

• The Rule: Pr(B | A) = (Pr(A | B) * Pr(B)) / Pr(A)
• The Odds Form: A particularly useful version of Bayes' Rule compares the posterior odds of two events (B and C) after observing some evidence A:
  Pr(B | A) / Pr(C | A) = (Pr(A | B) / Pr(A | C)) * (Pr(B) / Pr(C))
  (Posterior Odds = Likelihood Ratio * Prior Odds)
• Terminology:
  • Pr(B): The prior probability of B (our belief before seeing evidence A).
  • Pr(B | A): The posterior probability of B (our updated belief after seeing A).
  • Pr(A | B): The likelihood of observing evidence A if B were true.

5. Applications and Paradoxes of Conditional Probability
The lecture uses several examples to illustrate the power and counter-intuitive nature of conditional probability.

• Example 1: The Two Coins Problem:
  • Setup: You have a fair coin and a two-headed coin. You pick one at random, flip it, and get heads. What is the probability you picked the fair coin?
  • Analysis: Using the odds form of Bayes' Rule, the posterior odds of (Fair / Biased) are calculated. The prior odds are 1 (50/50). The likelihood ratio is Pr(Heads|Fair) / Pr(Heads|Biased) = (1/2) / 1 = 1/2.
  • Result: The posterior odds are 1/2. This means the probability of having the fair coin is 1/3. The observation of heads makes it more likely that we have the biased coin.
• Example 2: COVID Testing (Base Rate Fallacy):
  • Setup: 10% of a population has COVID. A test has a 10% false-negative rate and a 30% false-positive rate. If you test positive, what is the probability you actually have COVID?
  • Analysis: Again using Bayes' Rule, we compare Pr(Sick | Positive) to Pr(Healthy | Positive).
  • Result: The posterior probability of being sick is only 1/4 (25%).
  • The Paradox: Even with a positive result from a reasonably accurate test, you are still more likely to be healthy. This is because the prior probability (the base rate) of being sick was very low to begin with. Many people neglect the base rate and overestimate the probability, a cognitive bias known as the base rate fallacy.
• Example 3: Simpson's Paradox:
  • The Paradox: A statistical trend that appears in several different groups of data can disappear or even reverse when these groups are combined.
  • Example (Berkeley Admissions): A university was sued for gender bias because its overall admission rate for men was higher than for women. However, when looking at individual departments, the admission rate for women was consistently higher than for men in most departments.
  • The Explanation: This paradox arises from a confounding variable. The men and women were applying to different departments at different rates. Women tended to apply to more competitive departments (like CS) with low admission rates for everyone, while men tended to apply to less competitive departments (like EE) with high admission rates for everyone. This structural difference in application patterns, not departmental bias, created the misleading overall statistic.
• Example 4: The Prosecutor's Fallacy:
  • The Problem: Distinguishing between Pr(Evidence | Innocent) and Pr(Innocent | Evidence).
  • Scenario: A cake is stolen. The suspect is a known jelly-tart thief. The baker argues this makes him a more likely culprit. The suspect argues that the probability of any given jelly-tart thief also being a cake thief is still very low.
  • The Fallacy: Both parties are making claims about Pr(Cake Thief | Jelly Thief). The crucial missing piece of information is the evidence that a cake was stolen. The relevant probability is Pr(Cake Thief | Jelly Thief AND Cake was Stolen). When this new evidence is properly conditioned on, the probability of guilt can become very high, even if the prior probability was low. This illustrates the importance of correctly identifying and conditioning on all available evidence.

L20: Independence

1. Introduction: The Rules of Probability
The lecture, led by instructor Brynmor Chapman, continues the unit on probability. It builds upon the tree method (or four-step method) introduced in the previous lecture and explores more complex scenarios and key theorems like Bayes' Rule.

• Review of Basic Probability Rules: The lecture begins by formalizing several fundamental rules for calculating the probabilities of events. An event is a subset of the sample space.
  • Sum Rule: For disjoint events A and B, Pr(A ∪ B) = Pr(A) + Pr(B).
  • Complement Rule: Pr(¬A) = 1 - Pr(A).
  • Difference Rule: Pr(A - B) = Pr(A) - Pr(A ∩ B).
  • Principle of Inclusion-Exclusion (PIE): Pr(A ∪ B) = Pr(A) + Pr(B) - Pr(A ∩ B).
  • Union Bound: Pr(A ∪ B) ≤ Pr(A) + Pr(B).
  • Monotonicity Rule: If A ⊆ B, then Pr(A) ≤ Pr(B).

2. Conditional Probability and Independence
The main topic is conditional probability, which allows for updating beliefs based on new information, leading to the crucial concept of independence.

• Conditional Probability: The probability of event A occurring given that event B has occurred is defined as: Pr(A | B) = Pr(A ∩ B) / Pr(B).
• The Product Rule: By rearranging the definition, we get a powerful tool for calculating the probability of intersections: Pr(A ∩ B) = Pr(A | B) * Pr(B).
• Independence: Two events A and B are independent if knowing that B occurred does not change the probability of A occurring.
  • Definition 1: Pr(A | B) = Pr(A) (assuming Pr(B) > 0).
  • Definition 2 (Product Rule for Independent Events): An equivalent and more symmetric definition is Pr(A ∩ B) = Pr(A) * Pr(B).
• Examples:
  • Disjoint Events: Non-empty disjoint events are not independent. Knowing one occurred means the other could not have.
  • Coin Flips: The outcomes of two fair, independent coin flips are used to illustrate the concept. The event "the first coin is heads" is shown to be independent of the event "the two coins come out the same." However, if the coins are biased, these events are generally not independent.

3. Pairwise vs. Mutual Independence
The concept of independence is extended from two events to a collection of n events.

• Pairwise Independence: A set of events is pairwise independent if every pair of events in the set is independent.
• Mutual Independence: A stronger condition where for any event Eᵢ and any subset of the other events J, Eᵢ is independent of the intersection of the events in J.
  • An equivalent definition is that for any subset of events, the probability of their intersection is the product of their individual probabilities.
• Key Distinction: Pairwise independence does not imply mutual independence. An example with three coin flips is used to demonstrate this. The events A = "C1=C2", B = "C2=C3", and C = "C3=C1" are shown to be pairwise independent, but not mutually independent because Pr(C | A ∩ B) = 1 ≠ Pr(C) = 1/2.

4. The Birthday Paradox
This classic problem illustrates a surprising consequence of probability and is used as an application of the counting principles from previous lectures.

• The "Paradox": In a group of just 23 people, there is a greater than 50% chance that at least two people share the same birthday. This number is counter-intuitively small compared to the 366 people required by the pigeonhole principle to guarantee a match.
• The Analysis: The problem is solved by calculating the probability of the complement event: that no two people share a birthday.
  1. Sample Space: The set of all possible birthday assignments for n people is dⁿ, where d=365.
  2. Counting the Complement: The number of ways to assign n distinct birthdays is d * (d-1) * ... * (d-n+1).
  3. Probability: The probability of no match is the ratio of these two quantities.
  4. Approximation: This product is approximated using the inequality 1-x ≤ e⁻ˣ. The probability of no match is approximately e^(-n(n-1)/(2d)).
  5. Solving for the 50% Threshold: Setting this probability to 1/2 and solving for n shows that the number of people needed is roughly proportional to the square root of the number of days: n ≈ 1.2 * √d. For d=365, this gives n ≈ 23.

5. The Gambler's Fallacy
The lecture concludes by discussing another common cognitive bias related to probability.

• The Fallacy: The mistaken belief that if a particular random event has occurred more frequently than expected in the past, it is less likely to occur in the future (or vice versa). For example, after flipping 10 heads in a row with a fair coin, a gambler might feel that a tails is "due."
• The Probabilist's View: For a known fair and independent process, the past has no bearing on the future. The probability of the 11th flip being heads is still exactly 1/2.
• The Bayesian's View: A Bayesian observer might question the premise. Seeing 10 heads in a row provides strong evidence that the coin is not fair. They would update their prior belief about the coin's fairness and conclude that the probability of the next flip being heads is actually greater than 1/2. This is formalized using the law of total probability, conditioning on whether the coin is fair or biased.

L21: Random Variables

1. Introduction: Counting and Probability
The lecture, led by instructor Brynmor Chapman, continues the unit on probability. The main goal is to show how the counting techniques developed in the previous unit (like the Sum Rule and PIE) naturally extend from reasoning about the sizes of sets to reasoning about the probabilities of events.

• Review of Events and Probabilities:
  • An event is a subset of the sample space.
  • The probability of an event, Pr(A), is the sum of the probabilities of all outcomes within that event.
• Rules of Probability (Analogous to Counting Rules):
  • Sum Rule: For disjoint events A and B, Pr(A ∪ B) = Pr(A) + Pr(B).
  • Complement Rule: Pr(¬A) = 1 - Pr(A).
  • Difference Rule: Pr(A - B) = Pr(A) - Pr(A ∩ B).
  • Principle of Inclusion-Exclusion (PIE): Pr(A ∪ B) = Pr(A) + Pr(B) - Pr(A ∩ B).
  • Union Bound: Pr(A ∪ B) ≤ Pr(A) + Pr(B).
  • Monotonicity Rule: If A ⊆ B, then Pr(A) ≤ Pr(B).

2. Conditional Probability and Bayes' Rule
The lecture then formally introduces conditional probability, a cornerstone of probabilistic reasoning.

• Definition: The probability of event A occurring given that event B has occurred is defined as: Pr(A | B) = Pr(A ∩ B) / Pr(B).
• The Product Rule: Rearranging the definition gives a powerful tool for calculating the probability of intersections: Pr(A ∩ B) = Pr(A | B) * Pr(B). This can be chained for multiple events and provides the formal justification for multiplying probabilities along the paths of a tree diagram.
• Example (Ash vs. Gary): A problem involving a three-game series is analyzed using a tree diagram. The probability of an outcome is the product of the conditional probabilities along its path. This setup is then used to calculate Pr(Ash wins series | Ash wins first game).
• Bayes' Rule: This fundamental theorem allows for "inverting" conditional probabilities. It relates Pr(B | A) to Pr(A | B).
  Pr(B | A) = (Pr(A | B) * Pr(B)) / Pr(A)
  This is used to solve problems where it's easier to reason about Pr(Evidence | Hypothesis) but we want to find Pr(Hypothesis | Evidence).
• Applications and Paradoxes: Several examples illustrate the power and counter-intuitive nature of Bayes' Rule, including the Two Coins Problem, the COVID testing example (highlighting the base rate fallacy), Simpson's Paradox, and the Prosecutor's Fallacy. The common theme is that rigorous, step-by-step calculation is necessary to avoid being misled by flawed intuition.

3. Random Variables (RVs)
The second half of the lecture introduces the crucial concept of random variables.

• The "Naughty Word": The term "random variable" is described as a historical misnomer; an RV is neither random nor a variable.
• Definition: A random variable F is a function that maps outcomes from the sample space S to a numerical value (usually a real number). F: S → R.
• Example (Three Coin Flips):
  • F(outcome) = number of heads in the outcome.
  • G(outcome) = 1 if the first flip is heads, 0 otherwise.
• Events from RVs: An RV can be used to define events. For example, the event [F=2] is the set of all outcomes that F maps to the value 2.
• Indicator RVs: An RV that only takes values 0 or 1. There is a direct correspondence between events and indicator RVs.
• Independence of RVs: Two RVs F and G are independent if for all possible values x and y, the events [F=x] and [G=y] are independent. Knowing the value of one RV provides no information about the value of the other.

4. Distributions
Often, it is convenient to reason about a random variable without reference to the underlying sample space. This is done by studying its distribution.

• Probability Mass Function (PMF): For a discrete RV F, the PMF p_F(x) is a function that gives the probability that the RV takes on a specific value x.
  p_F(x) = Pr(F=x)
• Cumulative Distribution Function (CDF): The CDF F_F(x) gives the probability that the RV takes on a value less than or equal to x.
  F_F(x) = Pr(F ≤ x) = Σ_{y≤x} p_F(y)
• Common Distributions:
  • Bernoulli: The distribution of an indicator RV (a single trial with two outcomes).
  • Uniform: An RV where each of n outcomes is equally likely.
  • Binomial: The distribution of the number of "successes" (e.g., heads) in n independent Bernoulli trials.

5. The Binomial Distribution and Stirling's Approximation
The lecture concludes with a detailed analysis of the binomial distribution.

• The PMF: The probability of getting exactly k successes in n trials, each with success probability p, is given by:
  Pr(X=k) = (n choose k) * pᵏ * (1-p)ⁿ⁻ᵏ
• Approximating the PMF: For large n, calculating the (n choose k) term with factorials is difficult. The lecture derives a powerful approximation for the PMF using Stirling's approximation for factorials.
• The Result: The binomial PMF is well-approximated by a Gaussian-like (bell-shaped) curve. The approximation shows that the probability is maximized when k is close to np (the expected value) and decays exponentially fast as k moves away from the mean.
• Counter-intuitive Result: This exponential decay can lead to surprising results. For example, when flipping 100 fair coins, it is much more likely to get exactly 25 heads than it is to get fewer than 25 heads. This is because the probabilities in the extreme tail of the distribution are so small that their sum is less than the probability of the first point outside the tail.

L22: Expectation

1. Introduction to Expectation
The lecture, led by instructor Erik Demaine, introduces the concept of expectation, a fundamental tool in probability theory for summarizing a random variable.

• Random Variable (RV) Recap: A random variable is a function X mapping outcomes in a sample space S to a numerical value (usually a real number).
• Expectation (Definition): The expected value of a random variable X, denoted E[X], is the probability-weighted average of its possible values. It is a single number that summarizes the "center" or "average outcome" of the random process described by X.
  E[X] = Σ_{ω ∈ S} Pr(ω) * X(ω)
• Example (Fair Die): For a single roll of a fair six-sided die, the sample space is {1, 2, 3, 4, 5, 6}, and each outcome has a probability of 1/6. The expected value is (1/6)*1 + (1/6)*2 + ... + (1/6)*6 = 3.5. This illustrates that the expected value is not necessarily a value that the random variable can actually take on.

2. Alternative Formulas for Expectation
The lecture presents several equivalent, and often more convenient, formulas for calculating expectation.

• Formula 1 (Sum over Range): Instead of summing over the entire sample space, we can group outcomes by the value the RV assigns to them. This leads to a sum over the range of the random variable:
  E[X] = Σ_{x ∈ range(X)} Pr(X=x) * x
• Formula 2 (Sum over CDF for Natural Numbers): For a random variable X that takes on non-negative integer values, the expectation can be calculated by summing the tail probabilities of its cumulative distribution function (CDF):
  E[X] = Σ_{i=0 to ∞} Pr(X > i)
  This formula is often useful when Pr(X > i) is easier to compute than Pr(X = i).

3. Key Examples and Applications
Several classic probability problems are used to illustrate the calculation and application of expectation.

• Expectation of an Indicator RV: The expected value of an indicator random variable I_A for an event A is simply the probability of that event. E[I_A] = Pr(A). This is a crucial and frequently used fact.
• Mean Time to Failure (Geometric Distribution):
  • Problem: How many times do you need to flip a biased coin (with Pr(Heads) = p) until you get the first heads?
  • Analysis: Let F be the number of flips. The event [F > i] is equivalent to the event that the first i flips are all tails. The probability of this is (1-p)ⁱ.
  • Solution: Using the CDF formula, E[F] = Σ_{i=0 to ∞} Pr(F > i) = Σ (1-p)ⁱ. This is a geometric series that sums to 1 / (1 - (1-p)) = 1/p.
  • Intuition: If a success happens with probability p, you expect to wait 1/p trials for it to occur. For a fair coin (p=1/2), you expect to wait 2 flips.

4. The Power of Linearity of Expectation
This is presented as the most important and useful property of expectation.

• The Theorem: The expectation of a sum of random variables is the sum of their individual expectations.
  E[X₁ + X₂ + ... + Xₙ] = E[X₁] + E[X₂] + ... + E[Xₙ]
• The "Magic": This property holds regardless of whether the random variables are independent. This is a stark contrast to the product rule for probabilities, which requires independence. This makes linearity of expectation an incredibly powerful and versatile tool.
• The "Decomposition" Technique: The primary strategy for using linearity of expectation is to take a complex random variable X and decompose it into a sum of simpler random variables X = Σ Xᵢ, often indicator variables. Then, compute the (usually simple) expectation of each Xᵢ and sum them up.

5. Examples of Linearity of Expectation
Several problems are solved using the decomposition technique.

• Expected Number of Heads in
  • Let H be the total number of heads in n flips of a coin with Pr(Heads) = p.
  • Decompose H into a sum of n indicator variables: H = Σ_{i=1 to n} Hᵢ, where Hᵢ is the indicator that the i-th flip is heads.
  • E[H] = Σ E[Hᵢ].
  • The expectation of each indicator is E[Hᵢ] = Pr(Hᵢ=1) = p.
  • The total expectation is n * p. This holds even if the coin flips are dependent.
• Expected Number of Hearts in a 3-Card Hand:
  • Let H be the number of hearts in a 3-card hand drawn from a 52-card deck.
  • Decompose H into a sum of 13 indicator variables: H = Σ_{i=1 to 13} Hᵢ, where Hᵢ is the indicator that the i-th heart card (e.g., the Ace of Hearts) is in the hand.
  • E[H] = Σ E[Hᵢ] = 13 * E[Hᵢ].
  • E[Hᵢ] = Pr(i-th heart is in hand). This probability is 3/52.
  • The total expectation is 13 * (3/52) = 39/52 = 3/4. This is much simpler than calculating the probabilities for getting 0, 1, 2, or 3 hearts and using the direct expectation formula.
• The Hat Check Problem (Derangements):
  • Problem: n people throw their hats in a pile, and each person randomly receives one hat back. What is the expected number of people who get their own hat back?
  • Analysis: Let X be the number of people who get their own hat back.
  • Decompose X = Σ_{k=1 to n} X_k, where X_k is the indicator that person k gets their own hat back.
  • E[X] = Σ E[X_k] = n * E[X_k].
  • For any specific person k, Pr(X_k=1) is simply 1/n, as their hat is equally likely to go to any of the n people.
  • E[X] = n * (1/n) = 1.
  • The Surprising Result: The expected number of people who get their own hat back is always 1, regardless of the total number of people n.

The lecture powerfully demonstrates how linearity of expectation, combined with the technique of decomposing a complex random variable into a sum of simple (often indicator) variables, can elegantly solve problems that would be combinatorially difficult otherwise.

L23: Variance

1. Introduction to Expectation
The lecture, led by instructor Erik Demaine, introduces the concept of expectation, a fundamental tool in probability theory for summarizing a random variable.

• Random Variable (RV) Recap: A random variable is a function X mapping outcomes in a sample space S to a numerical value (usually a real number).
• Expectation (Definition): The expected value of a random variable X, denoted E[X], is the probability-weighted average of its possible values. It is a single number that summarizes the "center" or "average outcome" of the random process described by X.
  E[X] = Σ_{ω ∈ S} Pr(ω) * X(ω)
• Example (Fair Die): For a single roll of a fair six-sided die, the sample space is {1, 2, 3, 4, 5, 6}, and each outcome has a probability of 1/6. The expected value is (1/6)*1 + (1/6)*2 + ... + (1/6)*6 = 3.5. This illustrates that the expected value is not necessarily a value that the random variable can actually take on.

2. Alternative Formulas for Expectation
The lecture presents several equivalent, and often more convenient, formulas for calculating expectation.

• Formula 1 (Sum over Range): Instead of summing over the entire sample space, we can group outcomes by the value the RV assigns to them. This leads to a sum over the range of the random variable:
  E[X] = Σ_{x ∈ range(X)} Pr(X=x) * x
• Formula 2 (Sum over CDF for Natural Numbers): For a random variable X that takes on non-negative integer values, the expectation can be calculated by summing the tail probabilities of its cumulative distribution function (CDF):
  E[X] = Σ_{i=0 to ∞} Pr(X > i)
  This formula is often useful when Pr(X > i) is easier to compute than Pr(X = i).

3. Key Examples and Applications
Several classic probability problems are used to illustrate the calculation and application of expectation.

• Expectation of an Indicator RV: The expected value of an indicator random variable I_A for an event A is simply the probability of that event. E[I_A] = Pr(A). This is a crucial and frequently used fact.
• Mean Time to Failure (Geometric Distribution):
  • Problem: How many times do you need to flip a biased coin (with Pr(Heads) = p) until you get the first heads?
  • Analysis: Let F be the number of flips. The event [F > i] is equivalent to the event that the first i flips are all tails. The probability of this is (1-p)ⁱ.
  • Solution: Using the CDF formula, E[F] = Σ_{i=0 to ∞} Pr(F > i) = Σ (1-p)ⁱ. This is a geometric series that sums to 1 / (1 - (1-p)) = 1/p.
  • Intuition: If a success happens with probability p, you expect to wait 1/p trials for it to occur. For a fair coin (p=1/2), you expect to wait 2 flips.

4. The Power of Linearity of Expectation
This is presented as the most important and useful property of expectation.

• The Theorem: The expectation of a sum of random variables is the sum of their individual expectations.
  E[X₁ + X₂ + ... + Xₙ] = E[X₁] + E[X₂] + ... + E[Xₙ]
• The "Magic": This property holds regardless of whether the random variables are independent. This is a stark contrast to the product rule for probabilities, which requires independence. This makes linearity of expectation an incredibly powerful and versatile tool.
• The "Decomposition" Technique: The primary strategy for using linearity of expectation is to take a complex random variable X and decompose it into a sum of simpler random variables X = Σ Xᵢ, often indicator variables. Then, compute the (usually simple) expectation of each Xᵢ and sum them up.

5. Examples of Linearity of Expectation
Several problems are solved using the decomposition technique.

• Expected Number of Heads in
  • Let H be the total number of heads in n flips of a coin with Pr(Heads) = p.
  • Decompose H into a sum of n indicator variables: H = Σ_{i=1 to n} Hᵢ, where Hᵢ is the indicator that the i-th flip is heads.
  • E[H] = Σ E[Hᵢ].
  • The expectation of each indicator is E[Hᵢ] = Pr(Hᵢ=1) = p.
  • The total expectation is n * p. This holds even if the coin flips are dependent.
• Expected Number of Hearts in a 3-Card Hand:
  • Let H be the number of hearts in a 3-card hand drawn from a 52-card deck.
  • Decompose H into a sum of 13 indicator variables: H = Σ_{i=1 to 13} Hᵢ, where Hᵢ is the indicator that the i-th heart card (e.g., the Ace of Hearts) is in the hand.
  • E[H] = Σ E[Hᵢ] = 13 * E[Hᵢ].
  • E[Hᵢ] = Pr(i-th heart is in hand). This probability is 3/52.
  • The total expectation is 13 * (3/52) = 39/52 = 3/4. This is much simpler than calculating the probabilities for getting 0, 1, 2, or 3 hearts and using the direct expectation formula.
• The Hat Check Problem (Derangements):
  • Problem: n people throw their hats in a pile, and each person randomly receives one hat back. What is the expected number of people who get their own hat back?
  • Analysis: Let X be the number of people who get their own hat back.
  • Decompose X = Σ_{k=1 to n} X_k, where X_k is the indicator that person k gets their own hat back.
  • E[X] = Σ E[X_k] = n * E[X_k].
  • For any specific person k, Pr(X_k=1) is simply 1/n, as their hat is equally likely to go to any of the n people.
  • E[X] = n * (1/n) = 1.
  • The Surprising Result: The expected number of people who get their own hat back is always 1, regardless of the total number of people n.

The lecture powerfully demonstrates how linearity of expectation, combined with the technique of decomposing a complex random variable into a sum of simple (often indicator) variables, can elegantly solve problems that would be combinatorially difficult otherwise.

L24: Large Deviations and Bounds

1. Introduction: Tail Bounds
The final lecture of the course, led by instructor Brynmor Chapman, focuses on tail bounds. While expectation and variance provide one- or two-number summaries of a random variable, tail bounds answer a more practical question: What is the probability that a random variable deviates significantly from its expected value?

• Review of Variance:
  • Var(R) = E[(R - E[R])²] = E[R²] - (E[R])²
  • Linearity of Variance: For pairwise independent random variables R₁...Rₙ, the variance of their sum is the sum of their variances: Var(ΣRᵢ) = ΣVar(Rᵢ).

2. Markov's Inequality
Markov's Inequality provides a simple, fundamental upper bound on the probability of a random variable being large.

• The Inequality: For a non-negative random variable R and any x > 0:
  Pr(R ≥ x) ≤ E[R] / x
• Intuition: A random variable cannot be "too large, too often," because that would pull its average (expectation) up. The total probability mass in the tail is constrained by the expectation.
• Proof: The proof uses the law of total expectation, conditioning on the event [R ≥ x].
  E[R] = E[R | R ≥ x] * Pr(R ≥ x) + E[R | R < x] * Pr(R < x)
  Since R is non-negative, E[R | R ≥ x] ≥ x and E[R | R < x] ≥ 0. Dropping the second term and rearranging the inequality gives the result.
• Improving the Bound: Markov's bound is often loose. A key technique to tighten it is to shift and flip the random variable. For example, to bound Pr(R ≤ 65) for a variable with E[R] = 75 and range [30, 100], one can define a new non-negative variable S = 100 - R and apply Markov's inequality to Pr(S ≥ 35).
• Tightness: An example (the "Lazy Susan" hat check problem) shows that Markov's inequality can be tight; there exist distributions for which the inequality becomes an equality. This means it is the best possible bound given only the expectation and non-negativity.

3. Chebyshev's Inequality
Chebyshev's Inequality provides a stronger tail bound by incorporating information about the variance of the random variable.

• The Inequality: For any random variable R (not necessarily non-negative) and any x > 0:
  Pr(|R - E[R]| ≥ x) ≤ Var(R) / x²
• Intuition: If a random variable has low variance, it is less likely to be found far from its mean. The probability of deviating by x decreases quadratically with x.
• Proof: The proof is a clever application of Markov's inequality.
  1. Define a new, non-negative random variable R' = (R - E[R])².
  2. The event [|R - E[R]| ≥ x] is the same as the event [R' ≥ x²].
  3. Apply Markov's inequality to R': Pr(R' ≥ x²) ≤ E[R'] / x².
  4. By definition, E[R'] = E[(R - E[R])²] = Var(R).
  5. Substituting this in gives Chebyshev's inequality.
• Comparison: Applying Chebyshev's inequality to the problem of flipping n fair coins (Pr(Heads ≥ 3n/4)) gives a bound of 4/n, which is much stronger than the constant bound of 2/3 given by Markov's inequality.

4. Chernoff Bounds
Chernoff bounds provide even stronger, exponentially decreasing tail bounds, but they require a stronger assumption: the random variable must be a sum of mutually independent random variables.

• The Inequality (a simplified version): For a sum of independent, bounded random variables T = ΣTᵢ, and any c ≥ 1:
  Pr(T ≥ c * E[T]) ≤ e^(-Ω(E[T])) (The exact exponent is more complex but shows exponential decay in the expectation).
• Proof Sketch (The "Exponentiation Trick"):
  1. The core idea is to apply Markov's inequality not to T itself, but to an exponentiated version, e^(sT), for some carefully chosen s > 0.
  2. Pr(T ≥ x) = Pr(e^(sT) ≥ e^(sx)).
  3. Applying Markov's gives Pr(e^(sT) ≥ e^(sx)) ≤ E[e^(sT)] / e^(sx).
  4. Because the Tᵢ are mutually independent, the expectation of the product E[e^(sΣTᵢ)] becomes a product of expectations Π E[e^(sTᵢ)].
  5. This product can be bounded, and then one can optimize over the free parameter s to find the tightest possible bound.
• Comparison: Applying a Chernoff bound to the coin flipping problem gives a bound of e^(-Ω(n)). This is exponentially stronger than the 1/n bound from Chebyshev's and the constant bound from Markov's.

5. Course Wrap-up and Farewell
The lecture concludes with a final summary and a farewell from the instructors.

• Hierarchy of Bounds: The lecture presents a clear hierarchy of tail bounds, each requiring progressively stronger assumptions to yield progressively tighter results:
  • Markov: Weakest bound, requires only non-negativity and the mean.
  • Chebyshev: Stronger (polynomial decay), requires mean and variance.
  • Chernoff: Strongest (exponential decay), requires the variable to be a sum of mutually independent variables.
• Final Thanks: The instructors thank the students for their engagement throughout the semester, highlighting the contributions of the TAs.

This final lecture provides students with a powerful toolkit for analyzing the probabilistic behavior of algorithms and systems, capping off the course's journey from logic and proofs to the uncertainties of the real world.