The hitting and cover times of Metropolis walks

DOI10.1016/j.tcs.2010.01.032zbMath1190.68040MaRDI QIDQ964410

Masafumi Yamashita, Kunihiko Sadakane, Hirotaka Ono, Yoshiaki Nonaka

Publication date: 15 April 2010

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2324/26643

zbMATH Keywords

Markov chain Monte Carlo; Metropolis-Hastings algorithm; hitting time; cover time; Metropolis walks; random walk Monte Carlo

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C81: Random walks on graphs

68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)

Related Items

Linear Time Average Consensus and Distributed Optimization on Fixed Graphs, Reversible random walks on dynamic graphs, Memory efficient algorithms for cactus graphs and block graphs, The cover time of deterministic random walks for general transition probabilities, Geometric bounds for convergence rates of averaging algorithms, Random Walks with the Minimum Degree Local Rule Have $O(n^2)$ Cover Time, The Hitting Time of Multiple Random Walks, Stochastic forms of non-negative matrices and Perron-regularity, How to Design a Linear Cover Time Random Walk on a Finite Graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Covering problems for Markov chains
• The hitting and cover times of random walks on finite graphs using local degree information
• On the time taken by random walks on finite groups to visit every state
• Maximum hitting time for random walks on graphs
• A tight upper bound on the cover time for random walks on graphs
• A tight lower bound on the cover time for random walks on graphs
• Equation of State Calculations by Fast Computing Machines
• Monte Carlo sampling methods using Markov chains and their applications