Moment-Generating Functions
The moment-generating function (MGF) of a random variable \(X\) is defined as:
\[M_X(t) = \mathbb{E}[e^{tX}]\]when this expectation exists for \(t\) in a neighborhood of 0.
Why MGFs?
The MGF is the key tool behind the Chernoff bound. The idea is to transform the event \(\{X \geq a\}\) into \(\{e^{tX} \geq e^{ta}\}\) for a parameter \(t > 0\), then apply Markov's inequality to the non-negative random variable \(e^{tX}\).
Key Properties
- If \(X_1, \ldots, X_n\) are independent, then \(M_{X_1 + \cdots + X_n}(t) = \prod_{i=1}^{n} M_{X_i}(t)\)
- For \(X \sim \text{Bern}(p)\): \(M_X(t) = 1 - p + pe^t = 1 + p(e^t - 1)\)
- The \(k\)-th moment can be recovered: \(\mathbb{E}[X^k] = M_X^{(k)}(0)\)
Quick Check
If \(X\) and \(Y\) are independent, what is \(M_{X+Y}(t)\)?
Exponential & Logarithm Properties
The Crucial Inequality: \(\ln(1+x) \leq x\)
This is arguably the single most important inequality in the Chernoff proof. It follows from the concavity of \(\ln\): the tangent line at \(x=0\) (which is \(y = x\)) lies above the curve.
Equivalently: \(1 + x \leq e^x\) for all \(x \in \mathbb{R}\).
Quick Check
Which is true for all \(x > -1\)?
Series & Convergence
Geometric Series
For \(|r| < 1\):
\[\sum_{k=0}^{\infty} r^k = \frac{1}{1-r}\]This is used extensively in algorithm analysis (e.g., bounding the expected number of geometric repetitions).
Exponential Series
\[e^x = \sum_{k=0}^{\infty} \frac{x^k}{k!}\]Used when computing MGFs and Poisson probabilities. Converges for all \(x \in \mathbb{R}\).
Taylor Expansion of \(\ln(1+\gamma)\)
\[\ln(1+\gamma) = \gamma - \frac{\gamma^2}{2} + \frac{\gamma^3}{3} - \cdots = \sum_{k=1}^{\infty} \frac{(-1)^{k+1} \gamma^k}{k}\]The expansion \((1+\gamma)\ln(1+\gamma) - \gamma = \frac{\gamma^2}{2} - O(\gamma^3)\) shows the quadratic dependence that appears in the Chernoff exponent.
Quick Check
What is \(\sum_{k=0}^{\infty} (3/16)^k\)?
Poisson Distribution
If \(X \sim \text{Poisson}(\lambda)\), then for integer \(k \geq 0\):
\[\Pr[X = k] = \frac{e^{-\lambda} \lambda^k}{k!}\]Key facts: \(\mathbb{E}[X] = \lambda\), \(\operatorname{Var}[X] = \lambda\).
Poisson limit theorem: If \(X \sim \text{Bin}(n, p)\) and \(n \to \infty\) with \(np \to \lambda\), then \(X\) converges in distribution to \(\text{Poisson}(\lambda)\).
Quick Check
If \(X \sim \text{Poisson}(5)\), what is \(\operatorname{Var}[X]\)?
Geometric Distribution
The geometric distribution models the number of independent trials until the first success. If each trial succeeds with probability \(p\):
\[\Pr[K = k] = (1-p)^{k-1} p, \quad k = 1, 2, 3, \ldots\]\(\mathbb{E}[K] = \frac{1}{p}\), \(\operatorname{Var}[K] = \frac{1-p}{p^2}\).
This appears directly in the MC → LV conversion: the number of repetitions until success is geometric.
Tail-Sum Formula
For non-negative integer-valued \(K\):
\[\mathbb{E}[K] = \sum_{k=1}^{\infty} \Pr[K \geq k]\]For geometric \(K\) with parameter \(p\):
\[\mathbb{E}[K] = \sum_{k=1}^{\infty} (1-p)^{k-1} = \frac{1}{p}\]Markov's Inequality: Deep Dive
Statement
For non-negative \(X\) with \(\mathbb{E}[X] < \infty\) and \(t > 0\):
\[\Pr[X \geq t] \leq \frac{\mathbb{E}[X]}{t}\]Proof (indicator method)
Note that \(t \cdot \mathbf{1}[X \geq t] \leq X\) pointwise (since \(X \geq 0\)). Taking expectations:
\[t \cdot \Pr[X \geq t] = t \cdot \mathbb{E}[\mathbf{1}[X \geq t]] = \mathbb{E}[t \cdot \mathbf{1}[X \geq t]] \leq \mathbb{E}[X]\]When is Markov tight?
Markov is tight for random variables that place all their mass at 0 and some value \(a > 0\). For example, \(\Pr[X = a] = 1/a\) and \(\Pr[X = 0] = 1 - 1/a\) gives \(\mathbb{E}[X] = 1\) and \(\Pr[X \geq a] = 1/a = \mathbb{E}[X]/a\).
The "First Moment Method"
Markov's inequality is sometimes called the first moment method because it only uses the first moment (\(\mathbb{E}[X]\)). Chebyshev uses the second moment (variance), and the Chernoff/MGF approach uses all moments.
Quick Check
If \(X \geq 0\) and \(\mathbb{E}[X] = 50\), what does Markov tell us about \(\Pr[X \geq 200]\)?
Chebyshev's Inequality: Deep Dive
Statement
\[\Pr[|X - \mathbb{E}[X]| \geq t] \leq \frac{\operatorname{Var}[X]}{t^2}\]Derivation from Markov
Apply Markov to \(Y = (X - \mathbb{E}[X])^2 \geq 0\):
\[\Pr[|X - \mu| \geq t] = \Pr[Y \geq t^2] \leq \frac{\mathbb{E}[Y]}{t^2} = \frac{\operatorname{Var}[X]}{t^2}\]Standard Deviation Interpretation
Setting \(t = k\sigma\) where \(\sigma = \sqrt{\operatorname{Var}[X]}\):
\[\Pr[|X - \mu| \geq k\sigma] \leq \frac{1}{k^2}\]- \(k = 2\): at most 25% probability
- \(k = 3\): at most 11.1% probability
- \(k = 10\): at most 1% probability
Pairwise Independence Suffices
Chebyshev only uses \(\operatorname{Var}[X]\). For \(X = \sum X_i\), we need \(\operatorname{Var}[\sum X_i] = \sum \operatorname{Var}[X_i]\), which holds under pairwise independence (not full independence). This is strictly weaker than what Chernoff requires.
Quick Check
What is the minimum independence assumption for Chebyshev?
Chernoff Bound: Full Proof
We prove: for \(X_1, \ldots, X_n\) i.i.d. \(\text{Bern}(p)\), \(X = \sum X_i\), and \(\gamma \in (0,1]\):
\[\Pr[X > (1+\gamma)\mathbb{E}[X]] \leq e^{-\gamma^2 \mathbb{E}[X] / 3}\]Step 1: Exponential Transform
For any \(t > 0\), since \(x \mapsto e^{tx}\) is increasing:
\[\Pr[X > (1+\gamma)\mu] = \Pr[e^{tX} > e^{t(1+\gamma)\mu}]\]Step 2: Markov's Inequality
\[\Pr[e^{tX} > e^{t(1+\gamma)\mu}] \leq \frac{\mathbb{E}[e^{tX}]}{e^{t(1+\gamma)\mu}}\]Step 3: Independence + MGF
\[\mathbb{E}[e^{tX}] = \mathbb{E}\left[\prod_{i=1}^n e^{tX_i}\right] = \prod_{i=1}^n \mathbb{E}[e^{tX_i}] = \left(\mathbb{E}[e^{tX_1}]\right)^n\]For \(X_1 \sim \text{Bern}(p)\):
\[\mathbb{E}[e^{tX_1}] = (1-p) \cdot 1 + p \cdot e^t = 1 + p(e^t - 1)\]Step 4: Apply \(\ln(1+x) \leq x\)
\[\frac{(1 + p(e^t-1))^n}{e^{t(1+\gamma)np}} = \frac{e^{n\ln(1+p(e^t-1))}}{e^{t(1+\gamma)np}} \leq \frac{e^{np(e^t-1)}}{e^{t(1+\gamma)np}} = e^{-np \cdot f(t)}\]where \(f(t) = (1+\gamma)t - (e^t - 1)\).
Step 5: Optimize over \(t\)
Since the bound holds for any \(t > 0\), we pick the best one. Differentiate:
\[f'(t) = (1+\gamma) - e^t = 0 \implies t^* = \ln(1+\gamma)\]Substituting:
\[f(t^*) = (1+\gamma)\ln(1+\gamma) - \gamma\]Step 6: Final Simplification
One can verify (by Taylor expansion or calculus) that for \(\gamma \in (0,1]\):
\[(1+\gamma)\ln(1+\gamma) - \gamma \geq \frac{\gamma^2}{3}\]Therefore:
\[\Pr[X > (1+\gamma)\mu] \leq e^{-np \cdot \gamma^2/3} = e^{-\gamma^2 \mu / 3} \quad \square\]Hoeffding Bound: Details
General Form
For independent \(X_i \in [a_i, b_i]\):
\[\Pr\!\left[\sum X_i - \sum \mathbb{E}[X_i] \geq t\right] \leq \exp\!\left(-\frac{2t^2}{\sum_{i=1}^n (b_i - a_i)^2}\right)\]i.i.d. Simplified Form
For i.i.d. \(X_i \in [0,1]\) with mean \(\mu\):
\[\Pr\!\left[\left|\frac{1}{n}\sum_{i=1}^n X_i - \mu\right| > \varepsilon\right] \leq 2\exp(-2\varepsilon^2 n)\]This is an additive bound: the deviation is measured as an absolute quantity \(\varepsilon\), not relative to \(\mu\).
Chernoff vs Hoeffding
- Chernoff (multiplicative): bound is \(e^{-\delta^2 P/3}\) where \(P = n\mu\). Better when \(\mu \ll 1\) (sparse regime).
- Hoeffding (additive): bound is \(e^{-2\varepsilon^2 n}\). Better when \(\mu\) is moderate and you want additive guarantees.
Quick Check
When is the Chernoff bound preferable to Hoeffding?
Calculus Optimization in Proofs
The "Free Parameter" Technique
In the Chernoff proof, we derive a bound valid for any \(t > 0\). Since every choice of \(t\) gives a valid upper bound, we optimize to find the tightest one:
- Write the bound as \(e^{-np \cdot f(t)}\)
- To minimize the bound, maximize \(f(t)\)
- Set \(f'(t) = 0\) and verify it's a maximum
- Substitute back to get the final expression
This is a standard technique that appears throughout the analysis of randomized algorithms.
Key Analytic Inequalities
Math quiz
Chapter math quizzes are in the Quiz Hub. Filter by this chapter and choose Study / Math / All.