When does a discrete-time random walk in ${\mathbb{R}}^n$ absorb the origin into its convex hull?

Abstract

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. 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 extend the "escape" phenomenon to a broad class of random matrices; as an application, we show that $e^{Cn}$ steps are sufficient for the standard walk on ${\mathbb{Z}}^n$ to absorb the origin into its convex hull with a high probability.

Added the matching bound contained in the paper Minimax of an n-dimension Brownian motion which is withdrawn