Method of conditional probabilities: Difference between revisions

Revision as of 11:50, 14 September 2023

Latest revision as of 16:49, 21 February 2025

(One intermediate revision by one other user not shown)

Line 20:

Often, the [[probabilistic method]] is used to prove the existence of mathematical objects with some desired combinatorial properties. The proofs in that method work by showing that a random object, chosen from some probability distribution, has the desired properties with positive probability. Consequently, they are [[nonconstructive proof|nonconstructive]] — they don't explicitly describe an efficient method for computing the desired objects.

The method foof conditional probabilities converts such a proof, in a "very precise sense", into an efficient [[deterministic algorithm]], one that is guaranteed to compute an object with the desired properties. That is, the method [[derandomization|derandomizes]] the proof. The basic idea is to replace each random choice in a random experiment by a deterministic choice, so as to keep the conditional probability of failure, given the choices so far, below 1.

The method is particularly relevant in the context of [[randomized rounding]] (which uses the probabilistic method to design [[approximation algorithm]]s).

Line 209:

== Further reading ==

The method of conditional rounding is explaindexplained in several textbooks:

* {{Cite book |first1=Noga |last1= Alon |authorlink1=Noga Alon