×

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
PDF BibTeX XML Cite
Full Text: DOI Euclid arXiv