Poisson matching

Alexander E. Holroyd; Robin Pemantle; Yuval Peres; Oded Schramm

Annales de l'I.H.P. Probabilités et statistiques (2009)

  • Volume: 45, Issue: 1, page 266-287
  • ISSN: 0246-0203

Abstract

top
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.

How to cite

top

Holroyd, Alexander E., et al. "Poisson matching." Annales de l'I.H.P. Probabilités et statistiques 45.1 (2009): 266-287. <http://eudml.org/doc/78020>.

@article{Holroyd2009,
abstract = {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.},
author = {Holroyd, Alexander E., Pemantle, Robin, Peres, Yuval, Schramm, Oded},
journal = {Annales de l'I.H.P. Probabilités et statistiques},
keywords = {Poisson process; point process; matching; stable marriage; Gale-Shapley stable marriage; matching distance},
language = {eng},
number = {1},
pages = {266-287},
publisher = {Gauthier-Villars},
title = {Poisson matching},
url = {http://eudml.org/doc/78020},
volume = {45},
year = {2009},
}

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
PB - Gauthier-Villars
VL - 45
IS - 1
SP - 266
EP - 287
AB - 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.
LA - eng
KW - Poisson process; point process; matching; stable marriage; Gale-Shapley stable marriage; matching distance
UR - http://eudml.org/doc/78020
ER -

References

top
  1. [1] M. Ajtai, J. Komlós and G. Tusnády. On optimal matchings. Combinatorica 4 (1984) 259–264. Zbl0562.60012MR779885
  2. [2] K. S. Alexander. Percolation and minimal spanning forests in infinite graphs. Ann. Probab. 23 (1995) 87–104. Zbl0827.60079MR1330762
  3. [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. Zbl1134.90468
  4. [4] I. Benjamini, R. Lyons, Y. Peres and O. Schramm. Group-invariant percolation on graphs. Geom. Funct. Anal. 9 (1999) 29–66. Zbl0924.43002MR1675890
  5. [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. Zbl1206.60013
  6. [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. Zbl1042.60064MR2044812
  7. [7] A. Frieze, C. McDiarmid and B. Reed. Greedy matching on the line. SIAM J. Comput. 19 (1990) 666–672. Zbl0697.68035MR1053934
  8. [8] D. Gale and L. Shapley. College admissions and stability of marriage. Amer. Math. Monthly 69 (1962) 9–15. Zbl0109.24403MR1531503
  9. [9] O. Häggström and R. Meester. Nearest neighbor and hard sphere models in continuum percolation. Random Structures Algorithms 9 (1996) 295–315. Zbl0866.60088MR1606845
  10. [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. Zbl1191.60015MR2588423
  11. [11] C. Hoffman, A. E. Holroyd and Y. Peres. A stable marriage of Poisson and Lebesgue. Ann. Probab. 34 (2006) 1241–1272. Zbl1111.60008MR2257646
  12. [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. Zbl1019.60048MR1880225
  13. [13] A. E. Holroyd and Y. Peres. Trees and matchings from point processes. Electron. Comm. Probab. 8 (2003) 17–27 (electronic). Zbl1060.60048MR1961286
  14. [14] A. E. Holroyd and Y. Peres. Extra heads and invariant allocations. Ann. Probab. 33 (2005) 31–52. Zbl1097.60032MR2118858
  15. [15] O. Kallenberg. Foundations of Modern Probability, 2nd edition. Springer, New York, 2002. Zbl0996.60001MR1876169
  16. [16] D. E. Knuth. Stable Marriage and Its Relation to Other Combinatorial Problems. Amer. Math. Soc., Providence, RI, 1997. Zbl0860.68054MR1415126
  17. [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. Zbl1108.60319MR1901951
  18. [18] T. Soo. Translation-invariant matchings of coin-flips on Zd. Preprint. Available at arXiv:math/0610334. Zbl1205.60098
  19. [19] M. Talagrand. The transportation cost from the uniform measure to the empirical measure in dimension ≥3. Ann. Probab. 22 (1994) 919–959. Zbl0809.60015MR1288137
  20. [20] A. Timar. Invariant matchings of exponential tail on coin flips in Zd. Preprint. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.