The Probabilistic Method in Derandomized Form: Conditional Expectations and Small-Bias Spaces

Randomization buys expected-case guarantees and costs a source of entropy, reproducibility, and a small probability of failure. Derandomization is the business of getting the guarantee without the coin flips, and it comes in two strengths. The first removes the randomness from a specific algorithm while keeping its exact performance, by exploiting the structure of the expectation. The second replaces a fully random distribution with a small sample space that preserves the few statistical properties the analysis actually used. Both are more delicate than they appear, and both fail in specific ways when the property being preserved is not the one the analysis needs.

Conditional expectations as a search procedure

The method of conditional expectations turns an existence proof into a deterministic algorithm by fixing the random choices one variable at a time. At each step the algorithm has fixed some variables and has an expression for the expected cost conditioned on those fixings; it tries each possible value of the next variable and keeps the one that minimizes the conditional expectation.

The correctness argument is a two-line induction. Let E be the unconditional expectation of the cost, and suppose the algorithm maintains the invariant that the conditional expectation given the choices made so far is at most E. When the next variable is fixed, the conditional expectation over its values averages to the current conditional expectation, so at least one value does not increase it. Choosing that value preserves the invariant. At the end, all variables are fixed and the conditional expectation equals the actual cost, which is therefore at most E. If E < 1 and the cost is a non-negative integer, the cost is 0.

The difficulty is computing the conditional expectation efficiently. For the hypergraph coloring example, the cost is the number of monochromatic edges and the conditional expectation given a partial coloring is the sum over edges of the probability that the edge ends up monochromatic. For an edge with k vertices of which a are fixed red, b fixed blue, and the rest unfixed, the probability is 0 if a > 0 and b > 0, 2^{-(k-a-b)} if a > 0 or b > 0, and 2^{1-k} if nothing is fixed. Maintaining this sum incrementally as vertices are colored costs a constant per edge touched, so a full pass over the edges per vertex gives O(nm) total.

The cost can be reduced by maintaining, for each edge, its current contribution and updating only the edges incident to the vertex just colored. That gives O(sum of edge sizes) per vertex in the worst case and O(total edge size) overall for sparse hypergraphs, which matches the input size up to the number of vertices. The reduction is a standard example of turning an existence proof into an algorithm whose cost is proportional to the amount of structure the proof inspected.

When the conditional expectation cannot be computed

The method requires the conditional expectation to be exactly computable. For many randomized algorithms the cost is a maximum over a set of outcomes rather than a sum, and the conditional expectation of a maximum is not the maximum of conditional expectations. Replacing one by the other is the most common error in applying the method, and it invalidates the invariant: the algorithm may choose a value that increases the true conditional expectation while appearing to decrease the surrogate.

The safe cases are those where the cost decomposes as a sum of local terms, each depending on a bounded number of variables. The expectation of a sum is the sum of expectations, and each local term’s conditional expectation is computable from the variables it depends on. This covers constraint satisfaction, graph coloring, and the assignment problems where the objective is a sum of pairwise costs.

The unsafe cases are those with a global constraint: a maximum load, a diameter, a longest path. For these the method of conditional expectations is usually replaced by a different derandomization, such as the method of pessimistic estimators, which maintains an upper bound on the conditional expectation rather than the expectation itself. The bound must be computable and must remain valid under conditioning, and constructing one is often the hardest part of the argument.

Small sample spaces that preserve pairwise independence

A different route keeps the algorithm unchanged and shrinks the space from which its random choices are drawn. If the analysis used only pairwise independence, then a distribution that is pairwise independent is as good as a fully random one for that analysis, and such distributions can be supported on a space of size polynomial in the number of variables rather than exponential.

The standard construction uses arithmetic over a finite field. To generate n pairwise-independent values, choose a and b uniformly from GF(2^k) with 2^k > n, label the positions with distinct field elements v_1, ..., v_n, and set the i-th output to a · v_i + b in the field. Any two outputs form a uniform pair, because the linear map from (a, b) to that pair has full rank, and each individual bit of the outputs inherits pairwise independence. The sample space has size 2^{2k}, which is O(n^2), and each draw requires O(k) field operations.

The saving is substantial. An algorithm that needs n independent bits and is analysed only through pairwise probabilities can be run over all O(n^2) seeds instead of all 2^n assignments, and the guarantee that some seed achieves the bound is preserved. Running over all seeds is itself a derandomization, and it is deterministic.

The catch is that the analysis must genuinely use only pairwise independence. Many analyses quietly use three-wise or full independence, for instance when applying a Chernoff bound, and replacing the source with a pairwise-independent one invalidates the tail estimate. The Chernoff bound requires independence across the summed indicators; a pairwise-independent source gives the right mean and the right variance but not the exponential tail, so the failure probability can be much larger than the bound suggests.

Epsilon-biased distributions and what they preserve

A distribution over {0,1}^n is ε-biased if every parity of a non-empty subset of the bits is within ε of uniform. Small-bias distributions preserve the expectation of any linear function of the bits, and they preserve the variance of sums, which is what most algebraic analyses need. Constructions exist with sample space size polynomial in n and 1/ε, and they are the basis for derandomizing algorithms whose analysis depends on the Fourier spectrum of the input distribution.

The property is weaker than pairwise independence in one direction and stronger in another. A pairwise-independent distribution is 0-biased for parities of size two, but ε-biased distributions need not be pairwise independent for individual bits. What they guarantee is that every linear test, meaning every XOR of a subset, sees an almost uniform answer, which is exactly what an algorithm that computes parities needs.

The limitation is that ε-biased distributions say nothing about non-linear tests. An algorithm whose analysis depends on the probability that three specific bits are all 1 cannot be derandomized with an ε-biased distribution unless the distribution happens to have that property as well. The general principle is that the sample space must preserve the specific statistics the analysis used, and identifying those statistics is the first step of any derandomization.

The limits of derandomization

Removing randomness from an algorithm does not always preserve its complexity. The method of conditional expectations can cost a factor of n or more over the randomized version, because it computes conditional expectations that the randomized algorithm never needed. For problems where the randomized algorithm is linear, the derandomized version is often quadratic or worse.

Some derandomizations are not known to be efficient at all. The probabilistic method proves the existence of objects such as expander graphs with certain parameters or error-correcting codes with certain distance, for which no polynomial-time construction is known in the general case. In those settings the randomized algorithm is the only known way to find the object, and the existence proof is a statement about the object rather than about an algorithm.

There is also a trade in the other direction: derandomization can improve reliability. A randomized algorithm with a small failure probability is not the same as a deterministic algorithm with no failure, and in a setting where a single wrong answer is unacceptable, the deterministic version is preferable even at a cost in running time. The decision depends on whether the failure can be detected and retried, which is a property of the application rather than of the algorithm.

The cluster’s earlier material connects here in two places. The existence arguments in The Probabilistic Method are the objects being derandomized, and the tail bounds in Randomized Recurrences and the Indicator Variable Method determine which statistics a smaller sample space must preserve. A derandomization that keeps the mean but loses the tail is a change of algorithm, not a simplification of it.