The hitting and cover times of Metropolis walks
From MaRDI portal
Publication:964410
DOI10.1016/j.tcs.2010.01.032zbMath1190.68040MaRDI QIDQ964410
Hirotaka Ono, Kunihiko Sadakane, Masafumi Yamashita, 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
Markov chain Monte Carlo; Metropolis-Hastings algorithm; hitting time; cover time; Metropolis walks; random walk Monte Carlo
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
Memory efficient algorithms for cactus graphs and block graphs, 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