An Information-theoretic Analysis of Edge-reinforced Random Walks

Qinghua (Devon) Ding, Venkat Anantharam · 2026

Read An Information-theoretic Analysis of Edge-reinforced Random Walks by Qinghua (Devon) Ding, Venkat Anantharam (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-21853.txt.

Introduction

Qinghua Ding and Venkat Anantharam study information quantities of edge-reinforced random walks on finite graphs, where each traversed edge gains one unit. On a finite graph such a walk is a random-environment walk, whose law is the magic formula for initial weights. They derive an annealed entropy-rate representation and a closed-form environment-level Kullback-Leibler divergence formula and trajectory-level divergence bounds converging toward that level. They serve two-point testing for trajectories, the Stein exponent, and should matter for identity and closeness testing.

Catalog record

CREATORQinghua (Devon) Ding, Venkat Anantharam
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE107329
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.21853

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An Information-theoretic Analysis of Edge-reinforced Random Walks Qinghua (Devon) Ding, Venkat Anantharam Abstract Reinforced random walks are random walks on graphs whose transition probabilities along edges from a vertex are proportional to the weights of those edges, but where the weight of an edge evolves in a way that depends on the past traversals across it. In an edge-reinforced random walk (ERRW) the weight of an edge increases by 1 1 whenever that edge is traversed, in either direction. On a finite graph, an ERRW admits a remarkable representation as a random walk in a random environment. The law of the environment is given by the so-called magic formula [ 10 , 14 ] , with this law depending on the initial edge weights. This representation provides a natural route for studying statistical properties of ERRWs [ 6 , 20 , 19 ] . This work focuses on various information-theoretic quantities associated with ERRWs on finite graphs, motivated in part by the problem of statistically distinguishing between different ERRW models from observed trajectories. In particular, we study the entropy rate of an ERRW. We also study the Kullback–Leibler divergence (KL divergence) between two ERRW environment laws, and the KL divergence between the corresponding finite-trajectory distributions. Leveraging structural properties of the underlying random environment [ 20 , 19 ] , we derive an annealed representation of the entropy rate, a closed-form formula for the environment-level KL divergence, and quantitative bounds on the convergence of trajectory-level KL divergence toward environment-level KL divergence. These information-theoretic quantities are motivated by the two-point hypothesis testing problem for ERRW trajectories, and in particular by the associated Stein exponent. We also expect them to play a fundamental role in the study of other testing problems for ERRWs, including identity testing and closeness testing. 1 Introduction An edge-reinforced random walk (ERRW) is a random walk on a graph whose transition probabilities along an edge from a vertex are proportional to the weights of those edges, and where the weight of an edge increases by 1 whenever that edge is traversed, in either direction. Introduced in the work of Coppersmith and Diaconis, the model has since been studied from several points of view, including its intimate connections with the concept of partial exchangeability; Bayesian statistics for reversible Markov chains; and as an example of a random walk in a random environment; see, for example, [ 10 , 18 , 6 , 15 , 14 ] . On finite graphs, a basic structural fact is that ERRW has the same law as a mixture of reversible Markov chains, or equivalently as a random walk in a random environment, with an explicit mixing measure given by the so-called magic formula [ 10 , 14 ] . This representation places ERRW in the broader framework of de Finetti-type results for Markov chains and reversible processes [ 5 , 6 ] . This random-environment point of view has also led to the further developments relating ERRW to the vertex-reinforced jump process (VRJP) and to random Schrödinger operators and the supersymmetric hyperbolic sigma model [ 20 , 19 ] . We refer the reader to the survey article of Merkl and Rolles [ 15 ] for background on linearly edge-reinforced random walk and its principal structural properties. The purpose of the present paper is to study several information-theoretic quantities associated with ERRW on finite graphs. The main objects of interest are the entropy rate of the reinforced walk, the Kullback–Leibler divergence (KL divergence) between two ERRW environment laws, and the KL divergence between the corresponding finite-trajectory laws. These quantities arise naturally when one considers statistical questions for ERRW trajectories. In particular, the trajectory-level KL divergence governs the asymptotic exponent in two-point hypothesis testing, through Stein’s lemma. More broadly, the same quantities should be relevant for other testing problems for ERRW, such as identity testing and closeness testing. Our main results are as follows. • Entropy rate of ERRW. We prove that the entropy rate of ERRW admits an annealed representation in terms of the mixing measure. We derive an explicit formula for the entropy rate. We also provide an upper bound for it, expressed via the normalizing constant in the magic formula. • KL divergence between environment laws. We derive a closed-form formula for the environment-level KL divergence, i.e. the divergence between the mixing measures of ERRW when started from two different initial edge weights. This is based on the fact that the family of ERRW mixing measures forms a canonical exponential family. We show that this formula admits a natural probabilistic interpretation through the Sabot-Tarrès-Zheng field representation (STZ-field representation) [ 19 ] : the underlying edge Gamma field factorizes into an ERRW environment component and independent Gamma fields on the vertices, so that the KL identity appears as the net contribution of the edge-Gamma and vertex-Gamma terms. For details see Section 5 . • Convergence of trajectory-level KL divergences. We prove that the trajectory-level KL divergence converges to the environment-level KL divergence as T\to\infty at a sublinear convergence rate on general graphs, with a tight characterization in the urn ( n -star) case. The main technical difficulty is the derivation of quantitative bounds on the random environment. We address this by combining a combinatorial lemma with analytic control of the normalized environment over the simplex, and concentration estimates for finite reversible Markov chains. The results of the paper support the following general point of view. For ERRW on finite graphs, the random environment, especially at the level of the STZ-field [ 19 ] , is the natural object in terms of which entropy and KL divergence are most naturally understood. In this sense, the random-environment representation is not only a structural description of the model, but also the appropriate framework for its information-theoretic analysis. The paper is organized as follows. In Section 2 , we review the most relevant earlier work. In Section 3 , we recall the definition of an ERRW and its random-environment representation. In Section 4 , we study the entropy rate of ERRW. In Section 5 , we analyze the KL divergence between ERRW environment laws. In Section 6 , we study the KL divergence between finite trajectory laws and its relation to posterior updating. We then conclude with a discussion of several open problems. 2 Related Work Linearly edge-reinforced random walk was introduced by Coppersmith and Diaconis [ 3 ] and has been studied extensively on both finite and infinite graphs. On finite graphs, a basic structural result is that ERRW has the same law as a mixture of reversible Markov chains, or equivalently as a random walk in a random environment; this representation was established by Keane and Rolles [ 10 ] , and the corresponding mixing measure was later identified explicitly through the magic formula by Merkl, Öry, and Rolles [ 10 , 14 ] . The survey article [ 15 ] provides further background on linearly edge-reinforced random walk and its principal structural properties. A second line of work concerns the statistical interpretation of ERRW. Rolles [ 18 ] showed that ERRW arises naturally in the Bayesian analysis of reversible Markov chains, and Diaconis and Rolles developed the corresponding conjugate-prior framework for reversible transition matrices

Read the complete text