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

DOI10.1007/978-3-642-04944-6_9MaRDI QIDQ3646121zbMATH OpenOpenAlexFDO

Authors Yoshiaki Nonaka, Hirotaka Ono, Kunihiko Sadakane, 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

cover timehitting timerandom walkspeed up a random walktransition probability matrix

Mathematics Subject Classification ID

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

Recommendations

• On the cover time of random walks on graphs
• Linear cover time is exponentially unlikely
• The hitting and cover times of random walks on finite graphs using local degree information
• Expected cover times of random walks on symmetric graphs
• A Technique for Lower Bounding the Cover Time

Cites work

• A tight lower bound on the cover time for random walks on graphs
• A tight upper bound on the cover time for random walks on graphs
• Covering problems for Markov chains
• scientific article; zbMATH DE number 420886 (Why is no real title available?)
• scientific article; zbMATH DE number 2038774 (Why is no real title available?)
• scientific article; zbMATH DE number 840151 (Why is no real title available?)
• scientific article; zbMATH DE number 3255204 (Why is no real title available?)
• Maximum hitting time for random walks on graphs
• Monte Carlo sampling methods using Markov chains and their applications
• On the time taken by random walks on finite groups to visit every state
• The hitting and cover times of Metropolis walks
• The hitting and cover times of random walks on finite graphs using local degree information

Cited in

(3)

• The hitting and cover times of random walks on finite graphs using local degree information
• Linear cover time is exponentially unlikely
• scientific article; zbMATH DE number 2038774 (Why is no real title available?)

This page was built for publication: How to Design a Linear Cover Time Random Walk on a Finite Graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3646121)