Method of conditional probabilities: Difference between revisions

Revision as of 15:09, 11 August 2014

Revision as of 22:26, 16 September 2014

Line 1:

In [[mathematics]] and [[computer science]], the [[probabilistic method]] is used to prove the existence of mathematical objects with desired combinatorial properties. The proofs are probabilistic — they 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 of conditional probabilities''' {{harv|ErdösErdős|Selfridge|1973}}, {{harv|Spencer|1987}}, {{harv|Raghavan|1988}} 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 188:

| title = On a combinatorial game

| first1 = Paul | last1 = ErdösErdős | authorlink1= Paul ErdösErdős

| first2 = J. L. | last2 = Selfridge

| journal = [[Journal of Combinatorial Theory, Series A]]