Insertion depth in power-weight trees

• Published in: Information processing letters 2022-06, Vol.176, p.106227, Article 106227
• Main Authors: Lyon, Merritt, Mahmoud, Hosam
• Format: Article
• Language: English
• Subjects: Chen-Stein method; Graph algorithms; Insertion depth; Preferential attachment; Random tree
• ISSN: 0020-0190; 1872-6119
• DOI: 10.1016/j.ipl.2021.106227

•Many real-world networks display attachment preference based on node age.•We introduce a random tree model with preferential attachment based on node index (age).•The form of index (age) preference is controlled by a real-valued parameter.•We study insertion depth in our attachment model and find that the behavior varies depending on the value of the parameter. We study the insertion depth in a class of nonuniform random recursive trees grown with an attachment preference for a power of the node index. The strength of index preference is controlled by a real-valued power parameter α; the model accommodates both young-age and old-age preference as specific cases. We find the exact probability law in terms of the Poisson-Binomial distribution, and consequently, the exact and asymptotic mean and variance. Under appropriate normalization, we derive concentration laws and limiting distributions. For α>−1, with logarithmic normalization of the depth, we have a normal limit. The case α=−1 is a critical point at which we retain a normal limit but under an iterated logarithm normalization. For these normal cases, Chen-Stein approximation gives a slow rate of convergence in the Wasserstein distance. The case α