Vertex-reinforced random walk on <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mi mathvariant="double-struck">Z</mml:mi> </mml:math> with sub-square-root weights is recurrent

Jun Chen, Gady Kozma

TL;DR

This paper proves that a specific type of "vertex-reinforced random walk" on a line, where the probability of revisiting a site depends on how many times it's been visited with a sub-square-root weight, is guaranteed to eventually visit every site infinitely often. This confirms a long-standing conjecture for a specific range of reinforcement strengths.

What Problem Does This Paper Address?

Imagine a random walk on a line (like the integers, $\mathbb{Z}$). In a standard random walk, the probability of moving left or right from your current position is always 50/50. Now, consider a "reinforced" random walk: the more times you visit a particular location (vertex), the more likely you are to return there. This is called "vertex-reinforced random walk" (VRRW).

The paper focuses on a specific type of reinforcement where the "attractiveness" of a vertex increases with its visit count, but not too quickly. Specifically, the weight assigned to a vertex visited $k$ times is proportional to $k^\alpha$, where $\alpha$ is a parameter. A key question for these walks is whether they are "recurrent" (meaning they will visit every site infinitely often with probability 1) or "transient" (meaning they will visit each site only a finite number of times). For linear VRRW, it was known that the walk visits only a finite number of sites. However, for non-linear VRRW with weights like $k^\alpha$, a phase transition was observed: for $\alpha > 1$, the walk is transient; for $\alpha = 1$, it visits a finite number of sites; and for $\alpha < 1$, it visits infinitely many sites. The crucial open question was whether, in the $\alpha < 1$ case, the walk is recurrent (visits every site infinitely often). This paper addresses this by proving recurrence for $\alpha < 1/2$.

Methods

The authors employ a combination of techniques to prove their result. The core of their argument relies on a martingale approach. They define a sequence of random variables, $F_i(v)$, which are related to the local times of the walk up to time $i$ at vertex $v$. They show that this sequence, under certain conditions, forms a supermartingale. A supermartingale is a sequence whose expected future value, given the present, is less than or equal to the present value. This property is crucial because it implies that the sequence converges to a finite random variable.

To bridge the gap between the convergence of this supermartingale and the recurrence of the walk, they use two key lemmas:

  1. Lemma 1: Establishes that the defined $F_i(v)$ sequence is indeed a supermartingale. This involves showing that the walk's transition probabilities, when applied to $F_i(v)$, result in a decrease in expectation (harmonicity) and that $F_i(v)$ itself tends to decrease over time (monotonicity).
  2. Lemma 2: This lemma is critical for the $\alpha < 1/2$ condition. It shows that the walk, with high probability, does not visit nearby sites too many times before moving to a new site. This "domino principle" is essential for preventing the walk from getting "stuck" in a small region.

Finally, they leverage a 0-1 law previously proven by Schapira, which states that for VRRW with weights $k^\alpha$ where $\alpha < 1/2$, the walk is either recurrent or transient. By showing that transience leads to a contradiction with the supermartingale convergence, they conclude that the walk must be recurrent.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The Power of Sub-Square-Root Reinforcement: The paper highlights that when the reinforcement strength ($\alpha$) is "weak enough" (specifically, less than 1/2), the random walk's tendency to revisit sites is not strong enough to prevent it from eventually exploring the entire line.
  • Martingales as a Tool for Random Walks: The successful application of martingale theory to prove properties of complex random processes like VRRW demonstrates its versatility and power in this field.
  • Bridging Local Behavior to Global Properties: The paper elegantly connects local properties of the walk (how it moves between adjacent sites, influenced by local times) to its global behavior (visiting every site on the infinite line). Lemma 2 is key here, ensuring that local "stickiness" doesn't become global.
  • Confirmation of a Conjecture: The work provides a significant step towards resolving a conjecture by Volkov regarding the recurrence behavior of VRRW, solidifying understanding for a specific parameter regime.

Key Results

The main result is the proof that a vertex-reinforced random walk on $\mathbb{Z}$ with a weight function $w(k) \approx k^\alpha$ for $\alpha \in [0, 1/2)$ is recurrent. This means that, with probability 1, the walk will visit every integer on the line infinitely many times. This confirms a conjecture by Volkov for the case $\alpha < 1/2$.

Limitations and Future Work

The paper explicitly states that the conjecture for $\alpha \in [1/2, 1)$ remains open. This is a significant limitation, as the techniques used in this paper are tailored to the $\alpha < 1/2$ regime. Future work would naturally focus on extending these results to the remaining range of $\alpha$, which is expected to be more challenging. The authors also mention that their Lemma 1 holds more generally for any self-interacting process with increasing vertex weights on any tree, suggesting potential for broader applications of their methods.

Summary updated

Abstract

We prove that vertex-reinforced random walk on <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mi mathvariant="double-struck">Z</mml:mi> </mml:math> with weight of order <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:msup> <mml:mrow> <mml:mi>k</mml:mi> </mml:mrow> <mml:mrow> <mml:mi>α</mml:mi> </mml:mrow> </mml:msup> </mml:math> , for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mi>α</mml:mi> <mml:mo>∈</mml:mo> <mml:mo stretchy="false">[</mml:mo> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">/</mml:mo> <mml:mn>2</mml:mn> <mml:mo stretchy="false">)</mml:mo> </mml:math> , is recurrent. This confirms a conjecture of Volkov for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mi>α</mml:mi> <mml:mo>&lt;</mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">/</mml:mo> <mml:mn>2</mml:mn> </mml:math> . The conjecture for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mi>α</mml:mi> <mml:mo>∈</mml:mo> <mml:mo stretchy="false">[</mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">/</mml:mo> <mml:mn>2</mml:mn> <mml:mo>,</mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> </mml:math> remains open.
BibTeX
@inproceedings{chen2014vertex,
  author = {Jun Chen and Gady Kozma},
  title = {{Vertex-reinforced random walk on <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mi mathvariant="double-struck">Z</mml:mi> </mml:math> with sub-square-root weights is recurrent}},
  booktitle = {Comptes},
  year = {2014},
  doi = {10.1016/j.crma.2014.03.019},
}

Loading related content...

Figure