Name
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 . |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/s00373-012-1175-x | Graphs and Combinatorics |
Keywords | Field | DocType |
mixing time,random walk,tree,stopping rule,markov chain | Discrete mathematics,Combinatorics,Vertex (geometry),Optimal stopping,Random walk,Markov chain,Stationary distribution,Mathematics,Stopping rule | Journal |
Volume | Issue | ISSN |
29 | 4 | 1435-5914 |
Citations | PageRank | References |
7 | 0.53 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrew Beveridge | 1 | 55 | 8.21 |
| Meng Wang | 2 | 28 | 5.60 |