Counterbalancing steps at random in a random walk

A random walk with counterbalanced steps is a process of partial sums S-(SIC)(n)=X-1((SIC))+& ctdot;+X-n((SIC)) whose steps X-n((SIC)) are given recursively as follows. For each n >= 2, with a fixed probability p, X-n((SIC)) is a new independent sample from some fixed law mu, and with complementary probability 1-p, X-n((SIC))=-X-v(n)((SIC)) counterbalances a previous step, with v(n) a uniform random pick from {1,& mldr;,n-1}. We determine the asymptotic behavior of S-(SIC)(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.