HOME

TheInfoList



OR:

In
mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, the probabilistic method is a nonconstructive method, primarily used in
combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ...
and pioneered by
Paul Erdős Paul Erdős ( ; 26March 191320September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in discrete mathematics, g ...
, 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 Probability is a branch of mathematics and statistics concerning events and numerical descriptions of how likely they are to occur. The probability of an event is a number between 0 and 1; the larger the probability, the more likely an e ...
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 Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
such as
number theory Number theory is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. Number theorists study prime numbers as well as the properties of mathematical objects constructed from integers (for example ...
,
linear algebra Linear algebra is the branch of mathematics concerning linear equations such as :a_1x_1+\cdots +a_nx_n=b, linear maps such as :(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n, and their representations in vector spaces and through matrix (mathemat ...
, and
real analysis In mathematics, the branch of real analysis studies the behavior of real numbers, sequences and series of real numbers, and real functions. Some particular properties of real-valued sequences and functions that real analysis studies include co ...
, as well as in
computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
(e.g.
randomized rounding In computer science and operations research, randomized rounding is a widely used approach for designing and analyzing approximation algorithms. Many combinatorial optimization problems are computationally intractability (complexity), intrac ...
), and
information theory Information theory is the mathematical study of the quantification (science), quantification, Data storage, storage, and telecommunications, communication of information. The field was established and formalized by Claude Shannon in the 1940s, ...
.


Introduction

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 In logic and mathematics, contraposition, or ''transposition'', refers to the inference of going from a conditional statement into its logically equivalent contrapositive, and an associated proof method known as . The contrapositive of a stateme ...
, 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 In probability theory, the expected value (also called expectation, expectancy, expectation operator, mathematical expectation, mean, expectation value, or first Moment (mathematics), moment) is a generalization of the weighted average. Informa ...
of some
random variable A random variable (also called random quantity, aleatory variable, or stochastic variable) is a Mathematics, mathematical formalization of a quantity or object which depends on randomness, random events. The term 'random variable' in its mathema ...
. 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 In probability theory, Markov's inequality gives an upper bound on the probability that a non-negative random variable is greater than or equal to some positive Constant (mathematics), constant. Markov's inequality is tight in the sense that for e ...
, the Chernoff bound, and the Lovász local lemma.


Two examples due to Erdős

Although others before him proved
theorem In mathematics and formal logic, a theorem is a statement (logic), statement that has been Mathematical proof, proven, or can be proven. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to esta ...
s via the probabilistic method (for example, Szele's 1943 result that there exist
tournaments A tournament is a competition involving at least three competitors, all participating in a sport or game. More specifically, the term may be used in either of two overlapping senses: # One or more competitions held at a single venue and concentr ...
containing a large number of
Hamiltonian cycle In the mathematics, mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path (graph theory), path in an undirected or directed graph that visits each vertex (graph theory), vertex exactly once. A Hamiltonian cycle (or ...
s), 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 .


First example

Suppose we have a
complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices i ...
on vertices. We wish to show (for small enough values of ) that it is possible to color the edges of the
graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discret ...
in two colors (say red and blue) so that there is no complete subgraph on vertices which is monochromatic (every edge colored the same color). To do so, we color the graph randomly. Color each edge independently with probability of being red and of being blue. We calculate the expected number of monochromatic subgraphs on vertices as follows: For any set S_r of r vertices from our graph, define the variable X(S_r) to be if every edge amongst the r vertices is the same color, and otherwise. Note that the number of monochromatic r-subgraphs is the sum of X(S_r) over all possible
subset In mathematics, a Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they a ...
s S_r. For any individual set S_r^i, the
expected value In probability theory, the expected value (also called expectation, expectancy, expectation operator, mathematical expectation, mean, expectation value, or first Moment (mathematics), moment) is a generalization of the weighted average. Informa ...
of X(S_r^i) is simply the probability that all of the C(r, 2) edges in S_r^i are the same color: :E (S_r^i)= 2 \cdot 2^ (the factor of comes because there are two possible colors). This holds true for any of the C(n, r) possible subsets we could have chosen, i.e. i ranges from to C(n,r). So we have that the sum of E (S_r^i)/math> over all S_r^i is :\sum_^ E (S_r^i)= 2^. The sum of expectations is the expectation of the sum (''regardless'' of whether the variables are
independent Independent or Independents may refer to: Arts, entertainment, and media Artist groups * Independents (artist group), a group of modernist painters based in Pennsylvania, United States * Independentes (English: Independents), a Portuguese artist ...
), so the expectation of the sum (the expected number of all monochromatic r-subgraphs) is :E (S_r)= 2^. Consider what happens if this value is less than . Since the expected number of monochromatic -subgraphs is strictly less than , there exists a coloring satisfying the condition that the number of monochromatic -subgraphs is strictly less than . The number of monochromatic -subgraphs in this random coloring is a non-negative
integer An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
, hence it must be ( is the only non-negative integer less than ). It follows that if :E (S_r)= 2^ < 1 (which holds, for example, for and ), there must exist a coloring in which there are no monochromatic -subgraphs. By definition of the Ramsey number, this implies that must be bigger than . In particular, must grow at least exponentially with . 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 vertices contains no monochromatic -subgraph, it gives no explicit example of such a coloring. The problem of finding such a coloring has been
open Open or OPEN may refer to: Music * Open (band), Australian pop/rock band * The Open (band), English indie rock band * ''Open'' (Blues Image album), 1969 * ''Open'' (Gerd Dudek, Buschi Niebergall, and Edward Vesala album), 1979 * ''Open'' (Go ...
for more than 50 years.


Second example

A 1959 paper of Erdős (see reference cited below) addressed the following problem in
graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
: given positive integers and , does there exist a graph containing only cycles of length at least , such that the
chromatic number In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring i ...
of is at least ? It can be shown that such a graph exists for any and , and the proof is reasonably simple. Let be very large and consider a random graph on vertices, where every edge in exists with probability . We show that with positive probability, satisfies the following two properties: :Property 1. contains at most cycles of length less than . Proof. Let be the number cycles of length less than . The number of cycles of length in the complete graph on vertices is :\frac \le \frac and each of them is present in with probability . Hence by
Markov's inequality In probability theory, Markov's inequality gives an upper bound on the probability that a non-negative random variable is greater than or equal to some positive Constant (mathematics), constant. Markov's inequality is tight in the sense that for e ...
we have :\Pr \left (X> \tfrac \right )\le \frac E \le \frac \sum_^ p^i n^i = \frac \sum_^ n^ \le \frac n^ = gn^ = o(1). : Thus for sufficiently large , property 1 holds with a probability of more than . :Property 2. contains no independent set of size \lceil \tfrac \rceil. Proof. Let be the size of the largest independent set in . Clearly, we have :\Pr (Y\ge y) \le (1-p)^ \le n^y e^ = e^ = o(1), when :y = \left \lceil \frac \right \rceil\!. Thus, for sufficiently large , property 2 holds with a probability of more than . For sufficiently large , 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 has these two properties, we can remove at most vertices from to obtain a new graph on n'\geq n/2 vertices that contains only cycles of length at least . We can see that this new graph has no independent set of size \left \lceil \frac\right\rceil. can only be partitioned into at least independent sets, and, hence, has chromatic number at least . 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 also

* Interactive proof system *
Las Vegas algorithm In computing, a Las Vegas algorithm is a randomized algorithm that always gives Correctness (computer science), correct results; that is, it always produces the correct result or it informs about the failure. However, the runtime of a Las Vegas alg ...
* Incompressibility method *
Method of conditional probabilities In mathematics and computer science, the method of conditional probabilities is a systematic method for converting non-constructive probabilistic existence proofs into efficient Deterministic algorithm, deterministic algorithms that explicitly con ...
* Probabilistic proofs of non-probabilistic theorems *
Random graph In mathematics, random graph is the general term to refer to probability distributions over graphs. Random graphs may be described simply by a probability distribution, or by a random process which generates them. The theory of random graphs l ...


Additional resources


Probabilistic Methods in Combinatorics
MIT OpenCourseWare


References

* Alon, Noga; Spencer, Joel H. (2000). ''The probabilistic method'' (2ed). New York: Wiley-Interscience. . * * * J. Matoušek, J. Vondrak
The Probabilistic Method
Lecture notes. * Alon, N and Krivelevich, M (2006)
Extremal and Probabilistic Combinatorics
* Elishakoff I., Probabilistic Methods in the Theory of Structures: Random Strength of Materials, Random Vibration, and Buckling, World Scientific, Singapore, , 2017 * Elishakoff I., Lin Y.K. and Zhu L.P., Probabilistic and Convex Modeling of Acoustically Excited Structures, Elsevier Science Publishers, Amsterdam, 1994, VIII + pp. 296;


Footnotes

{{Authority control Combinatorics Mathematical proofs
method Method (, methodos, from μετά/meta "in pursuit or quest of" + ὁδός/hodos "a method, system; a way or manner" of doing, saying, etc.), literally means a pursuit of knowledge, investigation, mode of prosecuting such inquiry, or system. In re ...