The independence an estimator spends

Every analysis in this field opens the same way. Let $h$ be a hash function chosen uniformly at random from all functions $U \to [w]$. Then the proof proceeds, the bound comes out, and nobody returns to the first line.

The first line is false. A function chosen uniformly from all functions on a universe of $2^{32}$ keys takes $2^{32} \cdot \log_2 w$ bits to write down — for $w = 64$, twenty-five gigabytes — and a summary that needed one would be a summary that had already lost. What is used instead is a family small enough to store, and the entire question is how much of the proof survives the substitution.

The answer is a number, it is a property of the family, and this essay measures it.

What the degree is #

A family $\mathcal{H}$ is $j$-wise independent if, for any $j$ distinct keys $x_1, \dots, x_j$ and any $j$ values $v_1, \dots, v_j$, a uniformly drawn $h \in \mathcal{H}$ satisfies $h(x_i) = v_i$ for all $i$ with probability exactly $w^{-j}$.

Two readings, and the second is the useful one.

The first: $j$ keys’ hash values look like $j$ independent uniform draws. The second: knowing $j-1$ of them says nothing about the $j$-th. For a family of degree exactly $j$, knowing $j$ of them decides the $j+1$-th entirely, which is why the failure is so abrupt.

The standard construction is a polynomial. Take a prime $p$, draw $a_0, \dots, a_{j-1}$ uniformly from $\mathbb{Z}_p$, and set $h(x) = (\sum_i a_i x^i \bmod p) \bmod w$. It is $j$-wise independent because a polynomial of degree $j-1$ is determined by its values at $j$ points and there is exactly one such polynomial for each choice of those values — so the map from coefficients to value tuples is a bijection. And it stops there for the same reason: given $j$ points the polynomial is pinned, so the $j+1$-th value is a function of the others rather than a free choice.

Enumerated, not estimated #

Over $\mathbb{Z}_{13}$ a family of $k$ coefficients has $13^k$ members. For $k = 4$ that is 28,561 — few enough to walk every one of them and tabulate what it does.

That is what the figure above is. For $j$ keys the $13^j$ tuples of values are counted across all members, and $j$-wise independence is the statement that every count is exactly $13^{k-j}$. There is no tolerance in it, no seed, and no statistic: a cell is right or it is not.

The failures beyond the degree have the same number in every row, and the number is worth stating: exactly $(p-1)/p = 92.3\%$ of the tuples are unreachable. For $j = k+1$ the first $k$ values determine the last one, so of the $p$ possible values for the final key, exactly one occurs and $p-1$ do not. At $j = k+2$ it is $(p^2-1)/p^2 = 99.4\%$, and so on.

That is a fact about a family over a thirteen-element field, established by exhaustion. Everything below is about families over $2^{31} - 1$, where exhaustion is not available and the honest description of what can be measured is a good deal weaker.

Where the estimator spends it #

The tug-of-war estimator is one register holding $Z = \sum_x s(x) f_x$, reported as $Z^2$. Expanding the square gives

$$Z^2 = \sum_x f_x^2 + \sum_{x \neq y} s(x)s(y)\, f_x f_y.$$

The expectation of every term in the second sum is $\mathbb{E}[s(x)s(y)]$ times a constant, and that is zero as soon as two distinct keys’ signs are independent. So the mean is exactly $F_2$ at degree two, and no more is needed for it.

The variance is $\mathbb{E}[Z^4] - F_2^2$, and $Z^4$ expands into products of four signs. Terms like $s(x)s(y)s(z)s(t)$ for four distinct keys must vanish, and terms like $s(x)^2 s(y)^2$ must be one; neither is controlled by pairwise independence. The bound $\mathrm{Var}[Z^2] \le 2F_2^2$ is a theorem about a four-wise family, and against a merely pairwise one there is no bound at all.

So the two halves of the same analysis buy different amounts of the same thing, and the phrase “assume a random hash” conceals both purchases.

What it is worth, measured #

Two hundred draws each, sixteen registers, the same 20,000-item stream, everything identical but where the signs come from:

The first two rows are the measurement this essay exists for. Both estimators are centred — the pairwise one’s mean is inside its own standard error of zero — and the pairwise one’s spread is 1.78 times larger, with a worst run three times as bad. The theory says the mean survives and the variance does not; the measurement says the mean survived and the variance grew by 78%.

The third row is a family with no pairwise independence at all, and it is biased: 10.9% high against a standard error of 2.6%, which is four standard errors. The fourth row is a fixed function rather than a family, and it is not an estimator in any sense — every run returns the same wrong number, and the spread of zero would look like extraordinary precision to anybody measuring only the spread.

The plateau is the finding #

That last line deserves its own heading, because it is the practical form of everything above.

Averaging $s$ estimators divides the variance by $s$ when the estimators are independent of each other and each has a bounded variance. A family too weak to bound the variance of one register does not stop the estimator from working; it stops the extra registers from buying anything. The sketch continues to return numbers, they continue to be roughly right, and the money spent on state stops converting into accuracy.

At 640 registers the weak family is at 17.0% — worse than the four-wise family at forty registers, which is 17.5% for a sixteenth of the state. A practitioner who measured accuracy at one size, found it acceptable, and then scaled the structure up would find the second half of that budget had bought nothing, with nothing in the output to say why.

What a degree costs to run #

A degree is not free and its price is easy to state exactly, which is unusual for anything in this essay.

Storage. $k$ coefficients of $\lceil \log_2 p \rceil$ bits. At $p = 2^{31}-1$ that is 31 bits each, so a four-wise family is 124 bits against a pairwise family’s 62. Beside a sketch holding twenty thousand bits it is nothing, and beside a five-bit register bank it is not.

Arithmetic. Evaluating a polynomial of degree $k-1$ by Horner’s rule is $k-1$ multiplications and $k-1$ additions, each modulo $p$. Doubling the degree doubles the work per key per hash, and the previous section’s accounting — 640 hash evaluations per arrival at the largest setting — is multiplied by it.

There is one piece of arithmetic here that is worth naming because getting it wrong is invisible. Multiplying two numbers below $2^{31}$ produces up to sixty-two bits, and a double carries fifty-three. The obvious expression (a * x) % p therefore returns the modulus of a rounded product, which is uniform-looking garbage — and a family built on it distributes keys perfectly well, passes the generic meter above, and has no independence of any degree. The multiplication is split so that it stays inside a double, and it is shared with the hashing library rather than written twice, because a second body for it would be a second chance to get it wrong.

Why not simply use a cryptographic hash #

The obvious escape is to stop reasoning about degrees and use a function that behaves randomly for every purpose anybody has tried — SipHash, or a truncated SHA-256.

It is a real answer and it is what most deployed sketches do. Two things are worth saying about it, and neither is that it is wrong.

It replaces a proof with an assumption that is much harder to state. “This family is four-wise independent” is a theorem with a two-line proof. “No adversary bounded by such-and-such resources can distinguish this function from random” is a cryptographic assumption, and the accuracy of a sketch built on it is a corollary of that assumption rather than of anything provable about the structure. For a summary whose whole appeal is a stated guarantee, that is a real trade rather than a free upgrade.

It costs more per evaluation than the property being bought. A SipHash round is several times the arithmetic of a degree-four polynomial, and the sketch above evaluates its hash hundreds of times per arrival. Where the required degree is known — and for this estimator it is exactly four — buying more than that is buying something the analysis cannot use.

The recommendation this site will make is the one it makes everywhere: state which property the argument consumes, and then buy that property. The estimator needs four-wise independence for its variance and two for its mean, both of those are theorems, and a family of four coefficients supplies both for 124 bits.

Measuring a family that cannot be enumerated #

The families that actually run are over $p = 2^{31} - 1$ with up to $2^{124}$ members. Enumeration is not available, and what is left is sampling: draw the family many times, tabulate the sign patterns of $j$ fixed keys, and compare the counts with uniformity by a chi-square statistic.

It works, in the sense of producing a number. It does not work, in the sense of establishing anything.

The trouble is that independence is a property of a family over all tuples of keys, and a meter only ever sees the tuple it was handed. Six keys chosen without reference to the family are overwhelmingly likely to be six keys on which the family behaves.

Choose them with reference to the family instead:

What the meter can and cannot say #

Collecting the three sets:

Three things this table says, and one it does not.

A sampled meter reports finding nothing, which is not the same as independence. Every entry in the generic column is a five, and three of those families are not five-wise independent. The correct reading of a passing chi-square is “these six thousand draws on these six keys gave no evidence against”, and that sentence is nearly worthless on its own.

A meter with well-chosen probes catches the family that fails hardest. Multiply-shift is caught at two keys by a factor of two thousand, not by a marginal statistic. When a family has a deterministic relationship in it, the right probe finds it decisively.

And it misses the family that fails by the least. Carter–Wegman is exactly two-wise independent and no meter here reports 2 for it; the best any probe set manages is 3. Its three-key failure is a bias in the parity of a linear function over a large prime, which is real, is provable, and is far too small to see in six thousand draws.

What the table does not say is that any family here is fit for any purpose. That is decided by which moments of which estimator the family has to support, and by nothing about the family alone.

Which degree each structure in this collection needs #

The tug-of-war estimator spends two on its mean and four on its variance, and that pattern is not shared by its neighbours. Collecting the requirements makes the point that a degree is bought per argument rather than per field.

Count-Min needs two. Its guarantee is an expectation followed by Markov’s inequality: the expected collision mass in a cell is $\varepsilon\lVert f\rVert_1$ provided any two distinct keys land independently, and the failure probability comes from repeating that over $d$ rows rather than from any higher moment. Pairwise is the whole purchase, which is why a Count-Min sketch built on Carter and Wegman’s family is on exactly as firm ground as one built on anything stronger.

Count-Sketch needs four, for the same reason the tug-of-war estimator does and in the same place. Its cell is a signed sum, its analysis bounds a variance, and a variance of a signed sum is a statement about products of four hash values.

A quantile summary needs none. Greenwald–Khanna has no randomness in it at all, so the column is empty rather than small — which is the trade the model essay in this collection draws out, and it is visible here as a structure that cannot spend a resource because it never had a use for one.

And a cardinality estimator’s requirement is not known to be a degree. The standard analysis of HyperLogLog assumes a fully random function, and the register a key lands in and the run of zeros it contributes are both derived from the same hash value — so the argument is about the whole distribution of the hash rather than about any fixed number of keys at a time. Families with proven guarantees for it exist and are not the polynomials above.

Two things follow from reading that list rather than any one row of it.

The requirement is a property of the proof, not of the structure. “This estimator needs degree four” is shorthand for “the argument used here needs degree four”, and a sharper argument can lower the number without changing a line of the code. That is not hypothetical — several results in this literature are exactly that, a known structure re-analysed under a weaker family. So the honest form of a requirement names the analysis it comes from.

And the requirement cannot be discovered by measurement. Nothing in the plates above would distinguish a structure that needs four from one that needs two; both look fine on a good family and both look plausible on a bad one until the state is scaled. The degree comes out of reading the proof and asking which moment it bounds, which is a paper exercise, and it is the only route to the number.

And one property that is not a degree at all #

The title of this essay says independence has a degree, and that is true of the property the polynomials supply. It is not true of every property an estimator can need, and the counterexample is in this collection already.

A bottom-$k$ sketch keeps the $k$ smallest hash values in the stream and estimates the cardinality from them. What its analysis requires is that each key be equally likely to be the minimum of any given set — that for any set $S$ and any $x \in S$, the probability that $h(x)$ is the smallest value in $h(S)$ is $1/|S|$. That is min-wise independence, and it is a statement about the ordering the hash induces rather than about the joint distribution of any fixed number of values.

The two properties do not contain one another in the way a reader would expect. A family can be $j$-wise independent for a respectable $j$ and still be a poor min-wise family on sets larger than $j$, because a minimum over a large set is a question about all of its elements at once. Exact min-wise families are known to be expensive; the practical answer is an approximate version, where the probability is $1/|S|$ to within a factor, and the sketch’s error inherits that factor.

So “assume a random hash” hides at least two different purchases, and knowing that one of them is a small integer says nothing about the other. The general form of the essay’s rule survives and gets longer: state which property the argument consumes, buy that property, and check that it is the property and not merely the nearest one with a number attached.

The rule this leaves #

The degree of a family is a design parameter, chosen the way a word size or a block size is chosen, and it costs something exact: one more coefficient of storage and one more multiplication per evaluation per unit of degree. Four-wise signs cost twice the arithmetic of pairwise ones and, on the evidence above, are worth it for a variance and unnecessary for a mean.

The failure mode to carry away is the one the plateau shows. A hash that is too weak does not produce obviously wrong answers, and it does not produce error bars that widen honestly. It produces answers that are approximately right and a structure whose accuracy stops responding to its size — which is exactly the symptom a practitioner is least likely to attribute to the hash, and most likely to attribute to the data.