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 .
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aldous, D., Fill, J.: Reversible Markov Chains and Random Walks on Graphs. http://www.stat.berkeley.edu/~aldous/RWG/book.html. Accessed 9 Aug 2010
Aldous D., Lovász L., Winkler P.: Mixing times for uniformly ergodic Markov chains. Stoch. Process. Appl. 71, 165–185 (1997)
Beveridge A.: Centers for random walks on trees. SIAM J. Discrete Math. 23(1), 300–318 (2009)
Beveridge A., Lovász L.: Exit frequency matrices for finite Markov chains. Combin. Probab. Comput. 19, 541–560 (2010)
Brightwell G., Winkler P.: Maximum hitting time for random walks on graphs. Random Struct. Algorithms 1(3), 263–276 (1990)
Brightwell G., Winkler P.: Extremal cover time for random walks on trees. J. Graph Theory 14(5), 547–554 (1990)
Coppersmith D., Tetali P., Winkler P.: Collisions among random walks on a graph. SIAM J. Discrete Math. 6(3), 363–374 (1993)
Feige U.: A tight lower bound on the cover time for random walks on graphs. Random Struct. Algorithms 6(4), 433–438 (1995)
Häggström O.: Finite Markov Chains and Algorithmic Applications. Cambridge University Press, Cambridge (2002)
Lovász, L.: Random walks on graphs: a survey. In: Miklós, D., Sós, V.T., Szőnyi, T. (eds.) Combinatorics, Paul Erdős is Eighty, vol. II, pp. 355–397. J. Bolyai Math. Soc., Budapest (1996)
Lovász, L., Winkler, P.: Efficient stopping rules for Markov chains. In: Proc. 27th ACM Symp. Theory Comput., pp. 76–82 (1995)
Lovász P., Winkler P.: Reversal of Markov chains and the forget time. Combin. Probab. Comput. 7, 189–204 (1998)
Pitman J.W.: Occupation measures for Markov chains. Adv. Appl. Probab. 9, 69–86 (1977)
Yaron, O.: Random walks on trees. Technical report, Hebrew University, Jerusalem (1988)
Author information
Authors and Affiliations
Corresponding author
Additional information
A. Beveridge supported in part by NSA Young Investigator Grant H98230-08-1-0064.
Rights and permissions
About this article
Cite this article
Beveridge, A., Wang, M. Exact Mixing Times for Random Walks on Trees. Graphs and Combinatorics 29, 757–772 (2013). https://doi.org/10.1007/s00373-012-1175-x
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-012-1175-x