×

zbMATH — the first resource for mathematics

Rooted edges of a minimal directed spanning tree on random points. (English) Zbl 1094.60004
Authors’ abstract: For \(n\) independent, identically distributed uniform points in \([0,1]^d\), \(d \geq 2\), let \(L_n\) be the total distance from the origin to all the minimal points under the coordinate-wise partial order (this is also the total length of the rooted edges of a minimal directed spanning tree on the given random points). For \(d \geq 3\) we establish the asymptotics of the mean and the variance of \(L_n\), and show that \(L_n\) satisfies a central limit theorem, unlike in the case \(d=2\).

MSC:
60D05 Geometric probability and stochastic geometry
60G70 Extreme value theory; extremal stochastic processes
05C80 Random graphs (graph-theoretic aspects)
60F05 Central limit and other weak theorems
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bai, Z.-D., Chao, C.-C., Hwang, H.-K. and Liang, W.-Q. (1998). On the variance of the number of maxima in random vectors and its applications. Ann. Appl. Prob. 8, 886–895. · Zbl 0941.60021 · doi:10.1214/aoap/1028903455
[2] Bai, Z.-D., Devroye, L., Hwang, H.-K. and Tsai, T.-H. (2005). Maxima in hypercubes. Random Structures Algorithms 27 , 290–309. · Zbl 1080.60007 · doi:10.1002/rsa.20053
[3] Bai, Z.-D. \et(2001). Limit theorems for the number of maxima in random samples from planar regions. Electron. J. Prob. 6, 41pp. · Zbl 0986.60007 · emis:journals/EJP-ECP/EjpVol6/paper3.abs.html · eudml:121837
[4] Barbour, A. D. and Xia, A. (2001). The number of two-dimensional maxima. Adv. Appl. Prob. 33, 727–750. · Zbl 1005.60028 · doi:10.1239/aap/1011994025
[5] Baryshnikov, Y. (2000). Supporting points processes and some of their applications. Prob. Theory Relat. Fields 117, 163–182. · Zbl 0961.60017 · doi:10.1007/s004400000047
[6] Bhatt, A. and Roy, R. (2004). On a random directed spanning tree. Adv. Appl. Prob. 36, 19–42. · Zbl 1055.60002 · doi:10.1239/aap/1077134462
[7] Bräker, H. and Hsing, T. (1998). On the area and perimeter of a random convex hull in a bounded convex set. Prob. Theory Relat. Fields 111, 517–550. · Zbl 0912.60029 · doi:10.1007/s004400050176
[8] Groeneboom, P. (1988). Limit theorems for convex hulls. Prob. Theory Relat. Fields 79, 329–368. · Zbl 0635.60012 · doi:10.1007/BF00342231
[9] Hall, P. (1992). The Bootstrap and Edgeworth Expansion. Springer, New York. · Zbl 0744.62026
[10] Hsing, T. (1994). On the asymptotic distribution of the area outside a random convex hull in a disk. Ann. Appl. Prob. 4, 478–493. · Zbl 0806.60004 · doi:10.1214/aoap/1177005069
[11] Janson, S., Łuczak, T. and Ruciński, A. (2000). Random Graphs. John Wiley, New York. · Zbl 0968.05003
[12] Kesten, H. and Lee, S. (1996). The central limit theorem for weighted minimal spanning trees on random points. Ann. Appl. Prob. 6, 495–527. · Zbl 0862.60008 · doi:10.1214/aoap/1034968141
[13] Penrose, M. D. (2003). Random Geometric Graphs (Oxford Studies Prob. 6 ). Oxford University Press. · Zbl 1029.60007 · doi:10.1093/acprof:oso/9780198506263.001.0001
[14] Penrose, M. D. and Wade, A. (2004). Random minimal directed spanning trees and Dickman-type distributions. Adv. Appl. Prob. 36, 691–714. · Zbl 1068.60023 · doi:10.1239/aap/1093962229
[15] Penrose, M. D. and Yukich, J. E. (2001). Central limit theorems for some graphs in computational geometry. Ann. Appl. Prob. 11, 1005–1041. · Zbl 1044.60016
[16] Penrose, M. D. and Yukich, J. E. (2003). Weak laws of large numbers in geometric probability. Ann. Appl. Prob. 13, 277–303. · Zbl 1029.60008 · doi:10.1214/aoap/1042765669
[17] Steele, J. M. (1997). Probability Theory and Combinatorial Optimization . Society for Industrial and Applied Mathematics, Philadelphia, PA. · Zbl 0916.90233
[18] Yukich, J. E. (1998). Probability Theory of Classical Euclidean Optimization Problems (Lecture Notes Math. 1675 ). Springer, Berlin. · Zbl 0902.60001 · doi:10.1007/BFb0093472
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.