Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Random bits — where it appears

The randomness an algorithm spends, counted at the point it is drawn, and a resource two algorithms with identical output can differ on wildly. Two algorithms with identical output can differ wildly in how many they spend, which makes randomness a third resource beside time and space.

Named by 7 essays across 3 fields — each of them below, with the objects they name alongside it.

0.1bits the register neededrelative errora = 2a = 1.5a = 1.2a = 1.1a = 1.05a = 1.02√((a−1)/2), predicted200 runs per base · n = 20,000 · exact counter needs 15 bits72.6% at 5 bits

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.

streaming · Sketch k/n = 0.1250.0810.1250.169position in the streamshare of runs in which it was sampledAlgorithm R, n = 32, k = 4, 40,000 runsworst departure 3.3% · noise 1.4%

One pass, k slots, and two randomness budgets

Reservoir sampling takes a uniform sample of k items from a stream of unknown length in one pass and k slots. The textbook version and a second version draw from exactly the same distribution, and at 65,536 items one of them spends 1,356,399 random bits and the other spends 9,380.

randomness · Randomness 10³10⁴10³10⁴10⁵nrandom bitsskip list, one build — ntreap, one build — nreservoir, Algorithm R — n log nn from 256 to 16,384bits charged including rejections

Counting the coin flips

A skip list spends 2.03 random bits per key and a treap spends exactly 32. Reservoir sampling spends 1,356,399 bits on a stream of 65,536 and a better version spends 9,380. None of those numbers appears in any complexity class any of these structures is described by, and none of the site's other three counters can see them.

counting · Count 1 coefficient13 members2 coefficients169 members3 coefficients2,197 members4 coefficients28,561 members1 key2 keys3 keys4 keys5 keysexact92% gone99% gone100% gone100% goneexactexact92% gone99% gone100% goneexactexactexact92% gone99% goneexactexactexactexact92% goneevery member walked · GF(13) · no tolerance and no seeddegree 1, 2, 3, 4

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.

randomness · Moment 2 halves, ties go left2 choices, ties at randomone choiceload 2 or more14,61015,03717,363load 3 or more2675785,250load 4 or morenone11,236load 5 or morenonenone223load 6 or morenonenone36load 7 or morenonenone2load 8 or morenonenone165,536 keys and buckets, seededbar length is log(1 + count)

The tie that breaks left

Two choices per key, the emptier bucket wins, and when the two are equally full a coin decides. Replace the coin with a rule — split the table into halves and always send a tie to the left one — and on a million keys the buckets holding three or more fall from 9,316 to 4,694, and the busiest bucket drops from four to three. The hashing, the probes and the keys are unchanged, and the rule spends no randomness at all.

randomness · Randomness independent hashestwo values, h₁ + i·h₂2 choices, load 2+60,41859,9942 choices, load 3+2,2832,3672 choices, load 4+123 choices, load 2+46,45646,2433 choices, load 3+138145262,144 keys and buckets, seededbar length is log(1 + count)

Choices that are not independent

The power of two choices is analysed for choices drawn independently, and computing four independent hashes per key costs four hash evaluations. Compute two and take the choices to be h₁, h₁ + h₂, h₁ + 2h₂ and h₁ + 3h₂, and the choices are about as far from independent as they could be. On a million keys the buckets holding two or more come to 147,536 against 147,367 for four independent hashes, and the busiest bucket holds three either way.

randomness · Randomness 3579111311.523510positions per key, krate ÷ the independent rateh₁ + i·h₂h₁ + i·h₂, step oddh₁ + i·h₂ + (i³ − i)/6optimal load m·ln 2 / k; one set of hash functions per schemedashed: the account

Two hash values and the keys they copy

A Bloom filter that makes its k bit positions from two hash values, as h₁ + i·h₂, answers yes to 1.6% of absent keys on a 64-bit filter where k independent hashes answer 0.69%. The penalty is not the one expected. With the step forced odd no key ever repeats a bit, while a quarter of independent keys do. What costs the filter is a query whose start and step reproduce a stored key's whole progression, which happens with probability 4n/m², measured to within a few per cent from 64 bits to 4,096. The penalty fades as the filter grows and returns as the hash count rises — 1.13 times at seven positions on 1,024 bits, 5.35 times at thirteen.

randomness · Randomness

Named alongside it

The objects these essays reach for when they reach for this one.

DerandomisationHash familyHash functionIndependence assumptionk-wise independenceMeasured countBucket loadEstimatorMaximum loadRandomised algorithmStreaming algorithmTail behaviour

All concepts