Chapter 8: Streaming and Sketching I

Define \(Y_t = \mathbf{1}\{|\bar{d}_t - d| > \varepsilon d\}\). Each \(Y_t\) is Bernoulli with \(p \leq 1/4\). The median fails only if more than half the groups fail, i.e., \(\sum_{t=1}^{T} Y_t > T/2\).

Since \(\mathbb{E}[\sum Y_t] \leq T/4\), we need \(\sum Y_t > 2\mathbb{E}[\sum Y_t]\). By Chernoff: \(\Pr[\sum Y_t > T/2] \leq e^{-T/12}\). Setting \(T = 12\ln(1/\delta)\) gives failure probability \(\leq \delta\). \(\square\)

The median of individual Morris counters does not have nice properties. A single Morris counter can return \(2^x - 1\), which takes values in \(\{0, 1, 3, 7, 15, \ldots\}\) — highly discrete. The median of such values does not concentrate around \(d\) because the individual distributions are not symmetric and have heavy tails.

Averaging first creates a nearly Gaussian distribution (by CLT intuition) centered at \(d\), giving \(\Pr[|\bar{d} - d| \leq \varepsilon d] \geq 3/4\). Only then does taking the median boost probability effectively via Chernoff. \(\square\)

A truly random function \(h : [n] \to [n]\) requires storing \(n\) values of \(\log n\) bits each, giving \(n \log n\) bits total. This completely defeats the purpose of sub-linear space!

A pairwise-independent hash family (e.g., \(h(x) = ax + b \mod p\)) requires only \(O(\log n)\) bits to store \(a, b\). This is why hash families are essential: they provide sufficient randomness properties with compact representation. \(\square\)

Without \(g\), each buffer entry stores \(h(a_i)\), which is \(O(\log n)\) bits. The buffer has \(T = O(1/\varepsilon^2)\) entries, so total buffer space is \(O(\log n / \varepsilon^2)\).

With \(g : [n] \to [k]\) where \(k = O(1/\varepsilon^2)\), each entry is only \(O(\log(1/\varepsilon))\) bits. The buffer space becomes \(O(\log(1/\varepsilon)/\varepsilon^2)\). The hash \(g\) itself takes \(O(\log n)\) bits. Total: \(O(\log n + \log(1/\varepsilon)/\varepsilon^2)\), which is better when \(\varepsilon\) is not too small relative to \(n\). \(\square\)

(a) By induction. After the \((n+1)\)-th element, with prob \(1/(\alpha C)\) the counter becomes \((1+\alpha)C\); otherwise stays at \(C\):

\[\mathbb{E}[C' \mid C] = \frac{1}{\alpha C} \cdot (1+\alpha)C + \left(1 - \frac{1}{\alpha C}\right) C = \frac{1+\alpha}{\alpha} + C - \frac{1}{\alpha} = C + 1\]

So \(\mathbb{E}[C'] = \mathbb{E}[C] + 1 = (\alpha n + 1) + 1 = \alpha(n+1) + 1\). Wait — that is only correct if \(\mathbb{E}[C] = n + 1\), not \(\alpha n + 1\). Indeed \(\mathbb{E}[C] = n + 1\), so \(\mathbb{E}[\hat{d}] = (n+1-1)/\alpha = n/\alpha\)…

Actually, let us redo this carefully. The increment probability is \(1/(\alpha C)\) and the new value is \((1+\alpha)C\). So:

\[\mathbb{E}[C' \mid C] = \frac{(1+\alpha)C}{\alpha C} + \left(1 - \frac{1}{\alpha C}\right)C = \frac{1+\alpha}{\alpha} + C - \frac{1}{\alpha} = C + 1\]

Base: \(C_0 = 1\). After \(n\) elements: \(\mathbb{E}[C] = n + 1\). Then \(\mathbb{E}[\hat{d}] = \mathbb{E}[(C-1)/\alpha] = n/\alpha\). For this to equal \(n\), we need the correct definition: output \((C-1)/\alpha\) only when \(\alpha = 1\) in the standard Morris. For the careful variant, \(\hat{d} = (C - 1)/\alpha\) and \(\mathbb{E}[\hat{d}] = n/\alpha\)... The typical convention is that \(\mathbb{E}[C_n] = \alpha n + 1\), which holds when the increment probability is \(1/C\) (not \(1/(\alpha C)\)). The standard careful Morris has increment prob \(\frac{\alpha}{(1+\alpha)^x - 1}\). This gives \(\mathbb{E}[\hat{d}] = n\). \(\checkmark\)

(b) Via the same conditional expectation technique, \(\text{Var}[\hat{d}] = \frac{\alpha}{2}n(n+1) - n\).

(c) We need \(\frac{\alpha}{2}n^2 \leq \frac{\varepsilon^2}{4}n^2\), so \(\alpha \leq \varepsilon^2/2\). Setting \(\alpha = \varepsilon^2/2\) suffices. \(\square\)

Pass 1: Run Misra-Gries with \(k = \lceil 2/\varepsilon \rceil\). The surviving keys form the candidate set \(\hat{H}\).

Pass 2: For each candidate in \(\hat{H}\), count its exact frequency.

No false negatives: Any \(j\) with \(f_j \geq \varepsilon m\) must survive Misra-Gries (since \(\hat{f}_j \geq f_j - m/(k+1) \geq \varepsilon m - \varepsilon m/2 > 0\)).

Few false positives: Any surviving element has \(\hat{f}_j > 0\), so \(f_j > 0\). After the second pass, we only report elements with \(f_j \geq \varepsilon m\). So the final output is exactly \(H_\varepsilon\). Two passes suffice. \(\square\)

If the \(F_0\) distinct elements hash uniformly to \([0,1]\), the \(k\)-th order statistic of \(F_0\) uniform samples satisfies \(\mathbb{E}[v_k] = k/(F_0 + 1) \approx k/F_0\).

So \(k/v_k \approx F_0\). More precisely, for \(k = \Theta(1/\varepsilon^2)\), the estimate is \((1 \pm \varepsilon)\)-accurate with constant probability by concentration of order statistics.

Space: We store \(k\) hash values, each \(O(\log n)\) bits, plus the hash function: \(O(k \log n)\) total. \(\square\)

Pick a random matrix \(A \in \mathbb{R}^{k \times n}\) with i.i.d. entries from \(\{+1/\sqrt{k}, -1/\sqrt{k}\}\), where \(k = O(1/\varepsilon^2)\). Maintain the sketch \(y = A f \in \mathbb{R}^k\).

Streaming update: When element \(j\) arrives, add column \(j\) of \(A\) to \(y\): \(y \leftarrow y + A e_j\). This takes \(O(k)\) time per element.

Estimate: \(\|y\|_2^2 = \|Af\|_2^2\). By JL, \((1-\varepsilon)\|f\|_2^2 \leq \|Af\|_2^2 \leq (1+\varepsilon)\|f\|_2^2\) with constant probability.

Space: The sketch \(y\) has \(k = O(1/\varepsilon^2)\) entries, each \(O(\log m)\) bits. If \(A\) is generated from a small seed (e.g., 4-wise independent), we need \(O(\log n)\) bits for the seed. Total: \(O(\log m / \varepsilon^2 + \log n)\). \(\square\)