Frequency Moments, Norms & Entropy

What the Shape of a Stream Reveals

Imagine two music playlists with eight plays each. One plays four artists twice; another plays one artist five times and three artists once each. Both have eight plays and four distinct artists, yet the second is much more concentrated. Frequency moments summarize the shape of a distribution without asking for any specific artist: the total number of events, the number of distinct keys, and how much repeated activity is concentrated on a few keys. For counts $(2,2,2,2)$ the sum of squares is 16; for $(5,1,1,1)$ it is 28. Why might a cache, network operator, or fraud investigator care about this difference? Frequency estimation from the prerequisite chapter answers how often a nominated key appears; here the question concerns the entire frequency vector. The number of distinct keys is called its support size, not the size of the possible universe. Entropy measures uncertainty in a normalized distribution, so a stream length and a measurement window must be specified before comparing it across workloads.

Moments, Norms and Entropy as Distribution Lenses

Fix a finite universe and a stream of unit insertions; let $f_i$ count occurrences of item $i$, and $N=\sum_i f_i>0$. The zeroth moment $F_0$ counts indices with $f_i>0$, $F_1=\sum_i f_i=N$, and for integer $k\geq2$, $F_k=\sum_i f_i^k$. More generally, for real $p>0$, $F_p=\sum_i \lvert f_i\rvert^p$ and $\lVert f\rVert_p=F_p^{1/p}$. In a signed turnstile stream, $F_1=\sum_i f_i$ can differ from $\lVert f\rVert_1=\sum_i\lvert f_i\rvert$; use absolute values and define support by $f_i\ne0$. For a probability distribution $p_i=f_i/N$ in the nonnegative model, Shannon entropy in bits is $H=-\sum_{i:f_i>0}p_i\log_2p_i$. It obeys $0\leq H\leq\log_2F_0$: a single occupied key attains zero, and uniform mass over $F_0$ keys attains the maximum. Collision probability is $\sum_i p_i^2=F_2/N^2$, so $N^2/F_2$ is the inverse-collision effective number of keys; it never exceeds $F_0$ by Cauchy–Schwarz. In the AMS sign estimator, choosing jointly four-wise independent unbiased signs $s_i\in\{-1,1\}$ makes $Z=\sum_i s_i f_i$ satisfy $\mathbb E[Z^2]=F_2$ and $\operatorname{Var}(Z^2)\leq2F_2^2$. Repetition and a median-of-means construction give relative error $\varepsilon$ with failure probability $\delta$ using order $\varepsilon^{-2}\log(1/\delta)$ counters, plus hash seeds, under a fixed-stream randomness model.

flowchart TD
 A["Positive frequencies f"] --> B["Sum N and support F0"]
 A --> C["Squares give F2"]
 B --> D["Normalize p = f/N"]
 C --> E["Collision probability F2/N²"]
 D --> F["Entropy H"]
 A --> G["Four-wise random signs"]
 G --> H["Unbiased AMS estimate of F2"]
 classDef navy fill:#17365D,color:#fff
 classDef teal fill:#147D84,color:#fff
 classDef crimson fill:#C6284D,color:#fff
 classDef purple fill:#6C3BAA,color:#fff
 class A,B navy
 class C,E teal
 class D,F purple
 class G,H crimson

From Random Signs to Moment Estimates

Why do signs work? Expand $Z^2=\sum_i f_i^2s_i^2+2\sum_{i\lt j}f_if_js_is_j$. Each diagonal term equals $f_i^2$, while pairwise independence and zero mean make each cross term vanish in expectation. For the variance, four-wise independence makes mixed products involving distinct indices vanish and yields $\operatorname{Var}(Z^2)=4\sum_{i\lt j}f_i^2f_j^2=2(F_2^2-F_4)\leq2F_2^2$. The equality requires the stated independence; pairwise independent signs are enough for unbiasedness but do not alone justify this variance calculation. Average $t$ independent copies: variance is at most $2F_2^2/t$; Chebyshev gives failure at most $2/(t\varepsilon^2)$, so taking $t\geq8/\varepsilon^2$ makes each group good with probability at least $3/4$. A median of order $\log(1/\delta)$ independent groups amplifies confidence. This analyzes a fixed frequency vector independent of the random seeds; an adaptive adversary who sees and reacts to hash choices needs a different guarantee. For $0\lt p\leq2$, symmetric $p$-stable random projections offer another route to $\ell_p$ scale because a weighted sum of independent $p$-stable variables has scale $\lVert f\rVert_p$; $p=2$ is Gaussian and $p=1$ is Cauchy. This is a distributional identity rather than a claim that one projection gives a precise estimate, and higher moments $k>2$ need separate methods and typically harder space tradeoffs.

flowchart TD
 A["Fixed vector and unbiased signs"] --> B["Pairwise independence"]
 B --> C["Cross terms cancel in mean"]
 C --> D["Expected Z² equals F2"]
 A --> E["Four-wise independence"]
 E --> F["Variance at most 2 F2²"]
 F --> G["Average groups; take median"]
 G --> H["Relative error with confidence"]
 A --> X["Adaptive updates after seed reveal"]
 X --> Y["Fixed-vector proof insufficient"]
 classDef navy fill:#17365D,color:#fff
 classDef teal fill:#147D84,color:#fff
 classDef crimson fill:#C6284D,color:#fff
 classDef purple fill:#6C3BAA,color:#fff
 class A,B,E navy
 class C,D teal
 class F,G,H purple
 class X,Y crimson

Skew Detection, Capacity Planning and Anomalies

An online store can compare product-view diversity between campaigns: equal traffic volumes may hide one campaign dominated by a single product. A CDN can use $F_2/N^2$ as a concentration signal for capacity planning across regional keys, while $F_0$ estimates the breadth of distinct cache objects. At production scale, assume 80 shards, roughly $10^8$ positive requests per hour, and a fixed one-hour event-time window. With shared hash seeds, each shard adds signed counts into the same AMS counters and merges them by summing before squaring; summing locally squared estimates would omit cross-shard terms and undercount global $F_2$. Entropy can distinguish a few dominant keys from a broad tail but cannot identify which keys cause the change; investigate candidates separately with heavy-hitter tools. An adversary can split traffic over rotating identities, raising apparent entropy without changing the underlying actor mix. Identity mapping, deduplication, and window boundaries determine whether the mathematical vector corresponds to the real operational question. A signed correction stream also makes $F_1=N$ and probability normalization inappropriate until final nonnegative counts are established.

Diagnose a Distribution with the Right Summary

First declare whether the desired result is distinct count $F_0$, total volume $F_1$, concentration $F_2/N^2$, a higher moment, a norm, or entropy. Record key identity, update model, observation window, permissible error, confidence, and whether the input can adapt to the estimator's randomness. Calculate exact small cases, compare sketches on replayable samples, and check merge ordering and window completeness. When a single key rather than a global shape matters, return to frequency estimation or heavy-hitter discovery. The exercises below ask for exact arithmetic, a justified AMS bound, and an operational decision that states where the model ceases to fit.