Convex hulls of random walks

Abstract

We study the convex hulls of random walks establishing both law of large numbers and weak convergence statements for the perimeter length, diameter and shape of the hull. It should come as no surprise that the case where the random walk has drift, and the zero-drift case behave differently. We make use of several different methods to gain a better insight into each case.

Classical results such as Cauchy’s surface area formula, the law of large numbers and the central limit theorem give some preliminary law of large number results.

Considering the convergence of the random walk and then using the continuous mapping theorem leads to intuitive results in the case with drift where, under the appropriate scaling, non-zero, deterministic limits exist. In the zero-drift case the random limiting process, Brownian motion, provides insight into the behaviour of such a walk. We add to the literature in this area by establishing tighter bounds on the expected diameter of planar Brownian motion. The Brownian motion process is also useful for proving that the convex hull of the zero-drift random walk has no limiting shape.

In the case with drift, a martingale difference method was used by Wade and Xu to prove a central limit theorem for the perimeter length. We use this framework to establish similar results for the diameter of the convex hull. Time-space processes give degenerate results here, so we use some geometric properties to further what is known about the variance of the functionals in this case and to prove a weak convergence statement for the diameter. During the study of the geometrical properties, we show that, only finitely often is there a single face in the convex minorant (or concave majorant) of such a walk.