Convex hulls of multidimensional random walks
HTML articles powered by AMS MathViewer
- by Vladislav Vysotsky and Dmitry Zaporozhets PDF
- Trans. Amer. Math. Soc. 370 (2018), 7985-8012 Request permission
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 $\operatorname {conv} (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: \begin{equation*} \mathbb E V_1 (\operatorname {conv} (0, S_1, \dots , S_n)) = \sum _{k=1}^n \frac {\mathbb E \|S_k\|}{k}, \end{equation*} 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
- Josh Abramson, Jim Pitman, Nathan Ross, and Gerónimo Uribe Bravo, Convex minorants of random walks and Lévy processes, Electron. Commun. Probab. 16 (2011), 423–434. MR 2831081, DOI 10.1214/ECP.v16-1648
- Frank Aurzada and Thomas Simon, Persistence probabilities and exponents, Lévy matters. V, Lecture Notes in Math., vol. 2149, Springer, Cham, 2015, pp. 183–224. MR 3468226, DOI 10.1007/978-3-319-23138-9_{3}
- O. Barndorff-Nielsen and Glen Baxter, Combinatorial lemmas in higher dimensions, Trans. Amer. Math. Soc. 108 (1963), 313–325. MR 156261, DOI 10.1090/S0002-9947-1963-0156261-1
- Glen Baxter, A combinatorial lemma for complex numbers, Ann. Math. Statist. 32 (1961), 901–904. MR 126290, DOI 10.1214/aoms/1177704985
- A. J. Bray, S. N. Majumdar, and G. Schehr, Persistence and first-passage properties in non-equilibrium systems, Advances in Physics 62 (2013), 225–361.
- Ronen Eldan, Extremal points of high-dimensional random walks and mixing times of a Brownian motion on the sphere, Ann. Inst. Henri Poincaré Probab. Stat. 50 (2014), no. 1, 95–110 (English, with English and French summaries). MR 3161524, DOI 10.1214/12-AIHP515
- Ronen Eldan, Volumetric properties of the convex hull of an $n$-dimensional Brownian motion, Electron. J. Probab. 19 (2014), no. 45, 34. MR 3210546, DOI 10.1214/EJP.v19-2571
- William Feller, An introduction to probability theory and its applications. Vol. II. , 2nd ed., John Wiley & Sons, Inc., New York-London-Sydney, 1971. MR 0270403
- Fuchang Gao, Daniel Hug, and Rolf Schneider, Intrinsic volumes and polar sets in spherical space, Math. Notae 41 (2001/02), 159–176 (2003). Homage to Luis Santaló. Vol. 1 (Spanish). MR 2049442
- F. Gao and R. A. Vitale, Intrinsic volumes of the Brownian motion body, Discrete Comput. Geom. 26 (2001), no. 1, 41–50. MR 1832728, DOI 10.1007/s00454-001-0023-1
- F. Götze, Z. Kabluchko, and D. Zaporozhets, Conic analogues of Sudakov–Tsirelson theorem, in preparation (2016).
- Zakhar Kabluchko, Vladislav Vysotsky, and Dmitry Zaporozhets, Convex hulls of random walks, hyperplane arrangements, and Weyl chambers, Geom. Funct. Anal. 27 (2017), no. 4, 880–918. MR 3678504, DOI 10.1007/s00039-017-0415-x
- D. N. Zaporozhets and Z. Kabluchko, Random determinants, mixed volumes of ellipsoids, and zeros of Gaussian random fields, Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 408 (2012), no. Veroyatnost′i Statistika. 18, 187–196, 327 (Russian, with English and Russian summaries); English transl., J. Math. Sci. (N.Y.) 199 (2014), no. 2, 168–173. MR 3032216, DOI 10.1007/s10958-014-1844-9
- Zakhar Kabluchko and Dmitry Zaporozhets, Intrinsic volumes of Sobolev balls with applications to Brownian convex hulls, Trans. Amer. Math. Soc. 368 (2016), no. 12, 8873–8899. MR 3551592, DOI 10.1090/tran/6628
- Jürgen Kampf, Günter Last, and Ilya Molchanov, On the convex hull of symmetric stable processes, Proc. Amer. Math. Soc. 140 (2012), no. 7, 2527–2535. MR 2898714, DOI 10.1090/S0002-9939-2012-11128-1
- Jacob Korevaar, Tauberian theory, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 329, Springer-Verlag, Berlin, 2004. A century of developments. MR 2073637, DOI 10.1007/978-3-662-10225-1
- Satya N. Majumdar, Alain Comtet, and Julien Randon-Furling, Random convex hulls and extreme value statistics, J. Stat. Phys. 138 (2010), no. 6, 955–1009. MR 2601420, DOI 10.1007/s10955-009-9905-z
- Michael B. McCoy and Joel A. Tropp, From Steiner formulas for cones to concentration of intrinsic volumes, Discrete Comput. Geom. 51 (2014), no. 4, 926–963. MR 3216671, DOI 10.1007/s00454-014-9595-4
- Ilya Molchanov and Florian Wespi, Convex hulls of Lévy processes, Electron. Commun. Probab. 21 (2016), Paper No. 69, 11. MR 3564216, DOI 10.1214/16-ECP19
- S. V. Nagaev, A new proof of the absolute convergence of the Spitzer series, Teor. Veroyatn. Primen. 54 (2009), no. 1, 149–152 (Russian, with Russian summary); English transl., Theory Probab. Appl. 54 (2010), no. 1, 151–154. MR 2766651, DOI 10.1137/S0040585X97984024
- Jim Pitman and Gerónimo Uribe Bravo, The convex minorant of a Lévy process, Ann. Probab. 40 (2012), no. 4, 1636–1674. MR 2978134, DOI 10.1214/11-AOP658
- Luis A. Santaló, Integral geometry and geometric probability, Encyclopedia of Mathematics and its Applications, Vol. 1, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1976. With a foreword by Mark Kac. MR 0433364
- Rolf Schneider and Wolfgang Weil, Stochastic and integral geometry, Probability and its Applications (New York), Springer-Verlag, Berlin, 2008. MR 2455326, DOI 10.1007/978-3-540-78859-1
- Timothy Law Snyder and J. Michael Steele, Convex hulls of random walks, Proc. Amer. Math. Soc. 117 (1993), no. 4, 1165–1173. MR 1169048, DOI 10.1090/S0002-9939-1993-1169048-2
- Erik Sparre Andersen, On the number of positive sums of random variables, Skand. Aktuarietidskr. 32 (1949), 27–36. MR 32115, DOI 10.1080/03461238.1949.10419756
- Erik Sparre Andersen, On sums of symmetrically dependent random variables, Skand. Aktuarietidskr. 36 (1953), 123–138. MR 60173, DOI 10.1080/03461238.1953.10419466
- Erik Sparre Andersen, On the fluctuations of sums of random variables. II, Math. Scand. 2 (1954), 195–223. MR 68154
- 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, The Bohnenblust-Spitzer algorithm and its applications, J. Comput. Appl. Math. 142 (2002), no. 1, 235–249. Probabilistic methods in combinatorics and combinatorial optimization. MR 1910531, DOI 10.1016/S0377-0427(01)00472-1
- V. N. Sudakov, Geometric problems of the theory of infinite-dimensional probability distributions, Trudy Mat. Inst. Steklov. 141 (1976), 191 (Russian). MR 0431359
- Konstantin Tikhomirov and Pierre Youssef, When does a discrete-time random walk in $\Bbb {R}^n$ absorb the origin into its convex hull?, Ann. Probab. 45 (2017), no. 2, 965–1002. MR 3630291, DOI 10.1214/15-AOP1079
- B. S. Tsirel′son, A geometric approach to maximum likelihood estimation for an infinite-dimensional Gaussian location. I, Teor. Veroyatnost. i Primenen. 27 (1982), no. 2, 388–395 (Russian, with English summary). MR 657940
- B. S. Tsirelson, A geometric approach to maximum likelihood estimation for an infinite-dimensional Gaussian location. II, Teor. Veroyatnost. i Primenen. 30 (1985), no. 4, 772–779 (Russian). MR 816291
- B. S. Tsirelson, A geometric approach to maximum likelihood estimation for an infinite-dimensional Gaussian location. III, Teor. Veroyatnost. i Primenen. 31 (1986), no. 3, 537–549 (Russian). MR 866873
- Andrew R. Wade and Chang Xu, Convex hulls of planar random walks with drift, Proc. Amer. Math. Soc. 143 (2015), no. 1, 433–445. MR 3272767, DOI 10.1090/S0002-9939-2014-12239-8
- J. G. Wendel, A problem in geometric probability, Math. Scand. 11 (1962), 109–111. MR 146858, DOI 10.7146/math.scand.a-10655
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
- MR Author ID: 744268
- Email: zap1979@gmail.com
- 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. - © Copyright 2018 American Mathematical Society
- 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
- MathSciNet review: 3852455