Gravitational allocation to Poisson points


For $d\ge 3$, we construct a non-randomized, fair, and translation-equivariant allocation of Lebesgue measure to the points of a standard Poisson point process in $\mathbb{R}^d$, defined by allocating to each of the Poisson points its basin of attraction with respect to the flow induced by a gravitational force field exerted by the points of the Poisson process. We prove that this allocation rule is economical in the sense that the allocation diameter, defined as the diameter $X$ of the basin of attraction containing the origin, is a random variable with a rapidly decaying tail. Specifically, we have the tail bound \[\mathbb{P}(X > R) \le C \operatorname{exp}\big[-c R (\log R)^{\alpha_d} \big]\] for all $R>2$, where: $\alpha_d = \frac{d-2}{d}$ for $d\ge 4$; $\alpha_3$ can be taken as any number less than $-4/3$; and $C$ and $c$ are positive constants that depend on $d$ and $\alpha_d$. This is the first construction of an allocation rule of Lebesgue measure to a Poisson point process with subpolynomial decay of the tail $\mathbb{P}(X>R)$.


Sourav Chatterjee

Department of Statistics, 367 Evans Hall, The University of California, Berkeley, CA 94720-3860, United States

Ron Peled

Courant Institute of Mathematical Sciences, New York University, 251 Mercer St., New York, NY 10012-1185, United States

Yuval Peres

Microsoft Research, One Microsoft Way, Redmond, WA 98052-6399, United States

Dan Romik

Department of Mathematics, University of California, Davis, One Shields Ave., Davis, CA 95616, United States