Explosion and linear transit times in infinite trees (Q510268): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(9 intermediate revisions by 7 users not shown) | |||
Property / author | |||
Property / author: Q175421 / rank | |||
Property / author | |||
Property / author: Luc P. Devroye / rank | |||
Normal rank | |||
Property / review text | |||
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\)? | |||
Property / review text: 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\)? / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 60J80 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 60K35 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 60C05 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 60G55 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6685604 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
infinite rooted tree | |||
Property / zbMATH Keywords: infinite rooted tree / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
random Galton-Watson tree | |||
Property / zbMATH Keywords: random Galton-Watson tree / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
branching random walk | |||
Property / zbMATH Keywords: branching random walk / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
spherically symmetric tree | |||
Property / zbMATH Keywords: spherically symmetric tree / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Poisson point process | |||
Property / zbMATH Keywords: Poisson point process / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Viktor V. Goryainov / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2292537660 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1411.4426 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Invasion percolation on the Poisson-weighted infinite tree / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Minima in branching random walks / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Convergence in law of the minimum of a branching random walk / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Seneta-Heyde scaling for the branching random walk / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The continuum random tree. I / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Asymptotics in the random assignment problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The continuum random tree. III / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Inhomogeneous continuum random trees and the entrance boundary of the additive coalescent / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4450065 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On explosions in heavy-tailed branching random walks / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The first- and last-birth problems for a multitype age-dependent branching process / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Chernoff's theorem in the branching random walk / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Spectrum of large random reversible Markov chains: heavy-tailed weights on the complete graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Minimal displacement of branching random walk / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Dissecting the circle, at random / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The stable trees are nested / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Limit distributions for minimal displacement of branching random walks / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A line-breaking construction of the stable trees / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Postulates for subadditive processes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Minimal position and critical martingale convergence in branching random walks, and directed polymers on disordered trees / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The first birth problem for an age-dependent branching process / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Minimal positions in a branching random walk / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Domination between trees and application to an explosion problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4940346 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Branching processes. II / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 11:22, 13 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Explosion and linear transit times in infinite trees |
scientific article |
Statements
Explosion and linear transit times in infinite trees (English)
0 references
17 February 2017
0 references
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\)?
0 references
infinite rooted tree
0 references
random Galton-Watson tree
0 references
branching random walk
0 references
spherically symmetric tree
0 references
Poisson point process
0 references
0 references
0 references