The Probabilistic Method

概率方法

• 批准号: 9970822
• 负责人: Joel Spencer
• 金额: $ 17.32万
• 依托单位: New York University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1999
• 资助国家: 美国
• 起止时间: 1999-06-01 至 2003-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9970822&HistoricalAwards=false
• 关键词: Probabilistic; Method

9970822The investigator will continue his study of The Probabilistic Method, a legacy of the late Paul Erdos that remains in a very active stage. The original, and still basic, applications are to discrete mathematics when one wishes to prove the existence of an object having certain properties. Very roughly, a random object is appropriately defined and it is shown that the random object has the desired properties with positive probability. The methodology strongly intersects with the use of randomness in Theoretical Computer Science, the interaction going both ways. If a random algorithm can be proven to have positive chance of success then the existence of a success is guaranteed. Further, the output of random algorithms is very much of interest for its own sake. As the random object evolves there are certain critical regions, dubbed threshold functions, where the probability of events move rapidly from near zero to near one. Using methods from mathematical logic the investigator attempts to describe the possible threshold functions for all events expressible in a given logical language.Randomness is now recognized to play an important role in many computer algorithms. The investigators particularly study packing algorithms. How can a set of partially overlapping requests - for bandwidth, takeoff slots or whatever - be handled to satisfy the maximal number of requests? With the random greedy algorithm the requests are taken in randomly shuffled order and then each is approved if not conflicting with previous approvals. Oftimes this natural and easily implemented algorithm can be shown to give near optimal results though analysis of it has proved to be particularly subtle. A second, though related, area is in percolation effects. Large systems are (often) nonlinear - they undergo a phase transition (liquid to gas, low crime to high crime) which is qualitative as well as quantitative in a surprisingly short period of time. With the appropriate scaling the investigator shall spread out this transition so as better to understand the phenomenon.

9970822研究者将继续研究概率方法，这是已故Paul Erdos的遗产，目前仍处于非常活跃的阶段。 原始的，仍然是基本的，应用程序是离散数学时，人们希望证明存在的一个对象具有某些性质。 非常粗略地，一个随机对象是适当的定义，它是随机对象具有所需的属性与正概率。 该方法与理论计算机科学中随机性的使用有很强的交叉，相互作用是双向的。 如果一个随机算法可以被证明有成功的机会，那么成功的存在是有保证的。 此外，随机算法的输出因其自身原因而非常有趣。 随着随机对象的演化，存在某些临界区域，称为阈值函数，事件的概率从接近零迅速移动到接近1。 使用方法从数理逻辑的调查人员试图描述可能的阈值函数的所有事件表达在一个给定的逻辑语言。随机性现在被认为在许多计算机算法中发挥着重要作用。 研究人员特别研究打包算法。 如何处理一组部分重叠的请求（带宽、起飞时隙或其他）以满足最大数量的请求？ 使用随机贪婪算法，请求以随机打乱的顺序进行，然后如果与先前的批准不冲突，则每个请求都被批准。 通常情况下，这种自然和易于实现的算法可以显示出接近最佳的结果，虽然它的分析已被证明是特别微妙的。 第二个相关领域是渗透效应。 大型系统（通常）是非线性的-它们在令人惊讶的短时间内经历了一个定性和定量的相变（液体到气体，低犯罪到高犯罪）。 通过适当的缩放，研究者应展开这种转变，以便更好地理解这种现象。