Markov chains on partitions and their diffusion analogs

Soumik Pal
University of Washington

A popular family of models of random partitions is called the Chinese Restaurant Process. We imagine n customers being seated randomly and sequentially at tables of a restaurant according to a fixed stochastic rule. Grouping customers by the tables gives us a partition of n. Consider a Markov chain on such partitions where we remove a randomly chosen customer and reseat her. How can one describe the limit of such a Markov chain as n tends to infinity? We will construct such limits as diffusions on partitions of the unit interval. Examples of such random partitions of the unit interval are given by the complement of the zeros of the Brownian motion or the Brownian bridge. The processes of ranked interval lengths of our partitions are members of a family of diffusions introduced by Ethier and Kurtz (1981) and Petrov (2009) that are stationary with respect to the Poisson-Dirichlet distributions. Our construction is a piece of a more complex diffusion on the space of real trees, stationary with respect to the law of the Brownian Continuum Random Tree, whose existence has been conjectured by David Aldous.

Presentation (PDF File)

Back to Workshop IV: Synergies between Machine Learning and Physical Models