Gravitational allocation to Poisson points

Abstract

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

  • [ajtaietal] Go to document M. Ajtai, J. Komlós, and G. Tusnády, "On optimal matchings," Combinatorica, vol. 4, iss. 4, pp. 259-264, 1984.
    @article {ajtaietal, MRKEY = {779885},
      AUTHOR = {Ajtai, M. and Koml{ó}s, J. and Tusn{á}dy, G.},
      TITLE = {On optimal matchings},
      JOURNAL = {Combinatorica},
      FJOURNAL = {Combinatorica. An International Journal of the János Bolyai Mathematical Society},
      VOLUME = {4},
      YEAR = {1984},
      NUMBER = {4},
      PAGES = {259--264},
      ISSN = {0209-9683},
      CODEN = {COMBDI},
      MRCLASS = {60D05 (60G40 90B15)},
      MRNUMBER = {86f:60018},
      MRREVIEWER = {Richard A. Vitale},
      DOI = {10.1007/BF02579135},
      ZBLNUMBER = {0562.60012},
      }
  • [arnold] V. I. Arnol$’$d, Mathematical Methods of Classical Mechanics, Second ed., New York: Springer-Verlag, 1989.
    @book {arnold, MRKEY = {997295},
      AUTHOR = {Arnol$'$d, V. I.},
      TITLE = {Mathematical Methods of Classical Mechanics},
      SERIES = {Grad. Texts Math.},
      NUMBER = {60},
      EDITION = {Second},
      PUBLISHER = {Springer-Verlag},
      ADDRESS = {New York},
      YEAR = {1989},
      PAGES = {xvi+508},
      ISBN = {0-387-96890-3},
      MRCLASS = {58Fxx (70-02 70H05)},
      MRNUMBER = {90c:58046},
      ZBLCOMMENT = {BIBPROC: YEAR doesn't match found ZBLNUMBER},
      ZBLNUMBER = {0386.70001},
      }
  • [chandrasekhar] Go to document S. Chandrasekhar, "Stochastic problems in physics and astronomy," Rev. Modern Phys., vol. 15, pp. 1-89, 1943.
    @article {chandrasekhar, MRKEY = {0008130},
      AUTHOR = {Chandrasekhar, S.},
      TITLE = {Stochastic problems in physics and astronomy},
      JOURNAL = {Rev. Modern Phys.},
      FJOURNAL = {Reviews of Modern Physics},
      VOLUME = {15},
      YEAR = {1943},
      PAGES = {1--89},
      ISSN = {0034-6861},
      MRCLASS = {60.0X},
      MRNUMBER = {4,248i},
      MRREVIEWER = {J. L. Doob},
      DOI = {10.1103/RevModPhys.15.1},
      ZBLNUMBER={0061.46403},
      }
  • [gravpaper2] S. Chatterjee, R. Peled, Y. Peres, and D. Romik, Phase transitions in gravitational allocation.
    @misc{gravpaper2,
      author={Chatterjee, S. and Peled, R. and Peres, Y. and Romik, D.},
      TITLE={Phase transitions in gravitational allocation},
      NOTE={to appear in {\it Geom. Funct. Anal.}},
      }
  • [grimmett] G. Grimmett, Percolation, Second ed., New York: Springer-Verlag, 1999, vol. 321.
    @book {grimmett, MRKEY = {1707339},
      AUTHOR = {Grimmett, Geoffrey},
      TITLE = {Percolation},
      SERIES = {Grundl. Math. Wissen.},
      VOLUME = {321},
      EDITION = {{S}econd},
      PUBLISHER = {Springer-Verlag},
      ADDRESS = {New York},
      YEAR = {1999},
      PAGES = {xiv+444},
      ISBN = {3-540-64902-6},
      MRCLASS = {60K35 (60-02 82B43)},
      MRNUMBER = {2001a:60114},
      MRREVIEWER = {Neal Madras},
      ZBLNUMBER = {0948.60092},
      }
  • [heathshepp] S. Heath and L. Shepp, "Olbers’ paradox, wireless telephones, and Poisson random sets. Is the universe finite?," in A Garden of Quanta, World Sci. Publ., River Edge, NJ, 2003, pp. 155-166.
    @incollection {heathshepp, MRKEY = {2045964},
      AUTHOR = {Heath, Susan and Shepp, Larry},
      TITLE = {Olbers' paradox, wireless telephones, and {P}oisson random sets. {I}s the universe finite?},
      BOOKTITLE = {A Garden of Quanta},
      PAGES = {155--166},
      PUBLISHER = {World Sci. Publ., River Edge, NJ},
      YEAR = {2003},
      MRCLASS = {82B31 (60G50 85A40 94A05)},
      MRNUMBER = {2004m:82046},
      ZBLNUMBER={1040.83048},
      }
  • [holroydperesmatchings] A. E. Holroyd and Y. Peres, "Trees and matchings from point processes," Electron. Comm. Probab., vol. 8, pp. 17-27, 2003.
    @article {holroydperesmatchings, MRKEY = {1961286},
      AUTHOR = {Holroyd, Alexander E. and Peres, Yuval},
      TITLE = {Trees and matchings from point processes},
      JOURNAL = {Electron. Comm. Probab.},
      FJOURNAL = {Electronic Communications in Probability},
      VOLUME = {8},
      YEAR = {2003},
      PAGES = {17--27},
      ISSN = {1083-589X},
      MRCLASS = {60G55 (60D05 60K35)},
      MRNUMBER = {2004b:60127},
      MRREVIEWER = {Anton Wakolbinger},
      ZBLNUMBER = {1060.60048},
      }
  • [holroydperes] Go to document A. E. Holroyd and Y. Peres, "Extra heads and invariant allocations," Ann. Probab., vol. 33, iss. 1, pp. 31-52, 2005.
    @article {holroydperes, MRKEY = {2118858},
      AUTHOR = {Holroyd, Alexander E. and Peres, Yuval},
      TITLE = {Extra heads and invariant allocations},
      JOURNAL = {Ann. Probab.},
      FJOURNAL = {The Annals of Probability},
      VOLUME = {33},
      YEAR = {2005},
      NUMBER = {1},
      PAGES = {31--52},
      ISSN = {0091-1798},
      CODEN = {APBYAE},
      MRCLASS = {60G55},
      MRNUMBER = {2005k:60153},
      MRREVIEWER = {Wolfgang Freudenberg},
      DOI = {10.1214/009117904000000603},
      ZBLNUMBER = {1097.60032},
      }
  • [kallenberg] O. Kallenberg, Foundations of Modern Probability, Second ed., New York: Springer-Verlag, 2002.
    @book {kallenberg, MRKEY = {1876169},
      AUTHOR = {Kallenberg, Olav},
      TITLE = {Foundations of Modern Probability},
      SERIES = {Probability and its Applications},
      VENUE={New York},
      EDITION = {{S}econd},
      PUBLISHER = {Springer-Verlag},
      ADDRESS = {New York},
      YEAR = {2002},
      PAGES = {xx+638},
      ISBN = {0-387-95313-2},
      MRCLASS = {60-01},
      MRNUMBER = {2002m:60002},
      MRREVIEWER = {Klaus D. Schmidt},
      ZBLNUMBER = {0996.60001},
      }
  • [stablemarriage1] Go to document C. Hoffman, A. E. Holroyd, and Y. Peres, "A stable marriage of Poisson and Lebesgue," Ann. Probab., vol. 34, iss. 4, pp. 1241-1272, 2006.
    @article {stablemarriage1, MRKEY = {2257646},
      AUTHOR = {Hoffman, Christopher and Holroyd, Alexander E. and Peres, Yuval},
      TITLE = {A stable marriage of {P}oisson and {L}ebesgue},
      JOURNAL = {Ann. Probab.},
      FJOURNAL = {The Annals of Probability},
      VOLUME = {34},
      YEAR = {2006},
      NUMBER = {4},
      PAGES = {1241--1272},
      ISSN = {0091-1798},
      CODEN = {APBYAE},
      MRCLASS = {60D05 (60G55)},
      MRNUMBER = {2007k:60034},
      MRREVIEWER = {Dominic Schuhmacher},
      DOI = {10.1214/009117906000000098},
      ZBLNUMBER = {1111.60008},
      }
  • [stablemarriage2] Go to document C. Hoffman, A. E. Holroyd, and Y. Peres, "Tail bounds for the stable marriage of Poisson and Lebesgue," Canad. J. Math., vol. 61, iss. 6, pp. 1279-1299, 2009.
    @article {stablemarriage2, MRKEY = {2588423},
      AUTHOR = {Hoffman, Christopher and Holroyd, Alexander E. and Peres, Yuval},
      TITLE = {Tail bounds for the stable marriage of {P}oisson and {L}ebesgue},
      JOURNAL = {Canad. J. Math.},
      FJOURNAL = {Canadian Journal of Mathematics. Journal Canadien de Mathématiques},
      VOLUME = {61},
      YEAR = {2009},
      NUMBER = {6},
      PAGES = {1279--1299},
      ISSN = {0008-414X},
      CODEN = {CJMAAB},
      MRCLASS = {60D05 (60G55)},
      MRNUMBER = {2588423},
      URL = {http://journals.cms.math.ca/ams/ams-redirect.php?Journal=CJM&Volume=61&FirstPage=1279},
      ZBLNUMBER = {05644856},
      }
  • [leightonshor] Go to document T. Leighton and P. Shor, "Tight bounds for minimax grid matching with applications to the average case analysis of algorithms," Combinatorica, vol. 9, iss. 2, pp. 161-187, 1989.
    @article {leightonshor, MRKEY = {1030371},
      AUTHOR = {Leighton, T. and Shor, P.},
      TITLE = {Tight bounds for minimax grid matching with applications to the average case analysis of algorithms},
      JOURNAL = {Combinatorica},
      FJOURNAL = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},
      VOLUME = {9},
      YEAR = {1989},
      NUMBER = {2},
      PAGES = {161--187},
      ISSN = {0209-9683},
      CODEN = {COMBDI},
      MRCLASS = {05B99 (60C05 68Q25 68R05)},
      MRNUMBER = {90k:05056},
      MRREVIEWER = {Mark R. Jerrum},
      DOI = {10.1007/BF02124678},
      ZBLNUMBER = {0686.68039},
      }
  • [mattila] Go to document P. Mattila, Geometry of Sets and Measures in Euclidean Spaces, Cambridge: Cambridge Univ. Press, 1995, vol. 44.
    @book {mattila, MRKEY = {1333890},
      AUTHOR = {Mattila, Pertti},
      TITLE = {Geometry of Sets and Measures in {E}uclidean Spaces},
      SERIES = {Cambridge Stud. Adv. Math.},
      VOLUME = {44},
      PUBLISHER = {Cambridge Univ. Press},
      ADDRESS = {Cambridge},
      YEAR = {1995},
      PAGES = {xii+343},
      ISBN = {0-521-46576-1; 0-521-65595-1},
      MRCLASS = {28A75 (49Q20)},
      MRNUMBER = {96h:28006},
      MRREVIEWER = {Harold Parks},
      DOI = {10.1017/CBO9780511623813},
      ZBLNUMBER = {0819.28004},
      }
  • [nazarovetal1] Go to document F. Nazarov, M. Sodin, and A. Volberg, "Transportation to random zeroes by the gradient flow," Geom. Funct. Anal., vol. 17, iss. 3, pp. 887-935, 2007.
    @article {nazarovetal1, MRKEY = {2346279},
      AUTHOR = {Nazarov, Fedor and Sodin, Mikhail and Volberg, Alexander},
      TITLE = {Transportation to random zeroes by the gradient flow},
      JOURNAL = {Geom. Funct. Anal.},
      FJOURNAL = {Geometric and Functional Analysis},
      VOLUME = {17},
      YEAR = {2007},
      NUMBER = {3},
      PAGES = {887--935},
      ISSN = {1016-443X},
      CODEN = {GFANFB},
      MRCLASS = {60G55 (30C15 30D15 31A35 60G15)},
      MRNUMBER = {2009c:60124},
      MRREVIEWER = {Lutz Peter Klotz},
      DOI = {10.1007/s00039-007-0613-z},
      ZBLNUMBER = {1153.60027},
      }
  • [nazarovetal2] Go to document F. Nazarov, M. Sodin, and A. Volberg, "Transportation to random zeroes by the gradient flow," Geom. Funct. Anal., vol. 17, iss. 3, pp. 887-935, 2007.
    @article {nazarovetal2, MRKEY = {2346279},
      AUTHOR = {Nazarov, Fedor and Sodin, Mikhail and Volberg, Alexander},
      TITLE = {Transportation to random zeroes by the gradient flow},
      JOURNAL = {Geom. Funct. Anal.},
      FJOURNAL = {Geometric and Functional Analysis},
      VOLUME = {17},
      YEAR = {2007},
      NUMBER = {3},
      PAGES = {887--935},
      ISSN = {1016-443X},
      CODEN = {GFANFB},
      MRCLASS = {60G55 (30C15 30D15 31A35 60G15)},
      MRNUMBER = {2009c:60124},
      MRREVIEWER = {Lutz Peter Klotz},
      DOI = {10.1007/s00039-007-0613-z},
      ZBLNUMBER = {1153.60027},
      }
  • [sodintsirelson] Go to document M. Sodin and B. Tsirelson, "Random complex zeroes. II. Perturbed lattice," Israel J. Math., vol. 152, pp. 105-124, 2006.
    @article {sodintsirelson, MRKEY = {2214455},
      AUTHOR = {Sodin, Mikhail and Tsirelson, Boris},
      TITLE = {Random complex zeroes. {II}. {P}erturbed lattice},
      JOURNAL = {Israel J. Math.},
      FJOURNAL = {Israel Journal of Mathematics},
      VOLUME = {152},
      YEAR = {2006},
      PAGES = {105--124},
      ISSN = {0021-2172},
      CODEN = {ISJMAP},
      MRCLASS = {60G15 (30D20 60D05)},
      MRNUMBER = {2007a:60027},
      MRREVIEWER = {M. Iosifescu},
      DOI = {10.1007/BF02771978},
      ZBLNUMBER={1125.60033},
      }
  • [talagrand] Go to document M. Talagrand, "Matching theorems and empirical discrepancy computations using majorizing measures," J. Amer. Math. Soc., vol. 7, iss. 2, pp. 455-537, 1994.
    @article {talagrand, MRKEY = {1227476},
      AUTHOR = {Talagrand, M.},
      TITLE = {Matching theorems and empirical discrepancy computations using majorizing measures},
      JOURNAL = {J. Amer. Math. Soc.},
      FJOURNAL = {Journal of the American Mathematical Society},
      VOLUME = {7},
      YEAR = {1994},
      NUMBER = {2},
      PAGES = {455--537},
      ISSN = {0894-0347},
      MRCLASS = {60C05 (60D05)},
      MRNUMBER = {94g:60021},
      MRREVIEWER = {Joseph E. Yukich},
      DOI = {10.2307/2152764},
      ZBLNUMBER = {0810.60036},
      }

Authors

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