How to Design a Linear Cover Time Random Walk on a Finite Graph

DOI10.1007/978-3-642-04944-6_9zbMath1260.05148OpenAlexW110816161MaRDI QIDQ3646121

Kunihiko Sadakane, Hirotaka Ono, Yoshiaki Nonaka, Masafumi Yamashita

Publication date: 19 November 2009

Published in: Stochastic Algorithms: Foundations and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-04944-6_9

zbMATH Keywords

transition probability matrixrandom walkhitting timecover timespeed up a random walk

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Combinatorial probability (60C05) Random walks on graphs (05C81)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Covering problems for Markov chains
• The hitting and cover times of Metropolis walks
• 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
• Monte Carlo sampling methods using Markov chains and their applications