On the Meeting Time for Two Random Walks on a Regular Graph

Yizhen Zhang, Zihan Tan, Bhaskar Krishnamachari

We provide an analysis of the expected meeting time of two independent random walks on a regular graph. For 1-D circle and 2-D torus graphs, we show that the expected meeting time…