WHEN DOES A DISCRETE-TIME RANDOM WALK IN Rn ABSORB THE ORIGIN INTO ITS CONVEX HULL?

• 成果类型: Article
• 署名作者: Tikhomirov, Konstantin; Youssef, Pierre
• 署名单位: University of Alberta
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/15-AOP1079
• 发表日期: 2017
• 页码: 965-1002
• 关键词: random subspaces; brownian-motion; inequalities; sections; bodies; SPACES; sphere

摘要

We connect this question to a problem of estimating the probability that the image of certain random matrices does not intersect with a subset of the unit sphere Sn-1. In this way, the case of a discretized Brownian motion is related to Gordon's escape theorem dealing with standard Gaussian matrices. We show that for the random walk BMn(i), i is an element of N, the convex hull of the first C-n steps (for a sufficiently large universal constant C) contains the origin with probability close to one. Moreover, the approach allows us to prove that with high probability the pi/2-covering time of certain random walks on Sn-1 is of order n. For certain spherical simplices on Sn-1, we prove an extension of Gordon's theorem dealing with a broad class of random matrices; as an application, we show that C-n steps are sufficient for the standard walk on Z(n) to absorb the origin into its convex hull with a high probability. Finally, we prove that the aforementioned bound is sharp in the following sense: for some universal constant c > 1, the convex hull of the n-dimensional Brownian motion conv{BMn(t) : t is an element of [1, c(n)]} does not contain the origin with probability close to one.