When does a discrete-time random walk in ℝn absorb the origin into its convex hull?

Konstantin Tikhomirov, Pierre Youssef

Research output: Contribution to journalArticlepeer-review

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 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 ∈ N, the convex hull of the first Cn 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 π/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 Cn steps are sufficient for the standard walk on ℤ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 ∈ [1, cn]) does not contain the origin with probability close to one.

Original languageEnglish (US)
Pages (from-to)965-1002
Number of pages38
JournalAnnals of Probability
Volume45
Issue number2
DOIs
StatePublished - Mar 1 2017

Keywords

  • Convex hull
  • Covering time
  • Random walk

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Fingerprint

Dive into the research topics of 'When does a discrete-time random walk in ℝn absorb the origin into its convex hull?'. Together they form a unique fingerprint.

Cite this