Please see PDF version
The Annals ofProbabil ty
1981, Vol. 9, No. 3,365 376
SUBADDITIVE EUCLIDEAN FUNCTIONALS AND NONLINEAR
GROWTH IN GEOMETRIC PROBABILITY
BY J. MICHAEL STEELE
Stanford University
A limit theorem is established for a class of random processes (called here subadditive Euclidean functionals) which arise in problems of geometric probability. Particular examples include the length of shortest path through a random sample, the length of a rectilinear Steiner tree spanned by a sample, and the length of a n dnimal matching. Also, a uniform convergence theorem is proved which is needed in Karp's probabilistic algorithm for the traveling salesman problem.
1. Introduction. The main objective of the present paper is to show how the methodology of independent subadditive processes can be used to obtain strong limit laws for a wide class of problems in geometrical probability which exhibit nonlinear growth.
The problems studied here find their origin and principal motivation in a theorem of Beardwood, Halton and Hammersley (1959) of which the following is a special case.
For any bounded i.i.d. random variables {Xi) with values in R' the length of the shortest path through {Xl, X2, . . ., X.} is asymptotic to cn'/2 with probability one.
Because of Karp's (1976) probabilistic algorithm for the traveling salesman problem, results like the above have gained accelerated practical interest. Motivated by algorithn dc applications Papadimitriou. and Steiglitz (1977) and Papadimitriou (1978) have taken pains to abstract the properties used in the Beardwood, Halton and Hammersley theorem. AS a consequence, they have been able to treat other problems, including that of minimal matching of a random sample by Buclidean edges.
The tack taken here differs considerably from. the method of Beardwood, Halton and Hammersley and is in the spirit of Kesten's lemma in the theory of independent subadditive processes (Kesten (1973), Hammersley (1974), Kingman (1976)). One benefit of the present approach is therefore a new proof of the Beardwood Halton Hanunersley theorem, but a level of generality is maintained which permits immediate application to a number of other optimality problems in geometric probability.
The second section is devoted to developing the basic properties of subadditive Euclidean functionals which are the central object of study. The limit theorem proved there (Theorem 1) is established by a pure subadditivity argument which makes no appeal to the two sided bounds sometimes available in specific problems.
The third and fourth sections extend Theorem 1 to nonuniform distributions and also weaken the monotonicity assumption. These sections then treat four specific examples. Section five provides a uniform convergence theorem which serves to rigorize one aspect of Karp's algorithm for the TSP. The final section makes brief comment on some unknown constants and on rates of convergence.
2. Subadditive Euelidean functionals. By L we denote a real valued function of the finite subsets of R, d k 2. It will be assumed that L is a Euclidean functional by which it is indicated that the following properties hold:
Received August 27, 1979; revised March 1, 1980.
Research was partially supported by the National Science Foundation Grant MCS 78 07736.
AMS 1970 subject classification. 601305, 60F15, 60C05, 60G55.
Key words andphrases. Subadditive process, traveling salesman problem, Steiner tree, Euclidean functional.
365
366 . J. MICHAEL STEELE
Al. L(axl, aX2, ..., ax.) = aL(xl, X2, ..., x.) for all real a > 0.
A2. L(x, + X, X2 + X, ..., x. + x) = L(xl, X2, , XJ for all x EE R`.
Since L is a function on the finite subsets of Rd, we also note that L(xl, X2, ..., X.) is
the same as L(x.(j), x,(2), * * ', X.W) for any permutation a: [1, n] > [1, n]. The function L
is also assumed to be monotone, i.e.,
d d
A3. L (x u A) ~~: L (A) for any x E R and finite subset A of R
Since L of the empty set is taken as zero, the monotonicity of L entails positivity; L(A)
0 for all finite sets A C Rd.
The required amount of boundedness of L is provided by an assumption of finite variance,
A4. Var(L (X,, X2, ..., XJ) < oo whenever Xi, 1:5 i:s n, are independent and uniformly distributed in [0, 11d.
The preceeding assumptions are met in a huge number of contexts, and the most telling
is a subadditivity restriction. Suppose that {Q,: 1 :5 i:S Md} is a partition of the d cube
[0, 1]d into cubes with edges parallel to the axle and of length 1/m. Let tQi ty, y
EE Qj}. The subadditivity hypothesis is
A5. There exists a C > 0, such that for all positive integers m and positive reals t one has
LQxi, X2, x.} n [0, t]d) 5 E i_`1 LQxi, x2, . , x.} n tQi) + Ctm`.
The next result provides the key to the subsequent extentions.
THEOREM 1. Suppose L is a monotone, Euclidean functional on R d with finite variance which satisfies the subadditivity hypothesis. If {Xi: 1 :5 i < 00} are independent and uniformly distributed in [0, 1] d, then there is a constant P (L) such that
lim. L(Xl, X2, X.)1n (d l)ld = #(L)
with probability one.
PROOF. We let n denote a Poisson point process in Rd with uniform intensity parameter 1, and for any A C Rd I I (A) denotes the random set of points in A. Next, let X(t) = L(II([0, t]d)) and 0(t) = EX(t). The first task is to prove
0(t)
(2.1) lim, . (L) exists.
By the subadditivity of L,
XW :5 E d M11(tQi)) + Cmd and since L is a Euclidean functional EL(I1(tQi)) = 0(tIm). Hence, one has
lp(t) :5 m do (Q + CM11t. m
Setting t = mu and dividing by td yields
O(MU) Ou) C
(2.2) +
(MU)7 U r U
If 8 = lim inf O(U)/Ud' we note that with u = 1 (2.2) implies by the monotonicity of that
P :5 lim sup. 0(u) lim sup,. . 0(m + 1) 0(1) + C< Co.
uj m g
ClUd d
One now chooses uo so that C :S e and 0(uo)/uo + e to obtain for all m
21...
SUBADDITIVE EUCLIDEAN FUNCTIONALS 367
O(MU0) + e) +
(MUO)7
Again, by the monotonicity of 0(.) and the fact that ((m + 1)U0)d/(MU0)d_ 1,
lim sup 44) p + 2e, U. so the limit, liM~. O(U)/Ud exists and is finite. It will be denoted P (L).
The second task is the calculation of a sum of variances by use of recursions given by
subadditivity. Set m = 2 and let Xi(t) = L(II(tQi)). By A5 one has
X(2t):s E,Ed, Xi(2t) + C2dt.
Define XW = AM + 2Ct and AM) = M2t) + 2Ct, 1 :s is 2~ The nice fact is that now
Xi(t) are i.i.d.,
(2.3) X(2t) 5 Xi(t),
and
(2.4) the X i(t) have the same distribution as X (t).
Next, let ~(t) = EX(t) and 0(t) = (E(X(t) )2)112. One has V(t) = VarX(t) VarX(t)
02(t) _ j2(t) and
(2.5) ~(t)ltd = 0(t)ltd +2C1t` >P(L) as t >oo.
Taking squares and expectations in (2.3) yields
02 (2t) :5 2 dp2(t) + (2 2d _ 2 d)~2(t).
SO,
V(2t) = ~2 (2t) ~2 (2t) :5 2 dV(t) + 22d~2(t)~2 (2t).
Dividing by (2t)2d yields
V(2t) V(t) ~2(t) ~2 (2t)
(2t) 2 t :S tm (2t)W_
Applying this result for t, 2t, ..., 2m` t and summing,
m V(2kt) 1 M 1 V(2kt) ~2(t) ~2 (2mt)~2(t)
h1 _r ) 27 2: r :5
_(2 t k_o (2 t)w ~iw (2fft)
Finally, one finds for all t > 0,
(2.6) ZZ 1 V(2kt) (1 2 d) ` V(t) + ~2(t) < 00.
7t~
72 0 ~t
Now, let N(t) be the Poisson counting process on [0, co) and suppose {Xi: 1 :5 i < oo} are Li.d. uniform on [0, 1] d. Since L is a Euclidean functional well known properties of the Poisson process II show that X(t) = L(HQ0, t] d) ) has the same distribution as tL (X,, X2, .. ., X^d)). Since by (2.1), 0(t)ltd __> P (L) Chebyshev's inequality applied to (2.6) yields for e > 0,
EkLO P t2*L(Xl, X2, XNW219.0 P(L)>e <00;
(1 (t2k) d
and consequently for each t > 0
L (Xl, X2,XNWA0 d)))
(2.7) (t2k)2 1 (L)a.s.
368 J. MICHAEL STEELE
The monotonicity of L will now be used in a slightly more subtle way than was done with 4).
Let p be a fixed positive integer and note for each real s k 2p there is an integer t, 21':5 t < 2P+1 and an integer k 2t 0 so that 2kt s ss 2k(t + 1). Since L is monotone,
L(Xl, X2, , XN((2't).')):5 L(Xl, X2, ..., XN(.,)):5 L(Xl, X2, XN(WU+Md)).
Since the set of t's, 2P:s t 2P+' is finite (2.7) implies
lim sup L (X,, X2, XNw))1sd` 9 (L) (1 + 2 )d 1
and
lim inf.. L (X,, X2, XN(.d)) 18d 1 > . P (L) (1 + 2 ) 1 d
Since p was arbitrary,
(2.8) lim.. L(Xl, X2, ..., X^,d))18" = #(L) a.s.
Next, let T(n) be defined so that N(TWd) n, and note by the elementary renewal theorem
(2.9) r(n)/n'/d 1 a.s.
By the deffflition of T(n) one has
LJi, X2, ..., X.)1n W 1)1d = (L(Xl,X2, "',XI(,(n)d))1,(n)"){,r(n)"1n(" 1)ld
So applying (2.8) and (2.9) to the first and second factors respectively, the theorem is proved. 0
3. Nonuniformly distributed random variables. To extend the preceding result to nonuniformly distributed random variables some additional 1ocalization" properties of L are needed. A Euchdean functional L will be called scale bounded, provided the following assumption holds:
A6. There is a constant B such that
L (xi, X2, ..., X.)Itn(d 1)1d 5 B for all n k 1, t k 1, and
(Xl, X2, ..., X") C [0, tId.
Also, L is called simply subadditive provided
A7. There is a constant B such that
L(A1 u A2)s L(A1) + L(A2) + tB
for any finite subsets A, and A 2 Of [0, tl'.
If g(A) = p (X EE A) is the distribution function of the Xi, the Lebesgue decomposition theorem allows us to write g = g. + g., where tt. is absolutely continuous and g. is singular (with respect to Lebesgue measure). The support of g. will be called the singular support of the Xi, and the next lemma shows that the contribution to L of observations in the singular support is very small.
LEMMA 3.1. Suppose that L is a scale bounded, simply subadditive Euclidean functional. Suppose also that (Xi: 1 s i < oo} are i.i.d. random variables with bounded singular support E, then
(3.1) LQX1p X2, ...,X.} n E) = o(n (d l)ld ) a.s.
PROOF. We can suppose that E C. [0, 1]d and then choose disjoint cubes Q i, 1:5 i:5 M,
W W c
100 ORD 1.19 5
A io 1*9
cl
GC 8
II m PR'
0
o I li (D (D
(D
ti lt;r
('D
AD C4
r~
M CD
c ~:1 . (D M
o CD
0 " % ~l
0 :~ * n 0 02
PD
to
0
Iv IA
:J
0
p m IA
0' 8' IA IA
~< IA
to
IA ;:;: m,,
(D IA 8 a o 0 c ~r ;S
COD. 61
t,
IA cz"
' D IA
(D
ch o cr
r IA t bl
CD
Cb
IA Z1 0"
CD
0
rD
c. S_ 5* li c n
0 OD
CD tl (D t.,
(D
& >
co CD
0Q M f ' CL >
02 n CL tx,
c) &
cr
CD
SD 70~
Cb
CD CD
P, CD
0
90 cl
0Q
t 1
IA
370 J. MICHAEL STEELE
The main result of this section can now be obtained from Lemma 3.2 and a "thinning argument."
THEOREm 2. Suppose L is a Euclidean functional which satisfies assumptions AlA8. There is a constant P (L) such that
lim.. MXi, X2, ..., XjIn W 1)1d = P (L) f,~.d f(X)(d l)ld dx a.s.
for any independent identically distributed random variables {Xi) with bounded support and asolutely continuous part f(x) dx.
PROOF. As before, suppose the {Xi} have support contained in [0, 11d and that E is
the singular support. Next choose a 0(x) =E,Li ailp(i)(x) where Q(i), l:s i 5 s, are disjoint
cubes with edges parallel to the axes. The "thinning domain" A is defined by
(3.4) A = {x: fix) :5 0(x)}.
Now a sequence of random variables Yi, 1 :S i < co, with density 0(x) can be generated from the X as follows. If X EE A U E, then Yi is set equal to some fixed ao EE A; and if Xi 0 A u E, then Yi is taken to be X, or ao according to an independent randomization with probabilities p = O(Xi)lf(Xi) and 1 p respectively.
By Y,~ we denote a third sequence of i.i.d. random variables. These are chosen to have bounded support and absolutely continuous part 4,(x).
The main point of the previous construction is that the two sets of random variables {Y1, Y2, ..., Y.) n (A u E)c and {Y1, Y2, ..., Y.') n (A u E)' now have the same distributions. One then has that the two processes
{L({Yi,Y2,.. ,Y.)n(AuE)e),nkl)={Ln,nkl) and
{L({Yl,Y'2,...,Yln)n(AuE)c),n2:1)={L'.,n2tl)
also have the same joint distributions. From this and the Hewitt Savage zero one law, we
get
(3.5) liminfn .L./n(d ')/d=liminf. .L./n(")/" a.s.
By simple subadditivity
L'n k L(Y1, Yo2, ..., Y'n) LQY1, Y'2, ..., Yn) n (A u E)) B,
so by applying Lemma 3.2 to the first term of the right hand side, then applying scale
boundedness and the law of large numbers to the second one, we get
(3.6) lim inf. . E. In (d l),d fl(L) o(x)(d l)ld dx B 0(x) dx (d l)ld.
L, (L.E
Here one should note that P (L) does not depend upon the auxiliary process {Ln: n ~t 1}; Lemma 3.2 shows that fl(L) depends only on the functional L. We can now apply the monotonicity of L to obtain
L (X,, X2, . . ., X.) 2t L QX,, X2, .. ., Xn) n (A U E)c) 2: L,
so (3.5), (3.6), and the arbitrariness of 0 in (3.4) imply
lim inf,, . MXi, X2, ..., XJ/n (d l)ld P (L) fe fix) (d l)ld dx.
A slightly more elaborate thinning argument will be used to obtain the opposite inequality. We will take (p (x) as before but set A = {x: 0(x) :5 f(x)). Let {Yi} be an i.i.d.
SUBADDITIVE EUCLIDEAN FUNCTIONALS 371
sequence with absolutely continuous part 4)(x) and an atom at ao EE A of size 1 fRd 0(x) dx. For each i define Xt~ = Y, if Yi E: A, otherwise choose Xt~ as Yi or ao according to an independent randomization with probabilities f(Yi)lo(Yi) and 1 f(YJ10(Yj) respectively.
Let E denote the singular support of the (Xi}. Also, let {Ti < T2 < ... {i: Xt~ 0 A} and (a, < a2 < ... } = (i: Xi 0 A u E}. The key observations are that the two dimensional processes {(X, ai)} and ((X',,, Ti)} have the same distribution and that (X',: k ~: 1} is just a subsequence of (Yi: Yi 0 A}. One now calculates,
lim, sup. L(Xl, X2, ..., X.)1n (d l)ld
s lim sup, . L({Xl, X2, X.} n Ec)1n (d l)ld
(3.7) 5 lim sup. LQXi, X2, X.} n Ec n Ac)1n W 1)1d
+ BP(X, E= Ec n A )(d l)ld.
Further one has
lim sup. L((Xl, X2, ..., X.} n Ec n A c)ln(d l)ld
= liM SUPn L QX,: uk :5 n}) /n (d l)ld
(3.8) = lim sup. LQX' : Tts n})/n (d l)ld
slim sup. L(Y1, Y2, ..., V.)1n W DId
Now Lemma 3.2 implies that the last limit superior actually equals #(L) fR4 (X) (d l)ld dx. Finally, one can choose 0 and A so that P(X, EE E' n A) is nearly zero, and fRd 0(x) (d~')"' dx is nearlyfRd f(X) W 1)1d. Used in (3.7) and (3.8), this implies
hin sup. LJi, X2, ..., X.)1n W 1)1d P (L) Ld f(x)(d l)ld dx which completes the proof.
4. Selected applications.
A. Beardwood Halton Hammersley theorem. To apply the preceding results to the Euclidean functional Lo(xi, x2, ..., x.) which equals the length of the shortest path through the points {xl, x2, ..., xJ, one much check several assumptions. It is trivial that Al A4 hold. Assumption A5 is not too hard to cheek, but it is perhaps most easily obtained as a consequence of the following well known lemma.
LEMMA 4.1. There is a constant c = cd such that for any {xi, x2, ..., X.} C [0, tId,
Lo(xi, x2, ..., x.):5 cn (d l)ldt.
PROOF. This has been treated by Fejes Toth (1940), S. Verblunsky (1951), and L. Few (1955), who devoted considerable effort to determining th6 best value of c. For a crude value of c the lemma is easily proved by partitioning the d cube.
Now to justify A5 we construct apath through {xi, x2, . . ., xJ. First take the set of m' path segments of length Lo(tQi n {xi, x2, ..., xn}) through tQi n {Xl, X2, ... ' xJ, and then consider the set of 2m d points which are end points of these segments. By Lemma 4.1 (and a change of scale) there is a path through this set of end points of length not greater than c2 W DIdnd lt. We therefore set a path through (xl, x2, ..', Xn} n [0, t]d with length not more than
Eim dl L({xl, x2, . , x,} n tQ,) + CtMd 1 with C= c2 W Uld.
372 J. MICHAEL STEELE
This completes the justification of Al A5 and thus gives a proof of the BeardwoodHalton Hammersley theorem. To push the result to cover the case of nonuniformly distributed random variables, we need to also verify Assumptions A6 and A7 of Theorem 2. This requires another lemma.
LEMMA4.2. For any finite collection Qi, 1:5 is s, of disjoint cubes and any infinite sequence {xi, x2, ...} c R` one has
q ..., x.} n QJ:5 Lo({xl, X2, ...x,} n (u', , Qi)) + 0(n W 2)/W 1)). (4.1) D i Lo(fxi, x2,
PRooF. Let P be a path which attains Lo({xl, X2, Xn} n u,q l Qi) = 1 and note that by a preliminary perturbation which changes 1 only slightly one can suppose no segment of P is contained in any face of Qi. Let Pi = P n Qi and let Pi., j = 1, 2, ... be the connected components of P, which contain an element of {xi, x2, .. , xJ. Let a, and bu be the points of Pi which intersect aQi. (One gets at most two points since aQ, cannot contain a segment and the Pi are connected). Let si be the length of the edges of Qi and let F,, F2, .. ., F2, be the faces. The set Fk n (ai: j 1, 2, . . ., n} = Aik is contained in a d 1 cube so by Lemma 4,1 there is a path through the elements of Aik of length Cd 1 8, J At 1(d 21/(d 1). Hence, there is a path through W di Aik of length no greater than
E2d 1 (d 2)1(d 1) d/2.
Cd 18, k 1 JAL.k + 2Cdsi2 Since the left side of (4.1) is not greater than
Lo ({xl, X2, .. ., x.) n uf, l Q) plus the lengths of the paths through the % and bij, one has
Is Lo( {xi, x2, xn} n u!, , Q) + V, E1 , EARd i 1 Aik 1(d 2)1(d 1)
(4.2) d 1(d 2)/(d 1)
+ y2 E7 , 1 , 1 Bik + y3Y
where the Bik are defined analogously to the Aik and yl,.y2,, Y3 are constants not depending
on n.
Now by H61der's inequality
2:2d 1(d 2)/(d 1) 2d (d 2)/(d l)(2:q 1 E2d(d l)) 11(d 1)
k 1 1Aik (2:.8 1 E1 1 1Aik k_
:S n W 2)/(d 1) (s2 d) ll(d 1).
Returning to (4.2) one has, as claimed, that
15 Lo({xl, x2, . , x.} n u,Li Q) + 0(n (d 2)/(d 1) 11
By Lemma 4.1 one sees that Lo is scale bounded (A6), and it is also trivial to see Lo is simply subadditive (A7). The last assumption of upper linearity (A8) is a consequence of Lemma 4.2 since (n (d 2)1(d 1) ) 0(n (d l)ld ).
This completes the proof of the Beardwood Halton Hammersley theorem, but comment on the nature of this proof will be postponed to the last section. First consideration will be given to additional applications of Theorems 1 and 2.
B. Papadimitrious matchingproblem. Let L, (xi, X2, x.) denote the length of the
least Buclidean matching of the points {Xl, X2, ... , x.} c R', i.e.,
(4.3) L, (xl, x2, .., X.) Min. ELn?' 11 X.(2. 1) X.(2i)
where 11 x y 11 is the distance from x to y and the minimum is over all permutations a: 11, nj [l, nj.
To treat limit theory of L,, it is useful to generalize Theorems 1 and 2 slightly to accommodate functionals which do not quite satisfy the monotonicity assumption A3. One can call a Euclidean functional L sufficiently monotone provided
(A3)'. There exist a positive sequence rn = o (n (d l)ld) such that for any infinite sequence {Xl, X2, ...} c R` and any m a n one has
L (xi, x2, . . ., x.) k L (xi, x2, X.) r.
SUBADDITIVE EUCLIDEAN FUNCTIONALS 373
With this assumption the proof of Theorems 1 and 2 can be repeated virtually without change to give the following:
THEOREm 3. (a). If L satisfies Al, A2, (A3)', and (A4), then
limn L(Xl, X2, ..., X~)ln (d l)ld = #(L) a.s.
provided (Xi} are independent and uniformly distributed in [0, 1]d.
(b) If, in addition, L satisfies (A5 A8), then
lim L(X, X2, ..., XjIn(d 1)1d = #(L) f? f(x)(d l)ld dx a.s.
provided (Xi} are i.i.d. with bounded support and absolutely continuous part f(x).
To apply Theorem 3 to the least matching functional L,, one first notes that all of the assumptions except A5 and A8 are easily checked. (To show A6, one applies Lemma 4.1 and the bound L, :5 Lo.) To verify A5, one gets a matching of (xl, x2, . . ., x.} n [0, t]" by taking the matchings of (Xl, X2, .. ., x.} n Qi together with a matching of the collection S of elements which are not used in any matching of a {xl, x2, x.} n Q. Since 1 S 1 s m d, A6 (or Lemma 4.1) now shows
L, ({xl, x2, .. ., x.} n [0, tId) :5 E m, dl L, ({xl, x2, x.} n Q) + Bt(Md) (d l)ld
which simplifies precisely to A5.
This lemma completes the considerations which are needed to make the first part of Theorem 1 applicable to the matching functional L,. To be able to use the second part, one further bound is needed.
LEMMA 4.3. For any cubes Qi, 1 :5 i < s,
L, ((xi, x2, x.} n Q) s L, ((xl, x2, x,} n U ~L 1 Qi) + 0(n(d 21/(d l))
for any infinite sequence xi, 1:5 i < 00, in Rd.
PROOF. LetA be a set of arcs which attain 1 L,Qxl, X2, ..., x.} n u'Ll Qj). By the usual perturbation argument there will be no loss in assuming A has no segment in any face of any Qi. Hence, one can let Cj be the set of points in A n aQi which are endpoints of segments which contain an element of Qi n {xi, x2, ..., x.}. By this definition we note
g 1 1 Cj 1 :5 n. Now L, ((xl, x2, ..., x.} n Qj) is certainly no larger than the sum of the length of the segments of A in Qi plus the length of a patch through all of Ci. One then decomposes Cj into the subsets on faces and applies Lemma 4.1 and H61der's inequality as in Lemma 4.2. [1
Remarking again that n (d 2)1(d 1) = 0(n(d l)ld), one has upper linearity (A8) as a consequence of the preceding lemma. Hence, both parts of Theorem 3 apply to the matching functional L,.
C. Steiner trees and rectilinear Steiner trees. A Steiner tree on (Xl, X2, "', Xn}
S C Rd is a connected graph which contains {Xl, X2, ' .., Xn} which has the least total sum of edge lengths among all such graphs. A rectilinear Steiner tree is defined similarly except that the edges are required to be parallel to the axes. One can naturally define two corresponding functionals, and these will be denoted by L2 and L,
While both of these functionals were mentioned in Beardwood, Halton, and Hammersley (1958), their limit theory was not explicitly developed in that paper. Since Al A5 are trivial to verify for L2 and L,3, one sees that Theorem 1 applies immediately. To check the
374 J. MICHAEL STEELE
conditions of Theorem 2, first note that L2 s LO and L3 :S ML2 so Lemma 4.1 gives scale boundedness (A6). Since simple subadditivity (A7) is trivial, only the last assumption (A8) needs individual attention; in this case, the proof of Lemma 4.2 can be applied almost without change.
5. Uniform convergence and Karp's algorithm. In Karp (1976) an algorithm for the probabilistic solution to the traveling salesman's problem is given which hinges on the Beardwood Halton Hammersley theorem and which actually assumes a uniform version of that theorem. The main objective of this section is to rigorize one part of Karp's procedure by establishing a uniform version of Theorem 2. For a further application of the present methods to the %ndependent model" of Karp's problem (B. Weide (1978)) see Steele (1979).
THEOREm 4. Let W denote the class of convex Borel subsets of R`. If A Euclidean functional L satisfies assumptions Al A8, and (Xij is a sequence of i.i.d. random variables with bounded support and absolutely continuous part given by f(x), then
supc. v 1 L QX,, X2, .. .,X.) n 0In (d~l)ld _ #(L) L AX) (d l)ld dx 1
converges to 0 a.s. as n > .
PROOF. Let E denote the singular support of the (Xi) and assume without loss that the whole support is contained in [0, 1]d . Let m(.) denote Lebesgue measure and recall that {C n [0, lld: C E W} = W' is compact in the Hausdorf metric d(A, B) = m (A A B). Defining df (A, B) = fAlB f(X) (d l)ld dX, one can use the compactness W' under d to prove compactness under df (e.g., by writing f(X) W 1)1d = fl (X) + f2 (x) where fl E L 2q0, 1]d ) and fRd f2 (x) dx < a and using Schwar& inequality). Hence, we can choose Q, 1 :s i :5 k, such that for all C EE W' there is a Ci such that
L, f(x) W 1)1d dx:s c.
Next, by simple subadditivity applied twice,
1 L QX,, X2, X.} n C) ~ L QX,, X2, X.} n Q) 1
:s B + L QX,, X2, X.) n CA Ch).
Now, consider the class of sets
S= {A:A = CA C', f(x) dx:s c dl(d 1), C, C'EE W},
fA .
and note for A e 8, fA f(X) (d l)ld dx :s c. The basic bounds are the following:
supcr=,( 1 L((Xl,X2, ...,X.} n C)1n W 1)1d L f(x) (d~l)ld dx
(5.1) :S maxisisk 1 L QX,, X2, ...,X.) n Ci)lnW 1)1d L f(x)(d l)ld dx
+ SUPAES W(Xl, X2, ..., X,} n A) + B)/n (d 1)d + E.
The first term on the right in (5.1) goes to zero a.s. by Theorem 2. For the second term note for all A EE S
L QX,, X2, X.} n A) :5 L QX, X2, X.) n E)
SUBADDITIVE EUCLIDEAN FUNCTIONALS 375
(5.2) + L QX,, X2, . , X.) n Ec n A) + B
s L({Xl, X2, ...,X,,} n E)
+ B(E,~' 1 1AIE~(Xi)) (d l)ld + B.
Since L({Xl, X2, ..., X.} n E)1n (d l)ld goes to zero a.s. by Lemma 3.1, it will suffice to verify that
dl(d 1)
(5.3) lim. . SUPAES D 1 1AnE~(Xi):5 e
n
dl(d 1)
Since P(X E A n E') = fA f(x) dx:s e ' (5.3) is an easy consequence of the fact that the class of convex sets is a uniformity class, i.e., the law of large numbers applies uniformly to the sums (l/n) Y,,Li lc(Yi) over all C E W provided supc P(Y, E: aC) = 0. (See, e.g., Ranga Rao (1962) or Steele (1978)).
6. Remarks on constants and rates. One of the persistently interesting aspects of subadditive methods is that one proves convergence to a constant which is unknown and sometimes seems unknowable. For the shortest path functional the best known bounds are to be found in Beardwood Halton Hammersley (1959) which improves upon Mahalanobis (1940), Marks (1948), and Ghosh (1949). Papadimitriou (1978) gives the best known bounds for the matching functional. While no independent bounds are known on the constant for the Steiner functional, the rectilinear Steiner problem has recently been studied by F. R. K. Chung and R. L. Graharn (1980) and F. R. K. Chung and F. K. Hwang (1979).
A second problem of interest is that of rates of convergence. At the level of generality of Theorem 1 it is unlikely that one can say anything about rates of convergence, but by considering processes which have two sided bounds, as in Theorem 2, it is much more likely that a rate result can be obtained, Some preliminary results in this direction have been obtained jointly with T. L. Lai and may be reported in a subsequent paper.
Acknowledgment. I would like to thank Patrick Billingsley and Steve Lalley for their detailed comments on an earlier draft of this paper.
REFERENCES
BEARDWOOD, 1, HALTON, J. H. and HAMMERSLEY, J. M. (1959). The shortest path through many points. Proc. Cambridge Philos. Soc 55 299 327.
CRUNG, F. R. K. and GRAHAM, R. L. (1980). On Steiner trees for bounded point sets. Unpublished manuscript.
CHUNG, F. R. K. and HWANG, F. K. (1979). The largest minimal rectilinear Steiner trees for a set of n points enclosed in a rectangle with given perimeter. Networks 9 19 36.
FEJES, L. T. (1940). Ober einen geometrischen Satz. Math. Z. 46 83 85.
FEw, L. (1955). The shortest path and the shortest road through n points. Mathematika 2 141 144. GROSH, H. W. (1949). Expected travel among random points. Bull. Calcutta Statist. Assoc. 2 82.
HAMMERSLEY, J. M. (1974). Postulates for subadditive processes. Ann. Probability 2 652 680.
KARP, R. M. (1976). The probabilistic analysis of some combinatorial search algorithms. In Proc. Symp. New Directions and Recent Results in Algorithms and Complexity. (F. Taub, ed.). Academic, San Francisco.
KARP, R. M. (1977). Probabilistic analysis of partitioning algorithms for the traveling salesman problem in the plane. Math. Op. Res. 2 209 224.
KFSTEN, H. (1973). Contribution to J. F. C. Kingman, "Subadditive ergodic theory." Ann. Probability 1883 909.
KINGMAN, J. F. C. (1976). Subadditive processes, Ecole WEt6 de probabilit& de Saint Flour. Lecture Notes in Math. 539. Springer, New York.
MAHALANOBIS, P. C. (1940). A sample survey of the acreage under jute in Bengal. Sankhyd 4 511~ 531.
MARKs, E. S. (1948). A lower bound for the expected travel among m random points. Ann. Math. Statist. 19 419 422.
PAPADIMITRIOU, C. H. (1978). The probabilistic analysis of matching heuristics. Proc. 15th Annual
376 J. MICHAEL STEELE
Conference Comm. Contr. Computing. Univ. Illinois.
PAPADIMITRIOU, C. H. and STEIGLITZ, K. (1979). Combinatorial Optimization Algorithms. To appear.
RAO, R. RANGA. (1962). Relations between weak and uniform convergence of measures with applications. Ann. Math. Statist. 33 659 680.
STFELE, J. M. (1981). Complete convergence of short paths and Karp's algorithm for the TSP. Math. Cp. Res. (To appear).
STEELE, J. M. (1978). Empirical discrepancies and subadditive processes. Ann. Probability 6 118~127.
VERBLUNSKY, S. (1951). On the shortest path through a number of points. Proc. Amer. Math. Soc. 2 904 913.
WEIDE, B. (1978). Statistical methods in algorithm design and analysis. Thesis, Depart. Computer Science, Carnegie Mellon Univ., Pittsburgh.
DEPARTMENT OF STATISTICS
STANFORD UNIVERSITY
STANFORD, CALIFORNIA 94305