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.
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] On optimal matchings. Combinatorica 4 (1984) 259-264. | MR | Zbl
, and .[2] Percolation and minimal spanning forests in infinite graphs. Ann. Probab. 23 (1995) 87-104. | MR | Zbl
.[3] Probabilistic analysis of a greedy heuristic for euclidean matching. Probab. Engrg. Inform. Sci. 2 (1988) 143-156. | Zbl
, and .[4] Group-invariant percolation on graphs. Geom. Funct. Anal. 9 (1999) 29-66. | MR | Zbl
, , and .[5] Gravitational allocation to Poisson points. Ann. Math. To appear. Available at arXiv:math.PR/0611886.
, , and .[6] Poisson trees, succession lines and coalescing random walks. Ann. Inst. H. Poincaré Probab. Statist. 40 (2004) 141-152. | Numdam | MR | Zbl
, and .[7] Greedy matching on the line. SIAM J. Comput. 19 (1990) 666-672. | MR | Zbl
, and .[8] College admissions and stability of marriage. Amer. Math. Monthly 69 (1962) 9-15. | MR | Zbl
and .[9] Nearest neighbor and hard sphere models in continuum percolation. Random Structures Algorithms 9 (1996) 295-315. | MR | Zbl
and .[10] Tail bounds for the stable marriage of Poisson and Lebesgue. Canad. J. Math. To appear. Available at arXiv:math.PR/0507324. | MR
, and .[11] A stable marriage of Poisson and Lebesgue. Ann. Probab. 34 (2006) 1241-1272. | MR | Zbl
, and .[12] How to find an extra head: optimal random shifts of Bernoulli and Poisson random fields. Ann. Probab. 29 (2001) 1405-1425. | MR | Zbl
and .[13] Trees and matchings from point processes. Electron. Comm. Probab. 8 (2003) 17-27 (electronic). | MR | Zbl
and .[14] Extra heads and invariant allocations. Ann. Probab. 33 (2005) 31-52. | MR | Zbl
and .[15] Foundations of Modern Probability, 2nd edition. Springer, New York, 2002. | MR | Zbl
.[16] Stable Marriage and Its Relation to Other Combinatorial Problems. Amer. Math. Soc., Providence, RI, 1997. | MR | Zbl
.[17] 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] Translation-invariant matchings of coin-flips on Zd. Preprint. Available at arXiv:math/0610334.
.[19] The transportation cost from the uniform measure to the empirical measure in dimension ≥3. Ann. Probab. 22 (1994) 919-959. | MR | Zbl
.[20] Invariant matchings of exponential tail on coin flips in Zd. Preprint.
.Cité par Sources :