Recurrence, transience and degree distribution for the Tree Builder Random Walk

Authors:

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.

This publication has 38 references indexed in Scilit: