A sharp estimate for cover times on binary trees

DOI10.1016/J.SPA.2012.03.008MaRDI QIDQ424523zbMATH OpenOpenAlexFDO

Authors Jian Ding, Ofer Zeitouni

Publication date 1 June 2012

Published in Stochastic Processes and their Applications (Search for Journal in Brave)

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

zbMATH Keywords

cover timeGaussian free fieldrandom walk

Mathematics Subject Classification ID

Random walks on graphs (05C81) Combinatorial probability (60C05)

Abstract: We compute the second order correction for the cover time of the binary tree of depth $n$ by (continuous-time) random walk, and show that with probability approaching 1 as $n$ increases, $sqrta{u}_{mathrmcov}=sqrt|E|[sqrt2log2cdotn-logn/sqrt2log2+O((loglogn{)}^8]$, thus showing that the second order correction differs from the corresponding one for the maximum of the Gaussian free field on the tree.

Review text

The paper deals with a cover time of a random walk on a graph. The cover time of a random walk on a graph, which is the time it takes the walk to visit every vertex in the graph is a basic parameter. The authors compute the second order correction for cover time of the binary tre of depth \(n\) (continuous time) random walk and show that the second order correction differs from corresponding one for the maximum of the Gaussian free field on the tree.

Recommendations

• Limit law for the cover time of a random walk on a binary tree
• A scaling limit for the cover time of the binary tree
• On the cover time of random walks on graphs
• Random walk covering of some special trees
• Barrier estimates for a critical Galton-Watson process and the cover time of the binary tree

Cites work

• Asymptotics of cover times via Gaussian free fields: bounded-degree graphs and general trees
• Convergence in law of the minimum of a branching random walk
• 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.
• scientific article; zbMATH DE number 5604036 (Why is no real title available?)
• scientific article; zbMATH DE number 3273551 (Why is no real title available?)
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Maximal displacement of branching brownian motion
• Minima in branching random walks
• Random walk covering of some special trees
• Tightness for a family of recursion equations
• Tightness of the recentered maximum of the two-dimensional discrete Gaussian free field

Cited in

(15)

• Maxima of branching random walks with piecewise constant variance
• Barrier estimates for a critical Galton-Watson process and the cover time of the binary tree
• 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
• Tightness for the cover time of the two dimensional sphere
• A spectral characterization for concentration of the cover time
• On the cover time of -biased walk on supercritical Galton-Watson trees
• A scaling limit for the cover time of the binary tree
• Asymptotics of cover times via Gaussian free fields: bounded-degree graphs and general trees
• Isomorphism theorems: Markov processes, Gaussian processes and beyond
• Exact computation for the cover times of certain classes of 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?)
• The subleading order of two dimensional cover times
• scientific article; zbMATH DE number 6292624 (Why is no real title available?)

This page was built for publication: A sharp estimate for cover times on binary trees

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