Nonuniform recursive trees with vertex attraction depending on their labels
The paper under review proposes a non-uniform model of random recursive trees (recall that a tree on vertex set \([n]=\{1,2,\ldots, n\}\) with root vertex 1 is said to be recursive if, for all \(2\leq k\leq n\), the labels of the vertices on the unique path from 1 to \(k\) are an increasing sequence). A model of random recursive trees is a distribution on the set of all recursive tress on \([n]\). The model introduced makes the choice of the parent \(i\) for the new node -- say \(n\) -- depends on the label of the parent \(i\), say it is \(p_{ni}\), where \(p_{ni}>0\) for all \(1\leq i\leq n-1\) and \(\sum_{i=1}^{n-1}p_{ni}=1\). The models where the attraction of vertices is proportional to their labels (i.e. \(p_{ni}=2i/(n(n-1))\)) and where the attraction is proportional to \(n-i\) (i.e. \(p_{ni}=2(n-i)/(n(n-1))\)) are of particular importance. The main results, often unsurprisingly relying on analysis of recurrent sequences, are about the degrees of vertices in the model.
scientific article; zbMATH DE number 7225513