COMPX270 — Chapter 8 Supplement
Mathematical Foundations: Streaming & Sketching
Logarithms, geometric random variables, conditional expectation and variance analysis, trailing zeros, and the median-of-means technique.
Logarithms Review
In streaming algorithms, we encounter \(\log\log m\). This is the iterated logarithm: the logarithm of the logarithm.
\[\log\log m = \log_2(\log_2 m)\]For example: \(\log\log 2^{64} = \log_2 64 = 6\). Even for astronomically large \(m\), \(\log\log m\) is tiny.
The Morris counter \(x\) represents values up to \(\approx \log_2 m\). To store \(x\), we need \(\lceil\log_2(\log_2 m)\rceil = O(\log\log m)\) bits. For a stream of \(m = 10^{18}\) elements:
\[\log_2 m \approx 60, \qquad \log_2 60 \approx 6 \text{ bits}\]Just 6 bits for approximate counting of a quintillion elements!
For any base \(b > 1\):
- \(\log_b(xy) = \log_b x + \log_b y\)
- \(\log_b(x^k) = k \log_b x\)
- \(\log_b x = \frac{\ln x}{\ln b}\) (change of base)
- \(b^{\log_b x} = x\) and \(\log_b(b^x) = x\)
Geometric Random Variables
A random variable \(X \sim \text{Geometric}(p)\) counts the number of independent Bernoulli(\(p\)) trials until the first success:
\[\Pr[X = k] = (1-p)^{k-1} p, \quad k = 1, 2, 3, \ldots\] \[\mathbb{E}[X] = \frac{1}{p}, \qquad \text{Var}[X] = \frac{1-p}{p^2}\]In the Morris counter, when \(x = k\), the probability of incrementing is \(p = 1/2^k\). The number of stream elements needed to trigger the next increment is \(\text{Geometric}(1/2^k)\) with expected value \(2^k\). This means the gaps between increments grow exponentially, which is why \(x\) only reaches \(\approx \log_2 m\) after \(m\) elements.
The geometric distribution is memoryless:
\[\Pr[X > s + t \mid X > s] = \Pr[X > t]\]Knowing you have waited \(s\) trials without success gives no information about how much longer you will wait.
Law of Total Expectation
For any random variables \(X\) and \(Y\):
\[\mathbb{E}[X] = \mathbb{E}[\mathbb{E}[X \mid Y]]\]In words: the expectation of \(X\) equals the expectation of the conditional expectation of \(X\) given \(Y\). This is also called the tower property or iterated expectation.
Let \(C_d = 2^{x_d}\) after \(d\) elements. To compute \(\mathbb{E}[C_{d+1}]\), we condition on \(C_d\):
\[\mathbb{E}[C_{d+1}] = \mathbb{E}[\mathbb{E}[C_{d+1} \mid C_d]]\]Given \(C_d\), the new value \(C_{d+1}\) is either \(2C_d\) (with prob \(1/C_d\)) or \(C_d\) (with prob \(1 - 1/C_d\)). So:
\[\mathbb{E}[C_{d+1} \mid C_d] = \frac{2C_d}{C_d} + \left(1 - \frac{1}{C_d}\right)C_d = 2 + C_d - 1 = C_d + 1\]Taking outer expectation: \(\mathbb{E}[C_{d+1}] = \mathbb{E}[C_d] + 1\). By induction: \(\mathbb{E}[C_d] = d + 1\).
General Form with Partitioning
If \(B_1, B_2, \ldots\) partition the sample space with \(\Pr[B_i] > 0\):
\[\mathbb{E}[X] = \sum_i \mathbb{E}[X \mid B_i] \cdot \Pr[B_i]\]Variance via Conditional Expectation
For any random variables \(X\) and \(Y\):
\[\text{Var}[X] = \mathbb{E}[\text{Var}[X \mid Y]] + \text{Var}[\mathbb{E}[X \mid Y]]\]In words: total variance = expected conditional variance + variance of conditional means.
We can also compute variance via \(\text{Var}[X] = \mathbb{E}[X^2] - \mathbb{E}[X]^2\). For the Morris counter, we need both \(\mathbb{E}[C_d]\) and \(\mathbb{E}[C_d^2]\). The second moment satisfies a similar inductive formula:
\[\mathbb{E}[C_{d+1}^2 \mid C_d] = \frac{(2C_d)^2}{C_d} + \left(1 - \frac{1}{C_d}\right)C_d^2 = 4C_d + C_d^2 - C_d = C_d^2 + 3C_d\]Taking expectation: \(\mathbb{E}[C_{d+1}^2] = \mathbb{E}[C_d^2] + 3\mathbb{E}[C_d] = \mathbb{E}[C_d^2] + 3(d+1)\).
Solving: \(\mathbb{E}[C_d^2] = 1 + 3\sum_{k=1}^{d} k = 1 + \frac{3d(d+1)}{2} = \frac{3d^2 + 3d + 2}{2}\).
Then: \(\text{Var}[\hat{d}] = \text{Var}[C - 1] = \mathbb{E}[C^2] - \mathbb{E}[C]^2 = \frac{3d^2+3d+2}{2} - (d+1)^2 = \frac{d^2 - d}{2} = \frac{d(d-1)}{2}\).
Trailing Zeros & Divisibility
For a positive integer \(x\), the number of trailing zeros in its binary representation, denoted \(\text{zeros}(x)\), is the largest \(r\) such that \(2^r\) divides \(x\):
\[\text{zeros}(x) = \max\{r \geq 0 : 2^r \mid x\}\]Equivalently, \(\text{zeros}(x) = \nu_2(x)\), the 2-adic valuation of \(x\).
- \(12 = 1100_2\): \(\text{zeros}(12) = 2\)
- \(7 = 111_2\): \(\text{zeros}(7) = 0\)
- \(16 = 10000_2\): \(\text{zeros}(16) = 4\)
- \(1 = 1_2\): \(\text{zeros}(1) = 0\)
If \(h\) maps uniformly to \([n]\), then for each distinct element \(j\):
\[\Pr[\text{zeros}(h(j)) \geq r] = \frac{\lfloor n / 2^r \rfloor}{n} \approx \frac{1}{2^r}\]The probability halves with each additional trailing zero. So seeing \(r\) trailing zeros is roughly as likely as seeing a specific event with probability \(1/2^r\).
Connection to Distinct Elements
If there are \(F_0\) distinct elements, the expected number with \(\geq r\) trailing zeros is \(F_0 / 2^r\). The maximum \(z = \max_j \text{zeros}(h(j))\) satisfies \(z \approx \log_2 F_0\), so \(2^z \approx F_0\). This is the core idea behind the Tidemark algorithm.
Median-of-Means Technique
Given an unbiased estimator \(\hat{\theta}\) with \(\text{Var}[\hat{\theta}] = \sigma^2\), Chebyshev gives:
\[\Pr[|\hat{\theta} - \theta| > t] \leq \frac{\sigma^2}{t^2}\]For a \((1\pm\varepsilon)\) guarantee: set \(t = \varepsilon\theta\), giving \(\Pr[\text{bad}] \leq \sigma^2 / (\varepsilon\theta)^2\). If \(\sigma^2 = \Theta(\theta^2)\) (like Morris), this is \(O(1/\varepsilon^2)\) — constant, not small.
Run \(k\) independent copies. The average \(\bar{\theta} = \frac{1}{k}\sum_{i=1}^{k} \hat{\theta}_i\) has:
\[\mathbb{E}[\bar{\theta}] = \theta, \qquad \text{Var}[\bar{\theta}] = \frac{\sigma^2}{k}\]Setting \(k = \lceil 8\sigma^2/(\varepsilon\theta)^2 \rceil\), Chebyshev gives \(\Pr[|\bar{\theta} - \theta| > \varepsilon\theta] \leq 1/8 < 1/4\).
So with probability \(\geq 3/4\), the average is \((1\pm\varepsilon)\)-accurate.
Run \(T\) independent groups, each with \(k\) copies. Let \(\bar{\theta}_1, \ldots, \bar{\theta}_T\) be the group averages. Take the median \(\tilde{\theta}\).
Define \(Y_t = \mathbf{1}\{|\bar{\theta}_t - \theta| > \varepsilon\theta\}\). Each \(\Pr[Y_t = 1] \leq 1/4\). The median fails iff more than half the groups fail: \(\sum Y_t > T/2\).
\[\mathbb{E}\!\left[\sum_{t=1}^{T} Y_t\right] \leq \frac{T}{4}\]By Chernoff (multiplicative form with \(\delta = 1\)): \(\Pr[\sum Y_t > T/2] \leq e^{-T/12}\). Setting \(T = 12\ln(1/\delta)\):
\[\Pr[|\tilde{\theta} - \theta| > \varepsilon\theta] \leq \delta\]Reversing the order (median first, then average) fails because:
- The median of \(k\) copies of a heavy-tailed estimator may not have bounded variance.
- Averaging medians does not benefit from Chebyshev without a variance bound.
The correct order is: mean first (creates bounded variance), median second (boosts probability).
Math quiz
Chapter math quizzes are in the Quiz Hub. Filter by this chapter and choose Study / Math / All.