Stochastic geometry

A possible stochastic geometry model (Boolean model) for wireless network coverage and connectivity constructed from randomly sized disks placed at random locations

In mathematics, stochastic geometry is the study of random spatial patterns. At the heart of the subject lies the study of random point patterns. This leads to the theory of spatial point processes, hence notions of Palm conditioning, which extend to the more abstract setting of random measures.

Models

There are various models for point processes, typically based on but going beyond the classic homogeneous Poisson point process (the basic model for complete spatial randomness) to find expressive models which allow effective statistical methods.

The point pattern theory provides a major building block for generation of random object processes, allowing construction of elaborate random spatial patterns. The simplest version, the Boolean model, places a random compact object at each point of a Poisson point process. More complex versions allow interactions based in various ways on the geometry of objects. Different directions of application include: the production of models for random images either as set-union of objects, or as patterns of overlapping objects; also the generation of geometrically inspired models for the underlying point process (for example, the point pattern distribution may be biased by an exponential factor involving the area of the union of the objects; this is related to the Widom–Rowlinson model^[1] of statistical mechanics).

Random object

What is meant by a random object? A complete answer to this question requires the theory of random closed sets, which makes contact with advanced concepts from measure theory. The key idea is to focus on the probabilities of the given random closed set hitting specified test sets. There arise questions of inference (for example, estimate the set which encloses a given point pattern) and theories of generalizations of means etc. to apply to random sets. Connections are now being made between this latter work and recent developments in geometric mathematical analysis concerning general metric spaces and their geometry. Good parametrizations of specific random sets can allow us to refer random object processes to the theory of marked point processes; object-point pairs are viewed as points in a larger product space formed as the product of the original space and the space of parametrization.

Line and hyper-flat processes

Suppose we are concerned no longer with compact objects, but with objects which are spatially extended: lines on the plane or flats in 3-space. This leads to consideration of line processes, and of processes of flats or hyper-flats. There can no longer be a preferred spatial location for each object; however the theory may be mapped back into point process theory by representing each object by a point in a suitable representation space. For example, in the case of directed lines in the plane one may take the representation space to be a cylinder. A complication is that the Euclidean motion symmetries will then be expressed on the representation space in a somewhat unusual way. Moreover, calculations need to take account of interesting spatial biases (for example, line segments are less likely to be hit by random lines to which they are nearly parallel) and this provides an interesting and significant connection to the hugely significant area of stereology, which in some respects can be viewed as yet another theme of stochastic geometry. It is often the case that calculations are best carried out in terms of bundles of lines hitting various test-sets, rather than by working in representation space.

Line and hyper-flat processes have their own direct applications, but also find application as one way of creating tessellations dividing space; hence for example one may speak of Poisson line tessellations. A notable recent result^[2] proves that the cell at the origin of the Poisson line tessellation is approximately circular when conditioned to be large. Tessellations in stochastic geometry can of course be produced by other means, for example by using Voronoi and variant constructions, and also by iterating various means of construction.

Origin of the name

The name appears to have been coined by David Kendall and Klaus Krickeberg^[3] while preparing for a June 1969 Oberwolfach workshop, though antecedents for the theory stretch back much further under the name geometric probability. The term "stochastic geometry" was also used by Frisch and Hammersley in 1963^[4] as one of two suggestions for names of a theory of "random irregular structures" inspired by percolation theory.

Applications

This brief description has focused on the theory^[3][5] of stochastic geometry, which allows a view of the structure of the subject. However, much of the life and interest of the subject, and indeed many of its original ideas, flow from a very wide range of applications, for example: astronomy,^[6] spatially distributed telecommunications,^[7] wireless network modeling and analysis,^[8] modeling of channel fading,^[9][10] forestry,^[11] the statistical theory of shape,^[12] material science,^[13] multivariate analysis, problems in image analysis^[14] and stereology. There are links to statistical mechanics,^[15] Markov chain Monte Carlo, and implementations of the theory in statistical computing (for example, spatstat^[16] in R). Most recently determinantal and permanental point processes (connected to random matrix theory) are beginning to play a role.^[17]

See also

• Nearest neighbour function
• Spherical contact distribution function
• Factorial moment measure
• Moment measure
• Continuum percolation theory
• Random graphs
• Spatial statistics
• Stochastic geometry models of wireless networks
• Mathematical morphology
• Information geometry
• Stochastic differential geometry

References

1. Chayes, J. T.; Chayes, L.; Kotecký, R. (1995). "The analysis of the Widom-Rowlinson model by stochastic geometric methods". Communications in Mathematical Physics. 172 (3): 551–569. Bibcode:1995CMaPh.172..551C. doi:10.1007/BF02101808.
2. Kovalenko, I. N. (1999). "A simplified proof of a conjecture of D. G. Kendall concerning shapes of random polygons". Journal of Applied Mathematics and Stochastic Analysis. 12 (4): 301–310. doi:10.1155/S1048953399000283.
3. See foreword in Stoyan, D.; Kendall, W. S.; Mecke, J. (1987). Stochastic geometry and its applications. Wiley. ISBN 0-471-90519-4.
4. Frisch, H. L.; Hammersley, J. M. (1963). "Percolation processes and related topics". SIAM Journal on Applied Mathematics. 11 (4): 894–918. doi:10.1137/0111066.
5. Schneider, R.; Weil, W. (2008). Stochastic and Integral Geometry. Probability and Its Applications. Springer. doi:10.1007/978-3-540-78859-1. ISBN 978-3-540-78858-4. MR 2455326.
6. Martinez, V. J.; Saar, E. (2001). Statistics of The Galaxy Distribution. Chapman & Hall. ISBN 1-58488-084-8.
7. Baccelli, F.; Klein, M.; Lebourges, M.; Zuyev, S. (1997). "Stochastic geometry and architecture of communication networks". Telecommunication Systems. 7: 209–227. doi:10.1023/A:1019172312328.
8. M. Haenggi. Stochastic geometry for wireless networks. Cambridge University Press, 2012.
9. Piterbarg, V. I.; Wong, K. T. (2005). "Spatial-Correlation-Coefficient at the Basestation, in Closed-Form Explicit Analytic Expression, Due to Heterogeneously Poisson Distributed Scatterers". IEEE Antennas and Wireless Propagation Letters. 4 (1): 385–388. Bibcode:2005IAWPL...4..385P. doi:10.1109/LAWP.2005.857968.
10. Abdulla, M.; Shayan, Y. R. (2014). "Large-Scale Fading Behavior for a Cellular Network with Uniform Spatial Distribution". Wireless Communications and Mobile Computing. 4 (7): 1–17. arXiv:1302.0891. doi:10.1002/WCM.2565.
11. Stoyan, D.; Penttinen, A. (2000). "Recent Applications of Point Process Methods in Forestry Statistics". Statistical Science. 15: 61–78.
12. Kendall, D. G. (1989). "A survey of the statistical theory of shape". Statistical Science. 4 (2): 87–99. doi:10.1214/ss/1177012582.
13. Torquato, S. (2002). Random heterogeneous materials. Springer-Verlag. ISBN 0-387-95167-9.
14. Van Lieshout, M. N. M. (1995). Stochastic Geometry Models in Image Analysis and Spatial Statistics. CWI Tract, 108. CWI. ISBN 90-6196-453-9.
15. Georgii, H.-O.; Häggström, O.; Maes, C. (2001). "The random geometry of equilibrium phases". Phase Transitions and Critical Phenomena. Vol. 18. Academic Press. pp. 1–142.
16. Baddeley, A.; Turner, R. (2005). "Spatstat: An R package for analyzing spatial point patterns". Journal of Statistical Software. 12 (6): 1–42. doi:10.18637/jss.v012.i06.
17. McCullagh, P.; Møller, J. (2006). "The permanental process". Advances in Applied Probability. 38 (4): 873–888. doi:10.1239/aap/1165414583.