Expected Value in Algorithms, in depth: linearity, indicator variables, tail bounds and simulations that check the maths

What an expectation is, and which average you mean

A random variable X assigns a number to each outcome of a random experiment; for an algorithm, the experiment is the sequence of coin flips it makes and X is something you care about, such as the number of comparisons. The expected value is the probability-weighted average: E[X] is the sum over values x of x times P(X = x). It is the long-run average over many independent runs, not a value any single run is promised to hit.

Two different averages hide behind the phrase "expected running time", and confusing them causes real bugs. In randomized analysis, the input is fixed (possibly chosen by an adversary) and the average is over the algorithm's own coins. In average-case analysis, the algorithm is deterministic and the average is over an assumed distribution of inputs. Quicksort that always picks the first element as pivot has good average-case cost on random permutations and quadratic cost on sorted input, which is exactly what production data often is. Quicksort with a random pivot has the same expected cost on every input. Only the first kind of guarantee survives an adversary, or a user who uploads an already sorted file.

Linearity and indicator variables

Linearity of expectation says E[X + Y] = E[X] + E[Y] for any random variables, and more generally the expectation of a sum is the sum of the expectations. The crucial word is any: X and Y do not have to be independent. That is what makes it so powerful, because the pieces of an algorithm's cost are almost never independent, and you do not have to care.

The companion trick is the indicator variable. For an event A, the indicator I_A is 1 if A happens and 0 otherwise, and E[I_A] = P(A). So the recipe is: write the cost you care about as a sum of indicators, one per thing that might or might not happen; find the probability of each; add them up. You never need the full distribution of X, which is usually hard, only the probability of each small event, which is usually easy.

Example: shuffle n cards. Card k stays in place with probability 1/n, so the expected number of fixed points is n times 1/n = 1, for every n, even though the events are dependent.

Worked example: randomized quicksort

Randomized quicksort picks a uniformly random pivot, partitions, and recurses. Count comparisons. Name the elements by their sorted rank, z_1 through z_n. Two elements are compared at most once, and only if one of them is chosen as a pivot while both are still in the same subarray. So the total is the sum, over all pairs i < j, of the indicator that z_i and z_j are ever compared.

Now price one pair. Consider the block of ranks z_i through z_j, which has j - i + 1 elements. They all stay together until the first time a pivot is chosen from inside the block. If that pivot is z_i or z_j, the pair is compared; if it is anything strictly between, they are split into different subarrays and never compared. Every element of the block is equally likely to be that first pivot, so P(compared) = 2 / (j - i + 1). Summing over all pairs gives exactly 2(n + 1)H_n - 4n, where H_n = 1 + 1/2 + ... + 1/n is the n-th harmonic number, and since H_n is about ln n the cost is about 2n ln n.

The asymptotic form overstates the exact value at practical sizes, which is worth knowing before you use it in a capacity estimate. A simulation of 200 runs on 1,000 elements averaged 11,002 comparisons, within 0.2 percent of the exact 10,985.9, and ranged from 9,780 to 13,227, so individual runs vary by about 20 percent around the mean even though the mean is pinned exactly. The same argument, with different pairs, is how treaps get their expected depth, and the full partitioning code is in the quicksort deep dive.

Geometric trials: retry until success

Many algorithms repeat a random attempt until it succeeds: rejection sampling, picking a random free slot, a randomized retry, a Las Vegas algorithm that is always correct but has random running time. If each attempt succeeds independently with probability p, the number of attempts is geometric with mean 1/p. With p = 0.3 you expect 3.33 attempts.

Conditioning on the first attempt gives E[T] = 1 + (1 - p)E[T], so E[T] = 1/p. The cost is fine while p is bounded away from zero, and terrible when it is not. A free-slot search in a table that is 99 percent full has p = 0.01 and an expected 100 probes; that is why open addressing tables resize long before they are full.

import random

def sample_in_disk(rng=random):
    # Rejection sampling: square has area 4, disk has area pi, so p = pi/4 ~ 0.785
    tries = 0
    while True:
        tries += 1
        x, y = rng.uniform(-1, 1), rng.uniform(-1, 1)
        if x * x + y * y <= 1:
            return (x, y), tries          # E[tries] = 4/pi ~ 1.27

Hashing: loads, collisions and empty buckets

Hashing is the setting where expected value earns its keep in production. Assume a hash function that spreads keys uniformly and independently over m buckets, and insert k keys. The load factor alpha = k/m is the expected number of keys per bucket, by linearity over the k keys. From that one number:

• An unsuccessful lookup with chaining scans a chain whose expected length is alpha.
• A successful lookup examines about 1 + alpha/2 entries on average.
• The expected number of colliding pairs is C(k, 2) / m, by one indicator per pair. With 10,000 keys in 2^20 buckets that is 47.7 pairs, which is why even a sparse table needs a collision strategy.
• The expected number of empty buckets is m(1 - 1/m)^k, by one indicator per bucket. With 1,000,000 keys in 2^20 = 1,048,576 buckets (alpha = 0.954) that is 404,040 empty buckets, 38.5 percent, close to e to the minus alpha.

The last number surprises people: at a load factor just under 1, more than a third of buckets are empty and the keys are piled into the rest. The expectation of chain length is small, but the longest chain is much longer, on the order of log k / log log k, and that maximum, not the mean, sets your worst-case lookup. The uniform-hashing assumption is also doing real work: a weak hash on structured keys, or an attacker who knows your hash, breaks it. That is why language runtimes seed their string hashes; see hash table internals for the engineering side.

The coupon collector

How many uniformly random draws from n types until you have seen all of them? Split the process into phases: phase i starts when you have i - 1 distinct types and ends when you get a new one. In phase i a draw is new with probability (n - i + 1)/n, so the phase is geometric with mean n/(n - i + 1). Linearity over phases gives E[T] = n(1/n + 1/(n - 1) + ... + 1) = nH_n.

For n = 50 that is 225.0 draws, about 4.5 times n, and in general the overhead grows like ln n. This shows up whenever you rely on randomness for coverage: how many random requests until every shard of a cache has been warmed, how many randomized test cases until every branch of a 50-way switch is hit, how many random probes until every node in a gossip protocol has been contacted. The last few types dominate: of the 225 expected draws, the final phase alone (one type left) costs 50.

From averages to guarantees

An expectation says nothing on its own about how often a run is far from it. Three tools convert it into a bound, each needing a little more information.

Markov is weak but needs nothing beyond the mean, so it is the right first step for any non-negative cost. Chebyshev needs the variance, which for sums of independent pieces is just the sum of the pieces' variances. Chernoff-style bounds, for sums of independent indicators, are exponentially tight and are what proves statements like "quicksort uses more than a constant times n log n comparisons with vanishing probability"; they are worth learning next.

Markov also gives an engineering trick. A Las Vegas algorithm with expected time E can be stopped at 2E and restarted with fresh coins: by Markov each attempt fails with probability at most one half, so k independent attempts all fail with probability at most 2 to the minus k. Restarts turn an expected-time guarantee into a high-probability one at constant-factor cost, and the same idea justifies capped retries with fresh randomness in distributed systems.

A simulation harness that checks the maths

Always check an analysis against a simulation. The harness below measures the mean, spread and extremes of any randomized cost function, and compares the mean to your formula. It produced the quicksort figures above.

import math, random, statistics

def harmonic(n):
    return sum(1.0 / k for k in range(1, n + 1))

def quicksort_comparisons(n, rng):
    count = 0
    def go(a):
        nonlocal count
        if len(a) <= 1:
            return a
        pivot = rng.choice(a)
        count += len(a) - 1                 # pivot is compared with every other element
        return (go([x for x in a if x < pivot]) + [pivot]
                + go([x for x in a if x > pivot]))
    go(list(range(n)))
    return count

def check(cost_fn, predicted, runs, seed=1):
    rng = random.Random(seed)
    xs = [cost_fn(rng) for _ in range(runs)]
    mean = statistics.fmean(xs)
    print(f"predicted {predicted:,.1f}  observed {mean:,.1f} "
          f"({100 * (mean - predicted) / predicted:+.2f}%)  "
          f"sd {statistics.pstdev(xs):,.1f}  min {min(xs):,}  max {max(xs):,}")

n = 1000
check(lambda r: quicksort_comparisons(n, r), 2 * (n + 1) * harmonic(n) - 4 * n, runs=200)

If the observed mean misses the prediction by more than a few standard errors (the standard deviation divided by the square root of the run count), either the analysis or the code is wrong, and both are worth knowing. Keep the seed fixed so the check is reproducible in CI, and test adversarial inputs, such as sorted and all-equal arrays, not only random ones: all-equal input is a classic way for a quicksort with a random pivot but a Lomuto-style partition to go quadratic anyway.

Pitfalls

E[f(X)] is not f(E[X]). Linearity holds for sums, not for nonlinear functions. Expected latency of a request that waits for the slower of two calls is E[max(X, Y)], which is larger than the max of the two expectations. For convex costs, Jensen's inequality says the true expected cost is at least the cost of the average.

Fan-out amplifies tails. If one backend call is slow with probability 1 percent, a request that waits for 100 independent calls is slow with probability 1 - 0.99^100, about 63 percent. The expected number of slow calls is exactly 1, which sounds harmless and is not; the event you care about is "at least one", and that is a tail question.

The hidden assumption. Every expected bound is conditional on its randomness model: truly random pivots, uniform hashing, independent failures. A predictable seed, a structured key set or correlated failures void the guarantee silently. Write the assumption next to the bound in your design doc.

Randomized structures that lean on these ideas, such as skip lists, are good places to practise: derive the expected search cost, then simulate it.

What to do next

1. Pick one randomized component in your codebase and write down the random variable that is its cost, and whether the guarantee is over its own coins or over an assumed input distribution.
2. Decompose that cost into indicators and compute its expectation with linearity.
3. Add a tail bound: Markov if you only have the mean, Chebyshev if you can get the variance.
4. Adapt the simulation harness above, fix the seed, and assert in CI that the observed mean stays within a few standard errors of the formula.
5. Run the harness on adversarial inputs (sorted, reversed, all equal, crafted hash collisions).
6. For anything with fan-out, compute the probability that at least one branch hits its slow tail, and set timeouts and hedging from that, not from the mean.
7. Where an algorithm has a random running time, add a cap with restart using fresh randomness.