Tightness for a family of recursion equations

Abstract

In this paper we study the tightness of solutions for a family of recursion equations. These equations arise naturally in the study of random walks on tree-like structures. Examples include the maximal displacement of a branching random walk in one dimension and the cover time of a symmetric simple random walk on regular binary trees. Recursion equations associated with the distribution functions of these quantities have been used to establish weak laws of large numbers. Here, we use these recursion equations to establish the tightness of the corresponding sequences of distribution functions after appropriate centering. We phrase our results in a fairly general context, which we hope will facilitate their application in other settings.

Published in at http://dx.doi.org/10.1214/08-AOP414 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (1)

• A survey of max-type recursive distributional equations

Cited by in corpus (30)

• Convergence in law of the minimum of a branching random walk
• Maximum of the characteristic polynomial of random unitary matrices
• Minima in branching random walks
• Extreme local extrema of two-dimensional discrete Gaussian free field
• Slowdown for time inhomogeneous branching Brownian motion
• Exact asymptotics of the freezing transition of a logarithmically correlated random energy model
• On large deviations for the cover time of two-dimensional torus
• Asymptotics of cover times via Gaussian free fields: Bounded-degree graphs and general trees
• Convergence in law for the branching random walk seen from its tip
• Poisson-Dirichlet branching random walks
• On explosions in heavy-tailed branching random walks
• Branching Brownian motion with selection
• Maxima of branching random walks with piecewise constant variance
• Longest path distance in random circuits
• Branching Random Walks in Time Inhomogeneous Environments
• Right-Most Position of a Last Progeny Modified Branching Random Walk
• The extremal process of critical points of the pure $p$-spin spherical spin glass model
• Cutoff for the East process
• Right-Most Position of a Last Progeny Modified Time Inhomogeneous Branching Random Walk
• Recursions and tightness for the maximum of the discrete, two dimensional Gaussian Free Field
• Continuum Cascade Model: Branching Random Walk for Traveling Wave
• On the Maximal Displacement of a Critical Branching Random Walk
• On cover times for 2D lattices
• Barrier estimates for a critical Galton--Watson process and the cover time of the binary tree
• Cyclic behavior of maxima in a hierarchical summation scheme
• Minimal position and critical martingale convergence in branching random walks, and directed polymers on disordered trees
• Extremal Process of Last Progeny Modified Branching Random Walks
• The Minimal Position of a Stable Branching Random Walk
• Fluctuations of recentered maxima of discrete Gaussian Free Fields on a class of recurrent graphs
• Chernoff bounds for branching random walks