University of Sussex
Browse
GAFA final text.pdf (839.46 kB)

Convex hulls of random walks, hyperplane arrangements, and Weyl chambers

Download (839.46 kB)
journal contribution
posted on 2023-06-09, 07:17 authored by Zakhar Kabluchko, Vladislav VysotskiyVladislav Vysotskiy, Dmitry Zaporozhets
We give an explicit formula for the probability that the convex hull of an n-step random walk in Rd does not contain the origin, under the assumption that the distribution of increments of the walk is centrally symmetric and puts no mass on affine hyperplanes. This extends the formula by Sparre Andersen (Skand Aktuarietidskr 32:27–36, 1949) for the probability that such random walk in dimension one stays positive. Our result is distribution-free, that is, the probability does not depend on the distribution of increments. This probabilistic problem is shown to be equivalent to either of the two geometric ones: (1) Find the number of Weyl chambers of type Bn intersected by a generic linear subspace of Rn of codimension d; (2) Find the conic intrinsic volumes of a Weyl chamber of type Bn. We solve the first geometric problem using the theory of hyperplane arrangements. A by-product of our method is a new simple proof of the general formula by Klivans and Swartz (Discrete Comput Geom 46(3):417–426, 2011) relating the coefficients of the characteristic polynomial of a linear hyperplane arrangement to the conic intrinsic volumes of the chambers constituting its complement. We obtain analogous distribution-free results for Weyl chambers of type An-1 (yielding the probability of absorption of the origin by the convex hull of a generic random walk bridge), type Dn, and direct products of Weyl chambers (yielding the absorption probability for the joint convex hull of several random walks or bridges). The simplest case of products of the form B1 ×···× B1 recovers the Wendel formula (Math Scand 11:109–111, 1962) for the probability that the convex hull of an i.i.d. multidimensional sample chosen from a centrally symmetric distribution does not contain the origin. We also give an asymptotic analysis of the obtained absorption probabilities as n ? 8, in both cases of fixed and increasing dimension d.

History

Publication status

  • Published

File Version

  • Published version

Journal

Geometric and Functional Analysis

ISSN

1016-443X

Publisher

Springer Verlag

Issue

4

Volume

27

Page range

880-918

Department affiliated with

  • Mathematics Publications

Full text available

  • Yes

Peer reviewed?

  • Yes

Legacy Posted Date

2017-07-20

First Open Access (FOA) Date

2017-07-20

First Compliant Deposit (FCD) Date

2017-07-20

Usage metrics

    University of Sussex (Publications)

    Categories

    No categories selected

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC