Probabilistic method

<h2 id="introduction">Introduction</h2>
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 <a href="/facts/Contraposition/ENPumbyv">contraposition</a>, 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 <a href="/facts/Expected_value/1XV0JKL8">expected value</a> of some <a href="/facts/Random_variable/TwTBXnLT">random variable</a>. 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 <a href="/facts/Markov%2527s_inequality/Re85kMQJ">Markov's inequality</a>, the <a href="/facts/Chernoff_bound/RLC6VlRU">Chernoff bound</a>, and the <a href="/facts/Lov%25C3%25A1sz_local_lemma/2p6WeGS5">Lovász local lemma</a>.

<h2 id="two-examples-due-to-erds">Two examples due to Erdős</h2>
Although others before him proved <a href="/facts/Theorem/f2Pe1FMD">theorems</a> via the probabilistic method (for example, Szele's 1943 result that there exist <a href="/facts/Tournament_(graph_theory)/SVj5jWWE">tournaments</a> containing a large number of <a href="/facts/Hamiltonian_cycle/MHjY2xoY">Hamiltonian cycles</a>), 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 <a href="/facts/Ramsey%2527s_theorem/VS6K8jGk">Ramsey number</a> R(r, r).

<h3>First example</h3>
Suppose we have a <a href="/facts/Complete_graph/AYD6hUqI">complete graph</a> on n <a href="/facts/Vertex_(graph_theory)/WhlWmL3o">vertices</a>. We wish to show (for small enough values of n) that it is possible to color the <a href="/facts/Edge_(graph_theory)/W0MqKkyE">edges</a> of the <a href="/facts/Graph_(discrete_mathematics)/kw3eIBUe">graph</a> in two colors (say red and blue) so that there is no complete <a href="/facts/Subgraph_(graph_theory)/W0MqKkyE">subgraph</a> 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
 
 r
 
 
 
 
 {\displaystyle S_{r}}
 
 of 
 
 
 
 r
 
 
 {\displaystyle r}
 
 vertices from our graph, define the variable 
 
 
 
 X
 (
 
 S
 
 r
 
 
 )
 
 
 {\displaystyle X(S_{r})}
 
 to be 1 if every edge amongst the 
 
 
 
 r
 
 
 {\displaystyle r}
 
 vertices is the same color, and 0 otherwise. Note that the number of monochromatic 
 
 
 
 r
 
 
 {\displaystyle r}
 
-subgraphs is the sum of 
 
 
 
 X
 (
 
 S
 
 r
 
 
 )
 
 
 {\displaystyle X(S_{r})}
 
 over all possible <a href="/facts/Subset/SJGERmbA">subsets</a> 
 
 
 
 
 S
 
 r
 
 
 
 
 {\displaystyle S_{r}}
 
. For any individual set 
 
 
 
 
 S
 
 r
 
 
 i
 
 
 
 
 {\displaystyle S_{r}^{i}}
 
, the <a href="/facts/Expected_value/1XV0JKL8">expected value</a> of 
 
 
 
 X
 (
 
 S
 
 r
 
 
 i
 
 
 )
 
 
 {\displaystyle X(S_{r}^{i})}
 
 is simply the probability that all of the 
 
 
 
 C
 (
 r
 ,
 2
 )
 
 
 {\displaystyle C(r,2)}
 
 edges in 
 
 
 
 
 S
 
 r
 
 
 i
 
 
 
 
 {\displaystyle S_{r}^{i}}
 
 are the same color:

E
        [
        X
        (
        
          S
          
            r
          
          
            i
          
        
        )
        ]
        =
        2
        ⋅
        
          2
          
            −
            
              
                
                  (
                
                
                  r
                  2
                
                
                  )
                
              
            
          
        
      
    
    {\displaystyle E[X(S_{r}^{i})]=2\cdot 2^{-{r \choose 2}}}

(the factor of 2 comes because there are two possible colors).
This holds true for any of the 
 
 
 
 C
 (
 n
 ,
 r
 )
 
 
 {\displaystyle C(n,r)}
 
 possible subsets we could have chosen, i.e. 
 
 
 
 i
 
 
 {\displaystyle i}
 
 ranges from 1 to 
 
 
 
 C
 (
 n
 ,
 r
 )
 
 
 {\displaystyle C(n,r)}
 
. So we have that the sum of 
 
 
 
 E
 [
 X
 (
 
 S
 
 r
 
 
 i
 
 
 )
 ]
 
 
 {\displaystyle E[X(S_{r}^{i})]}
 
 over all 
 
 
 
 
 S
 
 r
 
 
 i
 
 
 
 
 {\displaystyle S_{r}^{i}}
 
 is

∑
          
            i
            =
            1
          
          
            C
            (
            n
            ,
            r
            )
          
        
        E
        [
        X
        (
        
          S
          
            r
          
          
            i
          
        
        )
        ]
        =
        
          
            
              (
            
            
              n
              r
            
            
              )
            
          
        
        
          2
          
            1
            −
            
              
                
                  (
                
                
                  r
                  2
                
                
                  )
                
              
            
          
        
        .
      
    
    {\displaystyle \sum _{i=1}^{C(n,r)}E[X(S_{r}^{i})]={n \choose r}2^{1-{r \choose 2}}.}

The sum of expectations is the expectation of the sum (regardless of whether the variables are <a href="/facts/Statistical_independence/NUzQtnUL">independent</a>), so the expectation of the sum (the expected number of all monochromatic 
 
 
 
 r
 
 
 {\displaystyle r}
 
-subgraphs) is

E
        [
        X
        (
        
          S
          
            r
          
        
        )
        ]
        =
        
          
            
              (
            
            
              n
              r
            
            
              )
            
          
        
        
          2
          
            1
            −
            
              
                
                  (
                
                
                  r
                  2
                
                
                  )
                
              
            
          
        
        .
      
    
    {\displaystyle E[X(S_{r})]={n \choose r}2^{1-{r \choose 2}}.}

Consider what happens if this value is less than 1. Since the expected number of monochromatic r-subgraphs is strictly less than 1, there exists a coloring satisfying the condition that the number of monochromatic r-subgraphs is strictly less than 1. The number of monochromatic r-subgraphs in this random coloring is a non-negative <a href="/facts/Integer/PUwwrawx">integer</a>, hence it must be 0 (0 is the only non-negative integer less than 1). It follows that if

E
 [
 X
 (
 
 S
 
 r
 
 
 )
 ]
 =
 
 
 
 (
 
 
 n
 r
 
 
 )
 
 
 
 
 2
 
 1
 −
 
 
 
 (
 
 
 r
 2
 
 
 )
 
 
 
 
 
 <
 1
 
 
 {\displaystyle E[X(S_{r})]={n \choose r}2^{1-{r \choose 2}}<1}

(which holds, for example, for n = 5 and r = 4), there must exist a coloring in which there are no monochromatic r-subgraphs.<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a>
By definition of the <a href="/facts/Ramsey_number/VS6K8jGk">Ramsey number</a>, this implies that R(r, r) must be bigger than n. In particular, R(r, r) must grow at least <a href="/facts/Exponential_growth/m4yEqKJ7">exponentially</a> with r.
A weakness of this argument is that it is entirely <a href="/facts/Nonconstructive_proof/0QhhRjhW">nonconstructive</a>. 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 <a href="/facts/Open_problem/VuR6yLsW">open</a> for more than 50 years.

<h3>Second example</h3>
A 1959 paper of Erdős (see reference cited below) addressed the following problem in <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>: given positive integers g and k, does there exist a graph G containing only <a href="/facts/Cycle_(graph_theory)/Is44edrv">cycles</a> of length at least g, such that the <a href="/facts/Chromatic_number/J6HoBfP0">chromatic number</a> of G is at least k?
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 p = n1/g−1. We show that with positive probability, G satisfies the following two properties:

Property 1. G contains at most n/2 cycles of length less than g.
Proof. Let X be the number cycles of length less than g. The number of cycles of length i in the complete graph on n vertices is

n
              !
            
            
              2
              ⋅
              i
              ⋅
              (
              n
              −
              i
              )
              !
            
          
        
        ≤
        
          
            
              n
              
                i
              
            
            2
          
        
      
    
    {\displaystyle {\frac {n!}{2\cdot i\cdot (n-i)!}}\leq {\frac {n^{i}}{2}}}

and each of them is present in G with probability pi. Hence by <a href="/facts/Markov%2527s_inequality/Re85kMQJ">Markov's inequality</a> we have

Pr
        
          (
          
            X
            >
            
              
                
                  n
                  2
                
              
            
          
          )
        
        ≤
        
          
            2
            n
          
        
        E
        [
        X
        ]
        ≤
        
          
            1
            n
          
        
        
          ∑
          
            i
            =
            3
          
          
            g
            −
            1
          
        
        
          p
          
            i
          
        
        
          n
          
            i
          
        
        =
        
          
            1
            n
          
        
        
          ∑
          
            i
            =
            3
          
          
            g
            −
            1
          
        
        
          n
          
            
              i
              g
            
          
        
        ≤
        
          
            g
            n
          
        
        
          n
          
            
              
                g
                −
                1
              
              g
            
          
        
        =
        g
        
          n
          
            −
            
              
                1
                g
              
            
          
        
        =
        o
        (
        1
        )
        .
      
    
    {\displaystyle \Pr \left(X>{\tfrac {n}{2}}\right)\leq {\frac {2}{n}}E[X]\leq {\frac {1}{n}}\sum _{i=3}^{g-1}p^{i}n^{i}={\frac {1}{n}}\sum _{i=3}^{g-1}n^{\frac {i}{g}}\leq {\frac {g}{n}}n^{\frac {g-1}{g}}=gn^{-{\frac {1}{g}}}=o(1).}

Thus for sufficiently large n, property 1 holds with a probability of more than 1/2.
Property 2. G contains no <a href="/facts/Independent_set_(graph_theory)/ksu46kdz">independent set</a> of size 
 
 
 
 ⌈
 
 
 
 n
 
 2
 k
 
 
 
 
 ⌉
 
 
 {\displaystyle \lceil {\tfrac {n}{2k}}\rceil }
 
.
Proof. Let Y be the size of the largest independent set in G. Clearly, we have

Pr
        (
        Y
        ≥
        y
        )
        ≤
        
          
            
              (
            
            
              n
              y
            
            
              )
            
          
        
        (
        1
        −
        p
        
          )
          
            
              
                y
                (
                y
                −
                1
                )
              
              2
            
          
        
        ≤
        
          n
          
            y
          
        
        
          e
          
            −
            
              
                
                  p
                  y
                  (
                  y
                  −
                  1
                  )
                
                2
              
            
          
        
        =
        
          e
          
            −
            
              
                y
                2
              
            
            ⋅
            (
            p
            y
            −
            2
            ln
            ⁡
            n
            −
            p
            )
          
        
        =
        o
        (
        1
        )
        ,
      
    
    {\displaystyle \Pr(Y\geq y)\leq {n \choose y}(1-p)^{\frac {y(y-1)}{2}}\leq n^{y}e^{-{\frac {py(y-1)}{2}}}=e^{-{\frac {y}{2}}\cdot (py-2\ln n-p)}=o(1),}

when

y
 =
 
 ⌈
 
 
 n
 
 2
 k
 
 
 
 ⌉
 
 
 .
 
 
 {\displaystyle y=\left\lceil {\frac {n}{2k}}\right\rceil \!.}
 
 Thus, for sufficiently large n, property 2 holds with a probability of more than 1/2.
For sufficiently large n, 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 G has these two properties, we can remove at most n/2 vertices from G to obtain a new graph G′ on 
 
 
 
 
 n
 ′
 
 ≥
 n
 
 /
 
 2
 
 
 {\displaystyle n'\geq n/2}
 
 vertices that contains only cycles of length at least g. We can see that this new graph has no independent set of size 
 
 
 
 
 ⌈
 
 
 
 n
 ′
 
 k
 
 
 ⌉
 
 
 
 {\displaystyle \left\lceil {\frac {n'}{k}}\right\rceil }
 
. G′ can only be partitioned into at least k independent sets, and, hence, has chromatic number at least k.
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.

<h2 id="see-also">See also</h2>
<ul>
<li>Mathematics portal</li></ul>
<ul><li><a href="/facts/Interactive_proof_system/rDB0agR9">Interactive proof system</a></li>
<li><a href="/facts/Las_Vegas_algorithm/K43MRwQz">Las Vegas algorithm</a></li>
<li><a href="/facts/Incompressibility_method/AjedTG18">Incompressibility method</a></li>
<li><a href="/facts/Method_of_conditional_probabilities/qgFBql34">Method of conditional probabilities</a></li>
<li><a href="/facts/Probabilistic_proofs_of_non-probabilistic_theorems/3VJszExh">Probabilistic proofs of non-probabilistic theorems</a></li>
<li><a href="/facts/Random_graph/gfQhq1Sz">Random graph</a></li></ul>
<h2 id="additional-resources">Additional resources</h2>
<ul><li><a href="https://ocw.mit.edu/courses/18-226-probabilistic-methods-in-combinatorics-fall-2022/">Probabilistic Methods in Combinatorics</a>, MIT OpenCourseWare</li></ul>

<ul><li>Alon, Noga; Spencer, Joel H. (2000). The probabilistic method (2ed). New York: Wiley-Interscience. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-471-37046-0.</li>
<li>Erdős, P. (1959). <a href="https://doi.org/10.4153%2FCJM-1959-003-9">"Graph theory and probability"</a>. Can. J. Math. 11: 34–38. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.4153%2FCJM-1959-003-9">10.4153/CJM-1959-003-9</a>. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0102081">0102081</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:122784453">122784453</a>.</li>
<li>Erdős, P. (1961). <a href="https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/graph-theory-and-probability-ii/38F46DC839201178C2EEC2B14B1647BC">"Graph theory and probability, II"</a>. Can. J. Math. 13: 346–352. <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.210.6669">10.1.1.210.6669</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.4153%2FCJM-1961-029-9">10.4153/CJM-1961-029-9</a>. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0120168">0120168</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:15134755">15134755</a>.</li>
<li><a href="/facts/Ji%25C5%2599%25C3%25AD_Matou%25C5%25A1ek_(mathematician)/rgoef0Hc">J. Matoušek</a>, J. Vondrak. <a href="https://web.archive.org/web/20120205002452/http://kam.mff.cuni.cz/~matousek/prob-ln-2pp.ps.gz">The Probabilistic Method</a>. Lecture notes.</li>
<li>Alon, N and Krivelevich, M (2006). <a href="http://www.math.tau.ac.il/~nogaa/PDFS/epc7.pdf">Extremal and Probabilistic Combinatorics</a></li>
<li>Elishakoff I., Probabilistic Methods in the Theory of Structures: Random Strength of Materials, Random Vibration, and Buckling, World Scientific, Singapore, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-981-3149-84-7, 2017</li>
<li>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; <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0 444 81624 0</li></ul>

<h2 id="footnotes">Footnotes</h2>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">The same fact can be proved without probability, using a simple counting argument:
The total number of r-subgraphs is 
 
 
 
 
 
 
 (
 
 
 n
 r
 
 
 )
 
 
 
 
 
 {\displaystyle {n \choose r}}
 
.
Each r-subgraphs has 
 
 
 
 
 
 
 (
 
 
 r
 2
 
 
 )
 
 
 
 
 
 {\displaystyle {r \choose 2}}
 
 edges and thus can be colored in 
 
 
 
 
 2
 
 
 
 (
 
 
 r
 2
 
 
 )
 
 
 
 
 
 
 {\displaystyle 2^{r \choose 2}}
 
 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 
 
 
 
 2
 
 
 
 (
 
 
 n
 r
 
 
 )
 
 
 
 
 2
 
 
 
 
 (
 
 
 n
 2
 
 
 )
 
 
 
 −
 
 
 
 (
 
 
 r
 2
 
 
 )
 
 
 
 
 
 
 
 {\displaystyle 2{n \choose r}2^{{n \choose 2}-{r \choose 2}}}
 
.
Hence, if 
 
 
 
 2
 
 
 
 (
 
 
 n
 r
 
 
 )
 
 
 
 
 2
 
 
 
 
 (
 
 
 n
 2
 
 
 )
 
 
 
 −
 
 
 
 (
 
 
 r
 2
 
 
 )
 
 
 
 
 
 <
 
 2
 
 
 
 (
 
 
 n
 2
 
 
 )
 
 
 
 
 ⇔
 
 
 
 (
 
 
 n
 r
 
 
 )
 
 
 
 
 2
 
 1
 −
 
 
 
 (
 
 
 r
 2
 
 
 )
 
 
 
 
 
 <
 1
 
 
 {\displaystyle 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}
 
, there must be at least one coloring which is not 'bad' for any subgraph.
 <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
</ol>

Probabilistic method open-in-new

Probabilistic method