An introduction to covering problems for random walks on graphs

DOI10.1007/BF01048271zbMath0684.60054MaRDI QIDQ1825524

David J. Aldous

Publication date: 1989

Published in: Journal of Theoretical Probability (Search for Journal in Brave)

zbMATH Keywords

random walks on graphscovering problems

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50)

Related Items

Maximum hitting time for random walks on graphs ⋮ Analytical results for the distribution of cover times of random walks on random regular graphs ⋮ Covering with blocks in the non-symmetric case ⋮ Threshold limits for cover times ⋮ Potential Theory on Distance-Regular Graphs ⋮ Cover times for words in symmetric and nonsymmetric cases: A comparison ⋮ Rates of convergence for lamplighter processes ⋮ A tight lower bound on the cover time for random walks on graphs ⋮ Extremal points of high-dimensional random walks and mixing times of a Brownian motion on the sphere ⋮ Stationary distribution and cover time of sparse directed configuration models ⋮ The Evolution of the Cover Time ⋮ Hitting times for random walks on vertex-transitive graphs ⋮ Expected cover times of random walks on symmetric graphs ⋮ Combinatorial approach to the interpolation method and scaling limits in sparse random graphs ⋮ On a Result of Aleliunas et al. Concerning Random Walks on Graphs ⋮ Speed and concentration of the covering time for structured coupon collectors ⋮ Cover time of a random graph with a degree sequence II: Allowing vertices of degree two ⋮ Random walks and hyperplane arrangements ⋮ Random walk covering of some special trees

Cites Work

• Unnamed Item
• Covering problems for Markov chains
• Random shuffles and group representations
• Random walks on graphs with a strong isoperimetric property
• Random walks on graphs
• On the time taken by random walks on finite groups to visit every state
• Random walks on random trees