One can cut down a rooted tree by repeatedly randomly selecting edges and deleting the selected edge and the subtree depending on it, until only the root remains. Given a tree \(T\), the random variable \(X(T)\) is the number of cuts one may make before the tree is completely cut down.
In this paper, the distributions of \(X(T)\) and related random variables are studied in considerable depth. This paper is advertized as a development following [A. Meir and J. W. Moon, J. Aust. Math. Soc. 11, 313–324 (1970; Zbl 0196.27602)], as a companion to [S. Janson, “Random records and cuttings in complete binary trees”, in Mathematics and computer science III, Algorithms, trees, combinatorics and probabilities. Basel: Birkhäuser. Trends in Mathematics, 241–253 (2004; Zbl 1063.60018)], using proof techniques developed by D. Aldous.
The primary distribution used in selecting the edge to be cut is the uniform distribution, which is motivated by assigning to each edge \(e\) a (distinct) random value \(\lambda_e\), which is a record if it is the largest value on the path from \(e\) to the root. This article concerns trees generated by (conditioned) Galton-Watson processes, where the offspring random variable \(\xi\) satisfies \(\mathbb E (\xi) = 1\) and Var \(\xi = \sigma < \infty\). The primary random variables studied in this paper are \(X(T)\) and:
\(\bullet\) The random variables \(X(\mathcal T_n)\), where \(\mathcal T_n\) is a random variable ranging over the trees of \(n\) vertices.
\(\bullet\) The random variables \(w_k(\mathcal T_n)\), the number of vertices of depth (rank) \(k\) in \(\mathcal T_n\).
\(\bullet\) The random variables \(m_k(\mathcal T_n) = \mathbb E (X(\mathcal T_n)^k | \mathcal T_n)\) pervade this paper; these are associated with functionals \(m_k\) defined on real-valued functions on an interval.
The primary results are:
\(\bullet\) A normalized sequence of random variables \(X(\mathcal T_n)\) converges to a Rayleigh distribution.
\(\bullet\) There are several results using the functionals \(m_k\), e.g., if \(\mu_{\mathcal T_n}\) is the random distribution of \(X(\mathcal T_n)/\sqrt {n\sigma^2}\), then as \(n \to \infty\), \(\mu_{\mathcal T_n}\) converges in distribution to a measure defined in terms of \(m_k(2B_{\text{ex}})\), where \(B_{\text{ex}}\) is a normalized Brownian excursion.
And several significant asymptotic formulas for (conditional) variance and expectation of \(X(\mathcal T_n)\) are developed. In addition, if \(r \geq 1\) is an integer with \(\mathbb E \xi^{r+1} < \infty\), then for some fixed \(C\), \(\mathbb E(w_k(\mathbb T_r)^r) \leq C k^r\); further, the article asks if \(\mathbb E w_k(\mathbb T_n)\) is an increasing function of \(n\) (thus raising the entire issue of the asymptotics of these functions in general). Much of the paper consists of proofs of these results, which are dense but accessible (the statement of Lemma 4.4 should have the interval \([0, 2n]\), not \([0, 1]\); watch the normalizations carefully!).
The second half of the paper turns to vertex rather than edge cuttings, although the two random variables \(X(T)\) and \(X_v(T)\) are coupled, allowing results to be developed from the first half of the paper. Similarly arising from the initial computations are normalized asymptotics on the (normalized) heights and weights of random trees. And one may fiddle with \(m_k\) to get what appears to be a glimmering of a calculus of random variables \(X(\mathbb T_i)\), \(i = 1, 2, 3, \ldots\), although the author only presents formal results on the variants of \(m_k\) and instead of formally connecting them with the construction of trees, merely presents a few tantalizing examples, “leaving the details to the interested reader.”