Item Details

title

Random Walks with Pheromone

author

Wei, Shuowen

abstract

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.

subject

generating function

pheromone

random walks

toroidal graph

contributor

Berenhaut, Kenneth S (committee chair)

Rouse, Jeremy (committee member)

Erhardt, Robert (committee member)

date

2013-08-23T08:35:15Z (accessioned)

2013 (issued)

degree

Mathematics (discipline)

embargo

forever (terms)

10000-01-01 (liftdate)

identifier

http://hdl.handle.net/10339/39015 (uri)

language

en (iso)

publisher

Wake Forest University

type

Thesis