# Lecture 8: Tail Bounds

Source: https://www.youtube.com/watch?v=HC54KcgvReg
Recap page: https://rapidrecap.app/video/HC54KcgvReg
Generated: 2025-12-17T16:37:56.2+00:00

---
## Quick Overview

The lecture introduces tail bounds, starting with Markov's inequality for non-negative random variables and progressing to Chebyshev's bound, which uses variance to achieve tighter bounds, culminating in the introduction of the Weak Law of Large Numbers proven via Chebyshev's inequality and setting the stage for the exponentially tighter Chernoff bound.

**Key Points:**
- Markov's inequality states that for a non-negative random variable X, the probability P(X >= C) is bounded by E[X] / C.
- The proof of Markov's inequality critically relies on X being non-negative, as demonstrated by the counterexample using X = 1 (prob 0.5) and X = -1 (prob 0.5) when E[X] = 0.
- Chebyshev's bound applies to any random variable X, bounding the probability of deviation from the expectation: P(|X - E[X]| >= C) <= Var(X) / C^2.
- Chebyshev's proof involves defining a new non-negative random variable Y = (X - E[X])^2 and applying Markov's inequality to Y.
- The Weak Law of Large Numbers, proven using Chebyshev's bound, asserts that the empirical average Sn of n independent and identically distributed variables converges in probability to the true expectation C, requiring only pairwise independence.
- The Chernoff bound is introduced as a significantly more powerful tool that uses mutual independence to provide an exponential rate of convergence, P(X - mu >= delta) <= 2 * e^(-mu * delta^2 / 3), contrasting with the polynomial rates of Markov and Chebyshev.
- The lecture connects tail bounds to the probabilistic method, showing how they justify the existence of certain combinatorial structures like monochromatic arithmetic progressions (Van der Waerden's theorem) and improve randomized algorithm success probability.

**Context:** Ankur Moitra continues the probability unit by introducing 'tail bounds,' tools designed to quantify how likely it is for a random variable to be far away from its expected value, contrasting this with prior topics like expectation and variance which only describe the average behavior. The discussion establishes a progression of bounds, starting simply and incorporating more information about the random variable (like variance and independence) to achieve tighter probabilistic guarantees.

## Detailed Analysis

The lecture begins by establishing Markov's inequality, which provides a basic tail bound P(X >= C) <= E[X] / C, provided X is non-negative; the proof relies on partitioning the expectation according to the event X >= C and using the law of total expectation. Next, Chebyshev's bound is derived, which applies to any random variable X and bounds the deviation from the mean: P(|X - E[X]| >= C) <= Var(X) / C^2. The proof cleverly constructs a non-negative random variable Y = (X - E[X])^2 and applies Markov's inequality to Y. A corollary relates deviation to standard deviation sigma(X): P(|X - E[X]| >= C * sigma(X)) <= 1 / C^2. Using Chebyshev's bound, the speaker proves the Weak Law of Large Numbers, showing that the average Sn of n independent, identically distributed variables converges to the expectation E[X], noting that the proof only required pairwise independence. This is immediately applied to the concept of polling accuracy and the 'gambler's ruin,' where negative expected value games lead to eventual bankruptcy because the average winnings per round converges to a negative number. Finally, the lecture motivates the need for stronger tools by showing that applying Chebyshev to randomized primality testing yields impractically large sample sizes (N proportional to 1/epsilon), leading to the introduction of the Chernoff bound, which leverages mutual independence to achieve an exponential decay rate in the failure probability.

### Review of Prerequisites

- Sample space, events, independence, random variables, expectation, variance, conditioning, and inclusion-exclusion
- Counting methods and generating functions were covered previously.

### Markov's Inequality

- Assumes X is non-negative
- P(X >= C) <= E[X] / C
- Proof uses the law of total expectation broken at C, requiring X >= 0 to drop the non-negativity term.

### Chebyshev's Bound Derivation

- Applies to any random variable X
- P(
- X - E[X]
- >= C) <= Var(X) / C^2
- Proof involves squaring the deviation to create a non-negative variable Y and applying Markov's inequality to Y.

### Weak Law of Large Numbers Proof

- Sn = (1/n) * sum(xi) has E[Sn] = C and Var(Sn) = Var(X) / n
- Chebyshev's bound yields P(
- Sn - C
- >= epsilon) <= (Var(X) / n) / epsilon^2, showing convergence as n increases.

### Gambler's Ruin Application

- Playing games with negative expected value (like craps with house edge 0.0141) leads to eventual bankruptcy because the average winning per round converges to a negative value.

### Algorithmic Motivation for Stronger Bounds

- Using Chebyshev for randomized primality testing suggests N must be exponentially large relative to the desired failure probability (e.g., 1/N bound), which is too slow for cryptographic security.

### Chernoff Bound Introduction

- Requires mutual independence of Bernoulli random variables
- P(X - mu >= delta) is bounded by an exponential term, 2 * e^(-mu * delta^2 / 3)
- This exponential rate allows for practical repetition counts (N proportional to log(1/failure)).

### Probabilistic Method and Ramsey Theory

- The probabilistic method proves existence by showing a random object succeeds
- Van der Waerden's theorem states any large enough two-coloring of integers must contain a monochromatic k-term arithmetic progression.