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
- 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 and non-Gaussian random fields associated with Markov processes
- Gaussian Hilbert Spaces
- 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?)
- Is the critical percolation probability local?
- Largest random component of a k-cube
- Linear cover time is exponentially unlikely
- 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
- Markov Processes, Gaussian Processes, and Local Times
- 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 walk covering of some special trees
- Random Walks and A Sojourn Density Process of Brownian Motion
- 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 concentration of measure phenomenon
- The electrical resistance of a graph captures its commute and cover times
- The Generic Chaining
- 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)- Maxima of branching random walks with piecewise constant variance
- Chemical distances for percolation of planar Gaussian free fields and critical random walk loop soups
- Cut-off for lamplighter chains on tori: dimension interpolation and phase transition
- Exponential concentration of cover times
- Extremes of local times for simple random walks on symmetric trees
- Limit law for the cover time of a random walk on a binary tree
- Exceptional points of two-dimensional random walks at multiples of the cover time
- Tightness for the cover time of the two dimensional sphere
- A spectral characterization for concentration of the cover time
- A scaling limit for the cover time of the binary tree
- Geometric structures of late points of a two-dimensional simple random walk
- Exponents for the number of pairs of \(\alpha \)-favorite points of a simple random walk in \(\mathbb{Z}^2\)
- A polynomial time approximation scheme for computing the supremum of Gaussian processes
- Isomorphism theorems: Markov processes, Gaussian processes and beyond
- Exact computation for the cover times of certain classes of trees
- Extreme values for two-dimensional discrete Gaussian free field
- A sharp estimate for cover times on binary trees
- Geometry of the Gibbs measure for the discrete 2D Gaussian free field with scale-dependent variance
- scientific article; zbMATH DE number 6870610 (Why is no real title available?)
- On the cover time of the emerging giant
- The subleading order of two dimensional cover times
- On the cover time of dense graphs
- Cover times, blanket times, and majorizing measures
- A limit law for the most favorite point of simple random walk on a regular tree
- A Ray-Knight theorem for \(\nabla \phi\) interface models and scaling limits
- Linear cover time is exponentially unlikely
- One-arm exponent of critical level-set for metric graph Gaussian free field in high dimensions
- Learning and testing irreducible Markov chains via the k-cover time
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)
