A Stable Marriage of Poisson and Lebesgue
Picture based on research by Christopher Hoffman, Alexander Holroyd and Yuval Peres (scroll down for more information).
What is this?
We start with 300 "centres" (visible as the centres of the concentric
circles), distributed independently uniformly at random in a square.
Each centre has associated with it a region of the square, called its
territory, indicated by concentric annuli in two different colours.
The 300 territories form a partition of the square, and all
territories have equal areas. Note that not all territories are
connected. For example, the centre nearest the top-left corner has a
perfect disc as its territory (indicated in purple and blue); the
territory near the bottom-right corner (indicated in light blue and
brown) has two components. Note also that some territories include parts a very long way from their centres; look at the piece of red and green territory located about one third of the way down the right side.
Such a partition could be achieved in many possible ways, but the one
illustrated is a "canonical" choice. Informally, it is constructed as
follows. Each centre simultaneously starts growing a circle, all at
the same speed. A centre claims all territory encountered by its
circle, unless another centre has claimed it earlier, and until the
centre reaches its "quota" (the area of the square divided by the
number of centres). (Opposite sides of the square are identified, to
form a torus). Without the "quota" restriction, the resulting
territories would be precisely the Voronoi cells, in which each "site"
(location in the square) is allocated to the closest centre.
It is possible to extend the above procedure to the infinite plane (or
to space in any number of dimensions). The analogue of uniformly
distributed centres is called a Poisson process. If the quota equals
1 unit of area, and the intensity of the process (the average number
of centres per unit area) equals 1, then every centre will be
satisfied, and all space will be claimed. (Surprisingly, the same is
not true if we start with an arbitrary set of centres of "intensity" 1
- if the centres form a regular grid with a single centre missing,
then some space will not be claimed in any territory).
Stable Marriage
The above informal description is appealing, but it turns out to be
difficult to make it into a rigorous definition (especially in
infinite space). Instead we may proceed as follows. Suppose that
both sites (that is, ordinary points in space) and centres have
preferences; sites prefer to be in a territory of a nearby centre,
while centres prefer to have a nearby territory. We call a partition
unstable if there exist a site and centre which are not allocated to
each other, but both prefer each other compared with the current
partition. We call a partition stable if it is not unstable. One may
convince oneself that the informal construction above should give rise
to a stable partition. In fact it turns out that there is a unique
stable partition.
The idea of stability as above was introduced by Gale and Shapley in
the context of finite problems involving married couples and college
admissions. Gale and Shapley introduced a celebrated algorithm
(involving iterated proposals and rejections) for constructing stable
marriages. The algorithm may be adapted to our setting and proves the
existence of a stable partition. Stable marriage problems do not in
general have unique solutions, but in our case the preferences of
sites and centres are "consistent", both being based on distance; it
turns out that this guarantees uniqueness.
Geometry
Many questions arise about the shapes of the territories. Here are a
few answers. Each territory is bounded. Any bounded region of the
plane contains parts of only finitely many territories (this is by no
means obvious from the pictures - look at the following closeups of
busy regions of a picture with 10,000 centres). Furthermore each
territory has only finitely many connected components.
Subcritical and Supercritical models
Suppose we keep the intensity of the Poisson process of centres fixed
at 1 per unit area, but vary the "quota" or "appetite", T say, of the
centres. To extend the definition of a stable partition, suppose
also that a site prefers any centre rather than be unclaimed,
while a centre prefers any site rather than be unsated (have a
territory smaller than T). Above we considered the "critical case"
(T=1). In the subcritical case (T<1) some sites are unclaimed, while
in the supercritical case (T>1) some centres are unsated. The
following pictures show the five cases T = 0.2, 0.8, 1, 1.2,
infinity. When T=infinity the territories are the Voronoi cells.
The critical case differs qualitatively from the subcritical and
supercritical cases in more respects than just absence of unclaimed sites
and unsated centres. Roughly, the critical model looks "busier" and
possesses "long-range order". One way to formalize these ideas is to
consider the random variable X defined as the distance from the origin
to the centre whose territory contains the origin (we take X=infinity
if the origin is unclaimed). We expect X to be larger in the critical
case. Indeed, X has (at least) power-law tails in the critical case,
and exponential tails (on the event that it is finite) in the
non-critical cases. Known information about the critical
case varies with dimension, as follows.
| Critical case T=1 |
| Dimension | Lower bound | Upper bound
|
| 1 | E(X1/2)=infinity | E(X1/50) < infinity
|
| 2 | E(X)=infinity | X < infinity a.s.
|
| d>=3 | E(Xd)=infinity | X < infinity a.s.
|
It is an open problem to find any quantitative upper bound on X
in two or more dimensions!
References:
-
A Stable Marriage of Poisson and Lebesgue. (C. Hoffman, A. E. Holroyd
and Y. Peres). Preprint on ArXiv.
-
Extra heads and invariant allocations.
(A. Holroyd and Y. Peres). The Annals of Probability. 33, no.1
(2005).
-
Tail Bounds for the Stable Marriage of
Poisson and Lebesgue. (C. Hoffman, A. Holroyd, Y. Peres).
Preprint on ArXiv.
-
Intriguing Mathematical Picture Merits a
Second Look. (S. Robinson). SIAM News, 38, no. 6,
(2005).