Expected is not average

The words “on average” are not a number separated three things the word “average” is used for: the average case, the expected case, and the amortised cost. That essay had one worked example, quicksort’s pivot, and treated the distinction as a caution about vocabulary.

This one treats it as the organising fact of an entire field. Three unrelated problems — sorting, searching, hashing — each have a deterministic solution with an average-case guarantee and a randomised solution with an expected-case one. In each pair, the two guarantees look interchangeable when written down and behave completely differently when the input is chosen by somebody who has read the code.

The two statements, written out #

Average case. The cost, averaged over a distribution of inputs that the analyst assumed. First-element quicksort is average-case $\Theta(n\log n)$ given a uniformly random permutation. The guarantee is conditional on the data looking a particular way.

Expected case. The cost, averaged over the algorithm’s own random choices, for a fixed input. Randomised quicksort is expected $\Theta(n\log n)$ on every input. There is no condition on the data, because the data no longer selects which case arises.

Three consequences separate them, and only the first is usually mentioned.

The average case has a precondition and the expected case does not. This is the familiar half. If the input distribution differs from the assumed one, the average-case bound says nothing at all — not “roughly the same thing”, nothing. First-element quicksort’s average-case bound is silent about sorted input, and sorted input is where it costs $\binom{n}{2}$.

The precondition is usually unverifiable. “The keys are uniformly distributed” is not a property of an algorithm; it is a property of a program’s callers, and it is rarely checked, rarely documented, and frequently false in a way nobody notices until the data changes. The expected-case bound has no precondition to check.

An adversary can violate the precondition and cannot violate the coins. This is the half that makes the distinction consequential rather than pedantic, and it is what the three pairs above measure.

The three pairs, measured #

At $n = 2{,}048$, each on the input that is worst for the deterministic member of the pair:

Three things are worth saying about this table before anything else.

The deterministic numbers are not bad luck; they are exact. 2,096,128 is $\binom{2048}{2}$ — every possible pair of elements compared, which is the maximum a comparison sort can reach. 2,047 is $n-1$, a spine. 2,048 is every key in one bucket. These are not tail events, they are the certain outcome of the input in question.

The inputs are all ordinary. Sorted data arrives constantly — from a database with an index, from a previous sorting stage, from timestamps. Keys that collide under a hash that takes the low bits of an integer are just multiples of the table size, which is what pointers, aligned identifiers and anything counted in pages produce. None of these requires an attacker. They require a Tuesday.

And an attacker makes them worse, deliberately. Which is the subject of the essay that follows this one, and is where the distinction stops being about robustness and becomes about security.

The claim that survives, stated precisely #

It is easy to overclaim for randomisation, and the overclaim is common enough to be worth refuting with the same measurements.

Randomisation does not make the bad case impossible. Randomised quicksort can pick the minimum as its pivot every single time. The probability is $1/n!$, which at $n = 2048$ is a number with over five thousand zeros after the decimal point, and it is not zero. A treap can draw priorities in increasing key order and produce a spine — again, possible, again astronomically unlikely.

What it does is make the bad case independent of the input. Before: the algorithm is fast if the data is nice. After: the algorithm is fast unless the coins go badly. The first is a claim about something outside the program’s control; the second is a claim about something the algorithm brought with it.

That is the entire content of the switch, and it is worth being exact about what it costs. Three things, each measured elsewhere in this phase: the algorithm needs a source of randomness, which is a resource with a count; its behaviour stops being reproducible run to run, which makes a performance bug harder to chase; and it gains a variance it did not have, which for some algorithms is small and for others is not.

Concentration is what makes the expectation usable #

An expected-case bound on its own is a weak statement, and it is worth seeing how weak before treating it as a guarantee.

“Expected cost 26” is compatible with a distribution in which half the runs cost 2 and half cost 50. It is compatible with 99% of runs costing 1 and 1% costing 2,527. An expectation constrains one number about a distribution and says nothing about its shape, so an algorithm with a good expected bound and a heavy tail is an algorithm that will be fine on the day it is benchmarked and terrible on some later day.

So the second measurement, always, is the spread. Across two hundred independent builds of the same 2,048 keys:

Randomised selection has an expected bound as clean as any in this essay and a relative spread of about 25%, with the worst seed costing more than three times the best. That is not a defect in the algorithm; it is what an expected bound permits. The difference between it and the skip list is a fact about their distributions, and no amount of reading their asymptotic classes reveals it.

The rule this suggests is simple enough to state as one: an expected-case bound is a claim worth acting on only when it comes with a measured spread. The bound says where the mass is centred; the spread says whether “centred” means anything.

The three pairs at four settings #

The plate is three problems solved twice each, and the claim is about the pattern rather than about these numbers — so the same construction is run at three more settings.

And twice it, which is the direction that says whether the gap is a constant or a class.

The other two parameters are the table’s width and the seed the randomised half is given, and neither should change the shape.

Why the same trick works three times #

The three pairs are unrelated problems and the repair is structurally identical in all three, which is worth naming because it is the reason this is a technique rather than three coincidences.

In each case the deterministic algorithm makes a choice that the input can predict, and the randomised one makes the same choice by coin.

• Quicksort chooses a pivot. The first-element rule lets the input decide which element that is.
• A binary search tree chooses a root, and then a root for each subtree. Insertion order decides them all.
• A hash table chooses a bucket. A fixed function lets the key decide it deterministically.

The pattern is: find the point at which the input is choosing something on the algorithm’s behalf, and take the choice away from it. Once that is done the input’s ability to construct a bad case is gone, because the bad case is no longer a function of the input.

And the pattern has a matching failure, which is what happens when the choice is taken away from the input and given to something the adversary can still see. That is not a different problem; it is the same problem one level up, and it is why a hash “family” whose member is fixed at compile time is exactly as breakable as a fixed hash. The randomisation has to be at run time, from a source the caller cannot observe, or it is decoration. This is the point at which the pattern stops being about robustness and starts being about who knows what, and it is what the adversary who knows the seed is about.

There is a fourth instance of the pattern worth mentioning because it is the one people meet first and rarely recognise as the same thing: shuffling a deck before dealing. The deterministic algorithm — deal from the deck as it lies — is fine on average over a randomly ordered deck and catastrophic against a deck somebody stacked. Shuffling does not make a bad deal impossible; it makes it independent of who handled the cards.

Where average-case is the right tool #

Having spent five sections on what is wrong with average-case guarantees, the honest section is the one about where they are correct and preferable.

An average-case analysis is a statement about the problem as it actually occurs, and sometimes that is the statement wanted. If a system’s inputs are genuinely drawn from a known distribution — measured, not assumed — then the average-case bound over that distribution is a direct prediction of behaviour, and the expected-case bound over the algorithm’s coins is a strictly weaker one because it has to hold for inputs that never arrive.

Two examples from this site. Linear probing’s expected probe count is an average over the load factor and the hash’s behaviour, and it is a useful number precisely because the assumption behind it — that the hash spreads the keys roughly uniformly — is checkable against a filled table. And what amortised means is a third kind of statement altogether: a guarantee about a sequence, with no averaging over anything random, which holds absolutely and is the strongest of the three.

The failure is not using an average case. It is using an average case while describing it as though it were an expected case — saying “quicksort is $n\log n$” and leaving out which of the two claims is meant, when only one of them survives the data being sorted already.

A related case is worth separating out because it is often confused with the average case and is not one. A randomised algorithm and a probabilistic input model can be combined, and then there are two sources of averaging in play at once. Randomised quicksort on uniformly random input has an expected cost averaged over both the coins and the data, and that number is smaller and less useful than the expected cost on a worst-case input — which for randomised quicksort happens to be within a constant factor, and for other algorithms is not. Whenever two averages are being taken, the question worth asking is which of them the guarantee is over, and whether the answer is “both” by accident.

The word that does the damage #

Both statements are written with “average”, and the collapse is nearly always in the same direction: an average-case bound gets quoted and then relied on as though its precondition were part of the algorithm.

The tell is whether the sentence can be completed with “…for every input”. Randomised quicksort is expected $\Theta(n \log n)$ for every input. First-element quicksort is average-case $\Theta(n\log n)$ for — and here the sentence has to stop and name a distribution, and if it cannot, the claim has no content.

Three habits follow, and they are cheap:

1. Say which one. “Expected” for the coins, “average-case over $D$” for the data, and name $D$. A bound whose distribution is not written down is not a bound.
2. Report the spread with the expectation. One number describing a distribution is one number too few, which is the standing argument of distributions, not averages.
3. Ask what the worst input looks like, and whether it is unusual. For all three pairs above the answer is “sorted data, or aligned integers”, and neither is unusual. An average-case guarantee whose bad case is exotic is worth much more than one whose bad case is the default.

The third habit is the one that gets skipped, and it is the one with the most value per minute spent. It takes about five minutes to work out what a deterministic algorithm’s worst input looks like, and the answer is nearly always something with structure — sorted, reversed, all-equal, aligned, periodic. Real data has structure. The category of “inputs an adversary would have to construct” and the category of “inputs that turn up on their own” overlap far more than the phrase “worst case” suggests, which is why the three inputs in this essay’s table are all things a program produces by accident.

The third column, which is neither #

The table has two columns and the pattern above suggests a third, because taking a choice away from the input does not require a coin. It can be taken away by computing it, and each of the three pairs has such an answer with a different price.

Sorting. Choose the pivot by median-of-medians: split into groups of five, take each group’s median, recurse to find the median of those, and pivot on it. The result is a deterministic algorithm with a worst-case linear selection and a worst-case $\Theta(n\log n)$ sort, on every input, with no distribution assumed and no coins spent. Its price is a large constant — the pivot computation is itself a recursive pass — which is why it is the algorithm everybody cites and nobody runs, and why what derandomising costs is a measurement rather than a footnote.

Searching. Rebalance. An AVL or red-black tree makes the shape a function of the keys rather than of their arrival order, so sorted insertion produces a balanced tree and the height is $\Theta(\log n)$ absolutely. The price is bookkeeping on every insertion — rotations, and a stored balance factor or colour per node — where the treap pays a random draw and no rotations beyond what the heap property forces.

Hashing. Use a function nobody can invert cheaply rather than one nobody has chosen randomly. A cryptographic hash is deterministic and its behaviour on a chosen key set is unpredictable in practice, which restores the guarantee against an adversary without any run-time randomness at all. The price is per-evaluation cost, and it is the trade the independence essay prices exactly.

Three answers, three prices, and one common structure: the choice is removed from the input by spending work rather than by spending entropy. Which of the two currencies to spend is a real decision, and the table above is not a case for randomisation over derandomisation — it is a case for either over letting the input decide.

There is one place the third column is strictly better and it is worth naming, because it is why the deterministic answers survive at all. A computed choice restores a worst-case guarantee, and a coin restores only an expected one. A system that must not exceed a latency budget on any single request cannot use a bound that holds in expectation, however tight the concentration — and the sections above show that concentration varies enormously between algorithms with equally clean expected bounds. Where a hard ceiling is required, the coin is not an option and the constant has to be paid.

And there is one place the third column fails outright. Against an adversary who can observe outputs and adapt, a deterministic choice — however expensively computed — is a fixed function that can be probed and then defeated, given enough queries. Median-of-three is the cheap version of the computed pivot and there is a standard construction that defeats it. That is the boundary at which computing the choice stops being enough and only unpredictability will do.

The limit on all of it #

Everything above is measured at one size on one machine with stated seeds, and it inherits the site’s standing limit: a finite measurement can refute a claim and cannot establish an asymptotic one. What the three pairs establish is refutation, which is the direction that works — first-element quicksort’s average-case bound demonstrably does not describe its behaviour on sorted input at $n = 2{,}048$, and no argument about limits changes that.

There is a second limit specific to this essay and it is the one that leads into the next. Every “randomised” measurement here came from a stated seed, so every one of them is, strictly, a deterministic computation whose result is published on this page. The expected-case guarantee is a claim about an algorithm that draws fresh unpredictable randomness at run time. What a seeded figure demonstrates is the distribution — that is what the two hundred builds are for — and not the unpredictability. Those are different properties, only one of them is being measured, and an adversary who knows the seed is the case where the difference is the whole story.