Incubator escapee wiki

Probabilistic method

Article Discussion
Revision as of 01:18, 19 May 2025 by imported>Beland (custom spacing in math formulas (via WP:JWB))
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

Template:Short description

In mathematics, 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. 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 strictly 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.

IntroductionEdit

If every object in a collection of objects fails to have a certain property, then the probability that a random object chosen from the collection has that property is zero. Thus, by contraposition, if the probability that a random object chosen from the collection has that property is nonzero, then some object in the collection must possess the property.

Similarly, 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.

Alternatively, the probabilistic method can also be used to guarantee the existence of a desired element in a sample space with a value that is greater than or equal to the calculated expected value, since the non-existence of such element would imply every element in the sample space is less than the expected value, a contradiction.

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ősEdit

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. The first example below describes one such result from 1947 that gives a proof of a lower bound for the Ramsey number Template:Math.

First exampleEdit

Suppose we have a complete graph on Template:Mvar vertices. We wish to show (for small enough values of Template:Mvar) 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 Template:Mvar vertices which is monochromatic (every edge colored the same color).

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

For any set <math>S_r</math> of <math>r</math> vertices from our graph, define the variable <math>X(S_r)</math> to be Template:Math if every edge amongst the <math>r</math> vertices is the same color, and Template:Math otherwise. Note that the number of monochromatic <math>r</math>-subgraphs is the sum of <math>X(S_r)</math> over all possible subsets <math>S_r</math>. For any individual set <math>S_r^i</math>, the expected value of <math>X(S_r^i)</math> is simply the probability that all of the <math>C(r, 2)</math> edges in <math>S_r^i</math> are the same color:

<math>E[X(S_r^i)] = 2 \cdot 2^{-{r \choose 2}}</math>

(the factor of Template:Math comes because there are two possible colors).

This holds true for any of the <math>C(n, r)</math> possible subsets we could have chosen, i.e. <math>i</math> ranges from Template:Math to <math>C(n,r)</math>. So we have that the sum of <math>E[X(S_r^i)]</math> over all <math>S_r^i</math> is

<math>\sum_{i=1}^{C(n,r)} E[X(S_r^i)] = {n \choose r}2^{1-{r \choose 2}}.</math>

The sum of expectations is the expectation of the sum (regardless of whether the variables are independent), so the expectation of the sum (the expected number of all monochromatic <math>r</math>-subgraphs) is

<math>E[X(S_r)] = {n \choose r}2^{1-{r \choose 2}}.</math>

Consider what happens if this value is less than Template:Math. Since the expected number of monochromatic Template:Mvar-subgraphs is strictly less than Template:Math, there exists a coloring satisfying the condition that the number of monochromatic Template:Mvar-subgraphs is strictly less than Template:Math. The number of monochromatic Template:Mvar-subgraphs in this random coloring is a non-negative integer, hence it must be Template:Math (Template:Math is the only non-negative integer less than Template:Math). It follows that if

<math>E[X(S_r)] = {n \choose r}2^{1-{r \choose 2}} < 1</math>

(which holds, for example, for Template:Math and Template:Math), there must exist a coloring in which there are no monochromatic Template:Mvar-subgraphs.{{efn| The same fact can be proved without probability, using a simple counting argument:

  • The total number of r-subgraphs is <math>{n \choose r}</math>.
  • Each r-subgraphs has <math>{r \choose 2}</math> edges and thus can be colored in <math>2^{r \choose 2}</math> different ways.
  • Of these colorings, only 2 colorings are 'bad' for that subgraph (the colorings in which all vertices are red or all vertices are blue).
  • Hence, the total number of colorings that are bad for some (at least one) subgraph is at most <math>2 {n \choose r} 2^{{n \choose 2} - {r \choose 2}}</math>.
  • Hence, if <math>2 {n \choose r} 2^{{n \choose 2} - {r \choose 2}} < 2^{n \choose 2} \Leftrightarrow {n \choose r}2^{1-{r \choose 2}} < 1</math>, there must be at least one coloring which is not 'bad' for any subgraph.

}}

By definition of the Ramsey number, this implies that Template:Math must be bigger than Template:Mvar. In particular, Template:Math must grow at least exponentially with Template:Mvar.

A weakness of this argument is that it is entirely nonconstructive. Even though it proves (for example) that almost every coloring of the complete graph on Template:Math vertices contains no monochromatic Template:Mvar-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.

Second exampleEdit

A 1959 paper of Erdős (see reference cited below) addressed the following problem in graph theory: given positive integers Template:Mvar and Template:Mvar, does there exist a graph Template:Mvar containing only cycles of length at least Template:Mvar, such that the chromatic number of Template:Mvar is at least Template:Mvar?

It can be shown that such a graph exists for any Template:Mvar and Template:Mvar, and the proof is reasonably simple. Let Template:Mvar be very large and consider a random graph Template:Mvar on Template:Mvar vertices, where every edge in Template:Mvar exists with probability Template:Math. We show that with positive probability, Template:Mvar satisfies the following two properties:

Property 1. Template:Mvar contains at most Template:Math cycles of length less than Template:Mvar.

Proof. Let Template:Mvar be the number cycles of length less than Template:Mvar. The number of cycles of length Template:Mvar in the complete graph on Template:Mvar vertices is

<math>\frac{n!}{2\cdot i \cdot (n-i)!} \le \frac{n^i}{2}</math>

and each of them is present in Template:Mvar with probability Template:Math. Hence by Markov's inequality we have

<math>\Pr \left (X> \tfrac{n}{2} \right )\le \frac{2}{n} E[X] \le \frac{1}{n} \sum_{i=3}^{g-1} p^i n^i = \frac{1}{n} \sum_{i=3}^{g-1} n^{\frac{i}{g}} \le \frac{g}{n} n^{\frac{g-1}{g}} = gn^{-\frac{1}{g}} = o(1).</math>
Thus for sufficiently large Template:Mvar, property 1 holds with a probability of more than Template:Math.
Property 2. Template:Mvar contains no independent set of size <math>\lceil \tfrac{n}{2k} \rceil</math>.

Proof. Let Template:Mvar be the size of the largest independent set in Template:Mvar. Clearly, we have

<math>\Pr (Y\ge y) \le {n \choose y}(1-p)^{\frac{y(y-1)}{2}} \le n^y e^{-\frac{py(y-1)}{2}} = e^{- \frac{y}{2} \cdot (py -2\ln n - p)} = o(1),</math>

when

<math>y = \left \lceil \frac{n}{2k} \right \rceil\!.</math> Thus, for sufficiently large Template:Mvar, property 2 holds with a probability of more than Template:Math.

For sufficiently large Template:Mvar, the probability that a graph from the distribution has both properties is positive, as the events for these properties cannot be disjoint (if they were, their probabilities would sum up to more than 1).

Here comes the trick: since Template:Mvar has these two properties, we can remove at most Template:Math vertices from Template:Mvar to obtain a new graph Template:Math on <math>n'\geq n/2</math> vertices that contains only cycles of length at least Template:Mvar. We can see that this new graph has no independent set of size <math>\left \lceil \frac{n'}{k}\right\rceil</math>. Template:Math can only be partitioned into at least Template:Mvar independent sets, and, hence, has chromatic number at least Template:Mvar.

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.

See alsoEdit

Template:Portal

Additional resourcesEdit

ReferencesEdit

Template:Reflist

FootnotesEdit

Template:Notelist

Template:Authority control

Retrieved from "https://zalansite.site/mediawiki/index.php?title=Probabilistic_method&oldid=124233"