Random Discrete Structures

9803249 Pemantle The PI将研究概率论和离散数学之间的几个问题。这些问题中的一个本质上是组合问题，与格路的枚举和解决该问题中出现的一类递归有关。这个问题起源于计算机科学中的一个应用，但这种组合分析的应用扩展到粒子系统和许多其他计数问题。第二个研究领域是可数群上的随机过程理论。许多基本过程，如渗流、随机游动和马尔可夫随机场，相对于某个群的作用是对称的。当空间的几何形状是双曲线时，群通常是不可服从的，而在如此大的群的作用下过程的对称性迫使过程至少在某种程度上表现得很好。PI将尝试利用最近发展的一些质量传输方法来获得这样的结果。最后，他将继续研究树上的随机过程，特别是转子模型、接触过程、分枝随机游走和入侵渗流的检查。通常，大量的数学和物理兴趣被编码成一个幂序列，这是一个非常强大的工具，用于获得兴趣量的表达式，前提是一个人最终能够解码信息。已知如何对一个变量的幂函数级数这样做，但当有多个变量时，人们知道的相对较少。即使是一个合理的近似值，通常也是未知的。这项研究的结果有望包括一种可靠的方法来逼近多个变量的幂级数系数。这将允许近似解决从路径枚举到排队问题(生产网络的计算效率)，再到分析算法速度(本项目的最初动机)的各种问题。

9803249 Pemantle The PI will study several problems on the interface between probability theory and discrete mathematics. One of these problems is essentially combinatorial, having to do with enumeration of lattice paths and with solving a class of recursions arising in this problem. The problem arose from an application in computer science, but the applications of this combinatorial analysis extend to particle systems, and to many other enumeration problems. The second research area is the theory of random processes on countable groups. Many basic processes such as percolation, random walk, and Markov random fields are symmetric with respect to the action of some group. When the geometry of the space is hyperbolic, the group is typically non-amenable, and the symmetry of the process under the action of such a large group forces the process to be at least somewhat well behaved. The PI will attempt to exploit some recently developed mass transport methods to obtain such results. Finally, he will continue research into random processes on trees, and in particular, the examination of the rotor model, the contact process, branching random walk, and invasion percolation. Often quantities of mathematical and physical interest are encoded in a power series, which is a very powerful tool for obtaining expressions for the quantities of interest, provided one can in the end decode the information. It is known how to do this for power series in one variable, but relatively little is known when there is more than one variable. Even a reasonable approximation is in general unknown. The results from this research are expected to include a reliable method for approximating the coefficients of power series in more than one variable. This will then allow approximate solutions to problems that range from path enumeration, to queuing problems (computing efficiency of networks of production), to analysis of the speed of algorithms (the original motivation for this project).