Asymptotics of cover times via Gaussian free fields: bounded-degree graphs and general trees
From MaRDI portal
Publication:2447331
DOI10.1214/12-AOP822zbMATH Open1316.60064arXiv1103.4402OpenAlexW3100120030MaRDI QIDQ2447331FDOQ2447331
Authors: Jian Ding 
Publication date: 25 April 2014
Published in: The Annals of Probability (Search for Journal in Brave)
Abstract: In this paper we show that on bounded degree graphs and general trees, the cover time of the simple random walk is asymptotically equal to the product of the number of edges and the square of the expected supremum of the Gaussian free field on the graph, assuming that the maximal hitting time is significantly smaller than the cover time. Previously, this was only proved for regular trees and the 2D lattice. Furthermore, for general trees, we derive exponential concentration for the cover time, which implies that the standard deviation of the cover time is bounded by the geometric mean of the cover time and the maximal hitting time.
Full work available at URL: https://arxiv.org/abs/1103.4402
Recommendations
treessimple random walkcover timesbounded degree graphsGaussian free fieldsisomorphism theoremsprinkling method
Gaussian processes (60G15) Random fields (60G60) Trees (05C05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Sums of independent random variables; random walks (60G50) Random walks on graphs (05C81)
Cites Work
- Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
- Probability. Theory and examples.
- The concentration of measure phenomenon
- The Generic Chaining
- Gaussian Hilbert Spaces
- Cover times for Brownian motion and random walks in two dimensions
- Minima in branching random walks
- Markov Processes, Gaussian Processes, and Local Times
- Tightness of the recentered maximum of the two-dimensional discrete Gaussian free field
- On Unicursal Paths in a Network of Degree 4
- Title not available (Why is that?)
- Is the critical percolation probability local?
- Entropic repulsion and the maximum of the two-dimensional harmonic crystal.
- Maximal displacement of branching brownian motion
- Title not available (Why is that?)
- Regularity of Gaussian processes
- Random walk covering of some special trees
- Threshold limits for cover times
- Gaussian and non-Gaussian random fields associated with Markov processes
- Cover times, blanket times, and majorizing measures
- Tightness for a family of recursion equations
- The electrical resistance of a graph captures its commute and cover times
- Markov processes and random fields
- Recursions and tightness for the maximum of the discrete, two dimensional Gaussian free field
- Sojourn times of diffusion processes
- Random Walks and A Sojourn Density Process of Brownian Motion
- Largest random component of a k-cube
- A Ray-Knight theorem for symmetric Markov processes.
- Percolation on finite graphs and isoperimetric inequalities.
- Uniformity of the uncovered set of random walk and cutoff for lamplighter chains
- A sharp estimate for cover times on binary trees
- Sample path properties of the local times of strongly symmetric Markov processes via Gaussian processes
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Linear cover time is exponentially unlikely
Cited In (26)
- On the cover time of dense graphs
- Exact computation for the cover times of certain classes of trees
- A limit law for the most favorite point of simple random walk on a regular tree
- A polynomial time approximation scheme for computing the supremum of Gaussian processes
- The subleading order of two dimensional cover times
- A scaling limit for the cover time of the binary tree
- Maxima of branching random walks with piecewise constant variance
- A sharp estimate for cover times on binary trees
- Cover times, blanket times, and majorizing measures
- Cut-off for lamplighter chains on tori: dimension interpolation and phase transition
- Title not available (Why is that?)
- Exponential concentration of cover times
- Geometry of the Gibbs measure for the discrete 2D Gaussian free field with scale-dependent variance
- Exceptional points of two-dimensional random walks at multiples of the cover time
- On the cover time of the emerging giant
- Extreme values for two-dimensional discrete Gaussian free field
- Limit law for the cover time of a random walk on a binary tree
- Geometric structures of late points of a two-dimensional simple random walk
- A spectral characterization for concentration of the cover time
- Isomorphism theorems: Markov processes, Gaussian processes and beyond
- Exponents for the number of pairs of \(\alpha \)-favorite points of a simple random walk in \(\mathbb{Z}^2\)
- Chemical distances for percolation of planar Gaussian free fields and critical random walk loop soups
- A Ray-Knight theorem for \(\nabla \phi\) interface models and scaling limits
- Extremes of local times for simple random walks on symmetric trees
- Linear cover time is exponentially unlikely
- Tightness for the cover time of the two dimensional sphere
This page was built for publication: Asymptotics of cover times via Gaussian free fields: bounded-degree graphs and general trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2447331)
