Encyclopedia > Probabilistic method

Article Content

Probabilistic method

The probabilistic method is a non-constructive method pioneered by Paul Erdös for proving the existence of a prescribed kind of mathematical object, by showing that if one randomly chooses objects from a specified class, the probability that the result is of the prescribed kind is more than zero. Although the proof uses probability, the final conclusion is determined for certain, without any possible error.

One way of doing this is by considering a randomly selected thing from a finite-sized universe. If the probability that the random thing satifies certain properties is greater than zero, then this proves the existence of a thing that satisfies the properties. It doesn't matter if the probability is astronomically small; any probability strictly greater than zero will do. (Also, showing that the probability is zero can be used to prove the non-existence of such an object).

Another way to use the probabilistic method is by calculating the expected value of some random variable. If it can be shown that the random variable can take on a value less than the expected value, this proves that the random variable can also take on some value greater than the expected value.

[This is a still a stub article because of its lack of examples.]

All Wikipedia text is available under the terms of the GNU Free Documentation License

Search Encyclopedia
 Search over one million articles, find something about almost anything!

Featured Article
 U.S. presidential election, 1804 ... (W) 162 Democratic-Republican George Clinton (162) Charles C. Pinckney[?] 14 Federalist Rufus King (14) Other elections: 1792, 1796, 1800, 1804, 1808, ...