Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Convex hulls of multidimensional random walks


Authors: Vladislav Vysotsky and Dmitry Zaporozhets
Journal: Trans. Amer. Math. Soc. 370 (2018), 7985-8012
MSC (2010): Primary 60D05, 60G50, 60G70; Secondary 52B11
DOI: https://doi.org/10.1090/tran/7253
Published electronically: July 20, 2018
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ S_k$ be a random walk in $ \mathbb{R}^d$ such that its distribution of increments does not assign mass to hyperplanes. We study the probability $ p_n$ that the convex hull $ \mathop {\mathrm {conv}}\nolimits (S_1, \dots , S_n)$ 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, $ p_n$ 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 $ p_n$ as $ n \to \infty $ 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 \ge 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:

$\displaystyle \mathbb{E} V_1 (\mathop {\mathrm {conv}}\nolimits (0, S_1, \dots , S_n)) = \sum _{k=1}^n \frac {\mathbb{E} \Vert S_k\Vert}{k},$    

where $ V_1$ 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 $ p_n$.

We also prove similar results for convex hulls of random walk bridges and, more generally, for partial sums of exchangeable random vectors.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 60D05, 60G50, 60G70, 52B11

Retrieve articles in all journals with MSC (2010): 60D05, 60G50, 60G70, 52B11


Additional Information

Vladislav Vysotsky
Affiliation: Department of Mathematics, University of Sussex, Brighton BN1 9RH, United Kingdom — and — St. Petersburg Department of Steklov Mathematical Institute, 27, Fontanka, 191023 St. Petersburg, Russia
Email: v.vysotskiy@sussex.ac.uk, vysotsky@pdmi.ras.ru

Dmitry Zaporozhets
Affiliation: St. Petersburg Department of Steklov Mathematical Institute, 27, Fontanka, 191023 St. Petersburg, Russia
Email: zap1979@gmail.com

DOI: https://doi.org/10.1090/tran/7253
Keywords: Convex hull, random walk, distribution-free probability, random polytope, intrinsic volume, spherical intrinsic volume, average number of faces, average surface area, persistence probability, orthoscheme, path-simplex, Wiener spiral, uniform Tauberian theorem.
Received by editor(s): November 21, 2016
Received by editor(s) in revised form: February 28, 2017
Published electronically: July 20, 2018
Additional Notes: This paper was written when the first author was affiliated with Imperial College London, where his work was supported by People Programme (Marie Curie Actions) of the European Union’s Seventh Framework Programme (FP7/2007-2013) under REA grant agreement no. [628803]. He was also supported in part by Grant 16-01-00367 by RFBR
The work of the second author was supported in part by Grant 16-01-00367 by RFBR and by Project SFB 1283 of Bielefeld University.
Article copyright: © Copyright 2018 American Mathematical Society

American Mathematical Society