The *-Edge-Reinforced Random Walk

Sergio Bacallado, Christophe Sabot, Pierre TarrèsarXiv 2021 · DOI · arXiv

Abstract

We define a linearly reinforced process called the $\star$-Edge-Reinforced Random Walk ($\star$-ERRW), which serves as a Yaglom reversible, non-reversible extension of the classic Edge-Reinforced Random Walk (ERRW) introduced by Coppersmith and Diaconis in 1986. This family of processes generalizes the $r$-dependent ERRW and, under specific assumptions on initial weights, is partially exchangeable in the sense of Diaconis and Freedman (1980). Consequently, it can be viewed as a random walk in a random environment. Our main result provides an explicit expression for the mixing law, extending the celebrated "magic formula" from the case of mixtures of reversible Markov chains to the broader class of mixtures of Yaglom reversible Markov chains.

Introduction

Since its inception, the Edge-Reinforced Random Walk (ERRW) has been a cornerstone of probability theory, particularly in the study of self-interacting processes. The ERRW is characterized by a "rich-get-richer" dynamic where the probability of traversing an edge increases each time it is visited. A defining feature of the classic ERRW is its partial exchangeability, which allows it to be represented as a mixture of reversible Markov chains.

However, many real-world systems—such as molecular dynamics or higher-order language models—are inherently non-reversible. While these systems do not satisfy standard detailed balance, they often exhibit Yaglom reversibility, a generalized symmetry where time-reversal is coupled with a spatial transformation (an involution). This paper addresses the gap in reinforced walk literature by introducing the $\star$-ERRW, a model that captures these non-reversible symmetries while maintaining the mathematical elegance and explicit mixing laws of the original ERRW.

The $\star$-ERRW Framework

The $\star$-ERRW is constructed on a directed graph endowed with an involution $\star$ (a mapping where applying it twice returns the original state) on its vertices and edges.

Reinforcement Rule

Unlike the standard ERRW, which reinforces a single undirected edge, the $\star$-ERRW reinforces a pair of directed edges: the edge $(i, j)$ and its "dual" $(j^\star, i^\star)$. By tying the reinforcement of an edge to its Yaglom-dual, the authors preserve the exchangeability property even when the resulting walk is non-reversible. This coupled reinforcement ensures that the process respects the underlying symmetry of the graph's involution.

Continuous-Time Perspective

To derive the properties of the walk, the authors utilize a continuous-time version called the $\star$-Vertex Reinforced Jump Process ($\star$-VRJP). By employing independent Gamma-distributed conductances and considering the "annealed" version of this jump process, they demonstrate its equivalence to the $\star$-ERRW. This connection is technically vital, as it allows the use of the Matrix Tree Theorem and complex Gaussian integration over manifolds of possible edge weights to find closed-form solutions.

Key Results and the "Magic Formula"

The paper's primary contribution is the proof of partial exchangeability and the derivation of the mixing law.

  1. Partial Exchangeability: The authors prove that if the initial weights satisfy a specific "divergence" condition relative to the starting point, the $\star$-ERRW is partially exchangeable. This means the process is equivalent to a random walk in a random environment (RWRE).
  2. The Extended Magic Formula: One of the most famous results in reinforced walks is the "magic formula" for the mixing measure. This paper extends this formula (Theorem 1) to the $\star$-ERRW. The new formula provides the exact probability density function for the asymptotic occupation measure of the edges. Notably, the determinantal term $\sqrt{D(y)}$ in the original formula is replaced by a term involving a non-symmetric matrix representing the graph's structure, summed over spanning trees directed toward a root.
  3. Characterization: The $\star$-ERRW is shown to be a mixture of Yaglom reversible Markov chains, providing a complete description of the process's long-term behavior.

Implications and Applications

The $\star$-ERRW acts as a mathematical bridge between several previously distinct models. It generalizes the $r$-dependent ERRW and provides a link to Random Walks in random Dirichlet Environments (RWDE).

For statisticians, the $\star$-ERRW provides a conjugate prior for the Bayesian analysis of non-reversible Markov chains. This is particularly significant for researchers modeling processes with memory that are not strictly reversible, offering a tractable way to handle non-reversible transition matrices in a Bayesian framework.

Limitations and Future Work

While the $\star$-ERRW expands the scope of reinforced walks, several constraints remain. The results currently assume the underlying graph is strongly connected. Additionally, the authors note that the continuous-time $\star$-VRJP is not partially exchangeable without a specific, non-trivial randomization of the initial local times.

Future research may focus on the localization properties of these walks—determining if they become "trapped" in small regions of the graph similarly to reversible ERRWs—and identifying the most natural involutions for complex, real-world networks beyond de Bruijn graphs.

Conclusion

By extending the Coppersmith-Diaconis framework to Yaglom reversible processes, this paper demonstrates that partial exchangeability and explicit mixing laws are not exclusive to reversible systems. The $\star$-ERRW provides a robust new tool for understanding how reinforcement and non-reversible symmetries interact in stochastic processes.

Summary updated

Abstract

We define a linearly reinforced process called the *-Edge-Reinforced Random\nWalk (*-ERRW ) which can be seen as a Yaglom reversible, hence non-reversible,\nextension of the Edge-Reinforced Random Walk (ERRW) introduced by Coppersmith\nand Diaconis in 1986. This family of processes also generalizes the r-dependent\nERRW introduced by Bacallado (2009). Under some assumptions on the initial\nweights, the *-ERRW is partially exchangeable in the sense of Diaconis and\nFreedman (1980), and thus it is a random walk in a random environment. The main\nresult of the paper gives the explicit expression of the mixing law, hence\nextending the "magic formula" of Coppersmith and Diaconis from the case of\nmixtures of reversible Markov chains to the case of mixtures of Yaglom\nreversible Markov chains.\n
BibTeX
@misc{bacallado2021edge,
  author = {Sergio Bacallado and Christophe Sabot and Pierre Tarrès},
  title = {{The *-Edge-Reinforced Random Walk}},
  year = {2021},
  eprint = {2102.08984},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2102.08984},
}
Figure