TY - JOUR

T1 - Convex hulls of multidimensional random walks

AU - Vysotsky, Vladislav

AU - Zaporozhets, Dmitry

PY - 2018/1/1

Y1 - 2018/1/1

N2 - Let Sk be a random walk in ℝd such that its distribution of increments does not assign mass to hyperplanes. We study the probability pn that the convex hull conv(S1,…, Sn) of the first n steps of the walk does not include the origin. By providing an explicit formula, we show that for planar symmetrically distributed random walks, pn does not depend on the distribution of increments. This extends the well-known result by Sparre Andersen (1949) that a one-dimensional random walk satisfying the above continuity and symmetry assumptions stays positive with a distribution-free probability. We also find the asymptotics of pn as n → ∞ for any planar random walk with zero mean square-integrable increments. We further developed our approach from the planar case to study a wide class of geometric characteristics of convex hulls of random walks in any dimension d ≥ 2. In particular, we give formulas for the expected value of the number of faces, the volume, the surface area, and other intrinsic volumes, including the following multidimensional generalization of the Spitzer–Widom formula (1961) on the perimeter of planar walks: (Formula Presented) where V1 denotes the first intrinsic volume, which is proportional to the mean width. These results have applications to geometry and, in particular, imply the formula by Gao and Vitale (2001) for the intrinsic volumes of special path-simplexes, called canonical orthoschemes, which are finite-dimensional approximations of the closed convex hull of a Wiener spiral. Moreover, there is a direct connection between spherical intrinsic volumes of these simplexes and the probabilities pn. We also prove similar results for convex hulls of random walk bridges and, more generally, for partial sums of exchangeable random vectors.

AB - Let Sk be a random walk in ℝd such that its distribution of increments does not assign mass to hyperplanes. We study the probability pn that the convex hull conv(S1,…, Sn) of the first n steps of the walk does not include the origin. By providing an explicit formula, we show that for planar symmetrically distributed random walks, pn does not depend on the distribution of increments. This extends the well-known result by Sparre Andersen (1949) that a one-dimensional random walk satisfying the above continuity and symmetry assumptions stays positive with a distribution-free probability. We also find the asymptotics of pn as n → ∞ for any planar random walk with zero mean square-integrable increments. We further developed our approach from the planar case to study a wide class of geometric characteristics of convex hulls of random walks in any dimension d ≥ 2. In particular, we give formulas for the expected value of the number of faces, the volume, the surface area, and other intrinsic volumes, including the following multidimensional generalization of the Spitzer–Widom formula (1961) on the perimeter of planar walks: (Formula Presented) where V1 denotes the first intrinsic volume, which is proportional to the mean width. These results have applications to geometry and, in particular, imply the formula by Gao and Vitale (2001) for the intrinsic volumes of special path-simplexes, called canonical orthoschemes, which are finite-dimensional approximations of the closed convex hull of a Wiener spiral. Moreover, there is a direct connection between spherical intrinsic volumes of these simplexes and the probabilities pn. We also prove similar results for convex hulls of random walk bridges and, more generally, for partial sums of exchangeable random vectors.

KW - Average number of faces

KW - Average surface area

KW - Convex hull

KW - Distribution-free probability

KW - Intrinsic volume

KW - Orthoscheme

KW - Path-simplex

KW - Persistence probability

KW - Random poly-tope

KW - Random walk

KW - Spherical intrinsic volume

KW - Uniform Tauberian theorem

KW - Wiener spiral

UR - http://www.scopus.com/inward/record.url?scp=85055087946&partnerID=8YFLogxK

U2 - 10.1090/tran/7253

DO - 10.1090/tran/7253

M3 - Article

AN - SCOPUS:85055087946

VL - 370

SP - 7985

EP - 8012

JO - Transactions of the American Mathematical Society

JF - Transactions of the American Mathematical Society

SN - 0002-9947

IS - 11

ER -