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$.
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}$$
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