Abstract. Consider a Markov chain on the space of rooted real binary trees that randomly removes leaves and reinserts them on a random edge and suitably rescales the lengths of edges. This chain was introduced by David Aldous who conjectured a diffusion limit of this chain, as the size of the tree grows, on the space of continuum trees. We prove the existence of a process on continuum trees, which via a random time change, displays properties one would expect from the conjectured Aldous diffusion. The existence of our process is proved by considering an explicit scaled limit of a Poissonized version of the Aldous Markov chain running on finite trees. The analysis involves taking limit of a sequence of splitting trees whose age processes converge but the contour process does not. Several formulas about the limiting process are derived.  A Cladogram is an unrooted semi-labeled binary tree. That is to say, every vertex that is not of degree one must have degree three. The vertices of degree one are called leaves which are labeled by {1, 2, . . . , n}, while every other vertex will be called internal vertices. It follows that if such a tree has exactly n leaves, it must have 2n − 3 edges. In [4, 5] Aldous considers the following Markov chain on the space of n-leaf Cladograms. For a precise description we first define two operations on Cladograms closely following [5] , to which we refer the readers for more details. (i) To remove a leaf i. The leaf i is attached by an edge e 1 to a branchpoint b where two other edges e 2 and e 3 are incident. See Figure 1 . Delete edge e 1 and branchpoint b, and then merging the two remaining edges e 2 and e 3 into a single edge e. The resulting tree has 2n − 5 edges. (ii) To add a leaf to an edge f . Create a branchpoint b which splits the edge f into two edges f 2 , f 3 and attach the leaf i to branchpoint b via a new edge f 1 . This restores the number of leaves and edges to the tree. Let τ n denote the finite collection of all n-leaf Cladograms. Let T, T be elements on τ n . Write T ∼ T if T = T and T can be obtained from T by following the two operations above for some choice of i and f . Thus a τ n valued chain can be described by saying: remove leaf i uniformly at random, then pick edge f at random and re-attach i to f . In particular its transition matrix is This leads to a symmetric, aperiodic, and irreducible finite state space Markov chain. Schweinsberg [27] proved that the relaxation time for this chain is O(n 2 ), improving a previous result in [5] . We will refer to this Markov chain as the Aldous Markov chain in the following text. The problem of interest for us in this article is to establish a limiting diffusion for this sequence of Markov chains as n tends to infinity. It is not entirely rigorous at this point what we mean by a limit here. For example, what is our limiting state space? Detailed answers of such questions will be provided later. Roughly, our state space will be the space of continuum trees, i.e., compact metric spaces without loops which support a probability measure on them. Hence we are looking for a continuous Markov process on the space of continuum trees that can be argued as a weak limit of the above sequence of chains. There are some technical problems of working with an unrooted Cladogram. Hence, we will make a small change in the above model and consider Cladograms in which a distinguished vertex in the tree at time zero is marked as root which is never removed and continues as the root of all subsequent trees. Instead of calling Cladograms, we will simply call such trees as rooted binary trees. Please see Section 2 to find formal definitions of the kind of trees we work with. When trees are rooted, it is natural to associate a family structure with it where the root is an ancestor, and every vertex gives rise to a number of children / progeny. We will frequently use this analogy whose meaning will be obvious from the context. 1.1. Poissonization. We now introduce the important concept of Poissonization of the Markov chain described above. One challenging aspect of the Aldous Markov chain on Cladograms is that at every step of the chain the number of leaves remain the same. Things become simpler if we adopt the Poissonized version of the Markov chain: every leaf has an exponential clock with rate 2 attached to it which determines the time of their removal (deaths). Every edge also has an exponential clock of rate 1 at which point a new pair of vertices (an internal point and a leaf connected by a edge) is introduced on that edge. The rate of births and deaths are chosen to accommodate for the fact that there are about twice as many edges as leaves. We will refer to this model as the Poissonized Aldous Markov chain. This Poissonization changes the Markov chain when the number of leaves are finite. However, there are strong reasons to believe that the limiting diffusion for the non-Poissonized chain is equal in law the limiting diffusion of the Poissonized chain via a stochastic change of time. We provide an argument below to make our case. Going back to the Aldous Markov chain (unrooted), consider a branch point b in the tree T. It divides the collection of leaves naturally into three sets. Let X(T) = (X 1 , X 2 , X 3 )(T) denote the vector of proportion of leaves in each set. It can be verified (see Pal [23]) that the Markov chain on Cladograms induce a Markov chain on these vector of proportions, which, when run at n 2 /2 speed, converges in law to a diffusion on the state space {(x 1 , x 2 , x 3 ), x i ≥ 0, x 1 + x 2 + x 3 = 1}. The law of this diffusion is called the Negative-Wright-Fisher or NWF(1/2, 1/2, 1/2). In Pal [23] it is shown that the NWF law can be obtained by considering ratios of squared Bessel processes of negative dimensions. A comprehensive treatment of BESQ processes can be found in the book by Revuz & Yor [26]. This family of one dimensional diffusions is indexed by a single real parameter θ (called the dimension) and are solutions of the stochastic differential equations where β is a one dimensional standard Brownian motion. We denote the law of this process by Q θ x . It can be shown that the above SDE admits a unique strong solution until it hits the origin. The classical model only admits paramater θ to 4 SOUMIK PAL be non-negative. However, an extension, introduced by Göing-Jaeschke & Yor [15] , allows the parameter θ to be negative. It is well known that BESQ process with a nonnegative dimension θ is the diffusion limit, as the number of initial particles go to infinity, of a critical (discrete or continuous time) Galton-Watson tree with a rate of immigration θ. For example, this happens for a continuous time, binary Galton-Watson, every individual dies or reproduces at rate 2 and there is an influx of new members at rate θ. It follows from the same proof that when θ is negative, immigration changes to emigration, i.e., at rate θ, members leave the family until there is no one surviving. The following construction of NWF processes can be found in [23, Theorem 8]. Lemma 1. Let Z = (Z 1 , Z 2 , Z 3 ) be a vector of 3 iid BESQ processes of dimension −1. Let ζ be the sum Then there is a N W F (1/2, 1/2, 1/2) process (µ 1 , µ 2 , µ 3 ) for which the following equality holds: A very similar result holds when instead of considering one branch point we consider several branch points and look into the partition of leaf masses generated by these branch points. The vector of proportions admits a diffusion limit which can obtained via a random time change from independent BESQ processes (of possibly both positive and negative dimensions). Hence it is natural to search for a Markov chain on Cladograms such that leaf masses in partitions generated by branch points converge to BESQ processes. This is exactly what happens for the Poissonized Markov chain since the number of leaves in each partition evolves as an independent Galton-Watson branching process with immigration or emigration. Hence, Theorem 1 gives us the important clue as to the idea of poissonization of the Aldous' chain and the correct value of the rate of emigration which is crucial in the following. More examples of Poissonization can be found in Markov chains like the Wright-Fisher chain whose Poissonized version is a branching process with immigration. The diffusion limit of the former is the Wright-Fisher diffusion and the diffusion limit of the latter is the BESQ process. The time-change relationship between the two can be found in Pal [22] . More reminiscent is the Fleming-Viot model where the Superprocess is the Poissonized version, and the theorem that allows us to obtain the Fleming-Viot from the Superprocess by a time and mass change is called the Perkins Disintegration Theorem (see Etheridge [11]). We end this discussion with an obvious lemma. Lemma 2. Consider an internal vertex on a finite tree on which the Poissonized Aldous chain is running. This internal vertex divides the leaves of the tree in three subtrees rooted at that vertex. One of them contains the original root. Consider the number of leaves in any of the other two parts. The process of total number of leaves in these subtrees follow independent continuous time binary Galton-Watson branching process with a birth and death rate of two and an emigration rate 1 until one of them hits zero. Figure 2 . Coding of a tree 1.2. Coding trees by age. A fundamental concept at the heart of our argument is the so-called age of a random tree. Consider any model of generating a random tree starting with one individual. If after a units of time later the tree survives, then the age of the tree is a. This is particularly useful when we have one time-axis and several trees start sprouting at different points in time. At any given instance of time, we consider the set of trees surviving at that time. Their ages are given by the durations since they have sprouted. In this dynamic situation properties of trees can be described by its age. For example, suppose that the total existing population in a dynamically growing random tree is given by a continuous times Galton-Watson branching process. Then, given its age, one can deduce its size from the conditional distributions of Galton-Watson branching process conditioned to survive up to time a. Now, one can actually code an entire tree by the ages of its various subtrees. We will discuss these ideas in much more detail later in the text. However, to give an idea of our strategy, we provide a simplified informal description below. Consider the image of a finite tree in Figure 2 . The variables {d 1 , . . . , d 7 } will be considered (positive) distances and the variables {q 1 , . . . , q 7 } will be considered as (nonnegative) masses. Now we construct a stochastic process (A 1 , A 2 , A 3 ) as follows: A 1 takes three values d 1 < d 2 < d 7 with probabilities proportional to q 1 , q 2 , and q 7 respectively. Given A 1 the value of A 2 is determined. Case (i) Suppose A 1 = d 1 , we imagine our process enters the first subtree which is marked with dashes. Then, X 2 takes two values d 3 < d 5 with probability proportional to q 3 and q 6 respectively. Case (ii) Suppose A 1 = d 2 , then our process enters the dotted subtree, and A 2 is d 6 with probability one, irrespective of q 6 . Case (iii) Suppose A 1 = d 7 , then A 2 = 0 with probability one. The reader can now guess the distribution of A 3 , given the values of A 1 , A 2 . In fact A 3 = d 4 with probability one if {A 1 = d 1 , A 2 = d 3 }, or zero otherwise.
We refer to a single branch with an atomic measure as a string of beads, see also REF for related structures.
On the Aldous diffusion on Continuum Trees. I
arXiv: Probability
Mathematics