Limit behavior of linearly edge-reinforced random walks on the half-line

Technical Summary: Limit Behavior of Linearly Edge-Reinforced Random Walks on the Half-Line

Problem Statement
This paper investigates the almost sure limit behavior of linearly edge-reinforced random walks (LERRW) on the half-line $\mathbb{Z}_+$. The study focuses on the recurrent regime of the process, specifically examining how the initial weights assigned to edges influence the asymptotic growth of the walker's position $X_n$.

The authors consider a specific class of initial weights where the edge $\{x, x+1\}$ has an initial weight $w_0(x) = x^\alpha \ln^\beta x$ for $x \ge 2$, and $w_0(0)=w_0(1)=1$. The reinforcement parameter is $\delta > 0$, meaning that every time an edge is traversed, its weight increases by $\delta$. This work extends previous research by Takei [26], who analyzed the case where the logarithmic term was absent (i.e., $\beta = 0$). The primary objective is to determine whether the logarithmic factor $\ln^\beta x$ alters the limit behavior of the walk in the recurrent regime and, if so, to characterize the precise order of oscillation.

Methodology
The paper employs a combination of probabilistic techniques rooted in the equivalence between LERRW and Random Walks in Random Environments (RWRE).

1. RWRE Representation: Following the approach of Coppersmith and Diaconis and subsequent works, the LERRW is represented as a mixture of Markov chains. Specifically, the transition probabilities of the LERRW are expressed as the expectation of transition probabilities of a random walk $Y$ in a random environment defined by independent Beta-distributed variables.
2. Potential Theory and Resistance: For the associated random walk $Y$ in a fixed environment, the authors utilize standard potential theory. They define effective resistance and conductance terms ($\gamma_x$ and $\pi_x$) to analyze the expected hitting times $E[\tau_x]$.
3. Asymptotic Analysis of Sums: A significant portion of the technical work involves deriving the asymptotic behavior of sums involving the initial weights. The authors apply discrete versions of Karamata's theorem and Stolz-Cesàro limits to evaluate sums of the form $\sum i^\rho (\ln i)^\beta$ and their reciprocals.
4. Strong Laws for Sums of Independent Variables: To handle the random environment, the authors analyze the sum $S_x = \ln \gamma_x$, which represents the log-ratio of transition probabilities. They compute the expectation $E[S_x]$ and variance $V[S_x]$ using properties of the digamma function $\Psi(z)$. By applying Kolmogorov's strong law of large numbers, they establish the almost sure asymptotic behavior of $S_x$.
5. Inversion Estimates: The final step involves inverting the growth rates of the hitting times to derive the growth rates of the position $X_n$ (or $Y_n$ in the environment), utilizing elementary inversion estimates for functions of the form $\exp(cx^{1-\alpha}(\ln x)^{-\beta})$.

Key Contributions and Results
The paper provides a complete characterization of the limit behavior for the LERRW under the initial weights $w_0(x) = x^\alpha \ln^\beta x$. The results are categorized by the parameters $\alpha$ and $\beta$:

• Case $\alpha < 1$:
  The authors prove that the term $\ln^\beta x$ influences the limit behavior for any $\beta \neq 0$. The precise order of oscillation is given by:
  $$\limsup_{n \to \infty} \frac{X_n}{(K(\alpha, \beta, \delta)(1-\alpha)^{-\beta} \ln n (\ln \ln n)^\beta)^{1/(1-\alpha)}} = 1 \quad \text{a.s.}$$
  Here, $K(\alpha, \beta, \delta)$ is a constant depending on the parameters. This result generalizes Takei's finding for $\beta=0$, showing that the logarithmic factor introduces a $(\ln \ln n)^\beta$ correction term.

• Case $\alpha = 1$:
  The behavior depends critically on the sign of $\beta$:

  • If $\beta < 0$: The logarithmic term significantly alters the growth rate, leading to an exponential-type growth:
    $$\limsup_{n \to \infty} \frac{X_n}{\exp((\ln n)^{(1-\varepsilon)/(1-\beta)})} = +\infty \quad \text{and} \quad \lim_{n \to \infty} \frac{X_n}{\exp((\ln n)^{(1+\varepsilon)/(1-\beta)})} = 0 \quad \text{a.s.}$$
  • If $0 < \beta \le 1$: The limit behavior remains unchanged from the un-reinforced case (and the $\beta=0$ case), behaving like a standard random walk with diffusive scaling:
    $$\limsup_{n \to \infty} \frac{X_n}{n^{(1-\varepsilon)/2}} = +\infty \quad \text{and} \quad \lim_{n \to \infty} \frac{X_n}{n^{(1+\varepsilon)/2}} = 0 \quad \text{a.s.}$$

• Un-reinforced Case ($\delta = 0$):
  The paper also establishes limit theorems for the un-reinforced random walk with the same initial weights, providing a baseline for comparison. These results show how the initial weights alone dictate the recurrence and growth rates in the absence of reinforcement.

Significance
The paper claims to extend the results of Takei [26] by incorporating a logarithmic factor into the initial edge weights. The primary significance lies in demonstrating that the logarithmic term $\ln^\beta x$ is not negligible; it fundamentally changes the limit behavior of the LERRW in the recurrent regime when $\alpha < 1$ (for any $\beta \neq 0$) and when $\alpha = 1$ (specifically for $\beta < 0$).

The authors note that their arguments follow the general strategy of Takei [26] but require specific modifications to handle the additional logarithmic complexity. The work contributes to the broader understanding of phase transitions and limit theorems for reinforced random walks on acyclic graphs, refining the understanding of how initial conditions interact with reinforcement mechanisms to determine the long-term trajectory of the process.