  Motivated by studies on the recurrent properties of animal and human
mobility, we introduce a path-dependent random walk model with long range
memory for which not only the mean square displacement (MSD) can be obtained
exactly in the asymptotic limit, but also the propagator. The model consists of
a random walker on a lattice, which, at a constant rate, stochastically
relocates at a site occupied at some earlier time. This time in the past is
chosen randomly according to a memory kernel, whose temporal decay can be
varied via an exponent parameter. In the weakly non-Markovian regime, memory
reduces the diffusion coefficient from the bare value. When the mean backward
jump in time diverges, the diffusion coefficient vanishes and a transition to
an anomalous subdiffusive regime occurs. Paradoxically, at the transition, the
process is an anti-correlated L\'evy flight. Although in the subdiffusive
regime the model exhibits some features of the continuous time random walk with
infinite mean waiting time, it belongs to another universality class. If memory
is very long-ranged, a second transition takes place to a regime characterized
by a logarithmic growth of the MSD with time. In this case the process is
asymptotically Gaussian and effectively described as a scaled Brownian motion
with a diffusion coefficient decaying as 1/t.
