Randomized Recurrences and the Indicator Variable Method

Deterministic analysis counts operations on a fixed input. Randomized analysis has an extra variable, the coin flips, and the standard toolkit for handling it is small: linearity of expectation over indicator variables, conditioning on the first random event, and tail bounds to convert an expectation into a statement about single runs. Each tool has a characteristic failure mode, and most incorrect analyses in this area come from applying one where another is needed.

Indicator variables turn a count into a sum of probabilities

The workhorse is the decomposition of a count into indicators. If X counts some class of events and X_e is the indicator that event e occurs, then X = sum_e X_e and E[X] = sum_e Pr[e], with no assumption of independence. The step that requires care is identifying the events so that their probabilities are computable, and the step that is usually skipped in explanations is the one that makes the method useful: the events may be dependent, and the sum is still exact.

A canonical example is the expected number of inversions in a uniformly random permutation of n elements. For each pair of positions i < j, let X_ij be the indicator that the element at i is larger than the element at j. By symmetry the two orders are equally likely, so Pr[X_ij] = 1/2. There are n(n-1)/2 pairs, so the expected inversion count is n(n-1)/4. The indicators are heavily dependent, since knowing that a > b and b > c forces a > c, but linearity does not care.

The second example is the expected number of comparisons in a hash table lookup with chaining and a uniform hash. Let X be the length of the chain at the bucket probed. Each of the m stored keys lands in that bucket independently with probability 1/b for b buckets, so E[X] = m/b, the load factor. The cost is one plus the chain length. The result holds for any hash function that behaves uniformly over the key set. What “behaves uniformly” requires, and whether the keys are adversarial or random, is the part that work on universal hashing addresses.

Indicators are the right tool whenever the quantity of interest is a count of local events and each event’s probability is bounded without conditioning on other events. They are the wrong tool when the probability of an event depends on the state produced by earlier events in a way that cannot be averaged out.

Conditioning on the first step

When the process has a recursive structure, the analysis conditions on the first random choice and writes the expected cost as an average of the costs of the resulting subproblems.

For a randomized selection algorithm that picks a uniform pivot from n elements and recurses into one side, the recurrence is not a recurrence in the usual sense because the subproblem size is a random variable. Let T(n) be the expected cost. Condition on the rank k of the pivot, which is uniform on 1..n. If k is the target rank, the cost is n for the partition. Otherwise the algorithm recurses on a side of size max(k-1, n-k). So

$$ T(n) = n + \frac{1}{n}\sum_{k=1}^{n} T(\max(k-1,, n-k)) $$

The sum can be reorganized by grouping the ranks that give the same subproblem size: max(k-1, n-k) = s occurs for exactly two values of k when s > n/2, and for none below. This yields

$$ T(n) \le n + \frac{2}{n}\sum_{s=\lceil n/2 \rceil}^{n-1} T(s) $$

The standard solution guesses T(n) ≤ cn and verifies by substitution: the sum of cs for s from n/2 to n-1 is at most c times the sum of an arithmetic series, about (3/8) c n^2, and the factor 2/n in front of the sum turns that into (3/4) c n, so the right side is at most n + (3/4) c n, which is below c n when c ≥ 4. The constant is unremarkable; the point is that the verification works because the sum is bounded by an integral, not because the recurrence has a closed form.

The same shape appears in the analysis of randomized incremental construction, where the expected cost of adding the i-th element is the probability that the element changes the structure times the cost of the change. That probability is often bounded by the number of structural features divided by i, which turns the sum over i into a harmonic series and produces the logarithm.

Why the maximum is not the expectation of the maximum

A frequent error is to replace a random subproblem size by its expectation. If the two sides of a partition have expected sizes n/4 and 3n/4, it does not follow that the expected cost equals the cost of a deterministic split into those sizes, because the cost is a convex function of the size and the randomness is applied before the cost. Jensen’s inequality gives the direction of the error: for convex f, E[f(S)] ≥ f(E[S]), so substituting the mean underestimates the expected cost.

The safe route is to bound the cost for each outcome and then average, which is what the substitution above does. When the recurrence resists that, the alternative is to show that with constant probability the split is balanced, and that the unbalanced case contributes a geometrically decreasing amount. That argument gives the same Θ(n) result with a different constant and generalizes more easily to variants.

From expectation to a bound on one run

An expected bound is an average over runs, and a single run can exceed it. Markov’s inequality converts the expectation into a probability: for a non-negative X, Pr[X ≥ t E[X]] ≤ 1/t. For the comparison count of randomized quicksort, this says the probability of exceeding ten times the expectation is at most one in ten, which is far too weak to be useful as a guarantee but is enough to justify a retry strategy.

Chernoff bounds do better when the quantity is a sum of independent indicators. If X is a sum of independent indicators each with probability p, then Pr[X ≥ (1+δ) E[X]] ≤ exp(-δ^2 E[X] / 3) for δ in (0,1). The bound is exponentially small in the expectation, so a deviation of a constant factor has probability exponentially small in n. This is why randomized algorithms with a large number of independent choices can be made reliable by repetition: running the algorithm t times and taking the majority reduces the failure probability to exp(-Θ(t)) when each run fails with probability bounded below 1/2.

The independence requirement is the catch. The indicators in the quicksort comparison count are not independent, so Chernoff does not apply directly. The usual route is to bound the cost by a sum of independent variables that dominates it, or to use a martingale argument with Azuma’s inequality, which requires a bounded difference property rather than independence. Both are standard, and both produce a bound of the form Pr[X ≥ E[X] + t] ≤ exp(-t^2 / (2 sum c_i^2)) where c_i bounds the change from altering one random choice.

Verifying an analysis against a small case

Analytical errors are easiest to catch by enumerating a small instance exactly. For a randomized algorithm whose randomness is a small number of choices, the distribution over outcomes can be computed by iterating all choice sequences and weighting by their probability. For a shuffle of four elements, the 24 permutations each receive exactly one of the 24 choice sequences, and the count is a check on the algorithm, not on a machine.

from itertools import permutations
from fractions import Fraction

def exact_distribution(n):
    # Enumerate all choice sequences of the Fisher-Yates loop and
    # accumulate the exact probability of each resulting permutation.
    dist = {}
    def walk(i, perm, p):
        if i == 0:
            dist[perm] = dist.get(perm, Fraction(0)) + p
            return
        for j in range(i + 1):
            nxt = list(perm)
            nxt[i], nxt[j] = nxt[j], nxt[i]
            walk(i - 1, tuple(nxt), p / (i + 1))
    walk(n - 1, tuple(range(n)), Fraction(1))
    return dist

d = exact_distribution(5)
assert len(d) == 120 and all(v == Fraction(1, 120) for v in d.values())

The same technique checks an expectation: sum count(permutation) × cost(permutation) over the enumerated distribution using exact rationals, and compare with the value the recurrence predicts. For small n the two must agree exactly, and a discrepancy localizes the error to the recurrence or to the probability model, which is more than a simulation with a fixed seed can do. The enumeration is exponential in n and only usable for small instances, which is precisely the regime where hand analysis is most likely to have an off-by-one.

Where the tools stop

Linearity gives the expectation and nothing about the variance. Two algorithms with the same expected cost can differ by orders of magnitude in the probability of a bad run, and the variance is what distinguishes them. Computing it requires the covariances between indicator pairs, which is where the dependence that linearity ignored comes back.

Conditioning gives a recurrence only when the recursive structure is genuinely self-similar. An algorithm whose subproblems have different shapes at different levels, such as a geometric divide-and-conquer that alternates between two partition rules, needs a system of recurrences rather than one, and the solution is a matrix power or an eigenvalue argument.

Tail bounds give a guarantee only under assumptions that are often unstated. Chernoff needs independence; Azuma needs bounded differences; Markov needs only non-negativity but is correspondingly weak. An analysis that quotes a Chernoff bound for a quantity whose indicators are dependent is not a conservative approximation, it is a different statement about a different quantity.

The expected-cost derivations in Randomized Quicksort and The Probabilistic Method both rest on linearity, but they use it in opposite directions: one to compute a cost, the other to prove that a good object exists. The second use is the subject of the next step in the ladder.