Asymptotic Enumeration in Combinatorial Probability

组合概率中的渐近枚举

• 批准号: 0401246
• 负责人: Robin Pemantle
• 金额: $ 29.5万
• 依托单位: University of Pennsylvania
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-06-17 至 2006-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0401246&HistoricalAwards=false
• 关键词: Asymptotic; Enumeration; Combinatorial; Probability

0103635Pemantle The principal investigator will work in several areas of combinatorial probability. In the area of asymptotic enumeration, he will obtain approximations to coefficients of multivariate meromorphic generating functions that are asymptotically valid as the multi-index goes to infinity in any possible way. The ultimate goal is to automate this procedure, at least for the class of (multivariate) rational generating functions with nonnegative coefficients. Previous results indicate this may be feasible, or at least may be carried out to some extent. These results are to be applied to several combinatorial problems in probability theory, including asymptotics for random tilings for the so-called Aztec Diamond configurations and other related tiling ensembles conjectured to produce polynomial phase boundaries. In the area of random processes with reinforcement, he will investigate the rate at which processes of stochastic approximation type converge to their ultimate limiting behavior. In particular, the slow convergence of vertex-reinforced random walks and uniformly reinforced social network models to their limits is to be explained by giving quantitative bounds on the probabilities of deviating from this behavior at finite times. It is hoped that this will both explain simulation data and give a theoretical basis for the use of these models. Among the other miscellaneous problems are several problems in economic game theory and one concerning asymptotics of solutions to functional equations. Recent progress in computer algebra has made many types of computation automated which once were done only by skilled practitioners. Nowadays, a few messy equations are no barrier at all to a complete theoretical and practical understanding of a problem. The most tangible result of the asymptotic enumeration project will be the transformation of a formerly difficult type of computation into a straightforward, though messy, series of steps. Applications reach far beyond the motivating examples of random tilings, and include queuing theory, signal processing and combinatorial enumeration. Reinforcement processes arise most commonly in three application areas: formal models of learning, population biology, and economic behavior. In each of these areas, the results of the project will shed light on when and why the theoretically predicted limiting behaviors are not observed in the timeframes of real applications.

0103635Pemantle首席研究员将在组合概率的几个领域工作。 在渐近枚举领域，他将获得多元亚纯生成函数的系数的近似，这些函数在多指标以任何可能的方式趋于无穷大时渐近有效。 最终的目标是自动化这一过程，至少对于类（多元）合理的非负系数生成函数。以前的研究结果表明，这可能是可行的，或者至少可以在一定程度上进行。 这些结果将被应用到概率论中的几个组合问题，包括所谓的阿兹特克钻石配置和其他相关的瓷砖合奏的随机平铺渐近性被证明产生多项式相边界。 在加强随机过程领域，他将研究随机逼近型过程收敛到其最终极限行为的速率。 特别是，顶点强化随机游走和均匀强化社会网络模型收敛到极限的缓慢性，可以通过给出在有限时间偏离这种行为的概率的定量界限来解释。 希望这既能解释模拟数据，又能为这些模型的使用提供理论依据。 在其他杂项问题中有几个问题在经济博弈论和一个关于渐近解的功能方程。计算机代数的最新进展使许多类型的计算自动化，这些计算曾经只能由熟练的从业者完成。 如今，几个乱七八糟的方程根本不妨碍对一个问题的完整的理论和实践理解。 渐近枚举项目最切实的结果将是将以前困难的计算类型转变为简单的，尽管混乱的一系列步骤。 应用范围远远超出随机平铺的激励性例子，包括排队论，信号处理和组合枚举。 强化过程最常见于三个应用领域：学习的形式模型、群体生物学和经济行为。在这些领域中的每一个，该项目的结果将阐明何时以及为什么理论上预测的极限行为在真实的应用的时间范围内没有观察到。