Exact Mixing Times for Random Walks on Trees |
| |
Authors: | Andrew Beveridge Meng Wang |
| |
Institution: | 1. Department of Mathematics, Statistics and Computer Science, Macalester College, Saint Paul, MN, 55105, USA
|
| |
Abstract: | We characterize the extremal structures for certain random walks on trees. Let G = (V, E) be a tree with stationary distribution π. For a vertex ${i \in V}$ , let H(π, i) and H(i, π) denote the expected lengths of optimal stopping rules from π to i and from i to π, respectively. We show that among all trees with |V| = n, the quantities ${{\rm min}_{i \in V} H(\pi, i), {\rm max}_{i \in V} H(\pi, i), {\rm max}_{i \in V} H(i, \pi)}$ and ${\sum_{i \in V} \pi_i H(i, \pi)}$ are all minimized uniquely by the star S n = K 1,n?1 and maximized uniquely by the path P n . |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|