Convex hulls of random walks: Expected number of faces and face probabilities

Consider a sequence of partial sums $S_i={\xi }_1+\cdots +{\xi }_i$, $1\leq i\leq n$,startingat$S_0=0$,whoseincrements$\xi_1,\dots,\xi_n$ are random vectors in ${\mathbb{R}}^d$, $d\le n$. We are interested in the properties of the convex hull $C_n:=\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}(S_0,S_1,\dots ,S_n)$. Assuming that the tuple $({\xi }_1,\dots ,{\xi }_n)$ is exchangeable and a certain general position condition holds, we prove that the expected number of $k$-dimensional faces of $C_n$ is given by the formula $$\mathbb{E}[f_k(C_n)]=\frac{2\cdot k!}{n!}\sum _{l=0}^{\mathrm{\infty }}\left[\genfrac{}{}{0px}{}{n+1}{d-2l}\right]\left\{\genfrac{}{}{0px}{}{d-2l}{k+1}\right\},$$ for all $0\le k\le d-1$, where $\left[\genfrac{}{}{0px}{}{n}{m}\right]$ and $\left\{\genfrac{}{}{0px}{}{n}{m}\right\}$ are Stirling numbers of the first and second kind, respectively. Further, we compute explicitly the probability that for given indices $0\leq i_1<\dots <i_{k+1}\leq n$,thepoints$S_{i_1},\dots,S_{i_{k+1}}$forma$k$-dimensionalfaceof$$\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}$(S_0,S_1,\dots,S_n)$. 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 ${\xi }_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 $A_{n-1}$ and $B_n$. 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.