Tightness for a family of recursion equations. (English) Zbl 1169.60020

Authors’ abstract: 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.


60J80 Branching processes (Galton-Watson, birth-and-death, etc.)
60G50 Sums of independent random variables; random walks
39B12 Iteration theory, iterative and composite equations
Full Text: DOI arXiv


[1] Abramowitz, M. and Stegun, I. A. (1965). Handbook of Mathematical Functions . Dover. · Zbl 0171.38503
[2] Addario-Berry, D. (2007). Ballot theorems and the height of trees. Ph.D. thesis, McGill Univ.
[3] Aldous, D. (1989). Probability Approximations via the Poisson Clumping Heuristic. Applied Mathematical Sciences 77 . Springer, New York. · Zbl 0679.60013
[4] Aldous, D. J. (1991). Random walk covering of some special trees. J. Math. Anal. Appl. 157 271-283. · Zbl 0733.60092
[5] Aldous, D. J. and Bandyopadhyay, A. (2005). A survey of max-type recursive distributional equations. Ann. Appl. Probab. 15 1047-1110. · Zbl 1105.60012
[6] Athreya, K. B. and Ney, P. E. (1972). Branching Processes. Die Grundlehren der mathematischen Wissenschaften 196 . Springer, New York. · Zbl 0259.60002
[7] Bachmann, M. (2000). Limit theorems for the minimal position in a branching random walk with independent logconcave displacements. Adv. in Appl. Probab. 32 159-176. · Zbl 0973.60098
[8] Biggins, J. D. (1990). The central limit theorem for the supercritical branching random walk, and related results. Stochastic Process. Appl. 34 255-274. · Zbl 0703.60083
[9] Bramson, M. D. (1978). Maximal displacement of branching Brownian motion. Comm. Pure Appl. Math. 31 531-581. · Zbl 0361.60052
[10] Bramson, M. (1983). Convergence of solutions of the Kolmogorov equation to travelling waves. Mem. Amer. Math. Soc. 44 iv+190. · Zbl 0517.60083
[11] Bramson, M. and Zeitouni, O. (2007). Tightness for the minimal displacement of branching random walk. J. Stat. Mech. Theory Exp. 7 P07010 (electronic).
[12] Chauvin, B. and Drmota, M. (2006). The random multisection problem, travelling waves and the distribution of the height of m -ary search trees. Algorithmica 46 299-327. · Zbl 1117.68095
[13] Dekking, F. M. and Host, B. (1991). Limit distributions for minimal displacement of branching random walks. Probab. Theory Related Fields 90 403-426. · Zbl 0734.60074
[14] Dembo, A., Peres, Y., Rosen, J. and Zeitouni, O. (2004). Cover times for Brownian motion and random walks in two dimensions. Ann. of Math. ( 2 ) 160 433-464. · Zbl 1068.60018
[15] Drmota, M. (2003). An analytic approach to the height of binary search trees. II. J. ACM 50 333-374 (electronic). · Zbl 1325.68074
[16] Feller, W. (1957). An Introduction to Probability Theory and Its Applications , Vol. I , 2nd ed. Wiley, New York. · Zbl 0077.12201
[17] Fisher, R. A. (1937). The advance of advantageous genes. Ann. of Eugenics 7 355-369. · JFM 63.1111.04
[18] Hammersley, J. M. (1974). Postulates for subadditive processes. Ann. Probab. 2 652-680. · Zbl 0303.60044
[19] Harris, T. E. (1963). The Theory of Branching Processes. Die Grundlehren der Mathematischen Wissenschaften 119 . Springer, Berlin. · Zbl 0117.13002
[20] Kaplan, N. and Asmussen, S. (1976). Branching random walks. II. Stochastic Process. Appl. 4 15-31. · Zbl 0322.60065
[21] Kingman, J. F. C. (1975). The first birth problem for an age-dependent branching process. Ann. Probab. 3 790-801. · Zbl 0325.60079
[22] Kingman, J. F. C. (1976). Subadditive processes. In École D’Été de Probabilités de Saint-Flour , V-1975. Lecture Notes in Mathematics 539 167-223. Springer, Berlin. · Zbl 0367.60030
[23] Kolmogorov, A., Petrovsky, I. and Piscounov, N. (1937). Étude de l’équation de la diffusion avec croissance de la quantité de matière et son application à un problème biologique. Moscou Universitet Bull. Math. 1 1-25. · Zbl 0018.32106
[24] Liggett, T. M. (1985). An improved subadditive ergodic theorem. Ann. Probab. 13 1279-1285. · Zbl 0579.60023
[25] Loève, M. (1977). Probability Theory. I , 4th ed. Graduate Texts in Mathematics 45 . Springer, New York.
[26] Lui, R. (1982). A nonlinear integral operator arising from a model in population genetics. I. Monotone initial data. SIAM J. Math. Anal. 13 913-937. · Zbl 0508.45006
[27] McDiarmid, C. (1995). Minimal positions in a branching random walk. Ann. Appl. Probab. 5 128-139. · Zbl 0836.60089
[28] McKean, H. P. (1975). Application of Brownian motion to the equation of Kolmogorov-Petrovskii-Piskunov. Comm. Pure Appl. Math. 28 323-331. · Zbl 0316.35053
[29] Reed, B. (2003). The height of a random binary search tree. J. ACM 50 306-332 (electronic). · Zbl 1325.68076
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.