Selected Publications
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.
Jim Pitman's experimental
Bibserver has an essentially complete list of my papers.
Preprints
- (with C. McDiarmid and A. Scott)
Uniform Multicommodity Flow through the Complete Graph with Random Edge-capacities
- (with S. Bhamidi)
Edge Flows in the Complete Random-Lengths Network
- Spatial Transportation Networks with Transfer Costs: Asymptotic Optimality of Hub and Spoke Models
-
(with Charles Bordenave and Marc Lelarge)
Dynamic Programming Optimization over Random Data: the Scaling Exponent for Near-optimal Solutions
-
(with Charles Bordenave and Marc Lelarge)
Near-Minimal Spanning Trees: a Scaling Exponent in Probability Models
-
Cost-volume relationships for flows through a disordered network
Research Papers
- (with Wilf Kendall)
Short-length routes in low-cost networks via Poisson line patterns.
Adv. Appl. Probability 40 (2008) 1-21.
-
(with Maxim Krikun and Lea Popovic)
Stochastic Models for Phylogenetic Trees on Higher-order Taxa.
J. Math. Biology 56 (2008) 525-557.
-
Optimal spatial transportation networks where link-costs are sublinear in link-capacity.
J. Stat. Mech. (2008) P03006.
-
(with Russ Lyons)
Processes on Unimodular Random Networks. Electronic J. Probab. 12 (2007) 1454-1508.
-
Optimal flow through the disordered lattice.
Annals of Probability 35 (2007) 397--438.
- (with Jim Pitman)
Two Recursive Decompositions of Brownian Bridge Related to the Asymptotics of Random Mappings.
In In Memoriam Paul-Andre Meyer - Seminaire de Probabilites XXXIX.
(Springer Lecture Notes in Math. 1874), (2006) pages 269-303.
- Abstract
- Paper
-
(with Maxim Krikun)
Percolating Paths through Random Points.
ALEA 1 (2006) 89-109.
-
(with Lea Popovic)
A Critical Branching Process Model for Biodiversity.
Advances Applied Probability 37 (2005) 1094-1115.
- (with Gregory Miermont and Jim Pitman)
Weak Convergence of Random p-mappings and
the Exploration Process of Inhomogeneous Continuum Random Trees.
Probab. Th. Related Fields 133 (2005) 1-17.
-
(with Antar Bandyopadhyay)
A Survey of Max-type Recursive Distributional Equations.
Annals of Applied Probability
15 (2005) 1047-1110.
-
Percolation-like 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) 825-838.
- (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), 182-218.
- (with Gregory Miermont and Jim Pitman)
Brownian Bridge Asymptotics for Random p-mappings.
Electronic J. Probab.
9 (2004) 37 - 56.
- A Tractable Complex Network Model based on the Stochastic Mean-field
Model of Distance.
In Complex Networks ed. E. ben-Naim et al., pages 51-87.
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), 152-161.
- (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. 1-72. Springer, 2003.
- (with Allon Percus)
Scaling and Universality in Continuous length Combinatorial Optimization.
Proc. Natl. Acad. Sci. USA 100 (2003) 11211-11215.
- (with Jim Pitman)
Invariance Principles for Non-uniform Random Mappings and Trees.
In: Asymptotic Combinatorics with Applications to Mathematical Physics
, ed. V.A. Malyshev and A.M. Vershik, p. 113-147. Kluwer, 2002.
- (with Jim Pitman)
The Asymptotic Distribution of the Diameter of a Random Mapping.
C. R. Math. Acad. Sci. Paris
334 (2002) 1-4.
-
(with Persi Diaconis)
The Asymmetric One-dimensional Constrained Ising Model: Rigorous Results.
J. Statist. Phys.
107 (2002) 945-975.
-
(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) 621-634.
-
(with Antar Bandyopadhyay)
How to Combine Fast heuristic Markov Chain Monte Carlo with Slow Exact Sampling.
Electronic Commun. Probab.
6 (2001) 79-89.
-
Stochastic Models and Descriptive Statistics for Phylogenetic Trees,
from Yule to Today.
(revision of
Visualizing Phylogenetic Tree Balance
).
Statistical Science
16 (2001) 23-34.
-
The zeta(2) Limit in the Random Assignment Problem.
Random Structures and Algorithms
18 (2001) 381-418.
-
Reorganizing Large Web Sites.
Amer. Math. Monthly 108 (2001) 16-27.
- (with Jim Pitman)
Inhomogeneous Continuum Random Trees and the Entrance Boundary of
the Additive Coalescent.
Probab. Th. Related Fields
118 (2000) 455-482.
-
(with Boris Pittel)
On a Random Graph with Immigrating Vertices: Emergence of the Giant Component.
Random Structures Algorithms
17 (2000) 79-102.
-
Mixing Time for a Markov Chain on Cladograms.
Combinatorics, Probability and Computing
9 (2000) 191-204.
-
The Percolation Process on a Tree where Infinite Clusters are Frozen.
Math. Proc. Cambridge Philos. Soc.
128 (2000) 465-477.
-
(with Persi Diaconis)
Longest Increasing Subsequences: From Patience Sorting to the
Baik-Deift-Johansson Theorem.
Bull. Amer. Math. Soc.
36 (1999) 413-432.
- (with Steven Evans)
Dirichlet Forms on Totally Disconnected Spaces and Bipartite Markov chains.
J. Theoretical Probab
12 (1999) 839-858.
- (with Jim Pitman)
A Family of Random Trees with Random Edge Lengths.
Random Structures Algorithms
15 (1999) 176-195.
- Deterministic and Stochastic Models for Coalescence (Aggregation,
Coagulation): A Review of the Mean-Field Theory for Probabilists.
Bernoulli 5 (1999) 3-48.
- (with Jim Pitman)
The Standard Additive Coalescent.
Annals of Probability
26 (1998) 1703-1726.
- A Metropolis-Type Optimization Algorithm on the Infinite Tree.
Algorithmica 22 (1998) 388-412.
-
Brownian Excursion Conditioned on its Local Time
Electronic Commun. Probab.
3 (1998) 79-90.
- (with Jim Pitman)
Tree-Valued Markov Chains Derived from Galton-Watson Processes.
Ann. Inst. Henri Poincare.
34 (1998) 637-686.
- Stochastic Coalescence.
In Proceedings ICM 1998, volume 3, p. 205-211.
Special volume of Documenta Mathematica (1998).
- On the Critical Value for ``Percolation" of Minimum-Weight
Trees in the Mean-Field Distance Model.
Combinatorics, Probability and Computing
7 (1998) 1-10.
-
Tree-Valued Markov Chains and Poisson-Galton-Watson Distributions.
In Microsurveys in Discrete Probability,
ed. D. Aldous and J. Propp, pages 1-20.
Amer. Math. Soc. (DIMACS Ser. Discrete Math. Theoret. Comp. Sci. 41)
1998.
- Emergence of the Giant Component in Special
Marcus-Lushnikov Processes.
Random Structures Algorithms
12 (1998) 179-196.
- (with Vlada Limic)
The Entrance Boundary of the Multiplicative Coalescent
Electronic J. Probab.
3 (1998) 1-59.
- (with L. Lovasz and P. Winkler)
Mixing Times for Uniformly Ergodic Markov Chains.
Stochastic Process. Appl.
71 (1997), 165-185.
- Brownian Excursions, Critical Random Graphs and the Multiplicative Coalescent.
Annals of Probability
25 (1997), 812-854.
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), 199-213.
Abstract
Paper (compressed PS)
Paper (PDF)
- Darwin's Log: A Toy Model of Speciation and Extinction.
J. Appl. Probab
32 (1995), 279-295.
- Probability Distributions on Cladograms.
In: Random Discrete Structures,
eds. D. Aldous and R. Pemantle,
(1995), 1-18. 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 492-501.
- (with Jim Pitman)
Brownian Bridge Asymptotics for Random Mappings.
Random Struct. Alg. 5 (1994) 487-512.
- Recursive Self-Similarity for Random Trees, Random
Triangulations and Brownian Excursion.
Ann. Probab. 22 (1994), 527-545.
- Triangulating the Circle, at Random.
Amer. Math. Monthly
101 (1994) 223-233.
- Tree-Based Models for Random Distribution of Mass.
J. Statist. Phys.
73 (1993) 625-641.
- Greedy Search on the Binary Tree with Random Edge-Weights.
Combinatorics, Probability and Computing
1 (1992) 281-293.
- Asymptotics in the Random Assignment Problem.
Probab. Th. Related Fields
93 (1992) 507-534.
-
Inequalities for Rare Events in Time-Reversible Markov Chain II.
Stochastic Proc. Appl.
44 (1993) 15-25.
- (with Mark Brown) Inequalities for Rare Events in Time-Reversible
Markov Chain I.
In
Stochastic Inequalities
ed. M. Shaked and Y.L. Tong,
pages 1-16.
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 23-70.
Cambridge University Press, 1991.
- (with W.B. Krebs)
The Birth-and-Assassination Process.
Stat. Probab. Letters 10 (1990) 427-430.
- The random walk construction of uniform spanning trees and uniform
labelled trees.
SIAM J. Discrete Math. 3 (1990), 450-465.
- Meeting Times for Independent Markov Chains.
Stochastic Proc. Appl. 38 (1991), 185-193.
- On the Markov Chain Simulation Method for Uniform
Combinatorial Distributions and Simulated Annealing.
Probab. Engineering Inform. Sci.
1 (1987) 33--46.
- Ultimate Instability of Exponential Backoff Protocol
for Acknowledgement-based transmission Control of Random Access
Communication Channels. IEEE Trans. Inf. Th. 33 (1987) 219-223.
- Some interesting processes arising as heavy traffic limits
in an M/M/° storage process. Stochastic Proc. Appl. 22 (1986) 291-313.
- (with Persi Diaconis). Shuffling Cards and Stopping Times.
Amer. Math. Monthly 93 (1986) 333-348.
- Random Walks on Finite Groups and Rapidly Mixing
{M}arkov Chains. In
Seminaire de Probabilites XVII, Lecture Notes in Math. 986 (1983) 243--297.
- Exchangeability and Related Topics. In
Ecole d'Ete St Flour 1983.
Springer Lecture Notes in Math. 1117 (1985) 1-198.
- 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.
Springer-Verlag, 1989.
- 1992 update keyed to book.
Return to David Aldous's homepage