Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Method of conditional probabilities
open-in-new
<p>In <a href="/facts/Mathematics/pxTouaz4">mathematics</a> and <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, the method of conditional probabilities is a systematic method for converting <a href="/facts/Non-constructive/0QhhRjhW">non-constructive</a> probabilistic existence proofs into efficient <a href="/facts/Deterministic_algorithm/v8x4wz35">deterministic algorithms</a> that explicitly construct the desired object. </p><p>Often, the <a href="/facts/Probabilistic_method/AXKXrzrr">probabilistic method</a> 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 <a href="/facts/Nonconstructive_proof/0QhhRjhW">nonconstructive</a> — they don't explicitly describe an efficient method for computing the desired objects. </p><p>The method of conditional probabilities converts such a proof, in a "very precise sense", into an efficient <a href="/facts/Deterministic_algorithm/v8x4wz35">deterministic algorithm</a>, one that is guaranteed to compute an object with the desired properties. That is, the method <a href="/facts/Derandomization/Fngl1zgk">derandomizes</a> 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. </p><p>The method is particularly relevant in the context of <a href="/facts/Randomized_rounding/8e7sqFxk">randomized rounding</a> (which uses the probabilistic method to design <a href="/facts/Approximation_algorithm/BWlf7M32">approximation algorithms</a>). </p><p>When applying the method of conditional probabilities, the technical term pessimistic estimator refers to a quantity used in place of the true conditional probability (or conditional expectation) underlying the proof. </p>