The Best Mixing Time for Random Walks on Trees

We characterize the extremal structures for mixing walks on trees that start from the most advantageous vertex. Let \(G=(V,E)\) be a tree with stationary distribution \(\pi \). For a vertex \(v \in V\), let \(H(v,\pi )\) denote the expected length of an optimal stopping rule from v to \(\pi \). The best mixing time for G is \(\min _{v \in V} H(v,\pi )\). We show that among all trees with \(|V|=n\), the best mixing time is minimized uniquely by the star. For even n, the best mixing time is maximized by the uniquely path. Surprising, for odd n, the best mixing time is maximized uniquely by a path of length \(n-1\) with a single leaf adjacent to one central vertex.