Method of Conditional Probabilities

The method of conditional probabilities is a technique in mathematics and computer science for converting a non-constructive probabilistic existence proof into an efficient deterministic algorithm, a process known as derandomization. Instead of leaving a proof at the level of showing that a desired object exists with positive probability, the method builds the object directly by making each choice in turn so that the conditional probability of failure, given the choices made so far, stays below one. It is especially useful in the design of approximation algorithms, where it is commonly applied to derandomize randomized-rounding arguments into algorithms that always produce a guaranteed result rather than one that merely succeeds with high probability.