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

random walkGaussian free fieldcover time

Mathematics Subject Classification ID

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

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.

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

• scientific article; zbMATH DE number 5604036 (Why is no real title available?)
• scientific article; zbMATH DE number 3273551 (Why is no real title available?)
• 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.
• 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)

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

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)