Comptes Rendus
Mathématique

Nicolas Curien and Lucile Laulin

Recurrence of the plane Elephant random walk

Volume 362 (2024), p. 1183-1188

Online since: 5 November 2024

https://doi.org/10.5802/crmath.620

<figure><img src="image_1.png" /></figure>

This article is licensed under the

CREATIVE COMMONS ATTRIBUTION 4.0 INTERNATIONAL LICENSE.

http://creativecommons.org/licenses/by/4.0/
Research article / *Article de recherche*
Probability theory / *Probabilités*

# Recurrence of the plane Elephant random walk

## Récurrence de la marche aléatoire de l'éléphant dans le plan

Nicolas Curien<sup>a</sup> and Lucile Laulin<sup>*</sup>,<sup>●, b</sup>

<sup>a</sup> Laboratoire de mathématiques d'Orsay - UMR CNRS 8628, Université Paris-Saclay,
91405 Orsay, France

<sup>b</sup> Modal'X - UMR CNRS 9023, Université Paris Nanterre, 92000 Nanterre, France

E-mails: nicolas.curien@gmail.com, lucile.laulin@math.cnrs.fr

**Abstract.** We give a short proof of the recurrence of the two-dimensional elephant random walk in the diffusive regime. This was recently established by Qin (2023), but our proof mainly uses very rough comparison with the standard plane random walk. We hope that the method can be useful for other applications.

**Résumé.** Nous donnons une preuve courte de la récurrence de la marche aléatoire de l'éléphant dans le plan dans le régime diffusif. Cela a récemment été établi par Shuo Qin, mais notre preuve ne repose que sur une comparaison avec la marche aléatoire simple dans le plan. Nous espérons que cette méthode puisse être utile pour d'autres applications.

**Keywords.** Elephant random walk, recurrence of random walk, martingales.

**Mots-clés.** Marche aléatoire de l'éléphant, Récurrence de la marche aléatoire, Martingales.

**2020 Mathematics Subject Classification.** 60G50, 60G42, 60J10, 82C41.

Manuscript received 23 October 2023, accepted 30 January 2024.

## 1. Introduction

The elephant random walk on $Z^d$ has been introduced in dimension 1 by Schütz and Trimper [6] and is a well-studied discrete process with reinforcement, see [3] for background and references. Its definition (see (2.1)) depends on a memory parameter $\alpha \in (-\frac{1}{2d-1}, 1)$ and it exhibits a phase transition going from a diffusive when $\alpha < \alpha_c = \frac{1}{2}$ to a superdiffusive behavior when $\alpha > \alpha_c$. We focus here on the two-dimensional case and establish recurrence of the process in the diffusive regime.

**Theorem 1.** In the diffusive regime $\alpha < \alpha_c = \frac{1}{2}$, the plane elephant random walk is recurrent.

<footnote>*Corresponding author</footnote>

<footnote n="1">¹The usual definition uses a memory parameter $p \in [0, 1]$ which is the probability to reproduce a (uniform) former step of the walk, or to move in one of the 3 remaining directions with the same probability $(1-p)/3$ so that $\alpha = (4p-1)/3$, see [3, Equation (1.4)].</footnote>
This has been recently proved by Qin [5] but our approach is different and much shorter, however it gives less quantitative information and does not directly apply in the critical regime $\alpha = \alpha_c$. We use a comparison to the simple random walk which could apply in dimension 1 as well since the simple random walk is also recurrent in that case.

It is worth pointing out that [5] established that the elephant random walk is always transient when $d \ge 3$, similar to the simple random walk.

**Notation.** We write $\mathbf{e}_i$ the four directions of $\mathbb{Z}^2$ for $1 \le i \le 4$. We shall write $(X_k : k \ge 0)$ for the canonical underlying process starting from $\mathbf{0} := (0,0) \in \mathbb{Z}^2$, we denote its steps by $\Delta X_k = X_{k+1} - X_k \in \{\mathbf{e}_1, \mathbf{e}_2, \mathbf{e}_3, \mathbf{e}_4\}$ and we introduce for $1 \le i \le 4$ the centered counting direction processes $D_k^{[X]}(\mathbf{e}_i)$ defined by

$$D_k^{[X]}(\mathbf{e}_i) = \sum_{j=0}^{k-1} \mathbf{1}_{\{X_{j+1}-X_j=\mathbf{e}_i\}} - \frac{k}{4}, \quad \text{in particular notice that} \quad \sum_{i=1}^{4} D_n^{[X]}(\mathbf{e}_i) = 0. \quad (1.1)$$

For any stopping time $\theta$, we denote by $X^{(\theta)}$ the shifted process $X_k^{(\theta)} = X_{\theta+k} - X_{\theta}$ for $k \ge 0$. Finally $\mathcal{F}_n$ is the canonical filtration generated by the first $n$ steps of the walk and we use $X_{[0,n]}$ as a shorthand for $(X_k : 0 \le k \le n)$.

## 2. Comparison between elephant and simple random walk

Under the law $\mathbb{P}_{\#}$ the underlying process $(X)$ evolves as the standard simple random walk on $\mathbb{Z}^2$, whereas under $\mathbb{P}_{\#}$, it evolves as the $\alpha$-elephant random walk i.e. satisfying for $n \ge 0$,

$$\mathbb{P}_{\#}(\Delta X_n = \mathbf{e}_i | \mathcal{F}_n) = \frac{1}{4} + \alpha \frac{D_n^{[X]}(\mathbf{e}_i)}{n}, \quad (2.1)$$

(where we interpret $0/0 = 0$ for $n = 0$). In particular, under $\mathbb{P}_{\#}$, the process $(D_n^{[X]}(\mathbf{e}_i) : 1 \le i \le 4, k \ge 0)$ is Markov and evolves as an urn process with four colors, which was crucially used in [1] to establish the phase transition diffusive/superdiffusive. The local evolution of the elephant random walk (for large times) resembles that of the simple random walk and this is quantified in the following proposition:

**Proposition 2 (Markov contiguity).** For any $\varepsilon > 0$ and any $A > 0$, there exist $c_{\varepsilon,A} > 0$ and a sequence of events $E_n$ satisfying $\liminf_{n \to \infty} \mathbb{P}_{\#}(X_{[0,n]} \in E_n) \ge 1 - \varepsilon$ such that for any measurable function $f$,

$$\mathbb{E}_{\#} \left[ f(X_{[0,n]}^{(n)}) \mathbf{1}_{X_{[0,n]}^{(n)} \in E_n} \left| \mathcal{F}_n \text{ and } \frac{|D_n^{[X]}(\mathbf{e}_i)|}{\sqrt{n}} \le A \text{ for all } 1 \le i \le 4 \right. \right] \ge c_{\varepsilon,A} \cdot \mathbb{E}_{\#} \left[ f(X_{[0,n]}) \mathbf{1}_{X_{[0,n]} \in E_n} \right].$$

**Proof.** In the event considered in the conditioning, we have $|D_n^{[X]}(\mathbf{e}_i)| \le A\sqrt{n}$ for all $1 \le i \le 4$. By (2.1), the Radon-Nikodym derivative of $(X_{n+k} - X_n : 0 \le k \le n)$ under $\mathbb{P}_{\#}$ with respect to $\mathbb{P}_{\#}$ is given by

$$\mathrm{RND}_n := \prod_{k=n}^{2n-1} \left( 1 + \alpha \frac{D_k^{[X]}(\Delta X_k)}{k} \right) = \prod_{k=0}^{n-1} \left( 1 + \alpha \frac{D_n^{[X]}(\Delta X_k^{(n)}) + D_k^{[X^{(n)}]}(\Delta X_k^{(n)})}{n+k} \right). \quad (2.2)$$

By Donsker's invariance principle, we can find a constant $A_\varepsilon$ such that the event

$$G_n = \left\{ \max_i \sup_{0 \le k \le n} \left| D_k^{[X^{(n)}]}(\mathbf{e}_i) \right| \le A_\varepsilon \sqrt{n} \right\}$$

has probability at least $1 - \varepsilon$ under $\mathbb{P}_{\#}$. On this event (and conditionally on the event of the statement of the proposition), the counting directions processes $D_{[n,2n]}^{[X]}(\mathbf{e}_i)$ are in absolute value
bounded by $(A+A_\epsilon)\sqrt{n}$. In particular, using $\log(1+\alpha x) \ge \alpha x - (\alpha x)^2$ for small $|x|$, we deduce that on this event, for $n$ large enough, the Radon-Nikodym derivative in (2.2) is lower bounded by

$$ \mathrm{RND}_n \mathbf{1}_{G_n} \ge \exp(\alpha M_n - \alpha^2 (A + A_\epsilon)^2) \quad \text{where} \quad M_j = \sum_{k=0}^{j-1} \frac{D_{n+k}^{[X]} (\Delta X_{n+k})}{n+k} $$

Using (1.1), it is trivial to check that $(M_j : 0 \le j \le n)$ is a $(\mathcal{F}_{n+\cdot})$-martingale with quadratic variation

$$ \mathbb{E} [M_{j+1}^2 - M_j^2 | \mathcal{F}_{n+j}] = \mathbb{E} [(M_{j+1} - M_j)^2 | \mathcal{F}_{n+j}] = \frac{1}{4} \sum_{i=1}^{4} (D_{n+j}^{[X]}(\mathbf{e}_i))^2 \underset{\text{on } G_n}{\le} \frac{(A+A_\epsilon)^2}{4n} $$

It follows that $\mathbb{E}[M_n^2 \mathbf{1}_{G_n}] \le \frac{(A+A_\epsilon)^2}{4}$. In particular, thanks to Markov inequality, for any $\epsilon > 0$, the event $H_n = \{|M_n| \mathbf{1}_{G_n} < \frac{(A+A_\epsilon)}{2\sqrt{\epsilon}}\}$ is of probability at least $1 - \epsilon$. Gathering up the pieces, on the event $E_n = G_n \cap H_n$ which is of $\mathbb{P}_{\#\#}$ measure at least $1 - 2\epsilon$, the Radon-Nikodym derivative of the elephant w.r.t. the simple random walk is at least $e^{-\alpha \frac{(A+A_\epsilon)}{2\sqrt{\epsilon}} - \alpha^2 (A+A_\epsilon)^2} =: c_{\epsilon,A}$. $\square$

<figure><img src="image_2.png" /><figcaption>**Figure 1.** Illustration of the proof of Proposition 3. Conditionally on $\mathcal{F}_n$ and on the fact that the counting directions processes are controlled at time $n$, the blue and red parts are independent on events of large probability. This is sufficient to imply a lower bound on the probability of return to 0.</figcaption></figure>

It is classical that in the plane, the simple random walk started from $x \in \mathbb{Z}^2$ with $\|x\| \approx \sqrt{n}$ has a probability of order $\log^{-1} n$ to visit $(0,0)$ within $n$ steps. Our weak bound (Proposition 2) is sufficient to imply the same kind of estimate for the elephant random walk:

**Proposition 3.** For any $A > 0$ there exists $c_A > 0$ such that

$$ \mathbb{E} \left[ \exists \frac{5}{2} n \le k \le 3n : X_k = 0 \mid \mathcal{F}_n \text{ and } \frac{|D_n^{[X]}(\mathbf{e}_i)|}{\sqrt{n}} \le A \text{ for all } 1 \le i \le 4 \right] \ge \frac{c_A}{\log n} $$
**Proof.** Let us denote $\mathbf{x}_n = X_n$ which is fixed conditionally on $\mathcal{F}_n$. Using Proposition 2 twice, for any positive functions $f$ and $g$ and any $A, A' > 0$ and any $\varepsilon > 0$, we can find two sequences of events $E_n$ and $E'_n$ and constants $c_{\varepsilon,A}$ and $c_{\varepsilon,A'}$ such that

$$ \begin{aligned} \mathbb{E}_{\mathbb{P}_{\#}} \left[ f(X_{[0,n]}^{(2n)}) g(X_{[0,n]}^{(n)}) \middle| \mathcal{F}_n \right] & \\ & \ge \mathbb{E}_{\mathbb{P}_{\#}} \left[ f(X_{[0,n]}^{(2n)}) g(X_{[0,n]}^{(n)}) \mathbf{1}_{\frac{\|D_{2n}^{[X]}(\mathbf{e}_i)\|}{\sqrt{n}} \le A', \forall 1 \le i \le 4} \middle| \mathcal{F}_n \right] \\ & \ge c_{\varepsilon,A'} \cdot \mathbb{E}_{\#} \left[ f(X_{[0,n]}) \mathbf{1}_{X_{[0,n]} \in E'_n} \right] \cdot \mathbb{E}_{\mathbb{P}_{\#}} \left[ \mathbf{1}_{\frac{\|D_{2n}^{[X]}(\mathbf{e}_i)\|}{\sqrt{n}} \le A', \forall 1 \le i \le 4} g(X_{[0,n]}^{(n)}) \middle| \mathcal{F}_n \right] \\ & \ge c_{\varepsilon,A'} \cdot \mathbb{E}_{\#} \left[ f(X_{[0,n]}) \mathbf{1}_{X_{[0,n]} \in E'_n} \right] \\ & \quad \cdot c_{\varepsilon,A} \cdot \mathbb{E}_{\#} \left[ g(X_{[0,n]}) \mathbf{1}_{X_{[0,n]} \in E_n} \mathbf{1}_{\frac{\|D_{2n}^{[X]}(\mathbf{e}_i)\|}{\sqrt{n}} \le A' - A, \forall 1 \le i \le 4} \middle| \mathcal{F}_n \right] \mathbf{1}_{\frac{\|D_{2n}^{[X]}(\mathbf{e}_i)\|}{\sqrt{n}} \le A, \forall 1 \le i \le 4} \end{aligned} $$

Up to increasing $A'$ we may suppose that the event $H_n = E_n \cap E'_n \cap \left\{ \frac{\|D_n^{[X]}(\mathbf{e}_i)\|}{\sqrt{n}} \le A' - A, \forall 1 \le i \le 4 \right\}$ has probability at least $1 - 3\varepsilon$ and particularizing the inequality above, we deduce that for some constant $\tilde{c}_{\varepsilon,A} > 0$ the probability in the proposition is lower bounded by

$$ \tilde{c}_{\varepsilon,A} \cdot \mathbb{P}_{\#} \left( \exists \frac{3}{2} n \le k \le 2n : X_k = -\mathbf{x}_n \text{ and } \begin{array}{l} X_{[0,n]}^{(0)} \in H_n \\ X_{[0,n]}^{(n)} \in H_n \end{array} \right), $$

so that we can apply the following lemma to conclude.

**Lemma 4.** For any $A > 0$, there exists $\varepsilon > 0$ and $\delta_A > 0$ so that if $\mathbf{x}_n \in \mathbb{Z}^2$ is such that $\|\mathbf{x}_n\| \le A\sqrt{n}$ and if $E_n$ is a sequence of events such that $\mathbb{P}_{\#}(X_{[0,n]} \in E_n) \ge 1 - \varepsilon$ then we have

$$ \mathbb{P}_{\#} \left( \exists \frac{3}{2} n \le k \le 2n : X_k = -\mathbf{x}_n \text{ and } \begin{array}{l} X_{[0,n]}^{(0)} \in E_n \\ X_{[0,n]}^{(n)} \in E_n \end{array} \right) \ge \frac{\delta_A}{\log n}. $$

**Proof.** We use a second-moment method on the random variable

$$ \mathcal{N}_{\mathbf{x}_n}^{E_n} := \# \left\{ \frac{3}{2} n \le k \le 2n : X_k = -\mathbf{x}_n \right\} \mathbf{1}_{X_{[0,n]}^{(0)} \in E_n} \mathbf{1}_{X_{[0,n]}^{(n)} \in E_n}. $$

We denote by $p_k^{E_n}(y) = \mathbb{E}_{\#}[\mathbf{1}_{X_k=y} \mathbf{1}_{X_{[0,n]} \in E_n}]$ and $p_k(y) = \mathbb{P}_{\#}(X_k = y)$ for the heat kernels. By the standard local limit theorem (or just Stirling approximation on the binomial coefficients) there exists $C > 0$ such that $p_k(y) \le \frac{C}{k}$ for all $k \ge 1$ and $y \in \mathbb{Z}^2$. First, by lifting the restrictions on $E_n$ we have

$$ \begin{aligned} \mathbb{E}_{\#} \left[ \left( \mathcal{N}_{\mathbf{x}_n}^{E_n} \right)^2 \right] & \le \mathbb{E}_{\#} \left[ \left( \sum_{k=3/2n}^{2n} \mathbf{1}_{X_k = -\mathbf{x}_n} \right)^2 \right] \le 2 \sum_{\frac{3}{2} n \le k \le k' \le 2n} p_k(-\mathbf{x}_n) p_{k'-k}(\mathbf{0}) \\ & \le 2 \sum_{\frac{3}{2} n \le k \le k' \le 2n} \frac{C}{n} \frac{C}{k'-k} \le C' \log(n), \end{aligned} $$

for some $C' > 0$ (independent of $n$). To evaluate the first moment, introduce the (truncated) Green functions $g^{E_n}(y) = \sum_{k=n/2}^n p_k^{E_n}(y)$ and similarly $g(y) = \sum_{k=n/2}^n p_k(y)$. In particular, since
$\mathbb{P}_{\#}(E_n) \ge 1 - \varepsilon$ we have $\|p - p^{E_n}\|_1 := \sum_y p(y) - p^{E_n}(y) \le \varepsilon$ and similarly and $\|g - g^{E_n}\|_1 = \sum_y g(y) - g^{E_n}(y) \le \varepsilon n$. Recalling that $\frac{C}{n} \ge p_n^{E_n}(y) \ge p_n(y)$ and $2C \ge g^{E_n}(y) \ge g(y)$, we have

$$
\begin{align*}
\mathbb{E}_{\#} \left[ \mathcal{N}_{\mathbf{x}_n}^{E_n} \right] &= \sum_{y \in \mathbb{Z}^2} p_n^{E_n}(y) g^{E_n}(-y-\mathbf{x}_n) = \sum_{y \in \mathbb{Z}^2} \left( \begin{array}{@{}l@{}}
    p_n^{E_n}(y) g^{E_n}(-y-\mathbf{x}_n) - p_n^{E_n}(y) g(-y-\mathbf{x}_n) \\
    -p_n(y) g(-y-\mathbf{x}_n) + p_n^{E_n}(y) g(-y-\mathbf{x}_n) \\
    +p_n(y) g(-y-\mathbf{x}_n)
  \end{array} \right) \\
&\geq \sum_y p_n(y) g(-y-\mathbf{x}_n) - \left\| p_n^{E_n} \right\|_{\infty} \left\| g - g^{E_n} \right\|_1 - \left\| g \right\|_{\infty} \left\| p_n - p_n^{E_n} \right\| \\
&\geq \sum_y p_n(y) g(-y-\mathbf{x}_n) - 3C^2 \varepsilon.
\end{align*}
$$

However, since $\|\mathbf{x}_n\| \le A\sqrt{n}$, the local limit theorem implies that $\sum_y p(y)g(-y-\mathbf{x}_n) > c_A$ for some $c_A > 0$ independently of $n$ and so one can choose $\varepsilon > 0$ small enough so that if $\mathbb{P}_{\#}(E_n) \ge 1-\varepsilon$ then we have $\mathbb{E}_{\#}[\mathcal{N}_{\mathbf{x}_n}^{E_n}] > c_A/2$. We conclude by the second moment method that

$$
\mathbb{P}_{\#}(\mathcal{N}_{\mathbf{x}_n}^{E_n} > 0) \ge \mathbb{E}_{\#}(\mathcal{N}_{\mathbf{x}_n}^{E_n}) / \mathbb{E}_{\#}([\mathcal{N}_{\mathbf{x}_n}^{E_n}]^2) \ge \frac{c_A}{2C' \log n}. \quad \square
$$

3. Proof of Theorem 1

**Proof of Theorem 1.** Let us denote $\mathcal{P}_{3j} = \mathbb{P}_{\#}(\exists 3^j \le k \le 3^{j+1}, X_k = \mathbf{0} | \mathcal{F}_{3j})$. When $\alpha < \alpha_c$, i.e. the diffusive regime, Bertenghi [1, Theorem 4.2] showed that under $\mathbb{P}_{\#}$ we have

$$
\left( \frac{D_n^X(\mathbf{e}_i)}{\sqrt{n}} \right)_{1 \le i \le 4} \xrightarrow{n \to \infty} (\mathcal{X}_i)_{1 \le i \le 4},
$$

for some random variable $\mathcal{X}$ (whose distribution is irrelevant for our purposes). Together with
our Proposition 3, this shows that in the diffusive regime, for any $\varepsilon > 0$ there exists $\delta > 0$ such that
for large $j$'s we have

$$
\mathbb{P}_{\#}(j \cdot \mathcal{P}_{3j} > \delta) \ge 1 - \varepsilon. \tag{3.1}
$$

Notice that the variables $\mathcal{P}_{3j}$ are not independent, but Jeulin's lemma [4, Proposition 3.2] gives

$$
\sum_{k=1}^{\infty} \mathcal{P}_{3k} = \infty, \quad \mathbb{P}_{\#} - \text{a.s.} \tag{3.2}
$$

To be honest we rather use the proof than the lemma itself, and since the argument is short
let us reproduce it here: Suppose by contradiction that there exists $\varepsilon, M > 0$ so that the event
$A = \{\sum_{k=1}^{\infty} \mathcal{P}_{3k} < M\}$ has probability at least $\varepsilon > 0$. Using (3.1) we take $\delta > 0$ so that $\mathbb{P}_{\#}(j \cdot \mathcal{P}_{3j} > \delta) \ge 1 - \frac{\varepsilon}{2}$ and write

$$
M \ge \mathbb{E} \left[ \mathbf{1}_A \sum_{j \ge 1} \mathcal{P}_{3k} \right] = \sum_{j \ge 1} \frac{\delta}{j} \cdot \underbrace{\mathbb{P}_{\#} \left( A \cap \left\{ \mathcal{P}_{3j} > \frac{\delta}{j} \right\} \right)}_{\ge \varepsilon - \left(1 - \left(1 - \frac{\varepsilon}{2}\right)\right) = \varepsilon/2} = \infty,
$$

which is a contradiction. Given (3.2), the conditional Borel–Cantelli lemma ([2, Theorem 4.3.4])
then implies that the events $\exists 3^j \le k \le 3^{j+1} : X_k = \mathbf{0}$ happen for infinitely many $j$'s with
probability one, implying recurrence of the process.
$\square$

Acknowledgments

We thank Jean Bertoin and Thomas Budzinski for discussions about the plane elephant random
walk. We are also indebted to Alice Contat for providing us with the pictures # and 🌀.
**Declaration of interests**

The authors do not work for, advise, own shares in, or receive funds from any organization that could benefit from this article, and have declared no affiliations other than their research organizations.

**References**

[1] M. Bertenghi, "Functional limit theorems for the multi-dimensional elephant random walk", *Stoch. Models* **38** (2022), no. 1, pp. 37–50.

[2] R. Durrett, *Probability. Theory and examples*, Fifth edition, Cambridge University Press, 2019, pp. xii+419.

[3] L. Laulin, *About the elephant random walk*, PhD thesis, Université de Bordeaux, 2022.

[4] A. Matsumoto and K. Yano, "On a zero-one law for the norm process of transient random walk", in *Séminaire de Probabilités XLIII* (C. Donati-Martin, A. Lejay and A. Rouault, eds.), Springer, 2011, pp. 105–126.

[5] S. Qin, "Recurrence and transience of multidimensional elephant random walks", 2023. https://arxiv.org/abs/2309.09795.

[6] G. M. Schütz and S. Trimper, "Elephants can always remember: Exact long-range memory effects in a non-Markovian random walk", *Phys. Rev. E* **70** (2004), article no. 045101 (4 pages).