Beveridge, Andrew Centers for random walks on trees. (English) Zbl 1189.60134 SIAM J. Discrete Math. 23, No. 1, 300-318 (2009). Summary: We consider two distinct centers which arise in measuring how quickly a random walk on a tree mixes. L. Lovász and P. Winkler [Efficient stopping rules for Markov chains (extended abstract). Proceedings of the 27th annual ACM symposium on the theory of computing (STOC). Las Vegas, NV, USA, 1995. New York: ACM, 76–82 (1995; Zbl 0921.60062)] 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. Cited in 5 Documents MSC: 60J10 Markov chains (discrete-time Markov processes on discrete state spaces) 60G40 Stopping times; optimal stopping problems; gambling theory 05C05 Trees Keywords:Markov chain; random walk; stopping rule; tree; barycenter Citations:Zbl 0921.60062 PDFBibTeX XMLCite \textit{A. Beveridge}, SIAM J. Discrete Math. 23, No. 1, 300--318 (2009; Zbl 1189.60134) Full Text: DOI