Recurrence, transience and degree distribution for the Tree Builder Random Walk
Authors:
- 1 November 2025
- journal article
- Published by Institute of Mathematical Statistics in Annales de l'Institut Henri Poincaré, Probabilités et Statistiques
- Vol. 61 (4) , 2553-2578
Abstract
Nous étudions une marche aléatoire sur un arbre aléatoire construit par le marcheur lui-même, alors qu’il se promène. Au temps n=1,2,…, juste avant de faire un pas, le marcheur aléatoire ajoute un nombre aléatoire (éventuellement zéro) Zn de feuilles à sa position actuelle. Nous supposons que les Zn sont indépendants, mais pas nécessairement identiquement distribuées. Nous obtenons des conditions sur leurs distributions sous lesquelles la marche aléatoire est récurrente. Ce résultat contraste avec certains travaux antérieurs dans lesquels, sous l’hypothèse que Zn∼Ber(p) (donc i.i.d.), la marche aléatoire s’est avérée balistique pour chaque p∈(0,1]. Nous obtenons également des résultats sur la transience de la marche aléatoire, et sur la possibilité qu’elle “reste bloquée”. Du point de vue de l’environnement, nous fournissons des informations structurelles sur la séquence d’arbres aléatoires générés par le modèle lorsque Zn∼Ber(pn), avec pn=Θ(n−γ) et γ∈(2/3,1]. Nous prouvons que la distribution de degré empirique de cette séquence d’arbres aléatoires converge presque sûrement vers une loi de puissance d’exposant 3, révélant ainsi un lien avec le modèle de Barabási–Albert.Keywords
All Related Versions
This publication has 38 references indexed in Scilit:
- Cover time and mixing time of random walks on dynamic graphsRandom Structures & Algorithms, 2017
- Growing Networks Through Random Walks Without Restarts2016
- Transience of Edge-Reinforced Random WalkCommunications in Mathematical Physics, 2015
- Concentration Inequalities for Sums and Martingales2015
- Random walks on dynamical percolation: mixing times, mean squared displacement and hitting timesProbability Theory and Related Fields, 2014
- Multi-excited random walks on integersProbability Theory and Related Fields, 2005
- The degree sequence of a scale‐free random graph processRandom Structures & Algorithms, 2001
- Dynamics of stochastic approximation algorithms1999
- Extremal cover times for random walks on treesJournal of Graph Theory, 1990
- Reinforced random walkProbability Theory and Related Fields, 1990