Controlled Diffusion on Graphs

Speaker: Miklos Racz (Microsoft Research)

Abstract: Starting from a unit mass on a vertex of a graph, we investigate the minimum number of "controlled diffusion" steps needed to transport a constant mass outside of the ball of radius \$n\$. In a step of a controlled diffusion process we may select any site with positive mass and topple its mass equally to its neighbors. Our main result shows that on \$Z^d\$, on the order of \$n^{d+2}\$ steps are necessary and sufficient. We also present sharp bounds for several other graphs, such as the comb, regular trees, Galton-Watson trees, and more. This is joint work with Laura Florescu and Yuval Peres.