Andrew Beveridge

Andrew Beveridge

Math Professor

Random Walks and the Meeting Time for Trees

Published in TBD, 2025

A. Beveridge, B. Bridenbaugh, A. Holcombe-Pomerance, Random Walks and the Meeting Time for Trees, https://arxiv.org/abs/2508.02804

Preprint link: https://arxiv.org/abs/2508.02804

Consider a random walk on a tree $G=(V,E)$. For $v,w \in V$, let the hitting time $H(v,w)$ denote the expected number of steps required for the random walk started at $v$ to reach $w$, and let $\pi_v = \deg(v)/2|E|$ denote the stationary distribution for the random walk. We characterize the extremal tree structures for the meeting time $T_{\mathrm{meet}}(G) = \max_{w \in V} \sum_{v \in V} \pi_v H(v,w)$. For fixed order $n$ and diameter $d$, the meeting time is maximized by the broom graph. The meeting time is minimized by the balanced double broom graph, or a slight variant, depending on the relative parities of $n$ and $d$.