Random Discrete Structures

点击翻译按钮获取中文摘要

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).