Coalescent random forests.

Coalescent random forests.

Report Number
457
Authors
Jim Pitman
Citation
Ann. Inst. Henri Poincare 34, 339-383, 1998
Abstract

Various enumerations of labeled trees and forests, due to Cayley, Moon, and other authors, are consequences of the following {\em coalescent algorithm} for construction of a sequence of random forests $(R_n, R_{n-1}, \cdots, R_1)$ such that $R_k$ has uniform distribution over the set of all forests of $k$ rooted trees labeled by $\INn := \{1, \cdots , n\}$. Let $R_n$ be the trivial forest with $n$ root vertices and no edges. For $n \ge k \ge 2$, given that $R_n, \cdots, R_k$ have been defined so that $R_k$ is a rooted forest of $k$ trees, define $R_{k-1}$ by addition to $R_k$ of a single directed edge picked uniformly at random from the set of $n(k-1)$ directed edges which when added to $R_k$ yield a rooted forest of $k-1$ trees labeled by $\INn$. Variations of this coalescent algorithm are described, and related to the literature of physical processes of clustering and polymerization.

PDF File
Postscript File