Growth Rates of Euclidean Minimal Spanning Trees with Power Weighted Edges

Abstract

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\}$.