Mathematics of the PWIT
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
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
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,
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.
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