The hitting and cover times of Metropolis walks

DOI10.1016/j.tcs.2010.01.032zbMath1190.68040OpenAlexW1980467795MaRDI 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 CarloMetropolis-Hastings algorithmhitting timecover timeMetropolis walksrandom walk Monte Carlo

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Random walks on graphs (05C81) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (9)

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 ⋮ Geometric bounds for convergence rates of averaging algorithms ⋮ Reversible random walks on dynamic graphs ⋮ Linear Time Average Consensus and Distributed Optimization on Fixed Graphs ⋮ Memory efficient algorithms for cactus graphs and block graphs ⋮ The cover time of deterministic random walks for general transition probabilities ⋮ 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

This page was built for publication: The hitting and cover times of Metropolis walks