Cover times and generic chaining

DOI10.1239/JAP/1395771427zbMATH Open1291.60144arXiv1207.1024OpenAlexW2592738321MaRDI QIDQ5416554FDOQ5416554

Authors: Joseph Lehec 

Publication date: 14 May 2014

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

Abstract: A recent result of Ding, Lee and Peres expresses the cover time of the random walk on a graph in terms of generic chaining for the commute distance. Their proof is very involved and the purpose of this article is to present a simpler approach to this problem based on elementary hitting times estimates and chaining arguments. Unfortunately we fail to recover their full result, but not by much.

Full work available at URL: https://arxiv.org/abs/1207.1024

Recommendations

• Lower bounds for covering times for reversible Markov chains and random walks on graphs
• On the cover time of random walks on graphs
• Cover times, blanket times, and majorizing measures
• Cover times, blanket times, and majorizing measures
• Threshold limits for cover times

zbMATH Keywords

Markov chainhitting timecover timegeneric chaining

Mathematics Subject Classification ID

Gaussian processes (60G15) Discrete-time Markov processes on general state spaces (60J05)

Cites Work

• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• The Generic Chaining
• The evolution of the cover time
• Cover times, blanket times, and majorizing measures
• Covering problems for Brownian motion on spheres

Cited In (4)

• Exponential concentration of cover times
• Limit law for the cover time of a random walk on a binary tree
• Bounds on the cover time
• Cover times, blanket times, and majorizing measures

This page was built for publication: Cover times and generic chaining

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