The Dispersion Time of Random Walks on Finite Graphs.

Abstract: Consider two random processes on an n vertex graph related to Internal Diffusion-Limited Aggregation (IDLA). In each process n particles perform independent random walks from a fixed vertex until they reach an unvisited vertex, at which point they settle. In the first process only one particle moves until settling and then the next starts, in the second process all particles are released together.

We study the dispersion time which is the time taken for the longest walk to settle. We present a new coupling which allows us to compare dispersion time across the processes. We additionally prove bounds on the dispersion time(s) in terms of more well-studied parameters of random walks such as hitting times and the mixing time.

Posted on Apr 26, 2021 in ACGO, Seminars