COMPX270 — Chapter 9 Supplement
Mathematical Foundations: Sketching II
Strongly universal hash families, sign hash functions, \(\ell_p\) norm relationships, variance analysis of sketch estimators, and probability amplification.
Strongly Universal Hash Families
A family \(\mathcal{H}\) of hash functions \(h : [n] \to [m]\) is \(k\)-wise independent (or \(k\)-universal) if for any \(k\) distinct keys \(x_1, \ldots, x_k \in [n]\) and any values \(y_1, \ldots, y_k \in [m]\):
\[\Pr_{h \sim \mathcal{H}}[h(x_1) = y_1 \wedge \cdots \wedge h(x_k) = y_k] = \frac{1}{m^k}\]For a prime \(p \geq n\), the family \(\{h_{a,b}(x) = ((ax + b) \bmod p) \bmod m : a, b \in \mathbb{Z}_p\}\) is pairwise independent (2-universal). It needs only \(O(\log n)\) bits to store \(a\) and \(b\).
A hash family is strongly universal if it is 2-wise independent. For CountSketch, both \(h_t : [n] \to [k]\) and \(g_t : [n] \to \{-1, +1\}\) must come from strongly universal families. This ensures:
- \(\Pr[h(x) = h(y)] = 1/k\) for \(x \neq y\) (collision probability)
- \(\mathbb{E}[g(x) \cdot g(y)] = 0\) for \(x \neq y\) (sign cancellation)
Sign Hash Functions
A sign hash \(g : [n] \to \{-1, +1\}\) is drawn from a strongly universal family. For any distinct \(x, y \in [n]\):
\[\mathbb{E}[g(x)] = 0, \qquad \mathbb{E}[g(x)^2] = 1, \qquad \mathbb{E}[g(x) \cdot g(y)] = 0\]When computing \(g_t(j) \cdot C[t][h_t(j)]\), the sign hash ensures that contributions from elements \(i \neq j\) that collide with \(j\) (i.e., \(h_t(i) = h_t(j)\)) cancel in expectation:
\[\mathbb{E}\!\left[\sum_{i \neq j : h_t(i) = h_t(j)} g_t(j) g_t(i) f_i\right] = \sum_{i \neq j} f_i \cdot \Pr[h_t(i) = h_t(j)] \cdot \underbrace{\mathbb{E}[g_t(j) g_t(i)]}_{= 0} = 0\]This is the key difference from CountMinSketch, which has no sign hash and therefore always overestimates.
\(\ell_p\) Norms
For a vector \(x = (x_1, \ldots, x_d) \in \mathbb{R}^d\) and \(p \geq 1\):
\[\|x\|_p = \left(\sum_{i=1}^{d} |x_i|^p\right)^{1/p}\]Special cases: \(\|x\|_1 = \sum |x_i|\), \(\|x\|_2 = \sqrt{\sum x_i^2}\), \(\|x\|_\infty = \max_i |x_i|\).
For any \(x \in \mathbb{R}^d\):
\[\|x\|_\infty \leq \|x\|_2 \leq \|x\|_1\]And by Cauchy-Schwarz:
\[\|x\|_2 \geq \frac{\|x\|_1}{\sqrt{d}}\]This means the gap between \(\ell_1\) and \(\ell_2\) norms can be at most a factor of \(\sqrt{d}\).
Uniform: \(x = (1, 1, \ldots, 1) \in \mathbb{R}^d\). Then \(\|x\|_1 = d\), \(\|x\|_2 = \sqrt{d}\), so \(\|x\|_1 / \|x\|_2 = \sqrt{d}\). The gap is maximal.
Concentrated: \(x = (d, 0, \ldots, 0)\). Then \(\|x\|_1 = d\), \(\|x\|_2 = d\), so \(\|x\|_1 / \|x\|_2 = 1\). No gap.
This is exactly when CountSketch (\(\ell_2\) error) beats CountMinSketch (\(\ell_1\) error): when the distribution is spread out.
Both CountSketch and CountMinSketch bound error using the tail norm \(\|f_{-j}\|_p\), the norm of the frequency vector with element \(j\) removed. This means heavy hitters (large \(f_j\)) are estimated more accurately, since their contribution is excluded from the error bound.
Variance Analysis of Sketch Estimators
For a single row \(t\) of CountSketch, let \(X_t = g_t(j) \cdot C[t][h_t(j)]\). Then:
\[\mathbb{E}[X_t] = f_j\] \[\text{Var}[X_t] = \mathbb{E}[(X_t - f_j)^2] \leq \frac{\|f_{-j}\|_2^2}{k}\]The variance comes from collisions: element \(i \neq j\) contributes \(f_i^2 \cdot \Pr[h_t(i) = h_t(j)] = f_i^2 / k\) to the variance (using pairwise independence of \(h_t\) and the sign hash \(g_t\)).
Let \(Z_t = X_t - f_j = \sum_{i \neq j, h_t(i) = h_t(j)} g_t(j)g_t(i) f_i\). Then:
\[\mathbb{E}[Z_t^2] = \sum_{i \neq j} f_i^2 \cdot \Pr[h_t(i) = h_t(j)] \cdot \mathbb{E}[(g_t(j)g_t(i))^2]\]Cross-terms vanish by pairwise independence of \(g_t\). Each \(\mathbb{E}[(g_t(j)g_t(i))^2] = 1\) and \(\Pr[h_t(i) = h_t(j)] = 1/k\):
\[\text{Var}[X_t] = \sum_{i \neq j} \frac{f_i^2}{k} = \frac{\|f_{-j}\|_2^2}{k}\]CountMinSketch uses Markov’s inequality instead of Chebyshev, because its estimator is one-sided (always overestimates). For row \(t\):
\[\mathbb{E}[C[t][h_t(j)] - f_j] \leq \frac{\|f_{-j}\|_1}{k}\]By Markov: \(\Pr[C[t][h_t(j)] - f_j > \varepsilon\|f_{-j}\|_1] \leq 1/(k\varepsilon)\). Setting \(k = e/\varepsilon\) makes this \(\leq 1/e\).
Markov & Chebyshev Inequalities
For a non-negative random variable \(X\) and \(t > 0\):
\[\Pr[X \geq t] \leq \frac{\mathbb{E}[X]}{t}\]Used in CountMinSketch: \(X = C[t][h_t(j)] - f_j \geq 0\), giving one-sided bounds.
For any random variable \(X\) with finite variance:
\[\Pr[|X - \mathbb{E}[X]| \geq t] \leq \frac{\text{Var}[X]}{t^2}\]Used in CountSketch: \(X = g_t(j) \cdot C[t][h_t(j)]\), giving two-sided bounds.
- Markov: One-sided (non-negative RV). Gives weaker bounds but works for CMS because overestimation is guaranteed.
- Chebyshev: Two-sided. Gives tighter bounds when variance is small, which is why CS uses \(k = O(1/\varepsilon^2)\) columns (vs \(O(1/\varepsilon)\) for CMS).
The trade-off: CS needs more columns per row (\(1/\varepsilon^2\) vs \(1/\varepsilon\)) but gets a stronger \(\ell_2\) guarantee.
Median Amplification & Min Amplification
Run \(T\) independent rows, each with \(\Pr[\text{bad}] \leq 1/3\). Take the median estimate. The median is bad only if more than half the rows are bad:
\[\Pr[\text{median bad}] \leq \Pr\!\left[\text{Bin}(T, 1/3) > T/2\right] \leq e^{-\Omega(T)}\]Setting \(T = O(\log(1/\delta))\) achieves failure probability \(\leq \delta\).
Run \(T\) independent rows, each with \(\Pr[\text{row overestimates by} > \varepsilon\|f_{-j}\|_1] \leq 1/e\). Take the minimum. The min fails only if all rows fail:
\[\Pr[\text{min bad}] \leq (1/e)^T = e^{-T}\]Setting \(T = \lceil\ln(1/\delta)\rceil\) suffices. No need for the median trick!
CountMinSketch always overestimates (\(\hat{f}_j \geq f_j\) in every row). The minimum picks the row with the least overestimation. Each row independently has probability \(\leq 1/e\) of overestimating by more than \(\varepsilon\|f_{-j}\|_1\). The probability that all rows overestimate by too much decays exponentially, giving built-in amplification.
CountSketch, in contrast, can under- or over-estimate, so min does not work. The median provides a robust central tendency.
Math quiz
Chapter math quizzes are in the Quiz Hub. Filter by this chapter and choose Study / Math / All.