A sharp estimate for cover times on binary trees

DOI10.1016/J.SPA.2012.03.008zbMATH Open1255.05179arXiv1104.0434OpenAlexW2001123643MaRDI QIDQ424523FDOQ424523

Authors: Jian Ding, Ofer Zeitouni 

Publication date: 1 June 2012

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

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.

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

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

zbMATH Keywords

random walkGaussian free fieldcover time

Mathematics Subject Classification ID

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

Cites Work

• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Cover times for Brownian motion and random walks in two dimensions
• Minima in branching random walks
• Convergence in law of the minimum of a branching random walk
• Tightness of the recentered maximum of the two-dimensional discrete Gaussian free field
• Entropic repulsion and the maximum of the two-dimensional harmonic crystal.
• Maximal displacement of branching brownian motion
• Random walk covering of some special trees
• Tightness for a family of recursion equations
• Asymptotics of cover times via Gaussian free fields: bounded-degree graphs and general trees
• Cover times, blanket times, and majorizing measures

Cited In (15)

• Barrier estimates for a critical Galton-Watson process and the cover time of the binary tree
• Exact computation for the cover times of certain classes of trees
• The subleading order of two dimensional cover times
• A scaling limit for the cover time of the binary tree
• Maxima of branching random walks with piecewise constant variance
• On the cover time of \(\lambda\)-biased walk on supercritical Galton-Watson trees
• Title not available (Why is that?)
• Geometry of the Gibbs measure for the discrete 2D Gaussian free field with scale-dependent variance
• Asymptotics of cover times via Gaussian free fields: bounded-degree graphs and general trees
• Limit law for the cover time of a random walk on a binary tree
• A spectral characterization for concentration of the cover time
• Isomorphism theorems: Markov processes, Gaussian processes and beyond
• Title not available (Why is that?)
• Extremes of local times for simple random walks on symmetric trees
• Tightness for the cover time of the two dimensional sphere

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)