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.
