Random Walks and the Best Meeting Time for Trees

2025/10/28 by Beveridge, Andrew, Pomerance, Ari Holcombe
#05C05 (secondary) #05C81 (primary) #60J10 (secondary) #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2510.24387

Abstract

We consider random walks on a tree G=(V,E) with stationary distribution π_v = deg(v)/2|E| for v ∈ V. Let the hitting time H(v,w) denote the expected number of steps required for the random walk started at vertex v to reach vertex w. We characterize the extremal tree structures for the best meeting time T_bestmeet(G) = min_{w ∈ V} ∑_{v ∈ V} π_v H(v,w) for trees of order n with diameter d. The best meeting time is maximized by the balanced double broom graph, and it is minimized by the balanced lever graph.

Citations

• Random Walks and the Meeting Time for Trees
• On Kemeny's constant for trees with fixed order and diameter
• Global first passage times on fractal lattices

Related

• Random Walks and the Meeting Time for Trees
• The Best Mixing Time for Random Walks on Trees
• The Exact Mixing Time for Trees with Fixed Diameter
• On average hitting time and Kemeny's constant for weighted trees
• Optimal lower bound for the variance of hitting times for simple random walks on graphs