COMPX270 — Chapter 11 Supplement
Mathematical Foundations: Distribution Learning & Testing
\(\ell_p\) norms, total variation distance, chi-squared divergence, Hoeffding’s inequality, the birthday paradox, and multinomial distributions.
\(\ell_p\) Norms Review
For a vector \(v \in \mathbb{R}^k\), the \(\ell_p\) norm (\(p \geq 1\)) is:
\[\|v\|_p = \left(\sum_{i=1}^{k} |v_i|^p\right)^{1/p}\]Special cases:
- \(\|v\|_1 = \sum_i |v_i|\) (Manhattan distance)
- \(\|v\|_2 = \sqrt{\sum_i v_i^2}\) (Euclidean distance)
- \(\|v\|_\infty = \max_i |v_i|\) (Chebyshev distance)
For any \(v \in \mathbb{R}^k\):
\[\|v\|_\infty \leq \|v\|_2 \leq \|v\|_1 \leq \sqrt{k}\,\|v\|_2 \leq k\,\|v\|_\infty\]This chain explains why different norms give different sample complexities in distribution testing.
Let \(p = (1/2, 1/4, 1/4)\) and \(q = (1/3, 1/3, 1/3)\). The difference \(p - q = (1/6, -1/12, -1/12)\).
- \(\|p-q\|_1 = 1/6 + 1/12 + 1/12 = 1/3\)
- \(d_{TV}(p,q) = \frac{1}{2}\|p-q\|_1 = 1/6\)
- \(\|p-q\|_2 = \sqrt{1/36 + 1/144 + 1/144} = \sqrt{6/144} = \sqrt{1/24}\)
TV Distance: Formal Properties
\(d_{TV}\) satisfies the three axioms of a metric:
- Identity: \(d_{TV}(p,q) = 0 \iff p = q\)
- Symmetry: \(d_{TV}(p,q) = d_{TV}(q,p)\)
- Triangle inequality: \(d_{TV}(p,r) \leq d_{TV}(p,q) + d_{TV}(q,r)\)
All follow from the properties of the \(\ell_1\) norm.
An important alternative characterisation:
\[d_{TV}(p,q) = \min_{\gamma \in \Gamma(p,q)} \Pr_{(X,Y) \sim \gamma}[X \neq Y]\]where \(\Gamma(p,q)\) is the set of all joint distributions (couplings) with marginals \(p\) and \(q\). This means TV distance equals the minimum disagreement probability over all couplings.
For \(n\) i.i.d. samples, \(d_{TV}(p^{\otimes n}, q^{\otimes n}) \leq n \cdot d_{TV}(p,q)\) by the triangle inequality applied to each coordinate. More precisely:
\[d_{TV}(p^{\otimes n}, q^{\otimes n}) \leq 1 - (1 - d_{TV}(p,q))^n\]The TV distance between product distributions grows with \(n\), making distinguishing easier with more samples.
Chi-Squared Divergence
For distributions \(p, q\) with \(q(x) > 0\) for all \(x\):
\[\chi^2(p \| q) = \sum_{x \in \mathcal{X}} \frac{(p(x) - q(x))^2}{q(x)} = \sum_{x \in \mathcal{X}} \frac{p(x)^2}{q(x)} - 1\]The chi-squared divergence upper bounds the squared TV distance:
\[d_{TV}(p,q)^2 \leq \frac{1}{4}\chi^2(p \| q)\]This follows from Cauchy-Schwarz: \(\left(\sum |p(x)-q(x)|\right)^2 \leq \left(\sum \frac{(p(x)-q(x))^2}{q(x)}\right)\left(\sum q(x)\right)\).
Therefore: if \(\chi^2(p \| q) \leq 4\varepsilon^2\), then \(d_{TV}(p,q) \leq \varepsilon\).
The Laplace estimator \(\hat{p}(i) = (n_i + 1)/(n + k)\) satisfies:
\[\mathbb{E}[\chi^2(p \| \hat{p})] \leq \frac{k - 1}{n + 1}\]Combined with the inequality above and Markov: setting \(n = O(k/\varepsilon^2)\) gives \(d_{TV}(p, \hat{p}) \leq \varepsilon\) with constant probability.
Hoeffding’s Inequality
Let \(X_1, \ldots, X_n\) be independent with \(X_i \in [a_i, b_i]\). Let \(\bar{X} = \frac{1}{n}\sum_i X_i\). Then:
\[\Pr\!\left[|\bar{X} - \mathbb{E}[\bar{X}]| \geq t\right] \leq 2\exp\!\left(-\frac{2n^2 t^2}{\sum_{i=1}^n (b_i - a_i)^2}\right)\]For \(X_i \in [0, 1]\) (e.g., Bernoulli):
\[\Pr[|\bar{X} - \mathbb{E}[\bar{X}]| \geq t] \leq 2e^{-2nt^2}\]For a coin with bias \(\theta\), the empirical mean \(\hat{\theta} = \bar{X}\) from \(n\) flips has \(\mathbb{E}[\hat{\theta}] = \theta\). By Hoeffding:
\[\Pr[|\hat{\theta} - \theta| > \varepsilon] \leq 2e^{-2n\varepsilon^2}\]Setting RHS \(\leq \delta\): \(n \geq \frac{1}{2\varepsilon^2}\ln\frac{2}{\delta}\).
Chebyshev gives \(\Pr[|\bar{X} - \mu| \geq t] \leq \text{Var}[\bar{X}]/t^2 = \sigma^2/(nt^2)\) — polynomial decay. Hoeffding gives exponential decay \(e^{-\Omega(nt^2)}\), which is much stronger for bounded random variables. The \(\log(1/\delta)\) dependence in sample complexity comes from Hoeffding’s exponential tail.
Birthday Paradox
In a room of \(n\) people, each with a birthday chosen uniformly from \(k\) days, the probability of at least one shared birthday (collision) is:
\[\Pr[\text{collision}] = 1 - \prod_{i=1}^{n-1}\left(1 - \frac{i}{k}\right) \approx 1 - e^{-n(n-1)/(2k)}\]When \(n = \Theta(\sqrt{k})\), this probability becomes a non-trivial constant.
The number of collisions (pairs with the same value) among \(n\) uniform samples from \([k]\) is:
\[\mathbb{E}[Z] = \binom{n}{2} \cdot \frac{1}{k} = \frac{n(n-1)}{2k}\]More generally, for any distribution \(p\):
\[\mathbb{E}[Z] = \binom{n}{2} \sum_x p(x)^2 = \binom{n}{2} \|p\|_2^2\]Non-uniform distributions have \(\|p\|_2^2 > 1/k\), leading to more collisions. This is the basis of the collision-based uniformity tester.
For \(k = 365\) (days in a year):
- \(n = 23\): \(\Pr[\text{collision}] \approx 50.7\%\)
- \(n = 50\): \(\Pr[\text{collision}] \approx 97\%\)
- \(n = \sqrt{365} \approx 19\): expected collisions \(\approx 19 \cdot 18 / (2 \cdot 365) \approx 0.47\)
The threshold \(\sqrt{k}\) marks the transition from “collisions unlikely” to “collisions likely.”
Multinomial Distribution
Drawing \(n\) i.i.d. samples from a distribution \(p = (p_1, \ldots, p_k)\), the vector of counts \((n_1, \ldots, n_k)\) follows the multinomial distribution:
\[\Pr[n_1 = c_1, \ldots, n_k = c_k] = \frac{n!}{c_1! \cdots c_k!} \prod_{i=1}^k p_i^{c_i}\]where \(\sum_i c_i = n\).
- Each marginal: \(n_i \sim \text{Binomial}(n, p_i)\) with \(\mathbb{E}[n_i] = np_i\), \(\text{Var}[n_i] = np_i(1-p_i)\).
- Covariance: \(\text{Cov}[n_i, n_j] = -np_ip_j\) for \(i \neq j\) (negative correlation).
- The empirical distribution \(\hat{p}(i) = n_i/n\) is the MLE and is unbiased: \(\mathbb{E}[\hat{p}(i)] = p_i\).
The natural estimator \(d_{TV}(p, \hat{p}) = \frac{1}{2}\sum_i |p_i - n_i/n|\) is biased upward (Jensen’s inequality). The variance of \(\hat{p}(i) = n_i/n\) is:
\[\text{Var}[\hat{p}(i)] = \frac{p_i(1-p_i)}{n} \leq \frac{p_i}{n}\]Summing over all \(i\): the total variance is \(\sum_i p_i(1-p_i)/n \leq 1/n\), which drives the \(O(k/\varepsilon^2)\) learning bound.
Math quiz
Chapter math quizzes are in the Quiz Hub. Filter by this chapter and choose Study / Math / All.