Abstract: This is a set of lecture notes for a course given at the St. Flour summer school in July 2002. The theme of the course is the study of various combinatorial models of random partitions and random trees, and the asymptotics of these models related to continuous parameter stochastic processes. Following is a list of the main topics treated: models for random combinatorial structures, such as trees, forests, permutations, mappings, and partitions; probabilistic interpretations of various combinatorial notions e.g. Bell polynomials, Stirling numbers, polynomials of binomial type, Lagrange inversion; Kingmanâs theory of exchangeable random partitions and random discrete distributions; connections between random combinatorial structures and processes with independent increments: Poisson-Dirichlet limits; random partitions derived from subordinators; asymptotics of random trees, graphs and mappings related to excursions of Brownian motion; continuum random trees embedded in Brownian motion; Brownian local times and squares of Bessel processes; various processes of fragmentation and coagulation, including Kingmanâs coalescent, the additive and multiplicative coalescents
Notes: Lectures from the 32nd Summer School on Probability Theory held in Saint-Flour, July 7â24, 2002, With a foreword by Jean Picard
Abstract: We study fragmentation trees of Gibbs type. In the binary case, we identify the most general Gibbs type fragmentation tree with Aldousâs beta-splitting model, which has an extended parameter range $β>-2$ with respect to the $\rm Beta(β+1,β+1)$ probability distributions on which it is based. In the multifurcating case, we show that Gibbs fragmentation trees are associated with the two-parameter Poisson-Dirichlet models for exchangeable random partitions of $\bN$, with an extended parameter range $0\leα\le 1$, $θ\ge -2α$ and $α<0$, $θ=-mα$, $m\in\bN$.
Abstract: We develop some theory of spinal decompositions of discrete and continuous fragmentation trees. Specifically, we consider a coarse and a fine spinal integer partition derived from spinal tree decompositions. We prove that for a two-parameter Poisson-Dirichlet family of continuous fragmentation trees, including the stable trees of Duquesne and Le Gall, the fine partition is obtained from the coarse one by shattering each of its parts independently, according to the same law. As a second application of spinal decompositions, we prove that among the continuous fragmentation trees, stable trees are the only ones whose distribution is invariant under uniform re-rooting.
Abstract: Starting from a sequence regarded as a walk through some set of values, we consider the associated loop-erased walk as a sequence of directed edges, with an edge from $i$ to $j$ if the loop erased walk makes a step from $i$ to $j$. We introduce a coloring of these edges by painting edges with a fixed color as long as the walk does not loop back on itself, then switching to a new color whenever a loop is erased, with each new color distinct from all previous colors. The pattern of colors along the edges of the loop-erased walk then displays stretches of consecutive steps of the walk left untouched by the loop-erasure process. Assuming that the underlying sequence generating the loop-erased walk is a sequence of independent random variables, each uniform on $[N]:=1, 2, ..., N$, we condition the walk to start at $N$ and stop the walk when it first reaches the subset $[k]$, for some $1 \leq k \leq N-1$. We relate the distribution of the random length of this loop-erased walk to the distribution of the length of the first loop of the walk, via Cayleyâs enumerations of trees, and via Wilsonâs algorithm. For fixed $N$ and $k$, and $i = 1,2, ...$, let $B_i$ denote the event that the loop-erased walk from $N$ to $[k]$ has $i +1$ or more edges, and the $i^th$ and $(i+1)^th$ of these edges are colored differently. We show that given that the loop-erased random walk has $j$ edges for some $1\leq j \leq N-k$, the events $B_i$ for $1 \leq i \leq j-1$ are independent, with the probability of $B_i$ equal to $1/(k+i+1)$. This determines the distribution of the sequence of random lengths of differently colored segments of the loop-erased walk, and yields asymptotic descriptions of these random lengths as $N \to \infty$.
Abstract: We study interacting systems of linear Brownian motions whose drift vector at every time point is determined by the relative ranks of the coordinate processes at that time. Our main objective has been to study the long range behavior of the spacings between the particles in increasing order. For finite systems, we characterize drifts for which the spacing system remains stable, and show its convergence to a unique stationary joint distribution given by independent exponential distributions with varying means. We also study one particular countably infinite system, where only the minimum Brownian particle gets a constant upward drift, and prove that independent and identically distributed exponential spacings remain stationary under the dynamics of such a process. Some related conjectures in this direction have also been discussed.
Abstract: Given any regularly varying dislocation measure, we identify a natural self-similar fragmentation tree as scaling limit of discrete fragmentation trees with unit edge lengths. As an application we obtain continuum random tree limits of Aldousâs beta-splitting models and Fordâs alpha models for phylogenetic trees. This confirms in a strong way that the whole trees grow at the same speed as the mean height of a randomly chosen leaf.
Abstract: A presentation of ItÃŽâÂÂs excursion theory for general Markov processes is given, with several applications to Brownian motion and related processes.
Notes: Special Feature: Award of the 1st Gauss Prize to K. Itô
Abstract: In this paper we study random partitions of 1,...n, where every cluster of size j can be in any of w_j possible internal states. The Gibbs (n,k,w) distribution is obtained by sampling uniformly among such partitions with k clusters. We provide conditions on the weight sequence w allowing construction of a partition valued random process where at step k the state has the Gibbs (n,k,w) distribution, so the partition is subject to irreversible fragmentation as time evolves. For a particular one-parameter family of weight sequences w_j, the time-reversed process is the discrete Marcus-Lushnikov coalescent process with affine collision rate K_i,j=a+b(i+j) for some real numbers a and b. Under further restrictions on a and b, the fragmentation process can be realized by conditioning a Galton-Watson tree with suitable offspring distribution to have n nodes, and cutting the edges of this tree by random sampling of edges without replacement, to partition the tree into a collection of subtrees. Suitable offspring distributions include the binomial, negative binomial and Poisson distributions.
Abstract: This paper collects facts about the number of occupied boxes in the classical balls-in-boxes occupancy scheme with infinitely many positive frequencies: equivalently, about the number of species represented in samples from populations with infinitely many species. We present moments of this random variable, discuss asymptotic relations among them and with related random variables, and draw connections with regular variation, which appears in various manifestations.
Abstract: Kingman derived the Ewens sampling formula for random partitions describing the genetic variation in a neutral mutation model defined by a Poisson process of mutations along lines of descent governed by a simple coalescent process, and observed that similar methods could be applied to more complex models. Möhle described the recursion which determines the generalization of the Ewens sampling formula in the situation when the lines of descent are governed by a Î-coalescent, which allows multiple mergers. Here we show that the basic integral representation of transition rates for the Î-coalescent is forced by sampling consistency under more general assumptions on the coalescent process. Exploiting an analogy with the theory of regenerative partition structures, we provide various characterizations of the associated partition structures in terms of discrete-time Markov chains.
Abstract: The real trees form a class of metric spaces that extends the class of trees with edge lengths by allowing behavior such as infinite total edge length and vertices with infinite branching degree. Aldousâs Brownian continuum random tree, the random tree-like object naturally associated with a standard Brownian excursion, may be thought of as a random compact real tree. The continuum random tree is a scaling limit as N tends to infinity of both a critical Galton-Watson tree conditioned to have total population size N as well as a uniform random rooted combinatorial tree with N vertices. The AldousâBroder algorithm is a Markov chain on the space of rooted combinatorial trees with N vertices that has the uniform tree as its stationary distribution. We construct and study a Markov process on the space of all rooted compact real trees that has the continuum random tree as its stationary distribution and arises as the scaling limit as N tends to infinity of the AldousâBroder chain. A key technical ingredient in this work is the use of a pointed GromovâHausdorff distance to metrize the space of rooted compact real trees.
Abstract: Trees in Brownian excursions have been studied since the late 1980s. Forests in excursions of Brownian motion above its past minimum are a natural extension of this notion. In this paper we study a forest-valued Markov process which describes the growth of the Brownian forest. The key result is a composition rule for binary GaltonâWatson forests with i.i.d. exponential branch lengths. We give elementary proofs of this composition rule and explain how it is intimately linked with Williamsâ decomposition for Brownian motion with drift.
Abstract: We study the asymptotics of the $p$-mapping model of random mappings on $[n]$ as $n$ gets large, under a large class of asymptotic regimes for the underlying distribution $p$. We encode these random mappings in random walks which are shown to converge to a functional of the exploration process of inhomogeneous random trees, this exploration process being derived (Aldous-Miermont-Pitman 2003) from a bridge with exchangeable increments. Our setting generalizes previous results by allowing a finite number of âattracting pointsâ to emerge.
Abstract: We consider Kingmanâs partition structures which are regenerative with respect to a general operation of random deletion of some part. Prototypes of this class are the Ewens partition structures which Kingman characterised by regeneration after deletion of a part chosen by size-biased sampling. We associate each regenerative partition structure with a corresponding regenerative composition structure, which (as we showed in a previous paper) can be associated in turn with a regenerative random subset of the positive halfline, that is the closed range of a subordinator. A general regenerative partition structure is thus represented in terms of the Laplace exponent of an associated subordinator. We also analyse deletion properties characteristic of the two-parameter family of partition structures.
Abstract: The Joyal bijection between doubly-rooted trees and mappings can be lifted to a transformation on function space which takes tree-walks to mapping-walks. Applying known results on weak convergence of random tree walks to Brownian excursion, we give a conceptually simpler rederivation of the Aldous-Pitman (1994) result on convergence of uniform random mapping walks to reflecting Brownian bridge, and extend this result to random p-mappings.
Abstract: We study the inhomogeneous continuum random trees (ICRT) that arise as weak limits of birthday trees. We give a description of the exploration process, a function defined on [0,1] that encodes the structure of an ICRT, and also of its width process, determining the size of layers in order of height. These processes turn out to be transformations of bridges with exchangeable increments, which have already appeared in other ICRT related topics such as stochastic additive coalescence. The results rely on two different constructions of birthday trees from processes with exchangeable increments, on weak convergence arguments, and on general theory on continuum random trees.
Abstract: We define an n-dimensional polytope Pi_n(x), depending on parameters x_i>0, whose combinatorial properties are closely connected with empirical distributions, plane trees, plane partitions, parking functions, and the associahedron. In particular, we give explicit formulas for the volume of Pi_n(x) and, when the x_iâs are integers, the number of integer points in Pi_n(x). We give two polyhedral decompositions of Pi_n(x), one related to order cones of posets and the other to the associahedron.
Abstract: Consider the radial projection onto the unit sphere of the path a d-dimensional Brownian motion W, started at the center of the sphere and run for unit time. Given the occupation measure mu of this projected path, what can be said about the terminal point W(1), or about the range of the original path? In any dimension, for each Borel set A subseteq S^d-1, the conditional probability that the projection of W(1) is in A given mu(A) is just mu(A). Nevertheless, in dimension d>=3, both the range and the terminal point of W can be recovered with probability 1 from mu. In particular, for d>=3 the conditional law of the projection of W(1) given mu is not mu. In dimension 2 we conjecture that the projection of W(1) cannot be recovered almost surely from mu, and show that the conditional law of the projection of W(1) given mu is not mu.
Abstract: This paper reviews known results which connect Riemannâs integral representations of his zeta function, involving Jacobiâs theta function and its derivatives, to some particular probability laws governing sums of independent exponential variables. These laws are related to one-dimensional Brownian motion and to higher dimensional Bessel processes. We present some characterizations of these probability laws, and some approximations of Riemannâs zeta function which are related to these laws.
Abstract: It is well known that the random occupation measure induced by the sample path of a Brownian motion B = (Bt, t ÃÂâÃÂÃÂÃÂÃÂ¥ 0) admits a jointly continuous local time process (Lxt (B); x ÃÂâÃÂÃÂÃÂàÃÂâÃÂÃÂÃÂÃÂ, t ÃÂâÃÂÃÂÃÂÃÂ¥ 0) such that
Abstract: This chapter is inspired by the following quotation from Harrisâs 1952 paper on random walks and trees. "Random walks and branching processes are both objects of considerable interest in probability theory. We may consider a random walk as a probability measure on sequences of steps-that is, on walks. A branching process is a probability measure on trees. The purpose of the present section is to show that walks and trees are abstractly identical objects and to give probabilistic consequences of this correspondence. The identity referred to is nonprobabilistic and is quite distinct from the fact that a branching process, as a Markov process, may be considered in a certain sense to be a random walk, and also distinct from the fact that each step of the random walk, having two possible directions, represents a two fold branching., keywords = imported
Abstract: This chapter reviews Brownian bridge asymptotics for random mappings, first described in 1994 by Aldous and Pitman. The limit distributions as nÃÂâÃÂÃÂÃÂÃÂÃÂâÃÂÃÂÃÂÃÂ, of various functionals of a uniformly distributed random mapping from an n element set to itself, are those of correspondingfunctionals of a Brownian bridge. Similar results known to hold for various non-uniform models of random mappings, accordingto a kind of invariance principle. A mapping Mn : [n] ÃÂâÃÂÃÂÃÂà[n] can be identified with its digraph i ÃÂâÃÂÃÂÃÂàMn(i), i ÃÂâÃÂÃÂÃÂà[n], as in Figure 1.
Abstract: This chapter reviews how various representations of additive coalescent processes, whose state space may be either finite or infinite partitions, can be constructed from random trees and forests. These constructions establish deep connections betweenthe asymptotic behaviour of additive coalescent processes and the theory of Brownian trees and excursions. There are someclose parallels with the theory of multiplicative coalescents and the asymptotics of critical random graphs, described inSection 6.4.
Abstract: Aldous and Pitman (1994) studied asymptotic distributions, as n tends to infinity, of various functionals of a uniform random mapping of a set of n elements, by constructing a mapping-walk and showing these mapping-walks converge weakly to a reflecting Brownian bridge. Two different ways to encode a mapping as a walk lead to two different decompositions of the Brownian bridge, each defined by cutting the path of the bridge at an increasing sequence of recursively defined random times in the zero set of the bridge. The random mapping asymptotics entail some remarkable identities involving the random occupation measures of the bridge fragments defined by these decompositions. We derive various extensions of these identities for Brownian and Bessel bridges, and characterize the distributions of various path fragments involved, using the theory of Poisson processes of excursions for a self-similar Markov process whose zero set is the range of a stable subordinator of index between 0 and 1.
Abstract: The work of Kingman and others shows how the theory of exchangeable random partitions and associated random discrete distributions provides a natural mathematical framework for the analysis of coagulation processes (also called coalescents) and fragmentation processes.
Abstract: The Harris correspondence between random walks and random trees, reviewed in Section 6.3, suggests that a continuous path be regarded as encoding some kind of infinite tree, with each upward excursion of the path corresponding to a subtree. Thisidea has been developed and applied in various ways by Neveu- Pitman [324, 323], Aldous [5, 6, 7] and Le Gall [271, 272, 273,275]. This chapter reviews this circle of ideas, with emphasis on how the Brownian forest can be grown to explore finer andfiner oscillations of the Brownian path, and how this forest growth process is related to WilliamsÃÂâÃÂÃÂÃÂàpath decompositions ofBrownian motion at the time of a maximum or minimum.
Abstract: This chapter is a review of various constructions of random partitions from Poisson point processes of random lengths, based on the work of Kingman and subsequent authors. The lengths can be interpreted as the jumps of a subordinator, or as the lengths of excursions of some Markov process.
Abstract: This chapter is a review of basic ideas from Kingmanâs theory of exchangeable random partitions. This theory turns out to be of interest in a number of contexts, for instance in the study of populationgenetics, Bayesian statistics, and models for processes of coagulation and fragmentation.
Abstract: This chapter introduces a basic sequential construction of random partitions, motivated at first by consideration of uniform random permutations of a set of $n$ elements, which are consistent in a certain sense as n varies. This leads to consideration of a particular two-parameter family of exchangeable random partition structures, which can be characterized in various ways, and which is closely related to gamma and stable subordinators.
Abstract: For two collections of nonnegative and suitably normalised weights $W(j)$ and $V(n,k)$, a probability distribution on the set of partitions of the set $1,...,n$ is defined by assigning to a generic partition $A_j, j\leq k$ the probability $V(n,k) W(|A_1|)... W(|A_k|)$, where $|A_j|$ is the number of elements of $A_j$. We impose constraints on the weights by assuming that the resulting random partitions $Π_n$ of $[n]$ are consistent as $n$ varies, meaning that they define an exchangeable partition of the set of all natural numbers. This implies that the weights $W$ must be of a very special form depending on a single parameter $α\in [-\infty,1]$. The case $α=1$ is trivial, and for each value of $α\neq 1$ the set of possible $V$-weights is an infinite-dimensional simplex. We identify the extreme points of the simplex by solving the boundary problem for a generalised Stirling triangle. In particular, we show that the boundary is discrete for $-\infty\leqα<0$ and continuous for $0\leqα<1$. For $α\leq 0$ the extremes correspond to the members of the Ewens-Pitman family of random partitions indexed by $(α,θ)$, while for $0<α<1$ the extremes are obtained by conditioning an $(α,θ)$-partition on the asymptotics of the number of blocks of $Π_n$ as $n$ tends to infinity.
Abstract: The bijection between composition structures and random closed subsets of the unit interval implies that the composition structures associated with $S \cap [0,1]$ for a self-similar random set $S\subset R_+$ are those which are consistent with respect to a simple truncation operation. Using the standard coding of compositions by finite strings of binary digits starting with a 1, the random composition of $n$ is defined by the first $n$ terms of a random binary sequence of infinite length. The locations of 1s in the sequence are the places visited by an increasing time-homogeneous Markov chain on the positive integers if and only if $S = \exp(-W)$ for some stationary regenerative random subset $W$ of the real line. Complementing our study in previous papers, we identify self-similar Markovian composition structures associated with the two-parameter family of partition structures.
Abstract: This paper shows how the invariance of the arc sine distribution on $(0,1)$ under a family of rational maps is related on the one hand to various integral identities with probabilistic interpretations involving random variables derived from Brownian motion with arc sine, Gaussian, Cauchy and other distributions, and on the other hand to results in the analytic theory of iterated rational maps.
Abstract: This paper presents some general formulas for random partitions of a finite set derived by Kingmanâs model of random sampling from an interval partition generated by subintervals whose lengths are the points of a Poisson point process. These lengths can be also interpreted as the jumps of a subordinator, that is an increasing process with stationary independent increments. Examples include the two-parameter family of Poisson-Dirichlet models derived from the Poisson process of jumps of a stable subordinator. Applications are made to the random partition generated by the lengths of excursions of a Brownian motion or Brownian bridge conditioned on its local time at zero.
Abstract: We use a natural ordered extension of the Chinese Restaurant Process to grow a two-parameter family of binary self-similar continuum fragmentation trees. We provide an explicit embedding of Fordâs sequence of alpha model trees in the continuum tree which we identified in a previous article as a distributional scaling limit of Fordâs trees. In general, the Markov branching trees induced by the two-parameter growth rule are not sampling consistent, so the existence of compact limiting trees cannot be deduced from previous work on the sampling consistent case. We develop here a new approach to establish such limits, based on regenerative interval partitions and the urn-model description of sampling from Dirichlet random distributions.
Abstract: The boundary problem for graphs like Pascalâs but with general multiplicities of edges is related to a âbackwardâ problem of moments of the Hausdorff type.
Abstract: A simple explicit construction is provided of a partition-valued fragmentation process whose distribution on partitions of $[n]=1,...,n$ at time $θ \ge 0$ is governed by the Ewens sampling formula with parameter θ. These partition-valued processes are exchangeable and consistent, as $n$ varies. They can be derived by uniform sampling from a corresponding mass fragmentation process defined by cutting a unit interval at the points of a Poisson process with intensity $θ x^-1 dx$ on $R_+$, arranged to be intensifying as θ increases.
Notes: to appear in Combinatorics, Probability and Computing
Abstract: Scholarly societies are typically non-profit organizations which seek a stable and sustainable balance between two basic long term objectives: on the one hand to promote and develop a particular field of knowledge by widespread dissemination of high quality publications in that field, and on the other hand to sustain themselves as organizations and support various other beneficial activities besides publication. As chair of the publications committee of one such society, the Institute of Mathematical Statistics (IMS), I am looking for ways to achieve this balance, and seeking advice from others with the same intent.
