Mathematical Sciences: Topics in Discrete Probability and Algorithms

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

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.