Probability and real trees : École d'Été de Probabilités de Saint-Flour XXXV-2005 / Steven N. Evans.

Format:

Book

Conference/Event

Author/Creator:

Evans, Steven N. (Steven Neil)

Conference Name:

Ecole d'été de probabilités de Saint-Flour (35th : 2005)

Series:

Lecture notes in mathematics (Springer-Verlag) ; 1920.

Lecture notes in mathematics ; 1920

Language:

English

Subjects (All):

Phylogeny.

Stochastic processes.

Genre:

Conference papers and proceedings.

Physical Description:

xi, 193 pages : illustrations ; 24 cm.

Place of Publication:

Berlin : New York : Springer, [2008]

Summary:

Random trees and tree-valued stochastic processes are of particular importance in combinatorics, computer science, phylogenetics, and mathematical population genetics. Using the framework of abstract "tree-like" metric spaces (so-called real trees) and ideas from metric geometry such as the Gromov-Hausdorff distance, Evans and his collaborators have recently pioneered an approach to studying the asymptotic behaviour of such objects when the number of vertices goes to infinity. These notes survey the relevant mathematical background and present some selected applications of the theory.

Contents:

2 Around the Continuum Random Tree 9

2.1 Random Trees from Random Walks 9

2.1.1 Markov Chain Tree Theorem 9

2.1.2 Generating Uniform Random Trees 13

2.2 Random Trees from Conditioned Branching Processes 15

2.3 Finite Trees and Lattice Paths 16

2.4 The Brownian Continuum Random Tree 17

2.5 Trees as Subsets of l[superscript 1] 18

3 R-Trees and 0-Hyperbolic Spaces 21

3.1 Geodesic and Geodesically Linear Metric Spaces 21

3.2 0-Hyperbolic Spaces 23

3.3 R-Trees 26

3.3.1 Definition, Examples, and Elementary Properties 26

3.3.2 R-Trees are 0-Hyperbolic 32

3.3.3 Centroids in a 0-Hyperbolic Space 33

3.3.4 An Alternative Characterization of R-Trees 36

3.3.5 Embedding 0-Hyperbolic Spaces in R-Trees 36

3.3.6 Yet another Characterization of R-Trees 38

3.4 R-Trees without Leaves 39

3.4.1 Ends 39

3.4.2 The Ends Compactification 42

3.4.3 Examples of R-Trees without Leaves 44

4 Hausdorff and Gromov-Hausdorff Distance 45

4.1 Hausdorff Distance 45

4.2 Gromov-Hausdorff Distance 47

4.2.1 Definition and Elementary Properties 47

4.2.2 Correspondences and [epsilon]-Isometries 48

4.2.3 Gromov-Hausdorff Distance for Compact Spaces 50

4.2.4 Gromov-Hausdorff Distance for Geodesic Spaces 52

4.3 Compact R-Trees and the Gromov-Hausdorff Metric 53

4.3.1 Unrooted R-Trees 53

4.3.2 Trees with Four Leaves 53

4.3.3 Rooted R-Trees 55

4.3.4 Rooted Subtrees and Trimming 58

4.3.5 Length Measure on R-Trees 59

4.4 Weighted R-Trees 63

5 Root Growth with Re-Grafting 69

5.1 Background and Motivation 69

5.2 Construction of the Root Growth with Re-Grafting Process 71

5.2.1 Outline of the Construction 71

5.2.2 A Deterministic Construction 72

5.2.3 Putting Randomness into the Construction 76

5.2.4 Feller Property 78

5.3 Ergodicity, Recurrence, and Uniqueness 79

5.3.1 Brownian CRT and Root Growth with Re-Grafting 79

5.3.2 Coupling 82

5.3.3 Convergence to Equilibrium 83

5.3.4 Recurrence 83

5.3.5 Uniqueness of the Stationary Distribution 84

5.4 Convergence of the Markov Chain Tree Algorithm 85

6 The Wild Chain and other Bipartite Chains 87

6.2 More Examples of State Spaces 90

6.3 Proof of Theorem 6.4 92

6.4 Bipartite Chains 95

6.5 Quotient Processes 99

6.6 Additive Functionals 100

6.7 Bipartite Chains on the Boundary 101

7 Diffusions on a R-Tree without Leaves: Snakes and Spiders 105

7.2 Construction of the Diffusion Process 106

7.3 Symmetry and the Dirichlet Form 108

7.4 Recurrence, Transience, and Regularity of Points 113

7.6 Triviality of the Tail [sigma]-field 115

7.7 Martin Compactification and Excessive Functions 116

7.8 Probabilistic Interpretation of the Martin Compactification 122

7.9 Entrance Laws 123

7.10 Local Times and Semimartingale Decompositions 125

8 R-Trees from Coalescing Particle Systems 129

8.1 Kingman's Coalescent 129

8.2 Coalescing Brownian Motions 132

9 Subtree Prune and Re-Graft 143

9.2 The Weighted Brownian CRT 144

9.3 Campbell Measure Facts 146

9.4 A Symmetric Jump Measure 154

9.5 The Dirichlet Form 157

A Summary of Dirichlet Form Theory 163

A.1 Non-Negative Definite Symmetric Bilinear Forms 163

A.2 Dirichlet Forms 163

A.3 Semigroups and Resolvents 166

A.4 Generators 167

A.5 Spectral Theory 167

A.6 Dirichlet Form, Generator, Semigroup, Resolvent Correspondence 168

A.7 Capacities 169

A.8 Dirichlet Forms and Hunt Processes 169

B Some Fractal Notions 171

B.1 Hausdorff and Packing Dimensions 171

B.2 Energy and Capacity 172

B.3 Application to Trees from Coalescing Partitions 173.

Notes:

Notes from a series of ten lectures given at the Saint-Flour Probability Summer School, July 6-23, 2005.

Includes bibliographical references (pages [177]-184) and index.

ISBN:

3540747974

9783540747970

OCLC:

175285185