Exact mixing times for random walks on trees

DOI10.1007/S00373-012-1175-XMaRDI QIDQ354448zbMATHOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 1263183 (Why is no real title available?)
• scientific article; zbMATH DE number 878897 (Why is no real title available?)
• A tight lower bound on the cover time for random walks on graphs
• Centers for random walks on trees
• Collisions Among Random Walks on a Graph
• Exit frequency matrices for finite Markov chains
• Extremal cover times for random walks on trees
• Finite Markov Chains and Algorithmic Applications
• Maximum hitting time for random walks on graphs
• Mixing times for uniformly ergodic Markov chains
• Occupation measures for Markov chains
• Reversal of Markov Chains and the Forget Time

Cited in

(13)

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