The Exact Mixing Time for Trees with Fixed Diameter

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}_{mix}(G)={\max }_{G\in T_{n,d}}{\max }_{v\in V}H(v,\pi )$ is achieved uniquely by the balanced double broom.