Functional limit theorems for elephant random walks on general periodic structures

Basic Information

• Paper ID: 2511.10347
• Title: Functional limit theorems for elephant random walks on general periodic structures
• Author: Shuhei Shibata (Kyushu University)
• Classification: math.PR (Probability Theory)
• Publication Date: November 13, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2511.10347

Abstract

This paper investigates functional limit theorems for elephant random walks (ERW) on general periodic structures, extending results by Bertenghi on the standard integer lattice $\mathbb{Z}^d$. The research reveals new structure-dependent quantities that do not appear in the classical $\mathbb{Z}^d$ setting, highlighting how the underlying structure influences the asymptotic behavior of the walk.

Research Background and Motivation

Problem Background

1. Core Problem: Investigating the asymptotic behavior of random walks with long-range memory. The elephant random walk (ERW) was introduced by Schütz and Trimper in 2004 to study memory effects in one-dimensional discrete-time random walks, exhibiting a phase transition from diffusive to superdiffusive behavior.
2. Problem Significance:
   • ERW is an important model for studying memory effects with complete historical memory
   • The model exhibits fundamentally different behaviors across different parameter regions (diffusive, critical, superdiffusive)
   • Understanding how structure influences random walk behavior has both theoretical and applied value
3. Limitations of Existing Methods:
   • Most existing work focuses on the standard lattice $\mathbb{Z}^d$
   • Asymptotic theory on $\mathbb{Z}^d$ has been established by Bercu and Laulin, Bertenghi, and others
   • Systematic study of more general periodic structures (such as triangular, hexagonal, brick-wall lattices) is lacking
4. Research Motivation:
   • Generalize ERW theory to more general periodic structures
   • Discover structure-dependent new quantities, revealing how underlying geometric structure affects asymptotic behavior
   • Establish a unified analytical framework through Pólya-type urn model methods

Core Contributions

1. Theoretical Extension: Generalizes Bertenghi's functional limit theorems on $\mathbb{Z}^d$ to general periodic structures, including triangular, hexagonal, and brick-wall lattices.
2. Discovery of New Structure-Dependent Quantities: Identifies and analyzes structure-dependent quantities absent in the classical $\mathbb{Z}^d$ setting, such as covariance matrices $\Sigma(U)$ and $\Sigma(W)$, which encode information about the underlying geometric structure.
3. Unified Analytical Framework: Establishes a unified analytical framework through Pólya-type urn models, applicable to:
   • Type-I ERW (monochromatic vertex set, $U=W$)
   • Type-II ERW (bipartite vertex set, $U \neq W$)
4. Complete Phase Diagram Analysis: Establishes strong laws of large numbers and functional limit theorems across all parameter regions (diffusive, critical, superdiffusive), providing the exact critical value $p_c^m = \frac{m+1}{2m}$.
5. Explicit Calculations for Specific Examples: Provides explicit calculations of key quantities for multiple typical structures (standard lattices, triangular, hexagonal, brick-wall lattices, etc.).

Methodology Details

Task Definition

The research object is the elephant random walk $\{S_n\}_{n=0}^{\infty}$ defined on a general periodic structure $\Gamma$:

Input:

• Step vector sets $U = \{u_1, \ldots, u_m\} \subset \mathbb{R}^d$ and $W = \{w_1, \ldots, w_{m'}\} \subset \mathbb{R}^d$
• Memory parameter $p \in (0,1)$
• Initial step vectors $u_{i_0}$ and $w_{j_0}$

Output:

• Strong law of large numbers: $\frac{S_n}{n} \to \frac{1}{2}(\bar{u} + \bar{w})$ a.s.
• Functional limit theorems: Limiting distributions under appropriate normalization in different parameter regions

Constraints:

• $\Gamma$ must be a lattice in $\mathbb{R}^d$
• For Type-II ERW, must satisfy alternating rules (bipartite structure)

Model Architecture

1. State Space Construction

Case U = W (Type-I ERW): $\Gamma = \left\{\sum_{i=1}^m k_i u_i : k_i \in \mathbb{N} \cup \{0\}\right\}$ Monochromatic vertex set where all vertices have equivalent structure.

Case U ≠ W (Type-II ERW): First define: $\Gamma_0 = \left\{\sum_{i=1}^m k_i u_i + \sum_{j=1}^{m'} l_j w_j : \sum_{i=1}^m k_i = \sum_{j=1}^{m'} l_j, k_i, l_j \in \mathbb{N} \cup \{0\}\right\}$

Then: $\Gamma = \Gamma_0 \sqcup (\Gamma_0 + U)$

Define vertex classes: $Z_U := \Gamma_0$ and $Z_W := \Gamma_0 + U$, forming a bipartite graph structure.

2. Definition of ERW

Type-II ERW ($U \neq W$):

• Position definition: $S_{2n} = \sum_{i=1}^n (\sigma_i + \tau_i), \quad S_{2n-1} = S_{2(n-1)} + \sigma_n$
• Step selection mechanism: At time $n+1$, given history $\sigma_1, \ldots, \sigma_n$ and $\tau_1, \ldots, \tau_n$: $P(\sigma_{n+1} = \sigma_{U_n}) = p, \quad P(\sigma_{n+1} = \sigma) = \frac{1-p}{m-1} \text{ for } \sigma \in U \setminus \{\sigma_{U_n}\}$ where $U_n$ is uniformly distributed on $\{1,2,\ldots,n\}$.

Type-I ERW ($U = W$): $S_n = \sum_{i=1}^n \sigma_i$ Step selection mechanism is similar but samples from the entire history.

Technical Innovations

1. Connection to Pólya Urn Model

Establishes distributional equivalence between ERW and urn processes:

Type-II ERW: $\{S_{2n}\}_{n=0}^{\infty} \stackrel{d}{=} \left\{\sum_{i=1}^m X_n^i u_i + \sum_{j=1}^{m'} Y_n^j w_j\right\}_{n=0}^{\infty}$

Type-I ERW: $\{S_{2n}\}_{n=0}^{\infty} \stackrel{d}{=} \left\{\sum_{i=1}^m X_{2n}^i u_i\right\}_{n=0}^{\infty}$

where $X_n$ and $Y_n$ are independent Pólya urn processes.

2. Replacement Matrix Analysis

The key $m \times m$ replacement matrix: $A = \frac{1-p}{m-1}J_m + \frac{mp-1}{m-1}I_m$

Eigenvalues:

• $\lambda_1 = 1$ (multiplicity 1)
• $\lambda_2 = \frac{mp-1}{m-1}$ (multiplicity $m-1$)

The critical value is determined by $\lambda_2/\lambda_1 = 1/2$: $p_c^m = \frac{m+1}{2m}$

3. Structure-Dependent Covariance Matrices

Define key $d \times d$ covariance matrices: $\Sigma(U) = \frac{1}{m}\sum_{i=1}^m (u_i - \bar{u})(u_i - \bar{u})^{\top}$$\Sigma(W) = \frac{1}{m'}\sum_{j=1}^{m'} (w_j - \bar{w})(w_j - \bar{w})^{\top}$

These matrices encode the geometric configuration of step vectors. In the $\mathbb{Z}^d$ case they simplify to $I_d/d$, but in general structures may be non-diagonal, reflecting correlations in diffusion across different coordinate axes.

4. Connection to Janson's General Theory

The paper cleverly applies Janson's 2004 functional limit theorems for multitype branching processes and generalized Pólya urns (particularly Theorems 3.21, 3.24, 3.31), and uses the continuous mapping theorem to transform the asymptotic behavior of urn processes into asymptotic behavior of ERW.

Experimental Setup

Theoretical Verification

This is pure theoretical research with no numerical experiments or datasets. Verification is completed through rigorous mathematical proofs.

Typical Example Calculations

The paper provides calculations of key quantities for six concrete examples in Section 6:

1. Standard lattice $\mathbb{Z}^d$: $m=2d$, $p_c^m = \frac{2d+1}{4d}$, $\Sigma(U) = I_d/d$
2. Triangular lattice: $m=6$, $p_c^m = 7/12$, $\Sigma(U) = I_2/2$
3. Hexagonal lattice: $m=m'=3$, $p_c^m = 2/3$, $\Sigma(U) = I_2/2$
4. Brick-wall lattice: $m=m'=3$, $p_c^m = 2/3$, $\Sigma(U) = \frac{2}{9}\begin{pmatrix}3 & 0\\0 & 1\end{pmatrix}$
5. Mixed structure 1: $U = \{\pm u_1, \pm u_2\}$, $W = \{\pm e_1, \pm e_2\}$, $m=m'=4$
6. Mixed structure 2: $U = \{\pm e_1, \pm e_2, (1,2)^{\top}\}$, $W = \{\pm e_1, \pm e_2\}$, $m=5, m'=4$

Main Results

1. Strong Law of Large Numbers (Theorem 5.1)

For all $p \in (0,1)$: $\frac{S_n}{n} \to \frac{1}{2}(\bar{u} + \bar{w}) \quad \text{a.s. as } n \to \infty$

Key Features:

• The limit does not depend on the number of edges $m, m'$
• Depends only on the average of step vectors
• Holds for both Type-I and Type-II ERW

2. Diffusive Region (Theorem 5.3)

Condition: $0 < p < p_c^m \leq p_c^{m'}$

Result: $\left\{\frac{S_{\lfloor 2nt \rfloor} - nt(\bar{u} + \bar{w})}{\sqrt{n}}\right\}_{t \geq 0} \Rightarrow \{W_t\}_{t \geq 0}$

where $\{W_t\}_{t \geq 0}$ is a centered $\mathbb{R}^d$-valued continuous Gaussian process with covariance structure: $\mathbb{E}[W_s W_t^{\top}] = C_a s\left(\frac{t}{s}\right)^a \Sigma(U) + C_{a'} s\left(\frac{t}{s}\right)^{a'} \Sigma(W)$

where $a = \frac{mp-1}{m-1}$, $C_a = \frac{1}{1-2a}$.

Innovation:

• Covariance matrices $\Sigma(U), \Sigma(W)$ embody structure dependence
• Reduces to Bertenghi's result in the $\mathbb{Z}^d$ case
• When $\Sigma(U), \Sigma(W)$ are non-diagonal, diffusion along different coordinate axes are correlated

3. Critical Region (Theorem 5.5)

Condition: $0 < p_c^m = p = p_c^{m'}$

Result: $\left\{\frac{S_{\lfloor 2nt \rfloor} - nt(\bar{u} + \bar{w})}{n^{t/2}\sqrt{\log n}}\right\}_{t \geq 0} \Rightarrow \{W_t\}_{t \geq 0}$

Covariance structure: $\mathbb{E}[W_s W_t^{\top}] = s\Sigma(U, W)$

where $\Sigma(U, W) = \Sigma(U) + \Sigma(W)$.

Features:

• Requires an additional $\sqrt{\log n}$ normalization factor
• The limiting process can be expressed as $W_t = \Sigma(U,W)^{1/2}B_t$, where $B_t$ is standard Brownian motion
• In the $\mathbb{Z}^d$ case, $\{W_t/\sqrt{d}\}$ is standard Brownian motion

4. Superdiffusive Region (Theorem 5.8)

Condition: $0 < p_c^m = p_c^{m'} < p$

Type-II ERW Result: $\left\{\frac{S_{\lfloor 2nt \rfloor} - nt(\bar{u} + \bar{w})}{n^a}\right\}_{t \geq 0} \Rightarrow \{t^a L\}_{t \geq 0}$

Type-I ERW Result: $\left\{\frac{S_{\lfloor nt \rfloor} - nt\bar{u}}{n^a}\right\}_{t \geq 0} \Rightarrow \{t^a \tilde{L}\}_{t \geq 0}$

where $L, \tilde{L}$ are non-zero $\mathbb{R}^d$-valued random vectors.

Important Observations:

• Type-I and Type-II ERW have different limiting distributions in the superdiffusive region
• The limiting distribution depends on the choice of initial step
• Under the assumption $\bar{u} = \bar{w} = 0$ and uniform selection of initial steps: $\mathbb{E}[LL^{\top}] = \frac{1}{(2a-1)\Gamma(2a)}\Sigma(U,W)$

5. Mixed Parameter Regions (Remarks 5.7, 5.9)

The paper also discusses cases where $p_c^m \neq p_c^{m'}$:

• When $0 < p_c^m = p < p_c^{m'}$, the $X$ process dominates, and the limit depends only on $\Sigma(U)$
• When $0 < p_c^m < p_c^{m'} < p$, the dominant term must be determined based on the relationship between $a$ and $a'$

Related Work

One-Dimensional ERW Research

• Schütz and Trimper 2004: Introduced the ERW model, discovered phase transition at $p=3/4$
• Baur and Bertoin 2016: Established connection between ERW and Pólya urns
• Bercu 2017: Analyzed ERW using martingale methods
• Coletti et al. 2017: Central limit theorem
• Kubota and Takei 2019: Gaussian fluctuations in superdiffusive region

Multi-Dimensional ERW Research

• Bercu and Laulin 2019: Studied asymptotic behavior of MERW through martingale methods
• Bertenghi 2022: Established functional limit theorems on $\mathbb{Z}^d$ (the work directly generalized in this paper)
• González-Navarrete 2020: Multi-dimensional walks with random bias
• Chen and Laulin 2023: Multi-dimensional ERW with smooth memory decay
• Curien and Laulin 2024: Recurrence of planar ERW
• Qin 2025: Recurrence and transience of multi-dimensional ERW

Collision Problems

• Roy, Takei and Tanemura 2024: Collision problem for two ERWs on $\mathbb{Z}$
• Shibata and Shirai 2025: Collision problems and distance asymptotics with different memory parameters

Pólya Urn Theory

• Janson 2004: Functional limit theorems for multitype branching processes and generalized Pólya urns (core theoretical tool of this paper)
• Athreya and Karlin 1968: Embedding urn models in continuous-time branching processes
• Chauvin et al. 2011: Limiting distributions of large Pólya urns

Advantages of This Paper

1. Generality: Not limited to $\mathbb{Z}^d$, covers a wide range of periodic structures
2. Structure Dependence: Reveals new structure-dependent quantities
3. Unified Framework: Unified treatment of Type-I and Type-II ERW
4. Completeness: Complete theory covering all parameter regions

Conclusions and Discussion

Main Conclusions

1. Successful Theoretical Generalization: Successfully generalizes Bertenghi's results on $\mathbb{Z}^d$ to general periodic structures, demonstrating the universality of the Pólya urn method.
2. Quantification of Structure Effects: Precisely quantifies the influence of underlying geometric structure on ERW asymptotic behavior through covariance matrices $\Sigma(U)$ and $\Sigma(W)$.
3. Preservation of Phase Transition Phenomena: The critical value $p_c^m = \frac{m+1}{2m}$ is determined by eigenvalues of the replacement matrix; phase transition phenomena persist in general structures.
4. Differences Between Type-I and Type-II: Except in the superdiffusive region, the two types of ERW have identical limiting distributions; in the superdiffusive region, initial conditions lead to different limits.

Limitations

1. Structure Restrictions:
   • Only considers periodic structures representable as lattices
   • For multipartite graphs ($l \geq 3$), such as kagome lattice, different analytical techniques are needed
   • Excludes the trivial case $m=1$
2. Initial Conditions:
   • Assumes starting from the origin
   • First two steps are deterministic
   • Results in superdiffusive region depend on the distribution of initial steps
3. Parameter Range:
   • Only considers $p \in (0,1)$
   • $p=1$ corresponds to trivial case (deterministic walk)
   • $p=0$ is not discussed
4. Distribution Details:
   • Characterization of limiting random variable $L$ in superdiffusive region is incomplete
   • Only expressions for second moments are given; higher moments or complete distribution are unknown

Future Directions

1. Extension to More General Structures:
   • Non-periodic structures
   • Multipartite graphs ($l \geq 3$) such as kagome lattice
   • ERW in random environments
2. Refined Analysis of Limiting Distributions:
   • Complete distribution of $L$ in superdiffusive region
   • Application of fixed-point equation methods from Guérin et al. 2023, 2025
3. Collision Problems:
   • Collision problem for two ERWs on general structures
   • Cases with different memory parameters
4. Other Properties:
   • Complete characterization of recurrence and transience
   • Large deviation principles
   • Study of local times

In-Depth Evaluation

Strengths

1. Mathematical Rigor:
   • Proofs are complete and rigorous, fully utilizing Janson's general theory
   • Classification of different parameter regions is clear and complete
   • Technical details are handled appropriately (e.g., covariance calculations)
2. Theoretical Contributions:
   • First systematic study of ERW on general periodic structures
   • Discovery of structure-dependent new quantities $\Sigma(U), \Sigma(W)$
   • Establishment of unified framework for Type-I and Type-II ERW
3. Clarity:
   • Paper is well-organized, progressing from simple to complex
   • Illustrations (triangular, hexagonal, brick-wall lattices) are intuitive
   • Concrete example calculations in Section 6 are very useful
4. Completeness:
   • Covers all parameter regions (diffusive, critical, superdiffusive)
   • Discusses various mixed parameter cases
   • Clear connections to existing literature

Weaknesses

1. Limited Examples:
   • Although theory is general, only six concrete examples are provided
   • Lacks discussion of some interesting structures (e.g., kagome lattice)
   • Could include more examples of non-standard structures
2. Physical Intuition:
   • Lacks physical or geometric intuition for structure dependence
   • Significance of off-diagonal elements in $\Sigma(U), \Sigma(W)$ is not fully explained
   • Mechanisms by which different structures lead to different behaviors are insufficiently discussed
3. Superdiffusive Region:
   • Characterization of limiting distribution $L$ is incomplete
   • Only second moments are given; higher moments or complete distribution are unknown
   • Deep reasons for Type-I and Type-II differences are not fully clarified
4. Application Discussion:
   • Lacks discussion of practical application scenarios
   • Implications of these results for understanding real systems are not mentioned

Impact

1. Contribution to the Field:
   • Opens new direction for ERW research (general structures)
   • Provides methodology applicable to other memory-enhanced random walks
   • Enriches applications of Pólya urn theory
2. Practical Value:
   • Strong theoretical content but can provide theoretical foundation for studying diffusion in materials, random processes on networks, etc.
   • Formulas in Section 6 can be directly applied to concrete calculations
3. Reproducibility:
   • Complete proofs are verifiable
   • Formulas for key quantities are explicit
   • Theoretical results are applicable to new structures

Applicable Scenarios

1. Mathematical Research:
   • Limit theorems in probability theory
   • Stochastic process theory
   • Combinatorial random structures
2. Physical Systems:
   • Diffusion processes on lattices
   • Transport phenomena with memory
   • Study of phase transition phenomena
3. Network Science:
   • Random walks on graphs
   • Information propagation models
   • Network exploration algorithms
4. Statistical Physics:
   • Non-Markovian processes
   • Long-range correlated systems
   • Anomalous diffusion

Selected References

• 2 Baur & Bertoin (2016): Elephant random walks and their connection to Pólya-type urns. Physical Review E.
• 5 Bercu & Laulin (2019): On the multi-dimensional elephant random walk. J. Stat. Phys.
• 7 Bertenghi (2022): Functional limit theorems for the multi-dimensional elephant random walk. Stoch. Models.
• 17 Janson (2004): Functional limit theorems for multitype branching processes and generalized Pólya urns. Stochastic Process. Appl. (Core theoretical tool)
• 23 Schütz & Trimper (2004): Elephants can always remember: Exact long-range memory effects in a non-Markovian random walk. Physical Review E. (Origin of ERW)

Overall Assessment: This is a high-quality theoretical paper in probability theory that successfully generalizes ERW theory to general periodic structures, revealing profound effects of structure on asymptotic behavior. It is mathematically rigorous and complete with significant theoretical contributions, providing a foundation for further research in this field. Main weaknesses are insufficient discussion of physical intuition and application scenarios, and incomplete characterization of limiting distributions in the superdiffusive region.