Discrete Applied Mathematics 18 (1987) 99-103 99
NOTE
ON FRIEZE'S CO) LIMIT FOR LENGTHS OF MINIMAL
SPANNING TREES
J. Michael STEELE *
Program in Engineering Statistics, Princeton University, Princeton, NJ 08544
Received 26 March 1986
Revised 17 October 1986

The length of the minimal spanning tree on the complete graph on n vertices with edge weights determined by independent non-negative random variables with distribution F is proved to converge in probability to C(3)IFI(O), provided only that F have a non-zero derivative at the origin. In particular, no other smoothness or moment conditions are placed on F. This augments the result of Frieze for random variables with finite variances and differentiable distribution.

1. Introduction

Let G denote a complete graph with vertex set V with cardinality n and edge set E. Weights are assigned to each eeE by means of non-negative, independent random variables X, with common distribution F. We further let Ln denote the cost of the minimal spanning tree of G, i.e.

L, = min Y, X,
T ecT

where the minimum is taken over the set of all n n-2 trees which span V.
Under the assumption that the X, are uniformly distributed on [0, 11, Frieze [4] established that

0*
lim E(L,,) E k -3= 1.202 (1.2).
n-W k=1
and
L,-((3) in probability as n-oo. (1.3)

In Frieze [5] the result was extended to cover the case of continuous F with finite variances. The purpose of this note is to extend Frieze's theorem to the widest possible class of F. In particular, the next section establishes the following result:

If X, are independent non-negative random variables whose continuous distribution function F is differentiable from the right at 0, with F'(0) > 0, then Ln converges to ~(3)IF'(O) in probability, i.e., for all E > 0

*Research supported in part by National Science Foundation Grant *DMS-8414069.

0166-218X/87/$3.50 @ 1987, Elsevier Science Publishers B.V. (North-Holland)
100 J.M. Steele

P(JL,,-C(3)1F'(O)J>e)--O asn-w. (1.4)

The proof of this. extension leans only on Frieze's result for uniform random variables [4] and is developed independently of Frieze's extension to F with finite variance. The main issue rests in seeing how a variant of the usual probability transform device can fit together rather neatly with a greedy algorithm. This recipe for extension can be expected to be useful in some related problems, but the principal aim is to make Frieze's remarkable limit as widely useable as possible.

2. The limiting result

The independent random variables X, permit us to define a new related family of independent random variables Y, which have the uniform distribution. If F were continuous we could take Y, = F(X,,), but for F with jumps more care is required. For each X, we will define a new random variable Y, which depends on X, and possibly on an additional independent uniformly distributed random variable U, when X, c- A, the set of atoms of F. We will define Y, by

Ye =

F(X,) if XIA,
F(Xe - ) + Ue [F(X~) - F(X, i f X, E A.

(2.1)

What one should observe about the Y, is that although the Y, are not a deterministic monotone increasing image of the X, there is a monotone increasing ordering of the X, such that

A

Y,< Y,, implies X,:5X,,.

The point of this arrangement is now brought out by Kruskal's algorithm, where the edges are considered in non-increasing order and an edge is chosen for inclusion in T if it does not complete a circuit (see, e.g., Aho et al. [ 1, pp. 234-237]). Since there is an ordering of the edges which is consistent with non-decreasing values of both Y, and X, the Kruskal algorithm shows there is a tree T which is a simultaneously minimal spanning tree for both of the weight sequences {XJ and I Y,?J.
Now to express the hypothesis that F is differentiable at the origin in a convenient form we write F(x) = ax+xg(x) and F(x-) = ax+xh(x) where g and h go to zero as x- 0. By the definition of Y, given in (2. 1) and the definitions of f and g we have for the double minimal spanning tree calculated above,

E Xh(X,):5 E Ye-a E X,:5 E Xg(X,)
eET eET e e T ec- T

(2.2)

It will suffice therefore to show that with high probability the two outside terms of
(2.2) are small compared to E e E T X1 -
To bound those outside terms it will be useful to have a large deviation result for
X, when e is an element of the minimal spanning tree. We begin by considering a

I
On Frieze's limit for lengths of minimal spanning trees 101

general random graph G = ( V, E) such that the edge set E is constructed by considering each edge e of the complete graph and accepting e as an element of G with probability p, 0 < p < L We will get a simple and succinct bound on P(G is connected) by following a route like that used for the assignment problem in Karp and Steele [6]. The present method is easier (but less precise) than the methods used in Knuth and Sch6nhage [71 or Erd6s and R6nyi [2] for slightly different models.
If G is disconnected, then there exists a k-set, 1:5 k:5 n/2 which is not connected to its complement, so

n12 (n)(1 -P)k(n-k)
P(G is disconnected):5 E
k=1 k

:5 2 E (ne e - n12) k
1:5 k

where the second inequality is obtained using the symmetry of the previous summands and the standard bounds

(n):, (ne)k and I-p<_e-p.
k k

For np - 2(1 + log n) the summands are decreasing so the whole sum is majorized by n12 times the first term. This proves that

P(G is disconnected):5 en 2 e -pn12 (2.3)

for np > 2(1 + log n); and, since the right hand side is otherwise larger than one, we see (2.3) holds for all 0 < p < I and n 2t 1. Since for each e, P(X, - A) = F(A), inequality (2.3) also says

2 RA)/2
P max X,>A :sen e-n (2.4)
( ec- T

It is now easy to show that in probability we have

E X,9(Xe) = 0 E Xe) (2.5)
eET ( eeT
We first let g*(x)=max0,,-Y,,Xg(y) and note that g*(x)-O as x-0. We then fix
8 > 0, choose A so that g *(A) < E, and note that

P ( e Yc'T Xe g (X) > i 6 e EE T X)

:5P *(A) E X'+( ,E Xe)i maxX,~:A 2:8 E Xe)
(9 eeT cT (ec-T eET
:5P maxXe2tA :5en2e-nF(A)12
(eET
102 J.M. Steele

which establishes (2.5). The completely analogous argument can be applied to
Eec-TXeh(X,), so inequality (2.2) now says

P(ja E X,- E Yej~!g 0 (2.6)
ee T eET

as n - oo. By Frieze's theorem for the uniform distribution Eea T Y1 converges to
C(3) in probability so we have established that as n-co

E Xe-((3)1F'(0)
ec- T

in probability which was to be proved.

3. Concluding remarks

Frieze's theorem provides one of the. very few situations where an explicit limiting
value is known for a sum functional on a graph with random edge weights. This provides the main motivation for pushing the distributional hypothesis to the most general attainable. In the case of F'(0) > 0 there does not seem to be any reasonable way to push further than the result of this note, but if F'(0) = 0 there remains the possibility of a more precise understanding of L,, than the trivially obtainable result that L,-oo in probability. It seems within reason to expect proper rate results, especially if F is assumed to be regularly varying at 0.
Another promising direction is the exploration of functionals which are kindred
to the minimal spanning tree. Walkup [9] has attained interesting bounds on the assignment problem but obtaining the precise limit seems out of reach. Additional functionals for which there are good prospects for progress can be foulnd in Fenner and Frieze [31 and Lueker [8].

References

[11 A.V. Aho, J.E. Hopcroft and J.D. Ullman, Data Structures and Algorithms (Addison-Wesley, Reading, MA, 1983).
[2] P. Erd6s and A. R6nyi, Evolution of random graphs, MTA Mat. Kut. Int. K6zl 5 (1960) 17-61; also in: P. TurAn, e.d., Selected Papers of Alfr6d R6nyi 2 (Akad6miai Kaido, Budapest, 1960) 482-525.
[31 T.I. Fenner and A.M. Frieze, On tkhe connectivity of random m-orientable graphs and digraphs, Combinatorica 2 (1982) 347-359.
[4] A.M. Frieze, On the value of a minimal spanning tree problem, Technical Report, Queen Mary College, London, 1982.
[51 A.M. Frieze, On the -value of a minimal spanning tree problem, Discrete Appl. Math. 10 (1985) 47-56.
[6] R.M. Karp and J.M. Steele, Probabalistic analysis of heuristics, in: E.L. Lawler et al., eds., The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, (Wiley-Interscience, New York, 1985) 181-206.
On Frieze's limit for lengths of minimal spanning trees 103

[7] D.E. Knuth and A. Sch6nhage, The expected linearity of a simple equivalence algorithm, Theoret. Comput. Sc. 6 (1978) 2817315.
[81 G.S. Lueker, Optimization problems on graphs with independent random edge weights, SIAM J. Comput. 10 (1981) 338-351.
[91 D.W. Walkup, On the expected value of a random assignment problem, SIAM J. Comput. 8 440-442.

"I