# zbMATH — the first resource for mathematics

When does a discrete-time random walk in $$\mathbb{R}^{n}$$ absorb the origin into its convex hull? (English) Zbl 1377.52008
Summary: 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 $$\mathbb{S}^{n-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 $$\text{BM}_{n}(i),i\in\mathbb{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 $$\mathbb{S}^{n-1}$$ is of order $$n$$. For certain spherical simplices on $$\mathbb{S}^{n-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 $$\mathbb{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 $$\mathrm{conv}\{\mathrm{BM}_{n}(t):t\in[1,c^{n}]\}$$ does not contain the origin with probability close to one.

##### MSC:
 52A22 Random convex sets and integral geometry (aspects of convex geometry) 60J05 Discrete-time Markov processes on general state spaces 60J65 Brownian motion 60G50 Sums of independent random variables; random walks
##### Keywords:
convex hull; random walk; covering time
Full Text: