| Extremal Random Walks on Trees (2009) | |||||||||||
Abstract | |||||||||||
| We study random walks on trees, where we iteratively move from one vertex to a randomly chosen adjacent vertex. We study two quantities arising in random walks: the hitting time and the mixing time. The hitting time is the expected number of steps to walk between a chosen pair of vertices. The mixing time is the expected number of steps before the distribution of the current state is proportional to its degree. For a fixed tree size, we prove that the star is the unique minimizing structure and the path is the unique maximizing structure for both quantities. | |||||||||||
Publication details | |||||||||||
| |||||||||||