the Galton-Watson tree
/ GAWL-ton WOT-son /
The Galton-Watson process counts how many individuals are alive in each generation, but it forgets the family structure — who is whose child. The Galton-Watson tree restores that structure: it is the full random genealogical tree, the rooted tree whose root is the ancestor and where each individual has a random number of children drawn from the offspring law. Shifting attention from the population count Z_n to the whole tree is the move that opens the door to the deepest modern results, because the tree carries information (heights, contour, subtree shapes) invisible to the count alone.
Formally, a (plane, rooted) Galton-Watson tree T with offspring law (p_k) is the random tree in which the root has Offspring(p) children, each child independently has Offspring(p) children, and so on; the tree is finite if and only if the process goes extinct. Its key statistics: the total number of vertices |T| (the total progeny) has a generating function solving the Lagrange/Otter-Dwass equation — for a critical or subcritical tree, P(|T| = n) is given exactly by the cycle lemma, P(|T| = n) = (1/n) P(X_1 + ... + X_n = n - 1) where X_i are iid offspring. The height (depth of the deepest vertex) and the width also have rich limit laws. A central encoding is the contour or depth-first walk: traverse the tree depth-first and record the height of the current vertex, producing a path that, for a critical finite-variance tree conditioned to be large, becomes (after scaling) a Brownian excursion. Conditioning a Galton-Watson tree to have exactly n vertices yields, for many offspring laws (those in the domain of attraction of a Gaussian — equivalently the simply generated / conditioned GW trees), a single universal scaling limit.
Why it matters: the Galton-Watson tree is the model of a random tree, and conditioned versions are equivalent to uniform random labelled trees, random plane trees, and the cores of sparse random graphs — the contour-walk encoding is the technical heart of these equivalences. The honest content is the role of conditioning and moment assumptions: an unconditioned critical tree is finite almost surely but of random size; the beautiful scaling limit (the continuum random tree) emerges only after conditioning on size n and rescaling distances by sqrt(n), and only for offspring laws with finite variance — heavy-tailed offspring give stable trees with a different fractal dimension. The tree and its contour are different objects: do not confuse the genealogical height with the contour-process time index.
A critical geometric Galton-Watson tree, conditioned to have exactly n vertices, looks (after rescaling its graph distances by 1/sqrt(n)) like the same universal random fractal regardless of the precise offspring law, as long as the offspring variance is finite. Its contour walk, rescaled, converges to a normalized Brownian excursion — the encoding behind the continuum random tree.
Encode the tree by its depth-first contour walk; conditioned and rescaled, it becomes a Brownian excursion.
The universal scaling limit (the continuum random tree) requires conditioning on the total size n, rescaling distances by sqrt(n), AND finite offspring variance; heavy-tailed offspring give stable trees with a different dimension. The contour-process time index is not the genealogical height.