The Moran forest

Abstract : 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.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal.sorbonne-universite.fr/hal-02165001
Contributor : Félix Foutel-Rodier <>
Submitted on : Tuesday, June 25, 2019 - 3:09:49 PM
Last modification on : Saturday, June 29, 2019 - 1:18:20 AM

File

moran_forest.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02165001, version 1
  • ARXIV : 1906.08806

Citation

François Bienvenu, Jean-Jil Duchamps, Félix Foutel-Rodier. The Moran forest. 2019. ⟨hal-02165001⟩

Share

Metrics

Record views

16

Files downloads

24