Cutting down \(\mathbf{p}\)-trees and inhomogeneous continuum random trees. (English) Zbl 1388.60036

This paper is about random rooted trees. We initially consider a finite vertex set \(A\) and a probability distribution \(\mathbf{p}=(p_{1},p_{2},.\dots p_{| A|})\) on \(A\) (with all probabilities strictly positive) and select tree \(T\) with probability \(\prod_{u\in A}p_{u}^{C_{u}(t)}\) where \(C_{u}(t)\) is the indegree of vertex \(u\) in tree \(t\) when we think of edges as being oriented towards the root. (This is a probability distribution, by a version of Cayley’s formula). These are the \(\mathbf{p}\)-trees of M. Camarri and J. Pitman [Electron. J. Probab. 5, Paper No. 1, 19 p. (2000; Zbl 0953.60030)].
The tree is cut down to the root by choosing a vertex at random, according to \(\mathbf{p}\) conditioned on the remaining part containing a random vertex \(V\) according to \(\mathbf{p}\) at each stage, and we retain the component which contains \(V\). Let \(L(T)\) denote the time until \(V\) is chosen. There is a tree which encodes this fragmentation process, and one theme of the paper is to demonstrate certain exact correspondences between the original tree and the encoding tree.
The limit objects of \(\mathbf{p}\)-trees are inhomogeneous continuum random trees (Aldous’ original Brownian continuum random tree corresponds to the case of \(\mathbf{p}\) being uniform on \(A\)). The results referred to at the end of the last paragraph allow distributional correspondences between the initial inhomogeneous continuum random tree and a similar tree which encodes the fragmentation.


60C05 Combinatorial probability
05C80 Random graphs (graph-theoretic aspects)
60F17 Functional limit theorems; invariance principles


Zbl 0953.60030
Full Text: DOI arXiv Euclid