Random Recursive Trees and the Elephant Random Walk

Abstract

One class of random walks with infinite memory, so called elephant random walks, are simple models describing anomalous diffusion. We present a surprising connection between these models and bond percolation on random recursive trees. We use a coupling between the two models to translate results from elephant random walks to the percolation process. We calculate, besides other quantities, exact expressions for the first and the second moment of the root cluster size and of the number of nodes in child clusters of the first generation. We further introduce a new model, the skew elephant random walk and calculate the first and second moment of this process.

12 pages, 3 figures

References in corpus (6)

• The scaling laws of human travel
• Amnestically induced persistence in random walks
• Anomalous diffusions induced by enhancement of memory
• The fragmentation process of an infinite recursive tree and Ornstein-Uhlenbeck type processes
• Fragmentation of Random Trees
• Comment on 'Anomalous diffusion induced by enhancement of memory'

Cited by in corpus (21)

• Elephant Random Walks and their connection to Pólya-type urns
• A martingale approach for the elephant random walk
• Central Limit Theorem for the Elephant Random Walk
• A strong invariance principle for the elephant random walk
• Gaussian fluctuation for superdiffusive elephant random walks
• The Shark Random Swim (Lévy flight with memory)
• Functional limit theorems for the Multi-dimensional Elephant Random Walk
• On a class of random walks with reinforced memory
• A memory-induced diffusive-superdiffusive transition: ensemble and time-averaged observables
• Limit theorems for the 'laziest' minimal random walk model of elephant type
• Joint invariance principles for random walks with positively and negatively reinforced steps
• Weak ergodicity breaking induced by global memory effects
• Inhomogeneous diffusion and ergodicity breaking induced by global memory effects
• Limit theorems for a minimal random walk model
• Interacting elephant random walks
• Rate of moment convergence in the central limit theorem for the elephant random walk
• Non-stationary Markovian Replication Process causing Diverse Diffusions
• Recurrence and transience of multidimensional elephant random walks
• Broadcasting induced colourings of random recursive trees and preferential attachment trees
• Asymptotic Normality of Superdiffusive Step-Reinforced Random Walks
• Non-Markovian random walks with memory lapses