Convex hulls of random walks

Snyder, Timothy Law; Steele, J. Michael

doi:10.1090/S0002-9939-1993-1169048-2

Convex hulls of random walks
HTML articles powered by AMS MathViewer

by Timothy Law Snyder and J. Michael Steele PDF

Proc. Amer. Math. Soc. 117 (1993), 1165-1173 Request permission

Abstract:

Features related to the perimeter of the convex hull ${C_n}$ of a random walk in ${\mathbb {R}^2}$ are studied, with particular attention given to its length ${L_n}$. Bounds on the variance of ${L_n}$ are obtained to show that, for walks with drift, ${L_n}$ obeys a strong law. Exponential bounds on the tail probabilities of ${L_n}$ under special conditions are also obtained. We then develop simple expressions for the expected values of other features of ${C_n}$, 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.

References

Glen Baxter, A combinatorial lemma for complex numbers, Ann. Math. Statist. 32 (1961), 901–904. MR 126290, DOI 10.1214/aoms/1177704985
Jon Louis Bentley and Michael Ian Shamos, Divide and conquer for linear expected time, Information Processing Lett. 7 (1978), no. 2, 87–91. MR 483687, DOI 10.1016/0020-0190(78)90051-0
Karl-Heinz Borgwardt, Norbert Gaffke, Michael Jünger, and Gerhard Reinelt, Computing the convex hull in the Euclidean plane in linear expected time, Applied geometry and discrete mathematics, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 4, Amer. Math. Soc., Providence, RI, 1991, pp. 91–107. MR 1116341, DOI 10.1090/dimacs/004/07
Yuan Shih Chow and Henry Teicher, Probability theory, 2nd ed., Springer Texts in Statistics, Springer-Verlag, New York, 1988. Independence, interchangeability, martingales. MR 953964, DOI 10.1007/978-1-4684-0504-0
B. Efron and C. Stein, The jackknife estimate of variance, Ann. Statist. 9 (1981), no. 3, 586–596. MR 615434
H. G. Eggleston, Convexity, Cambridge Tracts in Mathematics and Mathematical Physics, No. 47, Cambridge University Press, New York, 1958. MR 0124813
Wassily Hoeffding, Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc. 58 (1963), 13–30. MR 144363
M. Kac, Toeplitz matrices, translation kernels and a related problem in probability theory, Duke Math. J. 21 (1954), 501–509. MR 62867
David G. Kirkpatrick and Raimund Seidel, The ultimate planar convex hull algorithm?, SIAM J. Comput. 15 (1986), no. 1, 287–299. MR 822206, DOI 10.1137/0215021
A. Rényi and R. Sulanke, Über die konvexe Hülle von $n$ zufällig gewählten Punkten, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 2 (1963), 75–84 (1963) (German). MR 156262, DOI 10.1007/BF00535300
F. Spitzer and H. Widom, The circumference of a convex polygon, Proc. Amer. Math. Soc. 12 (1961), 506–509. MR 130616, DOI 10.1090/S0002-9939-1961-0130616-7
J. Michael Steele, An Efron-Stein inequality for nonsymmetric statistics, Ann. Statist. 14 (1986), no. 2, 753–758. MR 840528, DOI 10.1214/aos/1176349952