Colloquium
3:00 p.m., Friday (Jan. 4, 2002)
Math Annex 1100
Vlada Limic
Cornell University
Properties of random walks with memory
Let G be a connected graph. Imagine a particle moving along the vertices of
G according to the following rules:
(i) if currently at vertex v, in the next step the particle jumps
to one of the neighbors of v,
(ii) the probability of a jump to a neighbor v' is proportional
to the number of previous traversals of the edge connecting v
and v'.
This process is the original reinforced random walk introduced by
Coppersmith and Diaconis in 1987 as a model of a person exploring
a new city. The reinforced random walk and its generalizations
became important ingredients in models of spatial exploration
and cooperative interaction. These processes often yield new and
surprising behavior. There are no general techniques developed
for studying them. I will list major open questions and discuss
two recent results: attracting edge property under strong power
law reinforcements, and transience of oncereinforced walks on
regular trees.
