Barrier estimates for a critical Galton--Watson process and the cover time of the binary tree

2017/02/10 by David Belius, Belius, David, Jay Rosen +3
Economics, Econometrics and Finance · Mathematics · #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Stochastic processes and financial applications #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.1702.03189

openalex publication_date 2017/02/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For the critical Galton--Watson process with geometric offspring distributions we provide sharp barrier estimates for barriers which are (small) perturbations of linear barriers. These are useful in analyzing the cover time of finite graphs in the critical regime by random walk, and the Brownian cover times of compact two dimensional manifolds. As an application of the barrier estimates, we prove that if C_L denotes the cover time of the binary tree of depth L by simple walk, then √C_L/2^L+1 -√(2log 2) L+log L/√(2log 2) is tight. The latter improves results of Aldous (1991), Bramson and Zeitouni (2009) and Ding and Zeitouni (2012). In a subsequent article we use these barrier estimates to prove tightness of the Brownian cover time for the two-dimensional sphere.

Citations

• Tightness for a family of recursion equations

Related

• The Contact Process on Random Graphs and Galton-Watson Trees
• Biased random walks on a Galton-Watson tree with leaves
• On the cover time of Brownian motion on the Brownian continuum random tree
• On the cover time of λ-biased walk on supercritical Galton-Watson trees
• Random walks on decorated Galton-Watson trees