Combinatorial stochastic processes. Ecole d'Eté de Probabilités de Saint-Flour XXXII -- 2002. (Q2492015): Difference between revisions

This is a collection of expository articles (``chapters'') about various topics at the interface between enumerative combinatorics and stochastic processes. The aim of this course is the study of various combinatorial models of random partitions and random trees, and the asymptotics of these models related to continuous parameter stochastic processes. A basic feature of models for random partitions is that the sum of the parts is usually constant. So the sizes of the parts cannot be independent. But the structure of many natural models for random partitions can be reduced by suitable conditioning or scaling to classical probabilistic results involving sums of independent random variables. Limit models for combinatorially defined random partitions are consequently related to the two fundamental limit processes of classical probability theory: Brownian motion and Poisson processes. Following is a list of the main topics to be treated: * models for random combinatorial structures, such as trees, forests, permutations, mappings, and partitions; * probabilistic interpretations of various combinatorial notions, e.g. Bell polynomials, Stirling numbers, polynomials of binomial type, Lagrange inversion; * Kingman's theory of exchangeable random partitions and random discrete distributions; * connections between random combinatorial structures and processes with independent increments: Poisson-Dirichlet limits; * random partitions derived from subordinators; * asymptotics of random trees, graphs and mappings related to excursions of Brownian motions; * continuum random trees embedded in Brownian motion; * Brownian local times and squares of Bessel processes; * various processes of fragmentation and coagulation, including Kingman's coalescent, the additive and multiplicative coalescents. Each chapter is fairly self-contained, so readers with adequate background can start reading any chapter, with occasional consultation of earlier chapters as necessary.