Derandomization, in depth: conditional expectations, pessimistic estimators, seed enumeration and pseudorandom generators

Why remove randomness at all

A randomized algorithm uses random bits r in addition to its input x. A Monte Carlo algorithm may be wrong with small probability; a Las Vegas algorithm is always right but its running time is random. Derandomization replaces r by something you can compute: a carefully chosen fixed sequence of decisions, or a short list of candidate seeds you can afford to try exhaustively.

Why bother, when a good random number generator is cheap? Four reasons come up in practice. First, reproducibility: deterministic output is easier to test, cache and diff. Second, adversaries: if an attacker can predict or influence your seed, a randomized guarantee evaporates; deterministic worst-case bounds do not. Third, certificates: a probabilistic proof that a good object exists is not the object, and derandomization constructs it. Fourth, distributed agreement: replicas that must agree on a choice cannot each flip their own coin. The cost is usually extra running time, sometimes a worse constant in the guarantee, and occasionally a much more complex algorithm.

The method of conditional expectations

The method of conditional expectations works whenever the quality of the random outcome is a sum of terms whose expectations you can compute exactly, given that some coins are already fixed. Let Q be the quality and suppose E[Q] is at least some target T. Fix the first coin both ways and compute the two conditional expectations. Because E[Q] is their average, at least one of them is at least E[Q]. Keep that choice, and repeat for the next coin. After the last coin nothing is random any more, so the quality of the final assignment equals its conditional expectation, which never dropped below T.

For MAX-CUT, a uniformly random side for each vertex cuts every edge with probability one half, so E[cut] = m/2. Conditioned on the sides of the vertices placed so far, an edge with both ends placed is cut or not, and every other edge is still cut with probability one half. So the conditional expectation is the number of decided cut edges plus half the undecided edges, and comparing the two choices for vertex v reduces to a local rule: put v on the side opposite the majority of its already-placed neighbours. The randomized algorithm turns into a greedy one, and the analysis turns into a proof that greedy cuts at least half the edges.

For exact-3 MAX-SAT, where every clause has three distinct variables, a random assignment satisfies a clause with probability 7/8. Conditioned on a partial assignment, a clause that is already satisfied contributes 1, and an unsatisfied clause with u unset literals contributes 1 - 2^-u. Each step costs one pass over the clauses, so the naive loop is O(nm); tracking only the clauses that touch the current variable brings it to O(n + m) total.

Tested code: MAX-CUT and exact-3 MAX-SAT

Here are both algorithms. The MAX-SAT version is deliberately the naive O(nm) form so that the conditional expectation is visible; production code would keep a per-clause counter of unset literals and update only clauses containing the variable just fixed.

def maxcut_conditional(n, edges):
    """Place each vertex opposite the majority of its placed neighbours.
    This is exactly the method of conditional expectations; the cut is >= m/2."""
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    side = [None] * n
    for v in range(n):
        zeros = sum(1 for u in adj[v] if side[u] == 0)
        ones = sum(1 for u in adj[v] if side[u] == 1)
        side[v] = 1 if zeros >= ones else 0
    return side


def max3sat_conditional(n, clauses):
    """clauses: tuples of DIMACS literals over 3 distinct variables.
    Fix x1..xn in turn, keeping E[#satisfied] >= 7m/8."""
    assign = {}

    def expected():
        total = 0.0
        for cl in clauses:
            unset, sat = 0, False
            for lit in cl:
                v = abs(lit)
                if v in assign:
                    sat = sat or assign[v] == (lit > 0)
                else:
                    unset += 1
            total += 1.0 if sat else 1.0 - 0.5 ** unset
        return total

    for v in range(1, n + 1):
        assign[v] = True
        e_true = expected()
        assign[v] = False
        e_false = expected()
        assign[v] = e_true >= e_false
    return assign

These were checked against their guarantees: on 500 random graphs with up to 60 vertices both MAX-CUT methods in this article always cut at least m/2 edges, and on 300 random exact-3 formulas the assignment always satisfied at least 7m/8 clauses (the worst observed ratio was 0.89). The 7/8 is essentially the best possible: Håstad proved that beating 7/8 + ε for MAX-E3SAT is NP-hard, so this ten-line derandomization matches the hardness threshold.

Worked example

Take five vertices in a cycle 0-1-2-3-4-0 plus the chord 0-2, so m = 6 and the random expectation is 3. Vertex 0 has no placed neighbours; the tie goes to side 1 and E stays 3. Vertex 1 sees one neighbour on side 1; side 0 cuts edge 0-1 for sure, giving E = 1 + 5/2 = 3.5 versus 2.5 for side 1. Vertex 2 sees vertex 1 on side 0 and vertex 0 on side 1, so either side cuts exactly one new edge: E = 3.5 both ways and the tie goes to side 1. Vertex 3 sees vertex 2 on side 1 and goes to side 0, E = 4. Vertex 4 sees one neighbour on each side, so E stays 4 and the final cut is 4 edges.

The guarantee was 3 and we got 4; the optimum, by brute force over 32 assignments, is 5. That is the honest picture of derandomization: you inherit the randomized guarantee, not optimality. The diagram traces the expectation along the chosen path.

Small sample spaces: try every seed

The second technique notices that the analysis only used a weak property of the coins. The MAX-CUT bound needs each pair of endpoints to land on different sides with probability one half; it never needs all n coins to be mutually independent. Pairwise-independent bits can be generated from a seed of only about log₂ n bits, and a sample space of size about n can simply be enumerated. Some seed must be at least as good as the average, so trying all of them is a deterministic algorithm with the same guarantee.

def maxcut_pairwise(n, edges):
    """side[v] = parity(label(v) AND s), label(v) = v + 1, over every k-bit seed s.
    For two distinct non-zero labels, half of all seeds separate them,
    so the average cut over the seed space is m/2 and the best seed is >= m/2."""
    k = n.bit_length()
    best, best_side = -1, None
    for s in range(1, 1 << k):          # s = 0 cuts nothing; skipping it is safe
        side = [bin((v + 1) & s).count("1") & 1 for v in range(n)]
        cut = sum(1 for u, v in edges if side[u] != side[v])
        if cut > best:
            best, best_side = cut, side
    return best_side

On the worked graph, k = 3 and the seed s = 7 gives sides 1, 1, 0, 1, 0, which happens to be an optimal cut of 5. The same idea generalises: k-wise independent values come from random polynomials of degree k - 1 over a finite field with a seed of O(k log n) bits, and Luby's parallel maximal independent set algorithm was derandomized this way. Small-bias spaces (Naor and Naor) go further: they fool every parity test with seeds of O(log n) bits. The seeds are independent trials, so seed enumeration parallelises perfectly, which is why it is popular in parallel and distributed algorithms where the sequential greedy order of conditional expectations is a bottleneck.

Pessimistic estimators

Conditional expectations need an exact formula. Often the quantity you care about is a probability of failure, say that some constraint in a randomized rounding is overloaded, and that probability has no closed form under partial conditioning. Raghavan's pessimistic estimators fix this. Replace the failure probability by an upper bound U that comes out of the proof, typically a sum of Chernoff-style moment-generating terms, one per bad event. You need three properties: U is below 1 at the start, U is an upper bound on the conditional failure probability at every step, and some choice of the next coin never increases U. Then you walk the coins exactly as before, minimising U instead of maximising an expectation, and you end with U below 1 for a fully determined outcome, which means no bad event occurred.

The design work is in choosing U so that it is cheap to update: usually a sum of products, one per constraint, updated incrementally as each variable is fixed. A union bound over exponentially many events gives an exponentially large estimator, a signal to look for a different proof.

The theory: pseudorandom generators and P versus BPP

Is every efficient randomized algorithm derandomizable? The class BPP holds problems solvable in polynomial time with bounded two-sided error, and the conjecture that P = BPP is widely believed. The strongest evidence is the hardness-versus-randomness line of work: Nisan and Wigderson showed how a hard function yields a pseudorandom generator that stretches a short seed into bits no small circuit can distinguish from random, and Impagliazzo and Wigderson proved that if some problem in E needs circuits of exponential size, then P = BPP. Run the algorithm on every seed of the generator, take the majority answer, and the coins are gone.

Several famous results are derandomizations of specific problems. The AKS test (2002) put primality in P, replacing Miller-Rabin's random witnesses. Reingold (2005) showed undirected connectivity is solvable in logarithmic space, removing the random walk. Nisan's generator fools any space-bounded computation with a seed of O(log² n) bits. And the big open case is polynomial identity testing: random evaluation decides whether an arithmetic circuit computes the zero polynomial, and Kabanets and Impagliazzo showed that derandomizing it would imply circuit lower bounds that nobody yet knows how to prove.

Operational guidance

In engineering terms, choose the technique from the shape of the proof. If the guarantee is an expectation of a sum of simple terms, use conditional expectations. If it is a Chernoff plus union bound, use a pessimistic estimator. If it only needs pairwise or k-wise independence and the seed is short, enumerate seeds, in parallel if you can. If none of these apply, a fixed seed from a cryptographic generator is pseudo-derandomization: reproducible, but with no worst-case guarantee against an adversary who knows the seed.

Measure what you gain. On a 2,000-vertex random graph with 10,155 edges, random assignments cut between 4,950 and 5,139 edges over 20 trials, the best pairwise seed out of 2,047 cut 5,257, and the conditional-expectation greedy cut 6,749. Both deterministic methods guarantee m/2, about 5,078, but greedy's adaptivity bought far more than the bound. Seed enumeration cost 2,047 full passes over the edges; greedy cost one.

Failure modes

• Inexact conditional expectations. Floating-point sums of 1 - 2^-u terms are fine at this size, but for huge formulas compare integer numerators scaled by 8 to avoid tie-breaking noise that silently violates the bound.
• Using a weaker sample space than the proof needs. Pairwise independence suffices for MAX-CUT; it does not suffice for a Chernoff tail bound, which needs much more independence. Check what the analysis actually uses.
• Estimator that is not monotone. If U can rise whichever way you set a coin, the walk can end above 1. Assert U never increases in debug builds.
• Confusing a fixed seed with derandomization. Hash tables seeded with a constant are reproducible and also open to hash-flooding attacks; keep a secret random seed where adversaries choose the input.

Trade-offs

What to do next

1. Pick one randomized algorithm in your codebase and write down which property of the coins its correctness or quality argument actually uses.
2. If the argument is an expectation of a sum, implement the conditional-expectation walk and assert at each step that the expectation never drops.
3. If it needs only pairwise independence, implement seed enumeration and run the seeds in parallel.
4. Re-run the worked example by hand and confirm the expectations 3, 3, 3.5, 3.5, 4, 4.
5. Read the derandomized rounding in randomized rounding and the sample-space construction in pairwise independence.
6. Compare Miller-Rabin with fixed witness sets to AKS, and study Karger's min cut as a case where derandomizing cheaply is still not obvious.