On trees invariant under edge contraction.
(Au sujet des arbres invariants par contraction de leurs arêtes.)

*(English. French summary)*Zbl 1364.60105Consider a random rooted, locally finite tree \(T=(V,E,\rho)\) with finitely many ends, and denote by \(\text{Spine}(T)\) the union of ends of \(T\) or \(\{\rho\}\), if \(T\) has no end. Take \(p,q\in(0,1)\), set \(V_0= V\setminus\mathrm{Spine}(T)\), \(V_1= \mathrm{Spine}(T)\setminus\rho\), and define the contracted tree \(C_{p,q}(T,V')\) as the tree with root \(\rho\) and vertex set \(V'\subset V\) containing \(\rho\), every vertex in \(V_0\) independently with probability \(p\), and every vertex in \(V_1\) independently with probability \(q\). The partial order on \(V'\) is the restriction of the partial order on \(V\). The tree \(T\) is called \((p,q)\)-self-similar, if it equals \(C_{p,q}(T,V')\) in distribution.

Next, consider the space of complete, locally compact, rooted, measured \(\mathbb{R}\)-trees \({\mathcal T}\)-\(({\mathcal V},d,\rho,\mu)\), with \(\mu\) bounded, modulo equivalence with respect to root- and measure-preserving isometries. Endow this space with the Gromov-Hausdorff-Prokhorov topology and the Borel \(\sigma\)-field induced by it. Restrict the space to trees with finitely many open ends and \(\mu\) dominating the length measure \(\ell_{{\mathcal T}}\). Define the spine of \({\mathcal T}\) as the subset of vertices which lie on an end, and the rescaled tree \({\mathcal S}_{p,q}({\mathcal T})\) as obtained from \({\mathcal T}\) by shrinking distances on the spine by the factor \(p\) and off the spine by a factor \(q\), and scaling the component \(\mu\)-\(\ell_{{\mathcal T}}\) of \(\mu\) by the factor \(p\). The tree \({\mathcal T}\) is called \((p,q)\)-self-similar, if it is equal in distribution to \({\mathcal S}_{p,q}({\mathcal T})\).

A one-to-one correspondence of \((p,q)\)-self-similar discrete trees and \((p,q)\)-self-similar \(\mathbb{R}\)-trees is obtained via the following discretization of the latter: let \(V^{(0)}\) be the set of atoms of a Poisson process on \({\mathcal V}\) with intensity measure \(\ell_{{\mathcal T}}\) and \(V^{(1)}\) the multiset of atoms of a Poisson process on \({\mathcal V}\) with intensity measure \(\mu\)-\(\ell_{{\mathcal T}}\). Define \(T\) as the rooted tree with vertex set \(V^{(0)}\cup V^{(1)}\) and \(v\) ancestor of \(w\) in \(T\) if and only if it is an ancestor of \(w\) in \({\mathcal T}\) and \(v\in V^{(0)}\). As an example, the class of trees which are invariant with respect to translation along the spine is discussed. In the case of self-similar trees consisting of a single spine to which i.i.d. subtrees are attached, the construction of the corresponding \(\mathbb{R}\)-trees is related to the quasi-stationary distributions of linear-fractional subcritical Bienaymé-Galton-Watson processes.

Next, consider the space of complete, locally compact, rooted, measured \(\mathbb{R}\)-trees \({\mathcal T}\)-\(({\mathcal V},d,\rho,\mu)\), with \(\mu\) bounded, modulo equivalence with respect to root- and measure-preserving isometries. Endow this space with the Gromov-Hausdorff-Prokhorov topology and the Borel \(\sigma\)-field induced by it. Restrict the space to trees with finitely many open ends and \(\mu\) dominating the length measure \(\ell_{{\mathcal T}}\). Define the spine of \({\mathcal T}\) as the subset of vertices which lie on an end, and the rescaled tree \({\mathcal S}_{p,q}({\mathcal T})\) as obtained from \({\mathcal T}\) by shrinking distances on the spine by the factor \(p\) and off the spine by a factor \(q\), and scaling the component \(\mu\)-\(\ell_{{\mathcal T}}\) of \(\mu\) by the factor \(p\). The tree \({\mathcal T}\) is called \((p,q)\)-self-similar, if it is equal in distribution to \({\mathcal S}_{p,q}({\mathcal T})\).

A one-to-one correspondence of \((p,q)\)-self-similar discrete trees and \((p,q)\)-self-similar \(\mathbb{R}\)-trees is obtained via the following discretization of the latter: let \(V^{(0)}\) be the set of atoms of a Poisson process on \({\mathcal V}\) with intensity measure \(\ell_{{\mathcal T}}\) and \(V^{(1)}\) the multiset of atoms of a Poisson process on \({\mathcal V}\) with intensity measure \(\mu\)-\(\ell_{{\mathcal T}}\). Define \(T\) as the rooted tree with vertex set \(V^{(0)}\cup V^{(1)}\) and \(v\) ancestor of \(w\) in \(T\) if and only if it is an ancestor of \(w\) in \({\mathcal T}\) and \(v\in V^{(0)}\). As an example, the class of trees which are invariant with respect to translation along the spine is discussed. In the case of self-similar trees consisting of a single spine to which i.i.d. subtrees are attached, the construction of the corresponding \(\mathbb{R}\)-trees is related to the quasi-stationary distributions of linear-fractional subcritical Bienaymé-Galton-Watson processes.

Reviewer: Heinrich Hering (Rockenberg)

##### MSC:

60J80 | Branching processes (Galton-Watson, birth-and-death, etc.) |

60G18 | Self-similar stochastic processes |

60B10 | Convergence of probability measures |

##### Keywords:

random tree; self-similar process; Gromov-Hausdorff-Prokhorov topology; Bienaymé-Galton-Watson process
PDF
BibTeX
XML
Cite

\textit{O. Hénard} and \textit{P. Maillard}, J. Éc. Polytech., Math. 3, 365--400 (2016; Zbl 1364.60105)

Full Text:
DOI

##### References:

[1] | Abraham, R.; Delmas, J.-F.; Hoscheit, P., A note on the Gromov-Hausdorff-Prokhorov distance between (locally) compact metric measure spaces, Electron. Comm. Probab., 18, 14, 1-21 (2013) · Zbl 1285.60004 |

[2] | Aldous, D., The continuum random tree III, Ann. Probability, 21, 1, 248-289 (1993) · Zbl 0791.60009 |

[3] | Athreya, S.; Löhr, W.; Winter, A., The gap between Gromov-vague and Gromov-Hausdorff-vague topology, Stochastic Processes Appl., 126, 9, 2527-2553 (2016) · Zbl 1384.60016 |

[4] | Aldous, D.; Pitman, J., Tree-valued Markov chains derived from Galton-Watson processes, Ann. Inst. H. Poincaré Probab. Statist., 34, 5, 637-686 (1998) · Zbl 0917.60082 |

[5] | Dress, A. W. M., Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: a note on combinatorial properties of metric spaces, Advances in Math., 53, 3, 321-402 (1984) · Zbl 0562.54041 |

[6] | Drmota, M., Random trees (2009) · Zbl 1170.05022 |

[7] | Dugundji, J., Topology (1966) · Zbl 0144.21501 |

[8] | Evans, S. N.; Pitman, J.; Winter, A., Rayleigh processes, real trees, and root growth with re-grafting, Probab. Theory Related Fields, 134, 1, 81-126 (2006) · Zbl 1086.60050 |

[9] | Evans, S. N., Probability and real trees, 1920 (2008) |

[10] | Forman, N.; Haulk, C.; Pitman, J., A representation of exchangeable hierarchies by sampling from real trees (2011) |

[11] | Flajolet, Ph.; Sedgewick, R., Analytic combinatorics (2009) · Zbl 1165.05001 |

[12] | Greven, A.; Pfaffelhuber, P.; Winter, A., Convergence in distribution of random metric measure spaces \(( \Lambda \)-coalescent measure trees), Probab. Theory Related Fields, 145, 1-2, 285-322 (2009) · Zbl 1215.05161 |

[13] | Gromov, M., Metric structures for Riemannian and non-Riemannian spaces (2007) |

[14] | Hurst, H. E.; Black, R. P.; Simaika, Y. M., Long-term storage: an experimental study (1965) |

[15] | Janson, S., Poset limits and exchangeable random posets, Combinatorica, 31, 5, 529-563 (2011) · Zbl 1265.06002 |

[16] | Lovász, L.; Szegedy, B., Limits of dense graph sequences, J. Combinatorial Theory Ser. B, 96, 6, 933-957 (2006) · Zbl 1113.05092 |

[17] | Maillard, P., The \(\lambda \)-invariant measures of subcritical Bienaymé-Galton-Watson processes, Bernoulli · Zbl 1454.60133 |

[18] | Mandelbrot, B. B.; Van Ness, J. W., Fractional Brownian motions, fractional noises and applications, SIAM Rev., 10, 4, 422-437 (1968) · Zbl 0179.47801 |

[19] | O’Brien, G. L.; Vervaat, W., Self-Similar Processes with Stationary Increments Generated by Point Processes, Ann. Probability, 13, 1, 28-52 (1985) · Zbl 0567.60052 |

[20] | Rémy, J.-L., Un procédé itératif de dénombrement d’arbres binaires et son application à leur génération aléatoire, RAIRO Inform. Théor., 19, 2, 179-195 (1985) · Zbl 0565.05037 |

[21] | Stanley, R. P., Enumerative combinatorics. Vol. 1, 49 (1997) · Zbl 0889.05001 |

[22] | Vervaat, W., Sample Path Properties of Self-Similar Processes with Stationary Increments, Ann. Probability, 13, 1, 1-27 (1985) · Zbl 0555.60025 |

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.