Counterbalancing steps at random in a random walk

Abstract

A random walk with counterbalanced steps is a process of partial sums $\check{S}(n)={\check{X}}_1+\cdots +{\check{X}}_n$ whose steps ${\check{X}}_n$ are given recursively as follows. For each $n\ge 2$, with a fixed probability $p$, ${\check{X}}_n$ is a new independent sample from some fixed law $\mu$, and with complementary probability $1-p$, ${\check{X}}_n=-{\check{X}}_{v(n)}$ counterbalances a previous step, with $v(n)$ a uniform random pick from $\{1,\dots ,n-1\}$. We determine the asymptotic behavior of $\check{S}(n)$ in terms of $p$ and the first two moments of $\mu$. Our approach relies on a coupling with a reinforcement algorithm due to H. A. Simon, and on properties of random recursive trees and Eulerian numbers, which may be of independent interest. The method can be adapted to the situation where the step distribution $\mu$ belongs to the domain of attraction of a stable law.