Convex hulls of multidimensional random walks

DOI10.1090/TRAN/7253MaRDI QIDQ4586336zbMATH OpenOpenAlexFDO

Authors Dmitry Zaporozhets, Vladislav V. Vysotsky

Publication date 13 September 2018

Published in Transactions of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1506.07827

zbMATH Keywords

average number of facesaverage surface areaconvex hulldistribution-free probabilityintrinsic volumeorthoschemepath-simplexpersistence probabilityrandom polytoperandom walkspherical intrinsic volumeuniform Tauberian theoremWiener spiral

Mathematics Subject Classification ID

(n)-dimensional polytopes (52B11) Geometric probability and stochastic geometry (60D05) Sums of independent random variables; random walks (60G50) Extreme value theory; extremal stochastic processes (60G70)

Abstract: Let $S_k$ be a random walk in $R^d$ such that its distribution of increments does not assign mass to hyperplanes. We study the probability $p_n$ that the convex hull $conv(S_1,ldots,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 $noinfty$ 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 $dge2$. 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 }$ E V_1 (conv(0, S_1, dots, S_n)) = sum_{k=1}^n frac{E |S_k|}{k}, ${\displaystyle }$ 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.

Recommendations

• Convex Hulls of Random Walks
• Convex hulls of random walks, hyperplane arrangements, and Weyl chambers
• The convex hull of a planar random walk: perimeter, diameter, and shape
• Convex hulls of random walks and their scaling limits
• Volumetric properties of the convex hull of an n-dimensional Brownian motion
• Convex hulls of planar random walks with drift
• Mean perimeter and mean area of the convex hull over planar random walks
• scientific article; zbMATH DE number 5019925
• Random points on the boundary of smooth convex bodies

Cites work

• A Combinatorial Lemma for Complex Numbers
• A Geometric Approach to Maximum Likelihood Estimation for Infinite- Dimensional Gaussian Location. II
• A Geometric Approach to Maximum Likelihood Estimation for Infinite-Dimensional Location. III
• A new proof of the absolute convergence of the Spitzer series
• A Problem in Geometric Probability.
• Combinatorial Lemmas in Higher Dimensions
• Convex hulls of Lévy processes
• Convex hulls of planar random walks with drift
• Convex Hulls of Random Walks
• Convex hulls of random walks, hyperplane arrangements, and Weyl chambers
• Convex minorants of random walks and Lévy processes
• Extremal points of high-dimensional random walks and mixing times of a Brownian motion on the sphere
• From Steiner formulas for cones to concentration of intrinsic volumes
• scientific article; zbMATH DE number 5829189 (Why is no real title available?)
• scientific article; zbMATH DE number 3786012 (Why is no real title available?)
• scientific article; zbMATH DE number 3636997 (Why is no real title available?)
• scientific article; zbMATH DE number 1849873 (Why is no real title available?)
• scientific article; zbMATH DE number 3349081 (Why is no real title available?)
• scientific article; zbMATH DE number 3063385 (Why is no real title available?)
• scientific article; zbMATH DE number 3083897 (Why is no real title available?)
• scientific article; zbMATH DE number 3092909 (Why is no real title available?)
• Intrinsic volumes of Sobolev balls with applications to Brownian convex hulls
• Intrinsic volumes of the Brownian motion body
• On the convex hull of symmetric stable processes
• Persistence probabilities and exponents
• Random convex hulls and extreme value statistics
• Random determinants, mixed volumes of ellipsoids, and zeros of Gaussian random fields
• Stochastic and Integral Geometry
• Tauberian Theory
• The Bohnenblust-Spitzer algorithm and its applications
• The Circumference of a Convex Polygon
• The convex minorant of a Lévy process
• Volumetric properties of the convex hull of an n-dimensional Brownian motion
• When does a discrete-time random walk in \(\mathbb{R}^{n}\) absorb the origin into its convex hull?

Cited in

(29)

• Convex rearrangements of random walks
• The Bohnenblust-Spitzer algorithm and its applications
• A multidimensional analogue of the arcsine law for the number of positive terms in a random walk
• The convex hull of a planar random walk: perimeter, diameter, and shape
• On the center of mass of the elephant random walk
• Large deviations of convex hulls of planar random walks and Brownian motions
• Angular asymptotics for random walks
• Convex hulls of stable random walks
• Positive hulls of random walks and bridges
• Random walks avoiding their convex hull with a finite memory
• Convex hulls of random walks, hyperplane arrangements, and Weyl chambers
• Convex hulls of random walks: expected number of faces and face probabilities
• When does a discrete-time random walk in \(\mathbb{R}^{n}\) absorb the origin into its convex hull?
• On the speed of a planar random walk avoiding its past convex hull
• On the convexity of a hitting distribution for discrete random walks
• Properties of uniform random walks in bounded convex bodies
• Dini derivatives and regularity for exchangeable increment processes
• Conical tessellations associated with Weyl chambers
• Convex Hulls of Random Walks
• Random walks in a convex body and an improved volume algorithm
• Multivariate and multiradial Schoenberg measures with their dimension walks
• Multivariate versions of dimension walks and Schoenberg measures
• A Convexity Property of Discrete Random Walks
• Convex hulls of planar random walks with drift
• Convex hulls of several multidimensional Gaussian random walks
• Iterated-logarithm laws for convex hulls of random walks with drift
• Random walks in the high-dimensional limit. I: The Wiener spiral.
• Bounds on some geometric functionals of high dimensional Brownian convex hulls and their inverse processes
• Bounds on the size of the convex hull of planar Brownian motion and related inverse processes

This page was built for publication: Convex hulls of multidimensional random walks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4586336)