Poisson matching
Annales de l'I.H.P. Probabilités et statistiques, Tome 45 (2009) no. 1, pp. 266-287.

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.

DOI : 10.1214/08-AIHP170
Classification : 60D05, 60G55, 05C70
Mots-clés : Poisson process, point process, matching, stable marriage 
@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},
     pages = {266--287},
     publisher = {Gauthier-Villars},
     volume = {45},
     number = {1},
     year = {2009},
     doi = {10.1214/08-AIHP170},
     mrnumber = {2500239},
     zbl = {1175.60012},
     language = {en},
     url = {http://www.numdam.org/articles/10.1214/08-AIHP170/}
}
TY  - JOUR
AU  - Holroyd, Alexander E.
AU  - Pemantle, Robin
AU  - Peres, Yuval
AU  - Schramm, Oded
TI  - Poisson matching
JO  - Annales de l'I.H.P. Probabilités et statistiques
PY  - 2009
SP  - 266
EP  - 287
VL  - 45
IS  - 1
PB  - Gauthier-Villars
UR  - http://www.numdam.org/articles/10.1214/08-AIHP170/
DO  - 10.1214/08-AIHP170
LA  - en
ID  - AIHPB_2009__45_1_266_0
ER  - 
%0 Journal Article
%A Holroyd, Alexander E.
%A Pemantle, Robin
%A Peres, Yuval
%A Schramm, Oded
%T Poisson matching
%J Annales de l'I.H.P. Probabilités et statistiques
%D 2009
%P 266-287
%V 45
%N 1
%I Gauthier-Villars
%U http://www.numdam.org/articles/10.1214/08-AIHP170/
%R 10.1214/08-AIHP170
%G en
%F 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) no. 1, pp. 266-287. doi : 10.1214/08-AIHP170. http://www.numdam.org/articles/10.1214/08-AIHP170/

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

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

[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

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

[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 | Zbl

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

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

[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 | Zbl

[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

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

[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 | Zbl

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

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

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

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

[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 | Zbl

[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 | Zbl

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

Cité par Sources :