Selected Publications

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
  • Paper
• (with S. Bhamidi) Edge Flows in the Complete Random-Lengths Network
  • Abstract
  • Paper
• Spatial Transportation Networks with Transfer Costs: Asymptotic Optimality of Hub and Spoke Models
  • Abstract
  • Paper
• (with Charles Bordenave and Marc Lelarge) Dynamic Programming Optimization over Random Data: the Scaling Exponent for Near-optimal Solutions
  • Abstract
  • Paper
• (with Charles Bordenave and Marc Lelarge) Near-Minimal Spanning Trees: a Scaling Exponent in Probability Models
  • Abstract
  • Paper
• Cost-volume relationships for flows through a disordered network
  • Abstract
  • Paper

Research Papers

• (with Wilf Kendall) Short-length routes in low-cost networks via Poisson line patterns. Adv. Appl. Probability 40 (2008) 1-21.
  • Abstract
  • Paper
• (with Maxim Krikun and Lea Popovic) Stochastic Models for Phylogenetic Trees on Higher-order Taxa. J. Math. Biology 56 (2008) 525-557.
  • Abstract
  • Paper
• Optimal spatial transportation networks where link-costs are sublinear in link-capacity. J. Stat. Mech. (2008) P03006.
  • Abstract
  • Paper
• (with Russ Lyons) Processes on Unimodular Random Networks. Electronic J. Probab. 12 (2007) 1454-1508.
  • Abstract and Paper
• Optimal flow through the disordered lattice. Annals of Probability 35 (2007) 397--438.
  • Abstract
  • Paper
• (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.
  • Abstract
  • Paper
  • Appendix with some simulations
• (with Lea Popovic) A Critical Branching Process Model for Biodiversity. Advances Applied Probability 37 (2005) 1094-1115.
  • Abstract
  • Paper
  • Pictures of simulations
• (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.
  • Abstract
  • Paper
• (with Antar Bandyopadhyay) A Survey of Max-type Recursive Distributional Equations. Annals of Applied Probability 15 (2005) 1047-1110.
  • Abstract
  • Paper
• 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.
  • Paper
• (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.
  • Abstract
  • Paper
• (with Gregory Miermont and Jim Pitman) Brownian Bridge Asymptotics for Random p-mappings. Electronic J. Probab. 9 (2004) 37 - 56.
  • Abstract
  • Paper
• 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.
  • Abstract
  • Paper
  • Slides from Talk
• A Stochastic Complex Network Model. Electron. Res. Announc. Amer. Math. Soc. 9 (2003), 152-161.
  • Abstract and link to paper
• (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.
  • Paper
  • Slides from talk
• (with Allon Percus) Scaling and Universality in Continuous length Combinatorial Optimization. Proc. Natl. Acad. Sci. USA 100 (2003) 11211-11215.
  • Abstract
  • Paper
  • Slides from talk
• (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.
  • Abstract
  • Paper
• (with Jim Pitman) The Asymptotic Distribution of the Diameter of a Random Mapping. C. R. Math. Acad. Sci. Paris 334 (2002) 1-4.
  • Abstract
  • Paper
• (with Persi Diaconis) The Asymmetric One-dimensional Constrained Ising Model: Rigorous Results. J. Statist. Phys. 107 (2002) 945-975.
  • Abstract
  • Paper
  • Slides from Talk
• (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.
  • Abstract
  • Paper
• (with Antar Bandyopadhyay) How to Combine Fast heuristic Markov Chain Monte Carlo with Slow Exact Sampling. Electronic Commun. Probab. 6 (2001) 79-89.
  • Abstract
  • Paper
  • Slides from Talk
• Stochastic Models and Descriptive Statistics for Phylogenetic Trees, from Yule to Today. (revision of Visualizing Phylogenetic Tree Balance ). Statistical Science 16 (2001) 23-34.
  • Paper
  • More scatterplots, not in paper, of splits in phylogenetic trees
• The zeta(2) Limit in the Random Assignment Problem. Random Structures and Algorithms 18 (2001) 381-418.
  • Paper
  • Abstract
  • Slides from Talk given in Berkeley (October 2000).
• Reorganizing Large Web Sites. Amer. Math. Monthly 108 (2001) 16-27.
  • Paper
• (with Jim Pitman) Inhomogeneous Continuum Random Trees and the Entrance Boundary of the Additive Coalescent. Probab. Th. Related Fields 118 (2000) 455-482.
  • Abstract
  • Paper
• (with Boris Pittel) On a Random Graph with Immigrating Vertices: Emergence of the Giant Component. Random Structures Algorithms 17 (2000) 79-102.
  • Abstract
  • Paper
• Mixing Time for a Markov Chain on Cladograms. Combinatorics, Probability and Computing 9 (2000) 191-204.
  • Abstract
  • Paper
• The Percolation Process on a Tree where Infinite Clusters are Frozen. Math. Proc. Cambridge Philos. Soc. 128 (2000) 465-477.
  • Abstract
  • Paper
• (with Persi Diaconis) Longest Increasing Subsequences: From Patience Sorting to the Baik-Deift-Johansson Theorem. Bull. Amer. Math. Soc. 36 (1999) 413-432.
  • Abstract
  • Paper
• (with Steven Evans) Dirichlet Forms on Totally Disconnected Spaces and Bipartite Markov chains. J. Theoretical Probab 12 (1999) 839-858.
  • Abstract
  • Paper
• (with Jim Pitman) A Family of Random Trees with Random Edge Lengths. Random Structures Algorithms 15 (1999) 176-195.
  • Abstract
  • Paper
• Deterministic and Stochastic Models for Coalescence (Aggregation, Coagulation): A Review of the Mean-Field Theory for Probabilists. Bernoulli 5 (1999) 3-48.
  Paper and Paper in PDF
• (with Jim Pitman) The Standard Additive Coalescent. Annals of Probability 26 (1998) 1703-1726.
  • Abstract
  • Paper
• A Metropolis-Type Optimization Algorithm on the Infinite Tree. Algorithmica 22 (1998) 388-412.
  Paper
• Brownian Excursion Conditioned on its Local Time Electronic Commun. Probab. 3 (1998) 79-90.
  • Abstract
  • Paper
• (with Jim Pitman) Tree-Valued Markov Chains Derived from Galton-Watson Processes. Ann. Inst. Henri Poincare. 34 (1998) 637-686.
  • Abstract
  • Paper
• Stochastic Coalescence. In Proceedings ICM 1998, volume 3, p. 205-211. Special volume of Documenta Mathematica (1998).
  Paper
• On the Critical Value for ``Percolation" of Minimum-Weight Trees in the Mean-Field Distance Model. Combinatorics, Probability and Computing 7 (1998) 1-10.
  • Abstract
  • Paper
• 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.
  • Paper
• Emergence of the Giant Component in Special Marcus-Lushnikov Processes. Random Structures Algorithms 12 (1998) 179-196.
  Paper and figure 1 and figure 2 and figure 3
• (with Vlada Limic) The Entrance Boundary of the Multiplicative Coalescent Electronic J. Probab. 3 (1998) 1-59.
  • Abstract
  • Paper
• (with L. Lovasz and P. Winkler) Mixing Times for Uniformly Ergodic Markov Chains. Stochastic Process. Appl. 71 (1997), 165-185.
  • Abstract
  • Paper
• 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.