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

Yizhen Zhang, Zihan Tan, Bhaskar KrishnamachariarXiv 2014 · arXiv

Abstract

This paper investigates the expected meeting time of two independent random walkers on $d$-regular graphs. By transforming the problem into a relative position walk and applying spectral graph theory, the authors derive an exact analytical expression for meeting times on circles and tori. Furthermore, they provide theoretical and empirical evidence that this elegant eigenvalue-based relationship holds universally for all regular graphs.

Introduction

In the study of networked systems, random walks are a fundamental tool for tasks such as database searching and information routing. A classic problem in this field is determining the "meeting time"—the expected time required for two independent walkers to reach the same node. While "hitting time" (the time to reach a fixed destination) is well-understood, meeting time is more complex because both targets are in motion. This paper seeks a general, exact analytical expression for the expected meeting time ($E[\tau]$) on $d$-regular graphs, where every node has an identical number of neighbors.

Methodology

The Relative Position Trick

To simplify the dynamics of two simultaneous walkers, the authors employ a transformation that fixes one walker at a specific node (the "origin") and analyzes the transition matrix of the relative position of the second walker. If the original transition matrix is $P$, the relative transition matrix is defined as $M = P \cdot P^T$.

The relative position trick simplifies the two-walker problem by fixing one node as the origin and analyzing the relative movement of the second walker.

Spectral Analysis

The authors define a Laplacian matrix $L = I - M$. In spectral graph theory, the eigenvalues of a Laplacian matrix reveal critical information about a graph's connectivity and diffusion properties. For 1-D circles and 2-D tori, the transition matrices possess highly symmetric structures (circulant and block-circulant), allowing the authors to explicitly calculate eigenvalues and solve recurrence equations for the expected meeting time.

Key Results and Discussion

Exact Formulas and Scaling Laws

The authors prove that for 1-D circles and 2-D tori, the expected meeting time is exactly the sum of the reciprocals of the non-zero eigenvalues of the Laplacian $L$: $$E[\tau] = \sum_{i \neq 0} \lambda_i^{-1}$$

Mapping a 2-D torus to a grid allows for the analytical calculation of meeting times using block-circulant matrix properties.

This relationship highlights how the "shape" of the graph dictates meeting dynamics. In a 1-D ring of size $N$, the meeting time grows quadratically, $\Theta(N^2)$. In a 2-D $N \times N$ torus, an additional logarithmic factor appears, $\Theta(N^2 \log N)$, indicating a relative slowdown in the meeting process as the dimensionality increases.

Generalization via Conjecture

To move beyond symmetric graphs, the authors propose a conjecture regarding the eigenvectors of adjacency matrices for any connected $d$-regular graph. They demonstrate that if this conjecture holds, their eigenvalue formula for meeting time is universal. Empirical validation using synthetic simulations on randomly generated $d$-regular graphs shows a near-perfect alignment between theoretical predictions and observed meeting times, supporting the formula's robustness.

Conclusion and Future Work

This research establishes a striking link between a dynamic stochastic process and the static algebraic properties of a graph. However, several avenues for future work remain. The current analysis is restricted to $d$-regular graphs, whereas many real-world networks follow power-law distributions. Additionally, the study is limited to two walkers and assumes they start from a steady-state distribution. Future research may extend these spectral methods to multi-walker scenarios and non-regular network topologies.

Summary updated

BibTeX
@misc{zhang2014meeting,
  author = {Yizhen Zhang and Zihan Tan and Bhaskar Krishnamachari},
  title = {{On the Meeting Time for Two Random Walks on a Regular Graph}},
  year = {2014},
  eprint = {1408.2005},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1408.2005},
}
Figure