2025-11-16T02:16:12.119388

A central limit theorem for unbalanced step-reinforced random walks

Hu, Dong

In this paper, we study a class of unbalanced step-reinforced random walks that unifies the elephant random walk, the positively step-reinforced random walk, and the negatively step-reinforced random walk. By establishing a connection with bond percolation on random recursive trees, these processes can be represented as randomly weighted sums of independent and identically distributed random variables. We first derive normal and stable central limit theorems for such randomly weighted sums, and then apply these results to obtain a unified central limit theorem for unbalanced step-reinforced random walks.

academic

A central limit theorem for unbalanced step-reinforced random walks

Basic Information

Paper ID: 2510.10898
Title: A central limit theorem for unbalanced step-reinforced random walks
Authors: Zhishui Hua (University of Science and Technology of China), Liang Dong (Suzhou University of Technology)
Classification: math.PR (Probability Theory)
Publication Date: October 13, 2024 (arXiv preprint)
Paper Link: https://arxiv.org/abs/2510.10898

Abstract

This paper investigates a class of unbalanced step-reinforced random walks that unifies elephant random walks, positively step-reinforced random walks, and negatively step-reinforced random walks. By establishing connections with bond percolation on random recursive trees, these processes can be represented as randomly weighted sums of independent and identically distributed random variables. The paper first derives normal and stable central limit theorems for such randomly weighted sums, then applies these results to obtain unified central limit theorems for unbalanced step-reinforced random walks.

Research Background and Motivation

Problem Background

Importance of step-reinforced random walks: Step-reinforced random walks are important objects of study in probability theory, possessing memory properties where the choice of future steps depends on historical paths.
Limitations of existing models:
- Elephant random walks (ERW) introduced by Schütz and Trimper have received widespread attention in recent years
- Positively and negatively step-reinforced random walks were introduced by Simon and Bertoin respectively
- These models have been studied independently, lacking a unified theoretical framework
Theoretical gaps:
- Corresponding limit theorems when ξ₁ belongs to the domain of attraction of normal distributions have not been established
- The case when ξ₁ belongs to the domain of attraction of stable distributions also requires investigation
- A unified method for handling different types of step-reinforced random walks is lacking

Research Motivation

This paper aims to address the above theoretical gaps by introducing a unified framework for unbalanced step-reinforced random walks and establishing more general central limit theorems.

Core Contributions

Unified framework: Proposes an unbalanced step-reinforced random walk model that unifies elephant random walks, positively step-reinforced random walks, and negatively step-reinforced random walks.
Innovative representation method: Establishes connections through bond percolation on random recursive trees, representing these processes as randomly weighted sums.
General central limit theorems: Establishes unified central limit theorems applicable to domains of attraction of normal and stable distributions.
Theoretical tools: Develops central limit theorems for general randomly weighted sums (Theorems 2.1-2.3) with independent theoretical value.

Methodology Details

Problem Formulation

Study the asymptotic behavior of unbalanced step-reinforced random walks $T_n = \sum_{k=1}^n X_k$ , where:

X_{U_n}, & \text{with probability } rp \\ -X_{U_n}, & \text{with probability } (1-r)p \\ \xi_n, & \text{with probability } 1-p \end{cases}$$ Here $p, r \in [0,1]$ are fixed parameters, $\{U_n\}$ is a sequence of independent uniformly distributed random variables, and $\{\xi_k\}$ is a sequence of independent and identically distributed random variables. ### Model Architecture #### 1. Construction of unbalanced step-reinforced random walks - **Parameters**: $p \in (0,1)$ (reinforcement probability), $r \in [0,1]$ (balance parameter) - **Special cases**: - $p=1$ and $P(\xi_1=1)=s$: elephant random walk - $r=1$: positively step-reinforced random walk - $r=0$: negatively step-reinforced random walk #### 2. Random recursive tree representation Establish connections with random recursive trees through the following steps: - Construct vertex set $\{1,2,\ldots,n\}$ and edge set $\{(U_k,k):k=2,\ldots,n\}$ - Use Bernoulli bond percolation: edge $(U_k,k)$ is open with probability $1-p$ - Assign weights to each connected component, forming a randomly weighted sum representation #### 3. Key technical innovations **Randomly weighted sum representation**: $$T_n = \sum_{k=1}^n W_{nk}\xi_k$$ where weights $W_{nk}$ are determined by the percolation process, satisfying $W_{nk} \stackrel{d}{=} T^0_{N_k(n)}$, where $T^0_k$ is a special elephant random walk. ### Technical Innovations 1. **Unified treatment framework**: Through parameters $(p,r)$, unifies the treatment of multiple step-reinforced random walks, avoiding the complexity of separate investigations. 2. **Application of percolation theory**: Innovatively uses bond percolation on random recursive trees to represent step-reinforced processes, establishing such connections for the first time. 3. **General conditions**: Handles the general case where ξ₁ belongs to the domain of attraction of α-stable distributions ($\alpha \in (0,2]$), rather than being limited to finite variance cases. ## Main Theoretical Results ### Theorem 1.2 (Main Result) Assume $\alpha \in (0,2]$, $p \in (0,1)$, $r \in [0,1]$ and $(2r-1)\alpha p < 1$. If $\{\xi_k\}$ satisfies: $$\frac{1}{a_n}\sum_{k=1}^n \xi_k \stackrel{d}{\to} S$$ where $S$ is a symmetric α-stable random variable, then: $$\frac{T_n}{a_n} \stackrel{d}{\to} (c(\alpha,p,r))^{1/\alpha}S$$ where: $$c(\alpha,p,r) = \frac{1-p}{p}\sum_{k=1}^{\infty} E(|T^0_k|^{\alpha})B(k, 1+1/p)$$ ### Central Limit Theorems for Randomly Weighted Sums #### Theorem 2.1 (Normal case) Under the conditions: - (A1) $\sum_{k=1}^n W_{nk}^2/n \stackrel{P}{\to} 1$ - (A2) $\max_{1 \leq k \leq n} |W_{nk}|/\sqrt{n} \stackrel{P}{\to} 0$ we have: $\frac{1}{\sqrt{n}}\sum_{k=1}^n W_{nk}\xi_k \stackrel{d}{\to} N(0,1)$ #### Theorem 2.2 (General normal domain of attraction) Under the conditions: - (A3) $\frac{1}{n}\sum_{k=1}^n W_{nk}^2 \stackrel{d}{\to} W$ - (A4) $\lim_{c \to \infty}\sup_n \frac{1}{n}\sum_{k=1}^n E(W_{nk}^2I(|W_{nk}|>c)) = 0$ If $\sum_{k=1}^n \xi_k/a_n \stackrel{d}{\to} N(0,1)$, then: $$\frac{1}{a_n}\sum_{k=1}^n W_{nk}\xi_k \stackrel{d}{\to} \sqrt{W}N$$ #### Theorem 2.3 (Stable distribution case) For α-stable distributions, corresponding limit theorems are established under appropriate conditions. ## Proof Strategy ### Overall Approach 1. **Representation step**: Represent $T_n$ as a randomly weighted sum $\sum_{k=1}^n W_{nk}\xi_k$ 2. **General theory**: Establish central limit theorems for randomly weighted sums 3. **Specific application**: Verify that weights satisfy required conditions and apply general results ### Key Lemmas #### Lemma 4.1 Conditional on $(N_1(n),\ldots,N_n(n)) = (m_1,\ldots,m_n)$, the weights $\{W_{nj}\}$ are independent and $W_{nj} \stackrel{d}{=} T^0_{m_j}$. #### Lemma 4.2 For $\beta \in (0,4]$: $$E(|T^0_n|^{\beta}) = O((a_r(n))^{\beta/2})$$ where: $$a_r(n) := \begin{cases} n, & r < 3/4 \\ n\log n, & r = 3/4 \\ n^{4r-2}, & r > 3/4 \end{cases}$$ #### Lemma 4.3 Define $Z_l(n) = \sum_{k=1}^n k^l \nu_k(n)$, then: $$E(Z_l(n)) \asymp b_l(n)$$ where: $$b_l(n) := \begin{cases} n^{lp}, & lp > 1 \\ n\log n, & lp = 1 \\ n, & lp < 1 \end{cases}$$ ## Experimental Verification This paper is purely theoretical research and does not involve numerical experiments. Verification of theoretical results is conducted through: 1. **Special case verification**: Verifies that when $\alpha=2$, the results of Aguech et al. are recovered 2. **Comparison with known results**: Compares with results from Businger, Bertoin, and others 3. **Consistency checks**: Ensures consistency of results under different parameter settings ## Related Work ### Historical Development 1. **Elephant random walks**: Introduced by Schütz and Trimper (2004), subsequently widely studied 2. **Step-reinforced random walks**: Work by Simon (1955) and Bertoin et al. 3. **Randomly weighted sums**: Classical results by Mason and Newton et al. ### Positioning of this paper's contributions - Unifies previously scattered research - Extends to more general distribution classes - Provides new technical tools ## Conclusions and Discussion ### Main Conclusions 1. Establishes unified central limit theorems for unbalanced step-reinforced random walks 2. Develops general theory for handling randomly weighted sums 3. Provides new analytical perspectives through percolation theory ### Theoretical Significance - **Unification**: Provides a unified framework for handling multiple types of step-reinforced random walks - **Generality**: Extends to cases where ξ₁ belongs to domains of attraction of stable distributions - **Methodology**: Innovative combination of percolation theory and random walks ### Limitations 1. **Critical cases**: Primarily focuses on the subcritical region $(2r-1)\alpha p < 1$ 2. **Symmetry**: Requires ξ₁ to belong to the domain of attraction of symmetric stable distributions 3. **Technical conditions**: Certain technical conditions may be further relaxed ### Future Directions 1. Study critical and supercritical cases 2. Extend to non-symmetric distributions 3. Generalization to multidimensional cases 4. Applications to other reinforced processes ## In-Depth Evaluation ### Strengths 1. **Theoretical innovation**: First to establish deep connections between percolation theory and step-reinforced random walks 2. **Unified framework**: Elegantly unifies multiple important random walk models 3. **Technical contributions**: Central limit theorems for randomly weighted sums have independent value 4. **Rigor**: Detailed proofs with appropriate technical handling ### Technical Highlights 1. **Representation theorem**: Clever representation through percolation processes is the key innovation 2. **Moment estimates**: Precise asymptotic analysis of $E(|T^0_n|^{\beta})$ 3. **Condition verification**: Systematic verification of applicability conditions for randomly weighted sum theory ### Shortcomings 1. **Scope of application**: Limited to subcritical region; critical and supercritical cases not addressed 2. **Symmetry requirement**: Symmetry requirements on distributions may be overly restrictive 3. **Computational complexity**: Specific calculation of constant $c(\alpha,p,r)$ is relatively complex ### Impact Assessment 1. **Theoretical value**: Provides important tools for step-reinforced random walk theory 2. **Methodological contribution**: Application of percolation theory may inspire other research 3. **Subsequent research**: Lays foundation for further investigation of critical cases ### Applicable Scenarios - Modeling random processes with memory properties - Random walks on complex networks - Analysis of exploration strategies in reinforcement learning - Path-dependent phenomena in financial markets ## References The paper cites 33 relevant references covering important works in random walks, percolation theory, limit theorems, and other fields, with comprehensive literature review. --- **Overall Assessment**: This is a high-quality theoretical probability paper that solves important theoretical problems through innovative technical methods, providing a unified analytical framework for step-reinforced random walks. Although there are certain limitations in scope of application, its theoretical contributions and methodological value are significant.