Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-27T19:25:02.141Z Has data issue: false hasContentIssue false
  • English
  • Français

Limit theorems for random spatial drainage networks

Part of: Graph theory Operations research and management science Limit theorems Geometric probability and stochastic geometry

Published online by Cambridge University Press:  01 July 2016

Mathew D. Penrose  and
Andrew R. Wade
Mathew D. Penrose*
Affiliation:
University of Bath
Andrew R. Wade*
Affiliation:
University of Strathclyde
*
∗ Postal address: Department of Mathematical Sciences, University of Bath, Claverton Down, Bath BA2 7AY, UK. Email address: [email protected]
∗∗ Postal address: Department of Mathematics and Statistics, University of Strathclyde, 26 Richmond Street, Glasgow G1 1XH, UK. Email address: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Suppose that, under the action of gravity, liquid drains through the unit d-cube via a minimal-length network of channels constrained to pass through random sites and to flow with nonnegative component in one of the canonical orthogonal basis directions of Rd, d ≥ 2. The resulting network is a version of the so-called minimal directed spanning tree. We give laws of large numbers and convergence in distribution results on the large-sample asymptotic behaviour of the total power-weighted edge length of the network on uniform random points in (0, 1)d. The distributional results exhibit a weight-dependent phase transition between Gaussian and boundary-effect-derived distributions. These boundary contributions are characterized in terms of limits of the so-called on-line nearest-neighbour graph, a natural model of spatial network evolution, for which we also present some new results. Also, we give a convergence in distribution result for the length of the longest edge in the drainage network; when d = 2, the limit is expressed in terms of Dickman-type variables.

Keywords

Random spatial graphspanning treeweak convergencephase transitionnearest-neighbour graphDickman distributiondistributional fixed-point equation

MSC classification

Primary: 60D05: Geometric probability and stochastic geometry
Secondary: 60F05: Central limit and other weak theorems 90B15: Network models, stochastic 60F25: $L^p$-limit theorems 05C80: Random graphs
Type
Stochastic Geometry and Statistical Applications
Information
Advances in Applied Probability , Volume 42 , Issue 3 , September 2010 , pp. 659 - 688
Copyright
Copyright © Applied Probability Trust 2010 

References

Abramowitz, M. and Stegun, I. A. (eds) (1965). Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables (Appl. Math. Ser. 55). US Government Printing Office, Washington, DC.Google Scholar
Aldous, D. J. and Bandyopadhyay, A. (2005). A survey of max-type recursive distributional equations. Ann. Appl. Prob. 15, 1047–1110.CrossRefGoogle Scholar
Avram, F. and Bertsimas, D. (1993). On central limit theorems in geometrical probability. Ann. Appl. Prob. 3, 1033–1046.CrossRefGoogle Scholar
Baccelli, F. and Bordenave, C. (2007). The radial spanning tree of a Poisson point process. Ann. Appl. Prob. 17, 305–359.CrossRefGoogle Scholar
Bai, Z. -D., Lee, S. and Penrose, M. D. (2006). Rooted edges in a minimal directed spanning tree on random points. Adv. Appl. Prob. 38, 1–30.CrossRefGoogle Scholar
Berger, N. et al. (2003). Degree distribution of the FKP network model. In Automata, Languages and Programming (Lecture Notes Comput. Sci. 2719), eds Baeten, J. C. M. et al., Springer, Berlin, pp. 725–738.CrossRefGoogle Scholar
Bhatt, A. G. and Roy, R. (2004). On a random directed spanning tree. Adv. Appl. Prob. 36, 19–42.CrossRefGoogle Scholar
Darling, D. A. (1953). On a class of problems related to the random division of an interval. Ann. Math. Statist. 24, 239–253.CrossRefGoogle Scholar
Durrett, R. (1991). Probability: Theory and Examples. Wadsworth & Brooks/Cole, Pacific Grove, CA.Google Scholar
Gangopadhyay, S., Roy, R. and Sarkar, A. (2004). Random oriented trees: a model of drainage networks. Ann. Appl. Prob. 14, 1242–1266.CrossRefGoogle Scholar
Huang, K. (1987). Statistical Mechanics, 2nd edn. John Wiley, New York.Google Scholar
Kesten, H. and Lee, S. (1996). The central limit theorem for weighted minimal spanning trees on random points. Ann. Appl. Prob. 6, 495–527.CrossRefGoogle Scholar
Kingman, J. F. C. (1993). Poisson Processes (Oxford Stud. Prob. 3). Oxford University Press.Google Scholar
Manna, S. S. and Sen, P. (2002). Modulated scale-free network in Euclidean space. Phys. Rev. E 66, 066114, 4 pp.CrossRefGoogle ScholarPubMed
Manna, S. S., Mukherjee, G. and Sen, P. (2004). Scale-free network on a vertical plane. Phys. Rev. E 69, 017102, 4 pp.CrossRefGoogle ScholarPubMed
Mukherjee, G. and Manna, S. S. (2006). Weighted scale-free networks in Euclidean space using local selection rule. Phys. Rev. E 74, 036111, 5 pp.CrossRefGoogle ScholarPubMed
Neininger, R. and Rüschendorf, L. (2004). A general limit theorem for recursive algorithms and combinatorial structures. Ann. Appl. Prob. 14, 378–418.CrossRefGoogle Scholar
Penrose, M. (2003). Random Geometric Graphs (Oxford Stud. Prob. 5). Oxford University Press.CrossRefGoogle Scholar
Penrose, M. D. (2005). Convergence of random measures in geometric probability. Preprint. Available at http://arxiv.org/abs/math.PR/0508464.Google Scholar
Penrose, M. D. (2005). Multivariate spatial central limit theorems with applications to percolation and spatial graphs. Ann. Prob. 33, 1945–1945.CrossRefGoogle Scholar
Penrose, M. D. (2007). Gaussian limits for random geometric measures. Electron. J. Prob. 12, 989–1035.CrossRefGoogle Scholar
Penrose, M. D. (2007). Laws of large numbers in stochastic geometry with statistical applications. Bernoulli 13, 1124–1150.CrossRefGoogle Scholar
Penrose, M. D. and Wade, A. R. (2004). Random minimal directed spanning trees and Dickman-type distributions. Adv. Appl. Prob. 36, 691–714.CrossRefGoogle Scholar
Penrose, M. D. and Wade, A. R. (2006). On the total length of the random minimal directed spanning tree. Adv. Appl. Prob. 38, 336–372. Extended version available at http://arxiv.org/abs/math.PR/0409201.CrossRefGoogle Scholar
Penrose, M. D. and Wade, A. R. (2008). Limit theory for the random on-line nearest-neighbor graph. Random Structures Algorithms 32, 125–156.CrossRefGoogle Scholar
Penrose, M. D. and Wade, A. R. (2008). Multivariate normal approximation in geometric probability. J. Statist. Theory Pract. 2, 293–326.CrossRefGoogle Scholar
Penrose, M. D. and Wade, A. R. (2009). Random directed and on-line networks. In New Perspectives in Stochastic Geometry, eds Kendall, W. S. and Molchanov, I., Oxford University Press, pp. 248–274.CrossRefGoogle Scholar
Penrose, M. D. and Yukich, J. E. (2001). Central limit theorems for some graphs in computational geometry. Ann. Appl. Prob. 11, 1005–1041.CrossRefGoogle Scholar
Penrose, M. D. and Yukich, J. E. (2003). Weak laws of large numbers in geometric probability. Ann. Appl. Prob. 13, 277–303.CrossRefGoogle Scholar
Rodriguez-Iturbe, I. and Rinaldo, A. (1997). Fractal River Basins: Chance and Self-Organization. Cambridge University Press.Google Scholar
Rösler, U. (1992). A fixed point theorem for distributions. Stoch. Process. Appl. 42, 195–214.CrossRefGoogle Scholar
Steele, J. M. (1986). An Efron–Stein inequality for nonsymmetric statistics. Ann. Statist. 14, 753–758.CrossRefGoogle Scholar
Steele, J. M. (1997). Probability Theory and Combinatorial Optimization. Society for Industrial and Applied Mathematics, Philadelphia, PA.CrossRefGoogle Scholar
Wade, A. R. (2007). Explicit laws of large numbers for random nearest-neighbour-type graphs. Adv. Appl. Prob. 39, 326–342.CrossRefGoogle Scholar
Wade, A. R. (2009). Asymptotic theory for the multidimensional random on-line nearest-neighbour graph. Stoch. Process. Appl. 119, 1889–1911.CrossRefGoogle Scholar
Yukich, J. E. (1998). Probability Theory of Classical Euclidean Optimization Problems (Lecture Notes Math. 1675). Springer, Berlin.CrossRefGoogle Scholar