Andrew Beveridge

Andrew Beveridge

Math Professor

The Exact Mixing Time for Trees with Fixed Diameter

Published in TBD, 2024

A. Beveridge, K. Heysse, R. O'Higgins, L. Vescovo, https://arxiv.org/abs/2411.06247.

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

We characterize the extremal structure for the exact mixing time for random walks on trees $T_{n,d}$ of order $n$ with diameter $d$. Given a graph $G=(V,E)$, let $H(v,\pi)$ denote the expected length of an optimal stopping rule from vertex $v$ to the stationary distributon $\pi$. We show that the quantity $\max_{G \in T_{n,d}} T_{\mathrm{mix}}(G) = \max_{G \in T_{n,d}} \max_{v \in V} H(v, \pi)$ is achieved uniquely by the balanced double broom.