Mathematics of the PWIT

Background

There is a basic Euclidean model for random points in (say) two dimensional space. Take n random points distributed independently and uniformly over some region in the plane; for definiteness take the region to a square centered at the origin, and as a useful scaling convention take the region to have area = n so there is density 1 point per unit area. In this setting there is a well-known limit process as n tends to infinity, the Poisson point process in the plane with intensity 1 per unit area. Many problems concerning random points are most conveniently viewed in terms of the Poisson process. For combinatorial optimization problems exemplified by the TSP, while various mathematical results about the optimal solutions are known (see e.g. Probability Theory and Combinatorial Optimization by Mike Steele), these tend not to be explicit formulas.

There is a less realistic but more mathematically tractable model, known as the random link model or as the complete graph with random edge-lengths model, but for which I prefer the more descriptive name stochastic mean-field model of distance. Here we take n points as vertices of a graph (without any d-dimensional geometry). For each of the n(n-1)/2 pairs of points, create an edge between them with random length. These edge-lengths are independent for different edges, as distributed as Exponential (mean n) random variables L; that is, P(L > x) = exp(-x/n).

It is not quite obvious, but there is a limit of this model as n tends to infinity. Consider a typical vertex; write d(1), d(2),...., d(n-1) for the edge-lengths at that vertex, in increasing order. As n tends to infinity, these ordered edge-lengths have a limit, the Poisson point process of rate 1, characterized by the property that the random variables d(1), d(2) - d(1), d(3) - d(2), ..... are independent with the Exponential (mean 1) distribution: P(d(i+1) - d(i) > x) = exp(-x). This motivates the definition below.

Definition of the PWIT

Take a ``root" vertex. Create an infinite number of edges at the root, whose lengths d(1), d(2), d(3), ..... are random, distributed as a Poisson point process of rate 1. Proceed recursively: for each vertex at the other end of an edge, create an infinite number of edges at that vertex, whose lengths form an independent Poisson point process of rate 1. Continuing in this way we construct an infinite tree with random edge-lengths; PWIT stands for Poisson weighted infinite tree.

Mathematically, the intrinsic structure of a realization of the PWIT is just the collection of all edge-lengths. In drawing a 2-dimensional picture, we insist that edge-lengths be correct, but other aspects (angles between edges) are arbitrary (in the sense of not being part of the mathematical structure). Because there is no external coordinate system to label vertices, we always work relative to some root vertex, but we can re-root at any vertex.

Mathematics on the PWIT

A main motivation for study of the PWIT is that for various problems, in particular combinatorial optimization problems, in the stochastic mean-field model of distance, the n tends to infinity limit solutions can be identified with the solutions of the corresponding problem on the PWIT. Thus one wants to do ``mathematics on the PWIT" to find the solutions. The actual mathematics involved is too complicated to explain here; the purpose of this site is to show what the solutions on the PWIT actually look like.

Further reading

There is no very non-technical further reading, but the survey paper The Objective Method: Probabilistic Combinatorial Optimization and Local Weak Convergence is accessible to readers with some basic familiarity with mathematical probability.

Back to Java simulation page