Extremes on trees. (English) Zbl 1096.60009

Summary: This paper considers the asymptotic distribution of the longest edge of the minimal spanning tree and nearest neighbor graph on \({\mathbf X}_1,\dots,{\mathbf X}_{N_n}\) where \({\mathbf X}_1,{\mathbf X}_2,\dots\) are i.i.d. in \(\operatorname{Re}^2\) with distribution \(F\) and \(N_n\) is independent of the \({\mathbf X}_i\) and satisfies \(N_n/n\to_p 1\). A new approach based on spatial blocking and a locally orthogonal coordinate system is developed to treat cases for which \(F\) has unbounded support. The general results are applied to a number of special cases, including elliptically contoured distributions, distributions with independent Weibull-like margins and distributions with parallel level curves.


60D05 Geometric probability and stochastic geometry
60F05 Central limit and other weak theorems
60G70 Extreme value theory; extremal stochastic processes
05C05 Trees
05C80 Random graphs (graph-theoretic aspects)
Full Text: DOI arXiv


[1] Bingham, N. H., Goldie, C. M. and Teugels, J. L. (1987). Regular Variation. Cambridge Univ. Press. · Zbl 0617.26001
[2] Erdelyi, A. (1956). Asymptotic Expansions . Dover, New York. · Zbl 0070.29002
[3] Ibragimov, I. A. and Linnik, Yu. V. (1971). Independent and Stationary Sequences of Random Variables . Wolters-Noordhoff, Groningen. · Zbl 0219.60027
[4] Kallenberg, O. (1983). Random Measures. Academic Press, New York. · Zbl 0544.60053
[5] Kesten, H. and Lee, S. (1996). The central limit theorem for weighted minimal spanning trees on random points. Ann. Appl. Probab. 6 495–527. · Zbl 0862.60008
[6] Leadbetter, M. R., Lindgren, G. and Rootzén, H. (1983). Extremes and Related Properties of Random Sequences and Processes . Springer, New York. · Zbl 0518.60021
[7] Lee, S. (1997). The central limit theorem for Euclidean minimal spanning trees. I. Ann. Appl. Probab. 7 996–1020. · Zbl 0892.60034
[8] Penrose, M. D. (1997). The longest edge of the minimal spanning tree. Ann. Appl. Probab. 7 340–361. · Zbl 0884.60042
[9] Penrose, M. D. (1998). Extremes for the minimal spanning tree on normally distributed points. Adv. in Appl. Probab. 30 628–639. · Zbl 0919.60025
[10] Penrose, M. (2000). Central limit theorems for \(k\)-nearest neighbour distances. Stochastic Process. Appl. 85 295–320. · Zbl 0997.60014
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.