Exact mixing times for random walks on trees

DOI10.1007/S00373-012-1175-XzbMATH Open1268.60097OpenAlexW2031369582MaRDI QIDQ354448FDOQ354448

Authors: Andrew Beveridge, Meng Wang 

Publication date: 19 July 2013

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-012-1175-x

Recommendations

• Mixing time for a random walk on rooted trees
• The best mixing time for random walks on trees
• On hitting times of random walks on trees
• On the moments of hitting times for random walks on trees
• On the distribution of random walk hitting times in random trees
• Commute times of random walks on trees
• Extremal cover times for random walks on trees
• On the speed of random walks on random trees
• Random walks on trees and matchings

zbMATH Keywords

treeMarkov chainrandom walkstopping rulemixing time

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Sums of independent random variables; random walks (60G50) Random walks on graphs (05C81)

Cites Work

• Maximum hitting time for random walks on graphs
• A tight lower bound on the cover time for random walks on graphs
• Title not available (Why is that?)
• Finite Markov Chains and Algorithmic Applications
• Mixing times for uniformly ergodic Markov chains
• Collisions Among Random Walks on a Graph
• Occupation measures for Markov chains
• Reversal of Markov Chains and the Forget Time
• Title not available (Why is that?)
• Extremal cover times for random walks on trees
• Exit frequency matrices for finite Markov chains
• Centers for random walks on trees

Cited In (13)

• Commute times of random walks on trees
• Mixing time for a random walk on rooted trees
• COMMUTE TIMES AND THE EFFECTIVE RESISTANCES OF RANDOM TREES
• A faster exact-counting protocol for anonymous dynamic networks
• Local times of subdiffusive biased walks on trees
• The access time of random walks on trees with given partition
• Pseudo-mixing Time of Random Walks
• Mixing times for the rook's walk via path coupling
• Exact and approximate mean first passage times on trees and other necklace structures: a local equilibrium approach
• The best mixing time for random walks on trees
• A hitting time formula for the discrete Green's function
• Extremal first passage times for trees
• Centers for random walks on trees

This page was built for publication: Exact mixing times for random walks on trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q354448)