A self-similar invariance of critical binary Galton-Watson trees (Q1975188): Difference between revisions

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.