Clustering and percolation of point processes

Bartlomiej Blaszczyszyn (INRIA / ENS Paris)
Dhandapani Yogeshwaran (Technion - Israel Institute of Technology)


We are interested in phase transitions in certain percolation models on point processes and their dependence on clustering properties of the point processes. We show that point processes with smaller void probabilities and factorial moment measures than the stationary Poisson point process exhibit non-trivial phase transition in the percolation of some coverage models based on level-sets of additive functionals of the point process. Examples of such point processes are determinantal point processes, some perturbed lattices and more generally, negatively associated point processes. Examples of such coverage models are k-coverage in the Boolean model (coverage by at least k grains), and SINR-coverage (coverage if the signal to-interference-and-noise ratio is large). In particular, we answer in affirmative the hypothesis of existence of phase transition in the percolation of k-faces in the Cech simplicial complex (called also clique percolation) on point processes which cluster less than the Poisson process.

We also construct a Cox point process, which is "more clustered” than the Poisson point process and whose Boolean model percolates for arbitrarily small radius. This shows that clustering (at least, as detected by our specific tools) does not always “worsen” percolation, as well as that upper-bounding this cluster-ing by a Poisson process is a consequential assumption for the phase transition to hold.

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

Pages: 1-20

Publication Date: July 31, 2013

DOI: 10.1214/EJP.v18-2468


  • Baccelli, François; Błaszczyszyn, Bartłomiej. On a coverage process ranging from the Boolean model to the Poisson-Voronoi tessellation with applications to wireless communications. Adv. in Appl. Probab. 33 (2001), no. 2, 293--323. MR1842294
  • Balister, P. N.; Bollobás, B. Counting regions with bounded surface area. Comm. Math. Phys. 273 (2007), no. 2, 305--315. MR2318308
  • Hough, J. Ben; Krishnapur, Manjunath; Peres, Yuval; Virág, Bálint. Zeros of Gaussian analytic functions and determinantal point processes. University Lecture Series, 51. American Mathematical Society, Providence, RI, 2009. x+154 pp. ISBN: 978-0-8218-4373-4 MR2552864
  • Benjamini, I ; Stauffer, A. Perturbing the hexagonal circle packing: a percolation perspective, arXiv:1104.0762, 2011.
  • Błaszczyszyn, Bartłomiej; Yogeshwaran, D. Directionally convex ordering of random measures, shot noise fields, and some applications to wireless communications. Adv. in Appl. Probab. 41 (2009), no. 3, 623--646. MR2571310
  • Błaszczyszyn, Bartłomiej; Yogeshwaran, D. Clustering comparison of point processes with applications to random geometric models, Stochastic Geometry, Spatial Statistics and Random Fields: Analysis, Modeling and Simulation of Complex Structures (V. Schmidt, ed.), to appear in Lecture Notes in Mathematics, Springer.
  • Błaszczyszyn, Bartłomiej; Yogeshwaran, D., Connectivity in sub-Poisson networks, Proc. of 48,th Annual Allerton Conference (University of Illinois at Urbana-Champaign, IL, USA), 2010, see also
  • Błaszczyszyn, Bartłomiej; Yogeshwaran, D., On comparison of clustering properties of point processes, Adv. Appl. Probab. 46 (2014), no. 1, to appear, see also
  • Bollobás, Béla; Riordan, Oliver. Clique percolation. Random Structures Algorithms 35 (2009), no. 3, 294--322. MR2548516
  • Burton, Robert; Waymire, Ed. Scaling limits for associated random measures. Ann. Probab. 13 (1985), no. 4, 1267--1278. MR0806223
  • Daley, D. J.; Vere-Jones, D. An introduction to the theory of point processes. Vol. I. Elementary theory and methods. Second edition. Probability and its Applications (New York). Springer-Verlag, New York, 2003. xxii+469 pp. ISBN: 0-387-95541-0 MR1950431
  • Daley, D. J.; Vere-Jones, D., An introduction to the theory of point processes: Vol. ii, Springer, New York, 2007.
  • Dousse, Olivier; Baccelli, François; Thiran, Patrick. Impact of interferences on connectivity in ad-hoc networks, IEEE/ACM Trans. Networking 13 (2005), 425--543.
  • Dousse, Olivier; Franceschetti, Massimo; Macris, Nicolas; Meester, Ronald; Thiran, Patrick. Percolation in the signal to interference ratio graph. J. Appl. Probab. 43 (2006), no. 2, 552--562. MR2248583
  • Franceschetti, Massimo; Booth, Lorna; Cook, Matthew; Meester, Ronald; Bruck, Jehoshua. Continuum percolation with unreliable and spread-out connections. J. Stat. Phys. 118 (2005), no. 3-4, 721--734. MR2123652
  • Franceschetti, Massimo; Penrose, Mathew D.; Rosoman, Tom. Strict inequalities of critical values in continuum percolation. J. Stat. Phys. 142 (2011), no. 3, 460--486. MR2771041
  • Georgii, Hans-Otto; Yoo, Hyun Jae. Conditional intensity and Gibbsianness of determinantal point processes. J. Stat. Phys. 118 (2005), no. 1-2, 55--84. MR2122549
  • Ghosh, S; Krishnapur, M.; Peres, Y. Continuum percolation for gaussian zeroes and ginibre eigenvalues, arXiv:1211.2514, 2012.
  • Gilbert, E. N. Random plane networks. J. Soc. Indust. Appl. Math. 9 1961 533--543. MR0132566
  • Grimmett, Geoffrey. Percolation. Second edition. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 321. Springer-Verlag, Berlin, 1999. xiv+444 pp. ISBN: 3-540-64902-6 MR1707339
  • Jonasson, Johan. Optimization of shape in continuum percolation. Ann. Probab. 29 (2001), no. 2, 624--635. MR1849172
  • Kahle, Matthew. Random geometric complexes. Discrete Comput. Geom. 45 (2011), no. 3, 553--573. MR2770552
  • 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
  • Kesten, H.; Sidoravicius, V.; Zhang, Y. Percolation of arbitrary words on the close-packed graph of $\Bbb Z^ 2$. Electron. J. Probab. 6 (2001), no. 4, 27 pp. (electronic). MR1825711
  • Lebowitz, J. L.; Mazel, A. E. Improved Peierls argument for high-dimensional Ising models. J. Statist. Phys. 90 (1998), no. 3-4, 1051--1059. MR1616958
  • Liggett, T. M.; Schonmann, R. H.; Stacey, A. M. Domination by product measures. Ann. Probab. 25 (1997), no. 1, 71--95. MR1428500
  • 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
  • Müller, Alfred; Stoyan, Dietrich. Comparison methods for stochastic models and risks. Wiley Series in Probability and Statistics. John Wiley & Sons, Ltd., Chichester, 2002. xii+330 pp. ISBN: 0-471-49446-1 MR1889865
  • Penrose, Mathew. Random geometric graphs. Oxford Studies in Probability, 5. Oxford University Press, Oxford, 2003. xiv+330 pp. ISBN: 0-19-850626-0 MR1986198
  • Roy, Rahul; Tanemura, Hideki. Critical intensities of Boolean models with different underlying convex shapes. Adv. in Appl. Probab. 34 (2002), no. 1, 48--57. MR1895330
  • D. Yogeshwaran, Stochastic geometric networks: connectivity and comparison, Ph.D. thesis, Université Pierre et Marie Curie, Paris, France., 2010, Available at

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