Summary: 4X games are a genre of modern computer games, exemplified by the Civilization series, whose initial stages implicitly involve exploring an unknown graph. One exploration scheme is “move to nearest unvisited vertex” and this is in fact forced in the game Endless Space. We revisit the small body of old “worst case” results about the efficiency of this scheme, and comment on the unstudied “average case” problem.

We show that, in the usual probabilistic model for the random assignment problem, the optimal cost tends to a limit constant in probability and in expectation. The method involves construction of an infinite limit structure, in terms of which the limit constant is defined. But we cannot improve on the known numerical bounds for the limit. © 1992 Springer-Verlag.

Is there a constant r0 such that, in any invariant tree network linking rate-1 Poisson points in the plane, the mean within-network distance between points at Euclidean distance r is infinite for r > r0? We prove a slightly weaker result. This is a continuum analog of a result of Benjamini et al (2001) on invariant spanning trees of the integer lattice.

Intuitively one expects that for any plausible parametric epidemic model, there will be some region in parameter-space where the epidemic affects (with high probability) only a small proportion of a large population, another region where it affects (with high probability) a nonnegligible proportion, with a lower-dimensional “critical” interface. This dichotomy is certainly true in well-studied specific models, but we know of no very general results. A recent result stated for a bond percolation model can be restated as giving weak conditions under which the dichotomy holds for an SI epidemic model on arbitrary finite networks. This result suggests a conjecture for more complex and more realistic SIR epidemic models, and the purpose of this article** is to record the conjecture.

In a simple model for sports, the probability A beats B is a specified function of their difference in strength. One might think this would be a staple topic in Applied Probability textbooks (like the Galton-Watson branching process model, for instance) but it is curiously absent. Our first purpose is to point out that the model suggests a wide range of questions, suitable for "undergraduate research" via simulation but also challenging as professional research. Our second, more specific, purpose concerns Elo-type rating algorithms for tracking changing strengths. There has been little foundational research on their accuracy, despite a much-copied "30 matches suffice" claim, which our simulation study casts doubt upon.

The style of mathematical models known to probabilists as Interacting Particle Systems and exemplified by the Voter, Exclusion and Contact processes have found use in many academic disciplines. In many such disciplines the underlying conceptual picture is of a social network, where individuals meet pairwise and update their "state" (opinion, activity etc) in a way depending on the two previous states. This picture motivates a precise general setup we call Finite Markov Information Exchange (FMIE) processes. We briefly describe a few less familiar models (Averaging, Compulsive Gambler, Deference, Fashionista) suggested by the social network picture, as well as a few familiar ones. © 2013 ISI/BS.

Consider routing traffic on the N × N torus, simultaneously between all source-destination pairs, to minimize the cost ∑ec(e)f 2(e). where f(e) is the volume of flow across edge e and the c(e) form an i.i.d. random environment. We prove existence of a rescaled N → ∞ limit constant for minimum cost, by comparison with an appropriate analogous problem about minimum-cost flows across a M × M subsquare of the lattice. © Institute of Mathematical Statistics, 2007.

Jim Pitman was born in June 1949, received a Ph.D. in 1974 from the University of Sheffield with advisor Terry Speed, and since 1979 has been in the U.C. Berkeley Statistics department. He is known for research on many topics within probability, in particular for a long-running collaboration with Marc Yor on distributional properties of Brownian motion, and for his influential lecture notes Combinatorial Stochastic Processes. The following conversation took place at his home in December 2017 and February 2018.

Consider the complete n-graph with independent exponential (mean n) edge-weights. Let M(c, n) be the maximal size of subtree for which the average edge-weight is at most c. It is shown that M(c, n) makes the transition from o(n) to Ω(n) around some critical value c(0), which can be specified in terms of a fixed point of a mapping on probability distributions.