Combinatorial Stochastic Processes

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

The project will continue an ongoing study of deep connections between the theory of combinatorial structures on a large finite set, such as trees, forests, mappings, and partitions, and the theory of stochastic processes such as Brownian excursion and Levy processes. Specific topics to be studied include exchangeable coalescent processes, random Gibbs partitions and fragmentations, coherent combinatorial structures, partial exchangeability, consistent systems of fragmentations, continuum tree limits, occupancy problems and power laws for random discrete distributions, and Bayesian inference. There has been a rich interplay of ideas between these subjects in the last few years, and it is expected that much more remains to be discovered as present models for the asymptotics of various combinatorial structures are challenged by problems arising in various application areas. One general theme is the rich variety of models of random discrete distributions which arise when unit of mass continuously distributed in the leaves of a continuum random tree is decomposed in various ways, such as by projection onto a branch of the tree, or by cutting with a Poisson point process of cuts along branches of the tree. Such constructions lead to models for random discrete distributions with natural interpretations in application contexts, for instance the Poisson cuts may represent mutations in a phylogenetic tree. Results of the project should provide deeper understanding of models for the evolution of random partitions and partition-valued processes, particularly processes of fragmentation and coagulation. Such results should be of value in the numerous fields where such processes have been applied before, including physics, astronomy, genetics, phylogeny, ecology, and document analysis. In particular, the application of random discrete distributions with power law tails to model the distribution of topics among scientific documents may provide improved methods for classification and navigation of large bodies of scientific literature.