Publications
Some older papers are compressed Postscript;
Click here for info if your browser doesn't automatically uncompress.
Abstracts are plain text.
Note there are some
prose descriptions of past and current research
available.
The main list is of research papers, or survey papers aimed at the research audience.
Slightly separate is the initial short list of "semipro" writings involving
undergraduatelevel mathematics
in loosely the American Math Monthly style.
Another page gives
book reviews, interviews, etc.
Popular (i.e. mostly nonmathematical) writings can be found
in other parts of the site.
Semipro
Research Preprints
 Waves in a Spatial Queue: StopandGo at Airport Security.
 The SI and SIR epidemics on General Networks.
 Which Connected Spatial Networks on Random Points have Linear RouteLengths?
 The Shape Theorem for Routelengths in Connected Spatial Networks on Random Points.
Research Papers
 Weak Concentration for First Passage Percolation Times on Graphs and General Increasing Setvalued Processes.
ALEA Lat. Am. J. Probab. Math. Stat. 13 (2016) 925940.
 The Incipient Giant Component in Bond Percolation on General Finite Weighted Graphs.
Electron. Commun. Probab.
21 (2016), paper no. 68, 9 pp.
 Routed Planar Networks.
Electron. J. Graph Theory Appl. (EJGTA) 4 (2016) 4259.
 (with Tamar Lando) The StretchLength Tradeoff in Geometric Networks: Average Case and
Worst Case Study. Math. Proc. Cambridge Philos. Soc. 159 (2015) 125151.
 (with Daniel Lanoue and Justin Salez) The Compulsive Gambler Process.
Electronic J. Probability 20 (2015) article 35: 118
 (with Jiangzhen Yu)
Random Eulerian Circuits.
Open Problems in Mathematics 2 (2014) 14.
 (with Nathan Ross)
Entropy of Some Models of Sparse Random Graphs With VertexNames.
Probab. Engineering Inform. Sci. 28 (2014) 145168.
 ScaleInvariant Random Spatial Networks.
Electronic J. Probability 19 (2014) article 15: 141.
 Interacting Particle Systems as Stochastic Social Dynamics.
Bernoulli 19 (2013) 11221149.
 (with Karthik Ganesan)
True scaleinvariant random spatial networks.
Proc. Natl. Acad. Sci. USA 110 (2013) 87828785.
 (with Mykahlo Shkolnikov)
Fluctuations of martingales and winning probabilities of game contestants.
Electronic J. Probability 18 (2013) article 47: 117
 When Knowing Early Matters: Gossip, Percolation and Nash Equilibria.
pp. 3  28 in Prokhorov and Contemporary Probability Theory, Eds.
A.N. Shiryaev, S.R.S. Varadhan and E.L. Presman. Springer, 2013.
 (with Daniel Lanoue) A lecture on the averaging process.
Probability Surveys 9 (2012).
 Exchangeability and continuum limits of discrete random structures.
Proceedings of the International Congress of
Mathematicians, 2010,
vol. 1, 141  153, ed. R. Bhatia. Hindustan Book Agency, 2011.
 (with Maxim A. Krikun and Lea Popovic)
Five Statistical Questions about the Tree of Life.
Syst. Biol. 60 (2011) 318  328.
 (with Julian Shun)
Connected Spatial Networks over Random Points and a RouteLength
Statistic.
Statistical Science 25 (2010) 275  288.
 (with S. Bhamidi)
Edge Flows in the Complete RandomLengths Network.
Random Structures Alg, 37 (2010) 271311.
 More Uses of Exchangeability: Representations of Complex Random Structures.
In
Probability and Mathematical Genetics:
Papers in Honour of Sir John Kingman,
ed. N. H. Bingham and C. M. Goldie, pp. 3563.
Cambridge University Press, 2010.

(with J.R. Ong and W. Zhou)
Empires and percolation: stochastic merging of adjacent regions.
J. Phys. A: Math. Theor. 43 (2010) 025001.
 (with C. McDiarmid and A. Scott)
Uniform Multicommodity Flow through the Complete Graph with Random Edgecapacities.
Operations Res. Letters 37 (2009) 299302.

(with Charles Bordenave and Marc Lelarge)
Dynamic Programming Optimization over Random Data: the Scaling Exponent for
Nearoptimal Solutions.
SIAM J. Comput. 38 (2009) 23822410.

Costvolume relationships for flows through a disordered network.
Math. Oper. Res. 33 (2008) 769786.

(with Charles Bordenave and Marc Lelarge)
NearMinimal Spanning Trees: a Scaling Exponent in Probability Models.
Ann. Inst. H. Poincare Probab. Statist. 44 (2008) 962976.
 Spatial Transportation Networks with Transfer Costs: Asymptotic Optimality of Hub and Spoke Models
Math. Proc. Cambridge Philos. Soc. 145 (2008) 471487.
 (with Wilf Kendall)
Shortlength routes in lowcost networks via Poisson line patterns.
Adv. Appl. Probability 40 (2008) 121.

(with Maxim Krikun and Lea Popovic)
Stochastic Models for Phylogenetic Trees on Higherorder Taxa.
J. Math. Biology 56 (2008) 525557.

Optimal spatial transportation networks where linkcosts are sublinear in linkcapacity.
J. Stat. Mech. (2008) P03006.

(with Russ Lyons)
Processes on Unimodular Random Networks. Electronic J. Probab. 12 (2007) 14541508.

Optimal flow through the disordered lattice.
Annals of Probability 35 (2007) 397438.
 (with Jim Pitman)
Two Recursive Decompositions of Brownian Bridge Related to the Asymptotics of Random Mappings.
In In Memoriam PaulAndre Meyer  Seminaire de Probabilites XXXIX.
(Springer Lecture Notes in Math. 1874), (2006) pages 269303.
 Abstract
 Paper

(with Maxim Krikun)
Percolating Paths through Random Points.
ALEA 1 (2006) 89109.

(with Lea Popovic)
A Critical Branching Process Model for Biodiversity.
Advances Applied Probability 37 (2005) 10941115.
 (with Gregory Miermont and Jim Pitman)
Weak Convergence of Random pmappings and
the Exploration Process of Inhomogeneous Continuum Random Trees.
Probab. Th. Related Fields 133 (2005) 117.

(with Antar Bandyopadhyay)
A Survey of Maxtype Recursive Distributional Equations.
Annals of Applied Probability
15 (2005) 10471110.

Percolationlike Scaling Exponents for Minimal Paths and Trees
in the Stochastic Mean Field Model.
Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci.
461 (2005) 825838.
 (with Gregory Miermont and Jim Pitman)
The Exploration Process of Inhomogeneous Continuum Random Trees
and an Extension of Jeulin's Local Time Identity.
Probab. Th. Related Fields
129 (2004), 182218.
 (with Gregory Miermont and Jim Pitman)
Brownian Bridge Asymptotics for Random pmappings.
Electronic J. Probab.
9 (2004) 37  56.
 A Tractable Complex Network Model based on the Stochastic Meanfield
Model of Distance.
In Complex Networks ed. E. benNaim et al., pages 5187.
Springer Lecture notes in Physics vol. 650 (2004).
Next item is shorter version.
 A Stochastic Complex Network Model.
Electron. Res. Announc. Amer. Math. Soc. 9 (2003), 152161.
 (with J. Michael Steele)
The Objective Method: Probabilistic Combinatorial Optimization and
Local Weak Convergence. In
Probability on Discrete Structures
(Volume 110 of Encyclopaedia of Mathematical Sciences),
ed. H. Kesten, p. 172. Springer, 2003.
 (with Allon Percus)
Scaling and Universality in Continuous length Combinatorial Optimization.
Proc. Natl. Acad. Sci. USA 100 (2003) 1121111215.
 (with Jim Pitman)
Invariance Principles for Nonuniform Random Mappings and Trees.
In: Asymptotic Combinatorics with Applications to Mathematical Physics
, ed. V.A. Malyshev and A.M. Vershik, p. 113147. Kluwer, 2002.
 (with Jim Pitman)
The Asymptotic Distribution of the Diameter of a Random Mapping.
C. R. Math. Acad. Sci. Paris
334 (2002) 14.

(with Persi Diaconis)
The Asymmetric Onedimensional Constrained Ising Model: Rigorous Results.
J. Statist. Phys.
107 (2002) 945975.

(with Masakiyo Miyazawa and Tomasz Rolski)
On the Stability of a Batch Clearing System with Poisson Arrivals
and Subadditive Service Times.
Journal of Applied Probability
38 (2001) 621634.

(with Antar Bandyopadhyay)
How to Combine Fast heuristic Markov Chain Monte Carlo with Slow Exact Sampling.
Electronic Commun. Probab.
6 (2001) 7989.

Stochastic Models and Descriptive Statistics for Phylogenetic Trees,
from Yule to Today.
(revision of
Visualizing Phylogenetic Tree Balance
).
Statistical Science
16 (2001) 2334.

The zeta(2) Limit in the Random Assignment Problem.
Random Structures and Algorithms
18 (2001) 381418.
 (with Jim Pitman)
Inhomogeneous Continuum Random Trees and the Entrance Boundary of
the Additive Coalescent.
Probab. Th. Related Fields
118 (2000) 455482.

(with Boris Pittel)
On a Random Graph with Immigrating Vertices: Emergence of the Giant Component.
Random Structures Algorithms
17 (2000) 79102.

Mixing Time for a Markov Chain on Cladograms.
Combinatorics, Probability and Computing
9 (2000) 191204.

The Percolation Process on a Tree where Infinite Clusters are Frozen.
Math. Proc. Cambridge Philos. Soc.
128 (2000) 465477.

(with Persi Diaconis)
Longest Increasing Subsequences: From Patience Sorting to the
BaikDeiftJohansson Theorem.
Bull. Amer. Math. Soc.
36 (1999) 413432.
 (with Steven Evans)
Dirichlet Forms on Totally Disconnected Spaces and Bipartite Markov chains.
J. Theoretical Probab
12 (1999) 839858.
 (with Jim Pitman)
A Family of Random Trees with Random Edge Lengths.
Random Structures Algorithms
15 (1999) 176195.
 Deterministic and Stochastic Models for Coalescence (Aggregation,
Coagulation): A Review of the MeanField Theory for Probabilists.
Bernoulli 5 (1999) 348.
 (with Jim Pitman)
The Standard Additive Coalescent.
Annals of Probability
26 (1998) 17031726.
 A MetropolisType Optimization Algorithm on the Infinite Tree.
Algorithmica 22 (1998) 388412.

Brownian Excursion Conditioned on its Local Time
Electronic Commun. Probab.
3 (1998) 7990.
 (with Jim Pitman)
TreeValued Markov Chains Derived from GaltonWatson Processes.
Ann. Inst. Henri Poincare.
34 (1998) 637686.
 Stochastic Coalescence.
In Proceedings ICM 1998, volume 3, p. 205211.
Special volume of Documenta Mathematica (1998).
 On the Critical Value for ``Percolation" of MinimumWeight
Trees in the MeanField Distance Model.
Combinatorics, Probability and Computing
7 (1998) 110.

TreeValued Markov Chains and PoissonGaltonWatson Distributions.
In Microsurveys in Discrete Probability,
ed. D. Aldous and J. Propp, pages 120.
Amer. Math. Soc. (DIMACS Ser. Discrete Math. Theoret. Comp. Sci. 41)
1998.
 Emergence of the Giant Component in Special
MarcusLushnikov Processes.
Random Structures Algorithms
12 (1998) 179196.
 (with Vlada Limic)
The Entrance Boundary of the Multiplicative Coalescent
Electronic J. Probab.
3 (1998) 159.
 (with L. Lovasz and P. Winkler)
Mixing Times for Uniformly Ergodic Markov Chains.
Stochastic Process. Appl.
71 (1997), 165185.
 Brownian Excursions, Critical Random Graphs and the Multiplicative Coalescent.
Annals of Probability
25 (1997), 812854.
Abstract
Paper
and figure 1
and figure 2
 (with Persi Diaconis). Hammersley's Interacting Particle Process and Longest
Increasing Subsequences.
Probab. Th. Related Fields
103 (1995), 199213.
Abstract
Paper (compressed PS)
Paper (PDF)
 Darwin's Log: A Toy Model of Speciation and Extinction.
J. Appl. Probab
32 (1995), 279295.
 Probability Distributions on Cladograms.
In: Random Discrete Structures,
eds. D. Aldous and R. Pemantle,
(1995), 118. Springer:
IMA Volumes in Mathematics and its Applications 76.
Paper
 (with Umesh Vazirani)
Go With the Winners Algorithms.
In: Proc. 35th Symp. Foundations of Computer Sci.,
(1994)
pages 492501.
 (with Jim Pitman)
Brownian Bridge Asymptotics for Random Mappings.
Random Struct. Alg. 5 (1994) 487512.
 Recursive SelfSimilarity for Random Trees, Random
Triangulations and Brownian Excursion.
Ann. Probab. 22 (1994), 527545.
 Triangulating the Circle, at Random.
Amer. Math. Monthly
101 (1994) 223233.
 TreeBased Models for Random Distribution of Mass.
J. Statist. Phys.
73 (1993) 625641.
 Greedy Search on the Binary Tree with Random EdgeWeights.
Combinatorics, Probability and Computing
1 (1992) 281293.
 Asymptotics in the Random Assignment Problem.
Probab. Th. Related Fields
93 (1992) 507534.

Inequalities for Rare Events in TimeReversible Markov Chain II.
Stochastic Proc. Appl.
44 (1993) 1525.
 (with Mark Brown) Inequalities for Rare Events in TimeReversible
Markov Chain I.
In
Stochastic Inequalities
ed. M. Shaked and Y.L. Tong,
pages 116.
IMS Lecture Notes volume 22, 1992.
 The continuum random tree II: an overview. In
Stochastic Analysis (ed.
M.T. Barlow and N.H. Bingham), pages 2370.
Cambridge University Press, 1991.
 Asymptotic fringe distributions for general families of random trees.
Ann. Appl. Probab. 1 (1991) 228266.
 A Random Tree Model Associated with Random Graphs.
Random Structures Algorithms 1 (1990) 383402.

Threshold Limits for Cover Times.
J. Theoretical Probability
4 (1991) 197211.
 (with W.B. Krebs)
The BirthandAssassination Process.
Stat. Probab. Letters 10 (1990) 427430.
 The random walk construction of uniform spanning trees and uniform
labelled trees.
SIAM J. Discrete Math. 3 (1990), 450465.
 Hitting times for random walks on vertextransitive graphs.
Math. Proc. Cambridge Philos. Soc. 106 (1989) 179191.
 Meeting Times for Independent Markov Chains.
Stochastic Proc. Appl. 38 (1991), 185193.
 (with Paul Shields) A diffusion limit for a class of
randomlygrowing binary trees Probab. Th. Related Fields 79 (1988), 509542.
 (with Larry Shepp) The Least Variable Phase Type Distribution is Erlang.
Stochastic Models 3 (1987) 467473.
 On the Markov Chain Simulation Method for Uniform
Combinatorial Distributions and Simulated Annealing.
Probab. Engineering Inform. Sci.
1 (1987) 3346.
 Ultimate Instability of Exponential Backoff Protocol
for Acknowledgementbased transmission Control of Random Access
Communication Channels. IEEE Trans. Inf. Th. 33 (1987) 219223.
 Some interesting processes arising as heavy traffic limits
in an M/M/° storage process. Stochastic Proc. Appl. 22 (1986) 291313.
 (with Persi Diaconis). Shuffling Cards and Stopping Times.
Amer. Math. Monthly 93 (1986) 333348.
 Random Walks on Finite Groups and Rapidly Mixing
{M}arkov Chains. In
Seminaire de Probabilites XVII, Lecture Notes in Math. 986 (1983) 243297.
 Exchangeability and Related Topics. In
Ecole d'Ete St Flour 1983.
Springer Lecture Notes in Math. 1117 (1985) 1198.
 Weak convergence and the general theory of processes.
Unpublished, 1983. Essentially the same as earlier version titled
Weak convergence of stochastic processes for processes viewed in the Strasbourg manner.
Book
 Probability Approximations via the Poisson Clumping Heuristic.
SpringerVerlag, 1989.
 1992 update keyed to book.
Return to David Aldous's homepage