Gravitational allocation to Poisson points

DOI10.4007/ANNALS.2010.172.617MaRDI QIDQ990185zbMATH OpenOpenAlexFDO

Authors Sourav Chatterjee, Ron Peled, Yuval Peres, Dan Romik

Publication date 6 September 2010

Published in Annals of Mathematics. Second Series (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0611886

zbMATH Keywords

allocation allocation diameter basin of attraction gravitational force Lebesgue measure Poisson process

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Point processes (e.g., Poisson, Cox, Hawkes processes) (60G55)

Abstract: For d>=3, we construct a non-randomized, fair and translation-equivariant allocation of Lebesgue measure to the points of a standard Poisson point process in 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: P(X > R) < C exp[ -c R(log R)^(alpha_d) ], for all R>2, where: alpha_d = (d-2)/d for d>=4; alpha_3 can be taken as any number <-4/3; and C,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 P(X>R).

Review text

Let \(Z\) be a stationary simple point process in \(\mathbb{R}^d\) with intensity one. An allocation (of Lebesgue measure to \(Z\)) is a map \(\psi_Z:\mathbb{R}^d\to Z\cup\{\infty\}\) whose inverse map partitions \(\mathbb{R}^d\) into cells of Lebesgue measure one that cover \(\mathbb{R}^d\) almost surely up to a set of measure zero and such that the mapping \(Z\mapsto\psi_Z\) is translation-equivariant. One can view the resulting cells as attracted to the corresponding points of \(Z\). One of the main characteristics of the allocation is the allocation diameter \(X\) being the diameter of the basin of attraction containing the origin, which is well defined if all cells are almost surely bounded. \textit{A. E. Holroyd} and \textit{Y. Peres} [Ann. Probab. 33, No. 1, 31--52 (2005; Zbl 1097.60032)] described an allocation rule for \(Z\) being a Poisson process with unit intensity and shown that if \(d=1,2\), then for every allocation rule one has \(\mathbb{E} X^{d/2}=\infty\), so that \(\mathbb{P}(X>R)\) decays no faster than a polynomial. Another allocation rule (called the stable marriage allocation) described by \textit{C. Hoffman, A. E. Holroyd} and \textit{Y. Peres} [Ann. Probab. 34, No. 4, 1241--1272 (2006; Zbl 1111.60008)] leads to \(\mathbb{E} X^d=\infty\) in every dimension \(d\geq1\). In this paper the authors construct a new allocation rule of Lebesgue measure to the unit rate Poisson point process in \(\mathbb{R}^d\) with dimension \(d\geq 3\). The allocation rule is based on considering the vector field \[ F(x)=\sum_{z\in Z}\frac{z-x}{|z-x|^d}\,, \] where the summands are arranged in order of increasing distance \(|z-x|\) between \(z\) and \(x\). The summands can be interpreted as the gravitational force at location \(x\) incurred by the unit mass located at \(z\) as in the classical Newton case for \(d=3\). The authors prove that the series converges almost surely simultaneously for all \(x\notin Z\) and the random field \(F\) is stationary and almost surely continuously differentiable on its definition domain. The gravitational flow curves are solutions of the equation \(\dot{Y}(t)=F(Y(t))\). The gravitational curve \(Y_x\) starting at \(x\) is well defined up to some positive time \(\tau_x\) that may be infinite. The basin of attraction \(B(z)\) attached to a point \(z\in Z\) is union of \(\{z\}\) and the set of points \(x\notin Z\) such that \(Y_x(t)\to z\) as \(t\uparrow\tau_x\), meaning that the gravitational curve starting from \(x\) ends at \(z\). The allocation rule allocates \(x\) to \(z\) if \(x\in B(z)\) and allocates \(x\) to \(\infty\) if \(x\) does not belong to any \(B(z)\). The main result establishes that the allocation has bounded cells with the allocation diameter having a rapidly decaying tail. Specifically, \[ \mathbb{P}(X>R)\leq C\exp\left[-cR(\log R)^{\alpha_d}\right] \] for all \(R>2\), where \(\alpha_d=(d-2)/d\) for \(d\geq4\); \(\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)\).

Recommendations

Cites work

Cited in

(27)

This page was built for publication: Gravitational allocation to Poisson points

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q990185)