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

The height of a red-black tree over $n$ keys is at most $2\log_2(n+1)$. That is a theorem: not usually, not on average, not with high probability — always, for every insertion order and every set of keys, proved from the colour invariant. Anyone sizing a stack for a recursive traversal can use it as a fact.

The height of a skip list over $n$ keys is a random variable with no upper bound at all. It has a mean, it concentrates well, and there is no $n$ for which any height is impossible. Both structures get described as $O(\log n)$ tall, and the two claims are not the same kind of statement.

The number that is not in the table #

The share of nodes at each level is a closed form and the measurement matches it to a fraction of a percentage point. That is reassuring and it is not the quantity a search cost depends on. A search starts at the top lane, so what it needs to know is how many lanes there are — the maximum height over all $n$ nodes, not the distribution of a single one.

The maximum of $n$ independent geometric draws has no clean closed form. It is concentrated around $\log_{1/p} n$ and it drifts upward slowly and without limit, and the measured behaviour is exactly that. Over two hundred builds of the same 2,048 keys:

The mean sits a little above $\log_2 n$, which is right — the expected maximum of $n$ geometric($\tfrac12$) draws is about $\log_2 n + 1.33$. The range is the interesting part. A build came out at 9 and a build came out at 19, on identical keys, and the second is more than twice the first.

This is what it means for a structure’s shape to be a random variable, and it is why the phrase “a skip list is $O(\log n)$ tall” needs reading with more care than the same phrase applied to a balanced tree. The skip list statement is about a mean with a tail; the balanced-tree statement is about a maximum with a proof.

Why it does not matter as much as it sounds #

Having made that distinction as sharply as it deserves, the honest next sentence is that in practice it usually does not bite, and the measurement says why.

The height varying from 9 to 19 sounds alarming until the question becomes what a tall list costs. Extra levels above the useful ones are almost empty: a level that only two nodes reach contributes at most two hops to any search and usually zero. The search cost is not proportional to the height; it is proportional to the height weighted by how much work each level does, and the top levels do almost none.

So the volatile quantity is the one nobody pays for, and the quantity that is paid for concentrates. That is a general property of randomised structures worth naming: the extreme of a distribution and the average of a distribution behave very differently, and which one an algorithm’s cost depends on decides whether the randomisation is safe. Quicksort’s cost depends on the sum over the recursion, which concentrates; the depth of its recursion depends on the extreme, which is why its space claim is the one that fails.

There is one place where a skip list’s height being unbounded really does bite, and it is an implementation detail rather than an analysis one: the array of forward pointers in the head node has to be allocated at some size, and that size is a bound on the height whether the analysis has one or not. Every real skip list caps the level at 24 or 32 and truncates the geometric draw there. That cap is a lie the structure tells, it is harmless — the probability of wanting level 33 with $p = \tfrac12$ is under $10^{-9}$ per key — and it should be in the code with a comment rather than absent and unnoticed.

How the height grows, measured #

If the height is a random variable, the sensible thing to ask of it is not a bound but a growth rate: how does the mean move as $n$ does, and does the spread move with it? Eighty builds at each of five sizes:

The mean tracks $\log_2 n$ with an offset that stays between 1.18 and 1.45 across a 256-fold range of sizes. That is the signature of $\log_2 n + c$ rather than of anything growing faster, and it is the closest a measurement gets to confirming the shape of the expected maximum.

The range is the other half of the answer, and it does something a bound would not suggest: it stays roughly the same absolute width. At $n = 256$ the eighty builds spanned seven levels; at $n = 65{,}536$ they spanned ten. The spread grows slowly enough that as a fraction of the height it shrinks — from 78% of the mean at 256 keys to 58% at 65,536. A larger skip list is a more predictable one, which is the usual behaviour of an extreme value and is worth knowing, because the intuition that more coin flips means more variance is exactly backwards here.

What a level is worth #

The claim two sections ago — that the volatile levels are the ones nobody pays for — is easy to state and easy to check. One build at $n = 16{,}384$, listing how many nodes reach each level:

Fifteen levels. The top five hold five, two, one and one nodes; between them they account for twenty-four of 16,384 keys, or 0.15%. A search that begins at level 15 spends its first four descents looking at a lane with one node in it and hopping nowhere.

So a build that comes out two levels taller than average pays about two extra descents, once, on every search — against a total cost of around 26 comparisons. Two more levels is under a 10% cost increase, which is why a height ranging over a factor of two produces a cost ranging over a factor of 1.38. The volatility is real and it is concentrated in the part of the structure that is nearly empty.

That relationship is not automatic and is worth not generalising from. It holds because the levels are geometrically thinning, so the tall ones are necessarily sparse. A randomised structure whose extreme was proportional to its cost would inherit the extreme’s volatility directly, and that is exactly what happens to quicksort’s stack depth.

The coin is a parameter, and it is not obviously a half #

Everything so far assumed a fair coin. There is no reason it has to be, and the standard analysis says something surprising about what happens when it is not.

The expected search cost of a skip list with promotion probability $p$ is

$$\frac{\log n}{p \log(1/p)}$$

comparisons: $\log_{1/p} n$ levels to descend, and $1/p$ steps expected along each. The denominator $p\log(1/p)$ is what to maximise, and it is maximised at $p = 1/e \approx 0.37$ — not at a half. Worse for the folklore, the expression is symmetric enough around that maximum that $p = \tfrac12$ and $p = \tfrac14$ give exactly the same predicted cost: $\tfrac12 \cdot 1 = \tfrac14 \cdot 2$.

If two values of $p$ predict the same search cost, the choice between them has to be made on something else. So measure all three quantities, over sixty builds each at $n = 8{,}192$:

The predicted costs are 26.00, 26.00 and 34.67, and the measurements land on all three.

What the table actually says #

Read down the columns rather than across the rows and the result is sharper than “the choice does not matter much”.

$p = \tfrac14$ dominates $p = \tfrac12$. It is not equal on the two quantities anyone counts; it is better on both. Fewer comparisons — 24.69 against 25.84, which is inside the noise but on the right side of it — and a third fewer pointers, which is not inside the noise at all: 1.333 per key against 2.000, exactly the $1/(1-p)$ the geometric distribution predicts. A structure that is cheaper to search and smaller is not a trade-off, it is a better setting.

And it is paid for in the resource nothing else measures. A quarter coin needs two bits per promotion decision instead of one, and the expected number of decisions falls by less than the cost per decision rises: 2.667 bits per key against 2.000, a third more randomness. That is the entire price of the improvement, and without the bit counter it would be invisible — the structure would simply look better, with no cost anywhere.

$p = \tfrac18$ is where it turns around. Pointers keep falling, to 1.143 per key, and the comparison count jumps 25% to 30.79. Past a quarter the lanes get too sparse to skip usefully and the search spends its time walking rather than descending. The measurement agrees with the formula’s prediction of 34.67, which is the shape of the curve doing what the derivation says it does.

Pugh’s original paper recommends $p = \tfrac14$, and this is why. It is a recommendation that is easy to state as folklore and easy to check, and the check is three numbers per setting rather than an argument.

The staircase at three settings #

The level counts are a geometric series and the whole page is about reading a distribution rather than its maximum, so the distribution is drawn at three settings of the two parameters that make it.

The third setting changes neither the coin nor the size, only how far down the series the plate is drawn — which is where the maximum actually lives.

Concentration is the guarantee #

The relative standard deviations in the table — 6.9%, 5.8%, 7.8% — are the number that makes any of this usable, and they deserve to be read as a result rather than as an error bar.

An expected-case bound says nothing on its own about the build actually in hand. “Expected 26 comparisons” is compatible with half the builds costing 2 and half costing 50. What rules that out is concentration, and concentration is a measurement.

At 6% relative spread, the mean is a description of essentially every build. The worst of two hundred cost 1.23 times the mean. Nothing in the two hundred came close to the kind of failure a plain binary search tree exhibits on sorted input, where the cost is not 1.2 times the mean but $n/\log n$ times it.

Compare the same measurement made on randomised selection, later in this phase: 24.6% relative spread, with the worst seed costing 1.6 times the mean and the best costing half of it. That is also a randomised algorithm with a good expected bound, and it is a much less comfortable one to deploy. The bounds look the same on paper. The distributions do not, and only one of the two is worth trusting a latency budget to.

This is the theme the site has been building since the words “on average” are not a number: the mean is the least informative summary of a distribution, and for a randomised algorithm the useful question is never “what is the expected cost” but “how far from it can one run land”.

Why the tail is thin, in one paragraph #

The concentration is not luck and the reason is short enough to give. A search’s cost is a sum of $\log_{1/p} n$ independent per-level contributions, each of which is a geometric random variable with mean $1/p$. Sums of many independent bounded-ish variables concentrate — that is the whole content of the Chernoff bounds — and the number of terms here grows with $n$, so the relative spread of the sum shrinks as $1/\sqrt{\log n}$. A larger skip list is a more predictable one for the same reason a longer coin-flipping session gives a head fraction nearer to a half.

That also says where the concentration would fail: a randomised structure whose cost is dominated by one draw rather than by a sum of many has no such argument available, and none of this transfers to it. Randomised selection is the example, and the reason its spread is four times a skip list’s is that the whole run turns on the first two or three pivots.

The cap is not as harmless as the per-key figure suggests #

The level cap is described above as a lie that is harmless, on the grounds that the probability of a key wanting level 33 at $p = \tfrac12$ is under $10^{-9}$. That is a per-key figure and the quantity that matters is per structure, which is the same number multiplied by $n$.

The probability that some key wants a level above the cap $L$ is about $n p^{L}$. At $p = \tfrac12$ and a cap of 32 that is $n \cdot 2^{-32}$, which is negligible at a thousand keys, one in four thousand at a million, and about a quarter at a billion. A billion-key skip list with a cap of 32 and a fair coin truncates roughly one build in four.

So the cap is not a formality at the sizes a structure like this is deployed at, and the arithmetic that says so is the same arithmetic the rest of the essay uses. The condition for the cap to bind is $n p^{L} \approx 1$, which rearranges to $L \approx \log_{1/p} n$ — the expected height. The cap starts to bind exactly when it is set near the height rather than comfortably above it, which is obvious once written down and is not what a fixed constant of 32 encodes.

What truncation actually costs is worth separating from whether it happens, because the two are usually conflated and only one of them is alarming.

Correctness is unaffected. A key that wanted level 35 and is capped at 32 simply joins the top lane. Every lane is still sorted, every search still descends correctly, and the structure has no way to be wrong about anything.

The cost is a longer top lane. Several keys now share the maximum level where one would have stood alone, so a search’s first descent walks further before dropping. At a cap binding one build in four the effect is a fraction of a comparison; at a cap set far below the height it is the structure degenerating towards a sorted list, one lane at a time.

That gives the sizing rule, and it is the essay’s own three-way trade appearing once more. The cap should be $\log_{1/p} n$ plus a margin, so it depends on the coin as well as on the size — and a quarter coin needs a smaller cap than a fair one for the same $n$, because its heights are half as tall. A structure that hard-codes 32 for both is over-provisioned at $p = \tfrac14$ and under-provisioned at $p = \tfrac12$ for a large enough $n$, which is one more entry on the list of things the choice of coin quietly decides.

What is left unmeasured, and stated as such #

Two limits on the above, both real.

Sixty builds is sixty builds. The relative standard deviations quoted here have their own uncertainty, of roughly $1/\sqrt{2 \times 60} \approx 9\%$ of themselves — so 6.9% and 5.8% are not reliably different from each other, and the essay does not claim they are. What the sixty builds do support is that all three settings concentrate to within about a tenth, which is the claim being made.

The tail beyond the sample is not measured and cannot be. Two hundred builds see nothing rarer than about one in two hundred. Whether a skip list can produce a build costing five times the mean is not a question two hundred builds answer, and the honest statement is that the analysis says the probability decays exponentially and the measurement has not looked far enough out to see it. The same limit applies to every tail claim on this site, and it is the reason the figures report the worst observed build rather than the worst possible one.

What can be said is what the figures show: the shape of a skip list is a random variable, the quantity that varies most is the one that costs least, the promotion probability is a parameter with a measurable three-way trade behind it, and a quarter is a better coin than a half on every axis but the one that nothing else on this site would have counted.