Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
Consider a complete undirected graph with $n$ vertices, $K_n$. Let weight of an edge between vertices $i\; \& \;j$ be a random variable $E_{ij}$. Let $E_{ij} \sim exp(\lambda)$, where $exp(\lambda)$ is an exponential distribution.
Problem
What is the distribution of weight of the minimum spanning tree of the above graph?
Note : If $ X_1 \sim exp(\lambda_1)$ and $X_2 \sim exp(\lambda_2)$, then $min(X_1, X_2) \sim exp(\lambda_1+\lambda_2)$
Let's consider a general model in which $L_n(\mu)$ is the (random) length of an MST on $K_n$, where the weight of each edge is sampled independently from a probability distribution $\mu$. When $\mu$ is uniform on $[0,1]$, Frieze showed that $\lim_{n \to \infty} \mathbb{E}[L_n(\mu)] = \sum_{k\ge1}{\frac{1}{k^3}} = \zeta(3)$. Steele showed that for a $\mu$ with CDF $F$ which is differentiable from the right at $0$, this same limit is $\zeta(3)/F'(0)$. In particular, for $\mu$ an exponential distribution with parameter $1$, the expectation is once again $\zeta(3)$ in the limit.
It follows from general results that $L_n(\mu)$ is tightly concentrated around the mean. For example, in his survey McDiarmid shows how to use Talagrand's inequality to prove that, in the case of $\mu$ uniform on $[0,1]$, for any $t$ there exists a $\delta(t)$ such that $\Pr[|L_n(\mu) - \zeta(3)| > t] < e^{-\delta(t) n}$. I am fairly certain that the argument extends to the case of an exponential random variable.
Central limit theorems are also available. Janson proved that $\sqrt{n}(L_n(\mu) - \zeta(3))$ converges in distribution to a Gaussian with mean $0$ and constant variance. (The constant was computed exactly by Wastlund.) This is again shown for uniform $\mu$, but I think it should extend to exponential.
BTW, Steele's result is basically a reduction to the uniform case. Say $\mu$ has a continuous CDF $F$. Then, if $X$ is distributed according to $\mu$, $F(X)$ is uniform on $(0,1)$, and, moreover, $F$ is a monotone function. So, if you apply $F$ to the random weights of your graph, you don't change the MST, and you change the weights to be uniform. The other key observation is that all weights in the MST will be fairly small, so you only really care about the behavior of $F$ close to $0$.
