Abstract
We prove that vertex-reinforced random walk on the integers with weight of order $k$ to the power $\alpha$, for $\alpha \in [0, 1/2)$, is recurrent. This confirms a conjecture of Volkov for $\alpha < 1/2$. The conjecture for $\alpha \in [1/2, 1)$ remains open.
Introduction
In a standard random walk, future movement is independent of the past. However, many real-world systems—from ant foraging trails to the strengthening of neural pathways—exhibit "memory," where frequently used paths become more likely to be chosen again. The Vertex-Reinforced Random Walk (VRRW) is a mathematical model for this phenomenon. In a VRRW, the probability of moving to a neighboring site increases based on how many times that neighbor has been visited in the past.
This paper addresses a fundamental question regarding the long-term behavior of these walks on the integer lattice $\mathbb{Z}$: under what conditions does the walk return to every site infinitely often (recurrence) versus eventually wandering off to infinity (transience)?
The Reinforcement Phase Transition
The behavior of a VRRW is determined by the weight function $w(k)$, which dictates the reinforcement strength based on $k$ visits. Previous research established a clear phase transition based on the growth rate of $w(k) \approx k^\alpha$:
- Strong Reinforcement ($\alpha \geq 1$): The walk is "trapped." It eventually restricts itself to a small set of 2 to 5 sites, visiting them exclusively forever.
- Weak Reinforcement ($\alpha < 1$): The walk is known to visit infinitely many distinct sites.
While it was known that weak reinforcement leads to an infinite range, it was not previously proven whether the walk was recurrent or transient for $\alpha < 1$. In 2006, Volkov conjectured that the walk remains recurrent for all $\alpha < 1$. This paper provides the first formal proof of this conjecture for the sub-square-root regime where $\alpha < 1/2$.
Methodology
The authors utilize a sophisticated martingale argument to analyze the walk's trajectory. A martingale is a stochastic process where the conditional expectation of the next value, given the current value, is equal to the current value (a "fair game").
1. The Potential Function
The core of the proof involves defining a sequence of random variables $F_i(v)$ that track the "local time" (the number of visits to each site $v$ up to time $i$). The authors demonstrate that the value of this function at the walk's current position, $F_i(X_i)$, behaves as a supermartingale. This means its expected future value is less than or equal to its current value, providing a mathematical "ceiling" on the process's growth.
2. The Domino Principle
To bridge the gap between the local reinforcement and global behavior, the authors rely on the "domino principle." This principle ensures that the walk does not spend a disproportionate amount of time at the "frontier" (newly discovered sites) before pushing further out. This allows the authors to bound the local time effectively.
3. Proof by Contradiction
The proof concludes by assuming the walk is transient. If the walk were transient, the supermartingale $F_i(X_i)$ would necessarily converge to a finite value. However, the authors show that every time the walk reaches a new vertex, the potential function $F$ increases by a non-negligible positive amount. Since a transient walk would visit infinitely many new vertices, the sum of these jumps would eventually exceed any finite bound, creating a contradiction. Therefore, the walk must be recurrent.
Key Insights
- The $1/2$ Threshold: The value $\alpha = 1/2$ is a significant threshold in probability theory, often appearing in the Law of the Iterated Logarithm. In this context, it represents the limit where the "local" reinforcement is weak enough that the walk's inherent diffusive nature outweighs the attraction of frequently visited sites.
- Harmonicity and Monotonicity: The proof cleverly balances the movement of the walk (harmonicity) against the updating of weights (monotonicity). By showing the potential function is harmonic on the graph and decreases as weights increase, the supermartingale property is preserved.
- Robustness of Recurrence: The result demonstrates that even with significant reinforcement, the fundamental behavior of a 1D random walk is surprisingly robust, provided the reinforcement grows slower than the square root of the visit count.
Conclusion and Future Work
This paper confirms Volkov’s conjecture for $\alpha \in [0, 1/2)$, proving that such walks are almost surely recurrent. However, two major challenges remain:
- The $[1/2, 1)$ Gap: When reinforcement grows faster than the square root but slower than linear, the current potential function jumps are not large enough to force a contradiction. The behavior in this regime remains an open mystery.
- Higher Dimensions: This analysis is specific to the one-dimensional lattice $\mathbb{Z}$. VRRW behavior on $\mathbb{Z}^d$ for $d \geq 2$ involves much more complex geometry and remains a primary frontier in probability research.
Summary updated