Lecture 8: Tail Bounds

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.