Variance — where it appears
Named by 10 essays across 5 fields — each of them below, with the objects they name alongside it.
Counting past what the register holds
Morris's counter counts ten million events in five bits by incrementing with probability 2 to the minus c. The estimate is exactly unbiased at every n, its relative error is 71%, and the base is a dial that trades one against the other at a rate of the square root of half of a minus one.
A count read off the leading zeros
Hash every key and watch for the longest run of leading zeros. Seeing k of them is evidence of about two to the k distinct keys — an estimator with a variance so large it is worthless, and the two devices that fix it are the whole of what a cardinality sketch is.
What derandomising costs
Randomised selection finds the median of twenty thousand elements in 3.21 comparisons per element and median-of-medians takes 8.15 — two and a half times as many for the same answer, both linear. The number that decides between them is not either of those. It is that the first varies by 28% from seed to seed and the second by 1.6%.
The estimate that squares the stream
The length of a stream is a counter and the number of distinct keys is a register bank. The sum of the squared frequencies has nothing obvious to count — and one number, one sign per key, and a squaring get within 4% of it in a fortieth of the space.
The probe nobody waits for
Robin Hood hashing makes an inserting key steal a slot from a key that has probed less far. The mean number of probes afterwards is 4.817, and before it was 4.817 — identical, and it cannot be otherwise, because the total displacement is fixed by the hash. What changes is the worst case, from 114 slots from home to 19, and a table reported by its average lookup cost shows no difference at all.
A bucket that becomes a tree
Java's HashMap converts a chained bucket into a red-black tree once it holds eight entries. The comment in the source computes the probability of that happening under a decent hash at about six in a hundred million, so the mechanism is written never to run. Under a hash that fails, the worst lookup falls from 192 comparisons to 8 — and the whole value of the tree is in a case its author does not control.
The estimate that is a median of means
An estimator with a 70% spread is not usable and an estimator with a stated failure probability is. The construction that turns the first into the second is two lines long, it is where every delta in this field comes from, and its exponential is measured here by counting failures rather than by evaluating a bound.
The independence an estimator spends
Every sketch's analysis begins by assuming a truly random hash, and nobody comes back to that line. Independence has a degree, the degree is enumerable over a small field, and an estimator's mean and its variance spend different amounts of it.
A distribution computed rather than sampled
Quicksort with a random pivot makes a random number of comparisons, and every plate on this site reports one draw from that distribution. The distribution itself can be computed exactly — every pivot, every split, weighed — and on sixty-four elements its mean is 360.706 and its standard deviation 36.741. A hundred real runs average 365.98; two thousand average 360.74. The exact answer says how many runs a sample needs, and it is fewer as the input grows.
A decay measured from where it started
An exponentially decayed counter is one number because its weights fade by elapsed time alone. Forward decay keeps a polynomial weight in one number too, by measuring each arrival from a fixed landmark. Its memory is then a share of the time since that landmark: at β = 2 an arrival counts half at 29% of that time. Anchored at the start of a stream, it takes 5.3 seconds to register a fourfold rise twenty seconds in and 83 seconds when the rise comes at five minutes.
Named alongside it
The objects these essays reach for when they reach for this one.
EstimatorRelative errorState bitsDistributionRandomised algorithmSketchUnbiased estimatorStreaming algorithmWorst caseGuaranteeHash familyHash function