Mathematical Sciences: Topics in Discrete Probability and Algorithms

数学科学：离散概率和算法主题

• 批准号: 9622859
• 负责人: David Aldous
• 金额: $ 17.64万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1996
• 资助国家: 美国
• 起止时间: 1996-06-01 至 2000-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9622859&HistoricalAwards=false
• 关键词: Mathematical; Sciences; Topics; Discrete; Probability

Aldous A general methodology for the study of size-asymptotics of random finite structures is to seek to establish, via the techniques of weak convergence theory, existence of a limiting continuous-space structure. In this spirit, one part of the proposal is to develop a new approach to the emergence of the giant component in random graph theory, by representing limit component sizes as excursion lengths in a Brownian-type process. This representation opens up a relation between two well-studied but hitherto apparently unrelated areas of probability theory. Other parts of the proposal include foundational work relating to mixing times for Markov chains, and analysis of specific randomized algorithms. As background, the study of matter aggregating into clusters is of interest in many areas of science: polymers in physical chemistry, condensation of raindrops in clouds, and formation of galaxies in the early universe, to name just three examples. Models of clustering incorporating the effects of randomness received some attention from physicists in the early and mid 1980s, but faded out when the mathematical tools then available had been used to their limits. The main part of this proposal concerns detailed study of one particular model of this kind via sophisticated modern mathematical tools. It is hoped that new tools to be developed under this proposal will be useful in at least some of these scientific areas.

奥尔德斯 研究随机有限结构的尺寸渐近性的一般方法是通过弱收敛理论的技巧来寻求建立一个极限连续空间结构的存在性。本着这种精神，该提案的一部分是开发一种新的方法，在随机图论中的巨型组件的出现，通过表示极限组件的大小作为在布朗型过程中的行程长度。这种表示打开了两个研究得很好但迄今为止显然无关的概率论领域之间的关系。该提案的其他部分包括与马尔可夫链的混合时间有关的基础工作，以及对特定随机算法的分析。 作为背景，物质聚集成团的研究在许多科学领域都很有趣：物理化学中的聚合物，云中雨滴的凝结，以及早期宇宙中星系的形成，仅举三个例子。 在20世纪80年代早期和中期，包含随机性效应的聚类模型受到了物理学家的关注，但当当时可用的数学工具被使用到极限时，它就逐渐消失了。 该建议的主要部分涉及通过复杂的现代数学工具对这种特定模型进行详细研究。 希望根据这一建议开发的新工具至少在其中一些科学领域有用。