Invasion percolation on regular trees Structure, scaling limit and ponds by Jesse Alexander Goodman B.A., The University of British Columbia, 2001 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY in The Faculty of Graduate Studies (Mathematics) THE UNIVERSITY OF BRITISH COLUMBIA (Vancouver) June 2010 c Jesse Alexander Goodman 2010 Abstract Invasion percolation is an infinite subgraph of an infinite connected graph with finite degrees, defined inductively as follows. To each edge of the underlying graph, attach a random edge weight chosen uniformly from [0, 1], independently for each edge. Starting from a single vertex, a cluster is grown by adding at each step the boundary edge with least weight. Continue this process forever to obtain the invasion cluster. In the following, we consider the case where the underlying graph is a regular tree: starting from the root, each vertex has a fixed number of children. In chapter 2, we study the structure of the invasion cluster, considered as a subgraph of the underlying tree. We show that it consists of a single backbone, the unique infinite path in the cluster, together with sub-critical percolation clusters emerging at every point along the backbone. By studying the scaling properties of the sub-critical parameters, we obtain detailed results such as scaling formulas for the r-point functions, limiting Laplace transforms for the level sizes and volumes within balls, and mutual singularity compared to the incipient infinite cluster. Chapter 3 gives the scaling limit of the invasion cluster. This is a random continuous tree described by a drifted Brownian motion, with a drift that depends on a certain local time. This representation also yields a probabilistic interpretation of the level size scaling limit. Finally, chapter 4 studies the internal structure of the invasion cluster through its ponds and outlets. These are shown to grow exponentially, with law of large numbers, central limit theorem and large deviation results. Tail asymptotics for fixed ponds are also derived. ii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . vii Dedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii Statement of Co-Authorship . . . . . . . . . . . . . . . . . . . . . ix 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1 Invasion percolation and Bernoulli percolation . . . . . . . . 1.1.1 Definition of invasion percolation . . . . . . . . . . . 1.1.2 Bernoulli percolation and the critical parameter pc . . 1.1.3 Invasion percolation and critical percolation . . . . . 1.1.4 Self-organized criticality . . . . . . . . . . . . . . . . 1.1.5 The incipient infinite cluster . . . . . . . . . . . . . . 1.2 Summary of papers . . . . . . . . . . . . . . . . . . . . . . . 1.2.1 Invasion percolation on regular trees . . . . . . . . . . 1.2.2 Scaling limit of the invasion percolation cluster on a regular tree . . . . . . . . . . . . . . . . . . . . . . . . 1.2.3 Exponential growth of ponds in invasion percolation on regular trees . . . . . . . . . . . . . . . . . . . . . 1 1 1 3 4 5 6 6 6 2 Invasion percolation on regular trees 2.1 Introduction and main results . . . 2.1.1 Motivation and background 2.1.2 The incipient infinite cluster 2.1.3 Main results . . . . . . . . . 2.1.4 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 8 9 9 9 13 14 23 iii Table of Contents 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 Structural representation and local behaviour . . . . . . . . . 2.2.1 Structural representation and proof of Theorem 2.1.1 2.2.2 Local behaviour: proof of Theorem 2.1.2 . . . . . . . Analysis of the backbone forward maximum process . . . . . 2.3.1 The Markov representation . . . . . . . . . . . . . . . 2.3.2 Convergence of the forward maximum process to the Poisson lower envelope process . . . . . . . . . . . . . 2.3.3 Multivariate Laplace transform of the Poisson lower envelope . . . . . . . . . . . . . . . . . . . . . . . . . Proof of Theorem 2.1.3 and Corollary 2.1.4 . . . . . . . . . . Cluster size at a given height . . . . . . . . . . . . . . . . . . 2.5.1 Laplace transform of Co [m] . . . . . . . . . . . . . . . 2.5.2 Proof of Theorem 2.1.5 . . . . . . . . . . . . . . . . . 2.5.3 First and second moment . . . . . . . . . . . . . . . . Cluster size below a given height . . . . . . . . . . . . . . . . 2.6.1 Laplace transform of Co [1, m] . . . . . . . . . . . . . 2.6.2 Proof of Theorem 2.1.5 . . . . . . . . . . . . . . . . . 2.6.3 First and second moment . . . . . . . . . . . . . . . . Proof of Theorem 2.1.7 . . . . . . . . . . . . . . . . . . . . . Proof of Theorems 2.1.8 and 2.1.9 . . . . . . . . . . . . . . . Proofs for the incipient infinite cluster . . . . . . . . . . . . . 3 Scaling limit of invasion percolation on a regular tree 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Background . . . . . . . . . . . . . . . . . . . . 3.1.2 Overview . . . . . . . . . . . . . . . . . . . . . . 3.2 Solving E(L) . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Scaling simple sin-trees and their segments . . . . . . . 3.3.1 Notations . . . . . . . . . . . . . . . . . . . . . . 3.3.2 Scaling of segments . . . . . . . . . . . . . . . . 3.3.3 Proof of Proposition 3.3.1 . . . . . . . . . . . . . 3.3.4 Proof of Corollaries 3.3.3 and 3.3.4 . . . . . . . 3.3.5 Two sided trees . . . . . . . . . . . . . . . . . . 3.3.6 Scaling the IIC . . . . . . . . . . . . . . . . . . . 3.4 Bottom-up construction . . . . . . . . . . . . . . . . . . 3.4.1 Right grafting and concatenation . . . . . . . . 3.4.2 Notations . . . . . . . . . . . . . . . . . . . . . . 3.4.3 IPC structure and the coupling . . . . . . . . . 3.4.4 The two-sided tree . . . . . . . . . . . . . . . . . 3.4.5 Convergence of trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 23 27 29 29 32 35 37 39 39 42 44 46 46 50 51 53 55 58 61 61 64 68 69 71 71 72 73 78 79 80 81 81 82 82 85 86 iv Table of Contents 3.5 Level estimates . . . . . . . . . . . . . . . . . . . . . . . . . . 87 4 Exponential growth of ponds in invasion percolation on regular trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 4.1 Introduction and definitions . . . . . . . . . . . . . . . . . . 96 4.1.1 The model: invasion percolation, ponds and outlets . 96 4.1.2 Known results . . . . . . . . . . . . . . . . . . . . . . 98 4.1.3 Summary of notation . . . . . . . . . . . . . . . . . . 100 4.2 Main results . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 4.2.1 Exponential growth of the ponds . . . . . . . . . . . . 101 4.2.2 Tail behaviour of a pond . . . . . . . . . . . . . . . . 102 4.2.3 Outline of the paper . . . . . . . . . . . . . . . . . . . 103 4.3 Markov structure of invasion percolation . . . . . . . . . . . 103 4.3.1 General graphs: ponds, outlets and outlet weights . . 104 4.3.2 Geometric structure of the invasion cluster: the regular tree case . . . . . . . . . . . . . . . . . . . . . . . 105 4.3.3 The outlet weight process . . . . . . . . . . . . . . . . 106 4.4 Law of large numbers and central limit theorem . . . . . . . 107 4.4.1 Tail bounds for pond statistics . . . . . . . . . . . . . 107 4.4.2 A uniform convergence lemma . . . . . . . . . . . . . 108 4.4.3 Proof of Theorems 4.2.1–4.2.2 . . . . . . . . . . . . . 109 4.5 Large deviations: proof of Theorem 4.2.3 . . . . . . . . . . . 110 4.6 Tail asymptotics . . . . . . . . . . . . . . . . . . . . . . . . . 113 4.7 Pond bounds: proof of Proposition 4.4.1 . . . . . . . . . . . 116 4.7.1 The backbone length L: proof of (4.4.1) and (4.4.4) . 117 4.7.2 The pond radius R: proof of (4.4.2) and (4.4.5) . . . 117 4.7.3 The pond volume V : proof of (4.4.3) and (4.4.6) . . . 119 4.8 Percolation with defects . . . . . . . . . . . . . . . . . . . . . 121 5 Conclusion . . . . . . . . . . . . . . . . . . . . . . 5.1 Open questions . . . . . . . . . . . . . . . . . . 5.1.1 High-dimensional lattices . . . . . . . . 5.1.2 Finite super-critical percolation clusters 5.1.3 Ponds and outlets . . . . . . . . . . . . 5.1.4 Random walks with varying drift . . . 5.2 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 123 123 125 125 126 126 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 v List of Figures 2.1 2.2 2.3 2.4 3.1 A simulation of invasion percolation on the binary tree up to height 500. The hue of the ith added edge is i/M , with M the number of edges in the figure. The color sequence is red, orange, yellow, green, cyan, blue, purple, red, so the last edge is almost as red as the first. . . . . . . . . . . . . . . . . . . . The illustration at left shows a spanning tree S(x) for r = 11. The dots are the nodes in N (x). The dots at the leaves are the vertices in x. The dotted line indicates the cut that deletes everything above w in the direction of v; Mwv is the number of edges left after the cut. The illustration at right shows the relation between y, v, v− , k, and the dotted line isolates the edges contributing to Nwv defined in Section 2.4. . . . . . . . . . . . . . . . . . . . . . . . Spanning trees for r = 2 and r = 3. . . . . . . . . . . . . . . Sketch of the graph of L(t) versus t. The dots are the points in P. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A finite tree and its encodings. . . . . . . . . . . . . . . . . . 11 16 18 20 67 vi Acknowledgements I would like to thank the faculty, staff and fellow graduate students of the University of British Columbia Mathematics Department, and particularly the Probability group, for creating a truly friendly and welcoming academic environment, and for the many stimulating conversations we shared. Thank you also to my co-authors, with whom it has been a pleasure to work. Finally, I thank my supervisor, Gordon Slade, for his guidance throughout my graduate program, and for his excellent work with me as a mathematician and as a mentor. vii Dedication To my dear wife Joyce, for her constant support and patience, without which this thesis would not have been possible. viii Statement of Co-Authorship Chapter 2 was researched and jointly written by Omer Angel, Jesse Goodman, Frank den Hollander, and Gordon Slade. Chapter 3 was researched and jointly written by Omer Angel, Jesse Goodman and Mathieu Merle. ix Chapter 1 Introduction 1.1 Invasion percolation and Bernoulli percolation When a rock and a sponge are submerged in water, the rock will be dry on the inside while the sponge becomes wet all the way through. A natural question is how to account for the wetting properties of a material in terms of its intrinsic microscopic structure. To this end, we will model a macroscopic object by an infinite graph, such as a lattice Zd , with a random cluster of edges through which water can flow. In the ordinary (Bernoulli) percolation model first introduced by S. Broadbent and J. Hammersley in 1957 [11], the ability of each edge to carry water is chosen independently. In invasion percolation, first introduced by D. Wilkinson and J. Willemsen in 1983 [46], each edge carries a random weight representing the cost for water to flow through the edge. In this work, we will describe the invasion cluster, through its geometric structure, scaling limit and pond structure, when the underlying graph is a regular tree. This description will be in terms of slightly sub-critical Bernoulli percolation. 1.1.1 Definition of invasion percolation Invasion percolation is a dynamically defined variant of percolation. In this model, consider an infinite connected graph G with finite degrees and a distinguished vertex o. To each edge of G, associate a Uniform[0, 1] random variable called the edge weight. We grow a cluster recursively according to the following algorithm. Set C0 to be the cluster containing o only. At step i, examine the edges on the boundary of Ci−1 and select the boundary edge e whose weight is minimal. Form Ci by adjoining e to Ci−1 . Repeat this process indefinitely. The algorithm is well-defined since we may assume (a.s.) that all edge 1 1.1. Invasion percolation and Bernoulli percolation weights are distinct. We form ∞ C= Ci (1.1.1) i=0 and call C the invasion cluster started from o. By construction, C is an infinite (connected) cluster. Invasion percolation was originally proposed (see [46]) as a model for the displacement of one fluid by another in a porous medium. In this view the edge weights represent the thicknesses of microscopic channels between vertices, and fluid pressure effects lead to the invasion percolation mechanism. A particular application of the model was in oil drilling: water is injected into the bottom an oil reservoir, displacing the oil according to the invasion percolation mechanism and resulting in a flow of oil towards the driller at infinity (or at the boundary in a finite region). The invasion mechanism can also be modified to include the “trapping” rule: if a finite uninvaded region becomes completely surrounded by water, then no further invasions can take place within that region regardless of edge weights. (The oil forms a “bubble” with no escape route towards infinity.) In this context it is natural to ask, for example, what fraction of oil in a large box can be invaded before the trapping rule prevents any further invasions. On finite graphs, invasion percolation is related to the problem of finding minimal spanning trees. Indeed, modify the invasion mechanism so that an edge is rejected if accepting it would produce a loop in the cluster: this is known as Prim’s algorithm for identifying the minimal spanning tree. (Note that this mechanism does not change the vertices accepted into the cluster.) On infinite graphs, invasion percolation does not exhaust the entire graph, and this construction can lead in general to a minimal spanning forest: see [2]. Because invasion percolation accepts the edge of minimal weight, it also has a natural connection to certain models in mathematical physics. Interpret the edge weights as energy barriers in a random energy landscape. If the temperature is low or the energy levels are widely separated, then with high probability a random walker will traverse newly explored edges in the same order as invasion percolation: see [36]. A similar ordering analysis has been used to study the ground state structure of a spin-glass model: [37]. We shall primarily consider the case where G is a forward regular tree of degree σ: namely, the tree in which the root o has degree σ and every other vertex has degree σ + 1. This tree is given a generation structure by considering each vertex to have σ offspring, or children, with every vertex except the root having a unique parent. 2 1.1. Invasion percolation and Bernoulli percolation The regular tree case was first considered by B. Nickel and D. Wilkinson in [39]. Instead of the complete invasion cluster C, they consider the cluster Ci grown after i steps. Using a generating function analysis, Ci is shown to have the same scaling exponents as for a percolation cluster. (The comparison is to a percolation cluster conditioned to have size exactly i; on a regular tree, a symmetry argument shows that this is equivalent to a uniformly chosen subtree of √ size i.) Namely, after i steps both clusters have height and width of order i, with a scaling function that is essentially independent of the tree degree σ. Finally, an alternative definition associates the weights to the vertices (“sites”) of the lattice instead of the edges (“bonds”). This parallels the distinction between bond and site versions of ordinary percolation. As we are primarily concerned with trees, where this distinction is irrelevant, we shall not pursue this further. 1.1.2 Bernoulli percolation and the critical parameter pc As its name suggests, invasion percolation is closely related to ordinary (Bernoulli) percolation. In that model, instead of growing an infinite cluster dynamically, we fix a parameter p ∈ [0, 1] and define each edge to be open with probability p and closed otherwise, independently for every edge. We study the open clusters – connected subgraphs all of whose edges are open – and we are particularly interested in the existence or non-existence of infinite open clusters. Percolation has a natural stochastic ordering across different parameter values p in terms of the edge weights used in invasion percolation. Indeed, fix p and say that an edge is p-open iff its edge weight is at most p; then the p-open edges form a model of Bernoulli percolation with parameter p. Moreover, the open clusters are stochastically increasing in p. In particular there must be a phase transition at which infinite open clusters start to exist. Formally, we define p θ(p) = P o ↔ ∞ (1.1.2) to be the probability that the origin o is part of an infinite p-cluster; in other words, θ(p) is the probability that there exists an infinite non-intersecting path of p-open edges starting from o. By stochastic monotonicity θ(p) is increasing, and we define the critical probability pc = inf {p ∈ [0, 1] : θ(p) > 0} = sup {p ∈ [0, 1] : θ(p) = 0} (1.1.3) 3 1.1. Invasion percolation and Bernoulli percolation For most graphs (including for instance regular trees and Zd for d > 1) the critical probablity is non-trivial, pc ∈ (0, 1), and hence divides [0, 1] into two non-trivial phases – a sub-critical phase where θ(p) = 0 and no infinite clusters can exist, and a super-critical phase where θ(p) > 0 and any vertex has a positive probability of belonging to an infinite open cluster – separated by the critical point p = pc . A long-standing open question concerns the behaviour at the critical point. On many graphs (including regular trees, Z2 and high-dimensional Zd ) it is known that θ(pc ) = 0: all critical clusters must be finite. This result is widely conjectured to hold on Zd for all d ≥ 2; indeed I. Benjamini and O. Schramm [8] conjecture that any transitive1 graph with pc < 1 satisfies θ(pc ) = 0. 1.1.3 Invasion percolation and critical percolation Percolation is defined in terms of an external parameter p, with qualitatively different behaviour depending on the value chosen. By contrast, invasion percolation has no external parameter, instead choosing the smallest possible weight at each step. We therefore begin by asking about the weights of the edges accepted into the invasion cluster. As a first observation, fix any p, and notice that as soon as the invasion process encounters a finite p-cluster, the entire p-cluster will be invaded, followed by the next edge of weight > p. In particular, if p < pc then all p-clusters are finite, and so infinitely many edges of weight > p must be invaded. That is, if ξi denotes the weight of the ith invaded edge, then lim sup ξi ≥ pc (1.1.4) i→∞ Conversely, if an infinite p-cluster is ever encountered – and here we must necessarily have p ≥ pc – then no more edges of weight > p will ever be invaded. Under reasonable hypotheses, we therefore expect equality in (1.1.4), which the following theorem shows. Theorem 1.1.1 ([14] and [24]). If G is transitive then, with probability 1, lim sup ξi = pc (1.1.5) i→∞ This result was originally proved (subject to certain assumptions later verified) by J. Chayes, L. Chayes and C. Newman in [14] for the case G = 1 A graph is transitive iff for each pair of vertices u, v there is a one-to-one adjacencypreserving map of the graph to itself (an automorphism) sending u to v. 4 1.1. Invasion percolation and Bernoulli percolation Zd . It was later greatly generalized by O. H¨aggstr¨om, Y. Peres and R. Schonmann [24] in order to answer a question about ordinary percolation: using their result from Theorem 1.1.1, they analyze the uniqueness of infinite clusters simultaneously for all values of the percolation parameter. The limiting result (1.1.5) can be given a quantitative form as well. Many of the early numerical studies of invasion percolation considered the “acceptance profile” – the distribution of edge weights for the invaded edges. On the regular tree, B. Nickel and D. Wilkinson [39] showed for instance that the ith invaded edge can have weight up to order pc + O(i−1/2 ). The forward regular tree is not transitive because of the distinguished root, so that Theorem 1.1.1 does not apply. In fact the hypothesis of transitivity can be weakened sufficiently to handle the tree as well (see [24, Proposition 3.1]) so that (1.1.5) holds. Indeed, for the tree, (1.1.5) follows from the fact that the number of invaded edges of weight above p is geometric for each p > pc : see section 2.1.1 for a short proof. 1.1.4 Self-organized criticality The limiting result in Theorem 1.1.1 suggests that the invasion cluster behaves like a critical percolation cluster. Since invasion percolation does not have an external parameter, the invasion process “discovers” the critical value pc on its own (in contrast to percolation, where we must set p = pc ourselves). This makes invasion percolation an example of self-organized criticality. In the case of invasion percolation, self-organized criticality can be imagined as arising from a conflict between two opposing tendencies. The invasion mechanism prefers to invade edges of smaller weight, but must also occasionally invade edges with high enough weights to avoid running out of edges. We would therefore expect that, perhaps after an initial period of equilibration, only edges of weights up to about pc would be accepted, and that the invasion cluster looks like critical cluster with occasional extra edges. This heuristic picture is reflected in the Theorem 1.1.1. From another perspective, the invasion cluster must invade super-critical clusters to avoid running out of edges. However, in order to invade a supercritical edge, the invasion process must run out of competing smaller-weight edges. This suggests that the super-critical clusters cannot be too supercritical and must be close to critical in the limit, again as in Theorem 1.1.1. 5 1.2. Summary of papers 1.1.5 The incipient infinite cluster Because of Theorem 1.1.1, the invasion cluster should resemble an infinite “almost critical” percolation cluster. On the other hand, for most graphs of interest it is known or conjectured that all critical percolation clusters are finite. To study the local behaviour of large critical clusters, we therefore study the incipient infinite cluster (IIC), which can be loosely described as a critical cluster conditioned to be infinite. This is conditioning on an event of measure 0, so we must define the IIC by a suitable limiting process. There are several ways to define the IIC formally. In all cases we consider a “cylinder event” E (an event which depends only on the edges in a finite neighbourhood of o), take the conditional probability of E given that the cluster is “large” in some sense, then take a suitable limit. For many choices of conditioning and limit, the resulting limits are known to exist, and to define the same limiting object. One possibility is to set pc P∞ (E) = lim P E o ↔ ∂B(o, R) R→∞ (1.1.6) where B(o, R) denotes the ball of radius R around the root. Because of Theorem 4.3.2, invasion percolation should provide another way of defining the IIC. Indeed, in [27], A. J´arai showed that the invasion cluster in G = Z2 looks locally like the incipient infinite cluster, and a similar result for the tree will be proved in chapter 2. Notably, even though locally equivalent, the invasion cluster and the IIC have different global scaling, and in fact are mutually singular: see chapter 2. 1.2 Summary of papers In this section, we give an overview of the rest of the thesis. Chapters 2 to 4, which are versions of the papers [3, 4, 22], contain the main mathematical results, described below. Chapter 5 discusses some of the open problems related to invasion percolation, including possible techniques for solving them and the challenges that might arise. 1.2.1 Invasion percolation on regular trees In chapter 2, [3] by O. Angel, J. Goodman, F. den Hollander and G. Slade, we analyze the invasion cluster when G is a regular tree. Key to our results is a structural representation of the invasion cluster as an infinite backbone 6 1.2. Summary of papers (the unique infinite non-intersecting path in the cluster) and, along the offbackbone branches of the tree, super-critical percolation clusters conditioned to be finite. We moreover identify the super-critical parameter for the branch emerging from the backbone at height k with Wk , the maximum edge weight above height k on the backbone. Given this structural representation, we analyze the invasion cluster using two further ingredients: a duality between finite super-critical percolation and sub-critical percolation; and a scaling analysis of the process Wk . The decay rate for Wk towards its limiting value pc is given by Wk −pc ≈ k −1 . Comparing the invasion cluster to the incipient infinite cluster, this rate of decay implies that the two clusters have the same scaling exponents, but different scaling limits. From this we obtain the scaling behaviour for the r-point functions and, in terms of Laplace transforms, the number of invaded vertices at level k (the level size) and within a ball of radius k; and also heat kernel and return time estimates for random walk on the invasion cluster. We also compare the invasion cluster to the incipient infinite cluster: we find that the two clusters are locally equivalent and have the same scaling exponents, but that the invasion cluster is stochastically smaller and is indeed mutually singular to the incipient infinite cluster. This result was subsequently extended to Z2 in [16]. 1.2.2 Scaling limit of the invasion percolation cluster on a regular tree In chapter 3, [4] by O. Angel, J. Goodman and M. Merle, we determine the full scaling limit of the invasion cluster. We make extensive use of the encoding of a tree in terms of its Lukaciewicz path, contour function or height function. When the tree arises from critical or slightly sub-critical percolation, it is known that the Lukaciewicz path has a scaling limit in terms of Brownian motion, with or without drift respectively. From [3] we know that the process Wk is constant for long stretches. Within each such interval of constancy, we identify the scaling limit for that piece, then concatenate successive pieces. A key point in this analysis is the special effect of the backbone. To handle this, we prove a general result for trees (in this case, the branches emerging from the backbone) whose roots have a different offspring distribution from the bulk of the tree. As a consequence of identifying the scaling limit, we are able to give a more probabilistic interpretation of the level sizes studied in [3]. There we described the rescaled level size by a Laplace transform. Here we strengthen 7 1.2. Summary of papers that result by describing it explicitly as a sum of exponential variables, arising from the excursions of the Brownian motion from the scaling limit. 1.2.3 Exponential growth of ponds in invasion percolation on regular trees In [3] and [4], we described the invasion cluster by looking at a fixed height k in the original tree. Another natural viewpoint, taken in chapter 4, is to consider the internal structure of the invasion cluster, namely its ponds and outlets. The invaded edge e1 with largest weight is called the first outlet, and the edges invaded before e1 are called the first pond. In general, the nth outlet en is the edge of maximal weight invaded after en−1 , and the nth pond consists of the edges invaded after en−1 up to en . For the case G = Z2 , the ponds and outlet were studied extensively in a series of papers by J. van den Berg, M. Damron, A. J´arai, A. Sapozhnikov and B. V´ agv¨ olgyi ([42], [16], [15]). Let Rn be the largest distance from o to a point in the first n ponds. Then [16, Theorem 1.5] states that P(Rn > k) (log k)n−1 Ppc (o ↔ ∂B(k)) (1.2.1) A similar logarithmic factor appears in the asymptotics of the outlet weights. In [15] exponential bounds for the growth of the ponds were later proved. The work in chapter 4, [22], was motivated in part by the question of what would be the analagous results on regular trees. Somewhat surprisingly, many of the same results hold. We consider the weight Qn of the nth outlet, together with geometric statistics of the ponds such as the volume of the ponds and the length Rn of the longest path from o in the first n ponds. We show that all of these grow exponentially in n, with explicit exponential constants, and satisfy a central limit theorem with a single limiting Brownian motion and a large deviation principle for deviations away from those constants. Furthermore, the tail asymptotics for each quantity are the same as the corresponding asymptotics for critical percolation, with a logarithmic correction: for example, P(Rn > k) (log k)n−1 Ppc (o ↔ ∂B(k)) (1.2.2) exactly as in Z2 . All of these results are proved by analyzing the transition mechanism of the process Qn , together with conditional bounds for the ponds given Qn . 8 Chapter 2 Invasion percolation on regular trees1 2.1 2.1.1 Introduction and main results Motivation and background Invasion percolation is a stochastic growth model introduced by Wilkinson and Willemsen [46]. In its general setting, the edges of an infinite connected graph G are assigned i.i.d. uniform random variables on (0, 1), called weights, a distinguished vertex o is chosen, called the origin, and an infinite subgraph of G is grown inductively as follows. Define I0 to be the vertex o. For N ∈ N0 , given IN , let IN +1 be obtained by adjoining to IN the edge in its boundary with smallest weight. The invasion percolation cluster (IPC) is the random infinite subgraph ∪N ∈N0 IN ⊂ G, which we denote by C. We will occasionally blur the distinction between C as a graph and as a set of vertices. Invasion percolation is closely related to critical percolation. Indeed, suppose G has a bond percolation threshold pc that lies strictly between 0 and 1, and colour red those bonds (= edges) whose weight is at most pc . Once a red bond is invaded, all other red bonds in its cluster will be invaded before the invasion process leaves the cluster. For G = Zd , where critical clusters appear on all scales, we expect larger and larger critical clusters to be invaded, so that the invasion process spends a large proportion of its time in large critical clusters. A reflection of this is the fact, proved for G = Zd by Chayes, Chayes and Newman [14] and extended to much more general graphs by H¨ aggstr¨ om, Peres and Schonmann [24], that the number of bonds in C with weight above pc + ε is almost surely finite, for all ε > 0. When G is a regular tree, this is easy to prove: For any p > pc , whenever an edge is invaded with weight above p, there is an independent positive chance of encountering an infinite p-cluster and never again invading an edge of weight 1 A version of this chapter has been published: Omer Angel, Jesse Goodman, Frank den Hollander, and Gordon Slade. Invasion percolation on regular trees. Annals of Probability, 36(2):420–466, 2008. 9 2.1. Introduction and main results above p. Therefore the number of invaded edges above p is finite (indeed is a geometric random variable). The fact that invasion percolation is driven by the critical parameter pc , even though there is no parameter specification in its definition, makes it a prime example of self-organised criticality. Another reflection of the relation to critical percolation has been obtained by J´ arai [27], who showed for Z2 that the probability of an event E under the incipient infinite cluster (IIC) measure (constructed by Kesten [28]) is identical to the probability of the translation of E to x ∈ Z2 under the IPC measure, conditional on x being invaded and in the limit as x → ∞. It is tempting to take this a step further and conjecture that the scaling limit of invasion percolation on Zd when d > 6 is the canonical measure of super-Brownian motion conditioned to survive forever (see van der Hofstad [43], Conjecture 6.1). Indeed, such a result was proved for the IIC of spread-out (= long-range) oriented percolation on Zd × N0 when d > 4 in van der Hofstad, den Hollander and Slade [44], and van der Hofstad [43], and presumably it holds for the IIC of unoriented percolation on Zd when d > 6 as well. Invasion percolation on a regular tree was studied by Nickel and Wilkinson [39]. They computed the probability generating function for the height and weight of the bond added to IN to form IN +1 . They √ looked, in particular, at the expected number of vertices in IN at level t N , for t ∈ [0, 1] fixed and N → ∞, and found that this expectation is described by the same power law as in critical percolation, but has a different dependence on t (i.e., has a different shape function). They refer to this discrepancy as the “paradox of invasion percolation”. Their analysis does not apply directly to the infinite IPC, so it does not allow for a direct comparison with the IIC. It does suggest though that the IPC has a different scaling limit than the IIC. Let Tσ denote the rooted regular tree with forward degree σ ≥ 2 (i.e., all vertices have degree σ + 1, except the root o, which has degree σ). In the present paper, we study the IPC on Tσ (see Figure 2.1 for a simulation), and show that indeed it does not have the same scaling limit as the IIC. Furthermore, we show that the laws of the IPC and the IIC are mutually singular. There is no reason to believe that this discrepancy will disappear for other graphs, such as Zd , and so the conjecture raised in [43] must be expected to be false. Central to our analysis is a representation of C as an infinite backbone (an infinite self-avoiding path rising from the root) from which emerge branches having the same distribution as subcritical percolation clusters. The percolation parameter value of these subcritical branches depends on a process we call the forward maximal weight process along the backbone. We analyse 10 2.1. Introduction and main results Figure 2.1: A simulation of invasion percolation on the binary tree up to height 500. The hue of the ith added edge is i/M , with M the number of edges in the figure. The color sequence is red, orange, yellow, green, cyan, blue, purple, red, so the last edge is almost as red as the first. 11 2.1. Introduction and main results this process in detail, and prove, in particular, that as k → ∞ the maximum weight of a bond on the backbone above height k is asymptotically pc (1 + Z/k), where Z is an exponential random variable with mean 1. This quantifies the rate at which maximal bond weights approach pc as the invasion proceeds. It is through an understanding of this process that the “paradox of invasion percolation” can be resolved, both qualitatively and quantitatively. It is interesting to compare the above slow decay with the inhomogeneous model of Chayes, Chayes and Durrett [13], in which the percolation parameter p depends on x ∈ Zd and scales like pc + x −( +1/ν) , where ν is the critical exponent for the correlation length. It turns out that for ε < 0 the origin has a positive probability of being in an infinite cluster, but not for ε > 0. For invasion percolation on a tree, the weight pc (1 + Z/k) corresponds to the boundary value ε = 0 (we use graph distance on the tree), but with a random coefficient Z. Invasion percolation therefore corresponds in some sense to the critical case of the inhomogeneous model. From our analysis of the forward maximal weight process along the backbone of invasion percolation on a tree, we are able to compute the scaling of all the r-point functions of C, and of the size of C both at a given height and below a given height. The scaling limits are independent of σ apart from a simple overall factor. Each of these quantities scales according to the same powers laws as their counterparts for the IIC, but with different scaling functions. The Hausdorff dimension of both clusters is 4. Moreover, we apply results of Barlow, J´arai, Kumagai and Slade [5] to prove scaling estimates for simple random walk on C starting from o. These estimates establish that C has spectral dimension 34 , which is the same as for the IIC (see also Kesten [29], and Barlow and Kumagai [6]). It would be of interest to extend our results to invasion percolation on Zd when d > 6 in the unoriented setting and on Zd × N0 when d > 4 in the oriented setting, where lace expansion methods could be tried. However, it seems a challenging problem to carry over the expansion methods developed in Hara and Slade [25], van der Hofstad and Slade [45], and Nguyen and Yang [38], since invasion percolation lacks bond independence and uses supercritical bonds. An additional motivation for the problem on Zd is the following observation of Newman and Stein [35]: if the probability that x ∈ C scales like x 4−d , then this has consequences for the number of ground states of a spin glass model when d > 8. We begin in Section 2.1.2 with a review of the IIC on Tσ , for later comparison with our results for the IPC, which are stated in Section 2.1.3. Section 2.1.4 outlines the rest of the paper. 12 2.1. Introduction and main results Before discussing the IIC, we introduce some notation. We denote the height of a vertex v ∈ Tσ by v ; this is its graph distance from o in Tσ . We write Pp for the law of independent bond percolation with parameter p, P∞ for the law of the IIC of independent bond percolation, and P for the law of the IPC. 2.1.2 The incipient infinite cluster The IIC on a tree is discussed in detail in Kesten [29] and in Barlow and Kumagai [6]. It is constructed by conditioning a critical branching process to survive until time n, and then letting n → ∞. In our case, the branching process has a binomial offspring distribution with parameters (σ, 1/σ). We summarise some elementary properties of the IIC in this section. To keep our exposition self-contained, we provide quick indications of proofs of these properties in Section 2.9. On Tσ , the IIC can be viewed as consisting of an infinite backbone adorned with branches at each vertex that are independent critical percolation clusters in each direction away from the backbone. We write C∞ to denote the IIC. This is an infinite random subgraph of Tσ , but it will be convenient to think of C∞ as a set of vertices. Fix r ≥ 2. Pick r − 1 vertices x = (x1 , . . . , xr−1 ) in Tσ \{o} such that no xi lies on the path from o to any xj (j = i). Let S(x) denote the subtree of Tσ obtained by connecting the vertices in x to o. Call this the spanning tree of o and x. Let N denote the number of edges in S(x). Write x ∈ C∞ for the event that all vertices in x lie in C∞ , which is the same as the event that S(x) ⊂ C∞ . The r-point function is the probability P∞ (x ∈ C∞ ) (with o the rth point). Let ∂S(x) denote the external boundary of S(x); this is the set of vertices in Tσ \S(x) whose parent is a vertex in S(x). The cardinality of ∂S(x) is N (σ − 1) + σ. For y ∈ ∂S(x), let By denote the event that y is in the backbone, i.e., y is the first vertex in the backbone after it emerges from S(x). Then σ N +1 P∞ (x ∈ C∞ ) = N (σ − 1) + σ 1 P∞ (By | x ∈ C∞ ) = N (σ − 1) + σ for y ∈ ∂S(x) (2.1.1) The first line of (2.1.1) gives a simple formula for the r-point function of the IIC, in which only the size of S(x) is relevant, not its geometry. The second line shows that the backbone emerges uniformly from S(x). 13 2.1. Introduction and main results Let C∞ [n] = {x ∈ C∞ : x = n} C∞ [0, n] = {x ∈ C∞ : 0 ≤ x ≤ n}for and abbreviate ρ = ρ(σ) = (2.1.2) n ∈ N0 , σ−1 2σ (2.1.3) Then, under the law P∞ , 1 C∞ [n] =⇒ Γ∞ , ρn 1 C∞ [0, n] =⇒ Γ∞ ρn2 as n → ∞ (2.1.4) where =⇒ denotes convergence in distribution, and Γ∞ , Γ∞ are random variables with Laplace transforms √ −2 E∞ e−τ Γ∞ = cosh τ , (2.1.5) E∞ e−τ Γ∞ = (1 + τ )−2 , for τ ≥ 0. Γ∞ is the size biased exponential with parameter 1, i.e., the distribution with density xe−x , x ≥ 0. It is straightforward to compute the moments: E∞ (Γ∞ ) = 2, 2.1.3 E∞ (Γ2∞ ) = 6, E∞ (Γ∞ ) = 1, E∞ (Γ2∞ ) = 4 3 (2.1.6) Main results This section contains our main results for the scaling behaviour of C under the law P. It is easy to see that, under the law P, C has almost surely a single backbone. Indeed, suppose that with positive P-probability there is a vertex in C from which there are two disjoint branches containing paths to infinity. On this event, let M1 and M2 denote the maximal weights along these branches. It is not possible that M1 > M2 , because the entire infinite second path would be invaded before the edge carrying the weight M1 ; M2 > M1 is ruled out for the same reason. However, M1 = M2 has probability zero, because the Mi are independent with non-atomic distributions (given by the c.d.f. 1 − ζ where ζ is defined in (2.2.3)). Stochastic domination and local behaviour The following two theorems will be proved in Section 2.2. The first theorem is part of a deeper structural representation of the IPC, which is described in Section 2.2.1 and which is the key to all our scaling results. 14 2.1. Introduction and main results Theorem 2.1.1. The IIC stochastically dominates the IPC, i.e., there exists a coupling of C∞ and C such that C∞ ⊃ C with probability 1. Theorem 2.1.2. Let Tσ∗ denote the rooted regular tree in which all vertices (including the root) have degree σ + 1. Let E be a cylinder event on Tσ∗ (i.e., an event that depend on the status of only finitely many bonds), and suppose that E is invariant under the automorphisms of Tσ∗ . Then lim P(τx E | x ∈ C) = P∗∞ (E) x →∞ (2.1.7) where τx denotes the shift by x, and P∗∞ denotes the IIC on Tσ∗ . The symmetry assumption on E in Theorem 2.1.2 is necessary because the unique path in the tree from o to x must be invaded when x ∈ C, whereas P∗∞ has no such preferred path. Theorem 2.1.2 shows that C and C∞ are the same locally far above o. Comparing the results in Sections 2.1.3 – 2.1.3 below with the analogous results for the IIC show that globally they are different. J´ arai [27] proves additional statements in the spirit of Theorem 2.1.2 for invasion percolation on Z2 . We expect that similar statements can be proved also for the tree, but we do not pursue these here. The r-point function For r ≥ 2, the invasion percolation r-point function is the probability P(x1 , . . . , xr−1 ∈ C), which we write as P(x ∈ C) with x = (x1 , . . . , xr−1 ). We can and do assume that no xi lies on the path from o to any xj (j = i), since any such xi is automatically invaded when xj is. To state our result for the asymptotics of the r-point function, some more terminology is required. We recall the definition of S(x), ∂S(x), N and By given in Section 2.1.2. Let N (x) denote the set of nodes of S(x); this is the set consisting of o, the r − 1 vertices in x and any additional vertices where S(x) branches. For v ∈ N (x)\{o}, write v− to denote the node immediately below v, and nv to denote the number of edges in the segment of S(x) between v− and v. We write w < v when w is a node below v. For w, v ∈ N (x) with w < v, let Mwv denote the number of edges in the subtree obtained from S(x) by deleting everything above w in the direction of v. (See Figure 2.2 for an illustration.) Given y ∈ ∂S(x), let v be the first node above or equal to the parent of y, and let k be the distance from v− to the parent of y. Note that v and k depend on y, but we will not make this explicit in our notation. 15 2.1. Introduction and main results ✉v ✉ ✉ ✉ nv ✉ ✉ ✉ y ❜ ✉v− ✉ ✉w ✉ ✉ ✉ ✉ ✉ ✉w− ✉ ✉ o ✉ k❈ ✉ ❈❈❲ ✉ v− ✉ ❈❖ ✉ nw ✉v ✉ ✉ ✉ ✉ ✉ ✉ ✉ w ✉ ✉ ✉ ✉ ✉ ✉ o Figure 2.2: The illustration at left shows a spanning tree S(x) for r = 11. The dots are the nodes in N (x). The dots at the leaves are the vertices in x. The dotted line indicates the cut that deletes everything above w in the direction of v; Mwv is the number of edges left after the cut. The illustration at right shows the relation between y, v, v− , k, and the dotted line isolates the edges contributing to Nwv defined in Section 2.4. 16 2.1. Introduction and main results Theorem 2.1.3 and Corollary 2.1.4, which will be proved in Section 2.4, describe a scaling limit in which the lengths of all the segments of S(x) tend to infinity while the geometry of S(x) stays the same. More precisely, given tv ∈ (0, 1) for each v ∈ N (x)\{o}, with v∈N (x)\{o} tv = 1, we assume that nv → tv N as N → ∞, for v ∈ N (x)\{o} (2.1.8) and, given s ∈ [0, tv ], that k → s as N → ∞ N (2.1.9) with k and v related to y as described above. We write limN →∞ to denote the limit in (2.1.8)–(2.1.9). Furthermore, we define Mwv = mvw N →∞ N lim for w, v ∈ N (x)\{o}, w < v (2.1.10) In the scaling limit, we may associate with S(x) and N (x) a scaled spanning tree S with nodes N . The segments of this tree are labelled by N \{o} and are continuous line pieces with lengths tv , v ∈ N \{o}. The backbone emerges at height s above the bottom of segment v. Theorem 2.1.3. Let r ≥ 2. Suppose that S does not branch at o (i.e., o has degree 1 in S). Then lim σ N +1 P(x ∈ C, By ) = (s + mvv− )πv N →∞ where πv = w∈N tw + mvw− mvw for y ∈ ∂S(x) (2.1.11) (2.1.12) o<w<v with the convention that the empty product is 1. Note that in the right-hand side of (2.1.11) the dependence on s is linear, and that πv and mvv− are simple functionals of the geometry of the scaled spanning tree S. Further note that πv is a product of ratios that take values in (0, 1). By summing (2.1.11) over y ∈ ∂S(x), which amounts to summing first over 0 < k ≤ nv and then over v ∈ N (x)\{o}, we will derive the asymptotics for the r-point function. 17 2.1. Introduction and main results x1 x2 n1 n2 ✉ x1 ✉ ✉ x∗ ✉ n∗ n1 ✉ ✉ o o Figure 2.3: Spanning trees for r = 2 and r = 3. Corollary 2.1.4. Let r ≥ 2. Suppose that S does not branch at o. Then lim N →∞ 1 σ N +1 P(x ∈ C) = (σ − 1)N 1 2 2 tv + tv mvv− πv (2.1.13) v∈N \{o} By combining (2.1.11)–(2.1.13), we obtain the distribution for the vertex where the backbone emerges from S(x), conditional on S(x) being invaded: lim (σ − 1)N P(By | x ∈ C) = N →∞ (s + mvv− )πv 1 2 u∈N \{o} ( 2 tu + tu muu− )πu for y ∈ ∂S(x) (2.1.14) The restriction in Theorem 2.1.3 and Corollary 2.1.4 that S does not branch at o is essential. We will see in Section 2.4 that when S branches at o the limit in (2.1.11) is zero for all y ∈ S(x), i.e., diagrams branching at the bottom are of higher order. The following two examples illustrate (2.1.13)–(2.1.14): Two-point function: For r = 2, S(x) consists of o and a single vertex x1 at height n1 = N . See Figure 2.3. In this case, m1o = 0 and π1 = 1, and therefore 1 1 σ N +1 P(x1 ∈ C) = N →∞ (σ − 1)N 2 lim (2.1.15) lim (σ − 1)N P(By | x1 ∈ C) = 2s for y ∈ ∂S(x1 ) N →∞ The first formula in (2.1.15) also follows directly from the results of Nickel and Wilkinson [39]. The second formula in (2.1.15) shows that the backbone 18 2.1. Introduction and main results branches off the path from o to x1 with an asymptotically linear density. This should be contrasted with the constant density in (2.1.1) for the IIC. In particular, the backbone for invasion percolation is more likely to branch off later than earlier. The reason for this will be discussed at the end of Section 2.2.1. Three-point function: For r = 3, S(x) consists of the nodes o, x∗ at height n∗ , and x1 , x2 at heights n1 , n2 above x∗ . See Figure 2.3. By definition, m1∗ = t∗ + t2 , m2∗ = t∗ + t1 , π∗ = 1, π1 = t∗ /(t∗ + t2 ), and π2 = t∗ /(t∗ + t1 ). Let 1 t1 t2 u(t∗ , t1 , t2 ) = 1+ + (2.1.16) 2 t∗ + t2 t∗ + t1 Then, after some arithmetic, we find that 1 σ N +1 P(x1 , x2 ∈ C) = t∗ u(t∗ , t1 , t2 ) N →∞ (σ − 1)N lim (2.1.17) and lim (σ − 1)N P(By | x1 , x2 ∈ C) 1 t∗ s∗ 1 1 × 1 + t∗ +t = s1 2 u(t∗ , t1 , t2 ) 1 1 + t∗ +t1 s2 N →∞ y ∈ ∂S∗ (x) y ∈ ∂S1 (x) y ∈ ∂S2 (x) (2.1.18) where ∂S∗ (x), ∂S1 (x), ∂S2 (x) denote the external boundaries of the respective segments of S(x). Note that the right-hand side of (2.1.18) is a density on the scaled spanning tree S that is linearly increasing on each segment, and is continuous at the nodes. A similar picture follows from (2.1.14) for all r ≥ 2. The linear slope depends on the structure of the subtree obtained by cutting off everything above the segment, and decreases when moving upwards in the tree. This is in sharp contrast with the uniform distribution for the IIC in (2.1.1), and shows that the scaling limits of the IPC and the IIC are different. Cluster size asymptotics Let P denote the Poisson point process on the positive quadrant with intensity 1. Write PP to denote its law. Let L : (0, ∞) → (0, ∞) denote its lower envelope, defined by L(t) = min{y > 0 : (x, y) ∈ P for some x ≤ t} for t > 0 (2.1.19) 19 2.1. Introduction and main results y s s s s s s s s s s s s s x 0 t Figure 2.4: Sketch of the graph of L(t) versus t. The dots are the points in P. See Figure 2.4 for an illustration. This is a cadlag process, piecewise constant and non-increasing, with limt↓0 L(t) = ∞ and limt→∞ L(t) = 0, PP –a.s. In Section 2.3.2, we will compute its multivariate Laplace transform. As in (2.1.2), let C[n] denote the number of vertices in C at height n, and let C[0, n] = nm=0 C[m] denote the number of vertices up to height n. Recall from (2.1.3) that ρ = (σ − 1)/2σ. 1 Theorem 2.1.5. Let Γn = ρn C[n]. Under the law P, Γn =⇒ Γ as n → ∞, where Γ is the random variable with Laplace transform E e−τ Γ = EP e−S(τ,L) with 1 S(τ, L) = 2τ dt 0 for τ ≥ 0 (2.1.20) L(t)e−(1−t)L(t) L(t) + τ [1 − e−(1−t)L(t) ] (2.1.21) We will show in Section 2.5 that lim E(Γn ) = E(Γ) = 1, n→∞ Theorem 2.1.6. Let Γn = 1 ρn2 lim E(Γ2n ) = E(Γ2 ) = n→∞ 5 3 (2.1.22) C[0, n]. Under the law P, Γn =⇒ Γ as n → ∞, where Γ is the random variable with Laplace transform E e−τ Γ = EP e−S(τ,L) for τ ≥ 0 (2.1.23) with 1 S(τ, L) = 4τ 0 dt L(t) + κ(τ, t) coth[ 12 (1 − t)κ(τ, t)] (2.1.24) 20 2.1. Introduction and main results and κ(τ, t) = 4τ + L(t)2 . We will show in Section 2.6 that 25 1 lim E(Γn ) = E(Γ) = , lim E(Γ2n ) = E(Γ2 ) = n→∞ n→∞ 2 72 (2.1.25) We see no way to evaluate the expectations in (2.1.20) and (2.1.23) in closed form, despite our knowledge of the multivariate Laplace transform of the L-process. Theorems 2.1.5–2.1.6, in addition to showing that the two scaling limits exist, exhibit the underlying complexity of the IPC and underline the key role that is played by the L-process. We will see in Section 2.9 that by setting L ≡ 0, we recover the expressions for the IIC in (2.1.5). The laws of Γ and Γ are not the same as their IIC counterparts Γ∞ and Γ∞ , as is immediate from a comparison of (2.1.22) and (2.1.25) with (2.1.6). The power law scalings of C[n] and C[0, n] in Theorems 2.1.5– 2.1.6 are, however, the same linear and quadratic scalings as for the IIC. In particular, Theorem 2.1.6 is a statement that the Hausdorff dimension of the IPC is 4, as it is for the IIC. (For this, we imagine that paths in the IPC are embedded in Zd as random walk paths, with the root mapped to the origin, so that the on the order of n2 = r4 vertices in the IPC below level n = r2 will be within distance r of the origin.) Comparing the values of the first and second moments of Γ and Γ∞ , we see that the IPC has half the size of the IIC on average, while the ratio of the variance of the size of the IPC 7 to the square of its mean is 18 , compared to 13 for the IIC. The relatively larger fluctuation for the IPC is due to the randomness of the weights on the backbone; this will be discussed further in Section 2.2.1. The scaling of the first and second moments of C[n] and C[0, n] implied by (2.1.22) and (2.1.25) can also be deduced directly from the scaling of the 2-point and the 3-point function (recall (2.1.15) and (2.1.17)). In the same manner we can deduce that lim n1 ,n2 →∞ n1 /n2 →a E(Γn1 Γn2 ) = 1 + 31 a(1 + a) for a ∈ [0, 1] (2.1.26) as we will show in Section 2.5.3. It would be interesting to study (Γn )n∈N as a process, but we do not pursue this here. Mutual singularity of IPC and IIC We will prove the following theorem, which shows an interesting manifestation of the difference between the IPC and the IIC. Theorem 2.1.7. The laws of IPC and IIC are mutually singular. 21 2.1. Introduction and main results Simple random walk on the invasion percolation cluster Given C, let µy denote the degree in C (both forward and backward) of a vertex y ∈ C. Consider the discrete-time simple random walk X = (Xk )k∈N0 on C that starts at X0 = x and makes transitions from y in C to any neighbour of y in C with probability 1/µy . Denote the law of this random walk given C by PCx , with corresponding expectation ECx . We will consider three quantities: Rk = {X0 , . . . , Xk } (2.1.27) the range of X up to time k, with cardinality |Rk |; the k-step transition kernel 1 PC (Xk = y | X0 = x) (2.1.28) pC k (x, y) = µy C which satisfies the reversibility relation pC k (x, y) = pk (y, x); and the first exit time above height n, Tn = min{k ≥ 0 : Xk = n}. The following theorem provides power laws for these three quantities. Theorem 2.1.8. There is a set Ω0 of configurations of the IPC with P(Ω0 ) = 1, and positive constants α1 , α2 , such that for each configuration C ∈ Ω0 and for each x ∈ C, the simple random walk on C obeys the following: (a) log |Rk | 2 lim = PCx –a.s. (2.1.29) k→∞ log k 3 (b) There exists Kx (C) < ∞ such that α1 −2/3 (log k)−α1 k −2/3 ≤ pC 2k (x, x) ≤ (log k) k ∀ k ≥ Kx (C) (2.1.30) (c) There exists Nx (C) < ∞ such that (log n)−α2 n3 ≤ ECx (Tn ) ≤ (log n)α2 n3 ∀ n ≥ Nx (C) (2.1.31) The results in Theorem 2.1.8 are similar to the behaviour of simple random walk on the IIC; see Barlow, J´arai, Kumagai and Slade [5], Barlow and Kumagai [6], Kesten [29]. The spectral dimension ds of C can be defined by log pC 2k (o, o) k→∞ log k ds = −2 lim (2.1.32) From (2.1.30) we see that ds = 34 . For additional statements concerning the height Xn after n steps, see [5]. With the help of results from [6], it is shown in [5, Example 1.9(ii)] that (2.1.29)–(2.1.31) hold for simple random walk on any random subtree of 22 2.2. Structural representation and local behaviour the IIC for Tσ such that the expectation of 1/C[0, n] is bounded above by a multiple of 1/n2 . In view of Theorem 2.1.1, to prove Theorem 2.1.8 it therefore suffices to prove the following uniform bound, which will be done in Section 2.8. Theorem 2.1.9. supn∈N E 2.1.4 n2 C[0, n] <∞ Outline Section 2.2 puts forward a structural representation of the invasion percolation cluster in terms of independent bond percolation, and gives the proof of Theorems 2.1.1 and 2.1.2. This structural representation plays a key role throughout the paper. Section 2.3 analyses the process of forward maximal weights along the backbone and provides a scaling limit for this process in terms of the Poisson lower envelope process defined in (2.1.19). The multivariate Laplace transform of the latter is computed explicitly. Section 2.4 gives the proof of Theorem 2.1.3 and Corollary 2.1.4, based on the results in Section 2.3. Sections 2.5–2.8 give the proofs of Theorems 2.1.5, 2.1.6, 2.1.7 and 2.1.9, respectively. Section 2.9 provides a quick indication of proofs of the claims made in Section 2.1.2. 2.2 Structural representation and local behaviour In Section 2.2.1, we show that the IPC can be viewed as a random infinite backbone with subcritical percolation clusters emerging in all directions. The parameters of these subcritical clusters depend on the height of the vertex on the backbone from which they emerge, and tend to pc as this height tends to infinity. Theorem 2.1.1 follows immediately. In Section 2.2.2, we prove Theorem 2.1.2. 2.2.1 Structural representation and proof of Theorem 2.1.1 The structural representation As noted above, the backbone is a.s. unique. Let Bl , l ∈ N, denote the weights of its successive edges, and define Wk = max Bl l>k for k ∈ N0 (2.2.1) To see that the maximum in (2.2.1) is achieved, we first note that for each k ∈ N0 there must a.s. be an l > k with Bl > pc , since supercritical edges 23 2.2. Structural representation and local behaviour must be invaded to create an infinite cluster. On the other hand, we showed in Section 2.1.1 that for each p > pc there are at most finitely many edges invaded with weight above p. Thus the maximum in (2.2.1) is achieved, and Wk > pc a.s. In particular, W0 is the weight of the heaviest edge on the backbone. Hence it is also the weight of the heaviest edge ever invaded, since the existence of the infinite backbone path implies that no weight heavier than W0 need ever be accepted. The W -process is at the heart of our analysis, and we will study it in detail in Section 2.3. In particular, in a sense to be made precise in Proposition 2.3.3, we will see that 1 Wk ∼ p c 1 + Z k as k → ∞ (2.2.2) with Z an exponential random variable with mean 1. This shows the slow rate of decay of Wk towards the critical value. The key observation behind the scaling results in Section 2.1.3 is the following structural representation of C in terms of independent bond percolation. Proposition 2.2.1. Under P, C can be viewed as consisting of: (1) a single uniformly random infinite backbone; (2) for all k ∈ N0 , emerging from the k th vertex along the backbone, in all directions away from the backbone, a supercritical percolation cluster with parameter Wk conditioned to stay finite, all conditionally independent given (Wk )∞ k=0 . Proof. By symmetry, all possible backbones are equally likely. We condition on the backbone, abbreviated BB. Conditional on W = (Wk )k∈N0 , the following is true for every x ∈ Tσ : x ∈ C if and only if every edge on the path between xBB and x carries a weight below Wk , with xBB the vertex where the path downwards from x hits BB and k = xBB . Indeed, if one of the edges in the path has weight above Wk , then this edge cannot be invaded, because the entire infinite BB is invaded first. Conversely, if all edges in the path have weight below Wk , then x will be invaded before the edge on BB with weight Wk is. In other words, the event {BB = bb, W = w} is the same as the event that for all k ∈ N0 there is no percolation below level Wk in each of the branches off BB at height k, and the forward maximal weights along bb are equal to w. This proves the claim. 24 2.2. Structural representation and local behaviour The functions θ and ζ For independent bond percolation on Tσ with parameter p, let θ(p) denote the probability that o is in an infinite cluster, and let ζ(p) denote the probability that the cluster along a particular branch from o is finite. Then we have the relations θ(p) = 1 − ζ(p)σ , ζ(p) = 1 − pθ(p) (2.2.3) The critical probability is pc = 1/σ, and θ(pc ) = 0, ζ(pc ) = 1. For future reference, we note the following elementary facts. Differentiation of (2.2.3) gives θ (p) = σζ(p)σ−1 [−ζ (p)], ζ (p) = −θ(p) − pθ (p) (2.2.4) from which we see that − ζ (p) = θ(p) 1 − pσζ(p)σ−1 (2.2.5) The right-hand side gives 00 for p = pc . Using l’Hˆopital’s rule and the first equality of (2.2.4), we find that 2σ 1 = σ−1 ρ (2.2.6) where we recall the definition of ρ in (2.1.3), and where derivatives at pc are interpreted as right-derivatives. From this, we obtain − ζ (pc ) = σ[−ζ (pc )] −σ + (σ − 1)[−ζ (pc )] θ(p) ∼ σ (p − pc ), ρ and hence 1 − ζ(p) ∼ 1 (p − pc ) ρ − ζ (pc ) = as p ↓ pc (2.2.7) In Section 2.3 we will need that ζ(p) is a convex function of p ∈ [pc , 1]. This can be seen as follows. Since ζ is decreasing on [pc , 1] and maps this interval to [0, 1], it is convex if and only if the inverse function p = p(ζ) is 1−x a convex function of ζ ∈ [0, 1]. By (2.2.3), p = F (ζ) with F (x) = 1−x σ. Computation gives σxσ−2 G(x) with (1 − xσ )3 G(x) = −(σ − 1)xσ+1 + (σ + 1)xσ − (σ + 1)x + (σ − 1) F (x) = (2.2.8) and hence it suffices to show that G(x) is positive on [0, 1]. However, G(1) = 0, and G (x) = −(σ + 1) −σxσ−1 + (σ − 1)xσ + 1 (2.2.9) 25 2.2. Structural representation and local behaviour is negative by the arithmetic-geometric mean inequality (1 − α)x1 + αx2 ≥ (x1−α xα2 )1/α with α = 1/σ, x1 = xσ and x2 = 1. 1 For the special case σ = 2, (2.2.3) solves to give θ(p) = 0 ∨ 2p − 1 , p2 ζ(p) = 1 ∧ 1−p p (2.2.10) Duality and proof of Theorem 2.1.1 The following duality is important in view of Proposition 2.2.1. Although this duality is standard in the theory of branching processes, we sketch the proof for completeness. Lemma 2.2.2. On Tσ , a supercritical percolation cluster with parameter p > pc conditioned to stay finite has the same law as a subcritical cluster with dual parameter p = p(p) = pζ(p)σ−1 < pc (2.2.11) Moreover, p(pc ) = pc , p(1) = 0, d dp p(p) < 0 on (pc , 1), and pc − p(p) ∼ p − pc as p ↓ pc (2.2.12) For the special case σ = 2, (2.2.10) and (2.2.11) imply that the duality relation takes the simple form p = 1 − p. Proof. Let v be a vertex in Tσ and let C(v) denote the forward cluster of v for independent bond percolation with parameter p. Let U be any finite subtree of Tσ , say with m edges, and hence with (σ − 1)m + σ boundary edges. Then Pp (U ⊂ C(v) | |C(v)| < ∞) = = Pp (U ⊂ C(v), |C(v)| < ∞) Pp (|C(v)| < ∞) pm ζ(p)(σ−1)m+σ ζ(p)σ (2.2.13) the numerator being the probability that the edges of U are open and there is no percolation from any its vertices. Let p = pζ(p)σ−1 (2.2.14) Then the right-hand side of (2.2.13) equals pm = Ppˆ(U ⊂ C(v)). Since U is arbitrary, this proves the first claim. Since the p percolation clusters are a.s. finite we find p ≤ pc . Since ζ(pc ) = 1 and ζ(1) = 0, (2.2.14) implies that p(pc ) = pc and p(1) = 0. 26 2.2. Structural representation and local behaviour d Direct computation gives dp p(p) = ζ(p)σ−1 + p(σ − 1)ζ(p)σ−2 ζ (p), which is negative if and only if −ζ (p) > ζ(p)/p(σ − 1). By using (2.2.5) and (2.2.3), we see that the latter inequality holds if and only if pσ > 1, which is the same as p > pc . Finally, we use the above formula for the derivative of p(p), d together with (2.2.6), to see that dp p(pc ) = −1 and hence pc − p(p) ∼ p − pc (2.2.15) which is (2.2.12). Since a.s. Wk > pc for all k ∈ N0 , we have Wk < pc for all k ∈ N0 . Combining Proposition 2.2.1 and Lemma 2.2.2, we conclude that C can be regarded as a uniformly random infinite backbone with independent subcritical branches with parameter Wk emerging from the backbone vertex at height k in all directions away from the backbone. We are now in a position to better understand the difference between the IPC and the IIC. For the IIC, the branches emerging from the backbone are all critical percolation clusters. For the IPC, the branches are subcritical, and become increasingly close to critical as they branch off higher. Thus low branches tend to be smaller than high branches. Conditional on x ∈ C, it is more likely for x to be in a larger rather than a smaller branch, consistent with the observation in Section 2.1.3 that the backbone is more likely to branch off the path from o to x higher rather than lower. The fact that the IPC is on average thinner than the IIC, as was observed in Section 2.1.3, is obvious from the fact that the subcritical branches of the IPC are smaller than the critical branches of the IIC. Moreover, the fact that there is randomness in the weights Wk that determine the percolation parameters for the branches is consistent with the observation in Section 2.1.3 that the IPC has relatively larger fluctuations than the IIC. Proof of Theorem 2.1.1. It was noted in Section 2.1.2 that the IIC on Tσ can be viewed as consisting of a uniformly random infinite backbone with independent critical branches. In view of this observation, the statement made in Theorem 2.1.1 is an immediate consequence of Proposition 2.2.1 and Lemma 2.2.2. 2.2.2 Local behaviour: proof of Theorem 2.1.2 Proof of Theorem 2.1.2. The main idea in the proof is that a vertex x ∈ C is unlikely to be very close to the backbone. On the other hand, the branch 27 2.2. Structural representation and local behaviour off the backbone containing x is unlikely to branch close to o, and so it is close to critical percolation. Fix a cylinder event E on Tσ∗ . Let k = kE denote the maximal distance from o to a vertex in a bond upon which E depends. Fix x ∈ Tσ . Let M = M (x) denote the height of the highest vertex in the backbone on the path in Tσ from o to x. As before, we write WM for the forward maximal weight above this vertex at height M on the backbone. For ε > 0, let Ax = {M ≥ x − k} , B x,ε = {WM ≥ pc + ε} , Gx,ε = (Ax ∪ B x,ε )c (2.2.16) It follows from (2.1.15) (although we have not yet proved (2.1.15), we will not use circular reasoning) that lim P(Ax | x ∈ C) = 0 x →∞ ∀ε > 0 (2.2.17) We will prove that also lim P(B x,ε | x ∈ C) = 0 ∀ε > 0 (2.2.18) lim P(Gx,ε | x ∈ C) = 1 ∀ε > 0 (2.2.19) P(x ∈ C, M = m, B x,ε ) P(x ∈ C) (2.2.20) x →∞ implying x →∞ To prove (2.2.18), we put x = n and write n P(B x,ε | x ∈ C) = m=0 By (2.1.15), the denominator is at least cnσ −n for some c > 0. By Proposition 2.2.1 and Lemma 2.2.2, the numerator is at most σ −m [p(ε)]n−m P(Wm ≥ pc + ε) with p(ε) the dual of pc + ε (we used the fact that Wm ≥ p implies Wm ≤ p for all p > pc ). Since p(ε) ≤ pc = σ −1 , we thus have P(B x,ε | x ∈ C) ≤ 1 cn n P(Wm ≥ pc + ε) (2.2.21) m=0 From Lemma 2.3.2 in Section 2.3.1 we will see that P(Wm ≥ pc + ε) ≤ exp[−c(ε)m] for all m ∈ N for some c(ε) > 0. Hence the sum in (2.2.21) is bounded in n for fixed ε. This proves (2.2.18). For each ε > 0, we have P(τx E | x ∈ C) − P∗∞ (E) ≤ P(τx E | x ∈ C) − P(τx E | x ∈ C, Gx,ε ) + P(τx E | x ∈ C, Gx,ε ) − P∗∞ (E) (2.2.22) 28 2.3. Analysis of the backbone forward maximum process In view of (2.2.19), the first term on the right-hand side goes to zero as x → ∞ for ε > 0 fixed, so it suffices to prove that lim sup P(τx E | x ∈ C, Gx,ε ) − P∗∞ (E) = 0 ε↓0 x∈T ∗ σ (2.2.23) Now, on the event {x ∈ C} ∩ Gx,ε , we have x − k > M , so that the event τx E depends only on bonds within a branch leaving the backbone at height M , and WM ∈ [pc , pc + ε), so that this branch is as close as desired to a critical tree when ε is sufficiently small. Therefore, in the limit as ε ↓ 0, P(τx E | x ∈ C, Gx,ε ) approaches the probability of E under the IIC rooted at x and with a particular initial backbone segment of length x − M . The rate of convergence depends on the number of bonds upon which E depends, but is uniform in x. However, by our hypothesis that E is invariant under the automorphisms of Tσ∗ , E has the same probability under the law P∗∞ conditional on any choice of the initial backbone segment. This proves (2.2.23). 2.3 Analysis of the backbone forward maximum process In this section, we prove that the backbone forward maximum process W = (Wk )k∈N0 converges, after rescaling, to the Poisson lower envelope process L = (L(t))t>0 . In Section 2.3.1, we analyse W as a Markov chain. In Section 2.3.2, we prove the convergence to L. Finally, in Section 2.3.3, we compute the multivariate Laplace transform of L. 2.3.1 The Markov representation Proposition 2.3.1. W = (Wk )k∈N0 is a decreasing Markov chain taking values in (pc , 1) with initial distribution P(W0 ≤ u) = θ(u) and transition probabilities P (Wk+1 = Wk | Wk = u) = 1 − R(u)θ(u) (2.3.1) P (Wk+1 ∈ dv | Wk = u) = R(u) θ (v) dv for pc < v < u < 1, where R(u) = 1 . −ζ (u) Proof. The event {W0 ≤ u} is the event that there is percolation at level u on the tree, and hence has probability θ(u). Denote by W<k the vector (Wj )0≤j<k . Clearly the process does not depend on which particular path forms the backbone, so we may fix the first 29 2.3. Analysis of the backbone forward maximum process k edges of the backbone. Fix a vector w and v ≤ u ≤ wk−1 , and consider the conditional probability P(Wk+1 ∈ dv|Wk = u, W<k = w). This is defined in terms of the conditional expectation E I(Wk+1 ∈ dv) | Wk , W<k (2.3.2) by setting Wk = u and W<k = w. We let B<k denote the backbone weights below height k, and note that the above conditional expectation is equal to E E[I(Wk+1 ∈ dv) | Wk , B<k ] | Wk , W<k (2.3.3) since the pair Wk , B<k specifies more information that the pair Wk , W<k . However, it is clear that E[I(Wk+1 ∈ dv) | Wk , B<k ] = E[I(Wk+1 ∈ dv) | Wk ] (2.3.4) since given Wk the values of B<k cannot affect Wk+1 . Thus (2.3.2) is equal to E E[I(Wk+1 ∈ dv) | Wk ] | Wk , W<k = E[I(Wk+1 ∈ dv) | Wk ] (2.3.5) This shows that (Wk ) is a Markov process. To evaluate the transition probabilities we may consider only the case k = 0. We have already seen that P(W0 ∈ du) = θ (u)du (2.3.6) For v < u, to have both W0 ∈ du and W1 ∈ dv there must also be an edge e from the root such that: 1. the threshold for percolation above e is in dv; 2. the weight of edge e is we ∈ du; 3. there is no percolation at level u in the other branches emerging from the root. With σ choices for e we get P(W1 ∈ dv, W0 ∈ du) = σθ (v) dv du ζ σ−1 (u) (2.3.7) Combining (2.3.6), (2.3.7) and using (2.2.4) we get P(W1 ∈ dv|W0 = u) = σζ σ−1 (u) θ (v)dv = R(u)θ (v)dv θ (u) (2.3.8) 30 2.3. Analysis of the backbone forward maximum process Finally, integrating over v ∈ (pc , u) we find P(W1 < W0 |W0 = u) = R(u)θ(u) (2.3.9) and (2.3.1) follows from (2.3.8)–(2.3.9). Note the separation in u and v in (2.3.1). The convexity of ζ (see Section 2.2.1) implies that R is increasing and so, together with (2.2.6), yields R(u) ≥ R(pc ) = ρ for u ∈ [pc , 1] (2.3.10) For the special case σ = 2, (2.2.10) gives R(u) = u2 . We have established already that Wk > pc for all k ∈ N0 . Since θ(pc ) = 0, this fact is clear also from (2.3.13). The following large deviation estimate, which we applied in Section 2.2.2, shows that Wk ↓ pc as k → ∞, P-a.s. Lemma 2.3.2. For every δ > 0 there is a c(δ) > 0, satisfying c(δ) ∼ δ as δ ↓ 0, such that P Wk ≥ σ1 (1 + δ) ≤ e−c(δ)k and P Wk ≤ σ1 (1 − δ) ≤ e−c(δ)k ∀ k ∈ N0 (2.3.11) Proof. We first claim that P(Wk ≥ p) ≤ [1 − ρθ(p)]k ∀k ∈ N0 (2.3.12) Indeed, (2.3.1) tells us that, for every l ∈ N0 , given Wl = u, the probability that Wl+1 < p is R(u)θ(p). Hence, by (2.3.10), at each step W has probability at least ρθ(p) to jump below p, which implies (2.3.12). By (2.2.7), we have θ( σ1 (1 + δ)) ∼ ρδ as δ ↓ 0, and so we get the first part of (2.3.11). The second part follows from the first via Lemma 2.2.2. From (2.3.1), we have the following recursive representation for the W process. Let (Xk )k∈N0 be i.i.d. random variables with law P(X1 ∈ du) = θ (u)du, u ∈ (pc , 1). Then W0 = X0 and, for k ∈ N0 , Wk+1 = Wk Wk ∧ Xk+1 with probability 1 − R(Wk ) with probability R(Wk ) (2.3.13) To prepare the ground for Proposition 2.3.3 below, let Yk = ρ θ (Wk ) for k ∈ N0 (2.3.14) 31 2.3. Analysis of the backbone forward maximum process Note that Yk ↓ 0 as k → ∞, P-a.s., by Lemma 2.3.2. Let (Uk )k∈N0 be i.i.d. uniform random variables on [0, 1]. Then it follows from (2.3.13) that Y = (Yk )k∈N0 is a Markov chain with initial value Y0 = ρU0 and recursive representation Yk with probability 1 − q(Yk ) Yk Uk+1 with probability q(Yk ) Yk+1 = where q(y) = y R θ−1 ρ y ρ (2.3.15) (2.3.16) with θ−1 the inverse of the function θ. It then follows from (2.3.10) that q(y) ≥ y for y ∈ [0, ρ] q(y) ∼ y and as y ↓ 0 (2.3.17) This will be important in Section 2.3.2. 2.3.2 Convergence of the forward maximum process to the Poisson lower envelope process The key to our analysis is the following proposition, which shows that the Poisson lower envelope process L in (2.1.19) is the scaling limit of the backbone forward maximum process W in (2.2.1). In particular, by taking t = 1 in (2.3.18) and using the fact that L(1) is an exponential random variable ∗ with mean 1, we get the claim made in (2.2.2). We write =⇒ to denote convergence in distribution in the space of cadlag paths endowed with the Skorohod topology (see Billingsley [9, Section 14]). Proposition 2.3.3. For any ε > 0, k[σW kt − 1] ∗ t≥ε =⇒ (L(t))t≥ε as k → ∞ (2.3.18) Proof. The proof is based on the representation (2.3.15). Let N = (N (t))t≥0 denote the Poisson process on [0, ∞) that increases at rate 1. Define Y (t) = YN (t) for t ≥ 0 (2.3.19) Then Y = (Y (t))t≥0 is the continuous-time Markov process with initial value Y0 that from height z jumps down to height zU [0, 1] at exponential rate q(z). The L-process defined in (2.1.19) is the continuous-time Markov process that from height z jumps down to height zU [0, 1] at exponential rate z. Below we will first use (2.3.17) to show that, for any ε > 0, ∗ (k Y (kt))t≥ε =⇒ (L(t))t≥ε (2.3.20) 32 2.3. Analysis of the backbone forward maximum process After that we will use the strong law of large numbers for N , namely limk→∞ N (kt)/kt = 1 a.s., to show that, for any ε > 0, (kY ∗ kt )t≥ε =⇒ (L(t))t≥ε (2.3.21) Once we have (2.3.21), the proof is complete because Y kt ∼ σW kt − 1 as k → ∞, uniformly in t ≥ ε (2.3.22) as is immediate from (2.2.7) and (2.3.14), and the fact that the Y -process converges to 0, P-a.s. Proof of (2.3.20): The proof uses a perturbative coupling argument, relying on the fact that q(z) ≥ z for z > 0, while for every δ > 0 there exists a z0 = z0 (δ) > 0 such that q(z) ≤ (1 + δ)z for all z ∈ (0, z0 ]. Upper bound: For y0 > 0, let Ly0 = (Ly0 (t))t>0 be restriction to (0, ∞) × (0, y0 ] of the lower envelope process associated with the Poisson process P (recall Figure 2.4), i.e., for t > 0, Ly0 (t) = y0 ∧ L(t) = y0 ∧ min{y > 0 : (x, y) ∈ P for some x ≤ t} (2.3.23) From height z ≤ y0 , Ly0 jumps down at exponential rate z. Therefore, conditional on Y0 = y0 , we can couple Y and Ly0 such that Y (t) ≤ Ly0 (t) ∀t > 0 (2.3.24) Indeed, to achieve the coupling we use the same uniform random variables for the jumps downwards in both processes (so that the same sequence of heights are visited), but after each jump we arrange that Y waits less time than Ly0 for its next jump, which is possible because q(z) ≥ z for z > 0. Combining (2.3.23) and (2.3.24), we find that Y and L can be coupled so that Y (t) ≤ Ly0 (t) ≤ L(t) ∀t > 0 (2.3.25) This is a stochastic upper bound valid for all times. Lower bound: We can imitate the above coupling argument, except that, in order to properly exploit the inequality q(z) ≤ (1 + δ)z for z ∈ (0, z0 ], we need a Poisson process with intensity 1 + δ, which we denote by P 1+δ , and we start the coupling only after Y has dropped below height z0 . For y0 ≤ z0 , let Ly0 ,1+δ be the restriction to (0, ∞) × (0, y0 ] of the lower envelope process associated with P 1+δ , i.e., for t > 0, Ly0 ,1+δ (t) = y0 ∧ L1+δ (t) = y0 ∧ min{y > 0 : (x, y) ∈ P 1+δ for some x ≤ t} (2.3.26) 33 2.3. Analysis of the backbone forward maximum process Let T0 = min{t > 0 : Y (t) ≤ z0 } (2.3.27) Ly0 ,1+δ Then, conditional on Y (T0 ) = y0 , we can couple Y and gous fashion to the coupling in the upper bound, such that Y (t) ≥ Ly0 ,1+δ (t) in an analo- ∀ t ≥ T0 (2.3.28) Next, let T1 = min{x ≥ T0 : (x, y) ∈ P 1+δ for some y < Ly0 ,1+δ (T0 )} (2.3.29) In words, T1 is the first time after T0 that Ly0 ,1+δ (t) jumps. By construction, Ly0 ,1+δ (t) = L1+δ (t) ∀ t ≥ T1 (2.3.30) Combining (2.3.28) and (2.3.30), we find that Y and L1+δ can be coupled so that Y (t) ≥ L1+δ (t) ∀ t ≥ T1 (2.3.31) This is a stochastic upper bound valid for large times, provided that T1 = T1 (T0 ) < ∞ a.s. For this to be true it suffices that T0 < ∞ a.s. The latter is evidently true, because q is bounded away from 0 outside any neighbourhood of z = 0, implying that Y tends to 0, a.s. Sandwich: For all k ∈ N, (kL(kt))t>0 has the same distribution as (L(t))t>0 , 1 L(t))t>0 . Combined with and (L1+δ (t))t>0 has the same distribution as ( 1+δ (2.3.25) and (2.3.31), this implies that Y and L can be coupled so that 1 L(t) ≤ k Y (kt) ≤ L(t) 1+δ ∀ k ≥ K, uniformly in t ≥ ε (2.3.32) where K = K(δ, ε) is some finite random variable. Now let δ ↓ 0, to get the claim in (2.3.20). Proof of (2.3.21): Fix γ > 0. Let N denote the law of N . By the strong law of large numbers, we have N (kt) ∈ [(1 − γ)kt, (1 + γ)kt] ∀ k ≥ K, uniformly in t ≥ ε, N –a.s., (2.3.33) where K = K(γ, ε) is some finite random variable. Because Y is a decreasing process, it follows from (2.3.19) and (2.3.33) that kY kt ∈ k Y ((1 + γ)kt), k Y ((1 − γ)kt) ∀ k ≥ K uniformly in t ≥ ε, P × N –a.s. (2.3.34) 34 2.3. Analysis of the backbone forward maximum process Combining (2.3.32) and (2.3.34), we find that there is a K = K (γ, δ, ε) such that Y and L can be coupled so that 1 1 L(t) ≤ kY 1+δ 1+γ kt ≤ 1 L(t) 1−γ ∀ k ≥ K , uniformly in t ≥ ε (2.3.35) Now let δ, γ ↓ 0, to get the claim in (2.3.21). Corollary 2.3.1. For any ε > 0, k[1 − σ W kt ] ∗ t≥ε as k → ∞ =⇒ (L(t))t≥ε (2.3.36) Proof. By Lemma 2.3.2, Wk ↓ pc as k → ∞, P–a.s., so (2.3.36) is immediate from (2.2.12) and (2.3.18). 2.3.3 Multivariate Laplace transform of the Poisson lower envelope Recall the definition of the L-process in (2.1.19). The following lemma gives its multivariate Laplace transform. Lemma 2.3.4. For any n ∈ N, τ1 , . . . , τn ≥ 0 and 0 ≤ t1 < · · · < tn , n n τi ti + si (2.3.37) I = {1 ≤ i < n : L(ti+1 ) < L(ti )} (2.3.38) E exp − τi L(ti ) i=1 with si = 1− = i=1 i j=1 τj . Proof. Let We split the contribution according to the outcome of I. To that end, fix 0 ≤ m ≤ n − 1 and A = {a1 , . . . , am } with 1 ≤ a1 < · · · < am ≤ n − 1. Put a0 = 0 and am+1 = n. On the event {I = A}, there are u1 > u2 > · · · > um > um+1 > 0 such that ∀ j = 1, . . . , m + 1 : L(ti ) ∈ (uj , uj + duj ] for aj−1 < i ≤ aj (2.3.39) In terms of the Poisson process P, this is the same as the event ∀ j = 1, . . . , m + 1 : P ∩ (taj−1 , taj ] × (0, uj ] = ∅ P ∩ (taj−1 , taj−1 +1 ] × (uj , uj + duj ] = ∅ (2.3.40) 35 2.3. Analysis of the backbone forward maximum process where we put t0 = 0. The latter event has probability m+1 e−uj (taj −taj−1 ) (taj−1 +1 − taj−1 ) duj (2.3.41) j=1 Furthermore, on this event we have n m+1 uj (saj − saj−1 ) τi L(ti ) = i=1 (2.3.42) j=1 where we put s0 = 0. Therefore we obtain n E exp − τi L(ti ) 1{I=A} i=1 m+1 ∞ = 0 j=1 duj 1{u1 >u2 >···>um >um+1 } (2.3.43) m+1 (taj−1 +1 − taj−1 ) e−uj [(taj −taj−1 )+(saj −saj−1 )] × j=1 It is straightforward to perform the integrals in (2.3.43) in the order j = 1, . . . , m + 1, noting that the exponent telescopes, to get m+1 j=1 (taj−1 +1 − taj−1 ) (taj − ta0 ) + (saj − sa0 ) (2.3.44) Since a0 = 0, t0 = 0 and s0 = 0, this gives the formula n E exp − m+1 τi L(ti ) 1{I=A} = i=1 j=1 = taj−1 +1 − taj−1 taj + saj t1 tn + sn i∈A ti+1 − ti ti + si (2.3.45) with the empty product equal to 1. Finally, we sum over A and use that A i∈A ti+1 − ti = ti + si n−1 ti+1 − ti 1+ ti + si i=1 to arrive at n E exp − = i=1 n τi L(ti ) i=1 n−1 = i=1 ti+1 + si ti + si ti + si−1 ti + si (2.3.46) (2.3.47) which is the formula in (2.3.37). 36 2.4. Proof of Theorem 2.1.3 and Corollary 2.1.4 2.4 Proof of Theorem 2.1.3 and Corollary 2.1.4 Proof of Theorem 2.1.3. For fixed x, and for w, v ∈ N (x) with w ≤ v, let Nwv denote the number of edges in the connected component of w in the subgraph of S(x) that is obtained by removing all the edges in the path from o to v (see Figure 2.2). Pick y ∈ ∂S(x), and let v ∈ N (x)\{o} be the first node above the parent of y, and let 0 < k ≤ nv be the distance from v− to the parent of y. Then the event {x ∈ C} ∩ By amounts to the following: (1) The backbone runs from o to v− , runs up a height k along the segment between v− and v, and then moves to y; (2) for all w ∈ N (x) with w < v, Nwv invaded edges are connected to the backbone at height w ; (3) Nvv + (nv − k) invaded edges are connected to the backbone at height v− + k. Therefore P(x ∈ C, By | W ) = 1 σ v− +k+1 W v Nw w w∈N (x) W Nvv +(nv −k) v− +k w<v (2.4.1) where the three factors correspond to (1)–(3), and Proposition 2.2.1 and Lemma 2.2.2 are used to determine the probabilities of (2) and (3). Taking the average over W and using the relation Nwv + (nv − k) = N v− + k + (2.4.2) w≤v we obtain σ N +1 P(x ∈ C, By ) = E σW v Nw w σW Nvv +(nv −k) v− +k w∈N (x) w<v (2.4.3) Since, by assumption, S(x) does not branch at o, we have Nov = 0, and so the factor with w = o may be dropped. We next apply Corollary 2.3.1 in combination with the scaling limit defined by (2.1.8)–(2.1.9). To that end, we define w Nv k nv , nvw (N ) = w , s(N ) = , tv (N ) = N N N N N Zh (N ) = N [1 − σ WhN ], fN (x) = (1 − x/N ) 1[0,N ] (x) hw (N ) = (2.4.4) 37 2.4. Proof of Theorem 2.1.3 and Corollary 2.1.4 and rewrite the right-hand side of (2.4.3) as fN Zhw (N ) (N ) E nvw (N ) w∈N (x) o<w<v · fN Zhv− (N )+s(N ) (N ) nvv (N )+[tv (N )−s(N )] (2.4.5) Under the limit limN →∞ , there are hw , nvw , s and tv such that nvw (N ) → nvw , hw (N ) → hw , s(N ) → s, tv (N ) → tv (2.4.6) and, by Corollary 2.3.1, (Zhw (N ) (N ))o<w<v , Zhv− (N )+s(N ) (N ) =⇒ (L(hw ))o<w<v , L(hv− + s) (2.4.7) provided we assume that s > 0 when v− = o. This last assumption (which will be removed below) is needed here because Corollary 2.3.1 only applies for positive scaling heights. Let f (x) = exp(−x), x ∈ (0, ∞). Since fN converges to f as N → ∞ uniformly on (0, ∞), and since f is bounded and continuous on (0, ∞), it follows from (2.4.5)–(2.4.7) that lim σ N +1 P(x ∈ C, By ) N →∞ v [f (L(hw ))]nw = E f L(hv− + s) [nvv +(tv −s)] w∈N o<w<v (2.4.8) nvw L(hw ) − [nvv + (tv − s)]L(hv− + s) = E exp − w∈N o<w<v where N is the set of nodes in the scaled spanning tree S (defined above Theorem 2.1.3). Next, we use Lemma 2.3.4 to obtain v nw N +1 1 − [nvv + (tv − s)] lim σ P(x ∈ C, By ) = 1− v N →∞ m w w∈N o<w<v (2.4.9) where we recall the definition of in (2.1.10), and use the relations hw + v = mv and h v v n + s + v− w o<u≤w u o<w≤v− nw + nv + (tv − s) = 1 (by mvw 38 2.5. Cluster size at a given height (2.4.2) with Nov = 0). Finally, we note that mvw − nvw = tw + mvw− and 1 − (nvv + tv ) = mvv− , to obtain the formula in (2.1.11). It is easy to remove the restriction that s > 0 when v− = o. Indeed, the right-hand side of (2.4.3) is increasing in k, because Wl is increasing in l. Therefore we can include the case s = 0 via a monotone limit. Proof of Corollary 2.1.4. In the limit as N → ∞, the sum over 0 < k ≤ nv may be replaced by an integral over s ∈ [0, tv ] for all v ∈ N \{o}, by using the monotonicity in k noted above. v Remark. If S(x) branches at o, then the factor [σ W0 ]No in (2.4.3) is not 1. In fact, it tends to zero as N → ∞, P–a.s., because σ W0 is a random variable on (0, 1) while Nov ∼ nvo N → ∞ since nvo > 0. Thus the right-hand side of (2.4.3) tends to zero in this case. 2.5 Cluster size at a given height In this section, we prove Theorem 2.1.5. The cluster size at height n consists of the contributions at height n from branches leaving the backbone at height k, for all 0 ≤ k < n, plus the single backbone vertex at height n. This leads us, in Section 2.5.1, to first analyse the Laplace transform of Co [m], which is the contribution to the cluster at height m from a single branch from the root, in independent bond percolation with parameter p. Section 2.5.2 then uses this Laplace transform to provide the proof of Theorem 2.1.5, while Section 2.5.3 computes the first and second moment in the scaling limit. 2.5.1 Laplace transform of Co [m] For m ∈ N, let Co [m] denote the number of vertices in the cluster of o at height m, via a fixed branch from o, in independent bond percolation with parameter p ≤ pc = 1/σ. For τ ≥ 0, let fm (p; τ ) = Ep e−τ Co [m] (2.5.1) By conditioning on the occupation status of the edge leaving the root, we see that Co [m+1] is 0 with probability 1−p and is the sum of σ independent copies of Co [m] with probability p. Therefore fm obeys the recursion relation fm+1 (p; τ ) = 1 − p + p [fm (p; τ )]σ , f1 (p; τ ) = 1 − p + pe−τ (2.5.2) We set f0 (p; τ ) = e−τ /σ , so that the recursion in (2.5.2) holds for m = 0 as well. 39 2.5. Cluster size at a given height Let gm (p; τ ) = 1 − fm (p; τ ) and ρ = σ−1 2σ . Our goal is to determine the asymptotic behaviour of gm (p; τ ) for small τ and for p near pc . To emphasize the latter, we sometimes write p = σ1 (1 − δ). However, we usually suppress the arguments p and τ . In terms of gm , the recursion reads gm+1 = F (gm ), g0 = 1 − e−τ /σ (2.5.3) with F (x) = p[1 − (1 − x)σ ] for x ∈ [0, 1] (2.5.4) We will first show that the sequence (gm )m∈N0 is close to the sequence (gm )m∈N0 that satisfies the quadratic recursion gm+1 = F (gm ), g0 = g0 (2.5.5) where F (x) is the second-order approximation of F (x), namely, F (x) = pσ x − σ−1 2 x 2 for x ∈ [0, 1] (2.5.6) After that we will show that the sequence (gm )m∈N0 is close to the sequence (g(m))m∈N0 , where g(t) satisfies the differential equation g (t) = F (g(t)) − g(t), g(0) = g0 (2.5.7) The differential equation (2.5.7) is easily solved, as follows. We abbrevi1 ate q = 1−δ δ ρσ, where p = σ (1 − δ), and rewrite (2.5.7) as 1 q − g 1 + qg g = −δ (2.5.8) This may be integrated to give g(t) g0 = e−δt 1 + qg(t) 1 + qg0 or g(t) = g0 e−δt 1 + qg0 [1 − e−δt ] (2.5.9) The following lemma bounds the difference between gm and g(m). Lemma 2.5.1. For m ∈ N0 , p ≤ pc and τ ≥ 0, − 1 σ 1 δτ + τ 2 2 ≤ gm (p; τ ) − g(m) ≤ 1 mτ 3 6σ (2.5.10) with g(m) given by (2.5.9). 40 2.5. Cluster size at a given height Proof. We will prove the sandwiches 0 ≤ gm − gm ≤ and 0 ≤ g(m) − gm ≤ 1 mτ 3 6σ 1 σ 1 δτ + τ 2 2 (2.5.11) (2.5.12) which together give the lemma. We begin with (2.5.11). Since 0 ≤ F (x) ≤ pσ 3 ≤ σ 2 , it follows from a third-order Taylor expansion that 1 0 ≤ F (x) − F (x) ≤ σ 2 x3 6 for x ∈ [0, 1] (2.5.13) Moreover, F (0) = F (0) = 0, 0 ≤ F (x) ≤ 1, and F (x) ≤ 1, so 0 ≤ F (x) ≤ x and F (x) ≤ x for all x ∈ [0, 1], and hence gm , gm and g(t) are all decreasing. Write gm+1 − gm+1 = [F (gm ) − F (gm )] + [F (gm ) − F (gm )] (2.5.14) If gm ≥ gm , then F (gm ) − F (gm ) ≥ 0 by the monotonicity of F , while F (gm ) − F (gm ) ≥ 0 because F ≥ F , and so gm+1 ≥ gm+1 . Since g0 = g0 , it follows inductively that gm ≥ gm ∀ m ∈ N0 (2.5.15) Moreover, F (gm )−F (gm ) ≤ gm −gm because F ≤ 1, while F (gm )− F (gm ) ≤ 1 2 3 1 2 3 6 σ gm by (2.5.13). Therefore gm+1 − gm+1 ≤ gm − gm + 6 σ gm . Since gm is decreasing and g0 = g0 ≤ τ /σ, this yields (2.5.11). Next we prove (2.5.12). Define F (x) = h(1), where h = hx is the solution of h (t) = F (h(t)) − h(t), h(0) = x (2.5.16) According to (2.5.7), we have g(m + 1) = F (g(m)) (2.5.17) Since F (x) ≤ x, the solution of (2.5.16) is decreasing, and therefore the function F is increasing. Now, 1 h(1) − h(0) = dt [F (h(t)) − h(t)] (2.5.18) 0 41 2.5. Cluster size at a given height and so, h(t) and F (x) − x both being decreasing, we have F (h(0)) − h(0) ≤ h(1) − h(0) ≤ F (h(1)) − h(1) (2.5.19) Since h(1) = F (h(0)), the lower bound in (2.5.19) with h(0) = x gives F (x) ≥ F (x). With g(0) = g0 , because of (2.5.5) and (2.5.17) and the fact that F is increasing, the latter inductively implies that g(m) ≥ gm ∀ m ∈ N0 (2.5.20) Using the upper bound in (2.5.19) with h(0) = g(k − 1) and h(1) = g(k), and once more that F (x) − x is decreasing in combination with (2.5.20), we get g(k) − g(k − 1) ≤ F (g(k)) − g(k) ≤ F (gk ) − gk = gk+1 − gk (2.5.21) Summing (2.5.21) from k = 1 to k = m − 1, we obtain g(m − 1) − g(0) ≤ gm − g1 . Since g(m) ≤ g(m − 1), g˜(0) = g0 and g1 = F (g0 ) = F (g0 ), this yields the sandwich 0 ≤ g(m) − gm ≤ g0 − F (g0 ) ≤ 1 σ 1 δτ + τ 2 2 (2.5.22) where the last inequality is for p = σ1 (1 − δ) and uses g0 ≤ τ /σ. This proves (2.5.12). 2.5.2 Proof of Theorem 2.1.5 Let Ck,j [n] denote the contribution to the cluster size at height n due to the j th of the σ − 1 branches emerging from height k on the backbone. Then σ−1 C[n] = 1 + n−1 k=0 j=1 Ck,j [n], with the additional 1 due to the backbone vertex at level n. We note that, conditional on W = (Wk )k∈N0 , the different clusters are all independent, and Ck,j [n] depends on W only through Wk . According to Proposition 2.2.1 and Lemma 2.2.2, each cluster emerging from the backbone at height k is a subcritical cluster with parameter p = Wk . Thus τ − ρn Ck,j [n] E e τ ρn for k = 0, . . . , n − 1; j = 1, . . . , σ − 1; and τ ≥ 0 (2.5.23) |W = fn−k Wk ; 42 2.5. Cluster size at a given height with fm (p; τ ) as defined in (2.5.1). Consequently, E e −τ Γn |W =E e τ − ρn C[n] τ − ρn |W σ−1 n−1 =e fn−k k=0 τ − ρn =e τ Wk ; ρn n−1 exp (σ − 1) log 1 − gn−k Wk ; k=0 τ ρn (2.5.24) Note that, compared to Section 2.5.1, the argument τ has now become τ /ρn. Fix τ ≥ 0. Fix ε > 0 and, for notational simplicity, assume that εn is integer. Since gn−k ≤ g0 ≤ τ /σρn, bounding the first εn + 1 and the last εn − 1 terms in the sum individually and using a linear approximation of the logarithm for the remaining terms, we get E e−τ Γn | W = exp −Snε (τ, W ) + O ετ + with Snε (τ, W ) = (σ − 1) gn−k Wk ; εn<k≤n−εn τ2 n τ ρn Next, for t ∈ [ε, 1 − ε], put k = nt and Znt = n[1 − σ W Gtn (x) = (σ − 1) n g 1 x τ 1− ; σ n ρn n(1−t) (2.5.25) (2.5.26) nt 1[0,n] (x) ], and define for x ∈ (0, ∞) (2.5.27) Then we may write (2.5.26) as 1−ε Snε (τ, W ) = dt Gtn (Znt ) (2.5.28) ε Applying Lemma 2.5.1, after some arithmetic we find that for x ∈ [0, n] and n → ∞, Gtn (x) = 1 + O +O Put Gt (x) = 2τ τ n 2τ xe−(1−t)x −(1−t)x ] x + [1 + O( x+τ n )] τ [1 − e xτ + τ 2 + τ 3 n xe−(1−t)x x + τ [1 − e−(1−t)x ] for x ∈ (0, ∞) (2.5.29) (2.5.30) 43 2.5. Cluster size at a given height Note that Gt ≤ 2τ and that limx→∞ Gt (x) = 0 uniformly in t ∈ [ε, 1 − ε]. Also, it follows from the fact that fm (p; τ ) is decreasing in p that Gtn (x) is decreasing in x. It is clear from (2.5.29) that Gtn (x) → Gt (x) uniformly in √ √ x ∈ (0, n] and t ∈ (ε, 1 − ε). For x > n, the difference |Gtn (x) − Gt (x)| √ is bounded above by Gtn ( n) + Gt (x), which also goes to zero uniformly in √ x > n and t ∈ (ε, 1 − ε). We therefore see that Gtn (x) converges to Gt (x) as n → ∞, uniformly in x ∈ (0, ∞) and t ∈ [ε, 1 − ε]. Consequently, 1−ε lim n→∞ ε dt [Gtn (Znt ) − Gt (Znt )] = 0 (2.5.31) P–a.s. ∗ Moreover, we know from Corollary 2.3.1 that (Znt )t∈[ε,1−ε] =⇒ (L(t))t∈[ε,1−ε] 1−ε as n → ∞. Since (z(t))t∈[ε,1−ε] → ε dt Gt (z(t)) is bounded and continuous in the Skorohod topology, we therefore have 1−ε 1−ε dt Gt (Znt ) =⇒ ε dt Gt (L(t)) as n → ∞ (2.5.32) ε Combining (2.5.28), (2.5.31) and (2.5.32), we obtain 1−ε Snε (τ, W ) =⇒ dt Gt (L(t)) as n → ∞ (2.5.33) ε We substitute (2.5.33) into (2.5.25), and let n → ∞ followed by ε ↓ 0, to get 1 lim E e−τ Γn = E exp − dt Gt (L(t)) n→∞ ∀τ ≥ 0 (2.5.34) 0 The integral in the right-hand side equals S(τ, L) of (2.1.21), and this proves (2.1.20). 2.5.3 First and second moment In this section we prove (2.1.22). Differentiation of (2.1.21) gives E(Γ) = E ∂S (0, L) ∂τ 1 =E 2 e−(1−t)L(t) dt 1 =2 0 t dt = 1 (2.5.35) 0 where the third equality uses Lemma 2.3.4. Similarly, E(Γ2 ) = I + II (2.5.36) 44 2.5. Cluster size at a given height with I=E ∂S (0, L) ∂τ 2 1 =E 4 1 dt 0 ds e−(1−t)L(t) e−(1−s)L(s) 0 1 1 dt =E 8 ds e−(1−t)L(t) e−(1−s)L(s) t 0 1 1 1−t+s 2−t t 0 1 1 20 t (2 − t) − dt = =4 − 8 log 2 2−t 3 0 (2.5.37) ds t dt =8 and II = E − ∂2S (0, L) ∂τ 2 1 =E 4 0 dt −(1−t)L(t) 1 − e−(1−t)L(t) e L(t) 1 =E 4 1 dt 0 t 1 =4 1 dt 0 ds e−(2−t−s)L(t) ds t t = 8 log 2 − 5 2−s (2.5.38) Summing, we get E(Γ2 ) = I + II = 35 . It remains to prove that E(Γn ) → E(Γ) and E(Γ2n ) → E(Γ2 ) as n → ∞. By (2.1.15), we have P(x ∈ C) = [1 + o(1)] σ n × σ −(n+1) (σ − 1)n E(C[n]) = x : x =n 1 (2.5.39) 2 and hence 2σ 1 E(C[n]) = 1 (2.5.40) σ−1 n A similar argument applies for the second moment. Indeed, for n1 , n2 → ∞ lim E(Γn ) = lim n→∞ n→∞ 45 2.6. Cluster size below a given height with n2 ≥ n1 , we write P(x1 , x2 ∈ C) E(C[n1 ]C[n2 ]) = x1 : x1 =n1 x2 : x2 =n2 n1 −1 σ k × σ n1 −k × (σ − 1) σ n2 −k−1 = [1 + o(1)] ×σ k=0 −[k+(n1 −k)+(n2 −k)+1] (σ − 1)[k + (n1 − k) + (n2 − k)] n1 − k n2 − k + n2 n1 (2.5.41) where the terms with o, x1 , x2 all on a single path have been absorbed into the error term, and where we have split the sum according to the height k of the most recent common ancestor of x1 and x2 , counted the number of configurations with fixed k, and inserted the asymptotic formula in (2.1.17). For a ∈ (0, 1], this gives × n1 k 1 k + (n1 − k) + (n2 − k) 2 lim E(Γn1 Γn2 ) = ,n →∞ 2 n1 /n2 →a lim ,n →∞ n1 2 n1 /n2 →a 1 = 2a 2σ σ−1 2 1+ 1 E(C[n1 ]C[n2 ]) n1 n2 dt t 1 + a(1 − t) + (a−1 − t) (2.5.42) 0 = 1 + 31 a(1 + a) 1 while for a = 0 the limit is 2 0 dt t = 1. This proves (2.1.26), and with a = 1 also limn→∞ E(Γ2n ) = 53 . This completes the proof of (2.1.22). 2.6 Cluster size below a given height In this section, we prove Theorem 2.1.6. The arguments and notations mirror those in Section 2.5. We re-use the names of the functions in Section 2.5 for new functions here. 2.6.1 Laplace transform of Co [1, m] For m ∈ N, let Co [1, m] denote the number of vertices in the cluster of o at all heights from 1 to m, via a fixed branch from o, in independent bond percolation with parameter p ≤ pc = 1/σ. For τ ≥ 0, let fm (p; τ ) = Ep e−τ Co [1,m] (2.6.1) 46 2.6. Cluster size below a given height By conditioning on the occupation status of the edge leaving the root, we see that Co [1, m + 1] is 0 with probability 1 − p and is 1 plus the sum of σ independent copies of Co [1, m] with probability p. Therefore fm obeys the recursion relation fm+1 (p; τ ) = 1 − p + pe−τ [fm (p; τ )]σ , f0 (p; τ ) = 1 (2.6.2) As before, let gm (p; τ ) = 1 − fm (p; τ ) and ρ = σ−1 2σ . We again suppress the arguments p and τ . In terms of gm , the recursion reads gm+1 = F (gm ), g0 = 0 (2.6.3) with F (x) = p[1 − e−τ (1 − x)σ ] for x ∈ [0, 1] (2.6.4) We will compare gm with the solution of the quadratic recursion gm+1 = F (gm ), g0 = 0 (2.6.5) where F (x) is the second-order approximation of F (x). Thus 1 F (x) = p(1 − e−τ ) + αx − βx2 2 for x ∈ [0, 1] (2.6.6) where we abbreviate α = pσe−τ and β = (σ − 1)α; note that α ∈ [0, 1]. We will compare gm in turn with the solution of the quadratic differential equation g (t) = F (g(t)) − g(t), g(0) = 0 (2.6.7) The differential equation (2.6.7) is easily solved, as follows. By applying the linear transformation y(t) = (1 − α) + βg(t) (2.6.8) we can write (2.6.7) as y (t) = 12 [D2 − y(t)2 ], where D= (1 − α)2 + 2βp(1 − e−τ ) (2.6.9) This can be rewritten as 1 1 + D + y(t) D − y(t) y (t) = D (2.6.10) and then integrated to give D + y(t) D + y(0) Dt = e D − y(t) D − y(0) or y(t) = D CeDt − 1 CeDt + 1 (2.6.11) 47 2.6. Cluster size below a given height with C= D + y(0) , D − y(0) y(0) = 1 − α (2.6.12) Thus g(m) = 1 CeDm − 1 1 [y(m) − (1 − α)] = D − (1 − α) β β CeDm + 1 (2.6.13) Lemma 2.6.1. For m ∈ N0 , p ≤ pc and τ ≥ 0, g(m) ≤ gm (p; τ ) ≤ g(m) + τ + m4 τ 3 (2.6.14) with g(m) given by (2.6.13), (2.6.9) and (2.6.12). Remark. For τ 1 and p ∼ pc the approximation by g(m) is in fact much better than stated in the lemma, though the upper bound above is sufficient for our needs. Proof. The proof closely follows that of Lemma 2.5.1, but with some reversals of monotonicity. We will prove the sandwiches 0 ≤ gm − gm ≤ m4 τ 3 (2.6.15) 0 ≤ gm − g(m) ≤ τ (2.6.16) and which together give the lemma. We begin with (2.6.15). Since 0 ≤ F (x) ≤ ασ 2 ≤ σ 2 , we have 1 0 ≤ F (x) − F (x) ≤ σ 2 x3 6 ∀x ∈ [0, 1] (2.6.17) Moreover, F (0) = F (0) = p(1 − e−τ ), 0 ≤ F (x) ≤ α, and F (x) ≤ α, so 0 ≤ F (x) − F (0) ≤ αx, F (x) − F (0) ≤ αx (2.6.18) As in (2.5.14)–(2.5.15), this inductively yields gm ≥ gm ∀m ∈ N0 . (2.6.19) In addition, F (x) ≤ x + pτ and g0 = 0, and therefore gm ≤ mpτ ≤ mτ σ ∀m ∈ N0 (2.6.20) 48 2.6. Cluster size below a given height It then follows from F ≤ 1, (2.6.17) and (2.6.19)–(2.6.20) that gm+1 − gm+1 = F (gm ) − F (gm ) + F (gm ) − F (gm ) 1 1 3 3 3 ≤ (gm − gm ) + σ 2 gm ≤ (gm − gm ) + m τ 6 6σ (2.6.21) which yields (2.6.15). Next we prove (2.6.16). Let F (x) = hx (1), where hx is the solution of h (t) = F (h(t)) − h(t), h(0) = x (2.6.22) According to (2.6.7), we have g(m + 1) = F (g(m)) (2.6.23) Let x∗ = [D − (1 − α)]/β ≥ 0 with D defined in (2.6.9), and note that F (x) ≥ x for x ∈ [0, x∗ ]. Therefore solutions of (2.6.22) with h(0) ∈ [0, x∗ ] are increasing on [0, ∞), and the function F is increasing. Henceforth we will assume the restriction x ∈ [0, x∗ ]. Now, 1 h(1) − h(0) = dt [F (h(t)) − h(t)] (2.6.24) 0 and so, h being increasing and F (x) − x decreasing, we have F (h(1)) − h(1) ≤ h(1) − h(0) ≤ F (h(0)) − h(0) (2.6.25) Since h(1) = F (h(0)), the upper bound with h(0) = x gives F (x) ≥ F (x). Since F is increasing, this inductively implies gm ≥ g(m) ∀m ∈ N0 (2.6.26) Also, gk+1 − gk = F (gk ) − gk ≤ F (g(k)) − g(k) ≤ g(k) − g(k − 1) (2.6.27) where the first inequality follows from the fact that F (x) − x is decreasing, and the second inequality follows from the lower bound of (2.6.25) with h(0) = g(k − 1) and h(1) = g(k). Summing (2.6.27) from k = 1 to k = m − 1, we obtain gm − g1 ≤ g(m − 1) − g(0). Since g(m − 1) ≤ g(m), g˜(0) = g0 = 0 and g1 = F (g0 ) = F (0), this yields (2.6.16). 49 2.6. Cluster size below a given height 2.6.2 Proof of Theorem 2.1.5 For k = 0, . . . , n − 1, let Ck,j [k + 1, n] denote the contribution to the cluster size between heights k+1 and n due to the j th of the σ−1 branches emerging σ−1 from the backbone at height k. Then C[0, n] = n + 1 + n−1 k=0 j=1 Ck,j [k + 1, n], with the additional n + 1 due to the backbone vertices. Conditional on W = (Wk )k∈N0 , the Ck,j [k + 1, n] are all independent. As in (2.5.23), E e−τ Ck,j [k+1,n] | W = fn−k (Wk ; τ ) k = 0, . . . , n − 1; j = 1, . . . , σ − 1; τ ≥ 0 (2.6.28) with fm (p; τ ) as defined in (2.6.1). Consequently, since Γn = f0 = 1, n −τ Γn E e |W =e −τ (n+1)/ρn2 fn−k k=0 n 2 = e−τ (n+1)/ρn exp (σ − 1) 1 C[0, n] ρn2 and σ−1 τ Wk ; 2 ρn log 1 − gn−k Wk ; k=0 τ ρn2 (2.6.29) 2 Note that the prefactor e−τ (n+1)/ρn is equal to 1 + O(1/n). Fix ε > 0 and τ ≥ 0. Since, by (2.6.20), 0 ≤ gn−k ≤ (n − k) τ τ ≤O ρ2 n2 n (2.6.30) we may linearize the logarithm and disregard the first εn + 1 and the last εn terms, to get E e−τ Γn | W 2 = e−τ (n+1)/ρn exp −Snε (τ, W ) + O ετ + with Snε (τ, W ) = (σ − 1) gn−k Wk ; εn<k≤n−εn τ ρn2 Next, for t ∈ [ε, 1 − ε], put k = nt and Znt = n[1 − σ W Gtn (x) = (σ − 1) n g n(1−t) 1 x τ 1− ; 2 σ n ρn 1[0,n] (x) τ2 n (2.6.31) (2.6.32) nt ], and define for x ∈ (0, ∞) (2.6.33) 50 2.6. Cluster size below a given height Then we may write (2.6.32) as 1−ε dt Gtn (Znt ) Snε (τ, W ) = (2.6.34) ε Now we apply Lemma 2.6.1, noting that n(1 − α) = x + O( nτ ), to obtain Gtn (x) = nD CenD(1−t) − 1 −x CenD(1−t) + 1 1+O x τ + 2 n n +O τ + τ3 n (2.6.35) as n → ∞ and for x ∈ [0, n], with nD + x x2 + 4τ + O( nτ ), C= + O( nτ ) nD − x √ Let κ ¯=κ ¯ (τ, x) = x2 + 4τ , and put nD = t G (x) = κ ¯ κ ¯ +x κ ¯ −x κ ¯ +x κ ¯ −x e(1−t)¯κ − 1 e(1−t)¯κ +1 −x= 4τ x+κ ¯ coth[ 12 (1 − t)¯ κ] (2.6.36) for x ∈ (0, ∞) (2.6.37) Note that Gt (x) ≤ Gt (0) = 4τ and that limx→∞ Gt (x) = 0 uniformly in t ∈ [ε, 1 − ε]. As n → ∞, Gtn (x) converges to Gt (x) uniformly in x ∈ (0, ∞) and t ∈ [ε, 1 − ε]. The reasoning applied in (2.5.30)–(2.5.33) can also be applied here, to conclude that 1−ε Snε (τ, W ) =⇒ dt Gt (L(t)) (2.6.38) ε We substitute (2.6.38) into (2.6.34), and let n → ∞ followed by ε ↓ 0, to get 1 lim E e−τ Γn = E exp − n→∞ dt Gt (L(t)) ∀τ ≥ 0 (2.6.39) 0 Since κ ¯ (τ, L(t)) = κ(τ, t), the integral in the right-hand side equals S(τ, L) of (2.1.24), and this proves (2.1.23). 2.6.3 First and second moment In this section we prove (2.1.25). Taylor expansion up to first order in τ of the integrand in (2.1.24) gives ∂S (0, L) = 2 ∂τ − 1 dt 0 1 ∂2S ∂τ (0, L) = 8 2 dt 0 1 1 − e−(1−t)L(t) L(t) 1 1 − t −(1−t)L(t) 1 − e−2(1−t)L(t) − e 2L(t)3 L(t)2 (2.6.40) 51 2.6. Cluster size below a given height Hence, applying Lemma 2.3.4 for the fourth equality, we have ∂S (0, L) ∂τ E(Γ) = E 1 1 1 − e−(1−t)L(t) L(t) dt E =2 0 1 1 dt =2 (2.6.41) ds E e−(1−s)L(t) t 0 1 =2 1 dt 0 ds t t 1 = t+1−s 2 Also, as in (2.5.36)–(2.5.38), we have E(Γ2 ) = I + II with 2 ∂S ∂2S I = E (0, L) , II = E − 2 (0, L) ∂τ ∂τ (2.6.42) Using Lemma 2.3.4, we compute 1 I=E 1 2 dt 0 t 1 1 dt1 =8 t1 1 1 dt1 0 1 = 1 dt2 t1 1 ds1 t1 1 ds2 t2 dt2 t1 t1 t2 + (1 − s1 ) t1 + (1 − s1 ) t2 + (1 − s1 ) + (1 − s2 ) 2 − s1 t1 [t2 + (1 − s1 )] log t1 + (1 − s1 ) t2 + (1 − s1 ) ds1 t1 [t1 + (1 − s1 )] 4 log[t1 + (1 − s1 )] − 4 log(2 − s1 ) − 2 dt1 0 1 ds1 0 =8 2 ds e−(1−s)L(t) t1 1 +2 1 dt1 0 ds1 t1 t1 (2 − s1 )2 t1 + (1 − s1 ) 1 dx 2x3 log x − 2x(1 + x)2 log(1 + x) + = 0 17 8 = − log 2 8 3 13 3 8 2 x + x +x 6 3 (2.6.43) where to get the next to last line we set x = t1 + (1 − s1 ) and interchange the two integrals. For II, we expand the integrand of the second line of (2.6.40) in powers of L(t), take the expectation using that E(L(t)k ) = k!/tk , k ∈ N0 , 52 2.7. Proof of Theorem 2.1.7 and sum out afterwards, to obtain II = E − ∂2S (0, L) ∂τ 2 ∞ 1 dt (1 − t)3 =E 8 0 [−(1 − t)L(t)]k k=0 2k+2 1 − (k + 3)! (k + 2)! 1 1 1 dt 2t(2 − t)2 log(2 − t) − 2t3 log t − t + t2 2 2 0 16 8 = log 2 − 3 9 = Summing, we get E(Γ2 ) = I + II = (2.6.44) 25 72 . To verify that E(Γn ) → E(Γ) and E(Γ2n ) → E(Γ2 ) as n → ∞, we return to (2.5.39)–(2.5.42). Since C[0, n] = 1 + nk=1 C[k] by definition (recall (2.1.2)), it follows from (2.5.40) that limn→∞ E(Γn ) = limn→∞ n12 nk=1 k = 1 1 0 du u = 2 . A similar calculation, based on (2.5.41)–(2.5.42), yields 1 n→∞ n4 n lim E(Γ2n ) = lim n→∞ 1 =2 du 0 =2 du 0 25 18 dv uv lim E(Γ n→∞ u 1 1 = kl E(Γk Γl ) k,l=1 1 dv uv u 1 dv v 3 = 0 un Γ vn ) (2.6.45) 1u u 1+ 1+ 3 v v 25 72 This completes the proof of (2.1.25). 2.7 Proof of Theorem 2.1.7 In this section we prove Theorem 2.1.7. The key ingredient is the following mixing property, which is proved below. (n) Lemma 2.7.1. Let W (n) = (Wk )k∈N0 , n ∈ N, be independent realizations of W . There exists a sequence (kn )n∈N with kn+1 > nkn , n ∈ N, and a coupling of W to W (n) , n ∈ N, such that with probability 1 (n) Wi = Wi for all i with kn ≤ i ≤ nkn , for all but finitely many n (2.7.1) 53 2.7. Proof of Theorem 2.1.7 Proof of Theorem 2.1.7. Let C k [n] denote the number of vertices in C at height n whose most recent ancestor on the backbone is at height at k [n] denote the same quantity for C . Define Γk = least k, and let C∞ ∞ n 1 1 k k k [n]. A small modification of the proofs of (2.1.4) C [n], Γ = C n,∞ ρn ρn ∞ and Theorem 2.1.5 shows that if k = k(n) = o(n) as n → ∞, then Γkn =⇒ Γ as n → ∞ under the law P, and Γkn,∞ =⇒ Γ∞ as n → ∞ under the law P∞ . As different off-backbone branches are conditionally independent given W , it follows from Lemma 2.7.1 that we may couple C with independent realizations of C (n) such that C kn [nkn ] = C (n),kn [nkn ] for all but finitely many n. Let n 1 m for n ∈ N (2.7.2) Sn = Γkmk m n m=1 Under the law P, all but finitely many of the summands are equal to independent random variables that converge in distribution to Γ. Consequently, Sn → E(Γ) a.s. as n → ∞ under P. On the other hand, let Sn,∞ = 1 n n m Γkmk m ,∞ for n ∈ N (2.7.3) m=1 Then, under the law P∞ , the summands are already independent and converge in distribution to Γ∞ , so that Sn,∞ → E∞ (Γ∞ ) a.s. as n → ∞ under P∞ . Since E(Γ) = E∞ (Γ∞ ), it follows that the laws of IPC and IIC are mutually singular. Proof of Lemma 2.7.1. Choose k1 arbitrarily, e.g., k1 = 1. Suppose that k1 , . . . , kn have been chosen inductively such that P(Wnkn < pc + n−2 ) ≥ (m) ) for m > n. We will choose n 1 − n−2 and (Wk )nk k=0 is independent of (W (n+1) kn+1 , and couple (Wk ) and (Wk ) starting at k = nkn + 1, in such a (n+1) way that with high probability we will have Wk = Wk for all k with (n+1) kn+1 ≤ k ≤ (n + 1)kn+1 . We will have no further use for Wk once k > (n + 1)kn+1 . The coupling is achieved as follows. Let k > nkn . We use the same random variables (Xk ) for both processes (recall (2.3.13)). Since R is in(n+1) creasing, we can couple the two processes such that if Wk ≤ Wk and Wk (n+1) (n+1) (n+1) jumps down, then so does Wk , while if Wk ≤ Wk and Wk jumps down, then so does Wk . When such a jump occurs, both processes jump to the same value, and they then remain equal forever afterwards. Let (n+1) Tn = min{k > nkn : (Wk ∧ Wk (n+1) ) < (Wnkn ∧ Wnkn )} (2.7.4) 54 2.8. Proof of Theorems 2.1.8 and 2.1.9 i.e., Tn is the first time after time nkn at which one of the processes jumps below the previous minimum of the two. Since at each step the probability of a jump is bounded away from 0, we have that Tn < ∞ a.s. If the smallervalued process at time Tn − 1 jumps, then both processes jump to the same value, and we say that they coalesce at time Tn . If only the larger-valued process at time Tn − 1 jumps, then we say that a wrong jump occurs at time Tn . Now choose kn+1 such that P(Tn > kn+1 ) ≤ n−2 . By time kn+1 , the event that coalescence has not occurred is contained in the union of the two events: (1) Tn > kn+1 ; (2) the jump at time Tn is a wrong jump. By construction, the probability of (1) is at most n−2 . We will show below that the probability of (2) is at most cn−2 for some constant c. Since −2 < ∞, it follows from the Borel–Cantelli Lemma that with probn∈N n ability 1 these three events occur only finitely often. It remains to estimate the probability of (2). For a pair of coupled processes with values pc + ε and pc + ε with 0 < ε < ε , the probability to coalesce at the next step equals P(Xk+1 < pc +ε)R(pc +ε) ≥ θ(pc +ε)R(pc ) ≥ Cε for some C > 0. Also, the probability of a wrong jump at the next step equals P(Xk+1 < pc + ε)[R(pc + ε ) − R(pc + ε)] ≤ C εε for some C > 0, since the derivative R (p) remains bounded for p near pc . The probability that the jump at time Tn is a wrong jump is the second of these probabilities divided by the sum of the two, and hence is at most C ε /C. Moreover, between times nkn and Tn only the larger-valued process jumps, (n+1) so that pc + ε ≤ Wnkn ∨ Wnkn . Conditional on the event E = {Wnkn ≤ (n+1) pc + n−2 } ∩ {Wnkn ≥ pc + n−2 }, this gives ε ≤ n−2 . On the other hand, P (E c ) ≤ 2n−2 by construction, and this proves the desired bound on the probability of (2). 2.8 Proof of Theorems 2.1.8 and 2.1.9 In this section, we prove Theorem 2.1.9. As mentioned in Section 2.1.3, Theorem 2.1.8 then follows via [5, Example 1.9(ii)]. We retain the terminology of Lemma 2.6.1 and its proof, and begin with two technical estimates. 55 2.8. Proof of Theorems 2.1.8 and 2.1.9 Lemma 2.8.1. There is a c > 0 such that, for p = σ1 (1 − δ), √ D ≥ [1 + o(1)] τ as δ, τ ↓ 0 √ τ ∧ τ for 0 < δ, τ 1 D − (1 − α) ≥ c δ (2.8.1) (2.8.2) Proof. Recall the definition of α, β below (2.6.6). As δ, τ ↓ 0, 1 − α = 1 − (1 − δ)e−τ ∼ δ + τ 2βp(1 − e−τ ) = 4ρ(1 − δ)2 e−τ (1 − e−τ ) ∼ 4ρτ For (2.8.1), we use 4ρ ≥ 1 (recall (2.1.3) with σ ≥ 2) to obtain √ D = (1 − α)2 + 2βp(1 − e−τ ) ≥ [1 + o(1)] τ as δ, τ ↓ 0 (2.8.3) (2.8.4) For (2.8.2), note that D ≤ 2 (δ + τ ) ∨ 4ρτ for 0 < δ, τ 1 (2.8.5) to obtain D − (1 − α) = for 0 < δ, τ D2 − (1 − α)2 τ √ 2βp(1 − e−τ ) ρτ ≥ ≥ ≥c ∧ τ D + (1 − α) 2D D δ (2.8.6) 1. Lemma 2.8.2. There is a c > 0 such that, for n gn 1 (1 − δ); τ σ 1 and τ ≥ n−2 , ≥ c [D − (1 − α)] (2.8.7) Proof. We use Lemma 2.6.1 and the inequalities β < σ and C > 1 (recall (2.6.12)), to estimate gn 1 (1 − δ); τ σ 1 CeDn − 1 D Dn − (1 − α) β Ce + 1 1 2D D − (1 − α) − = β CeDn + 1 D − (1 − α) 2D ≥ 1− σ [D + (1 − α)]eDn D − (1 − α) ≥ 1 − 2e−Dn σ ≥ c [D − (1 − α)] ≥ (2.8.8) where in the last inequality we use (2.8.1), which implies that Dn ≥ [1 + √ o(1)]n τ ≥ [1 + o(1)]. 56 2.8. Proof of Theorems 2.1.8 and 2.1.9 Proof of Theorem 2.1.9. For convenience we restrict ourselves to n divisible by 3, which suffices. Our goal is to get a bound uniform in n for 1 C[0, 3n] 9n2 E ∞ = 9n2 dτ E e−τ C[0,3n] (2.8.9) 0 where the equality follows from Fubini’s Theorem. The contribution to the right-hand side of (2.8.9) due to 0 ≤ τ < n−2 is bounded by 9. Moreover, due to the presence of the backbone, we have C[0, 3n] ≥ 3n + 1, and so ∞ n−1 log n dτ E e−τ C[0,3n] ≤ ∞ dτ e−3nτ = n−1 log n 1 3n4 (2.8.10) Thus it suffices to show that n−1 log n sup n2 n−2 n∈N dτ E e−τ C[0,3n] < ∞ (2.8.11) As in (2.6.29), we have 3n −τ C[0,3n] E e |W ≤ 1 − g3n−k (Wk ; τ ) σ−1 k=0 2n−1 ≤ exp − g3n−k (Wk ; τ ) (2.8.12) k=n where the second inequality uses gm ≥ 0 and σ ≥ 2. We know that gm (p; τ ) is increasing in p and m (because fm (p; τ ) in (2.6.1) is decreasing in p, m). Since Wk is increasing in k, we may therefore estimate 2n−1 g3n−k Wk ; τ ≥ ngn Wn ; τ (2.8.13) k=n Thus, to get (2.8.11), it suffices to show that n−1 log n sup n n∈N 2 n−2 dτ E exp −ngn Wn ; τ <∞ (2.8.14) √ √ Let δn = 1 − σ Wn . By Lemma 2.3.2, P(δn ≥ 1/ n) ≤ exp[−c n] for some c > 0, and so we may restrict the integral in (2.8.14) to the event 57 2.9. Proofs for the incipient infinite cluster √ {δn < 1/ n}. By Lemmas 2.8.1–2.8.2, there is a c > 0 such that, for n sufficiently large to give δn , τ 1, exp −ngn Wn ; τ 1 (1 − δn ); τ σ √ ≤ exp −cn δτn ∧ τ = exp −ngn √ ≤ e−cnτ /δn + e−cn (2.8.15) τ Thus, to get (2.8.14), it suffices to show that ∞ sup n2 n∈N √ dτ E e−cnτ /δn + e−cn τ 0 = 1 sup E (nδn ) + c n∈N ∞ dt e−c √ t <∞ 0 (2.8.16) But, by Lemma 2.3.2, the last supremum is finite, and so the proof is complete. Remark. Note that the IIC corresponds to δn = 0 for √ all n, and that it ∞ follows from [6, Eqn. (2.17)] that the term 0 dt e−c t in (2.8.16) is an upper bound for the corresponding IIC expectation E∞ (n2 /C∞ [0, n]). The additional term in (2.8.16) is a reflection of the fact that the IPC is smaller than the IIC, and the uniform boundedness of the expectation E(nδn ) is consistent with the scaling of the W -process in Corollary 2.3.1. 2.9 Proofs for the incipient infinite cluster In this section, we give quick proofs of the statements made in Section 2.1.2. Proof. First we look at the structural representation of C∞ under the law P∞ . After that we turn to the r-point function and to the cluster size at and below a given height. Structural representation. Let {o → n} denote the event that the root is connected to a vertex that is distance n from the root. The law P∞ is defined as the limit P∞ (E) = lim Ppc (E | o → n) n→∞ ∀ cylinder event E (2.9.1) Let a1 , . . . , aσ denote the neighbours of o. Then Ppc (E | o → n) = 1 σ o Ppc (E | o → ai , ai → n) + O 1≤i≤σ 1 n (2.9.2) 58 2.9. Proofs for the incipient infinite cluster o where → means a connection avoiding o, and the error term covers the case of two or more disjoint connections from o to n. Suppose that E is an elementary event, i.e., E determines the state of all the edges it depends on. Let Ti denote the ith branch of Tσ from o, Ei the restriction of E to Ti , and Pipc the critical percolation measure on Ti . Then E = ⊗σi=1 Ei and o Ppc (E | o → ai , ai → n) = 1≤j≤σ i Pjpc (Ej ) Ppc (Ei | 0 → ai → n) (2.9.3) j=i Now let n → ∞ and use that the last factor tends to Pi∞ (Ei ), which is defined as the law on Ti under which the edge between o and ai is open and from ai there is an IIC. Then, using (2.9.2), we obtain P∞ (E) = 1 σ 1≤i≤σ 1≤j≤σ i Pjpc (Ej ) P∞ (Ei ) (2.9.4) j=i What this equation says is that the IIC can be grown recursively by opening a random edge, putting critical percolation clusters in the branches emerging from the bottom of this edge, and proceeding to grow from the top of this edge. Proof of (2.1.1). Pick y ∈ ∂S(x) and recall that By is the event that y is in the backbone. We have P∞ (By ) = σ − y P∞ (x ∈ C∞ | By ) = σ −(N − y +1) (2.9.5) Indeed, the first line comes from the fact that the backbone is uniformly random, while the second line uses that S(x) has N − y + 1 edges off the path from o to y. We multiply the two equations in (2.9.5), sum over y, and use that the cardinality of ∂S(x) is N (σ − 1) + σ, to get the first line of (2.1.1). Then we divide the product by the sum, to get the second line of (2.1.1). Proof of (2.1.4)–(2.1.5). In view of Proposition 2.2.1, Lemma 2.2.2 and Proposition 2.3.3, the IIC corresponds to taking the limit when L ≡ 0. In this case S(τ, L) in (2.1.21) reduces to 1 S∞ (τ ) = 2τ dt 0 1 = 2 log (1 + τ ) 1 + τ (1 − t) (2.9.6) 59 2.9. Proofs for the incipient infinite cluster Hence we get E∞ e−τ Γ = e−S∞ (τ ) = (1 + τ )−2 (2.9.7) Similarly, S(τ, L) in (2.1.24) reduces to 1 √ S(τ, L) = 2 τ √ √ dt tanh (1 − t) τ = 2 log cosh τ (2.9.8) 0 Hence we get E∞ e−τ Γ = cosh √ τ −2 (2.9.9) A more formal proof of (2.1.4)–(2.1.5) can be obtained along the lines of Sections 2.5–2.6. This requires that we set p = pc = σ1 in Lemmas 2.5.1 and 2.6.1 and repeat the estimates in Sections 2.5.2 and 2.6.2, which in fact simplify considerably. 60 Chapter 3 Scaling limit of invasion percolation on a regular tree1 3.1 Introduction Invasion percolation on an infinite connected graph is a random growth model which is closely related to critical percolation, and is a prime example of self-organized criticality. It was introduced in the eighties by Wilkinson and Willemsen [46] and first studied on the regular tree by Nickel and Wilkinson [39]. The relation between invasion percolation and critical percolation has been studied by many authors (see for instance [14, 27]). More recently, Angel, Goodman, den Hollander and Slade [3] have given a structural representation of the invasion percolation cluster on a regular tree, and used it to compute the scaling limits of various quantities related to the IPC such as the distribution of the number of invaded vertices at a given level of the tree. Fixing a degree σ ≥ 2, we consider T = Tσ : the rooted regular tree with index σ, i.e. the rooted tree where every vertex has σ children. Invasion percolation on T is defined as follows: Edges of T are assigned weights which are i.i.d. and uniform on [0, 1]. The invasion percolation cluster on T , denoted IPC, is grown inductively starting from a subgraph I0 consisting of the root of T . At each step In+1 consists of In together with the edge of minimal weight in the boundary of In . The invasion percolation cluster IPC is the limit In . We consider the infinite tree IPC as a metric space endowed with the shortest path metric, and consider its scaling limit in the sense of weak limits w.r.t. the Gromov-Hausdorff topology. The limit is a random R-tree — a topological space with a unique rectifiable simple path between any two points. A useful way to describe such R-trees is in terms of their contour or 1 A version of this chapter has been submitted for publication: Omer Angel, Jesse Goodman, and Mathieu Merle. Scaling limit of invasion percolation on a regular tree. arXiv:0910.4205v1 [math.PR], 2009. 61 3.1. Introduction height functions (see subsection 3.4.5 below). Note that the IPC is infinite, so that we take a fixed object and only change the metric when taking the scaling limit. Theorem 3.1.1. The IPC has a scaling limit w.r.t. local Gromov-Hausdorff topology, which is a random R-tree. A key point in our study is that the contour function (as well as height function and Lukaciewicz path) of an infinite tree do not generally encode the entire tree. If the various encodings of trees are applied to infinite trees they describe only the part of the tree to the left of the leftmost infinite branch. We present two ways to overcome this difficulty. Both are based on the fact (see [3]) that the IPC has a.s. a unique infinite branch. Following Aldous [1] we define a sin-tree to be an infinite one-ended tree (i.e. with a single infinite branch). The first approach is to use the symmetry of the underlying graph T and observe that the infinite branch of the IPC (called the backbone) is independent of the metric structure of the IPC. Thus for all purposes involving only the metric structure of the IPC we may as well assume (or condition) that the backbone is the rightmost branch of T . We denote by R the IPC under this condition. The various encodings of R encode the entire tree. The second approach is to consider a pair of encodings, one for the part of the tree to the left of the backbone, and a second encoding the part to the right of the backbone. This is done by considering also the encoding of the reflected tree IPC. The reflection of a plane tree is defined to be the same tree with the reversed order for the children of each vertex. The uniqueness of the backbone implies that together the two encodings determine the entire IPC. In order to describe the limits we first define the process L(t) which is the lower envelope of a Poisson process on (R+ )2 . Given a Poisson process P in the quarter plane, L(t) is defined by L(t) = inf{y : (x, y) ∈ P and x ≤ t} Our other results describe the scaling limits of the various encodings of the trees in terms of solutions of t Yt = Bt − L (−Y s ) ds E(L) 0 where Y s = inf 0≤u≤s Yu is the infimum process of Y . The reason for the notation is that we also consider solutions of equations E(L/2) where in the 62 3.1. Introduction above, L is replaced by L/2. Note that by the scale invariance of the Poisson process, kL(kt) has the same law as L(t). Hence the scaling of Brownian motion implies that the solution Y has Brownian scaling as well. We work primarily in the space C(R+ , R+ ) of continuous functions from R+ to itself with the topology of locally uniform convergence. We consider three well known and closely related encodings of plane trees, namely the Lukaciewicz path, and the contour and height functions (all are defined in subsection 3.1.1 below). The three are closely related and indeed their scaling limits are almost the same. The reason for the triplication is that the contour function is the simplest and most direct encoding of a plane tree, whereas the Lukaciewicz path turns out to be easier to deal with in practice. The height function is a middle ground. For the IPC conditioned on the backbone being on the right, we denote its Lukaciewicz path (resp. height and contour functions) by VR (resp. HR and CR ). It is interesting that the scaling limit depends on σ only by a multiplicative factor. The constant γ = σ−1 will be used in giving this σ factor. Theorem 3.1.2. We have the weak limits in C(R+ , R): k −1 VR (k 2 t) t≥0 → γ 1/2 (Yt − Y t ) k −1 HR (k 2 t) t≥0 → γ −1/2 (2Yt − 3Y t ) k −1 CR (2k 2 t) t≥0 → γ −1/2 (2Yt − 3Y t ) (3.1.1) t≥0 t≥0 t≥0 (3.1.2) (3.1.3) as k → ∞, where (Yt )t≥0 solves E(L) (and is the same solution in all three limits). To put this theorem into context, recall that the Lukaciewicz path of a critical Galton-Watson tree is an excursion of random walk with i.i.d. steps. From this it follows that the path of an infinite sequence of critical trees scales to Brownian motion. The height and contour functions of the sequence are easily expressed in terms of the Lukaciewicz path and, assuming the branching law has second moments, are seen to scale to reflected Brownian motion (cf Le Gall [32]). Duquesne and Le Gall generalized this approach in [19], and showed that the genealogical structure of a continuousstate branching process is similarly coded by a height process which can be expressed in terms of a L´evy process, and that this is also the limit of various Galton-Watson trees with heavy tails. 63 3.1. Introduction The case of sin-trees is considered by Duquesne [18] to study the scaling limit of the range of a random walk on a regular tree. His techniques suffice for analysis of the IIC, but the IPC requires additional ideas, the key difficulty being that the Lukaciewicz path is no longer a Markov process. The scaling limit of the IIC turns out to be an illustrative special case of our results, and we will describe its scaling limit as well (in Section 3.3.6). For the unconditioned IPC we define its left part IPCG to be the sub-tree consisting of the backbone and all vertices to its left. The right part IPCD is defined as the left part of the reflected IPC. We can now define VG and VD to be respectively the Lukaciewicz paths for the left and right parts of the IPC, and similarly define HG , HD , CG , CD (see also subsection 3.1.1 below). Theorem 3.1.3. We have the weak limits in C(R+ , R) k −1 VG (k 2 t), VD (k 2 t) k k −1 −1 2 3.1.1 2 HG (k t), HD (k t) 2 t≥0 2 CG (2k t), CD (2k t) where (Yt )t≥0 and Yt t≥0 t≥0 t≥0 → γ 1/2 Yt − Y t , Yt − Y →γ −1/2 →γ −1/2 t t≥0 Yt − 2Y t , Yt − 2Y t Yt − 2Y t , Yt − 2Y t t≥0 t≥0 are independent solutions of E(L/2). Background Structure of the IPC We now give a brief overview of the IPC structure theorem from [3], which is the basis for the present work. First of all, IPC contains a single infinite branch, called the backbone and denoted BB. The backbone is a uniformly random branch in the tree (in the natural sense). From the backbone emerge, at every height and on every edge away from the backbone, subcritical percolation clusters. This relates the IPC to the incipient infinite cluster (IIC), defined and discussed by Kesten [28] (see also [6]). The IIC consists of an infinite backbone from which emerge critical percolation clusters, hence it stochastically dominates the IPC. In particular, both IPC and IIC are sin-trees. The subcritical percolation parameter of the percolation clusters attached to the backbone of the IPC increases towards the critical parameter pc = σ −1 as one moves up along the backbone. This explains why the IPC and IIC resemble each other far above the root. However, the analysis of [3] shows that the convergence of the parameter of the attached clusters is 64 3.1. Introduction slow enough that r-point functions and other measurable quantities such as level sizes possess different scaling limits. All that remains is to describe the percolation parameter for each of the trees attached to the backbone. We will only recall part of the description here. These are given in terms of a certain Markov chain Wn with explicitly stated transition probabilities. The chain Wn is non-increasing and satisfies n→∞ Wn −−−→ pc = σ −1 . We then define Wn = Wn ζ(Wn )σ−1 , where ζ(p) is the probability that the p-percolation cluster along a particular branch from the root of T is finite. The percolation parameter for the sub-trees attached to BBn is Wn , which is a non-decreasing sequence that converges a.s. to pc . We will only be concerned with the scaling limit of Wn , which is the lower envelope process L(t) defined above. To be precise, writing [x] for the integer part of x, we have for any ε > 0 k σW[kt] − 1 k 1 − σ W[kt] −−−→ L(t) t≥ε −−−→ L(t) t≥ε t≥ε k→∞ t≥ε k→∞ (3.1.4) The process Lt diverges as t → 0, which somewhat complicates the study of the IPC close to the root. Note that setting Wn ≡ pc in the above description gives rise to the IIC on the one hand, while in the scaling limit L is replaced by 0. This enables us to use a common framework for both clusters. Encodings of finite trees For completeness we include here the definition of the various tree encodings we are concerned with. We refer to Le Gall [32] for further details in the case of finite trees and to Duquesne [18] in the case of sin-trees discussed below. A rooted plane tree θ (also called an ordered tree) is a tree with a description as follows. Vertices of θ belong to n≥0 Nn . By convention, ∅ ∈ N0 is always a vertex of θ which is called the root. For a vertex v ∈ θ, we let kv = kv (θ) be the number of children of v and whenever kv = k > 0, these children are denoted v1, . . . , vk. In particular, the ith child of the root is simply i, and if vi ∈ θ then ∀1 ≤ j < i, vj ∈ θ as well. Edges of θ are the edges (v, vi) whenever vi ∈ θ. Note that the set of edges of θ are determined by the set of vertices and vice-versa, which allows us to blur the distinction between a tree and its set of vertices. The k th generation of a tree contains every vertex v ∈ θ ∩ Nk , so that the 0th generation consists exactly of the root. Define #θ to be the total number of vertices in θ. 65 3.1. Introduction Let v i 0≤i<#θ be the vertices of θ listed in lexicographic order1 , so that v 0 = ∅. The Lukaciewicz path V of θ is the continuous function Vt = Vtθ , t ∈ [0, #θ] defined as follows: For n ∈ {1, . . . , #θ} n−1 Vn = Vnθ kv i − 1 := i=0 and between integers V is interpolated linearly.2 The values Vn are also given by the following right description of the Lukaciewicz path. This description is simpler to visualize, though we do not know of a reference for it. For v ∈ θ, consider the subtree θv ⊂ θ formed by all the vertices which are smaller or equal to v in the lexicographic order. Let n(v, θ) be the number of edges connecting vertices of θv with vertices of θ \ θv . Then V (k) = n(v k , θ) − 1 The reason we call this the right description is that n(v, θ) is also the number of edges attached on the right side of the path from ∅ to v. It is straightforward to check that this description is consistent with other definitions. The height function is the second encoding we wish to consider. We also define it to be a piecewise linear function3 with H(k) the height of v k above the root. It is related to the Lukaciewicz path by H(n) = # k < n : Vk = min{Vk , . . . , Vn } (3.1.5) Finally, the contour function of θ is obtained by considering a walker exploring θ at constant unit speed, starting from the root at time 0, and going from left to right. Each edge is traversed twice (once on each side), so that the total time before returning to the root is 2(#θ −1). The value C θ (t) of the contour function at time t ∈ [0, 2(#θ − 1)] is the distance between the walker and the root at time t. It is straightforward to check that the Lukaciewicz path, height function and contour function each uniquely determine — and hence represent — 1 This ordering of the vertices is different from the ordering considered in chapter 2. In [32, 19], the Lukaciewicz path is defined as a piecewise constant, discontinuous function, but there the case when the scaling limit of this path is discontinuous is also treated. Note that only the values of Vn , n ∈ {1, . . . , #θ} are needed to recover the tree θ. Moreover, in our case, supt≥0 |Vt+1 − Vt | is bounded by σ, so that the eventual scaling limit will be continuous. The advantage of our convention is that it allows us to consider locally uniform convergence of the rescaled Lukaciewicz paths in a space of continuous functions. 3 Again, in [32], the height function of a non-degenerate tree is discontinuous. 2 66 3.1. Introduction 1311 132 111 12 13 11 A tree, its Lukaciewicz path V, its height function H, and its contour function C. 21 H 3 2 2 1 1 0 V 1 3 2 3 C 2 1 1 2 3 Figure 3.1: A finite tree and its encodings. any finite tree θ. Figure 3.1 illustrates these definitions, as they are easier to understand from a picture. At times it is useful to encode a sequence of finite trees by a single function. This is done by concatenating the Lukaciewicz paths or height function of the trees of the sequence. Note that when coding a sequence of trees, jumping from one tree to the next corresponds to reaching a new integer infimum in the Lukaciewicz path, while it corresponds to a visit to 0 in the height process. Encoding sin-trees While the definitions of Lukaciewicz path, and height and contour functions extend immediately to infinite (discrete) trees, these paths generally no longer encode a unique infinite tree. For example, all the trees containing the infinite branch {∅, 1, 11, 111, . . . } would have the identity function for height function, so that equal paths correspond to distinct infinite trees. In fact, the only part of an infinite tree which one can recover from the the height and contour functions is the sub-tree that lies left of the left-most 67 3.1. Introduction infinite branch. The Lukaciewicz path encodes additionally the degrees of vertices along the left-most infinite branch. However, if we restrict the encodings to the class of trees whose only infinite branch is the rightmost branch, then the three encodings still correspond to unique trees. In particular, observe that IPCG and R are fully encoded by their Lukaciewicz paths (as well as by their height, or contour functions). That is the reason we begin our discussion with these conditioned objects. Not surprisingly, it is possible to encode any sin-tree, such as the IIC and IPC, by using two coding paths, one for the part of the tree lying to the left of the backbone, and one for the part lying to its right. More precisely, suppose T is a sin-tree, and BB denotes its backbone. The left tree is defined as the set of all vertices on or to the left of the backbone: T v = x ∈ T : ∃v ∈ BB, x ≤ v . TG := v∈BB We do not define the right-tree of T as the set of vertices which lie on or to the right of the backbone. Rather, in light of the way the encodings are defined, it is easier to work with the mirror-image of T , denoted T and defined as follows: Since a plane tree is a tree where the children of each vertex are ordered, T may be defined as the same tree but with the reverse order on the children at each vertex. We then define TD = T G Obviously, only the rightmost branches of TG , TD are infinite, so the Lukaciewicz paths VG , VD , of TG , TD , do encode uniquely each of these two trees (and so do the height functions HG , HD and the contour functions CG , CG ). Therefore, the pair of paths (VG , VD ) encodes T (and so do the pairs (HG , HD ), (CG , CD )). Note that HG , CG are also respectively the height and contour functions of T itself, while HD , CD are respectively the height and contour functions of T . 3.1.2 Overview Let us try to give briefly, and heuristically, some intuition of why Theorem 3.1.2 holds. For t > 0, the tree emerging from BB[kt] is coded by the [kt]th excursion of V above 0. Except for its first step, this excursion has the same transition probabilities as a random walk with drift σ W[kt] − 1, which, by the convergence (3.1.4), is approximately −L(t)/k. Additionally, by [3, 68 3.2. Solving E(L) Proposition 3.1] Wk is constant for long stretches of time. It is well known (see for instance [26, Theorem 2.2.1]) that a sequence of random walks with drift c/k, suitably scaled, converges as k → ∞ to a c-drifted Brownian motion. Thus we expect to find segments of drifted Brownian paths in our limit. According to the convergence (3.1.4), the drift is expressed in terms of the L-process. This is what the definition of Y expresses. Thus, the idea when dealing with either the conditioned or the unconditioned IPC is to cut these sin-trees into pieces (which we call segments) corresponding to stretches where W is constant, and to look separately at the convergence of each piece. In Section 3.3, we look at the convergence of the rescaled paths coding a sequence of such segments for well chosen, fixed values of the W -process. In fact, we consider slightly more general settings which allows us to treat the case of the IIC as well as the various flavours of the IPC. In Section 3.4, we prove Theorem 3.1.2, by combining segments to form R. To deal with the fact that W is random and exploit the convergence (3.1.4), we use a coupling argument (see Subsection 3.4.3). We then prove that the segments fall into the family dealt with in Section 3.3. Because of the divergence of the L-process at the origin, we only perform the above for sub-trees above certain levels, and bound the resulting error separately. Finally, in section 3.5, we apply our convergence results to establish asymptotics for level and volume estimates of the IPC, to recover and extend results of [3]. 3.2 Solving E(L) Claim 3.2.1. Solutions to E(L), E(L/2) are unique in law. An interesting question is whether the solutions to E(L) are a.s. pathwise unique (i.e. strong uniqueness). For our purposes uniqueness in law suffices. Proof. We prove this claim for equation E(L). The proof for equation E(L/2) is identical. Let Y be a solution of E(L). Since L is positive, Yt ≤ Bt . Since L t t is non-increasing, 0 L(−Y s )ds ≤ 0 L(−B s )ds. For any fixed ε > 0, a.s. for all small enough s, −B s > s1/2−ε , while a.s. for all small enough u, t L(u) < u−(1+ε) . We deduce that almost surely limt→0 0 L(−Y s )ds = 0. Thus any solution of E(L) is continuous. 69 3.2. Solving E(L) Let us now consider two solutions Y 1 , Y 2 of E(B, L) and fix ε > 0. Introduce j ε := inf{t > 0 : L(t) < ε−1 } and tε0 := inf{t > 0 : −B t > j ε } tε1 := inf{t > 0 : −Y 1t > j ε } tε2 := inf{t > 0 : −Y 2t > j ε } From the continuity of Y 1 , Y 2 we have Y 1 (tε1 ) = Y 2 (tε2 ) = −j ε . Moreover, we have a.s. tε1 ∨ tε2 ≤ tε0 , and therefore a.s. tε1 ∨ tε2 −−−→ 0 ε→0 (3.2.1) Introduce a Brownian motion β independent of B and consider the (SDE) t L (j ε − Z εs ) ds Ztε = βt − E(ε, L) 0 By standard arguments E(ε, L) is pathwise exact. We then define Yt1,ε = Yt1 Yt1ε + Ztε 1 if t < tε1 if t ≥ tε1 Yt2,ε = Yt2 Yt2ε 2 if t < tε2 if t ≥ tε2 + Ztε Clearly, Y 1,ε , Y 2,ε are a.s. continuous, and moreover, Y 1 and Y 1,ε have the same distribution, and so do Y 2 and Y 2,ε . However, Y i,ε (tε1 + t) t≥0 for i = 1, 2 have a.s. the same path. From this fact, the continuity of Y 1,ε , Y 2,ε and (3.2.1), it follows that for any F ∈ Cb (C(R+ , R), R) E F (Y 1 ) − E F (Y 2 ) = E F (Y 1,ε ) − E F (Y 2,ε ) goes to 0 as ε goes to 0, which completes the proof. 70 3.3. Scaling simple sin-trees and their segments 3.3 Scaling simple sin-trees and their segments The goal of this section is to establish the convergence of the rescaled paths encoding suitable sequences of well chosen segments. In order to cover the separate cases at once, we will work in a slightly more general context than might seem necessary. We first look at a sequence of particular sin-trees Tk for which the vertices adjacent to the backbone generate i.i.d. subcritical (or critical) Galton-Watson trees. The law of such a tree is determined by the branching law on these Galton-Watson trees and the degrees along the backbone. If the degrees along the backbone do not behave too erratically and the percolation parameter scales correctly then the sequence of Lukaciewicz paths Vk has a scaling limit. The results for the IIC follow directly. Also, we determine the scaling limits of the paths encoding a sequence of subtrees obtained by truncations at suitably vertices on the backbones of Tk . These will be important intermediate results in the proofs of Theorems 3.1.2 and 3.1.3. 3.3.1 Notations Throughout this section we fix for each k ∈ Z+ a parameter wk ∈ [0, 1/σ], and denote by (θnk )n∈Z+ a sequence of i.i.d. subcritical Galton-Watson trees with branching law Bin(σ, wk ). For each k we also let Zk be a sequence of random variables (Zk,n )n≥0 taking values in Z+ . Definition 3.3.1. The (Zk , θk )-tree is the sin-tree defined as follows. The backbone BB is the rightmost branch. The vertex BBi has 1 + Zk,i children, including BBi+1 . Let v0 , . . . be all vertices adjacent to the backbone, in lexicographic order, and identify vn with the root of the tree θnk . Thus the first Zk,0 of the θ’s are attached to children of BB0 , the next Zk,1 to children of BB1 , and so on. We will use the notation Tk to designate the (Zk , θk )-tree, and Vk for its Lukaciewicz path. Definition 3.3.2. Let T be a sin-tree whose backbone is its rightmost branch. For i ∈ Z+ , let BBi be the vertex at height i on the backbone of T . The i-truncation of T is the sub-tree T i := {v ∈ T : v ≤ BBi } Thus the i-truncation of a tree consists of the backbone up to BBi , and the sub-trees attached strictly below level i. We denote by Tk,i the i-truncation of Tk , and by Vk,i its Lukaciewicz path. We further define 71 3.3. Scaling simple sin-trees and their segments τ (i) as the time of the (i + 1)th return to 0 of Vk . Observe then that Vk,i coincides with Vk up to the time τ (i) , takes the value −1 at τ (i) + 1, and terminates at that time. It will be useful to study first the special case where Zk is a sequence of i.i.d. binomial Bin(σ, wk ) random variables. Observe that in this case the subtrees attached to the backbone are i.i.d. Galton-Watson trees (with branching law Bin(σ, wk )). We use calligraphed letters for the various objects in this case. We denote the binomial variables Zk,n , we write T k for the corresponding (Zk , θk )-tree, T k,i for its i-truncation, and V k , V k,i for the corresponding Lukaciewicz paths. In the perspective of proving our main results, we note another special distribution of the variables Zk,n that is of interest. If Zk,n are i.i.d. Bin(σ − 1, wk ), then the subtrees emerging from the backbone of the (Zk , θk )-tree are independent sub-critical percolation clusters with parameter wk . In particular, for suitably chosen values of wk , nk , Tk,nk has the same law as a certain segment of R. On the other hand if wk ≡ σ −1 , then the corresponding (Z, θ)-tree is simply the IIC conditioned on its backbone being the rightmost branch of T , which we denote by IICR . We will see below that the unconditioned IIC, as well as segments of the unconditioned IPC can be treated in a similar way. For our key lemmas we consider the following properties: For any k, the variables (Zk,n )n are i.i.d. for some C, α > 0, EZ 1+α < C, k,n A: for some η, P(Z > 0) > η, k,n if m = EZ then m = lim m exists. k k,n k However, note that the proofs use only easier consequences of these properties. We need to avoid many consecutive 0’s among the Z’s, we need the maximal Z to behave and we need the cummulative sum of the Z’s to grow linearly in various regimes. 3.3.2 Scaling of segments Proposition 3.3.1. Let Zk,n be random variables such that A holds a.s., and assume wk ≤ σ −1 satisfy limk k(1 − σwk ) = u. Then, as k → ∞, weakly in C(R+ , R), 1 k V 2 −−−→ (Xt )t≥0 (3.3.1) k [k t] t≥0 k→∞ where Xt = Yt − Y t and Yt = Bγt − ut is a drifted Brownian motion. 72 3.3. Scaling simple sin-trees and their segments Since our goal is to represent segments of the IPC as well-chosen Tk,i , we have to deduce from Proposition 3.3.1 some results for the coding paths of the truncated trees. The convergence will take place in the space of continuous stopped paths denoted S. An element f ∈ S is given by a lifetime ζ(f ) ≥ 0 and a continuous function f on [0, ζ(f )]. S is a Polish space with metric d(f, g) = |ζ(f ) − ζ(g)| + sup {|f (t) − g(t)|} t≤ζ(f )∧ζ(g) It is clear from the right description of Lukaciewicz paths that the path of Tk,i visits 0 exactly when reaching backbone vertices. In particular its length is τ (nk ) , where τ (i) denotes the ith return to 0 of the path Vk . We shall use this to prove Corollary 3.3.3. Assume the conditions of Proposition 3.3.1 are in force. Assume further that 0 < x = lim nk /k. Then, weakly in S, 1 k,nk V 2 k [k t] −−−→ (Xt )t≤τmx (3.3.2) t≤τ (nk ) /k2 k→∞ where X and Y are as in Proposition 3.3.1, and τy is the stopping time inf{t > 0 : Yt = −y}. It is then straightforward to deduce convergence of the height functions. Let hk (resp. hk,i ) denote the height function coding the tree Tk , (resp. Tk,i ). Corollary 3.3.4. Suppose the assumptions of Corollary 3.3.3 are in force. Then weakly in C(R+ , R), 1 k h 2 k [tk ] −−−→ t≥0 k→∞ 1 2 (Yt − Y t ) − Y γ m (3.3.3) t t≥0 Furthermore, weakly in S, 1 k,nk h 2 k [tk ] 3.3.3 −−−→ t≤τ (nk ) /k2 k→∞ 2 1 (Yt − Y t ) − Y γ m (3.3.4) t t≤τmx Proof of Proposition 3.3.1 We begin with the following Lemma, which relates the Lukaciewicz paths of a sequence of trees, and that of the tree consisting of a backbone to which the trees of the sequence are attached. 73 3.3. Scaling simple sin-trees and their segments Lemma 3.3.2. Let (θn )n≥0 be a sequence of trees, and define the sin-tree T to be the sin-tree with a backbone BB on the right, such that the root of θn is identified with BBn . Let U be the Lukaciewicz path coding the sequence θ, and let V be the Lukaciewicz path of T . Then Vn = Un + 1 − U n−1 where U is the infimum process of U and by convention U −1 = 1. Proof. The Lemma follows directly from the definition of Lukaciewicz paths. U reaches a new infimum (and U decreases) exactly when the process completes the exploration of a tree in the sequence. The increments of V differ from the increments of U only at vertices of the backbone of T , where the degree in T is one more than the degree in θn . We first establish the proposition in the special case introduced earlier, where Zk is a sequence of i.i.d. Bin(σ, wk ) random variables. In this case, the sub-trees attached to the backbone of T k are a sequence of i.i.d. GaltonWatson trees with branching law having expectation σwk (which tends to 1 as k → ∞), and variance σwk (1 − wk ) (which tends to γ as k → ∞). The Lukaciewicz path U k of this sequence of Galton-Watson trees is a random walk with drift σwk − 1 and stepwise variance σwk (1 − wk ). From a well known extension of Donsker’s invariance principle (see for instance [26, Theorem II.3.5]) it follows that 1 k 2 U (k t) k −−−→ (Yt )t≥0 t≥0 k→∞ weakly in C(R+ , R). It now follows from Lemma 3.3.2 that 1 k 2 V (k t) k −−−→ (Xt )t≥0 t≥0 k→∞ (3.3.5) Having Proposition 3.3.1 for Zk,n , we now extend it to other degree sequences. By the Skorokhod representation theorem, we may assume (by changing the probability space as needed) that (3.3.5) holds a.s.: 1 k 2 V (k t) k a.s. −−−→ (Xt )t≥0 t≥0 k→∞ (3.3.6) By adding the sequences Zk to the probability space we get a coupling of T k and Tk . Note that we use the same sequences θk in both trees. This 74 3.3. Scaling simple sin-trees and their segments allows us to identify each vertex of θnk with one vertex in each of T k , Tk , giving also a partial correspondence between T k and Tk (with the backbone vertices remaining unmatched). It will be convenient to consider the sets of points Gk := {(i, Vk (i)), i ∈ Z+ }, G k := {(i, V k (i)), i ∈ Z+ } which are the integer points in the graphs of Vk , V k . To each vertex v ∈ Tk corresponds a point (xv , yv ) ∈ Gk (and similarly (xv , yv ) ∈ G k for v ∈ T k ). From the right description of Lukaciewicz paths introduced in subsection 3.1.1, we see that Gk = {(xv , yv ) : v ∈ Tk } = (#(Tk )v , n(v, Tk ) − 1) : v ∈ Tk G k = {(xv , yv ) : v ∈ T k } = (#(T k )v , n(v, T k ) − 1) : v ∈ T k The next step is to show that these two sets are close to each other. Any v ∈ θnk is contained in both Tk and T k . We first show that xv ≈ xv and yv ≈ yv for such v, and then show how to deal with the backbones. Any tree θnk is attached by an edge to some vertex in the backbone of Tk and T k . For any vertex v ∈ θnk we denote the height of this vertex by lv and v respectively: lv = sup{t : BBt < v in Tk }, v = sup{t : BBt < v in T k } These values depend implicitly on k. Note that lv , v do not depend on which v ∈ θnk is chosen, hence by a slight abuse of notation, we also use ln , n for the same values whenever v ∈ θnk . Lemma 3.3.3. Assume v ∈ θnk . Then |xv − xv | = |lv − v| |yv − yv | ≤ σ + Zk,lv Proof. We have xv = #(T k )v = #θik + #(θnk )v + n i<n and similarly xv = #(Tk )v = #θik + #(θnk )v + ln i<n 75 3.3. Scaling simple sin-trees and their segments The first claim follows. For the second bound use yv = n(v, Tk ) − 1. There are n(v, θnk ) edges connecting (Tk )v to its complement inside θnk , and at most Zk,ln edges connecting BBln to the complement. Similarly, in T k we have the same n(v, θnk ) edges inside θnk and at most Zk, n ≤ σ edges connecting BB n to the complement. It follows that the difference is at most σ + Zk,ln . Next we prepare to deal with the backbone. For a vertex v ∈ Tk , define u ∈ Tk by u = min u ∈ (Tk \ BB) : u ≥ v If v ∈ / BB then u = v. If v is on the backbone then u is the first child of v, unless v has no children outside the backbone. Note that u ∈ θnk for some n, so we may also consider u as a vertex of T k . Note also that v → u is a non-decreasing map from Tk to T k . k . Lemma 3.3.4. For a backbone vertex v in Tk , define n by θnk < v < θn+1 Then |xv − xu | ≤ 1 + ln+1 − ln |yv − yu | ≤ σ + Zk,ln+1 Proof. The only vertices between v and u in the lexicographic order are u and some of the backbone vertices with indices from ln to ln+1 , yielding the first bound. Let w ∈ BB be u’s parent. If v has children apart from the next backbone vertex then w = v and u is v’s first child, so yu − yv = ku − 1 ≤ σ − 1. If v has no other children then yu − yv = (ku − 1) + (kw − 1) ≤ σ + Zk,ln+1 . Lemma 3.3.5. Fix ε, A > 0 and let w be the [Ak 2 ] vertex of Tk . Then with high probability w , lw ≤ k 1+ε . Proof. Since each θnk is (slightly) sub-critical, we have P(#θnk > k 2 ) > c1 k −1 for some c1 > 0. Consider the first k 1+ε vertices along the backbone in Tk . With overwhelming probability, the number of θ’s attached to them is at least ηk 1+ε /2. On this event, with overwhelming probability at least c2 k ε of these have size at least k 2 , hence there are c2 k 2+ε Ak 2 vertices v with lv ≤ k 1+ε (and these include the first Ak 2 vertices in the tree). w is dealt with in the same way. 76 3.3. Scaling simple sin-trees and their segments Lemma 3.3.6. Fix A > 0 and let w be the [Ak 2 ]th vertex of Tk . For ε > 0 small enough, P sup |xv − xu | > 3k 1+ε −−−→ 0 P max |yv − yu | > k 1−ε −−−→ 0 k→∞ v<w and v<w k→∞ Proof. For a vertex v ∈ θnk off the backbone we have u = v and |xv − xu | ≤ |lv − v| ≤ lv + v ≤ lw + w and with high probability this is at most 2k 1+ε . If v < w is in the backbone then we argue that |xv − xu | k 1+ε . To this end, note that ln+1 − ln is dominated by a geometric random variable with mean 1/η (since the Zk,n ’s are independent). Since only n < Ak 2 might be relevant to the initial part of the tree, this shows that with high probability |xv − xu | < c log k k 1+ε . The bound on the y’s follows from the bounds on |yv − yu |. All that is needed is to show that with high probability Zk,n < k 1−ε for all n < k 1+ε , and this follows from assumption A and Markov’s inequality. We now finish the proof of Proposition 3.3.1. Because the path of Vk is linearly interpolated between consecutive integers, and since for any A > 0 the paths of X are a.s. uniformly continuous on [0, A], the proposition will follow if we establish that for any A, ε > 0, P sup t∈[0,A] 1 k V 2 − Xt > ε k [k t] −−−→ 0 k→∞ (3.3.7) Consider first t such that k 2 t ∈ Z+ . Then there is some vertex v ∈ Tk so that xv = k 2 t. Let u ∈ T k be as defined above, and suppose k 2 s = xu . Then (3.3.6) implies that k −1 yu − Xs is uniformly small. Lemma 3.3.6 implies that with high probability k 2 s − k 2 t = |xu − xv | ≤ 3k 1+ε for all such v. Thus |s − t| ≤ k −1+ε 1. Since paths of X are uniformly continuous we find |Xs − Xt | is uniformly small, and so k −1 yu − Xt is uniformly small. Finally, Lemma 3.3.6 states that |yu − yv | ≤ C, so the scaled vertical distance is also o(1). Next, assume m < k 2 t < m + 1. Then Vk (k 2 t) lies between Vk (m) and k V (m + 1). Since both of these are close to the corresponding values of X, and since X is uniformly continuous (and the pertinent points differ by at most k −2 ) we may interpolate to find that (3.3.7) holds for all t < A. 77 3.3. Scaling simple sin-trees and their segments 3.3.4 Proof of Corollaries 3.3.3 and 3.3.4 Proof of Corollary 3.3.3. By Proposition 3.3.1, the limit of k1 Vkk2 t t≤τ (nk ) must take the form (Xt )t≤τ for some possibly random time τ , and furthermore Xτ = 0. We need to show that τ = τmx = inf{t ≥ 0 : −Yt = mx}. In the special case of the tree T k we note that the infimum process U k records the index of the last visited vertex along the backbone. Therefore τ (nk ) is the time at which U k first reaches −nk , and by assumption nk ∼ xk. Using the a.s. convergence of k1 U k (k 2 t) towards Yt , along with the fact that for any fixed x > 0, ε > 0, one has a.s. Y τx −ε > −x > Y τx +ε , we deduce that a.s., τ (nk ) /k 2 → τx . It then follows that 1 k V 2 , t ≤ (τ (nk ) + 1)/k 2 k k t a.s. −−−→ (Xt , t ≤ τx ) k→∞ Since, in this case, mk = σwk → m = 1, this implies the corollary for this special distribution. The general case is then a consequence of excursion theory. Indeed (−Y t , t ≥ 0) can be chosen to be the local time at its infimum of Y (see for instance [40, paragraph VI.8.55]), that is a local time at 0 of X, since excursions of Y away from its infimum match those of X away from 0. However, if (ε) Nt denotes the number of excursions of X away from 0 that are completed (ε) before t and reach level ε, then (limε→0 εNt , t ≥ 0) is also a local time at 0 of X, which means that it has to be proportional to (−Y t , t ≥ 0) (cf for instance [10, section III.3(c) and Theorem VI.2.1]). In other words, there exists a constant c > 0 such that for any t ≥ 0, (ε) lim εNt ε→0 = −cY t In the special case when Zk,n = Bin(σ, wk ) we have already proven the corollary. In particular, the number N k,(ε) of excursions of ( k1 Ukk2 t , t ≤ τ (nk ) ) which reach level ε is such that, when letting k → ∞ and then ε → 0, we have εN k,(ε) → cx. Let N k,(ε) be the number of excursions of k1 Vkk2 t , t ≤ τ (nk ) which reach level ε. It follows from Proposition 3.3.1 that, in distribution, N k,(ε) → Nτε as k → ∞. However, by assumption A we can use law of large numbers for the sequences (Zk,n )n∈N along with the fact that mk → m, to ensure that εN k,(ε) ∼ mεN k,(ε) . Therefore, letting first k → ∞, then ε → 0 we k→∞ find εN k,(ε) → mcx. 78 3.3. Scaling simple sin-trees and their segments From the fact that τ (nk ) are stopping times, we deduce that τ itself is a stopping time. Since Xτ = 0, for any s > 0, the local time at 0 of X (that is, −Y ) increases on the interval (τ, τ + s). It follows that for a certain real-valued random variable R, τ = τR = inf{t ≥ 0 : −Yt = R}, and we deduce that in distribution, R = mx, i.e. τ = τmx Proof of Corollary 3.3.4. The relation between the height function and the Lukaciewicz path is well known; see e.g. [19, Theorem 2.3.1 and equation (1.7)]. Combining with Proposition 3.3.1, one finds that the height process of the sequence of trees emerging from the backbone of Tk converges when rescaled to the process 2 (Yt − Y t ) γ Moreover, the difference between the height process of Tk and that of the sequence of trees emerging from the backbone of Tk is simply −U k . As in the proof of Corollary 3.3.3, one has weakly in C(R+ , R), 1 − U k[k2 t] k −−−→ t≥0 k→∞ − 1 Y m t t≥0 and (3.3.3) follows. The proof of (3.3.4) is similar. In fact, [19, Corollary 2.5.1] states the joint convergence of Lukaciewicz paths, height, and contour functions. It is thus easy to deduce a strengthening of Corollary 3.3.4 to get the joint convergence. 3.3.5 Two sided trees The limit appearing in Proposition 3.3.1 retains very minimal information about the sequence Zk . If two trees (or two sides of a tree) are constructed as above using independent θ’s but dependent sequences of Z’s, the dependence between two sequences might disappear in the scaling limit. For k ∈ Z+ , let wk ∈ [0, 1/σ], and denote by (θnk )n∈Z+ , (θnk )n∈Z+ two independent sequences of i.i.d. subcritical Galton-Watson trees with branching law Bin(σ, wk ). We let Zk , Zk be two sequences of random variables taking values in Z+ such that the pairs (Zk,n , Zk,n ) are independent for different n; however, we allow Zk,n and Zk,n to be correlated. Let Tk , Tk designate respectively the (Zk , θk )-tree, (Zk , θk )-tree as defined in Section 3.3.1. Let Vk , resp. Vk denote their Lukaciewicz paths. We recall that Tk,nk , Tk,nk are respectively the nk -truncation, of Tk , resp. Tk , and we denote by Vk,nk , Vk,nk their respective Lukaciewicz paths. 79 3.3. Scaling simple sin-trees and their segments Proposition 3.3.7. Suppose wk ≤ σ −1 is such that u = limk→∞ k(1 − σwk ) exists, and assume that both sequences of variables Zk,n , Zk,n satisfy assumption A. Then, as k → ∞, weakly in C(R+ , R2 ) k k k −1 V[k 2 t] , V[k 2 t] −−−→ Xt , Xt t≥0 k→∞ t≥0 where the processes X, X are two independent reflected Brownian motions with drift −u and diffusion coefficient γ. Moreover, if nk /k → x > 0, mk → m, mk → m as k → ∞, we have k,nk k,nk k −1 V[k 2 t] , V[k 2 t] −−−→ Xt , Xt t≤τ (nk ) /k2 k→∞ t≤τmx The proof is almost identical to that of Proposition 3.3.1. When the sequences Zk , Zk are independent with Bin(σ, wk ) elements the result follows from Proposition 3.3.1. For general sequences, the coupling of Section 3.3.3 shows that the sides have the same joint scaling limit. 3.3.6 Scaling the IIC It is known that the IIC is the result of setting wk = 1/σ in the above constructions. Specifically, let us first suppose that Z is a sequence of i.i.d. Bin(σ − 1, 1/σ), and (θn )n is a sequence of i.i.d. Bin(σ, 1/σ) Galton-Watson trees. Let T be a (Z, θ)-tree, then observe that T has the same distribution as IICR . The convergence of the rescaled Lukaciewicz path encoding this sin-tree to a time-changed reflected Brownian path is thus a special case of Proposition 3.3.1. The scaling limits of the height and contour functions follow from Corollary 3.3.4. We have m = γ, so both limits are γ2 Bγt − γ3 B γt . For the unconditioned IIC, let Yn be i.i.d. uniform in {1, . . . , σ}. Let Zn ∼ Bin(Yn − 1, 1/σ) and Zn ∼ Bin(σ − Yn , 1/σ), independent conditioned on Yn and independently of all other n. Moreover, suppose that θ, θ are two independent sequences of i.i.d. Bin(σ, 1/σ) Galton-Watson trees. Then, T and T are jointly distributed as IICG and IICD . Since in this case m = m = γ/2, from Proposition 3.3.7, we see that the rescaled Lukaciewicz paths encoding these two trees converge towards a pair of independent time-changed reflected Brownian motions. Corresponding results hold for the right/left height and contour functions of the IIC. For example, if HG , HD are the left and right height functions of the IIC, then 80 3.4. Bottom-up construction weakly in C(R+ , R2+ ), 1 1 HG (k 2 t), HD (k 2 t) k k −−−→ t≥0 k→∞ 2 2 (Bγt − 2B γt ), (Bγt − 2B γt ) γ γ t≥0 where B and B are two independent Brownian motions. Note that the limit 2 γ (Bγt − 2B γt ) is a constant times a 3-dimensional Bessel process. 3.4 3.4.1 Bottom-up construction Right grafting and concatenation Definition 3.4.1. Given a finite plane tree, its rightmost-leaf is the maximal vertex in the lexicographic order; equivalently, it is the last vertex to be reached by the contour process, and is the rightmost leaf of the sub-tree above the rightmost child of the root. Definition 3.4.2. The right-grafting of a plane tree S on a finite plane tree T , denoted T ⊕ S is the plane tree resulting from identifying the root of S with the rightmost leaf of T . More precisely, let v be the rightmost leaf of T . The tree T ⊕ S is given by its set of vertices {u, vw : u ∈ T \ {v}, w ∈ S}. Note in particular that the vertices of S have been relabeled in T ⊕ S through the mapping from S to T ⊕ S which maps w to vw. Definition 3.4.3. The concatenation of two functions Vi ∈ S with V2 (0) = 0, denoted V = V1 ⊕ V2 , is defined by V (t) = V1 (t) t ≤ x1 V1 (x1 ) + V2 (t − x1 ) t ∈ [x1 , x2 ] Lemma 3.4.1. If each Yi ∈ S attains its minimum at ζ(Yi ) then (Yi − Y i ) = Yi − Yi The following is straightforward to check, and may be used as an alternate definition of right-grafting. Lemma 3.4.2. Let R = T ⊕ S be finite plane trees, and denote the Lukaciewicz path of R (resp. T, S) by VR (resp. VT , VS ). Let VT be VT terminated at #T (i.e. without the final value of -1). Then VR = VT ⊕ VS . 81 3.4. Bottom-up construction Consider a sin-tree T in which the backbone is the rightmost path (i.e. the path that takes the rightmost child at each step). Given some increasing sequence {xi } of vertices along the backbone we cut the tree at these vertices: Let Ti := {v ∈ T : xi ≤ v ≤ xi+1 } Thus Ti contains the segment of the backbone [xi , xi+1 ] as well as all the sub-trees connected to any vertex of this segment except xi+1 . We let Ti be Ti rerooted at xi (Formally, Ti contains all v with xi v ∈ Ti .) It is clear from ∞ the definitions that T = i=0 Ti . Note that apart from being increasing, the sequence xi is arbitrary. 3.4.2 Notations In the rest of this section we consider both R and the unconditioned IPC. Our goal is to establish Theorems 3.1.2 and 3.1.3. In the next subsection we establish Theorem 3.1.2. We shall use V to denote the Lukaciewicz path of R. We construct below a sequence of copies of R whose scaling limits converge. These will be indexed by k, though the dependence on k will frequently be implicit. We denote by Rk the k th instance of R in the sequence. Note that the use of Skorokhod representation theorem will allow us to construct the sequence so that the Lukaciewicz paths converge almost surely, rather than just in distribution. While R is close to critical away from the root, the segments close to the root behave differently and need to be dealt with separately. We let Rβ (implicitly depending on k) be the subtrees above a certain vertex in the backbone (see below), and let V β denote its Lukaciewicz path. As β → ∞ the trees will get closer to the full trees. Lemma 3.4.5 below will show that V β is uniformly close to V (recalling that both depend implicitly on k.) 3.4.3 IPC structure and the coupling In this section we prove Theorem 3.1.2. Recall the W -process introduced in paragraph 3.1.1, and the convergence (3.1.4). The W -process is constant for long stretches, giving rise to a partition of R into what we shall call segments. Each segment consists of an interval of the backbone along which W is constant, together with all sub-trees attached to the interval. To be precise, define xi inductively by x0 = 0 and xi+1 = inf n>xi {Wn > Wxi }. With a slight abuse, we also let xi designate the vertex along the backbone at height xi . 82 3.4. Bottom-up construction Since we have convergence in distribution of the W ’s we may couple the IPC’s for different k’s so that the convergence holds a.s.. More precisely, let J be the set of jump times for {L(t)}. We may assume that a.s., {k −1 xki } −−−→ k→∞ J in the sense that there there is a 1-to-1 mapping from the jump times of W k (in Rk ) into J that eventually contains every point of J. Furthermore, k ) −−−→ L(t). we may assume that for any t ∈ / J we have a.s. k −1 (1 − σ W[kt] k→∞ The backbone is the union of the intervals [xi , xi+1 ] for all i ≥ 0, and the rest of the IPC consists of sub-critical percolation clusters attached to each vertex of the backbone y ∈ [xi , xi+1 ). We can now write ∞ R= Ri i=0 where Ri is the [xi , xi+1 ] segment of R, rerooted at xi . Ri has a rightmost branch of length ni := xi+1 − xi . The degrees along this branch are i.i.d. Bin(σ − 1, Wxi ), and each child off the rightmost branch is the root of an independent Galton-Watson tree with branching law Bin(σ, Wxi ). In what follows, we say that Ri is a Wxi -segment of length ni , and we observe that these segments fall into the family dealt with in section 3.3. We may summarize the above in the following lemma: Lemma 3.4.3. Suppose W consists of values Ui repeated ni times. Then Ri is distributed as a Ui -segment of length ni , and conditioned on {Ui , ni } the trees {Ri } are independent. A difficulty we must deal with is that in the scaling limit there is no first segment, but rather a doubly infinite sequence of segments. Furthermore, the initial segments are far from critical, and so need to be dealt with separately. This is related to the fact that the Poisson lower envelope process diverges near 0, and has no “first segment”. Because of this we restrict ourselves at first to a slightly truncated invasion percolation cluster. For any β > 0 we define xβ0 = min{x : σ Wx > 1 − β/k}. Thus we consider the first vertex along the backbone for which σ Wx > 1 − β/k. Let Rβ (depending implicitly on k) denote the subtree of Rk above xβ0 , Rβ the relabeled version of Rβ . If β is large then Rβ is almost the entire tree. For any fixed β, as k → ∞ the branches of Rβ are all close to critical. As for the entire tree, we define xβi+1 = inf{n > xβi : Wn > Wxβ }. Note that xβ0 = xm for some m i and that xβi = xm+i for the same m and all i. If β ∈ / {L(t)} then β gives rise to a partial indexing of J. Let j0β = inf{t > 0 : L(t) < β} 83 3.4. Bottom-up construction β and ji+1 the time of the first jump of L after jiβ . Under the coupling above we have the limits k −1 xβi −−−→ jiβ , and for y ∈ [xβi , xβi+1 ) we have that k→∞ k(1 − σ Wy ) −−−→ L(jiβ ). k→∞ Denote by Viβ (implicitly depending on k) the Lukaciewicz path corresponding to the ith segment Riβ in Rβ . For any β, i, the ith segment has associated percolation parameter wk satisfying k(1 − σwk ) −−−→ u for some k→∞ nβi k −1 nβi value u of L, and length satisfying → − x for some x > 0. By Corollary 3.3.3, we have the convergence in distribution β k −1 Viβ (k 2 t), 0 ≤ t ≤ τ (ni ) −−−→ (Xt , 0 ≤ t ≤ τγx ) k→∞ (3.4.1) where Xt = Yt − Y t , and Yt solves √ dYt = γ dBt − u dt β As in the previous section, τ (ni ) denotes the lifetime of Viβ (that is, its (nβi )th return to 0) and τy is the hitting time of −y by Y . Because this convergence holds for all β, i, we may construct the coupling of the probability spaces so that the convergence in (3.4.1) is also almost sure, and this is the final constraint in our coupling. Lemma 3.4.4. Fix β > 0. In the coupling described above we have, almost surely, the scaling limit k −1 V β (k 2 t) −−−→ Xt k→∞ where Xt = Ytβ − Y βt , and Y β solves Ytβ = t √ γBt − 0 L j0β − 1 β Y ds γ s Proof. Solutions of the equation for Y β are a concatenation of segments. In each segment the drift is fixed, and each segment terminates when Y β reaches a certain threshold. The corresponding segments of X exactly correspond to the scaling limit of the tree segments Riβ . Lemma 3.4.4 then follows from Lemma 3.4.1 and Lemma 3.4.2. Lemma 3.4.5. Almost surely, (Ytβ , t > 0) −−−→ Yt β→∞ 84 3.4. Bottom-up construction where Y solves Yt = √ t γBt − 0 1 L − Y s ds γ Proof. Consider the difference between the solutions for a pair β < β . We have the relation Yβ = Z ⊕ Yβ, √ t where Z is a solution of Zt = γBt − 0 L j0β − γ1 Z s ds, killed when Z first reaches γ(j0β − j0β ). In particular Z is a stochastic process with drift in [−β , −β] (and quadratic variation γ). Thus to show that Y β is close to Y β , we need to show that Z is small both horizontally and vertically, i.e. ζ(Z) is small, as is Z ∞ . √ The vertical translation of Y β is γk −1 (xβ0 − xβ0 ), which is at most k −1 xβ0 . From [3] we know that this tends to 0 in probability as β → ∞. This convergence is a.s. since xβ0 is non-increasing in β. The values of Z are unlikely to be large, since Z has a non-positive (in fact negative) drift and is killed when Z reaches some negative level close to 0. Finally, there is a horizontal translation of Y β in the concatenation. This translation is just the time at which Z first reaches γ(j0β − j0β ), which is also small, uniformly in β . Theorem 3.1.2(1) is now a simple consequence of Lemmas 3.4.4 and 3.4.5. Indeed, the process Y − Y has the same law as the righthand side of (1), due to the scale invariance of solutions of E(L). We shall note that in fact, Y is the limit of the rescaled Lukaciewicz path coding the sequence of off-backbone trees. The same argument using Corollary 3.3.4 instead of Corollary 3.3.3 gives the convergence of the height function. Finally, convergence of contour functions is deduced from that of height functions by a routine argument (see for instance [32, section 1.6]). 3.4.4 The two-sided tree For convenience we use the shorter notation T write V for its Lukaciewicz path. To deal with trees TG and TD as introduced in section 3.1.1. the same distribution, but are not independent. to designate the IPC, and T recall the left and right They obviously both have As in the previous section 85 3.4. Bottom-up construction we may cut these two trees into segments along which the W -process is constant. More precisely, ∞ ∞ TGi , TG = TDi TD = i=0 i=0 where the distribution of TDi , TGi can be made precise as follows. Let (θni )n , (θni )n be two independent sequences of independent GaltonWatson trees with branching law Bin(σ, Wxi ). Let Yn , n ∈ Z+ be independent uniform on {1, . . . , σ}, and conditionally on Yn , let Zn be Bin(Yn − 1, Wxi ) and Zn be Bin(σ − Yn , Wxi ), where conditioned on the Y ’s all are independent. Then TGi and TDi are distributed as the ni -truncations of the (Z, θi )-tree, resp. of the (Z, θi )-tree (constructed as in Definition 3.3.1). The rest of the proof of Theorem 3.1.3 is then almost identical to that of Theorem 3.1.2. In particular, to deal with the fact that the scaling limit has no first segment, introduce subtrees T β and consider left and right trees TGβ , TDβ . We then perform a similar coupling. The convergence for each sequence of segments then follows from the second part of Proposition 3.3.7. However, note that the value of the expected number of children of a vertex on the backbone is divided by 2 compared to the conditioned case. As a consequence, the limits of the rescaled coding paths of TGβ , TRβ will be expressed in terms of solutions to the equation Ytβ = √ t γBt − 0 L j0β − 2 β Y ds γ s Further details are left to the reader. 3.4.5 Convergence of trees In this section we discuss weak convergence of the trees as ordered metric spaces. We refer to [32] for background on the theory of continuous real trees. Given any two continuous functions CG , CD : R+ → R+ that satisfy CG (0) = CD (0) = 0 we can define the continuum tree with these functions as its left and right contour functions (Duquesne and Le Gall call these “height processes”, though they are mathematically closer to the contour function of a discrete tree). To do this, first define C(t) = CG (−t) CD (t) t≤0 t≥0 86 3.5. Level estimates Next, define a distance on R by d(s, t) = C(s) + C(t) − 2 inf C(u) u∈I(s,t) where for s < t we denote I(s, t) = [s, t] R \ [s, t] st ≥ 0 st < 0 (This second case is where we differ from the usual theory for compact trees.) The continuum tree is now defined as R/ ∼ where ∼ is the equivalence relation s ∼ t ⇐⇒ d(s, t) = 0. We may now define the continuum random sin-tree T IPC whose left and right contour processes are defined for t ∈ R by CG (t) := γ −1/2 (Yt − 2Y t ), CD (t) := γ −1/2 (Yt − 2Y t ) Recall that for x > 0 we defined earlier τx := inf{u > 0 : Ys = −x}, and define τx similarly for Y . For x > 0, we may consider the subtree TxIPC whose left and right contour process are defined by x CG (t) := CG (t ∧ τγ 1/2 x ), x CD (t) := CD (t ∧ τγ 1/2 x ) The tree TxIPC is a.s. a compact real tree. It corresponds to the truncation of IPC at height x on the backbone, that is, it consists of all the vertices at height below x on the backbone and their descendants off the backbone. For nk such that nk /k → x, consider the nk -truncation of IPC as a continuous tree, and rescale it so that its edges have length 1/k. We denote by IPCkx the rescaled tree. As in [19], one can then show that for any x > 0, the third line in Theorem 3.1.3 implies convergence of IPCkx towards TxIPC in the sense of weak convergence in the space of compact real trees equipped with the GromovHausdorff distance. In particular this yields Theorem 3.1.1. Clearly, a similar construction also holds in the case of the IIC. 3.5 Level estimates The goal of this section is to apply our convergence results to establish asymptotics for level, volume estimates of the invasion percolation cluster. In [3], it was proved that the size of the nth level of the IPC, rescaled by a factor n, converges to a non-degenerate limit. Similarly, the volume up 87 3.5. Level estimates to level n, rescaled by a factor n2 , converges to non-degenerate limit. The Laplace transforms of these limits were expressed as functions of the Lprocess. However formulas (1.20)–(1.23) of [3] do not provide insight into the limiting variables. With our convergence theorem for height functions of R, we can express the limit in terms of the continuous limiting height function. In the case of the asymptotics of the levels, we also provide an alternative way of expressing the limit. For x ∈ R+ we denote by C[x] the number of vertices of the IPC at [x] height [x]. We let C[0, x] = i=0 C[i] denote the number of vertices of the IPC up to height [x]. For simplicity, we use the shorter notation (Ht , t ≥ 0) := (γ −1/2 (2Yt − 3Y t ), t ≥ 0), to denote the continuous limit of the rescaled version of HR (see Theorem 3.1.2). In particular, observe that 1 C[0, an] = n2 ∞ 1[0,a] 0 1 HR sn2 n ds We denote by lta (H) the standard local time at level a, up to time t, of the semimartingale H, that is (since H has quadratic variation 4/γ): lta (H) = 4 1 lim γ η→0 η t 1[a,a+η] (Hs )ds 0 Proposition 3.5.1. Let a > 0. We have the distributional limit 1 C[0, an] −−−→ n→∞ n2 ∞ 1[0,a] (Hs )ds (3.5.1) 0 Furthermore, γ a 1 C[an] −−−→ l∞ (H) n→∞ n 4 (3.5.2) The limiting quantity in (3.5.2) can be expressed as a sum of independent contributions corresponding to distinct excursions of Y − Y . These contributions are, conditionally on the L-process, independent exponential random variables. For c > 0, let us denote by e(c) an exponential variable with parameter c. Corollary 3.5.1. Let S be a point process such that conditioned on the √ L-process, S is an inhomogeneous Poisson point process on [0, a γ], with intensity 2L (s) ds √ exp (a γ − s)L(s) − 1 88 3.5. Level estimates Then, conditionally on L, and in distribution, √ γ 1 C[an] −−−→ n→∞ n 2 L(s) √ 1 − exp −(a γ − s)L(s) e s∈S (3.5.3) where the terms in the sum are independent. From this representation and immediate properties of the L-process, it is straightforward to recover the representation of the asymptotic Laplace transform of level sizes, (1.21) of [3]. Also, as the proof of the Corollary will show, a.s. S is finite, thus only a finite number of distinct values of L contribute to the sum in (3.5.3). Proof of Proposition 3.5.1. We start by proving (3.5.1). Our objective is the limit in distribution ∞ 1 HR sn2 n 1[0,a] 0 ∞ ds −−−→ n→∞ 1[0,a] (Hs )ds 0 This almost follows from Theorem 3.1.2. The problem is that 1[0,a] (Xs )ds is not a continuous function of the process X, and this is for two reasons. First, because of the indicator function, and second, because the topology is uniform convergence on compacts and not on all of R. To overcome the second we argue that for any ε there is an A such that ∞ 1[0,a] P A 1 HR sn2 n ds = 0 <ε Indeed, in order for the height function to visit [0, na] after time n2 A the total size of the [na] sub-critical trees attached to the backbone up to height [na] must be at least [n2 A]. This probability is small for A sufficiently large, even if the trees are replaced by [na] critical trees. Thus it suffices to prove that for every A A 1[0,a] 0 1 HR sn2 n A dist. ds −−−→ n→∞ 1[0,a] (Hs )ds (3.5.4) 0 Next we deal with the discontinuity of 1[0,a] by a standard argument. We may bound fε ≤ 1[0,a] ≤ gε where fε , gε are continuous and coincide with 1[0,a] outside of [a − ε, a + ε]. Define the operators A Fε (X) = A fε (Xs )ds, 0 Gε (X) = gε (Xs )ds 0 89 3.5. Level estimates Then we have a sandwich Fε 1 HR sn2 n A ≤ 1[0,a] 0 1 HR sn2 n 1 HR sn2 n ds ≤ Gε and similarly for Hs . By continuity of the operators Fε 1 HR sn2 n dist. −−−→ Fε (Hs ), Fε n→∞ In the limit we have 1 HR sn2 n dist. −−−→ Fε (Hs ) n→∞ a.s. Gε (Hs ) − Fε (Hs ) −−−→ 0 ε→0 and since Gε − Fε is continuous we also have for any δ > 0 lim lim P Gε ε→0 n→∞ 1 HR sn2 n − Fε 1 HR sn2 n >δ =0 Combining these bounds implies (3.5.4), and thus (3.5.1). We now turn to the proof of (3.5.2). From (3.5.1), we know that for any η > 0, ∞ 1 dist. 1 1[a,a+η] (Hs )ds C[an, (a + η)n] − − − → n→∞ η 0 ηn2 Thus, (3.5.2) will follow if we can prove that for any η > 0, we have the following limit in probability as n → ∞: ηnC[an] − C[an, (a + η)n] P →0 ηn2 (3.5.5) For a given vertex v, let hv denote the height of v. If v is not on the backbone, we let perc(v) be the percolation parameter of the off-backbone percolation cluster to which v belongs. We now single out the vertex on the backbone at height [an], and group together vertices at height [an] which correspond to the same percolation parameter. More precisely, if w1 , w2 , w3 , ..., wNn are the distinct values taken by the W -process up to time [na], we let Cn(wi ) := {v ∈ IPC \ BB : hv = [an], perc(v) = wi } so that Nn C (wi ) ∪ BB[an] , C[an] := {v ∈ IPC : hv = [an]} = C[an] = #C[an] i=1 90 3.5. Level estimates Moreover, any vertex between heights [an] and [(a + η)n] in the IPC descends from one of the vertices of C[an]. We let Pn(wi ) := v ∈ IPC \ BB : [an] ≤ hv ≤ (a + η)n, ∃w ∈ C (wi ) s.t. w ≤ v BB[an] Pn := v ∈ IPC : [an] ≤ hv ≤ (a + η)n, BB[an] ≤ v (w ) (w ) In particular, Cn i ⊂ Pn i and vertices of the backbone between heights BB [an] and [(a + η)n] are contained in Pn [an] . Moreover, BB[an] C[an, (a + η)n] := {v ∈ IPC : [an] ≤ hv ≤ (a + η)n} = Pn Nn Pn(wi ) ∪ i=1 However, the number of distinct values of percolation parameters which one sees at height [an] remains bounded with arbitrarily high probability. Claim 3.5.2. For any > 0, there is A > 0 such that, for any n ∈ N, P #{i ∈ {1, ..., Nn } : Cn(wi ) = 0} > A ≤ From [3, Proposition 3.1], the number of distinct values the W -process takes between [na]/2 and [na] is bounded, uniformly in n, with arbitrarily high probability. Furthermore, it is well known that with arbitrarily high probability, among [na]/2 critical Galton-Watson trees, the number which reach height [na]/2 is bounded, uniformly in n. It follows that the number of clusters rising from the backbone at heights {0, ..., [na]/2} and which possess vertices at height [na] is, with arbitrarily high probability, also bounded for all n. The claim follows. Claim 3.5.3. For any η > 0, in probability, lim n→∞ 1 BB[an] Pn =0 ηn2 BB Fix η. We observe that Pn [an] is bounded by the total progeny up to height ηn, of ηn critical Galton-Watson trees. If |B| denotes a reflected Brownian motion, and lt0 (|B|) its local time at 0 up to t, we then deduce from a convergence result for a sequence of such trees (cf formula (7) of [32]) that for any > 0, lim sup P n→∞ 1 BB[an] Pn > ηn2 ≤P 1 inf{t > 0 : lt0 (|B|) > η} > η and the claim follows from the fact that inf{t > 0 : lt0 (|B|) > u}, u ≥ 0 is a half stable subordinator. 91 3.5. Level estimates Claim 3.5.4. For any t ∈ (0, a), η > 0, in probability, (W ) (W ) Pn [nt] #(Cn [nt] ) − =0 ηn2 n lim n→∞ Fix t, η, and define wn := W[nt] . We have (w ) P (wn ) Pn n #(Cn − ηn2 n ) > (w ) ≤P #(Cn(wn ) ) [ >n −2 +P −2 n] = k)P k=[ 2 n] ) (wn ) (w ) P(#(Cn(wn ) ) + (wn ) Pn n #(Cn − 2 ηn n #(Cn Pn n − 2 ηn n , #(Cn(wn ) ) < > ) > 2 n #(Cn(wn ) ) = k Using a comparison to critical trees as in the previous argument, the first two terms in the sum above go to 0 as n → ∞. Furthermore, from [19, Corollary 2.5.1], we know that, conditionally on the processes W , L, for any u > 0, the level sets of [un] subcritical Galton-Watson trees with branching law Bin(σ, wn ) converge to the local time process of a reflected drifted Brownian motion (|Xs | , s ≥ 0), with drift L(t), stopped at τu . Therefore, for any u > 0, (w ) lim P n→∞ =P 1 η τu ) > #(Cn(wn ) ) = [nu] 1[0,η] (|Xs |)ds − lt0 (|X|) > 0 > 0, goes to 0 as η → 0. Thus by dominated convergence, which for any [ −2 n] P(#(C (wn ) ) = k) lim lim sup η→0 n→∞ (wn ) Pn n #(Cn − 2 ηn n k=[ 2 n] (w ) ·P Pn n #(C (wn ) ) − > ηn2 n #(C (wn ) ) = k = 0 Claim 3.5.4 follows. 92 3.5. Level estimates From our decompositions of C[an, (a+η)n], C[an], and claims 3.5.2, 3.5.3, and 3.5.4, we now deduce (3.5.5). This implies (3.5.2), and completes the proof of Proposition 3.5.1. Proof of Corollary 3.5.1. From (3.5.2), the corollary will be proven if we a (H) as the righthand side of (3.5.3). Note that, if manage to express γ4 l∞ ltx √ γ 2 H denotes the local time up to time t at level x of √ γ 3 H = Yt − Y t 2 2 then √ √γ γ 2 a γ a lt (H) = l 4 2 t √ so that we may as well express √ γ γ 2 a 2 lt √ γ H 2 √ γ 2 H . √ γ To reach this goal, it is convenient to decompose the path of 2 H according to the excursions above the origin of Y − Y . Let us introduce a few notations. We let F(R+ , R) denote the space of real-valued finite paths, so that excursions of Y and of Y − Y are elements of F(R+ , R). For a path e ∈ F(R+ , R), we define e := sups≥0 e(s), e := inf s≥0 e(s). For c ≥ 0, we let N (−c) denote the excursion measure of drifted Brownian motion with drift −c away from the origin, and n(−c) that of reflected drifted Brownian motion with drift −c above the origin (see for example [40, chapter VI.8]). Lemma 3.5.2. For any c > 0, a > 0, we have 2c exp(2ca) − 1 c N (−c) (e < −a) = 1 − exp(−2ca) n(−c) (e > a) = (3.5.6) (3.5.7) This result is well known, and can be proven by using basic properties of drifted Brownian motion and excursion measures. We are now going to determine the excursions of Y − Y which give a a (H). We may and will choose −Y to be the non-zero contribution to γ4 l∞ local time process at 0 of Y − Y . Using excursion theory (see for instance [40, section VI.8.55]), we know that for this normalization of local time, conditionally on the L-process, the excursions of Y − Y form an inhomogeneous Poisson point process P in the space R+ × F(R+ , R+ ) with intensity ds × n(−L(s)) . 93 3.5. Level estimates For b ≥ 0, let τb denote the hitting time of b by −Y . Note that for any s > τb , −Y s > b, from the fact that drifted Brownian motion started at 0 instantaneously visits √ the negative half line. We therefore observe that the √ γ γ last visit to 2 a by 2 H is at time τa√γ . Hence, any point of P whose first √ coordinate is larger than a γ corresponds to a part of the path of H which a (H). Moreover, a lies strictly above a,√and therefore can not contribute to l∞ γ part of the path of 2 H which corresponds to an excursion of Y −Y starting √ γ at a time s < τa√γ will only reach height 2 a whenever the supremum of this √ excursion is greater or equal than 12 (a γ − Y s ). Therefore, any excursion of a (H) corresponds to a point Y − Y which gives a nonzero contribution to l∞ √ of P whose first coordinate is some s, such that s ≤ a γ, and whose second √ coordinate is an excursion e such that e ≥ 21 (a γ − s). These considerations, along with properties of Poisson point processes, lead to the following claim. Claim 3.5.5. Conditionally on the L-process, the excursions of Y −Y which √ √ γ γ √ a γ a (H) = 2 give a nonzero contribution to γ4 l∞ are points of a 2 l∞ 2 H Poisson point process P ⊂ P on R+ × F(R+ , R+ ) with intensity 1 √ 1[0,a√γ] (s) 1 e ≥ (a γ − s) 2 ds × n−L(s) (·) The number of points of P clearly is almost surely countable, so we may write P = (si , ei )i∈Z+ . In particular, by (3.5.6), (si )i∈Z+ are the points of √ the Poisson point process on [0, a γ] introduced in Corollary 3.5.1. Note that {ei , i ∈ Z+ } correspond√obviously to distinct excursions of γ Y − Y , so that their contributions to l∞2 a √ γ 2 H are independent. Claim 3.5.6. Conditionally given L, for each i ∈ Z+ the contribution of √ γ the excursion ei to l∞2 a √ γ 2 H is exponentially distributed with parameter 1 √ N (−L(s)) ei ≤ (−a γ + si ) 2 Fix i ∈ Z+ , and condition on L. Recall that (si , ei ) is one of the points of the Poisson process P, so that ei is chosen according to the measure √ √ n(−L(si )) · , e > 12 (a γ − si ) . Up to the time at which ei reaches 12 (a γ − √ γ a √ γ si ), ei does not contribute to l∞2 2 H . From the Markov property √ 1 (−L(s )) i under n · , e > 2 (a γ − si ) , the remaining part of ei (after it has 94 3.5. Level estimates √ reached 12 (a γ − si ) follows the path of a drifted Brownian motion, with √ drift −L(si ), started at 21 (a γ −√si ), and stopped when it gets to the origin. γ Thus, the contribution of ei to l∞2 a √ γ 2 H is exactly the local time of this √ level 12 (a γ −si ). By shifting vertically, stopped drifted Brownian motion at 0 (X), the total local time at the origin of X, a drifted Brownian it is also l∞ motion, with drift −L(si ), started at the origin and stopped when reaching √ 1 ˜ 2 (−a γ + si ). By excursion theory, if Pi is a Poisson point process on 0 (X) is the coordinate R+ × F(R+ , R) with intensity ds × N (−L(si )) , then l∞ ˜i which falls into the set of the first point of P 1 √ R+ × e ∈ F(R+ , R) : e < (−a γ + si ) 2 Claim 3.5.6 follows. From Lemma 3.5.2, Claim 3.5.5 (along with the remark which follows it), and Claim 3.5.6, we deduce Corollary 3.5.1. 95 Chapter 4 Exponential growth of ponds in invasion percolation on regular trees1 4.1 4.1.1 Introduction and definitions The model: invasion percolation, ponds and outlets Consider an infinite connected locally finite graph G, with a distinguished vertex o, the root. On each edge, place an independent Uniform[0, 1] edge weight, which we may assume (a.s.) to be all distinct. Starting from the subgraph C0 = {o}, inductively grow a sequence of subgraphs Ci according to the following deterministic rule. At step i, examine the edges on the boundary of Ci−1 , and form Ci by adjoining to Ci−1 the edge whose weight is minimal. The infinite union ∞ C= Ci (4.1.1) i=1 is called the invasion cluster. Invasion percolation is closely related to ordinary (Bernoulli) percolation. For instance, ([14] for G = Z d ; later greatly generalized by [24]) if G is quasitransitive, then for any p > pc , only a finite number of edges of weight greater than p are ever invaded. On the other hand, it is elementary to show that for any p < pc , infinitely many edges of weight greater than p must be invaded. In other words, writing ξi for the weight of the ith invaded edge, we have lim sup ξi = pc (4.1.2) i→∞ 1 A version of this chapter has been submitted for publication: Jesse Goodman. Exponential growth of ponds in invasion percolation on regular trees. arXiv:0912.5205v1 [math.PR], 2009. 96 4.1. Introduction and definitions So invasion percolation produces an infinite cluster using only slightly more than critical edges, even though there may be no infinite cluster at criticality. The fact that invasion percolation is linked to the critical value pc , even though it contains no parameter in its definition, makes it an example of self-organized criticality. Under mild hypotheses (see section 4.3.1), the invasion cluster has a natural decomposition into ponds and outlets. Let e1 ∈ C be the edge whose weight Q1 is the largest ever invaded. For n > 1, en is the edge in C whose weight Qn is the highest among edges invaded after en−1 . We call en the nth outlet and Qn the corresponding outlet weight. Write Vˆn for the step at which en was invaded, with Vˆ0 = 0. The nth pond is the subgraph of edges invaded at steps i ∈ (Vˆn−1 , Vˆn ]. Suppose an edge e, with weight p, is first examined at step i ∈ (Vˆn−1 , Vˆn ]. (That is, i is the first step at which e is on the boundary of Ci−1 .) Then we have the following dichotomy: either • e will be invaded as part of the nth pond (if p ≤ Qn ); or • e will never be invaded (if p > Qn ) This implies that the ponds are connected subgraphs and touch each other only at the outlets. Moreover, the outlets are pivotal in the sense that any infinite non-intersecting path in C starting at o must pass through every outlet. Consequently C is decomposed as an infinite chain of ponds, connected at the outlets. In this paper we take G to be a regular tree and analyze the asymptotic behaviour of the ponds, the outlets and the outlet weights. This problem can be approached in two directions: by considering the ponds as a sequence and studying the growth properties of that sequence; or by considering a fixed pond and finding its asymptotics. We will see that the sequence of ponds grows exponentially, with exact exponential constants. For a fixed pond, its asymptotics correspond to those of ordinary percolation with a logarithmic correction. These computations are based on representing C in terms of the outlet weights Qn , as in [3]. Conditional on (Qn )∞ n=0 , each pond is an independent percolation cluster with parameter related to Qn . In particular, the fluctuations of the ponds are a combination of fluctuations in Qn and the additional randomness. Surprisingly, in all but the large deviation sense, the asymptotic behaviour for the ponds is controlled by the outlet weights alone: the remaining randomness after conditioning only on (Qn )∞ n=0 disappears in the limit, 97 4.1. Introduction and definitions and the fluctuations are attributable solely to fluctuations of Qn . 4.1.2 Known results The terminology of ponds and outlets comes from the following description (see [42]) of invasion percolation. Consider a random landscape where the edge weights represent the heights of channels between locations. Pour water into the landscape at o; then as more and more water is added, it will flow into neighbouring areas according to the invasion percolation mechanism. The water level at o, and throughout the first pond, will rise until it reaches the height of the first outlet. Once water flows over an outlet, however, it will flow into a new pond where the water will only ever rise to a lower height. Note that the water level in the nth pond is the height (edge weight) of the nth outlet. The edge weights may also be interpreted as energy barriers for a random walker exploring a random energy landscape: see [36]. If the energy levels are highly separated, then (with high probability and until some large time horizon) the walker will visit the ponds in order, spending a long time in each pond before crossing the next outlet. In this interpretation the growth rate of the ponds determines the effect of entropy on this analysis. See the extended discussion in [36]. Invasion percolation is also related to the incipient infinite cluster (IIC), at least in the cases G = Z2 ([27]) and G a regular tree: see, e.g., [27], [3] and [15]. For a cylinder event E, the law of the IIC can be defined by def PIIC (E) = lim Ppc (E | o ↔ ∂B(k)) k→∞ (4.1.3) or by other limiting procedures, many of which can be proved to be equivalent to each other. Both the invasion cluster and the IIC consist of an infinite cluster that is “almost critical”, in view of (4.1.2) or (4.1.3) respectively. For G = Z2 ([27]) and G a regular tree ([3]), the IIC can be defined in terms of the invasion cluster: if Xk denotes a vertex chosen uniformly from among the invaded vertices within distance k of o, and τXk E denotes the translation of E when o is sent to Xk , then PIIC (E) = lim P (τXk E) k→∞ (4.1.4) Surprisingly, despite this local equivalence, the invasion cluster and the IIC are globally different: they are mutually singular and, at least on the regular tree, have different scaling limits, although they have the same scaling exponents. 98 4.1. Introduction and definitions The regular tree case, first considered in [39], was studied in great detail in [3]. Any infinite non-intersecting path from o must pass through every outlet; on a tree, this implies that there is a backbone, the unique infinite nonintersecting path from o. In [3] a description of the invasion cluster was given in terms of the forward maximal weight process, the outlet weights indexed by height along the backbone (see section 4.3.2). This parametrization in terms of the external geometry of the tree allowed the calculation of natural geometric quantities, such as the number of invaded edges within a ball. In the following, we will see that when information about the heights is discarded, the process of edge weights takes an even simpler form. The detailed structural information in [3] was used in [4] to identify the scaling limit of the invasion cluster (again for the regular tree). Since the invasion cluster is a tree with a single infinite end, it can be encoded by its Lukaciewicz path or its height and contour functions. Within each pond, the scaling limit of the Lukaciewicz path is computed, and the different ponds are stitched together to provide the full scaling limit. The two-dimensional case was also studied in a series of papers by van den Berg, Damron, J´ arai, Sapozhnikov and V´agv¨olgyi ([42], [16] and [15]). There they study, among other things, the probability that the nth pond extends a distance k from o, for n fixed. For n = 1 this is asymptotically of the same order as the probability that a critical percolation cluster extends a distance k, and for n > 1 there is a correction factor (log k)n−1 . Furthermore an exponential growth bound for the ponds is given. This present work was motivated in part by the question of what the corresponding results would be for the tree. Quite remarkably, they are essentially the same, suggesting that a more general phenomenon may be involved. In the results and proofs that follow, we shall see that the sequence of outlet weights plays a dominant role. Indeed, all of the results in Theorems 4.2.1–4.2.4 are proved first for Qn , then extended to other pond quantities using conditional tail estimates. Consequently, all of the results can be understood as consequences of the growth mechanism for the sequence Qn . On the regular tree, we are able to give an exact description of the sequence Qn in terms of a sum of independent random variables (see section 4.3.3). In more general graphs, this representation cannot be expected to hold exactly. However, the similarities between the between the pond behaviours, even on graphs as different as the tree and Z2 , suggest that an approximate analogue may hold. Such a result would provide a unifying explanation for both the exponential pond growth and the asymptotics of a fixed pond, even on potentially quite general graphs. 99 4.1. Introduction and definitions 4.1.3 Summary of notation We will primarily consider the case where G is the forward regular tree of degree σ: namely, the tree in which the root o has degree σ and every other vertex has degree σ + 1. The weight of the ith invaded edge is ξi . The nth outlet is en and its edge weight is Qn . We may naturally consider en to be an oriented edge en = (v n , v n ), where v n is invaded before v n . The step at which en is invaded is denoted Vˆn and the (graph) distance from o to v n is ˆ n . Setting Vˆ0 = L ˆ 0 = 0 for convenience, we write Vn = Vˆn − Vˆn−1 and L ˆ ˆ Ln = Ln − Ln−1 . There is a natural geometric interpretation of Ln as the length of the part of the backbone in the nth pond, and Vn as the volume (number of edges) of the nth pond. In particular Vˆn is the volume of the union of the first n ponds. Rn is the length of the longest upward-pointing path in the nth pond, and Rn is the length of the longest upward-pointing path in the union of the first n ponds. We shall later work with the quantity δn ; for its definition, see (4.3.8). We note the following elementary relations: n ˆn = L n Li , i=1 Vˆn = Vi i=1 (4.1.5) n Qn+1 < Qn , Ln ≤ Rn ≤ Rn ≤ Ri i=1 Probability laws will generically be denoted P. For p ∈ [0, 1], Pp denotes the law of Bernoulli percolation with parameter p. For a set A of vertices, the event {x ↔ A} means that there is a path of open edges joining x to some point of A, and {x ↔ ∞} means that there is an infinite non-intersecting path of open edges starting at x. We define the percolation probability θ(p) = Pp (o ↔ ∞) and pc = inf {p : θ(p) > 0}. ∂B(k) denotes the vertices at distance exactly k from o. (x) For non-zero functions f (x) and g(x), we write f (x) ∼ g(x) if lim fg(x) = 1; the point at which the limit is to be taken will usually be clear from the context. We write f (x) g(x) if there are constants c and C such that cg(x) ≤ f (x) ≤ Cg(x). 100 4.2. Main results 4.2 4.2.1 Main results Exponential growth of the ponds Let Zn denote the 7-tuple ˆ n, Zn = log (Qn − pc )−1 , log Ln , log L log Rn , log Rn , 21 log Vn , 12 log Vˆn and write (4.2.1) ✶ = (1, 1, 1, 1, 1, 1, 1). Theorem 4.2.1. With probability 1, Zn =✶ (4.2.2) n→∞ n denotes a standard Brownian motion then lim Theorem 4.2.2. If (Bt )t≥0 Z Nt − Nt · ✶ √ N ⇒ (Bt · ✶)t≥0 (4.2.3) t≥0 as N → ∞, with respect to the metric of uniform convergence on compact intervals of t. These theorems say that each component of Z satisfies a law of large numbers and functional central limit theorem, with the same limiting Brownian motion for each component. Theorem 4.2.2 shows that the logarithmic scaling in Theorem 4.2.1 cannot be replaced by a linear rescaling such as en (Qn − pc ). Indeed, log((Qn − √ pc )−1 ) has characteristic additive fluctuations of order ± n,√ and therefore Qn − pc fluctuates by a multiplicative factor of the form e± n . As n → ∞ this will be concentrated at 0 and ∞, causing tightness to fail. Theorem 4.2.3. n1 log (Qn − pc )−1 satisfies a large deviation principle on [0, ∞) with rate n and rate function ϕ(u) = u − log u − 1 (4.2.4) 1 n 1 log Ln , n1 log Rn and 2n log Vn satisfy large deviation principles on [0, ∞) with rate n and rate function ψ, where ψ(u) = u − log u − 1 log(2) − u if u ≥ if u ≤ 1 2 1 2 (4.2.5) It will be shown that ψ arises as the solution of the variational problem ψ(u) = inf ϕ(v) + v − u v≥u (4.2.6) 101 4.2. Main results 4.2.2 Tail behaviour of a pond Theorems 4.2.1–4.2.3 describe the growth of the ponds as a sequence. We now consider a fixed pond and study its tail behaviour. Theorem 4.2.4. For n fixed and → 0+ , k → ∞, 2σ P (Qn < pc (1 + )) ∼ σ−1 n−1 log −1 (n − 1)! (4.2.7) and n−1 ˆ n > k ∼ 2σ (log k) P (Ln > k) ∼ P L σ − 1 k(n − 1)! (log k)n−1 P (Rn > k) P Rn > k k n−1 (log k) √ P (Vn > k) P Vˆn > k k (4.2.8) (4.2.9) (4.2.10) Using the well-known asymptotics 2σ 2 (p − pc ) σ−1 2σ Ppc (o ↔ ∂B(k)) ∼ (σ − 1)k θ(p) ∼ as p → p+ c (4.2.11) as k → ∞ (4.2.12) we may rewrite (4.2.7)–(4.2.10) as n−1 log −1 P (Qn < pc (1 + )) ∼ θ(pc (1 + )) (n − 1)! n−1 ˆ n > k ∼ (log k) P (Ln > k) ∼ P L Ppc (o ↔ ∂B(k)) (n − 1)! P (Rn > k) P Rn > k (log k)n−1 Ppc (o ↔ ∂B(k)) P (Vn > k) P Vˆn > k (log k)n−1 Ppc (|C(o)| > k) (4.2.13) (4.2.14) (4.2.15) (4.2.16) ˜ n , the maximum distance Working in the case G = Z2 , [16] considers R from o to a point in the first n ponds, which is essentially Rn in our notation. [16, Theorem 1.5] states that ˜ n ≥ k) P(R (log k)n−1 Ppc (o ↔ ∂B(k)) (4.2.17) 102 4.3. Markov structure of invasion percolation and notes as a corollary ˜ n ≥ k) P(R n−1 Ppc (o ←→ ∂B(k)) (4.2.18) i where ↔ denotes a percolation connection where up to i edges are allowed to be vacant (“percolation with defects”). (4.2.18) suggests the somewhat plausible heuristic of approximating the union of the first n ponds by the set of vertices reachable by critical percolation with at most n − 1 defects. Indeed, the proof of (4.2.17) uses in part a comparison to percolation with defects. By contrast, on the tree the following result holds: Theorem 4.2.5. For fixed n and k → ∞, n Ppc (o ↔ ∂B(k)) k −2 −n (4.2.19) The dramatic contrast between (4.2.18) and (4.2.19) can be explained in terms of the number of large clusters in a box. In Z2 , a box of side length S has generically only one cluster of diameter of order S. On the tree, by contrast, there are many large clusters. Indeed, a cluster of size N has of order N edges on its outer boundary, any one of which might be adjacent to another large cluster, independently of every other edge. Percolation with defects allows the best boundary edge to be chosen, whereas invasion percolation is unlikely to invade the optimal edge. 4.2.3 Outline of the paper Section 4.3.1 states a Markov property for the outlet weights that is valid for any graph. From section 4.3.2 onwards, we specialize to the case where G is a regular tree. In section 4.3.2 we recall results from [3] that describe the structure of the invasion cluster conditional on the outlet weights Qn . Section 4.3.3 analyzes the Markov transition mechanism of section 4.3.1 and proves the results of Theorems 4.2.1–4.2.3 for Qn . Section 4.4.1 states conditional tail bounds for Ln , Rn and Vn given Qn . The rest of sections 4.4–4.6 use these tail bounds to prove Theorems 4.2.1–4.2.4. The proof of the bounds in section 4.4.1 is given in section 4.7. Finally, section 4.8 gives the proof of Theorem 4.2.5. 4.3 Markov structure of invasion percolation In section 4.3.1 we give sufficient conditions for the existence of ponds and outlets, and state a Markov property for the ponds, outlets and outlet 103 4.3. Markov structure of invasion percolation weights. Section 4.3.2 summarizes some previous results from [3] concerning the structure of the invasion cluster. Finally in section 4.3.3 we analyze the resulting Markov chain in the special case where G is a regular tree and prove the results of Theorems 4.2.1–4.2.3 for Qn . 4.3.1 General graphs: ponds, outlets and outlet weights The representation of an invasion cluster in terms of ponds and outlets is guaranteed to be valid under the following two assumptions: θ(pc ) = 0 (4.3.1) and lim sup ξi = pc a.s. (4.3.2) i→∞ (4.3.1) is known to hold for many graphs and is conjectured to hold for any transitive graph for which pc < 1 ([8, Conjecture 4]; see also, for instance, [33, section 8.3]). If the graph G is quasi-transitive, (4.3.2) follows from the general result [24, Proposition 3.1]. Both (4.3.1) and (4.3.2) hold when G is a regular tree. The assumption (4.3.1) implies that w.p. 1, sup ξi > pc for all i0 (4.3.3) i>i0 since otherwise there would exist somewhere an infinite percolation cluster at level pc . We can then make the inductive definition Q1 = max ξi = ξVˆ1 (4.3.4) i>0 Qn = max ξi = ξVˆn i>Vˆn−1 (n > 1) (4.3.5) since (4.3.2) and (4.3.3) imply that the maxima are attained. Condition on Qn , en , and the union C˜n of the first n ponds. We may naturally consider en to be an oriented edge en = (v n , v n ) where the vertex v n was invaded before v n . The condition that en is an outlet, with weight Qn , implies that there must exist an infinite path of edges with weights at most Qn , starting from v n and remaining in G\C˜n . However, the law of the edge weights in G\C˜n is not otherwise affected by Qn , en , C˜n . In particular we have Pq (en ↔ ∞ in G\C˜n ) P Qn+1 < q Qn , en , C˜n = PQn (en ↔ ∞ in G\C˜n ) (4.3.6) 104 4.3. Markov structure of invasion percolation on the event {q ≤ Qn }. In (4.3.6) we can replace G\C˜n by the connected component of G\C˜n that contains en . 4.3.2 Geometric structure of the invasion cluster: the regular tree case In [3, section 3.1], the same outlet weights are studied, parametrized by height rather than by pond. Wk is defined to be the maximum invaded edge weight above the vertex at height k along the backbone. A key point in the analysis in [3] is the observation that (Wk )∞ k=0 is itself a Markov process. Wk is constant for long stretches, corresponding to k in the same pond, and the jumps of Wk occur when an outlet is encountered. The relation between the two processes is given by Wk = Qn iff ˆ n−1 ≤ k < L ˆn L (4.3.7) From (4.3.7) we see that the (Qn )∞ n=0 are the successive distinct values ∞ ˆ ˆ of (Wk )k=0 , and Ln = Ln − Ln−1 is the length of time the Markov chain Wk spends in state Qn before jumping to state Qn+1 . In particular, Ln is geometric conditional on Qn , with some parameter depending only on Qn . As we will refer to it often, we define δn to be that geometric parameter: P ( Ln > m | Qn ) = (1 − δn )m (4.3.8) A further analysis (see [3, section 2.1]) shows that the off-backbone part of the nth pond is a sub-critical Bernoulli percolation cluster with a parameter depending on Qn , independently in each pond. We summarize these results in the following theorem. th Theorem 4.3.1 ([3], sections 2.1 and 3.1). Conditional on (Qn )∞ n=1 , the n pond of the invasion cluster consists of 1. Ln edges from the infinite backbone, where Ln is geometric with parameter δn ; and 2. emerging along the σ − 1 sibling edges of each backbone edge, independent sub-critical Bernoulli percolation clusters with parameter pc (1 − δn ) (4.3.9) Given (Qn )∞ n=0 , the ponds are conditionally independent for different n. δn is a continuous, strictly increasing functions of Qn and satisfies δn ∼ σ−1 θ(Qn ) ∼ σ(Qn − pc ) 2σ (4.3.10) 105 4.3. Markov structure of invasion percolation as Qn → p+ c . The meaning of (4.3.10) is that δn = f (Qn ) where f (q) ∼ σ−1 2σ θ(q) ∼ σ(q − pc ) as q → p+ . c It is not at first apparent that the geometric parameter δn in (4.3.8) is the same quantity that appears in (4.3.9), and indeed [3] has two different notations for the two quantities: see [3, equations (3.1) and (2.14)]. Combining equations (2.3), (2.5), (2.14) and (3.1) of [3] shows that they are equivalent to δn = 1 − σQn (1 − Qn θ(Qn ))σ−1 (4.3.11) For σ = 2 we can find explicit formulas for these parameters: pc = 21 , θ(p) = p−2 (2p − 1) for p ≥ pc , δn = 2Qn − 1 and pc (1 − δn ) = 1 − Qn . However, all the information needed for our purposes is contained in the asymptotic relation (4.3.10). 4.3.3 The outlet weight process The representation (4.3.6) simplifies dramatically when G is a regular tree. Then the connected component of G\C˜n containing en is isomorphic to G, with en corresponding to the root. Therefore the dependence of Qn+1 on en and C˜n is eliminated and we have the following result. Corollary 4.3.2. On the regular tree, the process (Qn )∞ n=1 forms a timehomogeneous Markov chain with P(Q1 < q) = θ(q) and P Qn+1 < q Qn = q = (4.3.12) θ(q ) θ(q) (4.3.13) for pc < q < q. Equations (4.3.12) and (4.3.13) say that, conditional on Qn , Qn+1 is chosen from the same distribution, conditioned to be smaller. In terms of (Wk )∞ k=0 , (4.3.13) describes the jumps of Wk when they occur, and indeed the transition mechanism (4.3.13) is implicit in [3]. Since θ is a continuous function, it is simpler to consider θ(Qn ): θ(Q1 ) is uniform on [0, 1] and P θ(Qn+1 ) < u θ(Qn ) = u = u u (4.3.14) 106 4.4. Law of large numbers and central limit theorem for 0 < u < u. But this is equivalent to multiplying θ(Qn ) by an independent Uniform[0, 1] variable. Noting further that the negative logarithm of a Uniform[0, 1] variable is exponential of mean 1, we have proved the following proposition. Proposition 4.3.3. Let Ui , i ∈ N, be independent Uniform[0, 1] random variables. Then, as processes, θ(Qn ) n=1 ∞ n ∞ d = (4.3.15) Ui i=1 n=1 Equivalently, with Ei = log Ui−1 independent exponentials of mean 1, n −1 log θ(Qn ) d = Ei (4.3.16) i=1 jointly for all n. Corollary 4.3.4. The triple Zn = log θ(Qn )−1 , log (Qn − pc )−1 , log δn−1 (4.3.17) satisfies the conclusions of Theorems 4.2.1 and 4.2.2, and each component of n1 Zn satisfies a large deviation principle with rate n and rate function ϕ(u) = u − log u − 1 (4.3.18) Proof. The conclusions about log θ(Qn )−1 follow from the representation (4.3.16) in terms of a sum of independent variables; the rate function ϕ is given by Cram´er’s theorem. The other results then follow from the asymptotic relation (4.3.10). 4.4 4.4.1 Law of large numbers and central limit theorem Tail bounds for pond statistics Theorem 4.3.1 expressed Ln , Rn and Vn as random variables whose parameters are given in terms of Qn . Their fluctuations are therefore a combination of fluctuations arising from Qn , and additional randomness. The following proposition gives bounds on the additional randomness. Recall that δn is a certain function of Qn with δn ∼ σ(Qn − pc ): see Theorem 4.3.1. 107 4.4. Law of large numbers and central limit theorem Proposition 4.4.1. There exist positive constants C, c, s0 , γL , γR , γV such that Ln , Rn and Vn satisfy the conditional bounds P ( δn Ln ≥ S| δ) ≤ Ce−cS P ( δn Ln ≤ s| δ) ≤ Cs (4.4.1) P ( δn Rn ≤ s| δ) ≤ Cs √ P δn2 Vn ≤ s δ ≤ C s (4.4.2) P ( δn Ln ≤ s| δ) ≥ cs on {δn ≤ γL s} (4.4.4) P ( δn Rn ≤ s| δ) ≥ cs √ P δn2 Vn ≤ s δ ≥ c s on {δn ≤ γR s} (4.4.5) −cS P ( δn Rn ≥ S| δ) ≤ Ce P δn2 Vn −cS ≥ S δ ≤ Ce (4.4.3) for all n and all S, s > 0; and on δn2 ≤ γV s (4.4.6) for s ≤ s0 . The proofs of (4.4.1)–(4.4.6), which involve random walk and branching process estimates, are deferred to section 4.7. 4.4.2 A uniform convergence lemma Because Theorem 4.2.2 involves weak convergence of several processes to the same joint limit, it will be convenient to use Skorohod’s representation theorem and almost sure convergence. The following uniform convergence result will be used to extend convergence from one set of coupled random variables (δn,N ) to another (Xn,N ): see section 4.4.3. Lemma 4.4.2. Suppose {Xn,N }n,N ∈N and {δn,N }n,N ∈N are positive random variables such that δn,N is decreasing in n for each fixed N , and for positive constants a, β and C, a P(δn,N Xn,N > S) ≤ CS −β (4.4.7) a P(δn,N Xn,N < s) ≤ Csβ (4.4.8) for all S and s. Define n ˆ n,N = X Xi,N (4.4.9) i=1 Then for any T > 0 and α > 0, w.p. 1, lim max N →∞ 1≤n≤N T a X log(δn,N n,N ) Nα = lim max N →∞ 1≤n≤N T a X ˆ n,N ) log(δn,N Nα = 0 (4.4.10) 108 4.4. Law of large numbers and central limit theorem Proof. Let P > 0 be given. For a fixed N , (4.4.7) implies max a X ˆ n,N ) log(δn,N 1≤n≤N T Nα a ˆ n,N > eN α P δn,N X ≤ > 1≤n≤N T n α a P δn,N Xi,N > ≤ 1≤n≤N T i=1 n ≤ α a δi,N Xi,N P 1≤n≤N T i=1 n Cnβ e−βN ≤ 1≤n≤N T i=1 2+β −βN α ≤ (N T ) eN n Ce eN > n α (4.4.11) where we used δi,N ≥ δn,N in the third inequality. But then, noticing that ∞ 2+β Ce−βN α < ∞, the Borel-Cantelli lemma implies N =1 (N T ) lim sup max a X ˆ n,N ) log(δn,N Nα N →∞ 1≤n≤N T ≤ (4.4.12) a.s. Similarly, (4.4.8) implies P max 1≤n≤N T a X log(δn,N n,N ) Nα <− a P δn,N Xn,N < e−N ≤ 1≤n≤N T −βN α ≤ N T Ce so that lim inf max 4.4.3 (4.4.13) a X log(δn,N n,N ) N →∞ 1≤n≤N T a.s. Since α > 0 was arbitrary and Xn,N ≥− (4.4.14) Nα ˆ n,N , (4.4.10) follows. ≤X Proof of Theorems 4.2.1–4.2.2 The conclusions about Qn are contained in Corollary 4.3.4. The other conclusions will follow from Lemma 4.4.2. From Corollary 4.3.4, we may apply Skorohod’s representation theorem to produce realizations of the ponds for each N ∈ N, coupled so that log δ −1 − N t N t ,N √ → (Bt )0≤t≤T (4.4.15) N 0≤t≤T 109 4.5. Large deviations: proof of Theorem 4.2.3 a.s. as N → ∞. Then the relation 1 a log δ −1 log δ aN t ,N X log Xn,N − N t N t ,N − N t = + N 1/2 N 1/2 aN 1/2 N t ,N (4.4.16) shows that a1 log Xn will satisfy a central limit theorem as well, with the same ˆ n . We will successively set limiting Brownian motion. The same holds for X Xn,N = Ln,N with a = 1 (4.4.17) Xn,N = Rn,N with a = 1 (4.4.18) Xn,N = Vn,N with a = 2 (4.4.19) The bounds (4.4.7)–(4.4.8) follow immediately from the bounds in Proposiˆ tion 4.4.1. This proves Theorem 4.2.2 for Ln and Vn . For Rn , the quantity R ˆn is not the one that appears in Theorem 4.2.2, but the bound Rn ≤ Rn ≤ R implies the result for Rn as well. The lemma also implies the law of large numbers results (4.2.2), by taking T = 1 and using the same ponds for every N . 4.5 Large deviations: proof of Theorem 4.2.3 In this section we present a proof of the large deviation results in Theorem 4.2.3. As in section 4.4, we prove a generic result using a variable Xn and tail estimates. Theorem 4.2.3 then follows immediately using Corollary 4.3.4 and Proposition 4.4.1. Note that Proposition 4.5.1 uses the full strength of the bounds in Proposition 4.4.1. Proposition 4.5.1. Suppose that δn and Xn are positive random variables such that, for positive constants a, β, c, C, γ, s0 , P ( δna Xn > S| δn ) ≤ Ce−cS β (4.5.1) P ( δna Xn < s| δn ) ≤ Cs1/a (4.5.2) P ( δna Xn < s| δn ) ≥ cs1/a (4.5.3) for all S and s, and on the event {δna < γs}, for s ≤ s0 . Suppose also that n1 log δn−1 satisfies a large deviation principle with rate n on [0, ∞) with rate function ϕ such 110 4.5. Large deviations: proof of Theorem 4.2.3 that ϕ(1) = 0, ϕ is continuous on (0, ∞), and ϕ is decreasing on (0, 1] and 1 increasing on [1, ∞). Then an log Xn satisfies a large deviation principle with rate n on [0, ∞) with rate function ψ(u) = inf ϕ(v) + v − u v≥u (4.5.4) Proof. It is easy to check that ψ is continuous, decreasing on [0, 1] and increasing on [1, ∞), ψ(1) = 0, and ψ(u) = ϕ(u) for u ≥ 1. So it suffices to show that 1 1 log Xn > u = − inf ϕ(v) (4.5.5) lim log P v>u n→∞ n an for u > 0 and 1 log P n→∞ n 1 log Xn < u an lim for 0 < u < 1. For (4.5.5), let P 1 log Xn > u an = −ψ(u) (4.5.6) > 0. Then 1 log δn−1 > u − n 1 1 +P log δn−1 ≤ u − , log Xn > u n an 1 1 ≤P log δn−1 > u − +P log(δna Xn ) > n an 1 βan ≤P log δn−1 > u − + Ce−ce (4.5.7) n ≤P where we used (4.5.1) with S = ean . The last term in (4.5.7) is superexponentially small, so (4.5.7) and the large deviation principle for n1 log δn−1 imply 1 1 lim sup log P log Xn > u ≤ − inf ϕ(v) (4.5.8) v>u− an n→∞ n On the other hand, P 1 log Xn > u an ≥P ≥P 1 1 log δn−1 > u + , log(δna Xn ) > − n an 1 log δn−1 > u + (1 − Ce−n ) (4.5.9) n using (4.5.2) with s = e−an . So lim inf n→∞ 1 log P n 1 log Xn > u an ≥ − inf ϕ(v) v>u+ (4.5.10) 111 4.5. Large deviations: proof of Theorem 4.2.3 Since ϕ is continuous and > 0 was arbitrary, this proves (4.5.5). For (4.5.6), let u ∈ (0, 1) be given and choose v ∈ (u, 1), ∈ (0, u). Then for n sufficiently large we have P 1 log Xn < u an 1 1 log δn−1 < v, log(δna Xn ) < u − v n an 1 (4.5.11) ≥ P v − < log δn−1 < v ce−n(v−u) n ≥P v− < Here we used (4.5.3) with s = e−an(v−u) . Note that if n is large enough then s ≤ s0 and the condition δna < γs follows from v − < n1 log δn−1 . Therefore, since ϕ is decreasing on (0, 1], lim inf n→∞ 1 log P n 1 log Xn < u an ≥− inf v− <w<v ϕ(w) − (v − u) = −ϕ(v) − a(v − u) (4.5.12) (4.5.12) was proved for u < v < 1. However, since ϕ is continuous and the function −ϕ(v) − av is decreasing in v for v ≥ 1, (4.5.12) holds for all v ≥ u. So take the supremum over v ≥ u to obtain lim inf n→∞ 1 log P n 1 log Xn < u an ≥ −ψ(u) (4.5.13) Finally P 1 log Xn < u an 1 1 1 ≤P log δn−1 ≤ u + E 1 log δn−1 > u P log Xn < u δn n n an 1 =P log δn−1 ≤ u n 1 1 1 +E 1 log δn−1 > u P log(δna Xn ) < u − log δn−1 δn n an n −1 1 1 1 ≤P log δn−1 ≤ u + E 1 log δn−1 > u Cen(u− n log δn ) n n (4.5.14) −1 1 (using (4.5.2) with s = ean(u− n log δn ) ). Apply Varadhan’s lemma (see, e.g., 112 4.6. Tail asymptotics [17, p. 32]) to the second term of (4.5.14): lim n→∞ 1 log E 1 n −1 1 1 log δn−1 > u Cen(u− n log δn ) n = sup(u − v − ϕ(v)) = −ψ(u) (4.5.15) v>u Therefore lim sup n→∞ 1 log P n 1 log Xn < u an ≤ max {−ϕ(u), −ψ(u)} = −ψ(u) (4.5.16) which completes the proof. 4.6 Tail asymptotics In this section we prove the fixed-pond asymptotics from Theorem 4.2.4. Proof of (4.2.7). Recall from (4.3.16) that log θ(Qn )−1 has the same distribution as a sum of n Exponential variables of mean 1, i.e., a Gamma variable with parameters n, 1. So P(θ(Qn ) < ) = P log θ(Qn )−1 > log ∞ xn−1 −x e dx (n − 1)! = log −1 P(θ(Qn ) < ) = (4.6.1) −1 : Make the substitution x = (1 + u) log log −1 (n − 1)! −1 n ∞ (1 + u)n−1 e−u log −1 (4.6.2) 0 Then Watson’s lemma (see for instance (2.13) of [34]) implies that n−1 P(θ(Qn ) < ) ∼ log −1 (n − 1)! (4.6.3) and so (4.3.10) gives n−1 P(Qn < pc (1 + )) ∼ 2σ log −1 (σ − 1)(n − 1)! (4.6.4) 113 4.6. Tail asymptotics Combining (4.6.3) with (4.3.10) implies at once that P (δn < ) −1 n−1 (log ) (4.6.5) We use (4.6.5) to prove (4.2.9)–(4.2.10) using the following lemma. Lemma 4.6.1. Let δn be a random variable satisfying (4.6.5). Suppose a, β are positive constants such that aβ > 1, and Xn is any positive random variable satisfying P ( δna Xn > S| δ) ≤ CS −β (4.6.6) for all S, n > 0, and P ( δna Xn > s0 | δ) ≥ p0 ˆ n = n Xi . Then for some s0 , p0 > 0. Write X i=1 P(Xn > k) (4.6.7) (log k)n−1 k 1/a ˆn > k P X (4.6.8) as k → ∞. Proof. From (4.6.7) and (4.6.5), we have the lower bound P(Xn > k) ≥ P δna Xn > s0 δn < s0 k −1/a P(δn < s0 k −1/a ) ≥ c1 (log k)n−1 k 1/a (4.6.9) For the upper bound, P(Xn > k) ≤ P(δn < k −1/a ) + E ✶(δn ≥k−1/a ) P ( δna Xn > kδna | δn ) (log k 1/a )n−1 +E k 1/a (log k)n−1 = C3 + CE k 1/a ✶(δn ≥k−1/a ) C(kδna )−β ≤ C2 (log k)n−1 +C ≤ C3 k 1/a ∞ dr δn ∞ dr k−1/a k −β r−aβ−1 ✶(k−1/a ≤δn <r) aβ + 1 k −β r−aβ−1 P(δn < r) aβ + 1 (4.6.10) Use (4.6.5) and make the substitution r = k −1/a (1 + u) to obtain P(Xn > k) ≤ C3 ≤ (log k)n−1 k 1/a (log k)n−1 C4 + 1/a 1/a k k ∞ C3 + C5 0 ∞ du (1 + u)−aβ log(k 1/a (1 + u)) n−1 0 du (1 + u)−aβ 1 + a log(1 + u) log k n−1 (4.6.11) 114 4.6. Tail asymptotics The last integral in (4.6.11) is bounded as k → ∞ since aβ > 1, which proves the upper bound for Xn . ˆ n , assume inductively that we have the bound To extend (4.6.8) to X n−1 ˆ n > k) P(X (log k) /k 1/a . (The case n = 1 is already proved since ˆ 1 = X1 .) The bound P(X ˆ n+1 > k) ≥ P(Xn+1 > k) is immediate, and we X can estimate ˆ n+1 > k ≤ P Xn+1 > k − k + P X ˆn > k P X (4.6.12) where we set k = k/(log k)a/2 . Then k − k ∼ k and log(k − k ) ∼ log k ∼ log k, so that (log k)n P Xn+1 > k − k (4.6.13) k 1/a while (log k )n−1 (log k)n−1/2 ˆn > k P X (4.6.14) k 1/a (k )1/a which is of lower order. This completes the induction. Proof of (4.2.9)–(4.2.10). These relations follow immediately from (4.6.5) and Lemma 4.6.1; the bounds (4.6.6)–(4.6.7) are immediate consequences of Proposition 4.4.1. As in section 4.4.3, the asymptotics for Rn follow from ˆn. ˆ n and the bound Rn ≤ Rn ≤ R the asymptotics for R Proof of (4.2.8). For Ln , we can use the exact formula P ( Ln > k| δn ) = (1 − δn )k . Write δn = g(θ(Qn )), where g(p) is a certain continuous and + increasing function. By (4.3.10), g(p) ∼ σ−1 2σ p as p → 0 ; we will use the bound g(p) ≥ cp for some constant c > 0. Noting as above that log θ(Qn )−1 is a Gamma random variable, we compute P(Ln > k) = 1 = (n − 1)! 1 (n − 1)! ∞ k 1 − g(e−x ) xn−1 e−x dx 0 k 1 − g(y/k) k (log k − log y)n−1 0 (log k)n−1 = k(n − 1)! ∞ 0 ✶(y ≤ k) 1 − g(y/k) k 1− dy k log y log k n−1 dy (4.6.15) after the substitution e−x = y/k. But the integral in (4.6.15) converges σ−1 ∞ 2σ to 0 e− 2σ y dy = σ−1 as k → ∞: pointwise convergence follows from σ−1 g(p) ∼ 2σ p, and we can uniformly bound the integrand using 1 − g(y/k) k ≤ e−kg(y/k) ≤ e−cy (4.6.16) 115 4.7. Pond bounds: proof of Proposition 4.4.1 ˆ n extends (4.2.8) to Lastly, a simple modification of the argument for X ˆ n. L 4.7 Pond bounds: proof of Proposition 4.4.1 In this section we prove the tail bounds (4.4.1)–(4.4.6). Since the laws of Ln , Rn and Vn do not depend on n except through the value of δn , we will omit the subscript in this section. For convenient reference we recall the structure of the bounds: P ( δ a X > S| δ) ≤ Ce−cS a (4.7.1) P ( δ X < s| δ) ≤ Cs (4.7.2) P ( δ a X < s| δ) ≥ cs1/a (4.7.3) for all S and s, and on the event {δ a < γs}, for s ≤ s0 . We have a = 1 for X = L and X = R, and a = 2 for X = V . In (4.7.3) it is necessary to assume δ a < γs. This is due only to a discretization effect: if X is any N-valued random variable, then necessarily P ( δ a X < s| δ) = 0 whenever δ a ≥ s. Indeed, the bounds (4.4.4)–(4.4.6) can be proved with γ = 1, although it is not necessary for our purposes. Note that, by proper choice of C and s0 , we can assume that S is large in (4.7.1) and s is small in (4.7.2) and (4.7.3). Since we only consider N-valued random variables X, we can assume δ is small in (4.7.2), say δ < 1/2 (otherwise take s < (1/2)a without loss of generality). Moreover, Theorem 4.3.1 shows that L, R and V are all stochastically decreasing in δ. Consequently it suffices to prove (4.7.1) for δ small, say δ < 1/2. Finally the constraint δ a < γs0 makes δ small in (4.7.3) also. We note for subsequent use the inequalities (1 − x)y ≤ e−xy (4.7.4) 1 − (1 − x)y ≤ 1 − e−2xy ≤ 2xy (4.7.5) for x ∈ (0, 1), y > 0 and for x ∈ (0, 1/2), y > 0, which follow from log(1 − x) ≤ −x for x ∈ (0, 1) and log(1 − x) ≥ −2x for x ∈ (0, 1/2). 116 4.7. Pond bounds: proof of Proposition 4.4.1 4.7.1 The backbone length L: proof of (4.4.1) and (4.4.4) From Theorem 4.3.1, L is a geometric random variable with parameter δ. So P ( L > S/δ| δ) = (1 − δ) ≤ e−δ S/δ ≤ e−S+δ ≤ e−S+1 S/δ (4.7.6) since δ ≤ 1, proving (4.7.1). For (4.7.2) and (4.7.3), we have P ( L < s/δ| δ) = 1 − (1 − δ) For δ ≤ 1 2 s/δ −1 (4.7.7) we can use (4.7.5) to get P ( L < s/δ| δ) ≤ 2δ( s/δ − 1) ≤ 2s (4.7.8) which proves (4.7.2). For (4.7.3), take γL = 1/2. Then on the event {δ < γL s} we have s/δ ≥ 3 so that expanding (4.7.7) as a binomial series gives P ( L < s/δ| δ) ≥ ( s/δ − 1) δ − 1 ( s/δ − 1) ( s/δ − 2) δ 2 2 1 ≥ (s − δ) − s(s − δ) 2 s s s ≥ 1− ≥ 2 2 4 (4.7.9) for s ≤ 1 = s0 . So (4.7.3) holds. 4.7.2 The pond radius R: proof of (4.4.2) and (4.4.5) Conditional on δ and L, R is the maximum height of a percolation cluster with parameter pc (1 − δ) started from a path of length L. We have R ≥ L so (4.7.2) follows immediately from the corresponding bound for L. R is stochastically dominated by ˜i L + max R 1≤i≤L (4.7.10) ˜ i is the maximum height of a branching process with offspring diswhere R tribution Binomial(σ, pc (1 − δ)) started from a single vertex, independently for each i. Define ˜i > k δ ak = P R (4.7.11) 117 4.7. Pond bounds: proof of Proposition 4.4.1 for k > 0. Thus ak is the probability that the branching process survives to generation k + 1. By comparison with a critical branching process, ak ≤ C1 k (4.7.12) for some constant C1 . On the other hand, ak satisfies ak+1 = 1 − f (1 − ak ) (4.7.13) where f (z) is the generating function for the offspring distribution of the branching process. (This is a reformulation of the well-known recursion for the extinction probability.) In particular, since f (z) ≤ f (1) = σpc (1 − δ) = 1 − δ, ak+1 ≤ f (1)ak = ak (1 − δ) (4.7.14) Combining (4.7.12) with (4.7.14), C1 −δj e k ak+j ≤ ak (1 − δ)j ≤ (4.7.15) and taking k = S/2δ ≥ S/2δ, j = S/δ − S/2δ ≥ S/2δ − 2, P ˜i > S δ R δ =a ≤ S/δ ≤ 2C1 δ δ(S/2δ−2) e S C2 δe−c3 S S (4.7.16) Using this estimate we can compute P R> S δ δ ≤P L> ≤ C4 e−c5 S S S ˜ S δ + P L ≤ ,R for some i ≤ S/2δ δ i > 2δ 2δ 2δ S C6 δe−c7 S + ≤ C8 e−c9 S (4.7.17) 2δ S Similarly P R< s s ˜ s s δ ≥ P L < ,R for all i < δ i < δ 2δ 2δ 2δ s/2δ C11 δe−c12 s ≥ c10 s 1 − ≥ c13 s s (4.7.18) provided δ is sufficiently small compared to s, i.e., provided γR is small enough. 118 4.7. Pond bounds: proof of Proposition 4.4.1 4.7.3 The pond volume V : proof of (4.4.3) and (4.4.6) From Theorem 4.3.1, conditional on δ and L, V is the number of edges in a percolation cluster with parameter pc (1 − δ), started from a path of length L and with no edges emerging from the top of the path. We can express V in terms of the return time of a random walk as follows. Start with an edge configuration with L backbone edges marked as occupied. Mark as unexamined the (σ − 1)L edges adjacent to the backbone, not including the edges emerging from the top. At each step, take an unexamined edge (if any remain) and either (1) with probability 1 − pc (1 − δ), mark it as vacant; or (2) with probability pc (1 − δ), mark it as occupied and mark its child edges as unexamined. Let Nk denote the number of unexamined edges after k steps. Then it is easy to see that Nk is a random walk Nk = N0 + ki=1 Yi (at least until Nk = 0) where N0 = (σ − 1)L and Yi = σ−1 −1 w.p. pc (1 − δ) w.p. 1 − pc (1 − δ) (4.7.19) Let T = inf {k : Nk = 0}. (T is finite a.s. since E ( Yi | δ) = −δ < 0 and Nk can jump down only by 1.) T counts the total number of off-backbone edges examined, namely the number of non-backbone edges in the cluster and on its boundary, not including the edges from the top of the backbone. Consequently T = [V − L] + [(σ − 1)V + σ] − σ = σV − L (4.7.20) In order to apply random walk estimates we write Xi = Yi +δ, Zk = ki=1 Xi , so that E ( Xi | δ) = 0; c1 ≤ E Xi2 δ ≤ C2 for universal constants c1 , C2 ; and Nk = Zk − kδ + (σ − 1)L. Note that {V > V0 } = {T > σV0 − L} ⊆ Z σV0 −L > δ σV0 − L − (σ − 1)L (4.7.21) so using, for instance, Freedman’s inequality [21, Proposition 2.1] leads after some computation to P ( V > S0 L/δ| δ, L) ≤ P Z ≤ exp − L(σS0 −δ)/δ L2 (σS0 − 2δ > L(σS0 − 2δ − σ + 1) δ, L − σ + 1)2 2(σL(σS0 − 2δ − σ + 1) + C2 L(σS0 − δ)/δ) ≤ exp −c3 S0 Lδ(1 − 2/S0 )2 ≤ exp(−c4 S0 Lδ) (4.7.22) 119 4.7. Pond bounds: proof of Proposition 4.4.1 if S0 ≥ 3, say. Then, setting S0 = S/δL, P V > S/δ 2 δ ≤ P ( L > S/3δ| δ) + P ( V > S0 L/δ, L ≤ S/3δ| δ) ≤ C5 e−c6 S + exp (−c4 (S/δL)Lδ) ≤ C7 e−c8 S (4.7.23) which proves (4.7.1). For (4.7.2), apply Freedman’s inequality again: P V ≤ s/δ 2 δ, L = P T ≤ σs/δ 2 − L δ, L =P ≤P min (Zk − kδ) ≤ −(σ − 1)L δ, L k≤σs/δ 2 −L min Zk ≤ −(L − δ(σs/δ 2 )) δ, L k≤σs/δ 2 ≤ exp − (L − σs/δ)2 2(σ(L − σs/δ) + C9 s/δ 2 ) ≤ exp −c(δL − σs)2 /s (4.7.24) (4.7.25) (where in the denominator of (4.7.24) we use L ≤ s/δ 2 since V ≥ L). So P V ≤ s/δ 2 δ ≤ P ( L < 2σs/δ| δ) +E ✶(L≥2σs/δ) exp −c(δL − σs)2 /s δ (4.7.26) The first term in (4.7.26) is at most C10 s from (4.4.1) and will therefore be √ negligible compared to s. For the second term, note that for L ≥ σs/δ, ∞ exp −c(δL − σs)2 /s = σs/δ ✶(l>L) 2cδ(δl − σs) −c(δl−σs)2 /s e dl s (4.7.27) √ and so, with the substitution x s = δl − σs, E ✶(L≥2σs/δ) exp −c(δL − σs)2 /s δ ∞ = 2c P ( L < l| δ) σs/δ ∞ δ(δl − σs) −c(δl−σs)2 /s e dl s √ x s + σs 2 δ xe−cx dx P L< δ ∞ √ √ 2 (x s + σs)xe−cx dx ≤ C12 s = 2c 0 ≤ C11 (4.7.28) 0 which proves (4.7.2) 120 4.8. Percolation with defects Finally, for (4.7.3), the Berry-Esseen inequality (see for instance [20, Theorem 2.4.9]) implies P √ Zk < −x k C13 E Xi2 δ δ − Φ(−x) ≤ √ k (4.7.29) where Φ(x) = P(G < x) for G a standard Gaussian, and C13 is some absolute constant. In particular, using 0 < c1 ≤ E Xi2 δ , √ P Zk < −(σ − 1) k δ ≥ c14 > 0 (4.7.30) for k ≥ C15 . Choose γV = 1 ∧ γL2 ∧ (C15 + 1)−1 . Then we have s/δ 2 ≥ 1 √ √ (so we may bound σs/δ 2 − s/δ ≥ s/δ 2 ); s/δ ≤ γL ; and s/δ 2 ≥ C15 , so that P V < s/δ 2 δ = P T < σs/δ 2 − L δ √ √ ≥ P T < σs/δ 2 − s/δ, L < s/δ δ √ ≥ P T < s/δ 2 , L < s/δ δ ≥P Z < δ s/δ 2 − (σ − 1)L, L < s/δ 2 ≥ P Z s/δ2 < −(σ − 1) √ ≥ c16 s √ s/δ δ √ s/δ 2 δ P L < s/δ δ (4.7.31) proving (4.7.3). 4.8 Percolation with defects In this section we prove n Ppc (o ↔ ∂B(k)) −n k −2 (4.8.1) The case n = 0 is a standard branching process result. For n > 0, proceed by induction. Write C(o) for the percolation cluster of the root o. The lower bound follows from the following well-known estimate: Ppc (|C(o)| > N ) N −1/2 (4.8.2) If C(o) > N then there are at least N vertices v1 , . . . , vN on the outer boundary of C(o), any one of which may have a connection to ∂B(k) with 121 4.8. Percolation with defects n − 1 defects. As a worst-case estimate we may assume that v1 , . . . , vN are still at distance k from ∂B(k), so that by independence we have n−1 n Ppc (o ↔ ∂B(k)) ≥ Ppc (|C(o)| > N ) 1 − 1 − Ppc o ↔ ∂B(k) c1 −n+1 N ≥√ 1 − (1 − c2 k −2 ) N N (4.8.3) −n+1 for constants c1 , c2 . If we set N = k 2 then the second factor is of order 1, and the lower bound is proved. For the upper bound, use a slightly stronger form of (4.8.2) (see for instance [23, p. 260]): Ppc (|C(o)| = N ) (N + 1)−3/2 (4.8.4) Now if C(o) = N , with N ≤ k/2, then there are at most σN vertices on the outer boundary of C(o), one of which must have a connection with n − 1 defects of length at least k − N ≥ k/2. So n Ppc (o ↔ ∂B(k)) ≤ Ppc (|C(o)| > k/2) k/2 n−1 Ppc (|C(o)| = N ) 1 − 1 − Ppc 0 ↔ ∂B(k/2) + σN N =0 ∞ c3 c4 −n+1 ≤√ + 1− 1 − c5 k −2 3/2 k N =0 (N + 1) c3 ≤√ + k −n+1 N <k2−n+1 −1 ≤ c3 k −2 σN c6 k −2 N + 3/2 (N + 1) −n+1 + c7 k 2 c4 N −3/2 N ≥k2−n+1 −1/2 (4.8.5) which proves the result (the first term is an error term if n ≥ 2 and combines with the second if n = 1). 122 Chapter 5 Conclusion On the regular tree, there is an exact duality between super-critical percolation conditioned to be finite, and (unconditioned) sub-critical percolation with a certain dual parameter. Consequently the invasion cluster is decomposed as a backbone together with sub-critical percolation clusters. This representation, together with a scaling analysis of the process of maximal edge weights, yields a very complete scaling picture of the cluster. In particular, asymptotic formulas for the r-point functions, level sizes and volume growth have been obtained (chapter 2, [3]), the full scaling limit of the cluster (chapter 3, [4]), and finally the pond and outlet structure (chapter 4, [22]). 5.1 Open questions Because of its dynamic definition and the infinitely many edge weights that arise in its analysis, invasion percolation requires detailed knowledge about near-critical percolation across a range of parameters. For this reason questions about invasion percolation are likely to be more difficult than the analogous questions about percolation. This has shown to be the case so far; and indeed many of the (presumed) results about super-critical percolation that would be needed to analyze invasion percolation in other graphs are not known. 5.1.1 High-dimensional lattices A main goal would be to extend the regular tree results to Zd , for d above the critical dimension dc = 6 (or dc = 4 in the oriented setting). On the tree, the absence of loops means that distinct branches of the invasion cluster do not interact, producing independence across branches and allowing many exact calculations to be made. In high-dimensional Zd , loops can exist, but critical (fractal) objects should be unlikely to form loops on a large scale. Thus, different parts of the invasion cluster should behave almost independently, as on the tree, and the scaling should be the same as in the tree (the “mean 123 5.1. Open questions field” case). Indeed, the critical dimension has a natural interpretation as the dimension above which certain independent processes generically do not intersect. Analyzing the invasion cluster on Zd faces two principal challenges: estimating the interaction among different parts of the cluster; and controlling the behaviour of finite super-critical percolation. For high-dimensional lattices, the main tool to estimate the interaction has been the lace expansion, originally introduced by Brydges and Spencer [12] and since considerably extended in a variety of contexts: see for instance [41]. The lace expansion for a percolation cluster is based on an inclusionexclusion analysis of percolation configurations. A connection is split across a pivotal bond (a bond, or edge, whose removal would destroy the connection) and the configuration is considered as two independent partial connections together with higher-order correction terms to account for possible intersections. The higher-order terms are expressed as diagrams, and a priori bounds are used to control their size. For invasion percolation, the cluster has a more complicated structure owing to the different edge weights accepted. This will require a new and more elaborate diagrammatic decomposition of the cluster, involving percolation parameters that are super-critical, but only slightly. Indeed, in all lace expansion work, each new model requires its own expansion, with a form tailored to the structure of the model. At the time of writing, R. van der Hofstad and A. Sapozhnikov have made preliminary progress towards such an expansion. Generally speaking, the lace expansion relies on certain key features to succeed. First is the existence of pivotal bonds, as these are the bonds used to divide the percolation cluster into smaller disjoint parts. Secondly, the dimension of the lattice must be sufficiently high so that the “triangle condition” holds. Finally, in order to complete the analysis the BK inequality must be used to bound complicated configurations in terms of simple ones. For invasion percolation and super-critical percolation, the third condition presents a problem. The basic form of the BK inequality is unavailable for both invasion percolation and finite super-critical percolation clusters. The reason is that both models involve a combination of increasing and decreasing events. For finite super-critical percolation, the finiteness condition directly involves the absence of connections. On the other hand, for invasion percolation, the edges to be invaded must have sufficiently small weights, but the edges not invaded must have larger weights so that they are uncompetitive. While there are versions of the BK inequality that apply to finite super-critical clusters, they involve some loss of information. For instance, 124 5.1. Open questions the probability of two disjoint connections in a finite cluster can be bounded by the product of probabilities for two independent connections, but only one of the connections can be guaranteed to be finite. In the tree, these conditions can be controlled through direct computation, resulting in the dual parameters described in [3]. The other case where invasion percolation has been extensively studied is Z2 , and there the method of planar duality and closed dual circuits allows the required control. Indeed, it is striking that these are the only two cases in which significant progress has been made. 5.1.2 Finite super-critical percolation clusters The second challenge for invasion percolation is to understand finite supercritical percolation clusters. This question is indeed an important open problem in its own right, with intriguing parallels to branching processes. Percolation has an approximate symmetry between the sub-critical and supercritical regimes. For example, the probabilities of a long sub-critical connection, or a long super-critical connection that belongs to a finite cluster, both decay exponentially in the distance. For branching processes there is an exact correspondence (used extensively in [3, 4, 22]) between super-critical branching conditioned to die out and sub-critical branching. For percolation no such corresponding result is known, but symmetry is still expected at the level of critical exponents on the sub- and super-critical sides. Recently, works by G. Kozma and A. Nachmias [30, 31] have derived the critical exponents for point-to-ball connections in critical percolation. A key feature of their work has been its use of “soft” arguments: they make only moderate assumptions such as a certain rate of decay of the two-point function, results that have long been known using lace expansion techniques. (This is to be contrasted with the “hard” analysis required in the lace expansion, where many detailed and complicated bounds are usually required.) In work in progress, O. Gurel-Gurevich and A. Nachmias use similar techniques to analyze the critical exponent for the expected cluster size for finite supercritical percolation. Given the complexity of invasion percolation, adapting such soft arguments would allow considerable simplification. 5.1.3 Ponds and outlets Another viewpoint on invasion percolation is to consider its ponds and outlets. The outlets are the sequence of successively largest-weight edges, and the ponds are the parts of the cluster invaded between the outlets. In [22], we 125 5.2. Summary obtain exponential growth and tail asymptotics for the sizes of the ponds. These results are quite strong, and indeed the tail bounds needed in the proofs are quite moderate. In two dimensions, results by J. van den Berg, M. Damron, A. J´arai, A. Sapozhnikov and B. V´ agv¨ olgyi ([42], [16], [15]) give the analogous growth bounds and tail asymptotics. Quite remarkably, these are virtually the same as on the tree. This similarity suggests that a more general phenomenon is at work, and that in Zd a similar pond-based analysis may be fruitful. In particular, it is natural to ask whether the first pond has volume, diameter, or r-point function comparable to critical percolation. Many of the obstacles pertaining to finite super-critical percolation apply also to any analysis of the ponds. 5.1.4 Random walks with varying drift Finally, the scaling limit for the invasion cluster involved a reflecting random walk whose drift scaled as the reciprocal of the occupation time at 0. Such random walks were considered in [7] for drifts that decayed strictly faster or strictly slower than the reciprocal. The critical case, of which the invasion percolation scaling limit is an example, is less understood. 5.2 Summary The three works in this thesis provide a very extensive analysis of invasion percolation in the case of regular trees. Because of the uniquely symmetric structure of these trees, virtually all natural questions – scaling, mutual singularity, scaling limit, pond structure – can be answered quite exactly. The answers to these questions have also revealed a surprisingly complex structure within the invasion clusters, with a mix of discrete and continuous phenomena. In addition, the methods used to understand the invasion cluster represent an ideal, simplified situation for many other graphs. Particularly, the methods of proof give a clear framework for the kind of questions and results to prove in other graphs, such as high-dimensional lattices. On the other hand, the analysis of the invasion cluster relies heavily on the tree structure. In particular, the exact analysis of the outlet weights, which underlies all of the reasoning in all three papers, is specific to the regular tree. There is at this time no strategy for analyzing the evolution of the outlet weights as a process on any other graphs. Furthermore, many of 126 5.2. Summary the underlying super-critical percolation facts remain unproven and indeed may be out of reach with current methods. All in all, invasion percolation presents a beautiful, but quite challenging, model. It involves some of the most difficult aspects of super-critical percolation that test the limits of major methods. The research in this thesis sheds light on the mechanisms involved, but at the same time show how much more there is to understand. 127 Bibliography [1] D. Aldous. Asymptotic fringe distributions for general families of random trees. Annals of Applied Probability, 1(2):228–266, 1991. [2] Kenneth S. Alexander. Percolation and minimal spanning forests in infinite graphs. Annals of Probability, 23(1):87–104, 1995. [3] Omer Angel, Jesse Goodman, Frank den Hollander, and Gordon Slade. Invasion percolation on regular trees. Annals of Probability, 36(2):420– 466, 2008. [4] Omer Angel, Jesse Goodman, and Mathieu Merle. Scaling limit of the invasion percolation cluster on a regular tree. arXiv:0910.4205v1 [math.PR], 2009. [5] Martin T. Barlow, Antal A. J´arai, Takashi Kumagai, and Gordon Slade. Random walk on the incipient infinite cluster for oriented percolation in high dimensions. Communications in Mathematical Physics, 278(2):385–431, 2008. [6] Martin T. Barlow and Takashi Kumagai. Random walk on the incipient infinite cluster on trees. Illinois Journal of Mathematics, 50(1):33–65, 2006. [7] Iddo Ben-Ari, Mathieu Merle, and Alexander Roitershtein. A random walk on Z with drift driven by its occupation time at zero. Stochastic Processes and their Applications, 119(8):2682–2710, 2009. [8] Itai Benjamini and Oded Schramm. Percolation beyond Zd , many questions and a few answers. Electronic Communications in Probability, 1:71–82, 1996. [9] Patrick Billingsley. Convergence of probability measures. Wiley series in probability and mathematical statistics. Wiley, 1968. [10] R. M. Blumenthal. Excursions of Markov processes. Probability and its applications. Birkh¨ auser, 1992. 128 Bibliography [11] S. R. Broadbent and J. M. Hammersley. Percolation processes. Mathematical Proceedings of the Cambridge Philosophical Society, 53(3):629– 641, 1957. [12] David Brydges and Thomas Spencer. Self-avoiding walk in 5 or more dimensions. Communications in Mathematical Physics, 97(1–2):125– 148, 1985. [13] J. T. Chayes, L. Chayes, and R. Durrett. Inhomogeneous percolation problems and incipient infinite clusters. Journal of Physics A: Mathematical and General, 20(6):1521–1530, 1987. [14] J. T. Chayes, L. Chayes, and C. M. Newman. The stochastic geometry of invasion percolation. Communications in Mathematical Physics, 101(3):383–407, 1985. [15] Michael Damron and Art¨em Sapozhnikov. Outlets of 2D invasion percolation and multiple-armed incipient infinite clusters. arXiv:0903.4496v1 [math.PR], 2009. [16] Michael Damron, Art¨em Sapozhnikov, and B´alint V´agv¨olgyi. Relations between invasion percolation and critical percolation in two dimensions. Annals of Probability, 37(6):2297–2331, 2009. [17] Frank den Hollander. Large Deviations. Fields Institute Monographs. American Mathematical Society, 2000. [18] Thomas Duquesne. Continuum tree limit for the range of random walks on regular trees. Annals of Probability, 33(6):2212–2254, 2005. [19] Thomas Duquesne and Jean-Fran¸cois Le Gall. Random Trees, L´evy Processes and Spatial Branching Processes. Number 281 in Ast´erisque. Soci´et´e Math´ematique de France, 2002. [20] Rick Durrett. Probability: theory and examples. Duxbury Advanced Series. Duxbury, third edition, 2005. [21] David A. Freedman. On tail probabilities for martingales. Annals of Probability, 3(1):100–118, 1975. [22] Jesse Goodman. Exponential growth of ponds in invasion percolation on regular trees. arXiv:0912.5205 [math.PR], 2009. [23] Geoffrey Grimmett. Percolation. Grundlehren der mathematischen Wissenschaften. Springer-Verlag, second edition, 1999. 129 Bibliography [24] O. H¨ aggstr¨ om, Y. Peres, and R. H. Schonmann. Percolation on transitive graphs as a coalescent process: relentless merging followed by simultaneous uniqueness. In Perplexing Problems in Probability: Festschrift in honor of Harry Kesten, pages 69–90. Birkh¨auser, 1999. [25] Takashi Hara and Gordon Slade. Mean-field critical behaviour for percolation in high dimensions. Communications in Mathematical Physics, 128(2):333–391, 1990. [26] Jean Jacod. Th´eor`emes limite pour les processus, pages 298–409. Springer-Verlag, 1985. [27] Antal A. J´ arai. Invasion percolation and the incipient infinite cluster in 2D. Communications in Mathematical Physics, 236(2):311–334, 2003. [28] Harry Kesten. The incipient infinite cluster in two-dimensional percolation. Probability Theory and Related Fields, 73(3):369–394, 1986. [29] Harry Kesten. Subdiffusive behavior of random walk on a random cluster. Annales de l’Institut Henri Poincar´e (B) Probabilit´es et Statistiques, 22(4):425–487, 1986. [30] Gady Kozma and Asaf Nachmias. The Alexander-Orbach conjecture holds in high dimensions. Inventiones Mathematicae, 178(3):635–654, 2009. [31] Gady Kozma and Asaf Nachmias. Arm exponents in high-dimensional percolation. arXiv:0911.0871, 2010. [32] Jean-Fran¸cois Le Gall. Random trees and applications. Probability Surveys, 2:245–311, 2005. [33] Russell Lyons and Yuval Peres. Probability on trees and networks. In preparation; see http://mypage.iu.edu/˜rdlyons/, 2009. [34] J. D. Murray. Asymptotic Analysis. Number 48 in Applied Mathematical Sciences. Springer-Verlag, 1984. [35] C. M. Newman and D. L. Stein. Spin-glass model with dimensiondependent ground state multiplicity. Physical Review Letters, 72(14):2286–2289, 1994. [36] C. M. Newman and D. L. Stein. Broken ergodicity and the geometry of rugged landscapes. Physical Review E, 51(6):5228–5238, 1995. 130 Bibliography [37] C. M. Newman and D. L. Stein. Ground-state structure in a highly disordered spin-glass model. Journal of Statistical Physics, 82(3–4):1113– 1132, 1996. [38] Bao Gia Nguyen and Wei-Shih Yang. Triangle condition for oriented percolation in high dimensions. Annals of Probability, 21(4):1809–1844, 1993. [39] Bernie Nickel and David Wilkinson. Invasion percolation on the Cayley tree: exact solution of a modified percolation model. Physical Review Letters, 51(2):71–74, 1983. [40] L. C. G. Rogers and David Williams. Diffusions, Markov Processes and Martingales, volume 2 of Cambridge Mathematical Library. Cambridge University Press, second edition, 1994. [41] Gordon Slade. The Lace Expansion and its Applications. Lecture Notes in Mathematics. Springer, 2006. [42] Jacob van den Berg, Antal A. J´arai, and B´alint V´agv¨olgyi. The size of a pond in 2D invasion percolation. Electronic Communications in Probability, 12:411–420, 2007. [43] Remco van der Hofstad. Infinite canonical super-Brownian motion and scaling limits. Communications in Mathematical Physics, 265(3):547– 583, 2006. [44] Remco van der Hofstad, Frank den Hollander, and Gordon Slade. Construction of the incipient infinite cluster for spread-out oriented percolation above 4+1 dimensions. Communications in Mathematical Physics, 231(3):435–461, 2002. [45] Remco van der Hofstad and Gordon Slade. Convergence of critical oriented percolation to super-Brownian motion above 4 + 1 dimensions. Annales de l’Institut Henri Poincar´e (B) Probabilit´es et Statistiques, 39(3):413–485, 2003. [46] David Wilkinson and Jorge F. Willemsen. Invasion percolation: a new form of percolation theory. Journal of Physics A: Mathematical and General, 16(14):3365–3376, 1983. 131
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Invasion percolation on regular trees : structure,...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Invasion percolation on regular trees : structure, scaling limit and ponds Goodman, Jesse Alexander 2010
pdf
Page Metadata
Item Metadata
Title | Invasion percolation on regular trees : structure, scaling limit and ponds |
Creator |
Goodman, Jesse Alexander |
Publisher | University of British Columbia |
Date Issued | 2010 |
Description | Invasion percolation is an infinite subgraph of an infinite connected graph with finite degrees, defined inductively as follows. To each edge of the underlying graph, attach a random edge weight chosen uniformly from [0,1], independently for each edge. Starting from a single vertex, a cluster is grown by adding at each step the boundary edge with least weight. Continue this process forever to obtain the invasion cluster. In the following, we consider the case where the underlying graph is a regular tree: starting from the root, each vertex has a fixed number of children. In chapter 2, we study the structure of the invasion cluster, considered as a subgraph of the underlying tree. We show that it consists of a single backbone, the unique infinite path in the cluster, together with sub-critical percolation clusters emerging at every point along the backbone. By studying the scaling properties of the sub-critical parameters, we obtain detailed results such as scaling formulas for the r-point functions, limiting Laplace transforms for the level sizes and volumes within balls, and mutual singularity compared to the incipient infinite cluster. Chapter 3 gives the scaling limit of the invasion cluster. This is a random continuous tree described by a drifted Brownian motion, with a drift that depends on a certain local time. This representation also yields a probabilistic interpretation of the level size scaling limit. Finally, chapter 4 studies the internal structure of the invasion cluster through its ponds and outlets. These are shown to grow exponentially, with law of large numbers, central limit theorem and large deviation results. Tail asymptotics for fixed ponds are also derived. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-06-14 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-ShareAlike 3.0 Unported |
IsShownAt | 10.14288/1.0071008 |
URI | http://hdl.handle.net/2429/25744 |
Degree |
Doctor of Philosophy - PhD |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2010-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-sa/3.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2010_fall_goodman_jesse.pdf [ 1.36MB ]
- Metadata
- JSON: 24-1.0071008.json
- JSON-LD: 24-1.0071008-ld.json
- RDF/XML (Pretty): 24-1.0071008-rdf.xml
- RDF/JSON: 24-1.0071008-rdf.json
- Turtle: 24-1.0071008-turtle.txt
- N-Triples: 24-1.0071008-rdf-ntriples.txt
- Original Record: 24-1.0071008-source.json
- Full Text
- 24-1.0071008-fulltext.txt
- Citation
- 24-1.0071008.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0071008/manifest