COMPX270 — Randomised and Advanced Algorithms
Chapter 11: Learning and Testing Probability Distributions
How many samples do you need to learn an unknown distribution, or test whether it has a certain property? Total variation distance, the Pearson-Neyman lemma, collision-based uniformity testing, and optimal sample complexities.
Total variation, birthday paradox, chi-squared divergence, Hoeffding and Chebyshev bounds
Problem Setup
The Distribution Learning/Testing Framework
We receive \(n\) i.i.d. samples \(x_1, x_2, \ldots, x_n \sim p\) drawn from an unknown distribution \(p\) over a discrete domain \(\mathcal{X}\) of size \(k = |\mathcal{X}|\).
The central question: how many samples \(n = n(k, \varepsilon, \delta)\) do we need to learn or test properties of \(p\)?
Two Fundamental Tasks
Learning (Estimation)
Output a distribution \(\hat{p}\) such that \(d_{TV}(p, \hat{p}) \leq \varepsilon\) with probability \(\geq 1 - \delta\).
Testing (Hypothesis Testing)
Given a reference distribution \(q\), decide whether \(p = q\) vs \(d_{TV}(p, q) \geq \varepsilon\) with probability \(\geq 1 - \delta\).
Total Variation Distance
Definition: Total Variation Distance
For distributions \(p, q\) over \(\mathcal{X}\):
\[d_{TV}(p, q) = \sup_{S \subseteq \mathcal{X}} \big(p(S) - q(S)\big) = \frac{1}{2} \|p - q\|_1 = \frac{1}{2} \sum_{x \in \mathcal{X}} |p(x) - q(x)|\]Key Properties of \(d_{TV}\)
- Metric: \(d_{TV}(p,q) = 0 \iff p = q\), symmetric, satisfies the triangle inequality.
- Bounded: \(0 \leq d_{TV}(p,q) \leq 1\). Equals 1 iff \(p\) and \(q\) have disjoint supports.
- Operational meaning: the maximum difference in probability that \(p\) and \(q\) assign to any event \(S\).
- Coupling interpretation: \(d_{TV}(p,q) = \min_{\text{couplings}} \Pr[X \neq Y]\) where \(X \sim p, Y \sim q\).
Scheffé’s Lemma
The supremum in \(d_{TV}\) is achieved by the Scheffé set:
\[S^* = \{x \in \mathcal{X} : p(x) > q(x)\}\]and we have:
\[d_{TV}(p,q) = p(S^*) - q(S^*) = \frac{1}{2}\sum_{x \in \mathcal{X}} |p(x) - q(x)|\]Interactive: Total Variation Distance Visualizer
Compare two distributions over \(k=8\) elements. Distribution \(p\) (blue) is fixed. Drag the orange bars to change \(q\) — bars auto-normalize to sum to 1.
For any \(S \subseteq \mathcal{X}\):
\[p(S) - q(S) = \sum_{x \in S} (p(x) - q(x)) \leq \sum_{x \in S} (p(x) - q(x))^+ \leq \sum_{x \in \mathcal{X}} (p(x) - q(x))^+\]where \(a^+ = \max(a, 0)\). The last sum equals \(\sum_{x \in S^*}(p(x) - q(x))\), which is achieved by choosing \(S = S^*\).
Now note that \(\sum_x p(x) = \sum_x q(x) = 1\), so \(\sum_x (p(x) - q(x)) = 0\). Therefore the positive parts sum to the same as the absolute values of the negative parts:
\[\sum_{x: p(x) > q(x)} (p(x) - q(x)) = \sum_{x: q(x) > p(x)} (q(x) - p(x)) = \frac{1}{2}\sum_x |p(x) - q(x)|\]This gives \(d_{TV}(p,q) = \frac{1}{2}\|p - q\|_1\). \(\square\)
Data Processing Inequality
Theorem (Data Processing Inequality for \(d_{TV}\))
For any (possibly randomised) function \(f\) and distributions \(p, q\):
\[d_{TV}(f(p), f(q)) \leq d_{TV}(p, q)\]In words: post-processing cannot increase total variation distance.
For any event \(T\) in the range of \(f\), define \(S = f^{-1}(T) = \{x : f(x) \in T\}\). Then:
\[f(p)(T) - f(q)(T) = p(S) - q(S) \leq d_{TV}(p, q)\]Taking the supremum over all \(T\) gives \(d_{TV}(f(p), f(q)) \leq d_{TV}(p,q)\). \(\square\)
Intuition & Importance
If two distributions are “close” (small TV distance), then no algorithm (any post-processing of samples) can tell them apart easily. This is fundamental to proving lower bounds on sample complexity: if you can’t distinguish \(p\) from \(q\) with few samples, no further computation helps.
Pearson-Neyman Lemma
Hypothesis Testing Framework
Given a single sample \(x\), decide between:
- \(H_0\) (null): \(x \sim p\)
- \(H_1\) (alternative): \(x \sim q\)
Any test \(\phi : \mathcal{X} \to \{0, 1\}\) (reject \(H_0\) if \(\phi(x) = 1\)) has two error types:
- Type I (false positive): \(\alpha = \Pr_{x \sim p}[\phi(x) = 1]\) — reject \(H_0\) when \(H_0\) is true.
- Type II (false negative): \(\beta = \Pr_{x \sim q}[\phi(x) = 0]\) — accept \(H_0\) when \(H_1\) is true.
Pearson-Neyman Lemma
For any test \(\phi\):
\[\alpha + \beta \geq 1 - d_{TV}(p, q)\]Equivalently, the total success probability \((1 - \alpha) + (1 - \beta) \leq 1 + d_{TV}(p,q)\). The optimal test uses the Scheffé set:
\[\phi^*(x) = \begin{cases} 1 & \text{if } q(x) > p(x) \\ 0 & \text{otherwise} \end{cases}\]This test achieves \(\alpha + \beta = 1 - d_{TV}(p,q)\).
Let \(S = \{x : \phi(x) = 1\}\) be the rejection region. Then:
\[\alpha + \beta = p(S) + q(\overline{S}) = p(S) + 1 - q(S) = 1 + (p(S) - q(S)) \geq 1 - d_{TV}(p,q)\]The last inequality holds because \(p(S) - q(S) \geq -d_{TV}(p,q)\) by definition. Equality is achieved when \(S = S^* = \{x : q(x) > p(x)\}\), giving:
\[\alpha^* + \beta^* = 1 + (p(S^*) - q(S^*)) = 1 - d_{TV}(p,q)\]since \(q(S^*) - p(S^*) = d_{TV}(p,q)\). \(\square\)
Alice-Bob Game Interpretation
Alice draws \(x\) from either \(p\) or \(q\) (each with probability \(1/2\)). Bob must guess which distribution. His optimal strategy:
- Guess \(q\) if \(q(x) > p(x)\), otherwise guess \(p\).
- Bob’s winning probability: \(\frac{1}{2} + \frac{d_{TV}(p,q)}{2}\).
When \(d_{TV}(p,q) = 0\): Bob can do no better than random guessing (\(1/2\)). When \(d_{TV}(p,q) = 1\): Bob can always tell them apart (probability 1).
Learning a Coin (\(k = 2\))
Setup
A coin has unknown bias \(\theta \in [0, 1]\). We observe \(n\) flips \(x_1, \ldots, x_n \sim \text{Bernoulli}(\theta)\). Goal: estimate \(\theta\) to within \(\pm \varepsilon\) with probability \(\geq 1 - \delta\).
Theorem: Sample Complexity for Coin Learning
The empirical mean \(\hat{\theta} = \frac{1}{n}\sum_{i=1}^n x_i\) satisfies:
\[\Pr\!\left[|\hat{\theta} - \theta| > \varepsilon\right] \leq 2\exp(-2n\varepsilon^2)\]by Hoeffding’s inequality. Setting the RHS \(\leq \delta\):
\[n = O\!\left(\frac{1}{\varepsilon^2} \cdot \log\frac{1}{\delta}\right)\]By Hoeffding: \(\Pr[|\hat{\theta} - \theta| > \varepsilon] \leq 2e^{-2n\varepsilon^2}\). Setting \(2e^{-2n\varepsilon^2} \leq \delta\):
\[n \geq \frac{1}{2\varepsilon^2}\ln\frac{2}{\delta} = O\!\left(\frac{\log(1/\delta)}{\varepsilon^2}\right) \quad \square\]Corollary 50.1: Known Lower Bound on Bias
If we know \(p \leq q\) (i.e., bias is bounded below by some known \(q\)), the sample complexity improves:
\[n = O\!\left(\frac{q}{\varepsilon^2} \cdot \log\frac{1}{\delta}\right)\]This is because the variance of the Bernoulli is \(\theta(1-\theta) \leq q\), allowing tighter Chebyshev-based analysis.
Learning Distributions
The Task
Given i.i.d. samples from unknown \(p\) over \(\mathcal{X}\) with \(|\mathcal{X}| = k\), output \(\hat{p}\) such that \(d_{TV}(p, \hat{p}) \leq \varepsilon\) with probability \(\geq 1 - \delta\).
The natural estimator: the empirical distribution \(\hat{p}(x) = n_x / n\) where \(n_x = |\{i : x_i = x\}|\).
Optimal Sample Complexity for Learning
\[n = O\!\left(\frac{k + \log(1/\delta)}{\varepsilon^2}\right)\]This is tight up to constants. The empirical distribution achieves this.
Suboptimal Approaches
Approach 1: Union Bound
Learn each \(p(x)\) to within \(\varepsilon / k\), then union bound over all \(x\). Gives:
\(n = O\!\left(\frac{k^2}{\varepsilon^2} \cdot \log\frac{k}{\delta}\right)\)
Suboptimal: extra factor of \(k\)!
Approach 2: Multiplicative
Learn each \(p(x)\) to within multiplicative \((1 \pm \varepsilon)\). Gives:
\(n = O\!\left(\frac{k}{\varepsilon^3} \cdot \log\frac{k}{\delta}\right)\)
Suboptimal: extra \(1/\varepsilon\) factor!
Uniformity Testing
The Problem
Given samples from \(p\), decide:
- \(H_0\): \(p = u_k\) (uniform over \(k\) elements)
- \(H_1\): \(d_{TV}(p, u_k) \geq \varepsilon\)
with success probability \(\geq 1 - \delta\).
Theorem: Optimal Uniformity Testing
The sample complexity of uniformity testing is:
\[n = \Theta\!\left(\frac{\sqrt{k}}{\varepsilon^2}\right)\]This is sublinear in \(k\)! We need far fewer samples than the domain size.
Birthday Paradox Connection
Why \(\sqrt{k}\)? If \(p = u_k\), the expected number of collisions (pairs of identical samples) in \(n\) samples is:
\[\mathbb{E}[\text{collisions}] = \binom{n}{2} \cdot \frac{1}{k} \approx \frac{n^2}{2k}\]When \(n = \Theta(\sqrt{k})\), we see \(\Theta(1)\) collisions under uniformity. If \(p \neq u_k\), the collision rate changes detectably — heavier elements contribute more collisions.
Algorithm 23: Collision-Based Uniformity Tester
Input: \(n\) i.i.d. samples from \(p\), parameters \(\varepsilon, k\)
- Draw \(n = \Theta(\sqrt{k}/\varepsilon^2)\) i.i.d. samples from \(p\).
- Compute \(Z = \) number of collisions = \(|\{(i,j) : i < j, x_i = x_j\}|\).
- Set threshold \(\tau = \binom{n}{2} \cdot \frac{1 + 2\varepsilon^2}{k}\).
- If \(Z > \tau\): reject \(H_0\) (not uniform). Otherwise: accept.
Why Collisions Work
The expected number of collisions is related to \(\|p\|_2^2 = \sum_x p(x)^2\):
\[\mathbb{E}[Z] = \binom{n}{2} \sum_{x} p(x)^2 = \binom{n}{2} \|p\|_2^2\]- Under \(H_0\): \(\|u_k\|_2^2 = 1/k\), so \(\mathbb{E}[Z] = \binom{n}{2}/k\).
- Under \(H_1\): By convexity, if \(d_{TV}(p, u_k) \geq \varepsilon\), then \(\|p\|_2^2 \geq \frac{1 + 4\varepsilon^2}{k}\) (approximately).
The gap in \(\mathbb{E}[Z]\) between \(H_0\) and \(H_1\) is detectable with \(n = \Theta(\sqrt{k}/\varepsilon^2)\) samples.
Interactive: Uniformity Testing Simulator
Generate samples from a distribution over \(k\) elements and run the collision-based tester. Compare uniform vs non-uniform distributions.
Identity Testing
The Problem
Given a known reference distribution \(q\) and samples from unknown \(p\), decide:
- \(H_0\): \(p = q\)
- \(H_1\): \(d_{TV}(p, q) \geq \varepsilon\)
Reduction to Uniformity Testing
Identity testing against any known \(q\) reduces to uniformity testing! The idea: “flatten” \(q\) into the uniform distribution by grouping elements.
Specifically, testing identity to \(q\) over domain of size \(k\) with TV distance \(\varepsilon\) can be solved using a uniformity tester with:
\[n(4k, \varepsilon/4, \delta) \text{ samples}\]How the Reduction Works
- Partition \(\mathcal{X}\) into groups so that \(q\) assigns roughly equal mass to each group.
- Within each group, split elements further to create a domain of size \(\leq 4k\) where \(q\) becomes nearly uniform.
- If \(p = q\), the induced distribution is nearly uniform. If \(d_{TV}(p,q) \geq \varepsilon\), the induced distribution is \(\varepsilon/4\)-far from uniform.
Optimal Testing
Theorem: Optimal Identity/Uniformity Testing
The optimal sample complexity for identity testing (and uniformity testing) with failure probability \(\delta\) is:
\[n = O\!\left(\frac{\sqrt{k} \cdot \log(1/\delta) + \log(1/\delta)}{\varepsilon^2}\right)\]Learning vs Testing: The Quadratic Gap
| Task | Sample Complexity | Scaling in \(k\) |
|---|---|---|
| Learning | \(O(k/\varepsilon^2)\) | Linear |
| Uniformity Testing | \(O(\sqrt{k}/\varepsilon^2)\) | Sublinear |
| Identity Testing | \(O(\sqrt{k}/\varepsilon^2)\) | Sublinear |
Testing is quadratically cheaper than learning. You do not need to learn the full distribution to decide if it has a given property — a much coarser sketch suffices.
Summary & Key Results
| Concept | Key Formula | Significance |
|---|---|---|
| TV Distance | \(d_{TV}(p,q) = \frac{1}{2}\|p-q\|_1\) | Standard metric for distribution closeness |
| Data Processing Ineq. | \(d_{TV}(f(p), f(q)) \leq d_{TV}(p,q)\) | Post-processing cannot help distinguish |
| Pearson-Neyman | \(\alpha + \beta \geq 1 - d_{TV}(p,q)\) | Optimal test uses Scheffé set |
| Learning a Coin | \(n = O(\varepsilon^{-2}\log(1/\delta))\) | Hoeffding-based |
| Learning Distributions | \(n = O((k + \log(1/\delta))/\varepsilon^2)\) | Linear in \(k\), tight |
| Uniformity Testing | \(n = O(\sqrt{k}/\varepsilon^2)\) | Sublinear! Birthday paradox |
| Identity Testing | Reduces to uniformity | \(n = O(\sqrt{k}/\varepsilon^2)\) |
Key Takeaways
- Total variation distance is the right metric for distribution testing: it satisfies the data processing inequality.
- Pearson-Neyman gives the optimal single-sample test and connects TV distance to hypothesis testing error.
- Learning requires \(\Theta(k/\varepsilon^2)\) samples — linear in domain size.
- Testing requires only \(\Theta(\sqrt{k}/\varepsilon^2)\) — a quadratic saving via the birthday paradox / collision counting.
- The collision-based tester (Algorithm 23) counts same-element pairs and compares to a threshold, exploiting the \(\ell_2^2\) connection.
Tutorial Problems
Work through these problems to solidify your understanding of distribution learning and testing.
Problem 1 Warm-up
(Pearson-Neyman as Alice-Bob Game) Alice picks \(b \sim \text{Uniform}\{0,1\}\). If \(b=0\) she draws \(x \sim p\); if \(b=1\) she draws \(x \sim q\). She sends \(x\) to Bob, who must guess \(b\). Show that Bob’s optimal winning probability is:
\[\Pr[\text{Bob wins}] = \frac{1}{2} + \frac{d_{TV}(p,q)}{2}\]Bob’s strategy is a function \(\phi(x) \in \{0, 1\}\). His winning probability is:
\[\Pr[\text{win}] = \frac{1}{2}\Pr_{x \sim p}[\phi(x) = 0] + \frac{1}{2}\Pr_{x \sim q}[\phi(x) = 1]\] \[= \frac{1}{2}(1 - \alpha) + \frac{1}{2}(1 - \beta) = 1 - \frac{\alpha + \beta}{2}\]By Pearson-Neyman, \(\alpha + \beta \geq 1 - d_{TV}(p,q)\), with equality for the optimal test. So:
\[\Pr[\text{win}] \leq 1 - \frac{1 - d_{TV}(p,q)}{2} = \frac{1}{2} + \frac{d_{TV}(p,q)}{2}\]The optimal strategy is: guess \(b = 1\) (i.e., \(q\)) when \(q(x) > p(x)\), else guess \(b = 0\). \(\square\)
Problem 2 Warm-up
(Corollary 50.1 via Hoeffding) Let \(p\) be a distribution on \(\{0,1\}\) with \(p(1) = \theta\). Show that the empirical mean \(\hat{\theta}\) from \(n\) samples satisfies \(\Pr[|\hat{\theta} - \theta| > \varepsilon] \leq \delta\) provided \(n = O(\varepsilon^{-2}\log(1/\delta))\).
Each sample \(x_i \in [0,1]\) is i.i.d. with mean \(\theta\). By Hoeffding’s inequality for bounded random variables:
\[\Pr\!\left[|\hat{\theta} - \theta| > \varepsilon\right] \leq 2\exp(-2n\varepsilon^2)\]Setting \(2\exp(-2n\varepsilon^2) \leq \delta\) and solving: \(n \geq \frac{1}{2\varepsilon^2}\ln\frac{2}{\delta}\). This is \(O(\varepsilon^{-2}\log(1/\delta))\). \(\square\)
Problem 3 Problem Solving ⭐
(\(\ell_2\) and \(\ell_\infty\) violate DPI) Show that the Data Processing Inequality does not hold for \(\ell_2\) or \(\ell_\infty\) distances. Give an explicit counterexample.
Let \(\mathcal{X} = \{1, 2, 3, 4\}\). Define:
- \(p = (1/4, 1/4, 1/4, 1/4)\) (uniform)
- \(q = (1/2, 1/2, 0, 0)\) (uniform on first two elements)
Then \(\|p - q\|_2 = \sqrt{2 \cdot (1/4)^2 + 2 \cdot (1/4)^2} = \sqrt{1/4} = 1/2\).
Now define \(f\) by: \(f(1) = f(2) = a\), \(f(3) = f(4) = b\). Then:
- \(f(p) = (1/2, 1/2)\) on \(\{a, b\}\)
- \(f(q) = (1, 0)\) on \(\{a, b\}\)
\(\|f(p) - f(q)\|_2 = \sqrt{(1/2)^2 + (1/2)^2} = 1/\sqrt{2} \approx 0.707 > 1/2 = \|p - q\|_2\).
So \(\ell_2\) distance increased under post-processing! A similar argument works for \(\ell_\infty\): \(\|p - q\|_\infty = 1/4\) but \(\|f(p) - f(q)\|_\infty = 1/2\). \(\square\)
Problem 4 Problem Solving ⭐
(Prove Scheffé’s Lemma) Show that for distributions \(p, q\) over \(\mathcal{X}\), the set \(S^* = \{x : p(x) > q(x)\}\) achieves the supremum in \(d_{TV}\), and that \(d_{TV}(p,q) = \frac{1}{2}\|p - q\|_1\).
Define \(S^* = \{x : p(x) > q(x)\}\). For any \(S \subseteq \mathcal{X}\):
\[p(S) - q(S) = \sum_{x \in S}(p(x) - q(x)) = \sum_{x \in S \cap S^*}(p(x) - q(x)) + \sum_{x \in S \setminus S^*}(p(x) - q(x))\]The second sum is \(\leq 0\) since \(p(x) \leq q(x)\) for \(x \notin S^*\). So:
\[p(S) - q(S) \leq \sum_{x \in S^*}(p(x) - q(x)) = p(S^*) - q(S^*)\]Thus \(S^*\) maximises \(p(S) - q(S)\) and \(d_{TV}(p,q) = p(S^*) - q(S^*)\).
Since \(\sum_x p(x) = \sum_x q(x) = 1\), the positive differences sum to the same as the negative:
\[p(S^*) - q(S^*) = q(\overline{S^*}) - p(\overline{S^*}) = \frac{1}{2}\sum_x |p(x) - q(x)| = \frac{1}{2}\|p - q\|_1 \quad \square\]Problem 5 Problem Solving ⭐
(Two suboptimal learning bounds) Derive the two suboptimal sample complexities for learning a distribution over \(\mathcal{X}\) with \(|\mathcal{X}| = k\):
(a) \(n = O(k^2/\varepsilon^2 \cdot \log(k/\delta))\) via the union bound approach.
(b) \(n = O(k/\varepsilon^3 \cdot \log(k/\delta))\) via the multiplicative approach.
(a) Union bound approach: We want \(|\hat{p}(x) - p(x)| \leq \varepsilon/k\) for all \(x\). By Hoeffding for each \(x\): need \(n = O((k/\varepsilon)^2 \cdot \log(1/\delta'))\). Union bounding over \(k\) elements with \(\delta' = \delta/k\): \(n = O(k^2/\varepsilon^2 \cdot \log(k/\delta))\).
Then \(d_{TV}(p, \hat{p}) = \frac{1}{2}\sum_x |p(x) - \hat{p}(x)| \leq \frac{1}{2} \cdot k \cdot \varepsilon/k = \varepsilon/2\). Rescaling gives the bound.
(b) Multiplicative approach: Partition \(\mathcal{X}\) into “heavy” elements (\(p(x) \geq \varepsilon/k\)) and “light” elements. For heavy elements, learn each to multiplicative \((1 \pm \varepsilon)\): need \(n = O(\log(k/\delta)/(p(x)\varepsilon^2))\). Since \(p(x) \geq \varepsilon/k\), this is \(O(k/(\varepsilon^3) \cdot \log(k/\delta))\). Light elements contribute at most \(\varepsilon\) to TV distance in total. \(\square\)
Problem 6 Problem Solving ⭐
(Independent-pairs tester) Consider a tester that draws two independent samples of size \(n\) and counts the number of collisions between them (not within each sample). Show that this gives sample complexity \(O(k/\varepsilon^4)\) — worse than the collision tester by a quadratic factor!
Draw \(x_1, \ldots, x_n\) and \(y_1, \ldots, y_n\) independently from \(p\). The number of cross-collisions is:
\[Z = |\{(i,j) : x_i = y_j\}| = \sum_{x \in \mathcal{X}} n_x \cdot m_x\]where \(n_x, m_x\) are counts in each sample. We have \(\mathbb{E}[Z] = n^2 \|p\|_2^2\).
Under \(H_0\): \(\mathbb{E}[Z] = n^2/k\). Under \(H_1\): \(\mathbb{E}[Z] \geq n^2(1 + \Omega(\varepsilon^2))/k\).
The variance of \(Z\) is \(\Theta(n^3 \|p\|_2^2/k)\) due to shared indices, which is larger than the within-sample collision tester. To distinguish the means at the variance scale, we need \(n^2 \varepsilon^2/k \gg n^{3/2}/\sqrt{k}\), giving \(n = \Omega(k/\varepsilon^4)\). This is quadratically worse in \(\varepsilon\) compared to the \(O(\sqrt{k}/\varepsilon^2)\) collision tester. \(\square\)
Problem 7 Advanced ⭐⭐
(Programming exercise) Implement the following and test on real data:
(a) A function computing \(d_{TV}(p,q)\) for two discrete distributions.
(b) The empirical distribution estimator from samples.
(c) The collision-based uniformity tester (Algorithm 23).
(d) Test your uniformity tester on lottery (Lotto) draw data: are the numbers uniformly distributed?
(a) tv_distance(p, q) = 0.5 * sum(|p[i] - q[i]|)
(b) Count occurrences: p_hat[x] = count(x) / n
(c) Count collisions \(Z = \sum_x \binom{n_x}{2}\), compare to threshold \(\tau = \binom{n}{2}(1 + 2\varepsilon^2)/k\).
(d) For Lotto data with \(k\) possible numbers, compute \(Z\) from the draw history and compare to the threshold. If \(Z \leq \tau\), the data is consistent with uniformity. Real lotto draws should pass the test (they use physical random mechanisms). \(\square\)
Problem 8 Advanced ⭐⭐
(Laplace estimator) Consider the Laplace-smoothed estimator:
\[\hat{p}(i) = \frac{n_i + 1}{n + k}\]where \(n_i\) is the number of times element \(i\) appears in \(n\) samples, and \(k = |\mathcal{X}|\).
(a) Show that \(\mathbb{E}[\chi^2(p \| \hat{p})] \leq \frac{k-1}{n+1}\), where \(\chi^2(p \| \hat{p}) = \sum_i \frac{(p(i) - \hat{p}(i))^2}{\hat{p}(i)}\).
(b) Use this to derive the optimal learning bound \(n = O(k/\varepsilon^2)\) via Markov’s inequality and the relation between \(\chi^2\) and TV distance.
(a) Each \(n_i \sim \text{Binomial}(n, p(i))\). We have \(\mathbb{E}[n_i] = np(i)\) and \(\text{Var}[n_i] = np(i)(1-p(i))\).
The Laplace estimator shifts each count by 1: \(\hat{p}(i) = (n_i+1)/(n+k)\). Then:
\[\mathbb{E}[\hat{p}(i)] = \frac{np(i) + 1}{n+k}\]The chi-squared divergence can be bounded using the bias-variance decomposition. After careful calculation:
\[\mathbb{E}[\chi^2(p\|\hat{p})] \leq \frac{k-1}{n+1}\](b) By the inequality \(d_{TV}(p, \hat{p})^2 \leq \frac{1}{4}\chi^2(p \| \hat{p})\), we get:
\[\mathbb{E}[d_{TV}(p, \hat{p})^2] \leq \frac{k-1}{4(n+1)}\]By Markov: \(\Pr[d_{TV}(p, \hat{p}) > \varepsilon] = \Pr[d_{TV}^2 > \varepsilon^2] \leq \frac{k-1}{4(n+1)\varepsilon^2}\). Setting this \(\leq \delta\):
\[n = O\!\left(\frac{k}{\varepsilon^2 \delta}\right)\]For constant \(\delta\), this is \(O(k/\varepsilon^2)\) — optimal! Boosting to arbitrary \(\delta\) via the median trick gives \(O((k + \log(1/\delta))/\varepsilon^2)\). \(\square\)
Chapter quizzes
Self-test and math questions for this chapter are in the Quiz Hub (practice or exam mode).