Videos

Markov chains on partitions and their diffusion analogs

Presenter
December 5, 2016
Abstract
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.
Supplementary Materials