Explosion and linear transit times in infinite trees (Q510268): Difference between revisions

Let i.\,i.\,d. random weights \(w_e\) be assigned to the edges of an infinite rooted tree \(T\). Denote by \(m_n(T)\) the minimum weight of a path from the root to a node of the \(n\)th generation. Then \(T\) is called explosive if \[ \lim\limits_{n\to\infty}m_n(T)\, < \infty, \] and we say that \(T\) exhibits linear growth if \[ \liminf\limits_{n\to\infty}\frac{m_n(T)}{n}\, > 0. \] The authors consider a class of infinite randomly weighted trees related to the Poisson-weighted infinite tree, and determine precisely which trees in this class have linear growth almost surely. Further, let \(f:\, \mathbb{N}_0\to\mathbb{N}\), and \(T_f\) denote the spherically-symmetric tree in which each node \(v\) of generation \(n\) has \(f(n)\) children. Given a distribution \(G\), let \(T_f^G\) denote the randomly weighted tree obtained by giving each edge of \(T_f\) an i.\,i.\,d. weight distributed according to \(G\). For a given distribution \(G\), the non-decreasing function \(f\) is said to be \(G\)-explosive if \(T_f^G\) is explosive almost surely, and said to be \(G\)-small if \(\sum_{n\geq 0}G^{-1}(f(n)^{-1}) <\infty\). In this paper, the authors obtain some results concerning a question of \textit{R. Pemantle} and \textit{Y. Peres} [Ann. Probab. 22, No. 1, 180--194 (1994; Zbl 0806.60098)]: For which \(G\) does the equivalence \[ f \text{ is } G\text{-small } \Leftrightarrow f \text{ is } G\text{-explosive} \] hold in the class of non-decreasing functions \(f\)?