Limit Theorems for step reinforced random walks with regularly varying memory

This paper establishes limit theorems for a generalized step-reinforced random walk with regularly varying memory, proving a law of large numbers and characterizing a phase transition between diffusive and superdiffusive behaviors based on the reinforcement probability $p$ and memory index $\gamma$, while providing novel almost sure and distributional convergence results for the critical regime under linear and time-independent scalings.

The Gist

Imagine a random walker, let's call him "The Elephant," who is trying to decide which way to step next. In a standard random walk, the Elephant flips a coin every time: heads, step right; tails, step left. It's a fresh decision every single time, with no memory of the past.

But this paper studies a much more complex version of The Elephant: The Step-Reinforced Random Walk. Here, The Elephant has a memory. At every step, he has a choice:

1. Recall: He looks back at a random moment from his past, picks the step he took then, and repeats it.
2. Innovate: He ignores his past and takes a brand new, random step.

The "twist" in this paper is how he chooses which past moment to look at. Instead of looking at any past moment with equal chance, his memory is "weighted." He is more likely to remember recent steps, but the exact weight of his memory follows a specific mathematical pattern called "regularly varying." Think of it like a fading photograph: some photos are clearer than others, and the clarity fades at a specific, predictable rate.

The authors, Aritra Majumdar and Krishanu Maulik, wanted to understand: If we watch this Elephant walk for a very long time, what does his path look like?

The Three "Personalities" of the Walk

The paper discovers that The Elephant's behavior changes dramatically depending on two things:

1. How likely he is to recall a past step (called the "recollection probability," $p$).
2. How his memory fades (the "memory sequence," $\mu$).

Based on these factors, the walk falls into three distinct regimes, like three different personalities:

1. The Subcritical Regime (The "Normal" Walker)

• When: The Elephant doesn't recall the past too often, or his memory fades very quickly.
• Behavior: He acts almost like a normal random walker. If you zoom out and look at his path over a long time, it looks like a Gaussian process (a smooth, bell-curve-shaped cloud of possibilities).
• The Scale: His distance from the start grows like the square root of time ($\sqrt{n}$). This is "diffusive" behavior, like a drop of ink spreading slowly in water.

2. The Supercritical Regime (The "Obsessive" Walker)

• When: The Elephant recalls the past very often, or his memory holds onto the past very strongly.
• Behavior: He gets stuck in a loop. He keeps repeating the same few steps over and over. His path becomes very predictable and "super-diffusive" (he moves away from the start much faster than a normal walker).
• The Scale: The paper proves that if you scale his position correctly, he converges to a specific, non-random path multiplied by a random number. It's almost as if he picks a direction early on and just keeps going, with the randomness only affecting how fast he goes, not where he goes.

3. The Critical Regime (The "Edge" Walker)

• When: The Elephant is right on the tipping point between being normal and being obsessive.
• The Big Discovery: This is where the paper makes its most exciting new findings. The authors found that the behavior here depends on the tiny details of how his memory fades.
  • Scenario A (Bounded Memory): If his memory fades just fast enough to be "bounded," he behaves like the Supercritical walker (predictable path, random speed).
  • Scenario B (Unbounded Memory): If his memory is "unbounded" (it fades just a tiny bit slower), he behaves like a Gaussian process (random cloud), but with a new scaling rule.

The "New" Scaling Rules

In previous studies of similar walks, scientists usually used a standard ruler to measure the walk: $\sqrt{n \log n}$.

This paper says: "Wait, that ruler doesn't always work!"

Depending on the specific shape of the Elephant's memory, the correct ruler to measure his distance can be:

• Smaller than $\sqrt{n \log n}$ (he moves slower than we thought).
• Larger than $\sqrt{n \log n}$ (he moves faster than we thought).
• Completely different: In some cases, the path converges to a random multiple of a square root function, not a standard Brownian motion.

The "Time" Problem

There is another clever insight about how we watch the Elephant.

• Traditional View: Scientists often watch the Elephant using "exponential time" (watching him at times like $2^1, 2^2, 2^3...$). This usually makes the math look like a standard Brownian motion (a smooth, wiggly line).
• This Paper's View: The authors argue that for this specific type of memory, the "exponential time" view is artificial and misleading. If you watch him with linear time (watching him at $1, 2, 3, 4...$), you see a different, more natural picture: a path that looks like a random multiple of a square root function ($\sqrt{t}$).

They show that trying to force the "exponential time" view often leads to weird results where the walk doesn't settle into a clear pattern at all.

Summary of the "Aha!" Moments

1. Phase Transitions: The walk isn't just "random" or "predictable." There is a sharp "critical point" where the behavior flips, and the exact nature of the flip depends on the fine details of the memory.
2. New Limits: In the critical zone, the walk can converge to a Gaussian process (random) OR a non-Gaussian process (predictable path with random speed), depending on the memory sequence. This "almost sure" convergence in the critical zone is a brand-new discovery.
3. Better Rulers: The standard "ruler" ($\sqrt{n \log n}$) used in the past is too simple. The correct ruler changes based on the memory sequence and can be much more complex (involving things like $\log \log n$).
4. Linear Time is Better: Watching the walk at a steady, linear pace gives a more natural and useful picture than the traditional exponential time scale.

In short, the paper takes a complex mathematical model of a "memory-heavy" random walker and maps out exactly how his long-term behavior changes. It reveals that the "critical" moment where the behavior shifts is far richer and more varied than anyone previously realized, offering new ways to measure and understand these random journeys.

Technical Summary

Technical Summary: Limit Theorems for Step Reinforced Random Walks with Regularly Varying Memory

Problem Statement
This paper investigates the asymptotic behavior of a generalized class of Step Reinforced Random Walks (SRRW) where the memory mechanism is governed by a regularly varying sequence $\{\mu_n\}$ of index $\gamma > -1$. Unlike the classical Elephant Random Walk (ERW) or standard SRRW, which typically assume uniform memory (selecting any past step with equal probability), this model, termed SRRW-RVM, selects a past epoch $k$ with probability proportional to $\mu_k$. The walker, starting at the origin, takes an initial step from an innovation sequence $\{\xi_n\}$ (i.i.d., mean zero). At each subsequent step $n+1$, with probability $p$ (recollection probability), the walker repeats a past step $X_{\beta_{n+1}}$ chosen according to the memory weights; otherwise, with probability $1-p$, it takes a new step from the innovation sequence. The primary objective is to establish limit theorems (Law of Large Numbers and Functional Central Limit Theorems) for the scaled process $S_{\lfloor nt \rfloor}$ as an element of the space of right-continuous with left limits (r.c.l.l.) functions $D([0, \infty))$ equipped with the Skorohod topology.

Methodology
The authors employ martingale methods to analyze the process. Key steps in the methodology include:

1. Martingale Decomposition: The increment process is decomposed into two martingales, $M_n$ and $L_n$. Specifically, $S_n$ is expressed as a linear combination of $L_n$ (a sum of centered increments) and a weighted sum of $M_k$ (a martingale transform).
2. Asymptotic Analysis of Coefficients: The sequence $\{a_n\}$, defined as a product involving the memory weights and recollection probability, is analyzed. It is shown to be regularly varying with index $-p(\gamma+1)$.
3. Phase Transition Identification: The behavior of the variance of the process is linked to the square summability of the sequence $\{a_n \mu_n\}$. This leads to the definition of a critical point $p_c = \frac{\gamma + 1/2}{\gamma + 1}$.
4. Functional Limit Theorems: The authors prove convergence in distribution to Gaussian processes and almost sure convergence using:
   • Truncation arguments for the Law of Large Numbers (LLN).
   • The Martingale Central Limit Theorem (specifically the Corollary to Theorem 2 of [25]) for weak convergence.
   • Tightness arguments in the Skorohod space, particularly establishing uniform equicontinuity at $t=0$.
   • Karamata's theorem for regularly varying sequences to derive precise scaling rates.

Key Contributions and Results

1. Complete Law of Large Numbers:
   The paper establishes a Strong Law of Large Numbers (SLLN) for the linearly scaled process $S_{\lfloor nt \rfloor}/n$ converging to zero almost surely and in $L^1$ for all $p \in [0, 1)$, assuming only a finite first moment for the innovation sequence. If the innovation has a finite second moment, the convergence holds in $L^2$. This extends previous results which were limited to specific parameter regimes.

2. Phase Transition and Critical Regime Analysis:
   A central contribution is the identification of a phase transition at $p_c = \frac{\gamma + 1/2}{\gamma + 1}$ based on the boundedness of a sequence $\{v_n\}$ (derived from the sum of squared martingale coefficients).

   • Subcritical Regime ($p < p_c$): The sequence $\{v_n\}$ is unbounded. The process, scaled by $\sqrt{n}$, converges weakly to a centered Gaussian process with a specific covariance kernel. This result extends previous findings to the entire range $p \in [0, p_c)$.
   • Supercritical Regime ($p > p_c$): The sequence $\{v_n\}$ is bounded. The process, scaled by $a_n \mu_n$, converges almost surely and in $L^2$ to a random multiple of a deterministic power function. The limit is generally non-Gaussian.
   • Critical Regime ($p = p_c$): This regime is the focus of the paper's novelty. The behavior depends on whether $\{v_n\}$ is bounded or unbounded, which in turn depends on the specific choice of the slowly varying part of the memory sequence $\{\mu_n\}$.
     • If $\{v_n\}$ is unbounded, the process scaled by $\sigma_n$ (a sequence derived from the memory weights) converges weakly to a centered Gaussian process proportional to $\sqrt{t}$.
     • If $\{v_n\}$ is bounded, the process scaled by $a_n \mu_n$ converges almost surely and in $L^2$ to a (possibly non-Gaussian) random multiple of $\sqrt{t}$. The existence of almost sure limits in the critical regime is claimed to be a new result.

3. Novel Scaling and Time Scales:

   • Scaling: The paper demonstrates that the traditional scaling of $\sqrt{n \log n}$ for the critical regime is not universal. Depending on the memory sequence, the scaling $\sigma_n$ can be of smaller or larger order than $\sqrt{n \log n}$.
   • Time Scale: The authors argue against the traditional use of an exponential time scale ($\lfloor n^t \rfloor$) for the critical regime. They show that under linear time scaling ($\lfloor nt \rfloor$) with time-independent space scaling, the process converges to a Gaussian multiple of $\sqrt{t}$. In contrast, the exponential time scale often fails to yield a non-degenerate limit or a Brownian motion limit for general memory sequences, suggesting the linear time scale is more natural for this class of models.

4. Continuity of Limits:
   The paper establishes that the limiting covariance kernel and the limiting process are continuous in the parameter $p$ at the critical point $p_c$ when the appropriate scaling $\sigma_n$ is used, bridging the diffusive subcritical regime and the superdiffusive critical regime.

Significance and Claims
The authors claim that this work provides the first comprehensive analysis of SRRW with regularly varying memory for all values of $p$ and $\gamma$.

• Novelty in Critical Regime: The identification of almost sure convergence in the critical regime (when $\{v_n\}$ is bounded) and the demonstration that the scaling in the critical regime can vary significantly from the standard $\sqrt{n \log n}$ are highlighted as major contributions.
• Methodological Unification: The paper provides a unified argument for the invariance principle that avoids truncation arguments used in previous literature, relying instead on tightness and martingale decompositions.
• Critique of Traditional Scales: The paper challenges the conventional wisdom of using exponential time scales for critical SRRW, providing examples where such scales do not yield Brownian motion limits, and advocating for linear time scales with time-independent space scaling as a more robust framework for these processes.
• Open Problems: The authors raise open problems regarding the process convergence under specific nonlinear time scales and the behavior of memory sequences with specific growth rates (e.g., involving iterated logarithms) in the critical regime.

The results are presented rigorously within the framework of r.c.l.l. functions and the Skorohod topology, ensuring that the limit theorems apply to the entire trajectory of the random walk, not just marginal distributions.