Insertion and deletion tolerance of point processes

Alexander E. Holroyd (Microsoft Research)
Terry Soo (University of Warwick)


We develop a theory of insertion and deletion tolerance for point processes. A process is insertion-tolerant if adding a suitably chosen random point results in a point process that is absolutely continuous in law with respect to the original process. This condition and the related notion of deletion-tolerance are extensions of the so-called finite energy condition for discrete random processes. We prove several equivalent formulations of each condition, including versions involving Palm processes. Certain other seemingly natural variants of the conditions turn out not to be equivalent. We illustrate the concepts in the context of a number of examples, including Gaussian zero processes and randomly perturbed lattices, and we provide applications to continuum percolation and stable matching.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-24

Publication Date: August 11, 2013

DOI: 10.1214/EJP.v18-2621


  • Burton, R. M.; Keane, M. Density and uniqueness in percolation. Comm. Math. Phys. 121 (1989), no. 3, 501--505. MR0990777
  • Daley, D. J.; Vere-Jones, D. An introduction to the theory of point processes. Vol. II. General theory and structure. Second edition. Probability and its Applications (New York). Springer, New York, 2008. xviii+573 pp. ISBN: 978-0-387-21337-8 MR2371524
  • Daley, Daryl J.; Last, Günter. Descending chains, the lilypond model, and mutual-nearest-neighbour matching. Adv. in Appl. Probab. 37 (2005), no. 3, 604--628. MR2156551
  • Durrett, R. Probability: Theory and Examples, second ed., Duxbury Press, Belmont, CA, 1996. MR1609153 (98m:60001)
  • Gale, D.; Shapley, L. S. College Admissions and the Stability of Marriage. Amer. Math. Monthly 69 (1962), no. 1, 9--15. MR1531503
  • Gamelin, Theodore W. Complex analysis. Undergraduate Texts in Mathematics. Springer-Verlag, New York, 2001. xviii+478 pp. ISBN: 0-387-95093-1; 0-387-95069-9 MR1830078
  • Häggström, Olle; Meester, Ronald. Nearest neighbor and hard sphere models in continuum percolation. Random Structures Algorithms 9 (1996), no. 3, 295--315. MR1606845
  • Hoffman, Christopher; Holroyd, Alexander E.; Peres, Yuval. A stable marriage of Poisson and Lebesgue. Ann. Probab. 34 (2006), no. 4, 1241--1272. MR2257646
  • Holroyd, Alexander E.; Pemantle, Robin; Peres, Yuval; Schramm, Oded. Poisson matching. Ann. Inst. Henri Poincaré Probab. Stat. 45 (2009), no. 1, 266--287. MR2500239
  • Holroyd, Alexander E.; Peres, Yuval. Extra heads and invariant allocations. Ann. Probab. 33 (2005), no. 1, 31--52. MR2118858
  • Hough, J.B.; Krishnapur, M.; Peres, Y.; Virág, B. Zeros of Gaussian analytic functions and determinantal point processes, University Lecture Series, vol. 51, American Mathematical Society, Providence, RI, 2009. MR2552864
  • Kallenberg, Olav. Random measures. Third edition. Akademie-Verlag, Berlin; Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London, 1983. 187 pp. ISBN: 0-12-394960-2 MR0818219
  • Kallenberg, Olav. An informal guide to the theory of conditioning in point processes. Internat. Statist. Rev. 52 (1984), no. 2, 151--164. MR0967208
  • Kallenberg, Olav. Foundations of Modern Probability, second ed., Probability and its Applications (New York), Springer-Verlag, New York, 2002. MR1876169 (2002m:60002)
  • Kallenberg, Olav. Invariant measures and disintegrations with applications to Palm and related kernels. Probab. Theory Related Fields 139 (2007), no. 1-2, 285--310. MR2322698
  • Knuth, Donald E. Stable marriage and its relation to other combinatorial problems. An introduction to the mathematical analysis of algorithms. Translated from the French by Martin Goldstein and revised by the author. CRM Proceedings & Lecture Notes, 10. American Mathematical Society, Providence, RI, 1997. xiv+74 pp. ISBN: 0-8218-0603-3 MR1415126
  • Kozlov, O. K. A Gibbsian description of point random fields. (Russian) Teor. Verojatnost. i Primenen. 21 (1976), no. 2, 348--365. MR0415808
  • Last, G. Modern random measures: Palm theory and related models, New perspectives in stochastic geometry, Clarendon Press, Oxford, 2008. MR2568654
  • Last, G. Stationary random measures on homogeneous spaces. J. Theoret. Probab. 23 (2010), no. 2, 478--497. MR2644871
  • Mattila, Pertti. Geometry of sets and measures in Euclidean spaces. Fractals and rectifiability. Cambridge Studies in Advanced Mathematics, 44. Cambridge University Press, Cambridge, 1995. xii+343 pp. ISBN: 0-521-46576-1; 0-521-65595-1 MR1333890
  • Meester, Ronald; Roy, Rahul. Continuum percolation. Cambridge Tracts in Mathematics, 119. Cambridge University Press, Cambridge, 1996. x+238 pp. ISBN: 0-521-47504-X MR1409145
  • Papangelou, F. The conditional intensity of general point processes and an application to line processes. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 28 (1973/74), 207--226. MR0373000
  • Peres, Yuval; Virág, Bálint. Zeros of the i.i.d. Gaussian power series: a conformally invariant determinantal process. Acta Math. 194 (2005), no. 1, 1--35. MR2231337
  • Sodin, Mikhail; Tsirelson, Boris. Random complex zeroes. I. Asymptotic normality. Israel J. Math. 144 (2004), 125--149. MR2121537
  • Thorisson, Hermann. Transforming random elements and shifting random fields. Ann. Probab. 24 (1996), no. 4, 2057--2064. MR1415240

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.