Derandomization

Derandomization converts a randomized construction or algorithm into a deterministic one while preserving its desired guarantee. The method of conditional probabilities does this by maintaining a computable conditional expectation until all choices are fixed.

For a random objective with an easily computable conditional expectation, reveal one random choice at a time and choose an outcome whose conditional expected objective is at least the current value. Such an outcome exists because the current value is an average of the child values. When all choices are fixed, the actual objective is at least the initial expectation. Biased as well as fair choices work. Efficient expectation updates make the resulting deterministic procedure a polynomial-time algorithm.