Publications
Note there are some prose descriptions of past and current research available:
see left margin of my research homepage
The main list is of research papers, or survey papers aimed at the research audience.
Slightly separate is the initial short list of "semi-pro" writings involving
undergraduate-level mathematics
in loosely the American Math Monthly style.
Another page gives
book reviews, interviews, etc.
Popular (i.e. mostly non-mathematical) writings can be found
in other parts of the site.
Semi-pro
Research Preprints (old)
Research Preprints (new)
Research Papers
- (with Svante Janson and Xiaodan Li)
The harmonic descent chain.
Electron. Commun. Probab. 29 (2024), paper no. 77, 1--10.
- (with Shi Feng)
Markov Chains and
Mappings of Distributions on Compact Spaces.
ALEA Lat. Am. J. Probab. Math. Stat. 21 (2024) 1407--1416.
-
(with Alice Contat, Nicolas Curien and Olivier Henard)
Parking on the infinite binary tree.
PTRF
187 (2023) 481--504.
- (with F.T. Bruss)
Gambling under unknown probabilities as a proxy for real world
decisions under uncertainty.
Amer. Math. Monthly 130 (2023) 303--320.
-
Covering a compact space by fixed-radius or growing random balls.
ALEA Lat. Am. J. Probab. Math. Stat. 19 (2022) 755--767.
-
On the Largest Common Subtree of Random Leaf-Labeled
Binary Trees.
SIAM J. Discrete Math. 36 (2022) 299 -- 314.
See this article by Ali Khezeli for an improved lower bound.
-
The Nearest Unvisited Vertex Walk on Random Graphs.
Probab. Engineering Inform. Sci.,
36 (2022) 851-867.
-
(With Brett Kolesnik)
To stay discovered:
On tournament mean score sequences and the Bradley--Terry model.
Stochastic Proc. Appl.
150 (2022) 844-852.
-
A Prediction Tournament Paradox.
The American Statistician 75 (2021) 243-248.
Online version here
- Route Lengths in Invariant Spatial Tree Networks.
Electron. Commun. Probab. 26 (2021), paper no. 31, 1--12.
- (with Marc Barthelemy)
The optimal geometry of transportation networks.
Physical Review E 99 (2019) 052303.
- (with Xiang Li) A Framework for Imperfectly Observed Networks.
Journal of Statistical Physics 173 (2018) 1303--1320.
-
Random partitions of the plane via Poissonian coloring, and a
self-similar process of coalescing planar partitions.
Ann. Probability 46 (2018) 2000--2037.
- The SI and SIR epidemics on General Networks.
Probab. Math. Statist. 37 (2017) 229 - 234.
- Waves in a Spatial Queue.
Stochastic Systems 7 (2017) 197-236.
- Weak Concentration for First Passage Percolation Times on Graphs and General Increasing Set-valued Processes.
ALEA Lat. Am. J. Probab. Math. Stat. 13 (2016) 925--940.
- 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) 42--59.
- (with Tamar Lando) The Stretch-Length Tradeoff in Geometric Networks: Average Case and
Worst Case Study. Math. Proc. Cambridge Philos. Soc. 159 (2015) 125-151.
- (with Daniel Lanoue and Justin Salez) The Compulsive Gambler Process.
Electronic J. Probability 20 (2015) article 35: 1--18
- (with Jiangzhen Yu)
Random Eulerian Circuits.
Open Problems in Mathematics 2 (2014) 1--4.
- (with Nathan Ross)
Entropy of Some Models of Sparse Random Graphs With Vertex-Names.
Probab. Engineering Inform. Sci. 28 (2014) 145-168.
- Scale-Invariant Random Spatial Networks.
Electronic J. Probability 19 (2014) article 15: 1--41.
- Interacting Particle Systems as Stochastic Social Dynamics.
Bernoulli 19 (2013) 1122--1149.
- (with Karthik Ganesan)
True scale-invariant random spatial networks.
Proc. Natl. Acad. Sci. USA 110 (2013) 8782-8785.
- (with Mykahlo Shkolnikov)
Fluctuations of martingales and winning probabilities of game contestants.
Electronic J. Probability 18 (2013) article 47: 1--17
- 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 Route-Length
Statistic.
Statistical Science 25 (2010) 275 - 288.
- (with S. Bhamidi)
Edge Flows in the Complete Random-Lengths Network.
Random Structures Alg, 37 (2010) 271-311.
- 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. 35-63.
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 Edge-capacities.
Operations Res. Letters 37 (2009) 299-302.
-
(with Charles Bordenave and Marc Lelarge)
Dynamic Programming Optimization over Random Data: the Scaling Exponent for
Near-optimal Solutions.
SIAM J. Comput. 38 (2009) 2382--2410.
-
Cost-volume relationships for flows through a disordered network.
Math. Oper. Res. 33 (2008) 769--786.
-
(with Charles Bordenave and Marc Lelarge)
Near-Minimal Spanning Trees: a Scaling Exponent in Probability Models.
Ann. Inst. H. Poincare Probab. Statist. 44 (2008) 962-976.
- Spatial Transportation Networks with Transfer Costs: Asymptotic Optimality of Hub and Spoke Models
Math. Proc. Cambridge Philos. Soc. 145 (2008) 471--487.
- (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.
- (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.
- (with Mike Steele)
Asymptotics for Euclidean minimal spanning trees on random points.
Probab. Theory Relat. Fields 92 (1992) 247-258.
- The Continuum Random Tree III Ann. Probab. 21 (1993) 248--289.
- 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.
- Asymptotic fringe distributions for general families of random trees.
Ann. Appl. Probab. 1 (1991) 228-266.
- A Random Tree Model Associated with Random Graphs.
Random Structures Algorithms 1 (1990) 383--402.
-
Threshold Limits for Cover Times.
J. Theoretical Probability
4 (1991) 197-211.
- (with W.B. Krebs)
The Birth-and-Assassination Process.
Stat. Probab. Letters 10 (1990) 427-430.
- The Continuum Random Tree I Ann. Probab. 19 (1991) 1--28.
- The random walk construction of uniform spanning trees and uniform
labelled trees.
SIAM J. Discrete Math. 3 (1990), 450-465.
- Hitting times for random walks on vertex-transitive graphs.
Math. Proc. Cambridge Philos. Soc. 106 (1989) 179-191.
- Meeting Times for Independent Markov Chains.
Stochastic Proc. Appl. 38 (1991), 185-193.
- (with Paul Shields) A diffusion limit for a class of
randomly-growing binary trees Probab. Th. Related Fields 79 (1988), 509-542.
- (with Larry Shepp) The Least Variable Phase Type Distribution is Erlang.
Stochastic Models 3 (1987) 467--473.
- 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