Random Walks with Pheromone

In this thesis we are interested in random walks on graphs where transition probabilities from each vertex depend on values of a function, f, at neighboring nodes. The work is motivated by applications that arise in bio-inspired models wherein questions of dynamics are effected by pheromone trails. In Chapter 2, we discuss when the graph is the n-cycle, and the set of non-zero function values (the trail) is generated by visits of a simple random walk. We show that an optimal trail length is, in some sense, approximately one third of the cycle length. In Chapter 3, we consider non-contiguous subsets of the n-cycle. Here, a first random walker leaves maps (indicating a shortest path to a point s) in a possibly non-contiguous subset, S. We are then interested in minimizing the expected time required for a second uniformly random located second walker to reach s (utilizing these maps when found). We show that the expected time is minimized when the maps are in a sense, evenly distributed on the cycle. The thesis concludes with some results (and a conjecture) regarding when f values are determined by a large number of random walks departing from a point s in Z and leaving accumulating pheromone.

Grantor dc:publisher

Wake Forest University

Year dc:date.issued

2013

Author dc:creator

• Wei, Shuowen

• generating function

Language dc:language.iso

en

Handle dc:identifier.uri

http://hdl.handle.net/10339/39015

OAI identifier oai:identifier

oai:wakespace.lib.wfu.edu:10339/39015