Limited-Independence Hash Families

How Much Independence Is Enough?

Imagine assigning students to tables by drawing cards. Perfect randomness would require a fresh, unrelated card for every student. Often the task needs much less: if the only concern is whether any particular pair meets, it is enough that every pair of assignments behaves independently. Questions about groups of four require four-wise independence, but still not a completely random assignment of everyone.

Hashing in streaming algorithms works the same way. A truly random function from a universe $U$ to $m$ buckets needs enough information to describe an arbitrary output for every key—roughly $|U|\log_2m$ bits. That is impossible when $U$ is enormous. A hash family is a compact set $\mathcal H$ of functions. We sample a short seed to choose $h\in\mathcal H$, then compute $h(x)$ deterministically. The proof must establish that this smaller family supplies exactly the joint randomness the algorithm uses.

This deep dive builds on the prerequisite treatment of streaming, hashing, and randomness. That chapter explains collision probability and randomized sketches; the unresolved engineering question is how to implement their “random hash” assumptions without storing a random table over the whole universe.

For a tiny warning, choose independent fair bits $A$ and $B$, and define $C=A\oplus B$. Each bit is fair and every pair among $A,B,C$ is independent. Yet the triple is not independent because $A\oplus B\oplus C=0$ always. Thus pairwise independence reproduces every one- and two-variable calculation, but it does not justify a proof step involving three variables jointly.

Formally, $\mathcal H$ is $k$-wise independent from $U$ to range $R$ when, for any distinct $x_1,\ldots,x_k$ and any $y_1,\ldots,y_k\in R$,

$$ \Pr_{h\leftarrow\mathcal H}[h(x_1)=y_1,\ldots,h(x_k)=y_k]=|R|^{-k}. $$

A family is universal when every distinct pair collides with probability at most $1/|R|$. Pairwise independence implies universality and uniform marginals, but universality alone does not imply pairwise-independent output values. The seed length is the number of random bits required to identify a family member. In real systems it affects memory, reproducibility, serialization, merge compatibility, and exposure to adversarially selected inputs.

Building Pairwise and k-Wise Hash Families

Let $p$ be prime and identify keys and outputs with the finite field $\mathbb F_p$. Sample $a,b$ independently and uniformly from $\mathbb F_p$, and define

$$ h_{a,b}(x)=ax+b\pmod p. $$

For distinct $x,y$ and requested outputs $u,v$, the constraints $ax+b=u$ and $ay+b=v$ have exactly one solution. Subtracting gives $a(x-y)=u-v$. Since $x-y$ is nonzero and every nonzero field element has an inverse,

$$ a=(u-v)(x-y)^{-1},\qquad b=u-ax. $$

There are $p^2$ equally likely coefficient pairs and exactly one produces $(u,v)$, so the joint probability is $1/p^2$. This proves pairwise independence, not merely the collision statement. Summing over the $p$ choices with $u=v$ gives collision probability $1/p$.

The same linear-algebra idea generalizes. Sample coefficients $a_0,\ldots,a_{k-1}$ uniformly from $\mathbb F_p$ and define

$$ h_{\mathbf a}(x)=\sum_{j=0}^{k-1}a_jx^j\pmod p. $$

For $k$ distinct inputs $x_1,\ldots,x_k$ and target outputs $y_1,\ldots,y_k$, the coefficient vector solves a Vandermonde system. Its determinant is $\prod_{i\lt j}(x_j-x_i)$, which is nonzero because inputs are distinct. Therefore there is exactly one coefficient vector for every output vector. Of the $p^k$ seeds, one realizes the requested vector, proving probability $p^{-k}$ and hence $k$-wise independence.

The seed contains $k$ field elements, or $k\lceil\log_2p\rceil$ stored bits with possible rejection or encoding overhead for uniform sampling. Horner's rule evaluates the polynomial in $k-1$ multiplications and $k-1$ additions. If outputs need $m\lt p$ buckets, applying ordinary remainder modulo $m$ can introduce bias unless $m$ divides the source range. Rejection, multiply-high range reduction with a proven distribution, or a construction tailored to the range must be analyzed explicitly.

The field condition is essential. Modulo a composite number, a nonzero difference need not be invertible. Over $\mathbb Z_8$, $x-y=2$ has no inverse, so the uniqueness proof collapses. Another boundary is domain encoding: two application keys that map to the same field element are not distinct inputs to the theorem.

flowchart TD
    A[Choose prime field Fp] --> B[Encode distinct keys as field elements]
    B --> C[Sample k uniform coefficients]
    C --> D[Evaluate degree k minus 1 polynomial]
    D --> E[Fix k distinct inputs and target outputs]
    E --> F[Vandermonde determinant is nonzero]
    F --> G[Exactly one seed realizes outputs]
    G --> H[Joint probability p to minus k]
    H --> I[k-wise independent family]
    B --> X{Distinct encoding and field arithmetic?}
    X -->|no| Y[Proof invalid: collisions or noninvertible differences]
    X -->|yes| C
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
    classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
    class A,B,C navy;
    class D,E,F purple;
    class G,H,I teal;
    class X,Y crimson;

Moments That Survive Limited Randomness

Why does the independence order map to a moment? Expand a statistic as a polynomial in random variables. Its expectation is a sum of expectations of monomials. If every monomial involves at most $k$ distinct hash outputs, $k$-wise independence makes its expectation identical to the fully independent case. Repeated powers do not increase the number of distinct variables, but a product containing $k+1$ distinct outputs exceeds the guarantee.

Let $I_i$ indicate that key $x_i$ lands in bucket zero, and let $S=\sum_{i=1}^n I_i$. Under a pairwise-independent uniform hash into $m$ buckets, $\mathbb E[I_i]=1/m$ and $\mathbb E[I_iI_j]=1/m^2$ for distinct keys. Therefore

$$ \mathbb E[S]=\frac nm,\qquad \operatorname{Var}(S)=\sum_i\operatorname{Var}(I_i)=n\frac1m\left(1-\frac1m\right). $$

All covariance terms vanish. This matches full independence exactly, so Chebyshev-based occupancy analysis needs only pairwise independence. But $\mathbb E[(S-\mathbb E S)^4]$ expands into products involving up to four distinct indicators; reproducing the fully independent fourth moment generally needs four-wise independence. Exponential Chernoff tails usually require substantially more independence or a special limited-independence theorem with explicit parameters.

The parity example $A,B,C=A\oplus B$ demonstrates the boundary. The sum $T=A+B+C$ takes only values $0$ and $2$, with probabilities $1/4$ and $3/4$. Three fully independent bits yield $0,1,2,3$ with probabilities $1/8,3/8,3/8,1/8$. Both models have mean $3/2$ and variance $3/4$, but their third and higher distributional behavior differs. Pairwise tests cannot certify a tail statement that depends on the missing triple independence.

from itertools import product
from fractions import Fraction

def poly_hash(coeffs, x, p):
    if p <= 1:
        raise ValueError("p must be a prime field modulus")
    if not 0 <= x < p:
        raise ValueError("x must be a canonical field element")
    value = 0
    for coefficient in reversed(coeffs):
        value = (value * x + coefficient) % p
    return value

def output_distribution(p, degree, keys):
    if len(set(keys)) != len(keys):
        raise ValueError("keys must be distinct for k-wise claims")
    counts = {}
    for coeffs in product(range(p), repeat=degree + 1):
        outputs = tuple(poly_hash(coeffs, x, p) for x in keys)
        counts[outputs] = counts.get(outputs, 0) + 1
    return counts, p ** (degree + 1)

def assert_uniform_joint(p, degree, keys):
    counts, seeds = output_distribution(p, degree, keys)
    expected = Fraction(1, p ** len(keys))
    for outputs in product(range(p), repeat=len(keys)):
        assert Fraction(counts.get(outputs, 0), seeds) == expected

#Normal case: affine hashes are uniform on every pair of distinct keys.
assert_uniform_joint(5, 1, [1, 2])

#Boundary: the affine family is not three-wise independent.
affine, affine_seeds = output_distribution(5, 1, [1, 2, 3])
assert Fraction(affine.get((0, 0, 0), 0), affine_seeds) == Fraction(1, 25)
assert Fraction(affine.get((0, 0, 1), 0), affine_seeds) == 0

#Higher order: quadratics give three-wise independence.
assert_uniform_joint(5, 2, [1, 2, 3])

#Moment check for bucket-zero occupancy under the affine family.
samples = []
for a, b in product(range(5), repeat=2):
    samples.append(sum(poly_hash((b, a), x, 5) == 0 for x in [1, 2, 3]))
mean = sum(samples) / len(samples)
variance = sum((s - mean) ** 2 for s in samples) / len(samples)
print("affine occupancy mean / variance:", mean, variance)
print("affine all-zero probability:", affine.get((0, 0, 0), 0) / affine_seeds)
assert mean == 3 / 5
assert abs(variance - 12 / 25) < 1e-12

#Invalid tests expose domain and distinctness assumptions.
for bad_keys in ([1, 1], [0, 5]):
    try:
        output_distribution(5, 1, bad_keys) if bad_keys[0] == bad_keys[1] else poly_hash((1, 2), bad_keys[1], 5)
    except ValueError as error:
        print("invalid test passed:", error)

Small Seeds in Large Sketches

In a teaching example, hash $n$ distinct balls into $m$ bins and study one bin's load. Pairwise independence supplies the exact mean and variance needed for Chebyshev's inequality. Moving to a fourth-moment tail changes the proof polynomial and therefore the required family: this is a clean demonstration that the algorithm name does not determine independence—the analysis does.

At professional scale, consider a Count Sketch service with $d$ rows and $w$ counters per row. A typical proof uses a bucket hash and random sign hash in each row, then controls a second moment before taking a median across rows. The bucket and sign families, their independence orders, and whether row seeds are independent must match that proof. Seeds must be serialized with sketch state so distributed workers evaluate identical functions before merging; changing a seed changes the coordinate system and makes direct counter-wise merging invalid.

For a public endpoint, an adversary may observe outputs and choose later keys. Information-theoretic pairwise independence describes a seed selected independently of a fixed key set; it does not automatically protect a reused, exposed seed against adaptive collision finding. If denial-of-service resistance is required, a keyed cryptographic hash or periodic secret rotation may be preferable even when it is slower. Likewise, using a noncryptographic PRNG to expand a short seed changes the claim from exact $k$-wise independence to a computational or empirical assumption unless the generated family has a proof.

Evidence that invalidates a choice includes failed exhaustive tests on a small field, biased coefficient sampling, unexpectedly correlated row errors, seed reuse where the proof needs separation, cross-language arithmetic disagreement, overflow that no longer implements the stated field, range-reduction bias, or an adaptive attack that raises collision rates.

flowchart TD
    A[Expand the sketch proof] --> B[List every joint hash product]
    B --> C[Find maximum distinct-variable degree k]
    C --> D[Select family with proved order at least k]
    D --> E[Specify field domain range and seed format]
    E --> F[Test exhaustive small cases and vectors]
    F --> G{Inputs adaptive or seed exposed?}
    G -->|yes| H[Add keyed cryptographic protection or revise model]
    G -->|no| I[Benchmark cost and deploy]
    H --> I
    I --> J[Monitor bias correlation and merge compatibility]
    J --> K{Evidence matches assumptions?}
    K -->|yes| J
    K -->|no| L[Reject rotate or upgrade family]
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
    classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
    class A,B,C navy;
    class D,E,F purple;
    class I,J teal;
    class G,H,K,L crimson;

Select Independence from the Proof

The reliable workflow runs backward from the theorem. Expand the estimator and its failure proof until every expectation is expressed as monomials in hash-derived variables. Count distinct inputs in the largest monomial, not merely the written exponent. Then select and implement a family with at least that independence order, including domain encoding and range reduction in the claim.

This connects backward to basic hash collisions and randomized streaming models. It connects forward to Count-Min, Count Sketch, AMS moments, sparse recovery, pseudorandom generators, and adversarially robust streaming. In each topic, replacing “assume a random hash” with a named family, seed format, and verified proof obligation turns an idealized algorithm into an auditable system.