7
$\begingroup$

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)$

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Sasho Nikolov Sep 14 '16 at 18:58
  • $\begingroup$ I am interested in the asymptotic behaviour of the distribution. Any concentration results around the mean would be helpful :). $\endgroup$ – Vivek Bagaria Sep 14 '16 at 22:40
4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Frieze proves the result that you attribute to Steele under some mild assumptions, which suffice to handle exponential distributions. $\endgroup$ – Yuval Filmus Sep 16 '16 at 18:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.