Poisson matching
Holroyd, Alexander E. ; Pemantle, Robin ; Peres, Yuval ; Schramm, Oded
Annales de l'I.H.P. Probabilités et statistiques, Tome 45 (2009), p. 266-287 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

Supposons que des points rouges et bleus évoluent suivant des processus de Poisson homogènes indépendants dans ℝd. Nous nous intéressons à des procédés invariants par translation appariant de manière bijective les points rouges et les points bleus. En dimensions d=1, 2, quelque soit le procédé considéré, la distance d'appariement (matching distance) X entre un point typique et son partenaire possède nécessairement un d/2-ème moment infini. En revanche, en dimensions d≥3 il existe des procédés pour lesquels X a des moments exponentiels finis. Le «mariage stable» de Gale-Shapley est un procédé naturel, obtenu en appariant une à une les paires mutuellement les plus proches. L'un des principaux résultats de cet article est que dans le cas de ce procédé, la distance d'appariement X est majorée par une loi de puissance. Une minoration en loi de puissance est également vérifiée. En particulier, le mariage stable est essentiellement optimal (en terme de queue de distribution) en dimension d=1, mais il est loin d'être optimal en dimensions d≥3. Dans le cas du problème qui consiste à apparier des points d'une seule couleur issus d'un processus de Poisson, en dimension d=1 il existe des procédés pour lesquels X a des moments exponentiels finis. Par contre, si l'on demande en plus que l'appariement soit une fonction déterministe du processus ponctuel, alors X a nécessairement une moyenne infinie.

Suppose that red and blue points occur as independent homogeneous Poisson processes in ℝd. We investigate translation-invariant schemes for perfectly matching the red points to the blue points. For any such scheme in dimensions d=1, 2, the matching distance X from a typical point to its partner must have infinite d/2th moment, while in dimensions d≥3 there exist schemes where X has finite exponential moments. The Gale-Shapley stable marriage is one natural matching scheme, obtained by iteratively matching mutually closest pairs. A principal result of this paper is a power law upper bound on the matching distance X for this scheme. A power law lower bound holds also. In particular, stable marriage is close to optimal (in tail behavior) in d=1, but far from optimal in d≥3. For the problem of matching Poisson points of a single color to each other, in d=1 there exist schemes where X has finite exponential moments, but if we insist that the matching is a deterministic factor of the point process then X must have infinite mean.

Publié le : 2009-01-01
DOI : https://doi.org/10.1214/08-AIHP170
Classification:  60D05,  60G55,  05C70 
@article{AIHPB_2009__45_1_266_0,
     author = {Holroyd, Alexander E. and Pemantle, Robin and Peres, Yuval and Schramm, Oded},
     title = {Poisson matching},
     journal = {Annales de l'I.H.P. Probabilit\'es et statistiques},
     volume = {45},
     year = {2009},
     pages = {266-287},
     doi = {10.1214/08-AIHP170},
     mrnumber = {2500239},
     zbl = {1175.60012},
     language = {en},
     url = {http://dml.mathdoc.fr/item/AIHPB_2009__45_1_266_0}
}

Holroyd, Alexander E.; Pemantle, Robin; Peres, Yuval; Schramm, Oded. Poisson matching. Annales de l'I.H.P. Probabilités et statistiques, Tome 45 (2009) pp. 266-287. doi : 10.1214/08-AIHP170. http://gdmltest.u-ga.fr/item/AIHPB_2009__45_1_266_0/

[1] M. Ajtai, J. Komlós and G. Tusnády. On optimal matchings. Combinatorica 4 (1984) 259-264. | MR 779885 | Zbl 0562.60012

[2] K. S. Alexander. Percolation and minimal spanning forests in infinite graphs. Ann. Probab. 23 (1995) 87-104. | MR 1330762 | Zbl 0827.60079

[3] D. Avis, B. Davis and J. M. Steele. Probabilistic analysis of a greedy heuristic for euclidean matching. Probab. Engrg. Inform. Sci. 2 (1988) 143-156. | Zbl 1134.90468

[4] I. Benjamini, R. Lyons, Y. Peres and O. Schramm. Group-invariant percolation on graphs. Geom. Funct. Anal. 9 (1999) 29-66. | MR 1675890 | Zbl 0924.43002

[5] S. Chatterjee, R. Peled, Y. Peres and D. Romik. Gravitational allocation to Poisson points. Ann. Math. To appear. Available at arXiv:math.PR/0611886.

[6] P. A. Ferrari, C. Landim and H. Thorisson. Poisson trees, succession lines and coalescing random walks. Ann. Inst. H. Poincaré Probab. Statist. 40 (2004) 141-152. | Numdam | MR 2044812 | Zbl 1042.60064

[7] A. Frieze, C. Mcdiarmid and B. Reed. Greedy matching on the line. SIAM J. Comput. 19 (1990) 666-672. | MR 1053934 | Zbl 0697.68035

[8] D. Gale and L. Shapley. College admissions and stability of marriage. Amer. Math. Monthly 69 (1962) 9-15. | MR 1531503 | Zbl 0109.24403

[9] O. Häggström and R. Meester. Nearest neighbor and hard sphere models in continuum percolation. Random Structures Algorithms 9 (1996) 295-315. | MR 1606845 | Zbl 0866.60088

[10] C. Hoffman, A. E. Holroyd and Y. Peres. Tail bounds for the stable marriage of Poisson and Lebesgue. Canad. J. Math. To appear. Available at arXiv:math.PR/0507324. | MR 2588423 | Zbl pre05644856

[11] C. Hoffman, A. E. Holroyd and Y. Peres. A stable marriage of Poisson and Lebesgue. Ann. Probab. 34 (2006) 1241-1272. | MR 2257646 | Zbl 1111.60008

[12] A. E. Holroyd and T. M. Liggett. How to find an extra head: optimal random shifts of Bernoulli and Poisson random fields. Ann. Probab. 29 (2001) 1405-1425. | MR 1880225 | Zbl 1019.60048

[13] A. E. Holroyd and Y. Peres. Trees and matchings from point processes. Electron. Comm. Probab. 8 (2003) 17-27 (electronic). | MR 1961286 | Zbl 1060.60048

[14] A. E. Holroyd and Y. Peres. Extra heads and invariant allocations. Ann. Probab. 33 (2005) 31-52. | MR 2118858 | Zbl 1097.60032

[15] O. Kallenberg. Foundations of Modern Probability, 2nd edition. Springer, New York, 2002. | MR 1876169 | Zbl 0996.60001

[16] D. E. Knuth. Stable Marriage and Its Relation to Other Combinatorial Problems. Amer. Math. Soc., Providence, RI, 1997. | MR 1415126 | Zbl 0860.68054

[17] T. M. Liggett. Tagged particle distributions or how to choose a head at random. In In and out of equilibrium (Mambucaba, 2000) 133-162. Progr. Probab. 51. Birkhäuser Boston, Boston, MA, 2002. | MR 1901951 | Zbl 1108.60319

[18] T. Soo. Translation-invariant matchings of coin-flips on Zd. Preprint. Available at arXiv:math/0610334.

[19] M. Talagrand. The transportation cost from the uniform measure to the empirical measure in dimension ≥3. Ann. Probab. 22 (1994) 919-959. | MR 1288137 | Zbl 0809.60015

[20] A. Timar. Invariant matchings of exponential tail on coin flips in Zd. Preprint.