Absorption probabilities of random walks without symmetry or general position

Source abstract

Let $S_1,S_2,\dots$ be a random walk in $\mathbb R^d$ with independent identically distributed increments. We show that, for every distribution of the increments and for every $n\ge1$, $$\mathbb P\bigl[0\notin\mathrm{conv}(S_1,\dots,S_n)\bigr] = \sum_{m=1}^n\frac1{m!}\sum_{\substack{k_1,\dots,k_m\ge1\\ k_1+\dots+k_m=n}}\frac{1}{k_1\cdots k_m}\,\mathbb P\bigl[0\notin\mathrm{conv}(S^{(1)}_{k_1},\dots,S^{(m)}_{k_m})\bigr],$$ where $S^{(1)},S^{(2)},\dots$ are independent copies of the walk. No symmetry, general position or moment assumptions are needed. The result rests on a deterministic identity: for arbitrary vectors $x_1,\dots,x_n$, the number of orderings for which the convex hull of the partial sums avoids the origin equals the number of permutations for which the convex hull of the cycle sums avoids it. We derive it from a permutation-averaging identity for valuations obtained in our earlier work. Consequences include the identities of Sparre Andersen and Spitzer, the distribution-free absorption probabilities of Kabluchko, Vysotsky and Zaporozhets, their generating function found by Petrov, Randon-Furling and Zaporozhets, and a formula for the probability that the origin is never absorbed.