Counterbalancing steps at random
in a random walk

In short, the purpose of the present work is to investigate long time effects of an algorithm for counterbalancing steps in a random walk. As we shall first explain, our motivation stems from a nearest neighbor process on the integer lattice, known as the elephant random walk.

The elephant random walk 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. It has been introduced by Schütz and Trimper [31] and triggered a growing interest in the recent years; see, for instance, [4, 5, 15, 16, 22, 23], and also [2, 6, 8, 14, 20, 26] for related models. The dynamics depend on a parameter $q\in[0,1]$ and can be described as follows. Let us assume that the first step of the elephant is a Rademacher variable, that is equals $+1$ or $-1$ with probability $1/2$. 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 $1-q$. Obviously, each step of the elephant has then the Rademacher law, although the sequence of steps is clearly not stationary.

Roughly speaking, it seems natural to generalize these dynamics and allow steps to have an arbitrary distribution on $\mathbb{R}$, say $\mu$. In this direction, Kürsten [23] pointed at an equivalent way of describing the dynamics of the elephant random walk which makes such generalization non trivial²²2 Note that merely replacing the Rademacher distribution for the first step of the elephant by $\mu$ would not be interesting, as one would then just get the evolution of the elephant random walk multiplied by some random factor with law $\mu$.. Let $p\in[0,1]$, and imagine a walker who makes at each time a step which is either, with probability $p$, a new independent random variable with law $\mu$, or, with probability $1-p$, a repetition of one of his preceding steps picked uniformly at random. It is immediately checked that when $\mu$ is the Rademacher distribution, then the walker follows the same dynamics as the elephant random walk with parameter $q=1-p/2$. When $\mu$ is an isotropic stable law, this is the model referred to as the shark random swim by Businger [14], and more generally, when $\mu$ is arbitrary, this is the step reinforced random walk that has been studied lately in e.g. [7, 9, 10, 11].

The model of Kürsten yields an elephant random walk only with parameter $q\in[1/2,1]$; nonetheless the remaining range can be obtained by a simple modification. Indeed, let again $p\in[0,1]$ and imagine now an repentant walker who makes at each time a step which is either, with probability $p$, a new independent random variable with law $\mu$, or, with probability $1-p$, the opposite of one of his previous steps picked uniformly at random. When $\mu$ is the Rademacher distribution, we simply get the dynamics of the elephant random walk with parameter $q=p/2\in[0,1/2]$.

More formally, we consider a sequence $(X_{n})$ of i.i.d. real random variables with some given law $\mu$ and a sequence $(\varepsilon_{n})_{n\geq 2}$ of i.i.d. Bernoulli variables with parameter $p\in[0,1]$, which we assume furthermore independent of $(X_{n})$. We construct 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. Specifically, we agree that $\varepsilon_{1}=1$ for definiteness and denote the number of innovations after $n$ steps by

We introduce a sequence $(v(n))_{n\geq 2}$ of independent variables, where each $v(n)$ has the uniform distribution on $\{1,\ldots,n-1\}$, and which is also independent of $(X_{n})$ and $(\varepsilon_{n})$. We then define recursively

Note that the same step can be counterbalanced several times, and also that certain steps counterbalance previous steps which in turn already counterbalanced earlier ones. The process

which records the positions of the repentant walker as a function of time, is called here a random walk with counterbalanced steps. Note that for $p=1$, i.e. when no counterbalancing events occur, $\check{S}$ is just a usual random walk with i.i.d. steps.

In short, we are interested in understanding how counterbalancing steps affects the asymptotic behavior of random walks. We first introduce some notation. Recall that $\mu$ denotes the distribution of the first step $X_{1}=\check{X}_{1}$ and write

for the moment of order $k\geq 1$ of $X_{1}$ whenever $X_{1}\in L^{k}(\mathbb{P})$. To start with, we point out that if the first moment is finite, then the algorithm (1) yields the recursive equation

with the initial condition $\mathbb{E}(\check{S}(1))=m_{1}$. It follows easily that

see e.g. Lemma 4.1.2 in [18]. Our first result about the ballistic behavior should therefore not come as a surprise.

We see in particular that counterbalancing steps reduces the asymptotic velocity of a random walk by a factor $p/(2-p)<1$. The velocity is smaller when the innovation rate $p$ is smaller (i.e. when counterbalancing events have a higher frequency), and vanishes as $p$ approaches $0+$.

The main purpose of this work is to establish the asymptotic normality when $\mu$ has a finite second moment.

It is interesting to observe that the variance of the Gaussian limit depends linearly on the square $m_{1}^{2}$ of the first moment and the second moment $m_{2}$ of $\mu$ only, although not just on the variance $m_{2}-m_{1}^{2}$ (except, of course, for $p=1$). Furthermore, it is not always a monotonous function³³3 For instance, in the simplest case when $\mu$ is a Dirac point mass, i.e. $m_{2}=m_{1}^{2}$, then the variance is given by $\frac{4(1-p)m_{2}}{(3-2p)(2-p)^{2}}$ and reaches its maximum for $p=(9-\sqrt{17})/8\approx 0.6$. At the opposite, when $\mu$ is centered, i.e. $m_{1}=0$, the variance is given by $m_{2}/(3-2p)$ and hence increases with $p$. of the innovation rate $p$, and does not vanish when $p$ tends to $0$ either.

Actually, our proofs of Proposition 1 and Theorem 1 provide a much finer analysis than what is encapsulated by those general statements. Indeed, we shall identify the main actors for the evolution of $\check{S}$ and their respective contributions to its asymptotic behavior. In short, we shall see that the ballistic behavior stems from those of the variables $X_{j}$ that have been used just once by the algorithm (1) (in particular, they have not yet been counterbalanced), whereas the impact of variables that occurred twice or more regardless of their signs $\pm$, is asymptotically negligible as far as only velocity is concerned. Asymptotic normality is more delicate to analyze. We shall show that, roughly speaking, it results from the combination of, on the one hand, the central limit theorem for certain centered random walks, and on the other hand, Gaussian fluctuations for the asymptotic frequencies of some pattern induced by (1).

Our analysis relies on a natural coupling of the counterbalancing algorithm (1) with a basic linear reinforcement algorithm which has been introduced a long time ago by H.A. Simon [32] to explain the occurrence of certain heavy tailed distributions in a variety of empirical data. Specifically, Simon defined recursively a sequence denoted here by $(\hat{X}_{n})$ (beware of the difference of notation between $\hat{X}$ and $\check{X}$) via

We stress that the same Bernoulli variables $\varepsilon_{n}$ and the same uniform variables $v(n)$ are used to run both Simon’s algorithm (2) and (1); in particular either $\check{X}_{n}=\hat{X}_{n}$ or $\check{X}_{n}=-\hat{X}_{n}$. It might then seem natural to refer to (1) and (2) respectively as negative and positive reinforcement algorithms. However, in the literature, negative reinforcement usually refers to a somehow different notion (see e.g. [29]), and we shall thus avoid using this terminology.

A key observation is that (1) can be recovered from (2) as follows. Simon’s algorithm naturally encodes a genealogical forest with set of vertices $\mathbb{N}=\{1,2,\ldots,\}$ and edges $(v(j),j)$ for all $j\geq 2$ with $\varepsilon_{j}=0$; see the forthcoming Figure 1. Then $\check{X}_{n}=\hat{X}_{n}$ if the vertex $n$ belongs to an even generation of its tree component, and $\check{X}_{n}=-\hat{X}_{n}$ if $n$ belongs to an odd generation. On the other hand, the statistics of Simon’s genealogical forest can be described in terms of independent random recursive trees (see e.g. Chapter 6 in [17] for background) conditionally on their sizes. This leads us to investigate the difference $\Delta(\mathbb{T}_{k})$ between the number of vertices at even generations and the number of vertices at odd generations in a random recursive tree $\mathbb{T}_{k}$ of size $k\geq 1$. The law of $\Delta(\mathbb{T}_{k})$ can be expressed in terms of Eulerian numbers, and properties of the latter enable us either to compute explicitly or estimate certain quantities which are crucial for the proofs of Proposition 1 and Theorem 1.

It is interesting to compare asymptotic behaviors for counterbalanced steps with those for reinforced steps. If we write $\hat{S}(n)=\hat{X}_{1}+\cdots+\hat{X}_{n}$ for the random walk with reinforced steps, then it is known that the law of large numbers holds for $\hat{S}$, namely $\hat{S}(n)/n\to m_{1}$ in $L^{1}$ when $\int_{\mathbb{R}}|x|\mu(\mathrm{d}x)<\infty$, independently of the innovation parameter $p$. Further, regarding fluctuations when $\int_{\mathbb{R}}|x|^{2}\mu(\mathrm{d}x)<\infty$, a phase transition occurs for the critical parameter $p_{c}=1/2$, in the sense that $\hat{S}$ is diffusive for $p>1/2$ and superdiffusive for $p<1/2$; see [10, 11]. Despite of the natural coupling between (1) and (2), there are thus major differences⁴⁴4 This should not come as a surprise. In the simplest case when $\mu=\delta_{1}$ is the Dirac mass at $1$, one has $\hat{S}(n)\equiv n$ whereas $\check{S}$ is a truly stochastic process, even for $p=0$ when there is no innovation. between the asymptotic behaviors of $\check{S}$ and of $\hat{S}$: Proposition 1 shows that the asymptotic speed of $\check{S}$ depends on $p$, and Theorem 1 that there is no such phase transition for counterbalanced steps and $\check{S}$ is always diffusive.

The phase transition for step reinforcement when $\mu$ has a finite second moment can be explained informally as follows; for the sake of simplicity, suppose also that $\mu$ is centered, i.e. $m_{1}=0$. There are $\mathrm{i}(n)\sim pn$ trees in Simon’s genealogical forest, which are overwhelmingly microscopic (i.e. of size $O(1)$), whereas only a few trees reach the size $O(n^{1-p})$. Because $\mu$ is centered, the contribution of microscopic trees to $\hat{S}(n)$ is of order $\sqrt{n}$, and that of the few largest trees of order $n^{1-p}$. This is the reason why $\hat{S}(n)$ grows like $\sqrt{n}\gg n^{1-p}$ when $p>1/2$, and rather like $n^{1-p}\gg\sqrt{n}$ when $p<1/2$. For counterbalanced steps, we will see that, due to the counterbalancing mechanism, the contribution of a large tree with size $\ell\gg 1$ is now only of order $\sqrt{\ell}$. As a consequence, the contribution to $\check{S}(n)$ of the largest trees of Simon’s genealogical forest is only of order $O(n^{(1-p)/2})$. This is always much smaller than the contribution of microscopic trees which remain of order $\sqrt{n}$. We further stress that, even though only the sizes of the trees in Simon’s genealogical forest are relevant for the analysis of the random walk $\hat{S}$ with reinforced steps, the study of the random walk $\check{S}$ with counterbalanced steps is more complex and requires informations on the fine structure of those trees, not merely their sizes.

The rest of this text is organized as follows. Section 2 focusses on the purely counterbalanced case $p=0$. In this situation, for each fixed $n\geq 1$, the distribution of $\check{S}(n)$ can be expressed explicitly in terms of Eulerian numbers. Section 3 is devoted to the coupling between the counterbalancing algorithm (1) and H.A. Simon’s algorithm (2), and to the interpretation of the former in terms of a forest of random recursive trees induced by the latter. Proposition 1 and Theorem 1 are proved in Section 4, where we analyze more finely the respective contributions of some natural sub-families. Last, in Section 5, we present a stable version of Theorem 1 when $\mu$ belongs to the domain of attraction (without centering) of an $\alpha$-stable distribution for some $\alpha\in(0,2)$.

This section is devoted to the simpler situation⁵⁵5 Observe that this case without innovation has been excluded in Theorem 1. when $p=0$. So $\varepsilon_{n}\equiv 0$ for all $n\geq 2$, meaning that every step, except of course the first one, counterbalances some preceding step. The law $\mu$ then only plays a superficial role as it is merely relevant for the first step. For the sake of simplicity, we further focus on the case when $\mu=\delta_{1}$ is the Dirac mass at $1$.

The dynamics are entirely encoded by the sequence $(v(n))_{n\geq 2}$ of independent uniform variables on $\{1,\ldots,n-1\}$; more precisely the purely counterbalanced sequence of bits is given by

The random algorithm (3) points at a convenient representation in terms of random recursive trees. Specifically, the sequence $(v(n))_{n\geq 2}$ encodes a random tree ${\mathbb{T}}_{\infty}$ with set of vertices $\mathbb{N}$ and set of edges $\{(v(n),n):n\geq 2\}$. Roughly speaking, ${\mathbb{T}}_{\infty}$ is constructed recursively by incorporating vertices one after the other and creating an edge between each new vertex $n$ and its parent $v(n)$ which is picked uniformly at random in $\{1,\ldots,n-1\}$ and independently of the other vertices. If we view $1$ as the root of ${\mathbb{T}}_{\infty}$ and call a vertex $j$ odd (respectively, even) when its generation (i.e. its distance to the root in ${\mathbb{T}}_{\infty}$) is an odd (respectively, even) number, then

Let us now introduce some notation with that respect. For every $n\geq 1$, we write ${\mathbb{T}}_{n}$ for the restriction of ${\mathbb{T}}_{\infty}$ to the set of vertices $\{1,\ldots,n\}$ and refer to ${\mathbb{T}}_{n}$ as a random recursive tree with size $n$. We also write $\mathrm{Odd}({\mathbb{T}}_{n})$ (respectively, $\mathrm{Even}({\mathbb{T}}_{n})$) for the number of odd (respectively, even) vertices in ${\mathbb{T}}_{n}$ and set

Of course, we can also express

which is the trajectory of an elephant full of regrets (i.e. for the parameter $q=0$).

The main observation of this section is that law of the number of odd vertices is readily expressed in terms of the Eulerian numbers. Recall that $\langle{}^{n}_{k}\rangle$ denotes the number of permutations $\varsigma$ of $\{1,\ldots,n\}$ with $k$ descents, i.e. such that $\#\{1\leq j<n:\varsigma(j)>\varsigma(j+1)\}=k$. Obviously $\langle{}^{n}_{k}\rangle\geq 1$ if and only if $0\leq k<n$, and one has

The linear recurrence equation

is easily derived from a recursive construction of permutations (see Theorem 1.3 in [30]); we also mention the explicit formula (see Corollary 1.3 in [30])

We next point at a useful identity related to Lemma 2 which goes back to Laplace (see Exercise 51 of Chapter I in Stanley [33]) and is often attributed to Tanny [34]. For every $n\geq 0$, there is the identity in distribution

where in the right-hand side, $U_{1},U_{2},\ldots$ is a sequence of i.i.d. uniform variables on $[0,1]$ and $\lceil\cdot\rceil$ denotes the ceiling function. We now record for future use the following consequences.

We now conclude this section with an application of (5) to the asymptotic normality of $\Delta({\mathbb{T}}_{n})$. Since $\mathbb{E}(U)=1/2$ and $\mathrm{Var}(U)=1/12$, the classical central limit theorem immediately yields the following.

Corollary 2 goes back to [27] in the setting of the number of leaves in random recursive trees; see also [4, 5, 15, 16] for alternative proofs in the framework of the elephant random walk.

From now on, $\mu$ is an arbitrary probability law on $\mathbb{R}$ and we also suppose that the innovation rate is strictly positive, $p\in(0,1)$. Recall the construction of the sequence $(\hat{X}_{n})$ from Simon’s reinforcement algorithm (2). Simon was interested in the asymptotic frequencies of variables having a given number of occurrences. Specifically, for every $n,j\in\mathbb{N}$, we write

for the number of occurrences of the variable $X_{j}$ until the $n$-th step of the algorithm (2), and

for the number of such variables that have occurred exactly $k$ times. Observe also that the number of innovations satisfies the law of large numbers ${\mathrm{i}}(n)\sim pn$ a.s.

Lemma 3 is essentially due to H.A. Simon [32], who actually only established the convergence of the mean value. The strengthening to convergence in probability can be obtained as in [13] from a concentration argument based on the Azuma-Hoeffding’s inequality; see Section 3.1 in [28]. The right-hand side in the formula is a probability mass on $\mathbb{N}$ known as the Yule-Simon distribution with parameter $1/(1-p)$. We record for future use a couple of identities which are easily checked from the integral definition of the beta function:

and

For $k=1$, Lemma 3 reads

We shall also need to estimate the fluctuations, which can be derived by specializing a Gaussian limit theorem for extended Pólya urns due to Bai et al. [1].

We shall also need a refinement of Lemma 3 in which one does not only record the number of occurrences of the variable $X_{j}$, but more generally the genealogical structure of these occurrences. We need to introduce first some notation in that respect.

Fix $n\geq 1$ and let some $1\leq j\leq{\mathrm{i}}(n)$ (i.e. the variable $X_{j}$ has already appeared at the $n$-th step of the algorithm). Write $\ell_{1}<\ldots<\ell_{k}\leq n$ for the increasing sequence of steps of the algorithm at which $X_{j}$ appears, where $k={N}_{j}(n)\geq 1$. The genealogy of occurrences of the variable $X_{j}$ until the $n$-th step is recorded as a tree $T_{j}(n)$ on $\{1,\ldots,k\}$ such that for every $1\leq a<b\leq k$, $(a,b)$ is an edge of $T_{j}(n)$ if and only if $v(\ell_{b})=\ell_{a}$, that is, if and only if the identity $\hat{X}_{\ell_{b}}=X_{j}$ actually results from the fact that the algorithm repeats the variable $\hat{X}_{\ell_{a}}$ at its $\ell_{b}$-th step. Plainly, $T_{j}(n)$ is an increasing tree with size $k$, meaning a tree on $\{1,\ldots,k\}$ such that the sequence of vertices along any branch from the root $1$ to a leaf is increasing. In this direction, we recall that there are $(k-1)!$ increasing trees with size $k$ and that the uniform distribution of the set increasing trees with size $k$ coincides with the law of the random recursive tree of size $k$, ${\mathbb{T}}_{k}$. See for instance Section 1.3.1 in Drmota [17].

More generally, the distribution of the entire genealogical forest given the sizes of the genealogical trees can be described as follows.

We shall also need for the proofs of Proposition 1 and Theorem 1 an argument of uniform integrability that relies in turn on the following lemma. Recall that if $T$ is a rooted tree, $\Delta(T)$ denotes the difference between the number of vertices at even distance from root and that at odd distance.

As its title indicates, the purpose of this section is to establish Proposition 1 and Theorem 1. The observation that for every $n\geq 1$ and $1\leq j\leq{{\mathrm{i}}(n)}$, the variable $X_{j}$ appears exactly $\mathrm{Even}(T_{j}(n))$ times and its opposite $-X_{j}$ exactly $\mathrm{Odd}(T_{j}(n))$ times until the $n$-step of the algorithm (1), yields the identity

which lies at the heart of our approach. We stress that in (10) as well as in related expressions that we shall use in the sequel, the sequence of i.i.d. variables $(X_{n})$ and the family of genealogical trees $(T_{j}(n))$ are independent, because the latter are constructed from the sequences $(\varepsilon_{n})$ and $(v(n))$ only.

Actually, our proof analyzes more precisely the effects of the counterbalancing algorithm (1) by estimating specifically the contributions of certain sub-families to the asymptotic behavior of $\check{S}$. Specifically, we set for every $k\geq 1$,

so that