Topological spaces of trees as state spaces for stochastic
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 infinity. In both situations, in order to get the full picture, one has to work in a suitable, sufficiently 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-specified 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 scientific 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 scientific field 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-Hausdorff-weak and related topologies . . . . . . . . . . . . . . . . 11
2.4 Infinite 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 diffusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 finite 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-Hausdorff-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 diffusion limit
193
L¨ohr, Mytnik, Winter : Ann. Probab., in press, 2020+
Part I
Introduction
1
Overview
About the thesis
This cumulative habilitation thesis is organized as follows. Part II, the main part, is a collection of eight articles. They are published in different journals, or on the arXiv preprint server and submitted to a journal. The reprints included here differ 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 finite 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 define limit objects and appropriate notions of convergence, as the size of the trees tends to infinity. On the one hand, there are local approaches yielding countably infinite 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 field of metric geometry, working with spaces of (sufficiently well-behaved, e.g. compact) metric spaces, and turning them into metric spaces themselves, dates back to the invention of the Gromov-Hausdorff 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 different 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 define generalizations of Laplace operators as well as the associated diffusion 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 Hausdorff dimension can be infinite, but the topological dimension is one), which simplifies the analysis. For instance, it is not too difficult to define a gradient (w.r.t. an arbitrary fixed point, the root) and, via a partial integration formula, a Laplace operator. This way, using Dirichlet form theory, Athreya, Eckhoff 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 defined on different 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 specific 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 (sufficiently 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 defined 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-Hausdorff-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, Pfaffelhuber 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 finite-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 different techniques. Continuing this line of research, Le Gall and Duquesne also showed that Galton-Watson trees with infinite variance converge to so called L´evy trees, which can be defined using L´evy processes. See [DLG02, Duq03]. Despite being quite
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 infinity. In both situations, in order to get the full picture, one has to work in a suitable, sufficiently 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-specified 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 scientific 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 scientific field 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-Hausdorff-weak and related topologies . . . . . . . . . . . . . . . . 11
2.4 Infinite 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 diffusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 finite 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-Hausdorff-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 diffusion limit
193
L¨ohr, Mytnik, Winter : Ann. Probab., in press, 2020+
Part I
Introduction
1
Overview
About the thesis
This cumulative habilitation thesis is organized as follows. Part II, the main part, is a collection of eight articles. They are published in different journals, or on the arXiv preprint server and submitted to a journal. The reprints included here differ 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 finite 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 define limit objects and appropriate notions of convergence, as the size of the trees tends to infinity. On the one hand, there are local approaches yielding countably infinite 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 field of metric geometry, working with spaces of (sufficiently well-behaved, e.g. compact) metric spaces, and turning them into metric spaces themselves, dates back to the invention of the Gromov-Hausdorff 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 different 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 define generalizations of Laplace operators as well as the associated diffusion 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 Hausdorff dimension can be infinite, but the topological dimension is one), which simplifies the analysis. For instance, it is not too difficult to define a gradient (w.r.t. an arbitrary fixed point, the root) and, via a partial integration formula, a Laplace operator. This way, using Dirichlet form theory, Athreya, Eckhoff 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 defined on different 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 specific 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 (sufficiently 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 defined 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-Hausdorff-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, Pfaffelhuber 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 finite-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 different techniques. Continuing this line of research, Le Gall and Duquesne also showed that Galton-Watson trees with infinite variance converge to so called L´evy trees, which can be defined using L´evy processes. See [DLG02, Duq03]. Despite being quite