The Best Mixing Time for Random Walks on Trees

Abstract

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 \emph{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.

25 pages, 7 figures, 3 tables