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

Geometric distribution — where it appears

The distribution of how many trials until a first success, which is what a coin-flipped structure's level or leading-zero count follows. It is what a coin-flipped structure's level or leading-zero count follows, and its long tail is why a random structure's height is a distribution rather than a number.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

level 1level 2level 3level 4level 5key 21search: 8 comparisons, 3 hops26 keys, p = 0.5, seed 2026081057 coin flips decided the shape

A structure made of coin flips

Insert the same 512 keys into a skip list twice, once sorted and once shuffled, from the same seed, and the two structures are identical — the same 11 levels, the same height for every key, the same silhouette. Nothing about the data reached the layout. The 1,064 coin flips did all of it.

randomness · Randomness share of nodespredictedlevel 149.68% · 50.00%level 225.29% · 25.00%level 312.52% · 12.50%level 46.24% · 6.25%level 53.08% · 3.13%level 61.64% · 1.56%level 70.79% · 0.78%level 80.34% · 0.39%20,000 nodes, p = 0.5, seed 5150worst departure 0.32 points

The height is a distribution, and the coin is a parameter

A skip list over 2,048 keys is described as being about log₂ n levels tall. Across two hundred builds of exactly those keys its height ranged from 9 to 19. The number in the description is the mean of something, and choosing the coin is choosing which something.

randomness · Randomness

Named alongside it

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

DistributionSkip listBinary searchBinary search treeComparison countConcentrationExpected caseParameter choiceRandomised algorithmRandomised data structureSeeded randomnessTail behaviour

All concepts