ON THE MULTI-DIMENSIONAL ELEPHANT RANDOM WALK

arXiv:1709.07345v1 [math.PR] 21 Sep 2017

BERNARD BERCU AND LUCILE LAULIN
Abstract. The purpose of this paper is to investigate the asymptotic behavior
of the multi-dimensional elephant random walk (MERW). It is a non-Markovian
random walk which has a complete memory of its entire history. A wide range of
literature is available on the one-dimensional ERW. Surprisingly, no references are
available on the MERW. The goal of this paper is to fill the gap by extending the
results on the one-dimensional ERW to the MERW. In the diffusive and critical
regimes, we establish the almost sure convergence, the law of iterated logarithm
and the quadratic strong law for the MERW. The asymptotic normality of the
MERW, properly normalized, is also provided. In the superdiffusive regime, we
prove the almost sure convergence as well as the mean square convergence of
the MERW. All our analysis relies on asymptotic results for multi-dimensional
martingales.

1. Introduction
The elephant random walk (ERW) is a fascinating discrete-time random process
arising from mathematical physics. It is a non-Markovian random walk on Z which
has a complete memory of its entire history. This anomalous random walk was introduced by Schütz and Trimper [20], in order to investigate how long-range memory
affects the random walk and induces a crossover from a diffusive to superdiffusive
behavior. It was referred to as the ERW in allusion to the traditional saying that
elephants can always remember where they have been. The ERW shows three differents regimes depending on the location of its memory parameter p which lies
between zero and one.
Over the last decade, the ERW has received considerable attention in the mathematical physics literature in the diffusive regime p < 3/4 and the critical regime
p = 3/4, see e.g. [1],[2],[8],[9],[10],[13],[17],[19] and the references therein. Quite
recently, Baur and Bertoin [1] and independently Coletti, Gava and Schütz [6] have
proven the asymptotic normality of the ERW, properly normalized, with an explicit
asymptotic variance.
The superdiffusive regime p > 3/4 is much harder to handle. Initially, it was suggested by Schütz and Trimper [20] that, even in the superdiffusive regime, the ERW
has a Gaussian limiting distribution. However, it turns out [3] that this limiting
distribution is not Gaussian, as it was already predicted in [10], see also [6],[19].
Surprisingly, to the best of our knowledge, no references are available on the multidimensional elephant random walk (MERW) on Zd , except [8],[18] in the special
case d = 2. The goal of this paper is to fill the gap by extending the results on the
Key words and phrases. Elephant random walk, Multi-dimensional martingales, Almost sure
convergence, Asymptotic normality.
1

2

BERNARD BERCU AND LUCILE LAULIN

one-dimensional ERW to the MERW. To be more precise, we shall study the influence of the memory parameter p on the MERW and we will show that the critical
value is given by
2d + 1
.
pd =
4d
In the diffusive and critical regimes p ≤ pd , the reader will find the natural extension
to higher dimension of the results recently established in [1],[3],[6],[7] on the almost
sure asymptotic behavior of the ERW as well as on its asymptotic normality. One
can notice that unlike in the classic random walk, the asymptotic normality of the
MERW holds in any dimension d ≥ 1. In the superdiffusive regime p > pd , we will
also prove some extensions of the results in [3],[8],[18].
Our strategy is to make an extensive use of the theory of martinagles [11],[15], in
particular the strong law of large numbers and the central limit theorem for multidimensional martingales [11], as well as the law of iterated logarithm [21],[22]. We
strongly believe that our approach could be successfully extended to MERW with
stops [8],[16], to amnesiac MERW [9], as well as to MERW with reinforced memory
[1],[14].
The paper is organized as follows. In Section 2, we introduce the exact MERW and
the multi-dimensional martingale we will extensively make use of. The main results
of the paper are given in Section 3. As usual, we first investigate the diffusive
regime p < pd and we establish the almost sure convergence, the law of iterated
logarithm and the quadratic strong law for the MERW. The asymptotic normality
of the MERW, properly normalized, is also provided. Next, we prove similar results
in the critical regime p = pd . At last, we study the superdiffusive regime p > pd and
we prove the almost sure convergence as well as the mean square convergence of the
MERW to a non-degenerate random vector. Our martingale approach is described
in Appendix A, while all technical proofs are postponed to Appendices B and C.

2. The multi-dimensional elephant random walk
First of all, let us introduce the MERW. It is the natural extension to higher
dimension of the one-dimensional ERW defined in the pioneer work of Schütz and
Trimper [20]. For a given dimension d ≥ 1, let (Sn ) be a random walk on Zd ,
starting at the origin at time zero, S0 = 0. At time n = 1, the elephant moves
in one of the 2d directions with the same probability 1/2d. Afterwards, at time
n ≥ 1, the elephant chooses uniformly at random an integer k among the previous
times 1, . . . , n. Then, he moves exactly in the same direction as that of time k with
probability p or in one of the 2d − 1 remaining directions with the same probability
(1 − p)/(2d − 1), where the parameter p stands for the memory parameter of the
MERW. From a mathematical point of view, the step of the elephant at time n ≥ 1
in given by
(2.1)

Xn+1 = An Xk

ON THE MULTI-DIMENSIONAL ELEPHANT RANDOM WALK

3

where

with


+Id





−Id






+Jd



−Jd
An =










+Jdd−1




−Jdd−1

with probability

p

with probability

1−p
2d−1
1−p
2d−1
1−p
2d−1

with probability
with probability
..
.
with probability
with probability



1 0 ··· 0
0 1 · · · 0

Id = 
 ... . . . . . . ... 
0 ··· 0 1

and

1−p
2d−1
1−p
2d−1



0 1 ··· 0
0 0 · · · 0

Jd = 
 ... . . . . . . ...  .
1 ··· 0 0

One can observe that the permutation matrix Jd satisfies Jdd = Id . Therefore, the
position of the elephant at time n ≥ 1 is given by
(2.2)

Sn+1 = Sn + Xn+1 .

It follows from our very definition of the MERW that at any n ≥ 1, Xn+1 = An Xbn
where An is the random matrix described before while bn is a random variable
uniformly distributed on {1, ..., n}. Moreover, as An and bn are conditionally independent, we clearly have E [Xn+1 |Fn ] = E [An ] E [Xbn |Fn ] where Fn stands for
the σ-algebra, Fn = σ(X1 , . . . , Xn ). Hence, we can deduce from the law of total
probability that at any time n ≥ 1,
1  2dp − 1 
a
(2.3)
E [Xn+1 |Fn ] =
Sn = Sn
a.s.
n 2d − 1
n
where a is the fundamental parameter of the MERW,
(2.4)

a=

2dp − 1
.
2d − 1

Consequently, we immediately obtain from (2.2) and (2.3) that for any n ≥ 1,
a
(2.5)
E [Sn+1 |Fn ] = γn Sn
where
γn = 1 + .
n
Furthermore,
n
Y
Γ(a + 1 + n)
γk =
Γ(a + 1)Γ(n + 1)
k=1

where Γ is the standard Euler Gamma function. The critical value associated with
the memory parameter p of the MERW is

(2.6)

pd =

2d + 1
.
4d

4

BERNARD BERCU AND LUCILE LAULIN

As a matter of fact,
1
1
1
a = ⇐⇒ p = pd ,
a > ⇐⇒ p > pd .
a < ⇐⇒ p < pd ,
2
2
2
Definition 2.1. The MERW (Sn ) is said to be diffusive if p < pd , critical if p = pd ,
and superdiffusive if p > pd .
All our investigation in the three regimes relies on a martingale approach. To be
more precise, the asymptotic behavior of (Sn ) is closely related to the one of the
sequence (Mn ) defined, for all n ≥ 0, by Mn = an Sn where a0 = 1, a1 = 1 and, for
all n ≥ 2,
(2.7)

an =

n−1
Y
k=1

γk−1 =

Γ(a + 1)Γ(n)
.
Γ(n + a)

It follows from a well-known property of the Euler Gamma function that
Γ(n + a)
(2.8)
lim
= 1.
n→∞ Γ(n)na
Hence, we obtain from (2.7) and (2.8) that
(2.9)

lim na an = Γ(a + 1).

n→∞

Furthermore, since an = γn an+1 , we can deduce from (2.5) that for all n ≥ 1,
E [Mn+1 |Fn ] = Mn

a.s.

It means that (Mn ) is a multi-dimensional martingale. Our goal is to extend the
results recently established in [3] to MERW. One can observe that our approach is
much more tricky than that of [3] as it requires to study the asymptotic behavior of
the multi-dimensional martingale (Mn ).
3. Main results
3.1. The diffusive regime. Our first result deals with the strong law of large
numbers for the MERW in the diffusive regime where 0 ≤ p < pd .
Theorem 3.1. We have the almost sure convergence
1
(3.1)
lim Sn = 0
a.s.
n→∞ n
Some refinements on the almost sure rates of convergence for the MERW are as
follows.
Theorem 3.2. We have the quadratic strong law
n
1
1 X 1
T
S
S
=
Id
(3.2)
lim
k
k
2
n→∞ log n
k
d(1
−
2a)
k=1

a.s.

In particular,

n

(3.3)

1 X kSk k2
1
lim
=
2
n→∞ log n
k
(1 − 2a)
k=1

a.s.

ON THE MULTI-DIMENSIONAL ELEPHANT RANDOM WALK

Moreover, we also have the law of iterated logarithm
1
kSn k2
=
(3.4)
lim sup
(1 − 2a)
n→∞ 2n log log n

5

a.s.

Our next result is devoted to the asymptotic normality of the MERW in the diffusive
regime 0 ≤ p < pd .
Theorem 3.3. We have the asymptotic normality


1
1
L
√ Sn −→ N 0,
(3.5)
Id .
(1 − 2a)d
n

Remark 3.1. We clearly have from (2.4) that
2d − 1
1
=
.
1 − 2a
2d(1 − 2p) + 1
Hence, in the special case d = 1, the critical value pd = 3/4 and the asymptotic
variance
1
1
=
.
1 − 2a
3 − 4p
Consequently, we find again the asymptotic normality for the one-dimensional ERW
in the diffusive regime 0 ≤ p < 3/4 recently established in [1],[3],[6].
3.2. The critical regime. We now focus our attention on the critical regime where
the memory parameter p = pd .
Theorem 3.4. We have the almost sure convergence
1
Sn = 0
a.s.
(3.6)
lim √
n→∞
n log n
We continue with some refinements on the almost sure rates of convergence for the
MERW.
Theorem 3.5. We have the quadratic strong law
n
X
1
1
1
Sk SkT = Id
(3.7)
lim
2
n→∞ log log n
(k log k)
d

a.s

k=2

In particular,

n

(3.8)

X kSk k2
1
lim
=1
2
n→∞ log log n
(k
log
k)
k=2

Moreover, we also have the law of iterated logarithm
kSn k2
(3.9)
lim sup
=1
n→∞ 2n log n log log log n

a.s.

a.s.

Our next result concerns the asymptotic normality of the MERW in the critical
regime p = pd .
Theorem 3.6. We have the asymptotic normality
 1 
1
L
√
(3.10)
Sn −→ N 0, Id .
d
n log n

6

BERNARD BERCU AND LUCILE LAULIN

Remark 3.2. As before, in the special case d = 1, we find again [1],[3],[6] the
asymptotic normality for the one-dimensional ERW
√

Sn
L
−→ N (0, 1).
n log n

3.3. The superdiffusive regime. Finally, we get a handle on the more arduous
superdiffusive regime where pd < p ≤ 1.
Theorem 3.7. We have the almost sure convergence
1
Sn = L
a.s.
n→∞ na
where the limiting value L is a non-degenerate random vector. Moreover, we also
have the mean square convergence
h 1
2i
(3.12)
lim E
= 0.
S
−
L
n
n→∞
na
(3.11)

lim

Theorem 3.8. The expected value of L is E[L] = 0, while its covariance matrix is
given by


1
(3.13)
E LLT =
Id .
d(2a − 1)Γ(2a)

In particular,
(3.14)



E kLk2 =

1
.
(2a − 1)Γ(2a)

Remark 3.3. Another possibility for the MERW is that, at time n = 1, the elephant
moves in one direction, say the first direction e1 of the standard basis (e1 , . . . , ed )
of Rd , with probability q or in one of the 2d − 1 remaining directions with the same
probability (1 − q)/(2d − 1), where the parameter q lies in the interval [0, 1]. Afterwards, at any time n ≥ 2, the elephant moves exactly as before, which means that his
steps are given by (2.1). Then, the results of Section 3 holds true except Theorem
3.8 where
 2dq − 1 
1
E[L] =
e1
Γ(a + 1) 2d − 1
and
 2dq − 1 
1
1 
1
E[LLT ] =
e1 eT1 − Id +
Id ,
Γ(2a + 1) 2d − 1
d
d(2a − 1)Γ(2a)
which also leads to


1
.
E kLk2 =
(2a − 1)Γ(2a)
Appendix A
A multi-dimensional martingale approach
We clearly obtain from (2.1) that for any time n ≥ 1, kXn k = 1. Consequently, it
follows from (2.2) that kSn k ≤ n. Therefore, the sequence (Mn ) given, for all n ≥ 0,

ON THE MULTI-DIMENSIONAL ELEPHANT RANDOM WALK

7

by Mn = an Sn , is a locally square-integrable multi-dimensional martingale. It can
be rewritten in the additive form
n
X
(A.1)
Mn =
ak εk
k=1

since its increments ∆Mn = Mn − Mn−1 satisfy ∆Mn = an Sn − an−1 Sn−1 = an εn
where εn = Sn − γn−1Sn−1 . The predictable quadratic variation associated with
(Mn ) is the random square matrix of order d given, for all n ≥ 1, by
(A.2)

n
X


E ∆Mk (∆Mk )T |Fk−1 .
hMin =
k=1

We already saw from (2.5) that E [εn+1 |Fn ] = 0. Moreover, we deduce from (2.2)
together with (2.3) that



 2a


T
T
E Sn+1 Sn+1
|Fn = E Sn SnT |Fn + Sn SnT + E Xn+1 Xn+1
|Fn
n




2a
T
(A.3)
Sn SnT + E Xn+1 Xn+1
|Fn
a.s.
=
1+
n

In order to calculate the right-hand side of (A.3), one can notice that for any n ≥ 1,
Xn XnT

=

d
X
i=1

IXni 6=0 ei eTi

where (e1 , . . . , ed ) stands for the standard basis of the Euclidean space Rd and Xni is
the i-th coordinate of the random vector Xn . Moreover, it follows from (2.1) together
with the law of total probability that any time n ≥ 1 and for any 1 ≤ i ≤ d,
n

i
P(Xn+1

1X
6 0|Fn ) =
=
P((An Xk )i 6= 0|Fn )
n k=1

n
n
1X
1X
I i P(An = ±Id ) +
(1 − IXki 6=0 )P(An = ±Jd )
=
n k=1 Xk 6=0
n k=1

NnX (i) 
=
P(An = Id ) − P(An = Jd ) + 2P(An = Jd )
n
which implies that for any 1 ≤ i ≤ d,

 a X
(1 − a)
i
(A.4)
E IXn+1
Nn (i) +
a.s.
6=0 |Fn =
n
d
where
n
X
X
Nn (i) =
IXki 6=0
k=1

and the parameter a is given by (2.4). Hence, we infer from (A.3) and (A.4) that
(A.5)


 a
(1 − a)
T
Id
E Xn+1 Xn+1
|Fn = Σn +
n
d

a.s.

8

BERNARD BERCU AND LUCILE LAULIN

where
(A.6)

Σn =

d
X

NnX (i)ei eTi .

i=1

One can observe the elementary fact that for all n ≥ 1, Tr(Σn ) = n where Tr(Σn )
stands for the trace of the positive definite matrix Σn . Therefore, we obtain from
(A.3) together with (A.5) that




T
|Fn − γn2 Sn SnT
E εn+1 εTn+1|Fn = E Sn+1 Sn+1

2a 
a
(1 − a)
= 1+
Sn SnT + Σn +
Id − γn2 Sn SnT
n
n
d
 a 2
(1 − a)
a
(A.7)
Σn +
Id −
Sn SnT
a.s.
=
n
d
n
which ensures that
 a 2


a
1−a
E kεn+1 k2 |Fn =
Tr(Σn ) +
Tr(Id ) −
kSn k2
n
d
n
(A.8)
= 1 − (γn − 1)2 kSn k2
a.s.
By the same token,


E kεn+1k4 |Fn = 1 − 3(γn − 1)4 kSn k4 − 2(γn − 1)2 kSn k2 + 4(γn − 1)2 ξn

where, thanks to (A.5),

 a
(1 − a)
kSn k2 .
ξn = E hSn , Xn+1 i2 |Fn = SnT Σn Sn +
n
d
It leads to



2(1 − a) 
4
4
4
(γn − 1)2 kSn k2
E kεn+1 k |Fn = 1 − 3(γn − 1) kSn k − 2 1 −
d
4a
(A.9)
a.s.
+ (γn − 1)2 SnT Σn Sn
n
Therefore, as Σn ≤ nId for the usual order of positive definite matrices, we clearly
obtain from (A.9) that


E kεn+1 k4 |Fn ≤ 1 − 3(γn − 1)4 kSn k4


2
+ (γn − 1)2 2a(d − 1) + 2 − d kSn k2 a.s.
(A.10)
d
Consequently, we obtain from (A.8) and (A.10) the almost sure upper bounds



 4
(A.11) sup E kεn+1 k2 |Fn ≤ 1
and
sup E kεn+1 k4 |Fn ≤
a.s.
3
n≥0
n≥0
Hereafter, we deduce from (A.2) and (A.7) that
hMin =

(A.12)

a21 E[ε1 εT1 ]

+

n−1
X
k=1

n
X



a2k+1 E εk+1 εTk+1|Fk

n−1
1
X
1 
1
2
Id
ak + a
a2k+1 Σk − Id − ζn
=
d k=1
k
d
k=1

ON THE MULTI-DIMENSIONAL ELEPHANT RANDOM WALK

9

where
ζn = a2

n−1 
X
ak+1 2

k

k=1

Sk SkT .

Hence, by taking the trace on both sides of (A.12), we find that
(A.13)

TrhMin =

n
X
k=1

a2k

2

−a

n−1 
X
ak+1 2

k

k=1

kSk k2 .

The asymptotic behavior of the multi-dimensional martingale (Mn ) is closely related
to the one of
n
n 
X
X
Γ(a + 1)Γ(k) 2
2
vn =
ak =
.
Γ(a + k)
k=1
k=1

One can observe that we always have TrhMin ≤ vn . In accordance with Definition
2.1, we have three regimes. In the diffusive regime where a < 1/2,
(A.14)

lim

vn

n→∞

n1−2a

=ℓ

where

ℓ=

(Γ(a + 1))2
.
1 − 2a

In the critical regime where a = 1/2,
vn
π
= (Γ(a + 1))2 = .
(A.15)
lim
n→∞ log n
4

Finally, in the superdiffusive regime where a > 1/2, vn converges to the finite value
lim vn =

n→∞

(A.16)

∞ 
X
Γ(a + 1)Γ(k + 1) 2

Γ(a + k + 1)


1, 1, 1
= 3 F2
1
a + 1, a + 1
k=0

=

∞
X
k=0

(1)k (1)k (1)k
(a + 1)k (a + 1)k k!

where, for any α ∈ R, (α)k = α(α + 1) · · · (α + k − 1) for k ≥ 1, (α)0 = 1 stands for
the Pochhammer symbol and 3 F2 is the generalized hypergeometric function defined
by
3 F2

∞
 X

(a)k (b)k (c)k k
a, b, c
z =
z .
d, e
(d)k (e)k k!
k=0

.

Appendix B
Proofs of the almost sure convergence results
B.1. The diffusive regime.

Proof of Theorem 3.1. First of all, we focus our attention on the proof of the
almost sure convergence (3.1). We already saw from (A.13) that TrhMin ≤ vn .
Moreover, we obtain from (A.14) that, in the diffusive regime where 0 < a < 1/2,
vn increases to infinity with the speed n1−2a . On the one hand, it follows from the

10

BERNARD BERCU AND LUCILE LAULIN

strong law of large numbers for multi-dimensional martingales given e.g. by the last
part of Theorem 4.3.15 in [11] that for any γ > 0,

1+γ 
kMn k2
= o log TrhMin
a.s
(B.1)
λmax hMin

where λmax hMin stands for the maximal eigenvalue of the random square matrix
hMin . However, as hMin is a positive definite matrix and TrhMin ≤ vn , we clearly
have λmax hMin ≤ TrhMin ≤ vn . Consequenly, we obtain from (B.1) that

kMn k2 = o vn (log vn )1+γ
a.s
which implies that

kMn k2 = o n1−2a (log n)1+γ

(B.2)



a.s.

Hence, as Mn = an Sn , it follows from (2.9) and (B.2) that for any γ > 0,

kSn k2 = o n(log n)1+γ
a.s.
which completes the proof of Theorem 3.1.

Proof of Theorem 3.2. We shall now proceed to the proof of the almost sure
rates of convergence given in Theorem 3.2. First of all, we claim that
1
1
(B.3)
lim Σn = Id
a.s.
n→∞ n
d
where Σn is the random square matrix of order d given by (A.6). As a matter of
fact, in order to prove (B.3) it is only necessary to show that for any 1 ≤ i ≤ d,
1
NnX (i)
=
lim
n→∞
n
d

(B.4)
For any 1 ≤ i ≤ d, denote

Λn (i) =

a.s.

NnX (i)
.
n

One can observe that
n
1
Λn (i) +
I i
n+1
n + 1 Xn+1 6=0
which leads, via (A.4), to the recurrence relation
Λn+1 (i) =

(B.5)

Λn+1 (i) =

(1 − a)
1
n
γn Λn (i) +
+
δn+1 (i)
n+1
d(n + 1) n + 1

i
i
where δn+1 (i) = IXn+1
6=0 − E[IXn+1
6=0 |Fn ]. After straightforward calculations, the
solution of this recurrence relation is given by
n

1 
(1 − a) X
(B.6)
Λn (i) =
Λ1 (i) +
ak + Ln (i)
nan
d

k=2

where

Ln (i) =

n
X
k=2

ak δk (i).

ON THE MULTI-DIMENSIONAL ELEPHANT RANDOM WALK

11

However, (Ln (i)) is a square-integrable real martingale with predictable quadratic
variation hL(i)in satisfying hL(i)in ≤ vn a.s. Then, it follows from the standard
strong law of large numbers for martingales given by Theorem 1.3.24 in [11] that
(Ln (i))2 = O(vn log vn ) a.s. Consequently, as na2n is equivalent to (1 − 2a)vn , we
obtain that for any 1 ≤ i ≤ d,
1
Ln (i) = 0
a.s.
(B.7)
lim
n→∞ nan
Furthermore, one can easily check from (2.9) that
n
1 X
1
(B.8)
lim
ak =
.
n→∞ nan
1−a
k=1

Therefore, we find from (B.6) together with (B.7) and (B.8) that for any 1 ≤ i ≤ d,
1
a.s.
(B.9)
lim Λn (i) =
n→∞
d
which immediately leads to (B.4). Hereafter, it follows from the conjunction of (3.1),
(A.7) and (B.4) that

 1
(B.10)
lim E εn+1 εTn+1 |Fn = Id
a.s.
n→∞
d
By the same token, we also obtain from (A.12) and Toeplitz lemma that
1
1
hMin = Id
a.s.
(B.11)
lim
n→∞ vn
d
We are now in the position to prove the quadratic strong law (3.2). For any vector
u of Rd , denote Mn (u) = hu, Mn i and εn (u) = hu, εni. We clearly have from (A.1)
n
X
Mn (u) =
ak εk (u).
k=1

Consequently, (Mn (u)) is a square-integrable real martingale. Moreover, it follows
from (B.10) that

 1
lim E |εn+1 (u)|2|Fn = kuk2
a.s.
n→∞
d
Moreover, we can deduce from (A.11) and the Cauchy-Schwarz inequality that

 4
a.s.
sup E |εn+1(u)|4 |Fn ≤ kuk4
3
n≥0

Furthermore, we clearly have from (2.9) and (A.14) that

a2n
,
n→∞
vn
which of course implies that fn converges to zero. Therefore, it follows from the
quadratic strong law for real martingales given e.g. in Theorem 3 of [4], that for
any vector u of Rd ,
n
1 X  Mk2 (u)  1
(B.12)
lim
fk
= kuk2
a.s.
n→∞ log vn
v
d
k
k=1
lim nfn = 1 − 2a

where

fn =

12

BERNARD BERCU AND LUCILE LAULIN

Consequently, we find from (A.14) and (B.12) that
n

(B.13)

(1 − 2a)
1 X a2k 2
kuk2
Mk (u) =
lim
2
n→∞ log n
vk
d

a.s.

k=1

Hereafter, as Mn = an Sn and n2 a4n is equivalent to (1 − 2a)2 vn2 , we obtain from
(B.13) that for any vector u of Rd ,
n

(B.14)

1
1 X 1 T
u Sk SkT u =
kuk2
lim
2
n→∞ log n
k
d(1 − 2a)

a.s.

k=1

By virtue of the second part of Proposition 4.2.8 in [11], we can conclude from (B.14)
that
n
1 X 1
1
(B.15)
lim
Sk SkT =
Id
a.s.
2
n→∞ log n
k
d(1 − 2a)
k=1
which completes the proof of (3.2). By taking the trace on both sides of (B.15), we
immediately obtain (3.3). Finally, we shall proceed to the proof of the law of iterated
logarithm given by (3.4). We already saw that a4n vn−2 is equivalent to (1 − 2a)2 n−2 .
It ensures that
+∞ 4
X
a

n

(B.16)

n=1

vn2

< +∞.

Hence, it follows from the law of iterated logarithm for real martingales due to Stout
[21],[22], see also Corollary 6.4.25 in [11], that for any vector u of Rd ,

1/2
1/2

1
1
lim sup
Mn (u) = − lim inf
Mn (u)
n→∞
2vn log log vn
2vn log log vn
n→∞
1
(B.17)
a.s.
= √ kuk
d
Consequently, as Mn (u) = an hu, Sn i, we obtain from (A.14) together with (B.17)
that

1/2
1/2

1
1
lim sup
hu, Sn i = − lim inf
hu, Sni
n→∞
2n log log n
2n log log n
n→∞
1
= p
kuk
a.s.
d(1 − 2a)
In particular, for any vector u of Rd ,
(B.18)

lim sup
n→∞

However,

1
1
hu, Sn i2 =
kuk2
2n log log n
d(1 − 2a)
2

kSn k =

d
X
i=1

hei , Sn i2

a.s.

ON THE MULTI-DIMENSIONAL ELEPHANT RANDOM WALK

13

where (e1 , . . . , ed ) is the standard basis of Rd . Finally, we deduce from (B.18) that
lim sup
n→∞

1
kSn k2
=
2n log log n
(1 − 2a)

a.s.

which achieves the proof of Theorem 3.2.
.

B.2. The critical regime.
Proof of Theorem 3.4. We already saw from (A.15) that in the critical regime
where a = 1/2, vn increases slowly to infinity with a logarithmic speed log n. We
obtain once again from the last part of Theorem 4.3.15 in [11] that for any γ > 0,

kMn k2 = o vn (log vn )1+γ
a.s
which leads to

kMn k2 = o log n(log log n)1+γ

(B.19)



a.s.

However, we clearly have from (2.9) with a = 1/2 that
π
(B.20)
lim na2n = .
n→∞
4
Consequently, as Mn = an Sn , we deduce from (B.19) and (B.20) that for any γ > 0,

kSn k2 = o n log n(log log n)1+γ
a.s.
which completes the proof of Theorem 3.4.
Proof of Theorem 3.5. The proof of Theorem 3.5 is left to the reader as it follows
the same lines as that of Theorem 3.2.
.
B.3. The superdiffusive regime.
Proof of Theorem 3.7. We already saw from (A.16) that in the superdiffusive
regime where 1/2 < a ≤ 1, vn converges to a finite value. As previously seen,
TrhMin ≤ vn . Hence, we clearly have
lim TrhMin < ∞

a.s.

n→∞

Therefore, if
(B.21)

Ln =

Mn
,
Γ(a + 1)

we can deduce from the second part of Theorem 4.3.15 in [11] that
(B.22)

lim Mn = M

n→∞

and

lim Ln = L

n→∞

a.s.

where the limiting values M and L are the random vectors of Rd given by
∞
∞
X
X
1
M=
ak εk
and
L=
ak εk .
Γ(a
+
1)
k=1
k=1

14

BERNARD BERCU AND LUCILE LAULIN

Consequently, as Mn = an Sn , (3.11) clearly follows from (2.9) and (B.22) We now
focus our attention on the mean square convergence (3.12). As M0 = 0, we have
from (A.1) and (A.2) that for all n ≥ 1,
n
X
2
E[kMn k ] =
E[k∆Mk k2 ] = E[TrhMin ] ≤ vn .
k=1

Hence, we obtain from (A.16) that




1, 1, 1
sup E kMn k2 ≤ 3 F2
1 < ∞,
a + 1, a + 1
n≥1

which means that the martingale (Mn ) is bounded in L2 . Therefore, we have the
mean square convergence


lim E kMn − Mk2 = 0,
n→∞

which clearly leads to (3.12).

Proof of Theorem 3.8. First of all, we clearly have for all n ≥ 1, E[Mn ] = 0
which implies that E[M] = 0 leading to E[L] = 0. Moreover, taking expectation on
both sides of (A.3) and (A.5), we obtain that for all n ≥ 1,






2a  
T
T
E Sn+1 Sn+1
= 1+
E Sn SnT + E Xn+1 Xn+1
n

 a
2a  
(1 − a)
= 1+
E Sn SnT + E [Σn ] +
(B.23)
Id .
n
n
d
However, we claim that
n
(B.24)
E [Σn ] = Id .
d
As a matter of fact, taking expectation on both sides of (B.6), we find that for any
1 ≤ i ≤ d,
n
1 
(1 − a) X 
(B.25)
E[Λn (i)] =
E[Λ1 (i)] +
ak .
nan
d
k=2

On the one hand, we clearly have

1
E[Λ1 (i)] = .
d
On the other hand, it follows from Lemma B.1 in [3] that
n
X
k=2

(B.26)

n
X
Γ(a + 1)Γ(k)

n−1
X
Γ(a + 1)Γ(k + 1)

=
Γ(k + a)
Γ(k + a + 1)
k=1


1
Γ(a + 1)Γ(n + 1)
(1 − nan )
=
1−
=
.
(a − 1)
Γ(a + n)
(a − 1)

ak =

k=2

Consequently, we can deduce from (B.25) and (B.26) that for any 1 ≤ i ≤ d,
1  1 (1 − nan )  1
= .
(B.27)
E[Λn (i)] =
−
nan d
d
d

ON THE MULTI-DIMENSIONAL ELEPHANT RANDOM WALK

15

Therefore, we get from (A.6) and (B.27) that
E[Σn ] = n

d
X

d

E[Λn (i)]ei eTi

i=1

n
nX T
ei ei = Id .
=
d i=1
d

Hereafter, we obtain from (B.23) and (B.24) that

 
 1
2a  
T
(B.28)
E Sn+1 Sn+1
= 1+
E Sn SnT + Id .
n
d
It is not hard to see that the solution of this recurrence relation is given by
!
n−1
X


1
Γ(n
+
2a)
Γ(2a
+
1)Γ(k
+
1)
E[S1 S1T ] +
E Sn SnT =
Id
Γ(2a + 1)Γ(n)
d
Γ(k + 2a + 1)
k=1
!
n
Γ(n + 2a) X Γ(k)
1
(B.29)
Id
=
Γ(n)
Γ(k
+
2a)
d
k=1
since

1
E[S1 S1T ] = Id .
d
Therefore, it follows once again from Lemma B.1 in [3] that




Γ(n + 2a)
1
n
T
−1
Id .
(B.30)
E Sn Sn =
(2a − 1) Γ(n + 1)Γ(2a)
d

Hence, we obtain from (B.21) together with (B.30) that


Γ(n + 2a)
1
na2n
T
−
1
Id
E[Ln Ln ] =
(2a − 1)(Γ(a + 1))2 Γ(n + 1)Γ(2a)
d

2 

n
Γ(n)
Γ(n + 2a)
1
=
(B.31)
−1
Id .
(2a − 1) Γ(n + a)
Γ(n + 1)Γ(2a)
d
Finally, we find from (3.12) and (B.31) that

lim E[Ln LTn ] = E[LLT ] =

n→∞

which achieves the proof of Theorem 3.8.

.

1
Id
d(2a − 1)Γ(2a)

Appendix C
Proofs of the asymptotic normality results
C.1. The diffusive regime.

Proof of Theorem 3.3. In order to establish the asymptotic normality (3.5), we
shall make use of the central limit theorem for multi-dimensional martingales given
e.g. by Corollary 2.1.10 of [11]. First of all, we already saw from (B.11) that
(C.1)

1
1
hMin = Id
n→∞ vn
d
lim

a.s.

16

BERNARD BERCU AND LUCILE LAULIN

Consequently, it only remains to show that (Mn ) satisfies Lindeberg’s condition, in
other words, for all ε > 0,
n
 P
1 X 
E k∆Mn k2 I{k∆Mn k≥ε√vn } |Fk−1 −→ 0.
vn k=1

We have from (A.11) that for all ε > 0

n
n


1 X 
1 X 
2
√
E k∆Mn k I{k∆Mn k≥ε vn } |Fk−1 ≤ 2 2
E k∆Mn k4 |Fk−1
vn k=1
ε vn k=1

n
 1 X
a4k
≤ sup E kεk k |Fk−1 2 2
ε vn k=1
1≤k≤n



≤
However, we already saw from (B.16) that
+∞ 4
X
a

n

n=1

vn2

4

n
4 X 4
a .
3ε2 vn2 k=1 k

< +∞.

Hence, it follows from Kronecker’s lemma that
n
1 X 4
lim
ak = 0,
n→∞ v 2
n k=1

which ensures that Lindeberg’s condition is satisfied. Therefore, we can conclude
from the central limit theorem for martingales that
 1 
1
L
(C.2)
√ Mn −→ N 0, Id .
vn
d
p
√
As Mn = an Sn and nan is equivalent to vn (1 − 2a), we find from (C.2) that


1
1
L
√ Sn −→ N 0,
Id ,
n
d(1 − 2a)

which completes the proof of Theorem 3.3.
.
C.2. The critical regime.

Proof of Theorem 3.6. Via the same lines as in the proof of (B.11), we can
deduce from (3.6), (A.13) and (A.15) that in the critical regime
1
1
(C.3)
lim
hMin = Id
a.s.
n→∞ vn
d
Moreover, it follows from (A.15) and (B.20) that a2n vn−1 is equivalent to (n log n)−1 .
It implies that
∞
X
a4n
(C.4)
< +∞.
2
v
n
k=1

ON THE MULTI-DIMENSIONAL ELEPHANT RANDOM WALK

17

As previously seen, we infer from (C.4) that (Mn ) satisfies Lindeberg’s condition.
Therefore, we can conclude from the central limit theorem for martingales that
 1 
1
L
(C.5)
√ Mn −→ N 0, Id .
vn
d
√
√
Finally, as Mn = an Sn and an n log n is equivalent to vn , we obtain from that
(C.5) that
1
L
√
Sn −→ N (0, 1),
n log n
which achieves the proof of Theorem 3.6.
References
[1] Baur, E. and Bertoin, J. Elephant Random Walks and their connection to Pólya-type urns.
Phys. Rev. E 94, 052134 (2016).
[2] Boyer, D., Romo-Cruz, J. C. R. Solvable random-walk model with memory and its relations
with Markovian models of anomalous diffusion. Phys. Rev. E 90, 042136 (2014).
[3] Bercu, B. A martingale approach for the elephant random walk. arXiv:1707.04130, (2017).
[4] Bercu, B. On the convergence of moments in the almost sure central limit theorem for martingales with statistical applications. Stochastic Process. Appl. 111, 1 (2004), pp. 157–173.
[5] Chauvin, B., Pouyanne, N., Sahnoun, R. Limit distributions for large Pólya urns. Ann.
Appl. Probab. 21, (2011), pp 1-32.
[6] Coletti, C. F., Gava, R., Schütz, G. M. Central limit theorem and related results for the
elephant random walk. J. Math. Phys. 58, 053303 (2017).
[7] Coletti, C. F., Gava, R., Schütz, G. M. A strong invariance principle for the elephant
random walk. arXiv:1707.06905, (2017).
[8] Cressoni, J. C., Viswanathan, G. M., Da Silva, M. A. A., Exact solution of an
anisotropic 2D random walk model with strong memory correlations. J. Phys. A: Math. Theor.
46, 505002 (2013).
[9] Cressoni, J. C., Da Silva, M. A. A., Viswanathan, G. M. Amnestically induced persistence in random walks. Phys. Rev. Let. 98, 070603 (2007).
[10] Da Silva, M. A. A., Cressoni, J. C., Schütz, G. M., Viswanathan, G. M., Trimper,
S. Non-Gaussian propagator for elephant random walks. Phys. Rev. E 88, 022115 (2013).
[11] Duflo, M., Random iterative models, Vol. 34 of Applications of Mathematics. SpringerVerlag, Berlin, 1997.
[12] Janson, S., Functional limit theorems for multitype branching processes and generalized
Pólya urns. Stochastic Process. Appl. 110, 2 (2004), pp. 177–245.
[13] Kumar, N., Harbola, U., Lindenberg, K. Memory-induced anomalous dynamics: Emergence of diffusion, subdiffusion, and superdiffusion from a single random walk model. Phys.
Rev. E 82, 021101 (2010).
[14] Harris, R. Random walkers with extreme value memory: modelling the peak-end rule. New
J. Phys. 17, 053049 (2015).
[15] Hall, P., and Heyde, C. C. Martingale limit theory and its application. Academic Press
Inc., New York, 1980.
[16] Harbola, U., Kumar, N., Lindenberg, K. Memory-induced anomalous dynamics in a
minimal random walk model. Phys. Rev. E 90, 022136 (2014).
[17] Kürsten, R. Random recursive trees and the elephant random walk. Phys. Rev. E 93, 032111
(2016).
[18] Lyu, J., Xin, J., Yu, Y. Residual diffusivity in elephant random walk models with stops.
arXiv:1705.02711, (2017).
[19] Paraan, F. N. C. and Esguerra, J. P. Exact moments in a continuous time random walk
with complete memory of its history. Phys. Rev. E 74, 032101 (2006).

18

BERNARD BERCU AND LUCILE LAULIN

[20] Schütz, G. M., and Trimper, S. Elephants can always remember: Exact long-range memory effects in a non-Markovian random walk. Phys. Rev. E 70, 045101 (2004).
[21] Stout, W. F. A martingale analogue of Kolmogorovs law of the iterated logarithm. Z.
Wahrscheinlichkeitstheorie 15 (1970), pp. 279-290.
[22] Stout, W. F., Almost sure convergence, Probability and Mathematical Statistics, Vol. 24,
Academic Press, New York-London, 1974.
Université de Bordeaux, Institut de Mathématiques de Bordeaux, UMR 5251, 351
Cours de la Libération, 33405 Talence cedex, France.
Ecole normale supérieure de Rennes, Département de Mathématiques, Campus
de Ker lann, Avenue Robert Schuman, 35170 Bruz

