Asymptotic Enumeration in Combinatorial Probability

首席研究员Pemantle将从事几个组合概率领域的工作。在渐近计数领域，他将以任何可能的方式获得多元亚纯生成函数的系数的近似值，这些系数在多指标趋于无穷大时是渐近有效的。最终目标是使这一过程自动化，至少对于具有非负系数的(多元)有理生成函数类是如此。此前的结果表明，这可能是可行的，或者至少可以在一定程度上实现。这些结果将被应用于概率论中的几个组合问题，包括所谓的阿兹特克钻石构型的随机拼接的渐近性，以及其他相关的拼接系综，这些拼接系综猜想产生多项式相边界。在具有强化的随机过程领域，他将研究随机近似类型的过程收敛到其最终极限行为的速度。特别是，顶点增强的随机游动和一致增强的社会网络模型收敛到其极限的速度是缓慢的，这可以通过给出在有限时间偏离这一行为的概率的量化界限来解释。希望这既能解释模拟数据，又能为这些模型的使用提供理论基础。在其他杂乱的问题中，有几个是经济博弈论的问题，还有一个是关于函数方程解的渐近性的问题。计算机代数的最新进展已经使许多类型的计算实现了自动化，而这些计算曾经只有熟练的实践者才能完成。如今，对于一个问题的完整理论和实践理解，几个杂乱无章的方程式根本不是障碍。渐近枚举项目最切实的结果将是将以前困难的计算类型转变为简单但混乱的一系列步骤。应用范围远远超出了随机分块的激励例子，还包括排队理论、信号处理和组合计数。强化过程最常出现在三个应用领域：正式的学习模型、种群生物学和经济行为。在这些领域中的每一个领域，该项目的结果将阐明什么时候以及为什么在实际应用的时间范围内没有观察到理论上预测的限制行为。

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.