Probabilistic method: Difference between revisions

Revision as of 03:06, 16 February 2023

Latest revision as of 01:18, 19 May 2025

(11 intermediate revisions by 11 users not shown)

Line 6:

==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]], 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.

Line 54:

A weakness of this argument is that it is entirely [[nonconstructive proof|nonconstructive]]. Even though it proves (for example) that almost every coloring of the complete graph on {{math|(1.1)^''r''}} vertices contains no monochromatic {{mvar|r}}-subgraph, it gives no explicit example of such a coloring. The problem of finding such a coloring has been [[open problem|open]] for more than 50 years.

----

{{notelist}}

===Second example===

A 1959 paper of Erdős (see reference cited below) addressed the following problem in [[graph theory]]: given positive integers {{mvar|g}} and {{mvar|k}}, does there exist a graph {{mvar|G}} containing only [[cycle (graph theory)|cycles]] of length at least {{mvar|g}}, such that the [[chromatic number]] of {{mvar|G}} is at least {{mvar|k}}?

It can be shown that such a graph exists for any {{mvar|g}} and {{mvar|k}}, and the proof is reasonably simple. Let {{mvar|n}} be very large and consider a random graph {{mvar|G}} on {{mvar|n}} vertices, where every edge in {{mvar|G}} exists with probability {{math|''p'' {{=}} ''n''^{1/''g'' −1}}}. We show that with positive probability, {{mvar|G}} satisfies the following two properties:

:'''Property 1.''' {{mvar|G}} contains at most {{math|''n''/2}} cycles of length less than {{mvar|g}}.

Line 94 ⟶ 90:

*[[Interactive proof system]]

*[[Las Vegas algorithm]]

*[[Incompressibility method]]

*[[Method of conditional probabilities]]

*[[Probabilistic proofs of non-probabilistic theorems]]

Line 100 ⟶ 97:

== Additional resources ==

* [https://ocw.mit.edu/courses/18-226-probabilistic-methodmethods-in-combinatorics-fall-20202022/ Probabilistic Methods in Combinatorics], MIT OpenCourseWare

==References==

Line 109 ⟶ 106:

* Alon, N and Krivelevich, M (2006). [http://www.math.tau.ac.il/~nogaa/PDFS/epc7.pdf Extremal and Probabilistic Combinatorics]

* Elishakoff I., Probabilistic Methods in the Theory of Structures: Random Strength of Materials, Random Vibration, and Buckling, World Scientific, Singapore, {{ISBN|978-981-3149-84-7}}, 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; {{ISBN|0 444 81624 0}}

{{Reflist}}

==Footnotes==

<references/>

{{notelist}}

{{Authority control}}

[[Category:Combinatorics]]

[[Category:Mathematical proofs]]

[[Category:Probabilistic arguments|method]]