David Aldous

OPTIMAL FLOW THROUGH THE DISORDERED LATTICE 1 (2008)

Weak convergence of random p-mappings and the exploration process of inhomogeneous continuum random trees

Consider routing traffic on the N × N torus, simultaneously between all source-destination pairs, to minimize the cost � e c(e)f 2 (e), wheref(e) is the volume of flow across edge e and the c(e)...

Probab. Theory Relat. Fields 129, 182–218 (2004) Digital Object Identifier (DOI) 10.1007/s00440-003-0334-7 (2008)

PIPE5 Finite Element Analysis For Buried Structures (2008)

The exploration process of inhomogeneous continuum random trees, and an extension of Jeulin’s local time identity

PIPE5 Finite Element Analysis For Buried Structures (2008)

PIPE5 is a two-dimensional finite element analysis program for buried structure analysis. The program has gone through several changes over the years. Some of the features that were added in the...

PIPE5 Finite Element Analysis For Buried Structures (2008)

PIPE5 is a two-dimensional finite element analysis program for buried structure analysis. The program has gone through several changes over the years. Some of the features that were added in the...

Probab. Theory Relat. Fields 118, 455–482 (2000) Digital Object Identifier (DOI) 10.1007/s004400000094 (2008)

PIPE5 is a two-dimensional finite element analysis program for buried structure analysis. The program has gone through several changes over the years. Some of the features that were added in the...

DIRICHLET FORMS ON TOTALLY DISCONNECTED SPACES AND BIPARTITE MARKOV CHAINS (2008)

Inhomogeneous continuum random trees and the entrance boundary of the additive coalescent ⋆

David Aldous, N. Evans

Abstract. We use Dirichlet form methods to construct and analyse a general class of reversible Markov processes with totally disconnected state spaces. We study in detail the special case of...

THE STANDARD ADDITIVE COALESCENT 1 (2008)

On the stability of a batch clearing system with Poisson arrivals and subadditive service times (2007)

Regard an element of the set � � = �x1�x2�� x1 ≥ x2 ≥···≥0 � � xi = 1

David Aldous, Masakiyo Miyazawa, Tomasz Rolski

We study a service system in which, in each service period, the server performs the current set B of tasks as a batch, taking time s(B), where the function s(\Delta) is subadditive. A natural...

Dirichlet Forms On Totally Disconnected Spaces And Bipartite Markov Chains (2007)

David Aldous, STEVEN N. EVANS

. We use Dirichlet form methods to construct and analyse a general class of reversible Markov processes with totally disconnected state spaces. We study in detail the special case of bipartite Markov...

Chapter 9 A Second Look at General Markov Chains (2007)

Running head: Constrained Ising Model. (2007)

In the spirit of Chapter 2, this is an unsystematic treatment of scattered topics which are related to topics discussed for reversible chains, but where reversibility plays no essential role. Section...

On the stability of a batch clearing system with Poisson (2007)

We study a one-dimensional spin (interacting particle) system, with product Bernoulli(p) stationary distribution, in which a site can flip only when its left neighbor is in state +1. Such models have...

David Aldous, Masakiyo Miyazawa, Tomasz Rolski

arrivals and subadditive service times

Spatial Transportation Networks with Transfer Costs: Asymptotic Optimality of Hub and Spoke Models (2007)

Stochastic Models for Phylogenetic Trees on Higher-order Taxa (2007)

Consider networks on $n$ vertices at average density 1 per unit area. We seek a network that minimizes total length subject to some constraint on journey times, averaged over source-destination...

Aldous, David, Krikun, Maxim, Popovic, Lea

Simple stochastic models for phylogenetic trees on species have been well studied. But much paleontology data concerns time series or trees on higher-order taxa, and any broad picture of...

Near-Minimal Spanning Trees: a Scaling Exponent in Probability Models (2006)

Aldous, David, Bordenave, Charles, Lelarge, Marc

We study the relation between the minimal spanning tree (MST) on many random points and the "near-minimal" tree which is optimal subject to the constraint that a proportion $\delta$ of its edges must...

Processes on Unimodular Random Networks (2006)

Aldous, David, Lyons, Russell

We investigate unimodular random networks. Our motivations include their characterization via reversibility of an associated random walk and their similarities to unimodular quasi-transitive graphs....

Percolating paths through random points (2006)

Aldous, David, Krikun, Maxim

We prove consistency of four different approaches to formalizing the idea of minimum average edge-length in a path linking some infinite subset of points of a Poisson process. The approaches are (i)...

Percolating paths through random points (2006)

Aldous, David, Krikun, Maxim

We prove consistency of four different approaches to formalizing the idea of minimum average edge-length in a path linking some infinite subset of points of a Poisson process. The approaches are (i)...

ABSTRACT Prediction Planes for the Pythagorean Percentage (2006)

Defensive Efficiency, Dennis Moy, Dennis Moy, Advisor Professor, David Aldous

by

A critical branching process model for biodiversity (2005)

Aldous, David, Popovic, Lea

We study the following model for a phylogenetic tree on n extant species: the origin of the clade is a random time in the past whose (improper) distribution is uniform on (0,∞); thereafter, the...

Optimal flow through the disordered lattice (2005)

Percolating paths through random points : (2005)

Consider routing traffic on the N x N torus, simultaneously between all source-destination pairs, to minimize the cost $\sum_ec(e)f^2(e)$, where f(e) is the volume of flow across edge e and the c(e)...

Aldous, David, Krikun, Maxim

We prove consistency of four different approaches to formalizing the idea of minimum average edge-length in a path linking some infinite subset of points of a Poisson process. The approaches are (i)...

Cost-volume relationships for flows through a disordered network (2005)

Weak convergence of random p-mappings and the exploration process of inhomogeneous continuum random trees (2005)

In a network where the cost of flow across an edge is nonlinear in the volume of flow, and where sources and destinations are uniform, one can consider the relationship between total volume $v$ of...

Weak convergence of random p-mappings and the exploration process of inhomogeneous continuum random trees (2005)

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...

Weak convergence of random p-mappings and the exploration process of inhomogeneous continuum random trees (2005)

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...

Weak convergence of random p-mappings and the exploration process of inhomogeneous continuum random trees (2005)

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...

Processes on unimodular random networks (2005)

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...

David Aldous, Russell Lyons

Abstract. We investigate unimodular random networks. Our motivations include their characterization via reversibility of an associated random walk and their similarities to unimodular...

Two recursive decompositions of Brownian bridge (2004)

Aldous, David, Pitman, Jim

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...

Brownian Bridge Asymptotics for Random p-Mappings (2004)

Aldous, David; University Of California, Berkeley; Aldous@stat.berkeley.edu, Miermont, Gregory; Ecole Normale Superieure; Miermont@dma.ens.fr, Pitman, Jim; University Of California, Berkeley; Pitman@stat.berkeley.edu

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...

The exploration process of inhomogeneous continuum random trees, and an extension of Jeulin's local time identity (2004)

The exploration process of inhomogeneous continuum random trees, and an extension of Jeulin's local time identity (2004)

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...

The exploration process of inhomogeneous continuum random trees, and an extension of Jeulin's local time identity (2004)

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...

The exploration process of inhomogeneous continuum random trees, and an extension of Jeulin's local time identity (2004)

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...

Coherent Stochastic Models for Macroevolution (2004)

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...

David Aldous, Lea Popovic

We give a mathematician’s view of evolutionary biology literature concerning stochastic models for phylogenetic trees. We spotlight a model for the tree on n extant species that would be observed...

Brownian Bridge Asymptotics for Random p-Mappings (2004)

Scaling and Universality in Continuous Length Combinatorial Optimization (2003)

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...

Aldous, David, Percus, Allon G.

We consider combinatorial optimization problems defined over random ensembles, and study how solution cost increases when the optimal solution undergoes a small perturbation delta. For the minimum...

The exploration process of inhomogeneous continuum random trees, and an extension of Jeulin's local time identity (2003)

David Aldous, Gregory Miermont, Jim Pitman

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...

The exploration process of inhomogeneous continuum random trees, and an extension of Jeulin's local time identity (2003)

The objective method: Probabilistic combinatorial optimization and local weak convergence (2003)

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...

David Aldous, J. Michael Steele

This survey describes a general approach to a class of problems that arise in combinatorial probability and combinatorial optimization. Formally, the method is part of weak convergence theory, but in...

The objective method: Probabilistic combinatorial optimization and local weak convergence (2003)

David Aldous, J. Michael Steele

1.2 A Stalking Horse: the Partial Matching Problem.................... 4

Brownian Bridge Asymptotics for Random p-Mappings (2002)

The Asymptotic Distribution of the Diameter of a Random Mapping (2002)

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...

Invariance principles for non-uniform random mappings and trees (2002)

The asymptotic distribution of the diameter of the digraph of a uniformly distributed random mapping of an n-element set to itself is represented as the distribution of a functional of a reflecting...

In the context of uniform random mappings of an n-element set to itself, Aldous and Pitman (1994) established a functional invariance principle, showing that many n!1limit distributions can be...

a random mapping (2002)

Let Fnbeauniformlydistributedrandommappingfromtheset[n]:= (2002)

asymptotic distribution of the diameter of

The Asymmetric One-Dimensional Constrained Ising Model (2001)

asymptotic distribution of the diameter of

Aldous, David, Diaconis, Persi

We study a reversible one-dimensional spin system with Bernoulli(p) stationary distribution, in which a site can flip only if the site to its left is in state +1. Such models have been used as simple...

On the stability of a batch clearing system with Poisson arrivals and subadditive service times (2001)

Aldous, David, Miyazawa, Masakiyo, Rolski, Tomasz

We study a service system in which, in each service period, the server performs the current set B of tasks as a batch, taking time s(B), where the function s(.) is subadditive. A natural definition...

Reorganizing Large Web Sites (2000)

Advanced L² Techniques for Bounding Mixing Times (1999)

this paper. The root index page offers about 45 links. Some are to content pages (available faculty positions, list of tutors etc) and some are to other index pages (faculty, staff, course offerings...

Longest Increasing Subsequences: From Patience Sorting to the Baik-Deift-Johansson Theorem (1999)

Chapter 2 section yyy:6.2, and Chapter 3 yyy:(55) and the spectral representation give useful reexpressions: kP i (X t 2 \Delta) \Gamma (\Delta)k 2 2 = X j j / p ij (t) j \Gamma 1 ! 2 = p ii (2t) i...

A family of random trees with random edge lengths (1999)

We describe a simple one-person card game, patience sorting. Its analysis leads to a broad circle of ideas linking Young tableaux with the longest increasing subsequence of a random permutation via...

A family of random trees with random edge lengths (1999)

We introduce a family of probability distributions on the space of trees with I labeled vertices and possibly extra unlabeled vertices of degree 3, whose edges have positive real lengths. Formulas...

Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem (1999)

ABSTRACT: We introduce a family of probability distributions on the space of trees with I labeled vertices and possibly extra unlabeled vertices of degree 3, whose edges have positive real lengths....

The standard additive coalescent (1998)

Abstract. We describe a simple one-person card game, patience sorting. Its analysis leads to a broad circle of ideas linking Young tableaux with the longest increasing subsequence of a random...

Aldous, David, Pitman, Jim

Regard an element of the set $$\Delta := {(x_1, x_2, \dots): x_1 \geq x_2 \geq \dots \geq 0, \Sigma_i x_i = 1}$$ as a fragmentation of unit mass into clusters of masses $x_i$. The additive coalescent...

The Entrance Boundary of the Multiplicative Coalescent (1998)

Aldous, David; University Of California, Berkeley; Aldous@stat.berkeley.edu, Limic, Vlada; University Of California, Berkeley; Aldous@stat.berkeley.edu

The multiplicative coalescent $X(t)$ is a $l^2$-valued Markov process representing coalescence of clusters of mass, where each pair of clusters merges at rate proportional to product of masses. From...

Tree-valued Markov chains derived from Galton-Watson processes (1998)

Aldous, David, Pitman, Jim

The entrance boundary of the multiplicative coalescent (1998)

David Aldous, Vlada Limic

a b i l i t y

Tree-valued Markov chains derived from Galton-Watson processes (1998)

Tree-valued Markov chains and Poisson-Galton-Watson distributions (1998)

Let G be a Galton-Watson tree, and for 0 u 1 let G u be the subtree of G obtained by retaining each edge with probability u. We study the tree-valued Markov process (G u; 0 u 1) and an analogous...

Inhomogeneous Continuum Random Trees and the Entrance Boundary of the Additive Coalescent (1998)

. The Poisson-Galton-Watson distribution on finite trees, and the related PGW 1 (1) distribution on infinite trees with one end, arise in several contexts, in particular as n !1 weak limits within...

By David Aldous, David Aldous, Jim Pitman

Regard an element of the set of ranked discrete distributions \Delta := f(x 1 ; x 2 ; : : :) : x 1 x 2 : : : 0; P i x i = 1g as a fragmentation of unit mass into clusters of masses x i . The additive...

The Entrance Boundary of the Multiplicative Coalescent (1998)

David Aldous, Vlada Limic

The multiplicative coalescent X(t) is a l 2 -valued Markov process representing coalescence of clusters of mass, where each pair of clusters merges at rate proportional to product of masses. From...

Inhomogeneous Continuum Random Trees and the Entrance Boundary of the Additive Coalescent (1998)

The entrance boundary of the multiplicative coalescent (1998)

Regard an element of the set of ranked discrete distributions \Delta := f(x 1 ; x 2 ; : : :) : x 1 x 2 : : : 0; P i x i = 1g as a fragmentation of unit mass into clusters of masses x i . The additive...

David Aldous, Vlada Limic

E l e c t r o n

Brownian excursions, critical random graphs and the multiplicative coalescent (1997)

The Standard Additive Coalescent (1997)

Let $(B^t (s), 0 \leq s < \infty)$ be reflecting inhomogeneous Brownian motion with drift $t - s$ at time $s$, started with $B^t (0) = 0$. Consider the random graph $\mathscr{G}(n, n^{-1} +...

Emergence of the Giant Component in Special Marcus-Lushnikov Processes (1997)

Regard an element of the set \Delta := f(x 1 ; x 2 ; : : :) : x 1 x 2 : : : 0; X i x i = 1g as a fragmentation of unit mass into clusters of masses x i . The additive coalescent of Evans and Pitman...

A Metropolis-type Optimization Algorithm on the Infinite Tree (1997)

Component sizes in the usual random graph process are a special case of the Marcus-Lushnikov process discussed in the scientific literature, so it is natural to ask how theory surrounding emergence...

Let S(v) be a function defined on the vertices v of the infinite binary tree. One algorithm to seek large positive values of S is the Metropolis-type Markov chain (Xn ) defined by P (Xn+1 = wjXn = v)...

Running (1997)

Let G be a Galton-Watson tree, and for 0 u 1let Gu be the subtree of G obtained by retaining each edge with probability u. We study the tree-valued Markov process (Gu; 0 u 1) and an analogous process...

Infinite Graphs (1996)

Examples: Special Graphs and Trees (1996)

Introduction There is a huge research literature concerning random walks on infinite discrete groups, and more generally on infinite graphs. Woess [22] provides an invaluable recent survey, quoting...

On the Critical Value for "Percolation" of Minimum-Weight Trees in the Mean-Field Distance Model (1996)

8.928> x + E x T v = w w vx ; where w = X i X j w ij : (2) Specializing to the unweighted case, E v T x = 2jE(v; x)j + 1 (3) E v T x +E x T v = 2jEj: (4) 1 Proof. It is enough to prove (1), since...

Probability Distributions on Cladograms (1996)

Consider the complete n-graph with independent exponential (mean n) edge-weights. Let M (c; n) be the maximal size of subtree for which the average edge-weight is at most c. It is shown that M (c; n)...

A Second Look at General Markov Chains (1995)

By analogy with the theory surrounding the Ewens sampling formula in neutral population genetics, we ask whether there exists a natural oneparameter family of probability distributions on cladograms...

Hammersley's Interacting Particle Process and Longest Increasing Subsequences (1995)

s for reversible chains. Here we discuss underlying "exact" results. Fix an initial distribution . Then 1 associated with each notion of mixing, there is a corresponding construction of a...

Recursive self-similarity for random trees, random triangulations and Brownian excursion (1994)

In a famous paper [8] Hammersley investigated the length Ln of the longest increasing subsequence of a random n-permutation. Implicit in that paper is a certain one-dimensional continuous-space...

"Go With the Winners" Algorithms (1994)

Your use of the JSTOR archive indicates your acceptance of JSTOR's Terms and Conditions of Use, available at

David Aldous, Umesh Vazirani

this paper, we give a rigorous analysis of such a "go with the winners" scheme in the concrete setting of searching for a deep leaf in a tree. There are two relevant parameters of the tree:...

Hitting and Convergence Time, and Flow Rate, Parameters for Reversible Markov Chains (1994)

Interacting Particles on Finite Graphs (1994)

) The relaxation time 2 , i.e. the time constant in the asymptotic rate of convergence to the stationary distribution. (v) A "flow" parameter c = sup A (A)(A c ) P i2A P j2A c i p ij = sup...

Reversible Markov Chains (1994)

intuitively obvious that P (X x) P (Y x) for all x: (1) 1 One could verify this from the exact formulas, but there is a more elegant non-computational proof. For 1 i n define events (A i ; B i ; C i...

ly, call f : [0; 1) ! [0; 1) completely monotone (CM) if there is a non-negative measure on [0; 1) such that f(t) = Z 1 0 e \Gamma`t (d`); 0 t ! 1: (41) Our applications will use only the special...

Cover Times (1994)

Symmetric Graphs and Chains (1994)

subset at the time when the graph is almost covered is believed to be "fractal" (see the Notes on Chapter 7). 1 We are ultimately interested in random walks on unweighted graphs, but some...

Tree-Based Models for Random Distribution of Mass (1993)

with random walk on a distance-regular graph, which roughly corresponds to nearest-neighbor isotropic random walk on a discrete Gelfand pair. This book focuses on inequalities rather than exact...

Probability Approximations via the Poisson Clumping Heuristic: An Update (1992)

A mathematical model for distribution of mass in d-dimensional space, based upon randomly embedding random trees into space, is introduced and studied. The model is a variant of the superBrownian...

MAXIMUM SIZE OF A DYNAMIC DATA STRUCTURE: Hashing with Lazy Deletion Revisited (1992)

s (which includes the geometric tails of some of our queueing examples) is given by Goldie [26]. C34 Rice's formula. Formalizations of the "local" version of the heurstic from...

David Aldous, Micha Hofri, Wojciech Szpankowski

We study the dynamic data structure management technique called Hashing with Lazy Deletion (HwLD). A table managed under HwLD is built via a sequence of insertions and deletions of items. When...

Probability Theory 9 Springer-Verlag 1992 Asymptotics in the random assignment problem (1991)

A Markovian extension of Valiant's learning model (Extended Abstract) (1990)

Summary. We show that, in the usual probabilistic model for the random assignment problem, the optimal cost tends to a limit constant in probability and in expectation. The method involves...

David Aldous, Umesh Vazirani

Formalizing the process of natural induction and justi-fying its predictive value is not only basic to the phi-

North-Holland THE ‘BIRTH-AND-ASSASSINATION ’ PROCESS (1989)

David Aldous, William B. Krebs

Abstract: A new variant of a branching process is introduced, with sufficient conditions for it to persist and to die out. The model is applied to discuss the asymptotic stability of a new type of...

Printed in Great Britain Hitting times for random walks on vertex-transitive graphs (1988)

A diffusion limit for a class of randomly-growing binary trees (1988)

For random walks on finite graphs, we record some equalities, inequalities and limit theorems (as the size of graph tends to infinity) which hold for vertex-transitive graphs but not for general...

David Aldous, Paul Shields

Summary. Binary trees are grown by adding one node at a time, an available node at height i being added with probability proportional to c-~, c> 1. We establish both a "strong law of large...

North-Holland SOME INTERESTING PROCESSES ARISING AS HEAVY TRAFFIC LIMITS IN AN M/M/co STORAGE PROCESS (1986)