Minima in branching random walks. (English) Zbl 1196.60142

The authors investigate a supercritical branching random walk: A Galton-Watson tree where each edge is supplemented with a (iid) weight and where each node is labeled by the sum of weights on the edges from the node to the root. Let \(M(n)\) be the minimum over the labels of all nodes in counting distance \(n\) from the root. The main result of the paper is a characterization of the asymptotic behaviour of the mean \(E(M(n))\) conditioned on that the branching random walk survives. For the case of bounded branching and weight size the results complement results from the literature such that the behaviour of the mean \(E(M(n))\) is completely characterized.


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


[1] Alon, N. and Spencer, J. H. (2000). The Probabilistic Method , 2nd ed. Wiley, New York. With an appendix on the life and work of Paul Erdős. · Zbl 0996.05001
[2] Andersen, E. S. (1953). On the fluctuations of sums of random variables. Math. Scand. 1 263-285. · Zbl 0053.09701
[3] Bachmann, M. (1998). Limit theorems for the minimal position in a branching random walk with independent logconcave displacements. Ph.D. thesis, Purdue Univ. · Zbl 0973.60098
[4] 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
[5] Bahadur, R. R. and Ranga Rao, R. (1960). On deviations of the sample mean. Ann. Math. Statist. 31 1015-1027. · Zbl 0101.12603
[6] Biggins, J. D. (1976). The first- and last-birth problems for a multitype age-dependent branching process. Adv. in Appl. Probab. 8 446-459. · Zbl 0339.60074
[7] Bramson, M. D. (1978). Maximal displacement of branching Brownian motion. Comm. Pure Appl. Math. 31 531-581. · Zbl 0361.60052
[8] Bramson, M. D. (1978). Minimal displacement of branching random walk. Z. Wahrsch. Verw. Gebiete 45 89-108. · Zbl 0373.60089
[9] Bramson, M. D. and Zeitouni, O. (2009). Tightness for a family of recursive equations. Ann. Probab. 37 615-653. · Zbl 1169.60020
[10] Bramson, M. and Zeitouni, O. (2007). Tightness for the minimal displacement of branching random walk. J. Stat. Mech. Theory Exp. 7 P07010 (electronic).
[11] Broutin, N. and Devroye, L. (2006). Large deviations for the weighted height of an extended class of trees. Algorithmica 46 271-297. · Zbl 1106.68027
[12] Broutin, N., Devroye, L. and McLeish, E. (2008). Weighted height of random trees. Acta Inform. 45 237-277. · Zbl 1147.68058
[13] 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
[14] Chernoff, H. (1952). A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Statist. 23 493-507. · Zbl 0048.11804
[15] Chung, K. L. and Erdös, P., (1952). On the application of the Borel-Cantelli lemma. Trans. Amer. Math. Soc. 72 179-186. · Zbl 0046.35203
[16] 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
[17] Dembo, A. and Zeitouni, O. (1993). Large Deviations Techniques and Applications . Jones & Bartlett, Boston, MA. · Zbl 0793.60030
[18] Devroye, L. (1998). Branching processes and their applications in the analysis of tree structures and tree algorithms. In Probabilistic Methods for Algorithmic Discrete Mathematics. Algorithms and Combinatorics 16 249-314. Springer, Berlin. · Zbl 0924.60077
[19] Devroye, L. (1999). Universal limit laws for depths in random trees. SIAM J. Comput. 28 409-432 (electronic). · Zbl 0915.68089
[20] Devroye, L. and Reed, B. (1995). On the variance of the height of random binary search trees. SIAM J. Comput. 24 1157-1162. · Zbl 0845.68027
[21] Drmota, M. (2003). An analytic approach to the height of binary search trees. II. J. ACM 50 333-374 (electronic). · Zbl 1325.68074
[22] Hammersley, J. M. (1974). Postulates for subadditive processes. Ann. Probab. 2 652-680. · Zbl 0303.60044
[23] Harris, T. E. (1963). The Theory of Branching Processes. Die Grundlehren der Mathematischen Wissenschaften 119 . Springer, Berlin. · Zbl 0117.13002
[24] Hu, Y. and Shi, Z. (2009). Minimal position and critical martingale convergence in branching random walks, and directed polymers on disordered trees. Ann. Probab. 37 742-789. · Zbl 1169.60021
[25] Kingman, J. F. C. (1975). The first birth problem for an age-dependent branching process. Ann. Probab. 3 790-801. · Zbl 0325.60079
[26] Lifshits, M. A. (2007). Some limit theorems on binary trees. In preparation.
[27] McDiarmid, C. (1995). Minimal positions in a branching random walk. Ann. Appl. Probab. 5 128-139. · Zbl 0836.60089
[28] 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.