Method of conditional probabilities: Difference between revisions

Revision as of 11:30, 14 September 2023

Revision as of 11:33, 14 September 2023

Line 5:

| year=1987

| publisher=SIAM

| isbn=978-0-89871-325-1}}</ref><ref name='raghavan'>

<ref name='raghavan'>

{{Citation

| title= Probabilistic construction of deterministic algorithms: approximating packing integer programs

Line 17 ⟶ 16:

| doi = 10.1016/0022-0000(88)90003-7| doi-access=free

}}

</ref> is a systematic method for converting [[non-constructive]] probabilistic existence proofs into efficient [[Deterministic algorithm|deterministic algorithms]] that explicitly construct the desired object.<ref>[http://algnotes.info/on/background/probabilistic-method/method-of-conditional-probabilities/ The probabilistic method — method of conditional probabilities], blog entry by Neal E. Young, accessed 19/04/2012 and 14/09/2023.</ref>

</ref>

is a method for constructing efficient [[Deterministic algorithm|deterministic]] [[approximation algorithms]], based on the [[probabilistic method]].

TheOften, 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 fo 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.