Final Exam Formulas & Identities Sheet

Streaming Algorithms & Approximate Counting

Morris Counter

Update rule: $C_i \leftarrow C_i + 1$ with probability $\frac{1}{2^{C_i}}$

Estimate: $\hat{n} = 2^C - 1$

Variance:

$$\text{Var}(2^C - 1) \approx \frac{N^2}{2}$$

Morris+ (Parallel Averaging)

Run $T = \lceil 1/\varepsilon^2 \rceil$ independent Morris counters, return average:

$$\text{Output} = \frac{1}{T} \sum_{i=1}^T (2^{C_i} - 1)$$

Success probability: $\geq 3/4$ (output within $\varepsilon N$ of truth)

Morris++ (Boosted Success Probability)

Run $\lceil \log(1/\delta) \rceil$ independent Morris+ instances, return median:

$$\text{Output} = \text{median}\{M_1, M_2, \ldots, M_{\lceil \log(1/\delta) \rceil}\}$$

Success probability: $\geq 1 - \delta$ (arbitrary confidence)

Total counters needed: $\lceil \log(1/\delta) \rceil \times \lceil 1/\varepsilon^2 \rceil$

---

Epsilon-Delta Approximate Median

Problem Statement

Find element with rank between $(1/2 - \varepsilon)n$ and $(1/2 + \varepsilon)n$ with confidence $\geq 1-\delta$.

Algorithm

Run $T = \lceil 1/\varepsilon^2 \cdot \log(1/\delta) \rceil$ independent uniform samples in parallel, return median of samples.

Why It Works

By Chernoff bounds, probability that more than half the samples fall in either “bad” tail region is $\leq \delta$.