<p>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)$. <a href="http://www-stat.wharton.upenn.edu/~steele/Publications/PDF/SteeleDAM87.pdf" rel="nofollow">Steele showed</a> 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.</p>

<p>It follows from general results that $L_n(\mu)$ is tightly concentrated around the mean. For example, in <a href="http://www.stats.ox.ac.uk/people/academic_staff/colin_mcdiarmid/?a=4139" rel="nofollow">his survey</a> 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)| &gt; t] &lt; e^{-\delta(t) n}$. I am fairly certain that the argument extends to the case of an exponential random variable.</p>

<p>Central limit theorems are also available. <a href="http://www2.math.uu.se/~svante/papers/sj110.pdf" rel="nofollow">Janson proved</a> that $\sqrt{n}(L_n(\mu) - \zeta(3))$ converges in distribution to a Gaussian with mean $0$ and constant variance. (The constant was <a href="http://liu.diva-portal.org/smash/get/diva2:375259/FULLTEXT01.pdf" rel="nofollow">computed exactly</a> by Wastlund.) This is again shown for uniform $\mu$, but I think it should extend to exponential. </p>

<p>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$.</p>

CC BY-SA 3.0
2016-09-16T18:34:39.403Z
[Frieze](https://www.math.cmu.edu/~af1p/Texfiles/MST.pdf) proves the result that you attribute to Steele under some mild assumptions, which suffice to handle exponential distributions.
Yuval Filmus
CC BY-SA 3.0
2016-09-15T01:25:03.233Z
2016-09-15T01:25:03.233Z
Sasho Nikolov
<p>Consider a complete undirected graph with $n$ vertices, $K_n$. Let weight of an edge between vertices $i\; \&amp; \;j$ be a random variable $E_{ij}$. Let $E_{ij} \sim exp(\lambda)$, where $exp(\lambda)$ is an <a href="https://en.wikipedia.org/wiki/Exponential_distribution" rel="nofollow">exponential distribution</a>.</p>

<p><strong>Problem</strong></p>

<p>What is the distribution of weight of the minimum spanning tree of the above graph?</p>

<p><strong>Note</strong> : 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)$</p>

CC BY-SA 3.0
2016-09-14T18:58:57.757Z
I think the distribution is quite complicated and there are no exact characterizations known. However, Alan Frieze has analyzed the expected weight of the MST in the limit as $n$ goes to infinity. Are you interested in that?
Sasho Nikolov
CC BY-SA 3.0
2016-09-14T22:40:27.880Z
I am interested in the asymptotic behaviour of the distribution. Any concentration results around the mean would be helpful :).
Vivek Bagaria
<reference-request><graph-theory><pr.probability><tree>
Minimum Spanning tree on a complete "random" graph
Vivek Bagaria
# Minimum Spanning tree on a complete "random" graph

(Asked by: username_0 on 2016-09-10)

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](https://en.wikipedia.org/wiki/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)$

**Tags:** reference-request, graph-theory, pr.probability, tree
> **Comments:**
> **username_1**: I think the distribution is quite complicated and there are no exact characterizations known. However, Alan Frieze has analyzed the expected weight of the MST in the limit as $n$ goes to infinity. Are you interested in that?  
> **username_0**: I am interested in the asymptotic behaviour of the distribution. Any concentration results around the mean would be helpful :).  

---

## 1 answers

### Answer by username_1 on 2016-09-15. Score: 4

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](http://www-stat.wharton.upenn.edu/~steele/Publications/PDF/SteeleDAM87.pdf) 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](http://www.stats.ox.ac.uk/people/academic_staff/colin_mcdiarmid/?a=4139) 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](http://www2.math.uu.se/~svante/papers/sj110.pdf) 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](http://liu.diva-portal.org/smash/get/diva2:375259/FULLTEXT01.pdf) 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$.

> **Comments:**
> **username_2**: [Frieze](https://www.math.cmu.edu/~af1p/Texfiles/MST.pdf) proves the result that you attribute to Steele under some mild assumptions, which suffice to handle exponential distributions.  

---

