More Uses of Exchangeability: Representations of Complex Random Structures (2009)
We review old and new uses of exchangeability, emphasizing the general theme of exchangeable representations of complex random structures. Illustrations of this theme include processes of stochastic...
Optimal spatial transportation networks where link-costs are sublinear in link-capacity (2008)
Consider designing a transportation network on $n$ vertices in the plane, with traffic demand uniform over all source-destination pairs. Suppose the cost of a link of length $\ell$ and capacity $c$...
Uniform Multicommodity Flow through the Complete Graph with Random Edge-capacities (2008)
David J. Aldous, Colin Mcdiarmid, Alex Scott
Give random capacities C to the edges of the complete n-vertex graph. Consider the maximum flow Φn that can be simultaneously routed between each source-destination pair. We prove that Φn → φ in...
The i(2) Limit in the Random Assignment Problem (2007)
The random assignment (or bipartite matching) problem asks about
Threshold Phenomena in an "easy" Class of Random Lattices and Efficient Reduction Algorithms (2007)
this paper is to give a simple proof of the following theorem:
Processes on Unimodular Random Networks (2007)
Aldous, David J.; University Of California, Berkeley; Aldous@stat.Berkeley.EDU, Lyons, Russell; Indiana University; Rdlyons@indiana.edu
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....
WITH SLOW EXACT SAMPLING (2007)
Markov Chain, Monte Carlo, Antar Bandyopadhyay, David J. Aldous
Given a probability law on a set S and a function g: S! R, suppose one wants to estimate the mean g = R g d. The Markov Chain Monte Carlo method consists of inventing and simulating a Markov chain...
Antar Bandyopadhyay, David J. Aldous
Given a probability law on a set S and a function g: S! R, suppose one wants to estimate the mean g =
Aldous, David J., Bordenave, Charles, Lelarge, Marc
A very simple example of an algorithmic problem solvable by dynamic programming is to maximize, over sets A in {1,2,...,n}, the objective function |A| - \sum_i \xi_i 1(i \in A,i+1 \in A) for given...
Edge Flows in the Complete Random-Lengths Network (2007)
Aldous, David J., Bhamidi, Shankar
Consider the complete n-vertex graph whose edge-lengths are independent exponentially distributed random variables. Simultaneously for each pair of vertices, put a constant flow between them along...
Short-length routes in low-cost networks via Poisson line patterns (2007)
Aldous, David J., Kendall, Wilfrid S.
In designing a network to link n cities in a square of area n, one might be guided by the following two desiderata. First, the total network length should not be much greater than the length of the...
Route-Length Efficiency in Spatial Transportation Networks (2007)
David J. Aldous, Yanjiao Cheng, Jesse Friedman, Yu-jay Huoh, Wayne Lee, Harrison Liu
In networks such as inter-city road or rail networks, a natural notion of “efficiency ” is that the route length ℓ(i, j) between typical cities i, j be not much longer than straight line...
Edge Flows in the Complete Random-Lengths Network. eprint arXiv: 0708.0555 (2007)
David J. Aldous, Shankar Bhamidi
Consider the complete n-vertex graph whose edge-lengths are independent exponentially distributed random variables. Simultaneously for each pair of vertices, put a constant flow between them along...
Mathematical Analysis of Subjectively Defined Coincidences; a case study using Wikipedia (2006)
Fayd Shelley. Rationalists assert that real-life coincidences occur no more frequently than is predictable by chance, but (outside stylized settings such as birthdays) empirical evidence is scant. We...
Percolation-like scaling exponents for minimal paths and trees in the stochastic mean-field (2005)
Abstract In the mean field (or random link) model there are n points andinter-point distances are independent random variables. For 0 < ` < 1and in the n! 1 limit, let ffi(`) = 1/n * (maximum...
informs doi 10.1287/moor.1080.0327
A tractable complex network model based on the stochastic mean-field model of distance (2003)
Abstract. Much recent research activity has been devoted to empirical study and theoretical models of complex networks (random graphs) possessing three qualitative features: power-law degree...
How to Combine Fast Heuristic Markov Chain Monte Carlo with Slow Exact Sampling (2001)
Bandyopadhyay, Antar; University Of California, Berkeley; Antar@stat.berkeley.edu, Aldous, David J.; University Of California, Berkeley; Aldous@stat.berkeley.edu
Given a probability law $pi$ on a set S and a function $g : S rightarrow R$, suppose one wants to estimate the mean $bar{g} = int g dpi$. The Markov Chain Monte Carlo method consists of inventing and...
Stochastic models and descriptive statistics for phylogenetic trees, from Yule to today (2001)
Yule (1924) observed that distributions of number of species per genus were typically long-tailed, and proposed a stochastic model to fit this data. Modern taxonomists often prefer to represent...
Stochastic Models and Descriptive Statistics for Phylogenetic Trees, from Yule to Today (2001)
Yule (1924) observed that distributions of number of species per genus were typically long-tailed, and proposed a stochastic model to fit these data. Modern taxonomists often prefer to represent...
COMMUNICATIONS in PROBABILITY HOW TO COMBINE FAST HEURISTIC (2001)
Markov Chain, Monte Carlo, David J. Aldous
Given a probability law π on a set S and a function g: S → R, suppose one wants to estimate the mean ¯g = � gdπ. The Markov Chain Monte Carlo method consists of inventing and simulating a...
The Percolation Process on a Tree Where Infinite Clusters are Frozen (1999)
Modify the usual percolation process on the infinite binary tree by forbidding infinite clusters to grow further. The ultimate configuration will consist of both infinite and finite clusters. We give...
On a Randomly Evolving Graph: Emergence of the Giant Component (1999)
A randomly evolving graph, with vertices immigrating at rate n and each possible edge appearing at rate 1=n, is studied. The detailed picture of emergence of giant components with O(n 2=3 ) vertices...
Brownian Excursion Conditioned on Its Local Time (1998)
Aldous, David J.; University Of California, Berkeley; Aldous@stat.berkeley.edu
For a function $ell$ satisfying suitable integrability (but not continuity) requirements, we construct a process $(B^ell_u, 0 leq u leq 1)$ interpretable as Brownian excursion conditioned to have...
Mixing Time for a Markov Chain on Cladograms (1998)
A cladogram is a tree with labeled leaves and unlabeled degree-3 branchpoints. A certain Markov chain on the set of n-leaf cladograms consists of removing a random leaf (and its incident edge) and...
Brownian Excursion Conditioned On Its Local Time (1998)
this paper is to present a construction, which can be outlined as follows.
Visualizing Phylogenetic Tree Balance (1998)
A certain graphical display of the sizes of clades involved in the splits of a phylogenetic tree both demonstrates the known poor fit of the simplest stochastic null models and suggests alternative...
. Consider N particles, which merge into clusters according to the rule: a cluster of size x and a cluster of size y merge at (stochastic) rate K(x; y)=N , where K is a specified rate kernel. This...
Consider N particles, which merge into clusters according to the rule: a cluster of size x and a cluster of size y merge at (stochastic) rate K(x; y)=N , where K is a specified rate kernel. This...
Brownian Excursions, Critical Random Graphs and the Multiplicative Coalescent (1996)
Let (B t (s); 0 s ! 1) be reflecting inhomogeneous Brownian motion with drift t \Gamma s at time s, started with B t (0) = 0. Consider the random graph G(n; n \Gamma1 +tn \Gamma4=3 ), whose largest...
Inequalities for Rare Events in Time-Reversible Markov Chains II (1993)
A previous paper discussed explicit bounds in the exponential approximation for the distribution of the waiting time until a stationary reversible Markov chain first enters a "rare" subset...
Inequalities for Rare Events in Time-Reversible Markov Chains I (1992)
The distribution of waiting time until a rare event is often approximated by the exponential distribution. In the context of first hitting times for stationary reversible chains, the error has a...
A random walk construction of uniform spanning trees and uniform labelled trees (1990)
Abstract A random walk on a finite graph can be used to construct a uniformrandom spanning tree. We show how random walk techniques can be applied to the study of several properties of the uniform...
North-Holland Meeting times for independent Markov chains (1988)
Start two independent copies of a reversible Markov chain from arbitrary initial states. Then the expected time until they meet is bounded by a constant times the maximum first hitting time for the...
Representations for partially exchangeable arrays of random variables
Consider an array of random variables (Xi,j), 1
Stein's method in a two-dimensional coverage problem
Consider a Poisson process of unit squares in the plane, with intensity [theta]. Let q(L, [theta]) be the chance that an L x L square is completely covered by the randomly-positioned unit squares....