An Information-theoretic Analysis of Edge-reinforced Random Walks

Technical Summary: An Information-theoretic Analysis of Edge-reinforced Random Walks

Problem Statement
This work investigates fundamental information-theoretic quantities associated with Edge-Reinforced Random Walks (ERRWs) on finite graphs. An ERRW is a stochastic process where the probability of traversing an edge is proportional to its current weight, and the weight of an edge increases by 1 upon traversal. While the structural properties of ERRWs are well-understood—specifically their representation as a random walk in a random environment (RWRE) governed by the "magic formula"—the information-theoretic characterization of these processes has remained underdeveloped.

The paper addresses three primary objectives motivated by statistical inference problems, particularly hypothesis testing:

1. Determining the entropy rate of the ERRW.
2. Deriving a closed-form expression for the Kullback–Leibler (KL) divergence between two distinct ERRW environment laws (mixing measures).
3. Quantifying the convergence rate of the trajectory-level KL divergence (between observed path distributions) toward the environment-level KL divergence as the trajectory length $T \to \infty$.

These quantities are critical for understanding the asymptotic behavior of statistical tests, such as the Stein exponent in two-point hypothesis testing, identity testing, and closeness testing.

Methodology
The authors leverage the structural representation of ERRWs as mixtures of reversible Markov chains. The core methodology relies on the following frameworks:

• Random Environment Representation: The ERRW is treated as a mixture of reversible Markov chains with transition kernels determined by a random environment $W$. The law of this environment is given by the magic formula, which defines a specific probability measure $\mu_{v_0, A}$ on the space of edge conductances.
• Exponential Family Structure: The family of mixing measures $\{\mu_{v_0, A}\}$ is identified as a canonical exponential family. This structural insight allows the authors to utilize standard results from exponential family theory to derive exact formulas for divergences.
• Sabot-Tarrès-Zheng (STZ) Field Representation: To interpret the KL divergence probabilistically, the authors employ the STZ field representation. This involves a "deghosted" parametrization where the underlying field factorizes into an ERRW environment component and independent Gamma fields on the vertices.
• Annealed vs. Quenched Analysis: The entropy rate is derived by relating the annealed entropy (averaged over the environment) to the quenched entropy (conditioned on a fixed environment), utilizing mutual information bounds to show that the difference vanishes asymptotically.
• Concentration and Tail Bounds: To analyze the convergence of trajectory-level KL divergence, the authors combine:
  • Combinatorial lemmas regarding the density of the normalized environment on the simplex.
  • Analytic control of the environment density using properties of the Gamma function and spanning trees.
  • Concentration inequalities for finite reversible Markov chains (e.g., L'ezaud's bounds, Azuma-Hoeffding) to control the deviation of edge counts from their expected values under a fixed environment.
  • Inverse local-time estimates to bound the probability of rare events where edge counts are small.

Key Contributions and Results

1. Entropy Rate of ERRW

• Annealed Representation: The paper proves that the entropy rate of the ERRW exists and admits an annealed representation. Specifically, the entropy rate $r(v_0, A)$ is the expectation of the entropy rate of the quenched reversible Markov chain with respect to the mixing measure $\mu_{v_0, A}$.
• Explicit Formula: An exact formula is derived expressing the entropy rate as an integral over the environment involving the ratios of edge weights to the geometric mean of incident vertex weights.
• Upper Bound: A closed-form upper bound is provided, expressed explicitly in terms of the initial edge weights using Gamma and digamma functions.

2. KL Divergence Between Environment Laws

• Closed-Form Formula: The authors derive an explicit formula for the KL divergence between two environment laws $\mu_{v_0, A^{(0)}}$ and $\mu_{v_0, A^{(1)}}$. This divergence is shown to be the Bregman divergence of the log-partition function of the exponential family. The formula is given as a difference of sums involving the function $\Lambda(p, q) = \log \Gamma(q) - \log \Gamma(p) - (q-p)\Psi(p)$, applied to edge weights and vertex parameters.
• Probabilistic Interpretation: Using the deghosted STZ field representation, the paper demonstrates that the environment-level KL divergence is the net contribution of the edge-Gamma fields minus the vertex-Gamma fields. Specifically, $D(\mu_0 \| \mu_1) = \sum_e D(\beta_e^{(0)} \| \beta_e^{(1)}) - \sum_v D(S_v^{(0)} \| S_v^{(1)})$, where $\beta$ represents edge variables and $S$ represents vertex variables.

3. Convergence of Trajectory-Level KL Divergence

• Posterior-Gap Identity: The paper establishes an identity relating the trajectory-level KL divergence to the environment-level KL divergence. The difference (gap) is exactly the expected posterior KL divergence between the environment laws after observing a trajectory.
• Quantitative Bounds: The authors provide quantitative bounds on the decay of this gap as $T \to \infty$.
  • n-Star Case: For the $n$-star graph (equivalent to a Pólya urn), the gap decays at rates of $O(T^{-1})$, $O((\log T)T^{-1})$, or $O(T^{-a})$ depending on the initial weights $a$.
  • General Graph Case: For general finite connected graphs, the paper proves polynomial upper bounds on the gap. The decay rate depends on the minimum initial weight $a$:
    • If $0 < a \le 4 + 2\sqrt{5}$, the gap decays as $O(T^{-r})$ for any $r < \min\{a/8, 3/4\}$.
    • If $a > 4 + 2\sqrt{5}$, the gap decays as $O(T^{-1})$.
• Technical Achievement: These results are achieved by deriving sharp tail bounds for the normalized edge weights (inverse local times) and combining them with concentration inequalities for the quenched walk.

Significance and Claims
The paper claims that the random-environment representation, particularly at the level of the STZ-field, is the natural framework for the information-theoretic analysis of ERRWs. The authors assert that:

• The derived formulas provide the first systematic treatment of the entropy rate and environment-level KL divergence for ERRWs.
• The identification of the environment laws as an exponential family simplifies the analysis of statistical distinguishability.
• The convergence results clarify the relationship between the hidden environment and observable trajectories, showing that the trajectory-level divergence converges to the environment-level divergence at a sublinear rate determined by the graph structure and initial weights.
• These information-theoretic quantities serve as fundamental tools for statistical testing problems involving ERRWs, specifically governing the Stein exponent for two-point hypothesis testing and offering a basis for identity and closeness testing.

The authors remain modest regarding the optimality of the convergence rates for general graphs, noting that while the derived polynomial bounds are rigorous, they may not be sharp for small initial weights, and identifying the exact rate for general graphs remains an open problem.