The Best Mixing Time for Random Walks on Trees

We use stopping rules to run a random walk on a tree until its current state is governed by the stationary distribution.ion. We characterize the extremal structures for mixing walks on trees on $n$ vertices that start from the most advantageous vertex. The star is the unique tree that minimizes the best mixing time. For even $n$, the path maximizes the best mixing time. Surprisingly, for odd $n$, a path with a single leaf attached to a central vertex maximizes the best mixing time.