Growth Rates of Euclidean Minimal Spanning Trees with Power Weighted Edges
Steele, J. Michael
Ann. Probab., Tome 16 (1988) no. 4, p. 1767-1787 / Harvested from Project Euclid
Let $X_i, 1 \leq i < \infty$, denote independent random variables with values in $\mathbb{R}^d, d \geq 2$, and let $M_n$ denote the cost of a minimal spanning tree of a complete graph with vertex set $\{X_1, X_2, \ldots, X_n\}$, where the cost of an edge $(X_i, X_j)$ is given by $\psi(|X_i - X_j|)$. Here $|X_i - X_j|$ denotes the Euclidean distance between $X_i$ and $X_j$ and $\psi$ is a monotone function. For bounded random variables and $0 < \alpha < d$, it is proved that as $n\rightarrow\infty$ one has $M_n \sim c(\alpha, d)n^{(d - \alpha)/d} \int_{R^d} f(x)^{(d-\alpha)/d} dx$ with probability 1, provided $\psi(x) \sim x^\alpha$ as $x\rightarrow 0$. Here $f(x)$ is the density of the absolutely continuous part of the distribution of the $\{X_i\}$.
Publié le : 1988-10-14
Classification:  Minimal spanning trees,  subadditive processes,  60F15,  05C05
@article{1176991596,
     author = {Steele, J. Michael},
     title = {Growth Rates of Euclidean Minimal Spanning Trees with Power Weighted Edges},
     journal = {Ann. Probab.},
     volume = {16},
     number = {4},
     year = {1988},
     pages = { 1767-1787},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1176991596}
}
Steele, J. Michael. Growth Rates of Euclidean Minimal Spanning Trees with Power Weighted Edges. Ann. Probab., Tome 16 (1988) no. 4, pp.  1767-1787. http://gdmltest.u-ga.fr/item/1176991596/