Asymptotics of cover times via Gaussian free fields: bounded-degree graphs and general trees
From MaRDI portal
Publication:2447331
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 1639849 (Why is no real title available?)
- scientific article; zbMATH DE number 3883338 (Why is no real title available?)
- scientific article; zbMATH DE number 816116 (Why is no real title available?)
- scientific article; zbMATH DE number 878897 (Why is no real title available?)
- scientific article; zbMATH DE number 3431598 (Why is no real title available?)
- scientific article; zbMATH DE number 3068971 (Why is no real title available?)
- A Ray-Knight theorem for symmetric Markov processes.
- A sharp estimate for cover times on binary trees
- Cover times for Brownian motion and random walks in two dimensions
- Cover times, blanket times, and majorizing measures
- Entropic repulsion and the maximum of the two-dimensional harmonic crystal.
- Gaussian Hilbert Spaces
- Gaussian and non-Gaussian random fields associated with Markov processes
- Is the critical percolation probability local?
- Largest random component of a k-cube
- Linear cover time is exponentially unlikely
- Markov Processes, Gaussian Processes, and Local Times
- Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
- Markov processes and random fields
- Maximal displacement of branching brownian motion
- Minima in branching random walks
- On Unicursal Paths in a Network of Degree 4
- Percolation on finite graphs and isoperimetric inequalities.
- Probability. Theory and examples.
- Random Walks and A Sojourn Density Process of Brownian Motion
- Random walk covering of some special trees
- Recursions and tightness for the maximum of the discrete, two dimensional Gaussian free field
- Regularity of Gaussian processes
- Sample path properties of the local times of strongly symmetric Markov processes via Gaussian processes
- Sojourn times of diffusion processes
- The Generic Chaining
- The concentration of measure phenomenon
- The electrical resistance of a graph captures its commute and cover times
- Threshold limits for cover times
- Tightness for a family of recursion equations
- Tightness of the recentered maximum of the two-dimensional discrete Gaussian free field
- Uniformity of the uncovered set of random walk and cutoff for lamplighter chains
Cited in
(28)- Tightness for the cover time of the two dimensional sphere
- One-arm exponent of critical level-set for metric graph Gaussian free field in high dimensions
- On the cover time of dense graphs
- Exact computation for the cover times of certain classes of trees
- The subleading order of two dimensional cover times
- A polynomial time approximation scheme for computing the supremum of Gaussian processes
- A limit law for the most favorite point of simple random walk on a regular tree
- 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
- Cut-off for lamplighter chains on tori: dimension interpolation and phase transition
- Cover times, blanket times, and majorizing measures
- Exponential concentration of cover times
- scientific article; zbMATH DE number 6870610 (Why is no real title available?)
- Exceptional points of two-dimensional random walks at multiples of the cover time
- Geometry of the Gibbs measure for the discrete 2D Gaussian free field with scale-dependent variance
- Learning and testing irreducible Markov chains via the k-cover time
- Extreme values for two-dimensional discrete Gaussian free field
- On the cover time of the emerging giant
- 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
- Extremes of local times for simple random walks on symmetric trees
- A Ray-Knight theorem for \(\nabla \phi\) interface models and scaling limits
- Linear cover time is exponentially unlikely
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)
