Name
Abstract | ||
|---|---|---|
We consider two distinct centers which arise in measuring how quickly a random walk on a tree mixes. Lovász and Winkler [Efficient stopping rules for Markov chains, in Proceedings of the 27th ACM Symposium on the Theory of Computing, 1995, pp. 76-82] point out that stopping rules which “look where they are going” (rather than simply walking a fixed number of steps) can achieve a desired distribution exactly and efficiently. Considering an optimal stopping rule that reflects some aspect of mixing, we can use the expected length of this rule as a mixing measure. On trees, a number of these mixing measures identify particular nodes with central properties. In this context, we study a variety of natural notions of centrality. Each of these criteria identifies the barycenter of the tree as the “average” center and the newly defined focus as the “extremal” center. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1137/070687402 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
random walk,stopping rule,expected length,tree,random walks,acm symposium,markov chain,particular node,barycenter,fixed number,distinct center,natural notion,central property,optimal stopping | Discrete mathematics,Combinatorics,Theory of computing,Random walk,Markov chain,Centrality,Optimal stopping rule,Distribution function,Mathematics,Stopping rule | Journal |
Volume | Issue | ISSN |
23 | 1 | 0895-4801 |
Citations | PageRank | References |
4 | 0.58 | 5 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrew Beveridge | 1 | 55 | 8.21 |