Tree-valued Markov chains and Poisson-Galton-Watson distributions
David Aldous · DIMACS series in discrete mathematics and theoretical computer science · 1998
. The Poisson-Galton-Watson distribution on finite trees, and the related PGW 1 (1) distribution on infinite trees with one end, arise in several contexts, in particular as n !1 weak limits within various size-n combinatorial models. We review this topic, introducing slick notation for describing such distributions. We then describe a family of continuous-time Markov chains whose marginal distributions are of Poisson-Galton-Watson type. Different chains in this family have connections with different parts of the extensive literature on tree and forest-valued chains (the random graph process, stochastic coalescence, spanning tree chains) and also illustrate the classical state-spacecompactification theory of continuous-time countable-state chains. 1. Introduction Tree- and forest-valued Markov chains have been studied in several areas. ffl Evolution of tree-based data structures (Knuth [13], Mahmoud [16]). ffl The Markov chain tree theorem (Pemantle [18], Lyons-Peres [15]), which t...