A self-similar invariance of critical binary Galton-Watson trees
type: Item
instance of: scholarly article
title: A self-similar invariance of critical binary Galton-Watson trees
zbMATH Open document ID: 0967.60081
DOI: 10.2307/3318630
author: Gregory A. Burd
author: Edward C. Waymire
author: Ronald D. Winn
published in: Bernoulli
publication date: 2001-08-23T00:00:00Z
full work available at URL: https://projecteuclid.org/euclid.bj/1082665377
review text: A pruning and compression operator on finite trees is introduced. The pruning cuts away all branches leading to only one leaf; the compression identifies all nodes with only one daughter node on a branch. A distribution, \(P\), on finite trees is called stochastically self-similar if, conditional on the tree not being just the root, the distribution of the pruned and compressed tree is also \(P\). The operator can be applied repeatedly, until only the root is left. One plus the number of applications needed for this is called the order of the tree, denoted by \(W\). The order of any node is the order of the sub-tree emanating from it. A stream of order \(i\) is that part of a line of descent containing only nodes of order \(i\); the terminal node of a stream is the one that has no daughter nodes of order \(i\). Let \(T_{i,j}\) be the number of trees of order \(j\) \((<i)\) emanating from the non-terminal nodes of a stream of order \(i\). Consideration of \(T_{i,j}\) is motivated by empirical observations on the branching structure of river systems. The main result is that if \(P\) is a Galton-Watson law with finite maximum family size, the following are equivalent: \(P\) is stochastically self-similar; the family size is critical binary splitting; \(W\) is geometric; \(E[T_{i,j}\mid W \geq i+1]\) is a function of \(i-j\) only.
Mathematics Subject Classification ID: 60J80
zbMATH DE Number: 1428368
zbMATH Keywords: conditioned limits
zbMATH Keywords: Galton-Watson trees
zbMATH Keywords: pruning
zbMATH Keywords: self-similarity
MaRDI profile type: Publication
OpenAlex ID: W1990601781
description: scientific article; zbMATH DE number 1428368