Probabilistic method: Difference between revisions

Revision as of 16:32, 7 December 2017

Revision as of 16:38, 18 May 2018

Line 1:

{{hatnote|This article is not about [[interactive proof system]]s which use probability to convince a verifier that a proof is correct, nor about [[probabilistic algorithm]]s, which give the right answer with high probability but not with certainty, nor about [[Monte Carlo method]]s, which are algorithms involving repeated random sampling.}}

The '''probabilistic method''' is a [[nonconstructive proof|nonconstructive]] method, primarily used in [[combinatorics]] and pioneered by [[Paul Erdős]], for proving the existence of a prescribed kind of mathematical object. It works by showing that if one randomly chooses objects from a specified class, the [[probability]] that the result is of the prescribed kind is morestrictly greater than zero. Although the proof uses probability, the final conclusion is determined for ''certain'', without any possible error.

This method has now been applied to other areas of [[mathematics]] such as [[number theory]], [[linear algebra]], and [[real analysis]], as well as in [[computer science]] (e.g. [[randomized rounding]]), and [[information theory]].