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

Poisson matching. (English) Zbl 1175.60012

Ann. Inst. Henri Poincaré, Probab. Stat. 45, No. 1, 266-287 (2009).
Authors’ abstract: Suppose that red and blue points occur as independent Poisson processes in \(\mathbb{R}^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/2\)th moment, while in dimension \(d\geq3\) 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\geq3\). 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.
Reviewer: Ilya S. Molchanov (Bern)

Cited in 39 Documents

MSC:

60D05 Geometric probability and stochastic geometry
60G55 Point processes (e.g., Poisson, Cox, Hawkes processes)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Keywords:

Poisson process; point process; matching; Gale-Shapley stable marriage; matching distance
Cite Review PDF
Full Text: DOI arXiv EuDML

References:

[1] M. Ajtai, J. Komlós and G. Tusnády. On optimal matchings. Combinatorica 4 (1984) 259-264. · Zbl 0562.60012 · doi:10.1007/BF02579135
[2] K. S. Alexander. Percolation and minimal spanning forests in infinite graphs. Ann. Probab. 23 (1995) 87-104. · Zbl 0827.60079 · doi:10.1214/aop/1176988378
[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 · doi:10.1017/S0269964800000711
[4] I. Benjamini, R. Lyons, Y. Peres and O. Schramm. Group-invariant percolation on graphs. Geom. Funct. Anal. 9 (1999) 29-66. · Zbl 0924.43002 · doi:10.1007/s000390050080
[5] S. Chatterjee, R. Peled, Y. Peres and D. Romik. Gravitational allocation to Poisson points. Ann. Math. To appear. Available at · Zbl 1206.60013
[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. · Zbl 1042.60064 · doi:10.1016/j.anihpb.2003.12.001
[7] A. Frieze, C. McDiarmid and B. Reed. Greedy matching on the line. SIAM J. Comput. 19 (1990) 666-672. · Zbl 0697.68035 · doi:10.1137/0219045
[8] D. Gale and L. Shapley. College admissions and stability of marriage. Amer. Math. Monthly 69 (1962) 9-15. JSTOR: · Zbl 0109.24403 · doi:10.2307/2312726
[9] O. Häggström and R. Meester. Nearest neighbor and hard sphere models in continuum percolation. Random Structures Algorithms 9 (1996) 295-315. · Zbl 0866.60088 · doi:10.1002/(SICI)1098-2418(199610)9:3<295::AID-RSA3>3.0.CO;2-S
[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 · Zbl 1191.60015 · doi:10.4153/CJM-2009-060-7
[11] C. Hoffman, A. E. Holroyd and Y. Peres. A stable marriage of Poisson and Lebesgue. Ann. Probab. 34 (2006) 1241-1272. · Zbl 1111.60008 · doi:10.1214/009117906000000098
[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. · Zbl 1019.60048
[13] A. E. Holroyd and Y. Peres. Trees and matchings from point processes. Electron. Comm. Probab. 8 (2003) 17-27 (electronic). · Zbl 1060.60048
[14] A. E. Holroyd and Y. Peres. Extra heads and invariant allocations. Ann. Probab. 33 (2005) 31-52. · Zbl 1097.60032 · doi:10.1214/009117904000000603
[15] O. Kallenberg. Foundations of Modern Probability , 2nd edition. Springer, New York, 2002. · Zbl 0996.60001
[16] D. E. Knuth. Stable Marriage and Its Relation to Other Combinatorial Problems . Amer. Math. Soc., Providence, RI, 1997.
[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. · Zbl 1108.60319
[18] T. Soo. Translation-invariant matchings of coin-flips on Z d . Preprint. Available at · Zbl 1205.60098
[19] M. Talagrand. The transportation cost from the uniform measure to the empirical measure in dimension \geq 3. Ann. Probab. 22 (1994) 919-959. · Zbl 0809.60015 · doi:10.1214/aop/1176988735
[20] A. Timar. Invariant matchings of exponential tail on coin flips in Z d .
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.