请输入您要查询的字词:

 

单词 ProbabilisticMethod
释义

probabilistic method


The probabilistic method was pioneered by Erdős Pál (known to Westerners as Paul Erdős) and initially used for solving problems in graph theoryMathworldPlanetmath, but has acquired ever wider applications. Broadly, the probabilistic method is somewhat the opposite of extremal graph theory. Instead of considering how a graph can behave in the most extreme case, we consider how a collectionMathworldPlanetmath of graphs behave “on average”, whereby we can formulate a probability spaceMathworldPlanetmath. The fruits reaped by this method are often raw existence theoremsMathworldPlanetmath, usually deduced from the fact that the nonexistence of whatever of graph would a zero probability. For instance, by means of the probabilistic method, Erdős proved the existence of a graph of arbitrarily high girth and chromatic numberMathworldPlanetmath, a very counterintuitive result. Graphs tend to get enormous as the chromatic number and girth increase, thereby severely hindering necessary computations to explicitly construct them, so an existence theorem is most welcome.

In all honesty, probabilistic proofs are nothing more than counting proofs in disguise, since determining the probabilities of interest will invariably involve detailed counting arguments. In fact, we could remove from any probabilistic proof any mention of a probability space, although the result may be significanltly less transparent. Also, the advantage of using probability is that we can employ all the machinery of probability theory. Markov chainsMathworldPlanetmath, martingalesMathworldPlanetmath, expectations (http://planetmath.org/ExpectedValue), probabilistic inequalities, and many other results, all become the tools of the trade in dealing with seemingly static objects of combinatorics and number theoryMathworldPlanetmathPlanetmath.

References

  • 1 Noga Alon and Joel H. Spencer. The probabilistic method. John Wiley & Sons, Inc., second edition, 2000. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0996.05001Zbl0996.05001.
  • 2 Paul Erdős and Joel Spencer. Probabilistic methods in combinatorics. Academic Press, 1973. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0308.05001Zbl0308.05001.
随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 6:11:48