×

The best mixing time for random walks on trees. (English) Zbl 1353.05114

Summary: We characterize the extremal structures for mixing walks on trees that start from the most advantageous vertex. Let \(G=(V,E)\) be a tree with stationary distribution \(\pi\). For a vertex \(v \in V\), let \(H(v,\pi)\) denote the expected length of an optimal stopping rule from \(v\) to \(\pi \). The best mixing time for \(G\) is \(\min _{v \in V} H(v,\pi)\). We show that among all trees with \(|V|=n\), the best mixing time is minimized uniquely by the star. For even \(n\), the best mixing time is maximized by the uniquely path. Surprising, for odd \(n\), the best mixing time is maximized uniquely by a path of length \(n-1\) with a single leaf adjacent to one central vertex.

MSC:

05C81 Random walks on graphs
05C05 Trees
05C35 Extremal problems in graph theory
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aldous, D., Fill, J.: Reversible Markov chains and random walks on graphs. http://www.stat.berkeley.edu/ aldous/RWG/book.html. Accessed Jan 2014 · Zbl 0826.60057
[2] Aldous, D., Lovász, L., Winkler, P.: Mixing times for uniformly ergodic Markov chains. Stoch. Process. Appl. 71, 165-185 (1997) · Zbl 0941.60080 · doi:10.1016/S0304-4149(97)00037-9
[3] Beveridge, A.: Centers for random walks on trees. SIAM J. Discrete Math. 23(1), 300-318 (2009) · Zbl 1189.60134 · doi:10.1137/070687402
[4] Beveridge, A., Wang, M.: Mixing times for random walks on trees. Graph Combin. 29(4), 757-772 (2013) · Zbl 1268.60097 · doi:10.1007/s00373-012-1175-x
[5] Brightwell, G., Winkler, P.: Maximum hitting time for random walks on graphs. In: Proceedings of 22nd ACM Symposium on Theory of Computing, pp. 369-378 (1990) · Zbl 0744.05044
[6] Dumitriu, I., Tetali, P., Winkler, P.: On playing golf with two balls. SIAM J. Discrete Math. 16(4), 604-615 (2003) · Zbl 1032.60065 · doi:10.1137/S0895480102408341
[7] Feige, U.: A tight lower bound on the cover time for random walks on graphs. Random Struct. Algorithms 6(4), 433-438 (1995) · Zbl 0832.60016 · doi:10.1002/rsa.3240060406
[8] Georgakopoulos, A., Wagner, S.: Hitting times, cover cost, and the Wiener index of a tree. Preprint · Zbl 1359.05113
[9] Lovász, L., Winkler, P.: Efficient stopping rules for Markov chains. In: Proceedings of 27th ACM Symposium on Theory Computing, pp. 76-82 (1995) · Zbl 0921.60062
[10] Lovász, L.; Winkler, P.; Rowlinson, P. (ed.), Mixing of random walks and other diffusions on a graph, No. 218, 119-154 (1995), Cambridge · Zbl 0826.60057
[11] Lovász, L., Winkler, P.: Reversal of Markov chains and the forget time. Combin. Probab. Comput. 7, 189-204 (1998) · Zbl 0924.60050 · doi:10.1017/S0963548397003349
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.