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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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},
}