Fine asymptotics for the maximum degree in weighted recursive trees with bounded random weights

Laura Eslava, Bas Lodewijks, Marcel Ortgiese

Research output: Contribution to journalArticlepeer-review

4 Citations (SciVal)
60 Downloads (Pure)

Abstract

A weighted recursive tree is an evolving tree in which vertices are assigned random
vertex-weights and new vertices connect to a predecessor with a probability proportional to its weight. Here, we study the maximum degree and near-maximum degrees in weighted recursive trees when the vertex-weights are almost surely bounded and their distribution function satisfies a mild regularity condition near zero. We are able to specify higher-order corrections to the first order growth of the maximum degree established in prior work. The accuracy of the results depends on the behaviour of the weight distribution near the largest possible value and in certain cases we manage to find the corrections up to random order. Additionally, we describe the tail distribution of the maximum degree, the distribution of the number of vertices attaining the maximum degree,
and establish asymptotic normality of the number of vertices with near-maximum degree. Our analysis extends the results proved for random recursive trees (where the weights are constant) to the case of random weights. The main technical result shows that the degrees of several uniformly chosen vertices are asymptotically independent with explicit error corrections.
Original languageEnglish
Pages (from-to)505-569
JournalStochastic Processes and their Applications
Volume158
Early online date25 Jan 2023
DOIs
Publication statusPublished - 30 Apr 2023

Funding

BL has been funded by an URSA whilst at the University of Bath and is currently funded by the grant GrHyDy ANR-20-CE40-0002 . LE was partially supported by the grant PAPIIT IN102822 .

Fingerprint

Dive into the research topics of 'Fine asymptotics for the maximum degree in weighted recursive trees with bounded random weights'. Together they form a unique fingerprint.

Cite this