| Probabilistic Method |
Article Index for Probabilistic |
Website Links For Probabilistic |
Information AboutProbabilistic Method |
| CATEGORIES ABOUT PROBABILISTIC METHOD | |
| combinatorics | |
| proofs | |
|
The probabilistic method is a Nonconstructive 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. One way of doing this is by considering a randomly selected thing from a finite-sized universe. If the probability that the random thing satisfies 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 vanishingly 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 . 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 Cycle s), 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). First example 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). 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 edges in ''S'' are the same color, : (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 {Link without Title} 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
|