{
  "id": "1506.07827",
  "version": "v1",
  "published": "2015-06-25T17:26:19.000Z",
  "updated": "2015-06-25T17:26:19.000Z",
  "title": "Convex hulls of multidimensional random walks",
  "authors": [
    "Vladislav Vysotsky",
    "Dmitry Zaporozhets"
  ],
  "categories": [
    "math.PR"
  ],
  "abstract": "Consider the convex hull of the first $n$ steps of a random walk $S_k$ in $\\mathbb R^d$. We show that for planar symmetric random walks, the probability $p_n$ that the hull does not include the origin does not depend on the distribution of increments of $S_k$. This extends the well known result by Sparre Andersen that the probability that a one-dimensional symmetric walk stays positive is distribution-free. We used the developed approach to obtain general results on geometric properties of convex hulls of random walks in any dimension. In particular, we give formulas for expected number of faces, volume, surface area, and other intrinsic volumes, including a multidimensional generalization of the Spitzer-Widom formula (1961): It holds that $$ \\mathbb E V_1 (conv(0, S_1, \\dots, S_n)) = \\sum_{i=1}^n \\frac{\\mathbb E|S_i|}{i}, $$ where $V_1$ denotes the first intrinsic volume, which up to a factor equals the mean width. Our method also works for convex hulls of random walk bridges and more general, for partial sums of exchangeable random vectors. As an application to geometry, these results imply the formula by Gao and Vitale [$Discrete \\, Comput. Geom.$ 26 (2001)] for intrinsic volumes of special path-simplexes (canonic orthoschemes), which they used to find intrinsic volumes of the convex hull of a Wiener spiral. The present paper was to a certain extent motivated by a direct connection between $spherical$ intrinsic volumes of these simplexes and the probabilities $p_n$ discussed above.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-06-25T17:26:19.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60D05",
      "60G50",
      "60G70",
      "52B11"
    ],
    "keywords": [
      "convex hull",
      "multidimensional random walks",
      "intrinsic volume",
      "planar symmetric random walks",
      "one-dimensional symmetric walk stays positive"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv150607827V"
    }
  }
}