The Moran forest - Sorbonne Université Accéder directement au contenu
Article Dans Une Revue Random Structures and Algorithms Année : 2021

The Moran forest

Résumé

Starting from any graph on {1, ..., n}, consider the Markov chain where at each time-step a uniformly chosen vertex is disconnected from all of its neighbors and reconnected to another uniformly chosen vertex. This Markov chain has a stationary distribution whose support is the set of non-empty forests on {1, ..., n}. The random forest corresponding to this stationary distribution has interesting connections with the uniform rooted labeled tree and the uniform attachment tree. We fully characterize its degree distribution , the distribution of its number of trees, and the limit distribution of the size of a tree sampled uniformly. We also show that the size of the largest tree is asymptotically α log n, where α = (1 − log(e − 1)) −1 ≈ 2.18, and that the degree of the most connected vertex is asymptotically log n/ log log n.
Fichier principal
Vignette du fichier
1906.08806.pdf (710.04 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02165001 , version 1 (25-06-2019)
hal-02165001 , version 2 (26-04-2021)
hal-02165001 , version 3 (16-02-2024)

Identifiants

Citer

François Bienvenu, Jean-Jil Duchamps, Félix Foutel-Rodier. The Moran forest. Random Structures and Algorithms, 2021, 59 (2), pp.155-188. ⟨10.1002/rsa.20997⟩. ⟨hal-02165001v3⟩
115 Consultations
46 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More