This article is not about probabilistic algorithms, which give the right answer with high probability but not with certainty, nor about Monte Carlo methods, which are simulations relying on pseudo-randomness. A randomized algorithm is an algorithm which is allowed to flip a truly random coin. ... Monte Carlo methods are algorithms for solving various kinds of computational problems by using random numbers (or more often pseudo-random numbers), as opposed to deterministic algorithms. ... A pseudorandom number generator (PRNG) is an algorithm that generates a sequence of numbers, the elements of which are approximately independent of each other. ...

The probabilistic method is a non-constructive method primarily used in combinatorics and pioneered by Paul Erdős, for proving the existence of a prescribed kind of mathematical object. This method has now been applied to other areas of mathematics such as number theory, linear algebra, and real analysis. 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 more than zero. Although the proof uses probability, the final conclusion is determined for certain, without any possible error. Combinatorics is a branch of mathematics that studies finite collections of objects that satisfy specified criteria. ... The title given to this article is incorrect due to technical limitations. ... Wikibooks Wikiversity has more about this subject: School of Mathematics Wikiquote has a collection of quotations by or about: Mathematics Look up Mathematics in Wiktionary, the free dictionary Wikimedia Commons has more media related to: Mathematics Bogomolny, Alexander: Interactive Mathematics Miscellany and Puzzles. ... Traditionally, number theory is that branch of pure mathematics concerned with the properties of integers. ... Linear algebra is the branch of mathematics concerned with the study of vectors, vector spaces (or linear spaces), linear transformations, and systems of linear equations. ... Real analysis is that branch of mathematical analysis dealing with the set of real numbers and functions of real numbers. ... The word probability derives from the Latin probare (to prove, or to test). ...

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 (strictly) less than 1 can be used to prove the existence of an object that does not satisfy the prescribed properties.

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.

Common tools used in the probabilistic method include Markov's inequality, the Chernoff bound, and the Lovász Local Lemma. In probability theory, Markovs inequality gives an upper bound for the probability that a non-negative function of a random variable is greater than or equal to some positive constant. ... In probability theory, the Chernoff bound, named after Herman Chernoff, gives a lower bound for the success of majority agreement for n independent, equally likely events. ...

Two examples due to Erdős

Although others before him proved theorems via the probabilistic method (for example, Szele's 1943 result that there exist tournaments containing a large number of Hamiltonian cycles), many of the most well known proofs using this method are due to Erdős. One such result is this 1947 proof giving a lower bound on the Ramsey number R(r, r; 2). One major problem that has plagued graph theory since its inception is the lack of consistency in terminology. ... In the mathematical field of graph theory, a Hamiltonian path is a path in a undirected graph which visits each vertex exactly once. ... In combinatorics, Ramseys theorem states that in colouring a large complete graph, one will find complete subgraphs all of the same colour. ...

Suppose we have a complete graph on n vertices. We wish to show (for small enough values of n) that it is possible to color the edges of the graph in two colors (say red and blue) so that there is no complete subgraph on r vertices which is monochromatic (every edge colored the same color). In the mathematical field of graph theory a complete graph is a simple graph where an edge connects every pair of vertices. ...

To do so, we color the graph randomly! Color each edge independently with probability 1/2 of being red and 1/2 of being blue. We calculate the expected number of monochromatic subgraphs on r vertices as follows:

For any set S of r vertices from our graph, define the variable X(S) to be 1 if every edge amongst the r vertices is the same color, and 0 otherwise. Note that the number of monochromatic r-subgraphs is the sum of X(S) over all possible subsets. For any S, the expected value of X(S) is simply the probability that all of the r(r − 1)/2 edges in S are the same color, In probability (and especially gambling), the expected value (or expectation) of a random variable is the sum of the probability of each possible outcome of the experiment multiplied by its payoff (value). Thus, it represents the average amount one expects to win per bet if bets with identical odds are...

2·2^{−r(r − 1)/2}

(the factor of 2 comes because there are two possible colors).

This holds true for any of the C(n,r) possible subsets we could have chosen, so we have that the sum of E[X(S)] over all S is

The sum of an expectation is the expectation of the sum (regardless of whether the variables are independent), so the expectation of the sum (the expected number of monochromatic r-subgraphs) is

Consider what happens if this value is less than 1. The number of monochromatic r-subgraphs in our random coloring will always be an integer, so must for at least one coloring be less than the expected value. But the only integer which satisfies this criterion is 0! Thus if

C(n, r) < 2^{r(r − 1)/2 − 1},

some coloring fits our desired criterion, so by definition R(r, r; 2) must be bigger than n. In particular, R(r, r; 2) must grow at least exponentially with r. In mathematics, a quantity that grows exponentially is one that grows at a rate proportional to its size. ...

A peculiarity of this argument is that it is entirely nonconstructive. Even though it proves (for example) that almost every coloring of the complete graph on (1.1)^r vertices contains no monochromatic r-subgraph, it gives no explicit example of such a coloring. The problem of finding such a coloring has been open for more than 50 years. In mathematics, a nonconstructive proof, is a mathematical proof that purports to demonstrate the existence of something, but which does not say how to construct it. ...

A 1959 paper of Erdős (see reference cited below) addressed the following problem in graph theory: given positive integers g and k, does there exist a graph G containing no cycles of length at most g, such that the chromatic number of G is at least k? In mathematics and computer science, graph theory studies the properties of graphs. ... One major problem that has plagued graph theory since its inception is the consistent lack of consistency in terminology. ... A 3_coloring suits this graph, but fewer colors would result in adjacent verticies of the same color. ...

It can be shown that such a graph exists for any g and k, and the proof is reasonably simple. Let n be very large and consider a random graph G on n vertices, where every edge in G exists with probability n^(1-g)/g. It can be shown that with positive probability, the following two properties hold:

• G contains no stable set of size
• G contains at most n/2 cycles of length at most g.

Here comes the trick: since G has these two properties, we can remove at most n/2 vertices from G to obtain a new graph G' on n' vertices that contains no cycles of length at most g. We can see that this new graph has no stable set of size , hence G' has chromatic number at least k. In graph theory, an independent, or stable, set in a graph G, which contains vertices V, is a set of vertices V (a subset of V) such that for every two vertices in V, there is no edge connecting the two. ...

This result gives a hint as to why the computation of the Chromatic Number of a graph is so difficult: even when there are no local reasons (such as small cycles) for a graph to require many colors the chromatic number can still be arbitrarily large. A 3-coloring suits this graph, but fewer colors would result in adjacent vertices of the same color. ...

References

• Alon, Noga; Spencer, Joel H. (2000). The probabilistic method (2ed). New York: Wiley-Interscience. ISBN 0-471-37046-0.
• Erdős, P. (1959). Graph theory and probability. Canad. J. Math. 11: 34–38.