Please see PDF version
PROCEEDINGS OF THE
AMERICAN MATHEMATICAL SOCIETY
Volume 117, Number 4, April 1993
CONVEX HULLS OF RANDOM WALKS
TIMOTHY LAW SNYDER AND J. MICHAEL STEELE
(Communicated by George C. Papanicolaou)
ABSTRACT. Features related to the perimeter of the convex hull Q of a random walk in R2 are studied, with particular attention given to its length L,, . Bounds on the variance of L,, are obtained to show that, for walks with drift, L,, obeys a strong law. Exponential bounds on the tail probabilities of L,, under special conditions are also obtained. We then develop simple expressions for the expected values of other features of Q , including the number of faces, the sum of the lengths and squared lengths of the faces, and the number of faces of length t or less.
1. INTRODUCTION
Let Zj, 1 < j < oo, be a sequence of independent, identically distributed random vectors with Zj E R2 , EZj = p, and EIZj12 < 00. We set So = 0 and let Sk denote the partial sum of the Zj over 1 < j :5 k. The purpose of this article is to investigate geometrical features of the convex hull Q of {SO, S,, ... , Sn}, and we are particularly concerned with L, the length of the perimeter of Q.
The variable L,, was first studied by Spitzer and Widom [ 11 ], and, by using a classical geometrical theorem of Cauchy (cf., Eggleston [6, p. 891) that says the length of the perimeter of a convex set is the average of the length of its projections on a line through the origin, they found an elegant formula for the expectation
(1. 1) EL, = 2 E1Ski.
k=l
Spitzer and Widom's passage from Cauchy's formula to (1. 1) called upon a combinatorial identity discovered earlier by Kac and proved by Dyson (cf., Kac [8]). A different proof of (1.1) was later given by Baxter [1], where the Cauchy representation was replaced by a purely combinatorial approach.
Received by the editors June 3, 199 1.
1991 Mathematics Subject Classification. Primary 60D05, 60C05, 68U05, 62G99.
Key words and phrases. Strong laws, convex hulls, random walks, Efron Stein Inequality, variance bounds, geometric probability.
The first author was supported in part by Georgetown University 1991 Summer Research Award and Georgetown University 1992 Junior Faculty Research Fellowship. The second author was supported in part by grants NSF DMS88 12868, NSA M13A904 89 H 2034, AFOSR 89 0301, and DAAL03 89 G 0092.
(D 1993 American Mathematical Society
0002.9939193 $1.00 + $15 per page
1165
1166 T. L. SNYDER AND J. M. STEELE
In §2, we obtain more detailed information concerning the distribution of L, This is achieved by coupling the classical representation of Spitzer and Widom with the theory of jackknife inequalities. The end product is a general bound on the variance of L, . When the Zj are assumed to have finite variance and nonzero mean, the variance bound can be used to obtain a law of large numbers for the length of the boundary of the convex hull of a random walk.
In §3 we obtain strong inequalities for the tail probabilities of L,, when the Zj are assumed to be bounded; namely, we find that if 11ZJ 11,,~ :5 1 , then P (1 L. EL, 1 > t) < 2 exp( t2 /8nn2). The proof of this inequality rests on three ingredients: martingale differences, "change one" random variables from the theory of jackknife inequalities, and a lemma of Hoeffiding [7].
Section 4 provides a simple formula for the expected value of several quantities related to the faces of Q. For example, for walks without drift, we obtain (2)
an intriguing identity for ELA , the expected sum of the squared lengths of the faces
(2) + U2).
(1.2) ELn = 2n(a,2 Y
Here ax2 and U2 denote the variances of the coordinates of the summands Y
(2
Zj = (Xj , Yj) , and, curiously, ELA ) does not depend on the correlation of the coordinates.
The last section focuses on connections between the results of this paper and basic questions in the theory of algorithms. Brief note is made of some open problems.
2. THE VARIANCE OF Ln
In the course of their proof of the basic identity (1. 1), Spitzer and Widom pointed out a useful representation of Ln , namely, that Ln equals the average size of the numerical range of the projections of the set {Sk , 0 < k < n} onto a line with direction 0. Thus, if p(Sk, 0) denotes the projection of Sk onto the line through the origin that makes an angle 0 with the x axis, then for all realizations of the random walk we have
(2.1) Ln = J'[0Taxnp(Sk, 0) min p(Sk, 0) dO,
0 where p(Sk, 0)=XkcosO+YksinO for Sk = (Xk, Yk) and 0< 0<7t.
Because of jackknife inequalities like that of Efron and Stein [5], this representation of Spitzer and Widom suggests a convenient way to bound the variance of Ln . Although the original Efron Stein Inequality applies only to functions of random variables S(Xl, Xl, ... , Xn) that are almost surely invariant under permutations of their arguments, a modified version given in Steele [12] can be applied to any real valued function Y(Xl , X2, ... , Xn) of n independent identically distributed random vectors Xi. Specifically, if we write Y = Y(Xl, X2, ... , X.) and let Y(j) = Y(Xl, X2, ... , Xi i, ki, Xi+l, . .. , Xn) 1 where the 2n random vectors Xj and kj , for 1 < i < n , are i.i.d., then Steele [121 shows that
n
(2.2) VarY < E E(y _ y(j))2.
j=1
CONVEX HULLS OF RANDOM WALKS 1167
Applying (2.2) to L, viewed as a (non permutation invariant) function of the Zj we obtain n
(2.3) VarL,:5 EE(Ln L(j))2,
n
j=1
where L(j) denotes the length of the convex hull of {Sl(j), S(j), S(j)} and
n 2 n
the S(j) are formed by replacing the jth summand Zj by the independent
k
copy Zj .
To bound E(Ln Ln(j))2, we use the parameterized range function
(2.4) R(n, 0) = max p(Sk, 0) min p(Sk, 0),
1so the Spitzer and Widom representation (2. 1) becomes Ln = fox R(n , 0) dO .
We can now write
2
E(Ln n )2
(2.5) L(j) = E { fo (R(n, 0) R0(n, 0)) dO
where R0(n, 0) isjust R(n, 0) with Sk replacedby S(P foreach 1 < k < n. k
Our first lemma bounds the change in the range function in terms of Zj and
its redrawn counterpart ii
Lemma 2.1. For all 1 < i < n,
(2.6) IR(n, 0) RU)(n, 0)l :5 lp(ZJ, 0) p(ij, 0)1.
Proof. Consider the effect on p (Sk , 0) when Zj is replaced with ij . If j > k ,
then p(Sk, 0) = p(S(j), 0). If j :5 k, then p(Sk, 0) = p(S(j), 0) + p(Zj, 0)
k k
p(Zj, 0). Hence, for all j,
(2.7) P(Sk, 0) :5 P(Sk'), 0) + [P(Zi, 0) P(2j, Ofl+,
where we write [x]+ = x if x > 0 and [x]+ = 0 if x < 0 (and [x] 0 if
x > 0 and [xl x if x < 0) . We therefore have that
'j)
(2.8) max P(Sk, 0) :5 max p(Sk 1 0) + 1PA 1 0) P('i 1 0)1+.
1Similarly, we find
U)
(2.9) min p(Sk, 0) k min p(Sk 1 0) + 1PA 1 0) P('i 1 0)1
1:~,kso, combining (2.8) and (2.9), one has
(2.10) R(n, 0) R(j)(n, 0) < [p(Zj, 0) p(ij, 0)1+ [p(Zj, 0) P(ii, 0)P;
but, by the identity [xl+ [xl = 1xl and by the symmetry of R(n, 0) and
RW(n, 0), we can replace the left side of (2.10) with the corresponding absolute
value, thus completing the lemma. E]
If we now insert the bound of Lemma 2.1 into equation (2.5) and apply the jackknife bound (2.3), we obtain
(2.11) Var L,, < 1 E n [i,,P(Zj,,)_P(,j, 0)l dO 2
~ E 1
j=1
To bound (2.11), write Zj = (Xj , Yj) , and let ax2 and uy2 be the variances of the Xj and Yj, respectively.
1168 T. L SNYDER AND J. M. STEELE
Lemma 2.2. For all 1 < j < n,
(2.12) E [J' jp (Zj, 0) p(ij, 0) 1 do] 2 < 712(aX2 + U2).
Y
Proof. We first apply the Schwarz Inequality to the left hand side of (2.12) to get
7r 2
(2.13) E Ifo lp(ZJ, 0) p(ij, 0)l do] < nE fo lp(Zj, 0) p(ij, 0) 12 do.
Since Zj and ii are identically distributed, by the definition of p(Zj, 0) one has
Elp(ZJ, 0) p(ij, 0)12 = 2Var[p(ZJ, 0)l
= 2 (ux2 COS2 0 + uy2 sin 20 + 2 cos 0 sin Opxyaxay), so
E/' lp(Zj, 0) p(ij, 0) 11 do 2 (UX2 COS2 0 do + UY2 sin 2 OdO
0 0
(2.14) +4pxyuxuy /0 cos 0 sin 0 do
71(aX2 + UY2).
This proves the lemma. ii
Lemma 2.2 and the jackknife inequality (2.11) provide a basic bound on the variance of L,
Theorem 2.3. For all n > 1
(2.15) Var Ln < n 2 n (ax2 + U2 )/2.
Y
The 0(n) bound can be used in a familiar way with an interpolation argument and the Borel Cantelli Lemma to give a strong law for L, when A 54 0. To sketch the argument, we first need to check that
(2.16) EL,, 2n1M1.
This follows from the Spitzer and Widom identity (1.1) if E1Ski kJAI, but, for summands with finite variance, the latter relation is well known and can be extracted using, for example, a theorem of Marcinkiewim and Zygmund (see Chow and Teicher [4, p. 125]).
Finally, by taking nk = k2 and C = n2(aX2+ay2)12 and applying our variance bound of Cnk with Chebyshev's inequality, we find for any e > 0 that
00 C 00 1
(2.17) 1: P((Ln, EL,jInk k e) :5 le 2 1: F2
k=l k=l
We therefore see that (L^,, ELnJInk + 0 almost surely as k + 00. Since ELn is monotone, there is no difficulty in completing the interpolation argument needed to show that LnIn converges almost surely.
3. LARGE DEVIATIONS
In this section we assume that the steps of the random walk are bounded. We use the following bound on the moment generating function of L,, to provide bounds on the tail probabilities of L, EL, .
CONVEX HULLS OF RANDOM WALKS 1169
Lemma 3.1. If 11 Zj 11 :5 1, then for all t > 0
(3.1) E[exp(t(L. ELffl:5 exp(2nx2 t2).
Before proving Lemma 3.1, we note that applying the lemma twice with
Markov's Inequality gives us a basic tail bound.
Corollary 3.2. If 11Zj11.:5 1, thenfor all t > 0
(3.2) P(IL, ELn 1 ~: t) :5 2 exp(_t2 18n 7r2).
Proof. We first note that the Spitzer Widom representation and Jensen's In
equality yield
exp(n it(L, EL,))=exp (R(n, 0) ER(n, 0)) dO
7r
(3.3) ( t fo',
< 1' exp(t(R(n, 0) ER(n, Offl dO.
it 0
Now if Yj denotes the a field generated by {Z1 , Z2, . Zj} and YO denotes
the trivial a field, then we have for each 0 that
n
(3.4) R(n, 0) ER(n, 0) = 1: dj (0) ,
j=1
where dj is the martingale difference defined by
(3.5) dj(O) = E[R(n, 0)1Yj] E[R(n, 0)1.grj 1]
for 1 < j < n. As in §2, we use the "change one" variables RM(n, 0) and
note that since ij is independent of Yj , we have
(3.6) E[R(j)(n, O)Igj ] = E[R(n, 0)1Yj_11;
thus, we can write dj conveniently as
(3.7) dj(O) = E[R(n, 0) Rffi(n, 0AY51
By Lemma 2.1 and the bound 11Zj11,,. < 1, we therefore find that Ildj(0)11.:5 2
for all 0 .
Next we note that
n exp ( n 1
(3.8) E exp t E dj (0)) ] =E tEdj(O) E[exp(td.(0))lY,1]
( j=1 j=1
By a lemma of Hoeffiding [7, Equation 4.1], if X has mean zero and if 11X11. <
a, then E[exp(tX)J:5 exp(altl/2). Applying Hoeffiding's lemma to the expec
tation of dn (0) in (3.8), we see that
n n 1
(3.9) E exp t 1: dj (0) :5 exp(2t2 )E exp tl:dj(O)
( j=1 )l ( j=1
Repeating the argument for n 1, n 2, we find for all 0 that
n
(3.10) E exp t E dj (0) :5 exp(2n t2),
( j=1 )l
soon returningto (3.3), we can apply (3.10) to obtain (3.1). E]
1170 T. L. SNYDER AND J. M. STEELE
4. FUNCTIONS OF THE FACE LENGTHS
We will now give a formula that generalizes that of Spitzer and Widom and provides new information on the expectations of several other features of the convex hull of a random walk. The derivation of these expectations will depend on the following
Lemma (Baxter [1]). Let {Zl , Z2, z,,} be vectors in R2 such that all 2n
subsets Of {ZI, Z2, ... , z,} have distinct sums. For any permutation a of
1, 2, n, let sk(a) = E~ 1 z,(i) for 1 < k < n, and let so = 0. Then, for any nonempty m set A c { 1 , 2, n} , the vector ZA = EjeA Zi is a face of the convex hull Cn(U) Of {SO(U), S1 (U), ... , Sn(a)} for exactly
(4.1) 2(m 1)! (n m)!
of the permutations of { 1 , 2, n} .
For any f :R ~ R, let
Hn
(4.2) Gn f(leil),
where jell, 1e21, ..., leHni are the lengths of the faces of the convex hull of {SO, S,, ... , S,,}. Here one should note that Hn is a random variable. If we suppose that the Zj for 1 < j :5 n have a common density, then with probability one {Zj, 1 < j :5 n} is a set with distinct subset sums, and we can
apply Baxtet's Lemma. If we let Gn(U) = Gn(Z,(i), 4(2), ... , Z,(,)), then we can now determine the sum of Gn(u) over all a in terms of a sum over all nonempty A c {1, 2, n}. Let Cn(a) denote the convex hull of So and
C
Sk (U) = 4(1) + + Za(k) , where 1 < k < n . Letting ZA denote Ei =A Zi and 1 the standard indicator function, we have
G,, (a) E f(IZA 1) 1 (ZA is a face of Q (a))
A
(4.3) f(l ZA 1) E 1 (ZA is a face of Q (a))
A a
j f(IZA1)2(1A1 1)! (n IAI)!,
A
where the last step follows from Baxler's Lemma. The left side of (4.3) has expectation WEGn, so, using the fact that EflIZA1) = Ef(ISki) if JAI = k, we see that
(4.4) WEG(n) = 2 n (n )Ef(ISkl)(k 1)! (n k)!.
E k
k=l
This yields the following lemma.
Lemma 4.1. If the summands Zj, where 1 < j :5 k, have a common density, then, for any f for which EfflSk 1) exists,
(4.5) EGn = 2 n Ef(ISki)
1: k
k=l
CONVEX HULLS OF RANDOM WALKS 1171
The identity (4.5) turns out to be quite powerful. For example, when f(x)
1 , then G,, = H, and we recapture the interesting relation
(4.6) EHn = 2 21nn,
k=l which is due to Baxter [1]. Further, if f(x) = x, then (4.5) returns to us the formula of Spitzer and Widom, (1. 1), which was originally proved via Cauchy's formula, but here emerges from purely combinatorial calculations.
These two choices of f are not the only ones for which interesting formulas (2) result. If we consider f(x) = xl and define Ln to be the sum of the squared edge lengths of Q, then we find for Zj = (Xj, Yj) that
1Sk12 = (X, + X2 + + Xk)2 + (y, + y
2 + + y
k)2.
If we take the Xj and Yj to be distributed with mean zero and variance UX2
2 12 + U2), SO
and ay, respectively, then E1Sk = k(ax2 Y
ISfl n
(4.7) E = 2 E(UX2 + a2) = 2 n (ux2 + U2),
k k=l
from which we find the remarkable formula
(4.8) EL (2) = 2 n (ux2 + U2);
n Y
that is, the expected sum of squares of the faces of the convex hull of a random walk is just n times twice the variance of an individual step. Although the development of (4.8) has proceeded somewhat seamlessly, it might otherwise have been difficult to guess or prove (4.8) without Lemma 4. 1.
The lemma can also be used to determine the expected cardinality of subsets of the faces that satisfy certain properties. As an example, we determine the expected number of hull faces that are of length t or less under a normality assumption.
Proposition. If Zj = (Xj, Yj) are i.i.d. N(O, U2j), then one has an exact expression for the number offaces ei of Q having length t or less:
1 ~t2/2ka2).
(4.9) El{i: leil :5 t}i = 21: ~~(1 e
k=l
Proof. Let f(x) = 1 (x < t) . To prove (4.9), we use Lemma 4. 1:
EG, = 2 n p(,Ski :5 t)
E k
k=l
(4.10) n p (( k Xj) 2 + ( k Y
= 2 E Y E E J) 2 < t2)
k=l j=1 j=1
Since the Xj and Yj are normally distributed, a traditional calculation tells
(Ek 1 Xj)2 + (Ek 1 yj)2 is exponentially distributed with mean 11A
us that j= j= ,2/2k,2
2ka2. We see then that P(I&I :5 t) e and thus (4.9) follows
immediately. 11
1172 T. L. SNYDER AND J. M. STEELE
5. CONCLUDING REMARKS
A basic topic in computational geometry is the determination of the convex hull of point sets in R2. One result of particular interest is the "output sensitive" algorithm of Kirkpatrick and Seidel [9] that determines the convex hull of an nset of R2 in time 0(n log h) , where h is the number of faces of the convex hull. The Kirkpatrick Seidel algorithm asymptotically outperforms older 0(n log n) algorithms when a point set is such that the number of faces of its convex hull is relatively small.
This situation prevails in some, but not all, probabilistic contexts. For example, R6nyi and Sulanke [ 10] showed that for points selected uniformly from the unit square, the expected number of hull faces is Eh (8/3) Inn. This implies that a convex hull for such point sets can be found in 0(n log log n) expected time by the Kirkpatrick Seidel algorithm. On the other hand, for variables that are distributed uniformly in the unit disk, R6nyi and Sulanke [10] showed that Eh , an 1/3, where a is constant. Thus, for these point sets, we can expect the Kirkpatrick Seidel algorithm to run in time that is the same order of magnitude as that required by older methods.
One of the motivations for studying the convex hull of random walks is that it provides a second rich stochastic context in which the Ktrkpatrick Scidel algorithm leads to an order of magnitude expected speedup in the time needed to determine the convex hull. Specifically, the results of §4 imply that an 0(n log log n) expected running time suffices to determine the convex hull of a random walk. Though there exist algorithms that run in linear expected time (see, e.g., Bentley and Shamos [2] and Borgwardt, Gaffke, Ainger, and Reinelt [3]), these algorithms still exhibit 0(n log n) worst case behavior.
0 500W 100000 150000 20C~O 250000
n
FIGURE 1
CONVEX HULLS OF RANDOM WALKS 1173
There are several natural and concrete problems that the methods of this article leave unresolved. First, the variance bound of 0(n) provided by the jackknife inequality appears to be difficult to improve, but there is no compelling reason to expect that 0(n) is the correct order of magnitude; VarLn may indeed be smaller. One would expect that an o(n) bound would contribute to the understanding of the behavior of Ln in the zero drift case. Results from simulations, however, as illustrated in Figure 1, indicate that an o(n) bound in the zero drift case may not hold. In a complementary direction, the analysis of §4 suggests that a distributional limit result, perhaps even a Poisson law, might hold for the number of edges of length less than t; however, the main tools used here, the Spitzer Widom representation and Baxter's Lemma, do not seem to offer progress on either of these problems.
REFERENCES
1. G. Baxter, A combinatorial lemma for complex numbers, Ann. Math. Statist. 32 (1961), 901 904.
2. J. L. Bentley and M. I. Shamos, Divide and conquerfor linear expected time, Inform. Process. Lett. 7 (1978), 87 91.
3. K. H. Borgwardt, N. Gaffke, M. Ringer, and G. Reinelt, Computing the convex hull in the Euclidean plane in linear expected time, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 4, Arner. Math. Soc., Providence, RI, 1991, pp. 91 106.
4. Y. S. Chow and H. Teicher, Probability theory. Independence, interchangeability, martingales, Springer Verlag, New York, 1988.
5. B. Efron and C. Stein, The jackknife estimate of variance, Ann. Statist. 10 (1981), 586 5 96.
6. H. G. Eggleston, Convexity, Cambridge Univ. Press, London, 1958.
7. W. Hoeffiding, Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc. 58 (1963), 13 30.
8. M. Kac, Toeplitz matrices, translation kernels, and a related problem in Probability theory, Duke Math. J. 21 (1954), 501 509.
9. D. G. Kirkpatrick and R. Seidel, The ultimate convex hull algorithm?, SIAM J. Comput. 15 (1986), 89 96.
10. A. Mnyi and R. Sulanke, (iber die konvexe Mille von n zufdllig gewdhlten Punkten, Z. Wahrsch. Verw. Gebiete 2 (1963), 75 84.
11. F. Spitzer and H. Widom, The circumference of a convex polygon, Proc. Amer. Math. Soc. 12 (1961), 506 509.
12. J. M. Steele, An Efron Stein inequalityfor non symmetric statistics, Ann. Statist. 14 (1986), 753 758.
DEPARTMENT OF COMPUTER SCIENCE, GEORGETOWN UNIVERSITY, WASHINGTON, DISTRICT OF CoLumBiA 20057
E mail address: tim@nomiaI.georgetown.edu
DEPARTMENT OF STATISTICS, THE WHARTON SCHOOL, UNIVERSITY OF PENNSYLVANIA, PHILADELPHIA, PENNSYLVANIA 19104
E mail address: steele@wharton.upenn.edu