  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.
