Cover times, blanket times, and majorizing measures

DOI10.4007/annals.2012.175.3.8zbMath1250.05098arXiv1004.4371MaRDI QIDQ431644

Yuval Peres, Jian Ding, James R. Lee

Publication date: 29 June 2012

Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)

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

zbMATH Keywords

random walks; Gaussian free field; effective resistance; majorizing measures; cover times; commute times; Dynkin isomorphism

Mathematics Subject Classification ID

60G15: Gaussian processes

05C85: Graph algorithms (graph-theoretic aspects)

60J55: Local time and additive functionals

05C81: Random walks on graphs

Related Items

Unnamed Item, Geometry of the Gibbs measure for the discrete 2D Gaussian free field with scale-dependent variance, Out-of-equilibrium random walks, On the Cover Time of Dense Graphs, Cover Times and Generic Chaining, New Bounds for Edge-Cover by Random Walk, Sandwich theorem of cover times, Extreme values for two-dimensional discrete Gaussian free field, Effective resistances for supercritical percolation clusters in boxes, Inverting Ray-Knight identity, On uniform closeness of local times of Markov chains and i.i.d. sequences, Maxima of branching random walks with piecewise constant variance, Exponential concentration of cover times, Extremes of local times for simple random walks on symmetric trees, Mixing time bounds via bottleneck sequences, Modulus metrics on networks, The geometry of random walk isomorphism theorems, Limit law for the cover time of a random walk on a binary tree, Second-order term of cover time for planar simple random walk, Tightness for the cover time of the two dimensional sphere, Thick points of random walk and the Gaussian free field, Divide and color representations for threshold Gaussian and stable vectors, A spectral characterization for concentration of the cover time, A comparison principle for random walk on dynamical percolation, On the cover time of \(\lambda\)-biased walk on supercritical Galton-Watson trees, A scaling limit for the cover time of the binary tree, Cover times for sequences of reversible Markov chains on random graphs, 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, Asymptotics of cover times via Gaussian free fields: bounded-degree graphs and general trees, Extreme local extrema of two-dimensional discrete Gaussian free field, Isomorphism Theorems: Markov Processes, Gaussian Processes and Beyond, The Cover Time of Cartesian Product Graphs, Extrema of the Two-Dimensional Discrete Gaussian Free Field

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Regularity of Gaussian processes
• Covering problems for Markov chains
• Random walks and the effective resistance of networks
• Gaussian and non-Gaussian random fields associated with Markov processes
• Random walk covering of some special trees
• Matrix multiplication via arithmetic progressions
• Markov chains with almost exponential hitting times
• Probability approximations via the Poisson clumping heuristic
• Sample path properties of the local times of strongly symmetric Markov processes via Gaussian processes
• Random walks, capacity and percolation on trees
• The electrical resistance of a graph captures its commute and cover times
• On the cover time of planar graphs
• Cover times for Brownian motion and random walks in two dimensions
• Bounds on the cover time
• On the cover time of random walks on graphs
• Lower bounds for covering times for reversible Markov chains and random walks on graphs
• A Ray-Knight theorem for symmetric Markov processes.
• Majorizing measures without measures
• The sizes of compact subsets of Hilbert space and continuity of Gaussian processes
• Régularité de processus gaussiens
• Majorizing measures: The generic chaining
• Sojourn times of diffusion processes
• Threshold limits for cover times
• Probability on Trees and Networks
• Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
• The Evolution of the Cover Time
• The cover time of the giant component of a random graph
• A Technique for Lower Bounding the Cover Time
• Chernoff's theorem in the branching random walk
• A tight upper bound on the cover time for random walks on graphs
• Gaussian Hilbert Spaces
• The Generic Chaining
• A tight lower bound on the cover time for random walks on graphs
• Markov Processes, Gaussian Processes, and Local Times
• Random Walks and A Sojourn Density Process of Brownian Motion