Asymptotic Enumeration in 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.