The central limit theorem for weighted minimal spanning trees on random points
Authors:
- Harry KestenHKHarry Kesten
- Sungchul LeeSLSungchul Lee
Open Access
- 1 May 1996
- journal article
- Published by Institute of Mathematical Statistics in The Annals of Applied Probability
- Vol. 6 (2) , 495-527
Abstract
Let ${X_i, 1 \leq i < \infty}$ be i.i.d. with uniform distribution on $[0, 1]^d$ and let $M(X_1, \dots, X_n; \alpha)$ be $\min {\sum_{e \epsilon T'} |e|^{\alpha}; T' \text{a spanning tree on ${X_1, \dots, X_n}$}}$. Then we show that for $\alpha > 0$, $$\frac{M(X_1, \dots, X_n; \alpha) - EM (X_1, \dots, X_n; \alpha)}{n^{(d-2 \alpha)/2d}} \to N(0, \sigma_{\alpha, d}^2)$$ in distribution for some $\sigma_{\alpha, d}^2 > 0$.
Keywords
This publication has 10 references indexed in Scilit:
- The RSW theorem for continuum percolation and the CLT for Euclidean minimal spanning treesThe Annals of Applied Probability, 1996
- Concentration of measure and isoperimetric inequalities in product spacesPublications mathématiques de l'IHÉS, 1995
- The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graphRandom Structures & Algorithms, 1995
- Limit Theorems and Rates of Convergence for Euclidean FunctionalsThe Annals of Applied Probability, 1994
- Rates of Convergence of Means for Distance-Minimizing Subadditive Euclidean FunctionalsThe Annals of Applied Probability, 1994
- On Central Limit Theorems in Geometrical ProbabilityThe Annals of Applied Probability, 1993
- Asymptotics for Euclidean minimal spanning trees on random pointsProbability Theory and Related Fields, 1992
- Growth Rates of Euclidean Minimal Spanning Trees with Power Weighted EdgesThe Annals of Probability, 1988
- Dependent Central Limit Theorems and Invariance PrinciplesThe Annals of Probability, 1974
- On the Shortest Spanning Subtree of a Graph and the Traveling Salesman ProblemProceedings of the American Mathematical Society, 1956