We consider the gravitational allocation to the standard
Poisson process in $R^d$ for $d\geq 3$. An allocation is a way of
partitioning $R^d$ into cells having volume exactly 1 and matching them
with the Poisson process points in a
translation equivariant way.
In other words, it is an algorithm which assigns each Poisson point a
unit volume cell (where cells are disjoint and exhaust $R^d$) with the
additional property that when performing that algorithm on a shifted
realization of the points, it returns the shift of the output on the
original realization.
The gravitational allocation
is a particular allocation rule inspired by
recent work of Nazarov, Tsirelson, Sodin and Volberg that is defined by
flow along the integral curves of a
gravitational force field induced by the Poisson points.
An allocation is considered more efficient if its cells are small
in some sense. We consider the cell containing the
origin, which is a typical cell by the translation equivariance,
and examine several measures of its size:\\
1) $X$ - The diameter of the cell.\\
2) $Y$ - The distance from a uniform point in the cell to the Poisson
point.\\
3) $Z_R$ - The volume left in the cell after removing a ball of
radius R around the Poisson point.\\
We discover the
characteristic exponents of the process corresponding to these measures.
We show that
$P(X > R) = \exp(-R^{1+o(1)})$,
$P(Y > R) = \exp(-R^{a_d+o(1)})$ where $a_3=1$ and $a_d=1+1/(d-1)$ for
$d>3$,
and $P(Z_R > \exp(-R^t)) = \exp(-R^{f_d(t)+o(1)})$ for $t>0$
and an explicit piecewise linear $f_d(t)$. We observe a phase
transition in the behavior of the allocation as the dimension increases
which occurs inside dimension $4$. The function
$f_d(t)$ behaves in one way for $d\geq 5$,
in a different way for $d=3$ and makes a
transition between these two behaviors in
dimension $4$ when $t=3/2$.
We explain this phase transition by showing that it follows from
a competition between the
probability that the Poisson process has many points in a small region and
the decay of the gravitational potential kernel.
For the Poisson process, this is the first deterministic allocation rule
shown to have exponential decay of these probabilities.\\
This is joint work with Sourav Chatterjee, Yuval Peres and Dan Romik.
Click
HERE for this
abstract in PDF format