Pairwise Independence, in depth: strongly universal hashing, XOR bits, Chebyshev, and derandomised MAX-CUT

Definitions: universal, pairwise, k-wise

A family H of functions from a domain U to a range R is pairwise independent (also called strongly universal or 2-independent) if, for h drawn uniformly from H, every two distinct inputs x ≠ y and every two outputs u, v satisfy Pr[h(x) = u and h(y) = v] = 1/|R|². Each value is uniform and any two are independent. k-wise independence extends this to every k distinct inputs.

A family is universal (Carter and Wegman's original notion) if only collisions are controlled: Pr[h(x) = h(y)] ≤ 1/|R| for x ≠ y. Strong universality implies universality, not the reverse. The difference matters as soon as an analysis uses the value of h(x), not just whether two values collide.

The (ax + b) mod p family

Let p be prime and work in Z_p. Define h_a,b(x) = (a·x + b) mod p with a and b drawn uniformly from all of Z_p. Claim: this family is pairwise independent on Z_p. Proof: for x ≠ y, the pair of equations a·x + b = u and a·y + b = v is a linear system in (a, b) with determinant x − y ≠ 0 mod p, so it has exactly one solution for each (u, v). Of the p² equally likely seeds, exactly one maps (x, y) to (u, v): probability 1/p².

A common implementation shortcut breaks this: drawing a from 1..p−1 to avoid the constant function. With a ≠ 0, h(x) = h(y) would require a(x − y) = 0, which is impossible, so the family never collides on distinct inputs. That is fine for a permutation, but it is no longer pairwise independent. An exhaustive check with p = 7 and inputs 2 and 5 shows both facts:

from collections import Counter
p = 7
full = Counter(((a*2 + b) % p, (a*5 + b) % p) for a in range(p) for b in range(p))
nz   = Counter(((a*2 + b) % p, (a*5 + b) % p) for a in range(1, p) for b in range(p))
print(len(full), min(full.values()), max(full.values()))   # 49 1 1
print(len(nz), sum(v for (u, w), v in nz.items() if u == w)) # 42 0

With the full family all 49 output pairs occur exactly once. With a ≠ 0 only 42 pairs ever occur, and none of them are collisions.

Shrinking the range. Hash tables want m buckets, not p. The standard Carter–Wegman family is h(x) = ((a·x + b) mod p) mod m with a ≠ 0, and it is universal, with collision probability at most 1/m. It is not exactly pairwise independent, because p values cannot split evenly into m buckets unless m divides p. Measured exhaustively with p = 101 and m = 10 over every pair of inputs, the worst-case collision probability is 0.0911 with a ≠ 0 (within the 1/m = 0.1 bound) and 0.1001 with a allowed to be zero. A single value is also slightly non-uniform: bucket 0 receives 1,111 of the 10,201 seeds and every other bucket 1,010. Choose p much larger than m and the bias becomes negligible.

Universality is already enough for the textbook hash-table result. With n keys in m buckets, the expected number of other keys sharing a given key's bucket is a sum of n − 1 collision indicators, each with expectation at most 1/m, so the expected chain length is at most 1 + n/m by linearity of expectation alone. No independence between different pairs is used at all.

Many random bits from a short seed

Sometimes you want many random bits, not hash values. Take a seed of k uniform bits s and, for every non-empty subset S of {1..k}, output the parity b_S = ⊕_i∈S s_i. That is 2^k − 1 bits from k. Each b_S is uniform because it is the parity of at least one fair bit. For S ≠ T, there is an index in exactly one of them, and flipping that seed bit changes one parity but not the other, which makes the pair uniform over all four outcomes.

The bits are not 3-wise independent: b_{1} ⊕ b_{2} = b_{1,2} always. Enumerating all 8 seeds with k = 3 gives only four outcomes for (b_{1}, b_{2}, b_{1,2}): 000, 101, 011 and 110, each twice. That is precisely why the construction is so cheap, and why it must only be used where the analysis needs nothing beyond pairs.

When you do need more, the linear family generalises directly. Draw k coefficients uniformly from Z_p and evaluate the polynomial h(x) = c_k−1x^k−1 + … + c₁x + c₀ mod p. For k distinct inputs, the values are related to the coefficients by a Vandermonde matrix, which is invertible over a field, so every k-tuple of outputs comes from exactly one coefficient vector. The seed grows to k numbers and evaluation to k multiply-adds with Horner's rule; that is the whole cost of buying 4-wise independence for an AMS sketch.

Why pairs suffice: variances add

Why do pairs suffice so often? Let X = X₁ + … + X_n. Then Var(X) = Σ Var(X_i) + Σ_i≠j Cov(X_i, X_j). Each covariance involves only two variables, so under pairwise independence every covariance is zero and variances add exactly as in the fully independent case. Chebyshev's inequality, Pr[|X − E X| ≥ t] ≤ Var(X) / t², needs nothing else.

Sampling with two random numbers. To estimate the fraction μ of items in a population of size p that satisfy a predicate, evaluate it at the points h(1), …, h(t) for one random h_a,b. The sample points are pairwise independent and uniform, so the sample mean has variance at most 1/(4t), and Pr[|mean − μ| ≥ ε] ≤ 1/(4tε²). For ε = 0.05 and 10% failure probability, t = 1,000 samples suffice, using two random numbers instead of a thousand.

What you lose is the tail. Full independence gives Chernoff bounds where failure probability falls exponentially in t; Chebyshev falls only as 1/t. The standard repair is the median trick: run r independent copies, each from its own two-number seed, and take the median. Each copy fails with probability at most 1/4, so the median fails only if half of them do, which happens with probability exponentially small in r. Count Sketch and the AMS estimator use this median-of-copies structure. Count-Min is a close cousin: its error is one-sided, so it takes the minimum over independent rows, each bounded with Markov's inequality; see Count-Min Sketch in depth.

Derandomising MAX-CUT

Small seeds make derandomisation possible: if an algorithm only needs pairwise independence and the seed space has polynomial size, try every seed. MAX-CUT is the classic example. Put each vertex on a random side; an edge is cut when its endpoints differ, which happens with probability 1/2 if the two sides are independent, so the expected cut is m/2. That argument touches only pairs of vertices.

Assign vertex v the parity bit for subset v + 1 of a k-bit seed with 2^k − 1 ≥ n. The average cut over all 2^k seeds is exactly m/2, so at least one seed achieves m/2 deterministically:

import random
rng = random.Random(42)
n, edges = 200, set()
while len(edges) < 1500:
    u, v = rng.randrange(n), rng.randrange(n)
    if u != v:
        edges.add((min(u, v), max(u, v)))

k = n.bit_length()                       # 8: 2^8 - 1 = 255 >= 200 subsets
def side(seed, v):                       # parity of seed bits in subset v+1
    return bin(seed & (v + 1)).count("1") & 1

cuts = [sum(side(s, u) != side(s, v) for u, v in edges) for s in range(2 ** k)]
print(sum(cuts) / len(cuts), max(cuts), min(cuts))   # 750.0 807 0

On this 200-vertex, 1,500-edge random graph the 256 seeds average exactly 750.0 cut edges, which is m/2, the best seed cuts 807, and the worst cuts 0 (seed 0 puts every vertex on the same side). The running time is O(n·m), and the guarantee is deterministic, not "with high probability". The same pattern, a small sample space enumerated exhaustively, underlies many derandomised algorithms; compare the conditional-expectations approach in randomized rounding.

In practice: fast families and their limits

Engineering choices for production hashing:

• Use a Mersenne prime. With p = 2⁶¹ − 1, reduction mod p is a shift, a mask and an add, avoiding a division. Keys must be smaller than p or first reduced; keys x and x + p collide under every function in the family.
• Multiply-shift on machine words. Dietzfelbinger's multiply-add-shift scheme replaces the prime with arithmetic mod 2^w and a right shift; with suitably wide random a and b it is strongly universal and much faster than a mod-p implementation. Thorup's notes on high-speed hashing give the exact bit widths.
• Strings and tuples. Hash variable-length keys to a word with a polynomial or tabulation hash first, then apply the pairwise layer; see perfect hashing for a full two-level design.
• Know when two is not enough. The AMS estimator of the second moment needs 4-wise independent signs for its variance bound. Linear probing gets expected constant time with 5-wise independence (Pagh, Pagh and Ružić, 2007), and Pătraşcu and Thorup (2010) showed some 4-wise families make it logarithmic.

Failure modes

What to do next

1. Write the (a·x + b) mod p family with a Mersenne prime and repeat the exhaustive pair check on a small prime.
2. For each randomised component you own, write down whether its analysis needs universal, pairwise or k-wise independence, and check that the hash matches.
3. Replace per-item random draws in a sampling job with one pairwise seed and verify the Chebyshev error bound empirically.
4. Implement the median-of-copies wrapper and measure how failure rate falls with the number of copies.
5. Derandomise one small randomised routine by enumerating its seeds, as in the MAX-CUT example.
6. Read how locality-sensitive hashing deliberately does the opposite, making similar inputs collide.