-
Trickle-down growth models, Doob-Martin boundaries, and random matrices
- Several Markov chains appearing in applied probability (for example, the random binary search tree and recursive random tree processes) may be viewed as growing connected subsets of a graph that evolve according to the following general dynamics: initially, all vertices of the graph are unoccupied, particles are fed in one-by-one at a distinguished source vertex, successive particles proceed along directed edges according to an appropriate stochastic mechanism, and each particle comes to rest once it encounters an unoccupied vertex. I will explain how classical tools from Doob-Martin boundary theory may be used to understand the large time asymptotics of such processes. Along the way, we will encounter objects such as Polya urns, Dirichlet random measures, Pitman's generalization of the Ewens sampling formula, and Chinese restaurant processes. If time permits, I will also discuss tools for understanding the asymptotics of the spectra of various random matrices associated with these models.
