Exact Mixing Times for Random Walks on Trees
Published in Graphs and Combinatorics, 2013
A. Beveridge and M. Wang, Exact Mixing Times for Random Walks on Trees, Graphs and Combinatorics, Vol. 29, No. 4, (2013), pp. 757-772.
Preprint link: https://www.macalester.edu/~abeverid/papers/tree-mixing.pdf
We characterize the extremal structures for random walks on trees. Using exact stopping rules, we follow random walks from/to singletons to/from the stationary distribution, and the reverse. These quantities are minimized by the star and maximized by the path.