INTRODUCTION

Many different models of random trees have arisen in a variety of applied setting, and there is a large but scattered literature on exact and asymptotic results for particular models. For several years I have been interested in what kinds of “general theory” (as opposed to ad hoc analysis of particular models) might be useful in studying asymptotics of random trees. In this paper, aimed at theoretical probabilists, I discuss aspects of this incipient general theory which are most closely related to topics of current interest in theoretical stochastic processes. No prior knowledge of this subject is assumed: the paper is intended as an introduction and survey.

To give the really big picture in a paragraph, consider a tree on n vertices. View the vertices as points in abstract (rather than d-dimensional) space, but let the edges have length (= 1, as a default) so that there is metric structure: the distance between two vertices is the length of the path between them. Consider the average distance between pairs of vertices. As n → ∞ this average distance could stay bounded or could grow as order n, but almost all natural random trees fall into one of two categories. In the first (and larger) category, the average distance grows as order logn. This category includes supercritical branching processes, and most “Markovian growth” models such as those occurring in the analysis of algorithms. This paper is concerned with the second category, in which the average distance grows as order n½.