Vertex (resp. Edge) Reinforced Random Walks (VRRW, resp ERRW),
introduced in 1986 by Coppersmith and Diaconis, are nearest-neighbour
walks on a discrete graph such that, at each time step, the
probability to visit an adjacent vertex is proportional to a function
- called the weight function - of the number of visits to this vertex
(resp. to the corresponding edge).
After a brief introduction to these self-interacting processes, we
focus in this minicourse on their localization properties under
certain assumptions, which leads them to asymptotically only visit a
finite connected set infinitely often.
We start by a short alternative proof of the result of Pemantle of
Volkov (1999) that, on the integers, linearly VRRWs (i.e. VRRW with
linear weight function) only visit finitely many vertices a.s. and
that they localize on five vertices with positive probability. The
technique enables us to describe the asymptotic occupation of the walk
conditionally on a localization on five particular consecutive
vertices, a result initially obtained by Bienvenue in 1999 by the use
of the Rubin construction.
Next we introduce this Rubin construction of a continuous-time version
of ERRWs by the use of exponentially distributed random times, and its
natural adaptation to VRRWs by Bienvenue in 1999. We explain how it
enables to show localization of strongly-reinforced random walks (i.e.
with reciprocally summable weight function) on certain graphs.
Although the linearly VRRW obviously does not satisfy the reciprocal
summability assumption, we show how an alternative Rubin construction
enables us to give a relatively short proof of the conjecture of
Pemantle and Volkov that the walk on the integers a.s. localizes on
five vertices, which we initially showed in 2004.
If time allows, we will then give the sketch of the proof of a joint
result with Benaim (2008), which generalizes a theorem of Volkov
(2001) and shows that, on arbitrary graphs, the linearly VRRW
localizes with positive probability on subsets which consist of a
complete $d$-partite subgraph and its outer boundary, for some
$d\ge1$. Our technique is based on a thorough description of the
dynamics by an associated linear replicator differential equation,
originally introduced by Pemantle (1992) and Benaim (1997).
Notes 1
Notes 2
Notes 3