Random walks with preferential relocations and fading memory: a study through random recursive trees

Abstract

Consider a stochastic process that behaves as a $d$-dimensional simple and symmetric random walk, except that, with a certain fixed probability, at each step, it chooses instead to jump to a given site with probability proportional to the time it has already spent there. This process has been analyzed in the physics literature under the name "random walk with preferential relocations", where it is argued that the position of the walker after $n$ steps, scaled by $\log n$, converges to a Gaussian random variable; because of the $\log$ spatial scaling, the process is said to undergo a "slow diffusion". In this paper, we generalize this model by allowing the underlying random walk to be any Markov process and the random run-lengths (time between two relocations) to be i.i.d.-distributed. We also allow the memory of the walker to fade with time, meaning that when a relocations occurs, the walker is more likely to go back to a place it has visited more recently. We prove rigorously the central limit theorem described above (plus a local limit theorem and the convergence of the weighted occupation measure) by associating to the process a growing family of vertex-weighted random recursive trees and a Markov chain indexed by this tree. The spatial scaling of our relocated random walk is related to the height of a "typical" vertex in the random tree. This typical height can range from doubly-logarithmic to logarithmic or even a power of the number of nodes of the tree, depending on the form of the memory.

References in corpus (12)

• Diffusion with Stochastic Resetting
• A survey of random processes with reinforcement
• Elephants can always remember: Exact long-range memory effects in a non-Markovian random walk
• Random walks with preferential relocations to places visited in the past and their application to biology
• Elephant Random Walks and their connection to Pólya-type urns
• Localization transition induced by learning in random searches
• Central Limit Theorem for the Elephant Random Walk
• Long time scaling behaviour for diffusion with resetting and memory
• The Shark Random Swim (Lévy flight with memory)
• Slow Lévy flights
• Self-similar scaling limits of non-increasing Markov chains
• A functional limit theorem for the profile of $b$-ary trees

Cited by in corpus (10)

• Stochastic Resetting and Applications
• On a class of random walks with reinforced memory
• Fine asymptotics for the maximum degree in weighted recursive trees with bounded random weights
• Power-law relaxation of a confined diffusing particle subject to resetting with memory
• The location of high-degree vertices in weighted recursive graphs with bounded random weights
• Emerging correlations between diffusing particles evolving via simultaneous resetting with memory
• Diffusion with preferential relocation in a confining potential
• Depths in random recursive metric spaces
• A random recursive tree model with doubling events
• Ultra slow sub-logarithmic diffusion of a sluggish random walker subject to resetting with memory