In the mean field (or random link) model there are n points and inter-point distances are independent random variables. For 0 < ℓ < ∞ and in the n → ∞ limit, let δ(ℓ) = 1/n times the maximum number of steps in a path whose average step-length is ≤ ℓ. The function δ(ℓ) is analogous to the percolation function in percolation theory: there is a critical value ℓ* = e-1 at which δ(·) becomes non-zero, and (presumably) a scaling exponent β in the sense δ(ℓ) equivalent to sign (ℓ - ℓ*) β. Recently developed probabilistic methodology (in some sense a rephrasing of the cavity method developed in the 1980s by Mézard and Parisi) provides a simple, albeit non-rigorous, way of writing down such functions in terms of solutions of fixed-point equations for probability distributions. Solving numerically gives convincing evidence that β = 3. A parallel study with trees and connected edge-sets in place of paths gives scaling exponent 2, while the analogue for classical percolation has scaling exponent 1. The new exponents coincide with those recently found in a different context (comparing optimal and near-optimal solutions of the mean-field travelling salesman problem (TSP) and the minimum spanning tree (MST) problem), and reinforce the suggestion that scaling exponents determine universality classes for optimization problems on random points. © 2005 The Royal Society.

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 a rigorous construction of a version of this process and show that one can do explicit calculations of various quantities, for instance the law of the time (if any) that the cluster containing a fixed edge becomes infinite. Surprisingly, the distribution of the shape of a cluster which becomes infinite at time t > 1/2 does not depend on t; it is always distributed as the incipient infinite percolation cluster on the tree. Similarly, a typical finite cluster at each time t > 1/2 has the distribution of a critical percolation cluster. This elaborates an observation of Stockmayer [12]. © 2000 Cambridge Philosophical Society.

We revisit an old topic in algorithms, the deterministic walk on a finite graph which always moves toward the nearest unvisited vertex until every vertex is visited. There is an elementary connection between this cover time and ball-covering (metric entropy) measures. For some familiar models of random graphs, this connection allows the order of magnitude of the cover time to be deduced from first passage percolation estimates. Establishing sharper results seems a challenging problem.

In 1924 Yule 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 relationships between species via phylogenetic trees; the counterpart to Yule's observation is that actual reconstructed trees look surprisingly unbalanced. The imbalance can readily be seen via a scatter diagram of the sizes of clades involved in the splits of published large phylogenetic trees. Attempting stochastic modeling leads to two puzzles. First, two somewhat opposite possible biological descriptions of what dominates the macroevolutionary process (adaptive radiation; "neutral" evolution) lead to exactly the same mathematical model (Markov or Yule or coalescent). Second, neither this nor any other simple stochastic model predicts the observed pattern of imbalance. This essay represents a probabilist's musings on these puzzles, complementing the more detailed survey of biological literature by Mooers and Heard.

Simple random coverage models, well studied in Euclidean space, can also be defined on a general compact metric space S. In one specific model, “seeds" arrive as a Poisson process (in time) at random positions with some distribution θ on S, and create balls whose radius increases at constant rate. By standardizing rates, the cover time C depends only on θ. The value x (S) = minθ (Formula presented)θ C is a numerical characteristic of the compact space S, and we give weak general upper and lower bounds in terms of the covering numbers of S. This suggests a future research program of improving such general bounds, and estimating x(S) for familiar examples of compact spaces. We treat one example, infinite product space [0,1]∞ with the product topology. On a different theme, by analogy with the geometric models, and with the discrete coupon collector's problem and with cover times for finite Markov chains, one expects a “weak concentration" bound for the distribution of C to hold under minimal assumptions. We prove this as a simple consequence of a general result for increasing set-valued Markov processes.

Prediction markets provide a rare setting, where results of mathematical probability theory can be related to events of real-world interest and where theory can be compared to data. The paper discusses two simple mathematical results - the halftime price principle and the serious candidates principle - and corresponding data from baseball and the 2012 Republican Presidential nomination race. © The Mathematical Association of America.

Consider N particles, which merge into clusters according to the following rule: a cluster of size x and a cluster of size y merge at (stochastic) rate K(x, y)/N, were AT is a specified rate kernel. This Marcus-Lushnikov model of stochastic coalescence and the underlying deterministic approximation given by the Smoluchowski coagulation equations have an extensive scientific literature. Some mathematical literature (Kingman's coalescent in population genetics; component sizes in random graphs) implicitly studies the special cases K(x, y) = 1 and K(x, y) = xy. We attempt a wide-ranging survey. General kernels are only now starting to be studied rigorously; so many interesting open problems appear. © 1999 ISI/BS.

In a prediction tournament, contestants “forecast” by asserting a numerical probability for each of (say) 100 future real-world events. The scoring system is designed so that (regardless of the unknown true probabilities) more accurate forecasters will likely score better. This is true for one-on-one comparisons between contestants. But consider a realistic-size tournament with many contestants, with a range of accuracies. It may seem self-evident that the winner will likely be one of the most accurate forecasters. But, in the setting where the range extends to very accurate forecasters, simulations show this is mathematically false, within a somewhat plausible model. Even outside that setting the winner is less likely than intuition suggests to be one of the handful of best forecasters. Though implicit in recent technical papers, this paradox has apparently not been explicitly pointed out before, though is easily explained. It perhaps has implications for the ongoing IARPA-sponsored research programs involving forecasting.