Topological spaces of trees as state spaces for stochastic

0 of 0
100%

Transcript Of Topological spaces of trees as state spaces for stochastic

Topological spaces of trees as state spaces for stochastic processes
Habilitationsschrift
Der Fakult¨at fu¨r Mathematik der Universit¨at Duisburg-Essen
eingereicht von
Dr. Wolfgang Lo¨hr
zur Erlangung der Lehrbef¨ahigung im Lehrgebiet
Mathematik
am 17. August 2020 angenommen

ii

iii
Abstract
This thesis presents some aspects of the theory of continuum limits of tree-valued stochastic processes, as well as limits of stochastic processes on (possibly random) trees as the size of the underlying trees tends to inﬁnity. In both situations, in order to get the full picture, one has to work in a suitable, suﬃciently nice, abstract topological state space of (continuum) trees. The focus of the articles collected in this thesis is on the construction and analysis of such state spaces, as well as their usage to obtain general limit theorems. The state spaces fall into two categories. Firstly, the more classical framework using metric measure spaces and various generalizations. Secondly, a new, more algebraic/combinatorial approach of coding the tree-structure by a branch point map without reference to a canonical or pre-speciﬁed metric. We call these objects algebraic measure trees. An important classical tool is to code metric measure trees by excursions. Similarly, we can code binary algebraic measure trees by triangulations of the circle. Some stochastic processes are considered as examples to highlight the applicability and usefulness of the developed state spaces and tools. These are tree-valued multi-type Fleming-Viot processes, tree-valued pruning processes, random walks on trees, and the Aldous chain on cladograms. In all these cases we obtain limit theorems in suitable state spaces of measure trees.
Acknowledgements
First of all, I want to thank Anita Winter for all the advice she gave me, for introducing me to the topic of tree-valued stochastic processes, for the discussions, the plenty of fascinating ideas and her incredible optimism, which motivated me to carry on. I also thank my co-authors of the articles forming the content of this thesis, Siva Athreya, Sandra Kliem, Leonid Mytnik, Thomas Rippl, Guillaume Voisin and Anita Winter, for the not only fruitful but also most enjoyable collaborations. The same applies to my collaborators Hui He, Anton Klimovsky, Sara Mazzonetto and Jan Nagel, who are not co-authors yet, but the discussions with whom certainly contributed to this thesis in one way or another. Further thanks go to my colleagues Fabian Gerle, Roland Meizis and Josue´ Nussbaumer for scientiﬁc discussions, and to them as well as to a lot of other present and former colleagues (in particular including those mentioned above) for the great, friendly atmosphere they created – and are still creating – in our working group. I am also indebted to Nihat Ay for still supporting me even though I changed the scientiﬁc ﬁeld a bit. Last but not least many thanks to Dagmar Goetz, the secretary of our group, who generally does a great and indispensable job, and on the same account to Nicole Obszanski.
Essen, November 27, 2019

iv

Contents

I Introduction

1

Overview

3

About the thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1 The big picture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.1 Trees as metric (measure) spaces . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2 Tree-valued stochastic processes . . . . . . . . . . . . . . . . . . . . . . . . 5

1.3 Continuum trees without a metric . . . . . . . . . . . . . . . . . . . . . . . 6

Main contributions

9

2 Spaces of metric measure spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.1 Topologies on M . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.2 Marked metric measure spaces & tree-valued Fleming-Viot . . . . . . . . . 11

2.3 Gromov-Hausdorﬀ-weak and related topologies . . . . . . . . . . . . . . . . 11

2.4 Inﬁnite measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3 Trees & coding by excursions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

4 Bi-measure trees, LWV-topology & the pruning process . . . . . . . . . . . . . . . 14

5 Tree structure without a metric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

5.1 Algebraic measure trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

5.2 The Aldous diﬀusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

6 An invariance principle on trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

6.1 Speed-ν motions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

6.2 Convergence of speed-ν motions . . . . . . . . . . . . . . . . . . . . . . . . 17

Bibliography

22

v

vi

Contents

II Articles

23

[1] Equivalence of Gromov-Prohorov- and Gromov’s 2λ-metric

on the space of metric measure spaces

25

L¨ohr : Electron. Commun. Probab. 18 (17), 10 pp., 2013

doi: 10.1214/ECP.v18-2268

[2] Existence of mark functions in marked metric measure spaces

33

Kliem, L¨ohr : Electron. J. Probab. 20 (73), 24 pp., 2015

doi: 10.1214/EJP.v20-3969

[3] Convergence of bi-measure R-trees and the pruning process

55

L¨ohr, Voisin, Winter : Ann. Inst. H. Poincar´e Probab. Stat. 51 (4), pp. 1342–1368, 2015

doi: 10.1214/14-AIHP628

[4] Boundedly ﬁnite measures:

Separation and convergence by an algebra of functions

81

L¨ohr, Rippl : Electron. Commun. Probab. 21 (60), 16 pp., 2016

doi: 10.1214/16-ECP17

[5] The gap between Gromov-vague and Gromov-Hausdorﬀ-vague topology

95

Athreya, L¨ohr, Winter : Stochastic Process. Appl. 126 (9), pp. 2527–2553, 2016

doi: 10.1016/j.spa.2016.02.009

[6] Invariance principle for variable speed random walks on trees

119

Athreya, L¨ohr, Winter : Ann. Probab. 45 (2), pp. 625–667, 2017

doi: 10.1214/15-AOP1071

[7] Spaces of algebraic measure trees and triangulations of the circle

151

L¨ohr, Winter : Bull. Soc. Math. France, in press, 2020+

[8] The Aldous chain on cladograms in the diﬀusion limit

193

L¨ohr, Mytnik, Winter : Ann. Probab., in press, 2020+

Part I
Introduction
1

Overview
This cumulative habilitation thesis is organized as follows. Part II, the main part, is a collection of eight articles. They are published in diﬀerent journals, or on the arXiv preprint server and submitted to a journal. The reprints included here diﬀer from the published versions in formatting, typesetting and minor corrections, but not in essential content. Preceding the paper reprints, I give in Section 1 a short overview over the topics and common theme of the articles, as well as a summary of some of their main results within a broader context in Sections 2 – 6.
1 The big picture
Graph-theoretic trees are abundant in mathematics and its applications, from computer science to theoretical biology. Often, the considered trees are ﬁnite but huge. Think, for instance, of search trees in big data analysis or the “tree of live” containing more than one million known species (mostly insects, see [ROO+19]). Therefore, a natural question is how to deﬁne limit objects and appropriate notions of convergence, as the size of the trees tends to inﬁnity. On the one hand, there are local approaches yielding countably inﬁnite graphs, or generalized so-called graphings with a Benjamini-Schramm-type approach (going back to [BS01], see also [Lov12, Part 4]). On the other hand, if one takes a more global point of view, as we are doing here, the predominant (but, as we will see, not the only possible) approach is to consider graph-theoretic trees as metric spaces equipped with the (rescaled) graph distance. Then the limit objects are certain “tree-like” metric spaces, most prominently so-called R-trees introduced by Tits in [Tit77], and we are talking about convergence of metric spaces.
1.1 Trees as metric (measure) spaces
In the ﬁeld of metric geometry, working with spaces of (suﬃciently well-behaved, e.g. compact) metric spaces, and turning them into metric spaces themselves, dates back to the invention of the Gromov-Hausdorﬀ metric in [Gro81, GP81]. It was also realized that, for many applications, more structure is required on the metric space, namely a measure (on its Borel σ-algebra). Hence, theory for spaces of metric measure spaces was developed, most notably by Gromov in [Gro99, Chapter 3 21 ], and with a diﬀerent perspective by Sturm in [Stu06]. A more recent and detailed treatment is given by Shioya in [Shi16]. Originally, the measure was motivated by the volume measure on Riemannian manifolds. It can, e.g., be used to generalize Ricci curvature from manifolds to more general spaces, study transportation problems ([Vil09, LV09]), and deﬁne generalizations of Laplace operators as well as the associated diﬀusion processes ([Stu98, KS05]).
More recently, metric measure spaces have been becoming important in probability theory and its applications. While the research in the area of metric geometry primarily focuses on geodesic
3

4

Overview

spaces with lower curvature bounds (e.g. Alexandrov spaces or Ricci curvature bounds) that behave manifold-like, here tree-like spaces, in particular R-trees, are more important. These are loopfree geodesic spaces or, equivalently, 0-hyperbolic connected spaces. The curvature of R-trees in branch points is −∞, thus they do not fall into the usual classes of spaces with curvature bounds. They are, however, essentially one-dimensional (the Hausdorﬀ dimension can be inﬁnite, but the topological dimension is one), which simpliﬁes the analysis. For instance, it is not too diﬃcult to deﬁne a gradient (w.r.t. an arbitrary ﬁxed point, the root) and, via a partial integration formula, a Laplace operator. This way, using Dirichlet form theory, Athreya, Eckhoﬀ and Winter constructed Brownian motions on R-trees (depending on a speed measure on the tree) in [AEW13]. See also [6] for a generalization to so-called metric trees. This naturally leads to the question if there is a “Donsker theorem for trees”, i.e. does a sequence of random walks on discrete trees with an increasing number of vertices (after suitable rescaling) converge in Skorokhod path space to Brownian motion on a limiting R-tree? And if so in what sense? What does “convergence in path space” actually mean if the stochastic processes are deﬁned on diﬀerent spaces? These questions are the topic of [6], and obviously answering them requires a suitable topological space of trees, which we constructed and analyzed in [5].
Our philosophy, here and elsewhere, is to prove – instead of a collection of speciﬁc cases – a general continuity theorem of the type

Whenever the initial condition converges,

(∗)

the corresponding processes converge, weakly in Skorokhod path space.

The Skorokhod path space of c`adl`ag paths is of course equipped with the standard Skorokhod J1-topology. Here, the “initial condition” includes, apart from the starting point of the process, the underlying tree. And indeed, in [6] we show a very general invariance principle of this type: For every (suﬃciently nice) metric measure tree (T, r, ν) there is a unique associated stochastic process, called speed-ν motion on the tree, in natural scale with the given speed measure ν. This process can be deﬁned via its occupation time formula (together with the strong Markov property), or by its Dirichlet form. It coincides with the random walk and Brownian motion in the cases of discrete trees and R-trees, respectively, and turns out to depend continuously (in path space) on the underlying metric measure tree, provided the space of metric measure trees is equipped with the Gromov-Hausdorﬀ-vague topology introduced in [5]. Of course, we have to make precise what we mean by this, see Section 6.
Long before (topological) spaces of metric measure spaces were introduced into probability theory by Greven, Pfaﬀelhuber and Winter in [GPW09], limits of random trees were extensively studied by Aldous in the seminal sequence of papers [Ald91a, Ald91b, Ald93] by embedding them into 1. In particular, he showed that ﬁnite-variance Galton-Watson trees conditioned to have N vertices, with suitably rescaled edge-lengths, tend in law to a particular, compact, binary random tree called the Brownian continuum random tree (CRT). His work, in particular [Ald93], contains many of the ideas which were put into the more elegant framework of metric measure spaces later. Another way of thinking about continuum trees is to see them as coded by a continuous excursion, which is the “contour process” of the tree. In this way, the Brownian CRT is coded by the normalized Brownian excursion. This idea allows one to use the more familiar theory of random continuous functions (with uniform convergence on compacta on the space of functions), a viewpoint taken around the same time by Le Gall in [LG91, LG93]. He also obtained the theorem of Aldous mentioned above with quite diﬀerent techniques. Continuing this line of research, Le Gall and Duquesne also showed that Galton-Watson trees with inﬁnite variance converge to so called L´evy trees, which can be deﬁned using L´evy processes. See [DLG02, Duq03]. Despite being quite
TreesSpacesProcessesMeasure SpacesMeasure Trees