×

Centers for random walks on trees. (English) Zbl 1189.60134

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.

MSC:

60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
60G40 Stopping times; optimal stopping problems; gambling theory
05C05 Trees

Citations:

Zbl 0921.60062
PDFBibTeX XMLCite
Full Text: DOI