New Directions in Random Walk

Dartmouth College, Hanover NH

Investigators

Abstract

The PI will open and pursue several new areas of research in random walks on graphs. Among them are expected time for a random walk or Brownian particle to cover all the edges of a network; coupling of random walks in order to avoid collisions; strategies for searching and patrolling graphs; and some new ideas on "mixing time," that is, the time required for a random walk to reach a random state. The random walk on a graph has been a fundamental construction in discrete probability. The concept has numerous applications in computer science and statistical physics, and a strong connection to the theory of electrical networks. The proposed work has additional possible applications to disparate fields such as software design and policing; it brings game theory, as well as combinatorics and probability, into the random walk picture.