Geodesic
Tail Bounds for the Stable Marriage of Poisson and Lebesgue
Canadian journal of mathematics, Tome 61 (2009) no. 6, pp. 1279-1299

Voir la notice de l'article provenant de la source Cambridge University Press

Let $\Xi $ be a discrete set in ${{\mathbb{R}}^{d}}$ . Call the elements of $\Xi $ centers. The well-known Voronoi tessellation partitions ${{\mathbb{R}}^{d}}$ into polyhedral regions (of varying volumes) by allocating each site of ${{\mathbb{R}}^{d}}$ to the closest center. Here we study allocations of ${{\mathbb{R}}^{d}}$ to $\Xi $ in which each center attempts to claim a region of equal volume $\alpha $ .We focus on the case where $\Xi $ arises from a Poisson process of unit intensity. In an earlier paper by the authors it was proved that there is a unique allocation which is stable in the sense of the Gale–Shapley marriage problem. We study the distance $X$ from a typical site to its allocated center in the stable allocation.The model exhibits a phase transition in the appetite $\alpha $ . In the critical case $\alpha \,=\,1$ we prove a power law upper bound on $X$ in dimension $d\,=\,1$ . (Power law lower bounds were proved earlier for all $d$ ). In the non-critical cases $\alpha <1$ and $\alpha \,>1$ we prove exponential upper bounds on $X$ .
DOI : 10.4153/CJM-2009-060-7
Mots-clés : 60D05, stable marriage, point process, phase transition 
Hoffman, Christopher; Holroyd, Alexander E.; Peres, Yuval. Tail Bounds for the Stable Marriage of Poisson and Lebesgue. Canadian journal of mathematics, Tome 61 (2009) no. 6, pp. 1279-1299. doi: 10.4153/CJM-2009-060-7
@article{10_4153_CJM_2009_060_7,
     author = {Hoffman, Christopher and Holroyd, Alexander E. and Peres, Yuval},
     title = {Tail {Bounds} for the {Stable} {Marriage} of {Poisson} and {Lebesgue}},
     journal = {Canadian journal of mathematics},
     pages = {1279--1299},
     year = {2009},
     volume = {61},
     number = {6},
     doi = {10.4153/CJM-2009-060-7},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-2009-060-7/}
}
TY  - JOUR
AU  - Hoffman, Christopher
AU  - Holroyd, Alexander E.
AU  - Peres, Yuval
TI  - Tail Bounds for the Stable Marriage of Poisson and Lebesgue
JO  - Canadian journal of mathematics
PY  - 2009
SP  - 1279
EP  - 1299
VL  - 61
IS  - 6
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CJM-2009-060-7/
DO  - 10.4153/CJM-2009-060-7
ID  - 10_4153_CJM_2009_060_7
ER  - 
%0 Journal Article
%A Hoffman, Christopher
%A Holroyd, Alexander E.
%A Peres, Yuval
%T Tail Bounds for the Stable Marriage of Poisson and Lebesgue
%J Canadian journal of mathematics
%D 2009
%P 1279-1299
%V 61
%N 6
%U http://geodesic.mathdoc.fr/articles/10.4153/CJM-2009-060-7/
%R 10.4153/CJM-2009-060-7
%F 10_4153_CJM_2009_060_7

[1] [1] Feller, W., An introduction to probability theory and its applications. II. John Wiley &amp; Sons, New York, 1966. Google Scholar

[2] [2] Gale, D. and Shapley, L., College admissions and stability of marriage. Amer. Math. Monthly 69(1962), no. 1, 9–15. Google Scholar

[3] [3] Hoffman, C., Holroyd, A. E., and Peres, Y., A stable marriage of Poisson and Lebesgue. Ann. Probab. 34(2006), no. 4, 1241–1272. Google Scholar

[4] [4] Holroyd, A. E., Pemantle, R., Peres, Y., and Schramm, O., Poisson matching. To appear in Ann. Inst. H. Poincaré Sect. B. Google Scholar

[5] [5] Holroyd, A. E. and Peres, Y., Extra heads and invariant allocations. Ann. Probab. 33(2005), no. 1, 31–52. Google Scholar

[6] [6] Kallenberg, O., Foundations of modern probability. Second edition. Probability and its Applications. Springer-Verlag, New York, 2002. Google Scholar

[7] [7] Liggett, T. M., Tagged particle distributions or how to choose a head at random. In: In and Out of Equilibrium. Progr. Probab. 51, Birkhäuser Boston, Boston, MA, 2002, pp. 133–162. Google Scholar

Cité par Sources :