Kabluchko, Zakhar, Vysotsky, Vladislav and Zaporozhets, Dmitry (2017) Convex hulls of random walks: expected number of faces and face probabilities. Advances in Mathematics, 320. pp. 595-629. ISSN 0001-8708

PDF - Accepted Version Available under License Creative Commons Attribution-NonCommercial No Derivatives. Download (472kB)

Abstract

Consider a sequence of partial sums Si=ξ1+…+ξi, 1≤i≤n, starting at S0=0, whose increments ξ1,…,ξn are random vectors in Rd, d≤n. We are interested in the properties of the convex hull Cn:=Conv(S0,S1,…,Sn). Assuming that the tuple (ξ1,…,ξn) is exchangeable and a certain general position condition holds, we prove that the expected number of k-dimensional faces of Cn is given by the formula

E[fk(Cn)]=2⋅k!n!∑l=0∞[n+1d−2l]{d−2lk+1},

for all 0≤k≤d−1, where [nm] and {nm} are Stirling numbers of the first and second kind, respectively.

Further, we compute explicitly the probability that for given indices 0≤i1<…<ik+1≤n, the points Si1,…,Sik+1 form a k-dimensional face of Conv(S0,S1,…,Sn). This is done in two different settings: for random walks with symmetrically exchangeable increments and for random bridges with exchangeable increments. These results generalize the classical one-dimensional discrete arcsine law for the position of the maximum due to E. Sparre Andersen. All our formulae are distribution-free, that is do not depend on the distribution of the increments ξk's.

The main ingredient in the proof is the computation of the probability that the origin is absorbed by a joint convex hull of several random walks and bridges whose increments are invariant with respect to the action of direct product of finitely many reflection groups of types An−1 and Bn. This probability, in turn, is related to the number of Weyl chambers of a product-type reflection group that are intersected by a linear subspace in general position.

Item Type:	Article
Keywords:	convex hull, random walk, random walk bridge, absorption probability, distribution-free probability, exchangeability, hyperplane arrangement, Whitney's formula, Zaslavsky's theorem, characteristic polynomial, Weyl chamber, finite reflection group, convex cone, Wendel's formula, random polytope, average number of faces, average number of vertices, discrete arcsine law
Schools and Departments:	School of Mathematical and Physical Sciences > Mathematics
Depositing User:	Vladislav Vysotskiy
Date Deposited:	20 Nov 2017 14:23
Last Modified:	15 Mar 2021 17:07
URI:	http://sro.sussex.ac.uk/id/eprint/71425

View download statistics for this item

📧 Request an update