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).