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

Cecile Mailler, Gerónimo Uribe Bravo

Research output: Contribution to journalArticle

1 Downloads (Pure)

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 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, converges to a Gaussian random variable; because of the 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 rigorously prove that 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.
Original languageEnglish
Article number093206
Pages (from-to)1-50
Number of pages50
JournalJournal of Statistical Mechanics-Theory and Experiment
Volume2019
Issue number9
DOIs
Publication statusPublished - 18 Sep 2019

Cite this

Random walks with preferential relocations and fading memory: a study through random recursive trees. / Mailler, Cecile; Uribe Bravo, Gerónimo.

In: Journal of Statistical Mechanics-Theory and Experiment, Vol. 2019, No. 9, 093206, 18.09.2019, p. 1-50.

Research output: Contribution to journalArticle

@article{31fc50efe6af4c36a9595bad8452f2b4,
title = "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 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, converges to a Gaussian random variable; because of the 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 rigorously prove that 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.",
author = "Cecile Mailler and {Uribe Bravo}, Ger{\'o}nimo",
year = "2019",
month = "9",
day = "18",
doi = "10.1088/1742-5468/ab081f",
language = "English",
volume = "2019",
pages = "1--50",
journal = "Journal of Statistical Mechanics-Theory and Experiment",
issn = "1742-5468",
publisher = "IOP Publishing",
number = "9",

}

TY - JOUR

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

AU - Mailler, Cecile

AU - Uribe Bravo, Gerónimo

PY - 2019/9/18

Y1 - 2019/9/18

N2 - 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 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, converges to a Gaussian random variable; because of the 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 rigorously prove that 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.

AB - 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 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, converges to a Gaussian random variable; because of the 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 rigorously prove that 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.

U2 - 10.1088/1742-5468/ab081f

DO - 10.1088/1742-5468/ab081f

M3 - Article

VL - 2019

SP - 1

EP - 50

JO - Journal of Statistical Mechanics-Theory and Experiment

JF - Journal of Statistical Mechanics-Theory and Experiment

SN - 1742-5468

IS - 9

M1 - 093206

ER -