Counterbalancing steps at random in a random walk (Q6566417)

The purpose of the present paper is to investigate long time effects of an algorithm for counterbalancing steps in a random walk. The motivation stems from a nearest neighbor process on the integer lattice, known as the elephant random walk. It is a stochastic process with memory on \(\mathbb{Z}\), which records the trajectory of an elephant that makes steps with unit length left or right at each positive integer time. The first step of the elephant is a Rademacher variable. For each time \(n\geq 2\), the elephant remembers a step picked uniformly at random among those it made previously, and decides either to repeat it with probability \(q\), or to make the opposite step with complementary probability. Obviously, each step of the elephant then has the Rademacher law, although the sequence of steps is clearly not stationary. This process triggered a growing interest in the recent years. Roughly speaking, the author considers a following generalization of the trajectory of an elephant: he introduces a sequence \((X_n)\) of i.i.d. real random variables with some given law \(\mu\) and a sequence \((\varepsilon_n, n\ge 2)\) of i.i.d. Bernoulli variables with parameter \(p\in[0,1]\), which is assumed to be independent of \((X_n)\). Then he constructs a counterbalanced sequence \((\check{X}_n)\) by interpreting each \(\{\varepsilon_n=0\}\) as a counterbalancing event and each \(\{\varepsilon_n=1\}\) as an innovation event. A random walk with counterbalanced steps is a process of partial sums \(\check{S}_n=\check{X}_1+\ldots+\check{X}_n\). The asymptotic behavior of \(\check{S}_n\) in terms of \(p\) and the first two moments of \(\mu\) is determined. The approach relies on a coupling with a reinforcement algorithm, 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.