2025-11-21T02:34:15.165429

Maximal Entropy Random Walks in Z: Random and non-random environments

Thibaut, Gerin, Offret
The Maximal Entropy Random Walk (MERW) is a natural process on a finite graph, introduced a few years ago with motivations from theoretical physics. The construction of this process relies on Perron-Frobenius theory for adjacency matrices. Generalizing to infinite graphs is rather delicate, and in this article, we treat in a fairly exhaustive manner the case of the MERW on Z with loops, for both random and nonrandom loops. Thanks to an explicit combinatorial representation of the corresponding Perron-Frobenius eigenvectors, we are able to precisely determine the asymptotic behavior of these walks. We show, in particular, that essentially all MERWs on Z with loops have positive speed.
academic

Maximal Entropy Random Walks in Z: Random and non-random environments

Basic Information

  • Paper ID: 2503.15957
  • Title: Maximal Entropy Random Walks in Z: Random and non-random environments
  • Authors: Thibaut Duboux (Université Bourgogne Europe), Lucas Gerin (École Polytechnique), Yoann Offret (Université Bourgogne Europe)
  • Classification: math.CO (Combinatorics), math.PR (Probability Theory)
  • Submission Date: November 20, 2025
  • Paper Link: https://arxiv.org/abs/2503.15957

Abstract

Maximal Entropy Random Walks (MERW) are natural processes on finite graphs, introduced several years ago with motivation from theoretical physics. The construction of this process relies on Perron-Frobenius theory of adjacency matrices. Generalization to infinite graphs is considerably subtle. This paper provides a detailed study of MERW models on the integer lattice Z with loops, covering both random and non-random environments. Through explicit combinatorial representations of the corresponding Perron-Frobenius eigenvectors, the authors are able to precisely determine the asymptotic behavior of these walks. In particular, it is proven that almost all MERW with loops on Z possess positive velocity.

Research Background and Motivation

Problem Background

  1. Limitations of Standard Random Walks: Traditional standard random walks are fundamental stochastic processes in probability theory, statistical physics, and network analysis, with transition probabilities given by pi,j=ai,j/∑ℓai,ℓp_{i,j} = a_{i,j}/\sum_\ell a_{i,\ell}. However, such walks do not necessarily maximize the entropy of trajectories.
  2. Physical Motivation for MERW: MERW originates from the path integral formulation of quantum mechanics, with transition probabilities pi,j=ai,jψj/(λψi)p_{i,j} = a_{i,j}\psi_j/(\lambda\psi_i), where ψ\psi is the positive eigenvector corresponding to spectral radius λ\lambda. This construction ensures that MERW maximizes the entropy rate of trajectories on finite graphs.
  3. Challenges on Infinite Graphs:
    • Perron-Frobenius theory no longer applies directly on infinite graphs
    • Distinction between R-recurrent and R-transient cases is necessary
    • In the R-transient case, positive eigenvectors are not unique; there exists a convex set of extremal solutions
  4. Research Gap: Although MERW on finite graphs has been thoroughly studied, systematic investigation of infinite graphs, particularly with random perturbations, remains lacking.

Research Significance

  1. Theoretical Significance: Connects combinatorial probability, stochastic processes, and Anderson localization theory
  2. Applied Value: Potential applications in community detection algorithms for complex networks
  3. Methodological Contribution: Provides new tools for analyzing MERW on infinite graphs

Core Contributions

The main contributions of this paper include:

  1. Explicit Eigenvector Representation (Theorem 2.9): For nice environments, complete explicit combinatorial descriptions of two extremal eigenvectors ψ+\psi^+ and ψ−\psi^- are provided:\beta_{-1}\cdots\beta_i, & i < 0\\ 1, & i = 0\\ (\beta_0\beta_1\cdots\beta_{i-1})^{-1}, & i > 0 \end{cases}$$ where $\beta_i$ and $\alpha_i$ can be expressed via generating functions or continued fractions.
  2. Complete Characterization for Deterministic Environments (Propositions 2.3, 2.5):
    • Proves that matrix AA is R-transient
    • Precisely describes monotonicity and limiting behavior of extremal eigenvectors
    • Establishes that all MERW in nice environments are transient
  3. Linear Velocity in Random Environments (Theorem 3.1): For i.i.d. random environments, extremal MERW possess constant positive velocity: lim⁡n→∞Xn+n=v>0(almost surely)\lim_{n\to\infty} \frac{X^+_n}{n} = v > 0 \quad \text{(almost surely)} where v=1/Eμ[S]v = 1/\mathbb{E}_\mu[S] with explicit expression for SS.
  4. Coupling Analysis of Non-extremal MERW (Theorem 3.4): For MERW corresponding to mixed eigenvectors ψ(κ)=κψ++(1−κ)ψ−\psi^{(\kappa)} = \kappa\psi^+ + (1-\kappa)\psi^-, linear velocity vv is established under the condition Xn(κ)→+∞X^{(\kappa)}_n \to +\infty.
  5. Exact Calculations for Bernoulli Environments (Proposition 3.6): When the environment satisfies P(wk=M)=pP(w_k=M)=p, it is proven that: lim⁡p→0vp,M=1−4(2+M)2>0\lim_{p\to 0} v_{p,M} = \sqrt{1-\frac{4}{(2+M)^2}} > 0 demonstrating discontinuous jump in velocity as p→0p\to 0.
  6. Contrast with Periodic Environments (Proposition A.1): For periodic deterministic environments, MERW is null recurrent and highly localized, contrasting sharply with random environments.

Methodology Details

Task Definition

Input:

  • Environment w=(wi)i∈Zw = (w_i)_{i\in\mathbb{Z}}, where wi≥0w_i \geq 0 is the weight of the self-loop at vertex ii
  • Adjacency matrix AA defined as: edge weight 1 between adjacent vertices, self-loop weight wiw_i at vertex ii

Output:

  • Combinatorial spectral radius λ\lambda
  • Positive λ\lambda-eigenvector ψ\psi (satisfying Aψ=λψA\psi = \lambda\psi)
  • Asymptotic behavior of corresponding MERW (Xn)n≥0(X_n)_{n\geq 0}

Constraints:

  • Environment is M-nice: bounded, not identically equal to MM, and for any ε>0\varepsilon>0 and r≥0r\geq 0 there exists ii such that wi,…,wi+rw_i,\ldots,w_{i+r} are all ≥M−ε\geq M-\varepsilon

Core Methodological Framework

1. Computation of Combinatorial Spectral Radius (Lemma 2.2)

Proof of λ=2+M\lambda = 2+M through path counting:

Lower Bound Proof Strategy:

  • Consider the number of paths from ii returning to ii while staying above ii: uri↺iu^{i\circlearrowleft i}_r
  • Use generating function Hi,i[≥i],w(z)=∑r≥0dr0↺0zrH^{[\geq i],w}_{i,i}(z) = \sum_{r\geq 0} d^{0\circlearrowleft 0}_r z^r
  • Via arch-decomposition obtain: Hi,i[≥i],w(z)=11−(M−ε)z−z2Hi,i[≥i],w(z)H^{[\geq i],w}_{i,i}(z) = \frac{1}{1-(M-\varepsilon)z - z^2H^{[\geq i],w}_{i,i}(z)}
  • Solving yields principal singularity at z∗=(2+M−ε)−1z^* = (2+M-\varepsilon)^{-1}
  • Using transfer theorem obtain dr0↺0≥c(2+M−ε)rr−3/2d^{0\circlearrowleft 0}_r \geq c(2+M-\varepsilon)^r r^{-3/2}

2. Construction of Extremal Eigenvectors (Proposition 2.3)

Truncation Approximation Method:

  • For k≤0k\leq 0, define ψ(k,ε)\psi^{(k,\varepsilon)} satisfying boundary conditions: 0, & n\leq k-2\\ \varepsilon, & n=k-1\\ 2\varepsilon, & n=k \end{cases}$$ and satisfying recurrence $\psi_{n+1} + w_n\psi_n + \psi_{n-1} = \lambda\psi_n$
  • Adjust εk\varepsilon_k so that ψ0(k,εk)=1\psi^{(k,\varepsilon_k)}_0 = 1
  • Obtain convergent subsequences via diagonal argument
  • Use convexity estimates to prove lim⁡n→∞ψn+=∞\lim_{n\to\infty}\psi^+_n = \infty

3. Derivation of Combinatorial Representation (Theorem 2.9)

Key Steps:

Define generating functions: βi=1λHi,i[≤i],w(1λ),αi=1λHi,i[≥i],w(1λ)\beta_i = \frac{1}{\lambda}H^{[\leq i],w}_{i,i}\left(\frac{1}{\lambda}\right), \quad \alpha_i = \frac{1}{\lambda}H^{[\geq i],w}_{i,i}\left(\frac{1}{\lambda}\right)

Via arch-decomposition obtain recurrence relations: βi=1λ−wi−βi−1,αi=λ−wi−1αi+1\beta_i = \frac{1}{\lambda - w_i - \beta_{i-1}}, \quad \alpha_i = \lambda - w_i - \frac{1}{\alpha_{i+1}}

This is equivalent to continued fraction expansion: αi=1λ−wi−1λ−wi+1−1⋱\alpha_i = \cfrac{1}{\lambda - w_i - \cfrac{1}{\lambda - w_{i+1} - \cfrac{1}{\ddots}}}

Verify that ψi+=β−1⋯βi\psi^+_i = \beta_{-1}\cdots\beta_i (for i<0i<0) indeed satisfies the eigenvalue equation.

4. Velocity Analysis in Random Environments

Markov Chain Identification:

  • When (wi)(w_i) is i.i.d., (βi)i(\beta_i)_i and (α−i)i(\alpha_{-i})_i are stationary ergodic Markov chains
  • Extremal MERW is a random walk in ergodic random environment

Velocity Formula (Equation 3.4): v=1Eμ[S],S=∑n≥0P0w(Xn+=0)v = \frac{1}{\mathbb{E}_\mu[S]}, \quad S = \sum_{n\geq 0} P^w_0(X^+_n = 0)

Finiteness Proof: Use control: βi≤1{wi≤M−δ}gM−δ(βi−1)+1{wi>M−δ}\beta_i \leq 1_{\{w_i\leq M-\delta\}} g_{M-\delta}(\beta_{i-1}) + 1_{\{w_i>M-\delta\}}

Obtain: Eμ[β0β−12⋯β−i2]≤Eμ[Z02]i<1\mathbb{E}_\mu[\beta_0\beta^2_{-1}\cdots\beta^2_{-i}] \leq \mathbb{E}_\mu[Z^2_0]^i < 1

Therefore Eμ[S]<∞\mathbb{E}_\mu[S] < \infty, ensuring positive velocity.

Technical Innovations

  1. Path Generating Function Method: Transforms eigenvector problems into path counting problems, leveraging analytic combinatorics tools.
  2. Riccati Variable Technique: The recurrence relations satisfied by αi\alpha_i and βi\beta_i relate to Riccati variables in Anderson localization theory, establishing connections between MERW and random Schrödinger operators.
  3. Coupling Arguments: For non-extremal MERW, construct couplings with extremal MERW and use finiteness of "bad time" sets to prove velocity consistency.
  4. Boundary Analysis of Generating Functions: Precisely control generating function behavior at principal singularities to obtain asymptotic estimates of path counts.

Experimental Setup

Numerical Simulation Parameters

Although primarily theoretical, the paper includes numerical verification:

  1. Figure 1: MERW Simulation in Bernoulli Environment
    • Parameters: M=20M=20, p=0.02p=0.02 and p=0.05p=0.05
    • 200 independent trajectories, time steps n=600n=600
    • Verifies that velocity vp,Mv_{p,M} decreases with pp
  2. Figure 3: Variation of Velocity vp,Mv_{p,M} with pp
    • Monte Carlo simulation of formula (3.21)
    • Different MM values: M=0.1,1,10M=0.1, 1, 10
    • Verifies asymptotic behavior of Proposition 3.6
  3. Figure 4: Variation of Velocity vp,Mv_{p,M} with MM
    • Parameters: p=0.3,0.5,0.8p=0.3, 0.5, 0.8
    • Shows non-monotonic behavior of velocity with respect to MM

Theoretical Verification

Exact Calculations for Bernoulli Environments:

  • Uses combinatorial identities related to Motzkin numbers
  • Verifies lim⁡p→0vp,M=1−4/(2+M)2\lim_{p\to 0} v_{p,M} = \sqrt{1-4/(2+M)^2}
  • Proves vp,M∼3(1−p)/(2+M)v_{p,M} \sim 3(1-p)/(2+M) as p→1p\to 1

Experimental Results

Main Results

1. Deterministic Environments (Section 2)

Verification of Theorem 2.9:

  • Provides complete explicit expressions for ψ+\psi^+ and ψ−\psi^-
  • Boundary estimates: γ≤αi,βi≤1\gamma \leq \alpha_i, \beta_i \leq 1, where γ=(λ−λ2−4)/2\gamma = (\lambda-\sqrt{\lambda^2-4})/2

Toy Example (End of Section 2.3): For step function environment (wi=Mw_i=M when i≤0i\leq 0, wi=0w_i=0 when i≥1i\geq 1):

1, & k\leq 0\\ \frac{\gamma}{1+\gamma}\gamma^{-k} + \frac{1}{1+\gamma}\gamma^k, & k\geq 0 \end{cases}$$ Velocity $v_M \sim \sqrt{M}$ as $M\to 0$, $v_M \sim M^{-1}$ as $M\to\infty$. #### 2. i.i.d. Random Environments (Section 3) **Numerical Verification of Theorem 3.1** (Figure 1): - For $p=0.02$, $M=20$: trajectories show clear rightward drift with velocity approximately $v_{0.02,20} \approx 0.35$ - For $p=0.05$, $M=20$: velocity decreases to approximately $v_{0.05,20} \approx 0.25$ - Supports theoretical prediction of monotone decrease of velocity with respect to $p$ **Implications of Theorem 3.4**: All mixed MERW $X^{(\kappa)}$ have the same velocity $v$ when $X^{(\kappa)}_n \to +\infty$, indicating: - Non-localization: contrasts with numerical experiments on finite graphs [BDLW09] - Universality of velocity: independent of mixing parameter $\kappa$ of eigenvectors #### 3. Exact Results for Bernoulli Environments (Section 3.3) **Key Findings of Proposition 3.6**: 1. **Discontinuity as $p\to 0$**: $$\lim_{p\to 0} v_{p,M} = \sqrt{1-\frac{4}{(2+M)^2}} > 0$$ - For $M=1$: $\lim_{p\to 0} v_{p,1} \approx 0.745$ - For $M=10$: $\lim_{p\to 0} v_{p,10} \approx 0.986$ - While at $p=0$ velocity is 0 (standard random walk) 2. **Asymptotics as $p\to 1$**: $$v_{p,M} \sim \frac{3(1-p)}{2+M}$$ Proof uses complex generating function expansions and geometric random variable analysis. 3. **Monotonicity**: - $p \mapsto v_{p,M}$ is strictly decreasing (Figure 3) - $M \mapsto v_{p,M}$ is non-monotonic with maximum (Figure 4) ### Ablation Studies **Comparative Study with Periodic Environments** (Appendix A): For periodic environment with period $\ell$ ($w_{n\ell}=M$, others 0): **Proposition A.1**: $$\liminf_{\ell\to\infty} \pi_{\ell,M}\left(\left\{n : |n| \leq \frac{1}{2\theta^*_M}\ln\left(\frac{1}{\lambda^*_M\varepsilon}\right)\right\}\right) \geq 1-\varepsilon$$ **Key Contrasts**: - Periodic environment: MERW is null recurrent, highly localized near loops - Random environment: MERW has positive velocity, non-localized - Even with identical average loop density ($p=1/\ell$), randomness causes qualitative differences ### Case Studies **Trajectory Analysis from Figure 1**: - Trajectories display clear "step" structure: longer residence times at loop locations - Overall trend is linear growth, not permanently captured by loops - Velocity consistency across different trajectories supports ergodicity **Phase Behavior from Figure 3**: - For larger $M$, decay of $v_{p,M}$ with respect to $p$ is slower - Critical value $M_c \approx 1$ exists where $p \mapsto v_{p,M}$ transitions from convex to concave **Non-monotonicity from Figure 4**: - For fixed $p$, $v_{p,M}$ first increases then decreases - Maximum location varies with $p$: smaller $p$ corresponds to larger $M$ at maximum - Physical interpretation: loops too weak to accelerate, loops too strong cause excessive residence ## Related Work ### Origins and Development of MERW 1. **MERW on Finite Graphs** [BDLW09, BDLW10]: - Burda et al. introduced MERW, proved entropy maximization property - Numerical experiments showed localization phenomena on $(\mathbb{Z}/n\mathbb{Z})^d$ - This paper proves fundamentally different behavior on infinite graphs 2. **Infinite Graph Theory** [VJ67, VJ68, DO24]: - Vere-Jones developed spectral theory of non-negative infinite matrices - Introduced R-recurrence and R-transience concepts - [DO24] systematically studied entropy maximization of MERW on infinite graphs 3. **h-Transform and Conditioned Processes** [Doo01]: - MERW transition probabilities resemble Doob h-transform - Deep connections with conditioned process theory ### Anderson Localization 1. **Standard Anderson Model** [CKM87, KS80, Lan91]: - Studies operator $H\psi_n = \psi_{n-1} + \omega_n\psi_n + \psi_{n+1}$ - Proves pure point spectrum and exponential localization in $\ell^2(\mathbb{Z})$ 2. **Parabolic Anderson Model** [GK05]: - Studies $\partial u/\partial t = \Delta u + \tilde{\omega}u$ - Feynman-Kac representation connects to MERW 3. **Riccati Variables** [Hal67, CTT10, CTT13]: - Paper's $\alpha_i, \beta_i$ relate to Riccati variables in physics literature - May provide new analytical tools for MERW ### Random Walks in Random Environments 1. **Random Walks in Ergodic Environments** [Zei04, Ali99]: - Extremal MERW belongs to this class - Uses velocity formula $v = 1/\mathbb{E}_\mu[S]$ and finiteness criteria 2. **Bessel-type Random Walks**: - $X^-$ in toy examples is Lamperti process - Related to discussion in [DO24] ## Conclusions and Discussion ### Main Conclusions 1. **Theoretical Completeness**: For M-nice environments, completely characterizes asymptotic behavior of MERW: - Deterministic environments: explicit formulas for eigenvectors - Random environments: proves existence and universality of positive velocity 2. **Non-localization Phenomenon**: Contrary to finite graph numerical observations, MERW on infinite graphs do not localize near loops but escape with positive velocity. 3. **Critical Role of Randomness**: Even with identical average loop density, random environments versus periodic environments yield completely different behaviors (positive velocity vs. null recurrence). 4. **Fine Structure of Velocity**: - Discontinuous jump at $p\to 0$ - Non-monotonic with respect to $M$ - Phase transition phenomena exist ### Limitations 1. **Environmental Restrictions**: - Requires bounded environments ($w_i \leq M$) - M-nice condition is strong, excluding some interesting cases - Does not cover non-constant edge weights 2. **Dimensional Restriction**: - Only studies one-dimensional case $\mathbb{Z}$ - Higher dimensions $\mathbb{Z}^d$ ($d\geq 2$) require completely different tools 3. **Non-i.i.d. Environments**: - Results incomplete for general ergodic environments - Some techniques (e.g., Markov property of $(\beta_i)$) depend on i.i.d. assumption 4. **Fine Asymptotics**: - Stationary distribution properties of $\alpha_i, \beta_i$ not fully understood - Convexity-concavity transition of velocity $v_{p,M}$ not rigorously proven ### Future Directions Section 4 of the paper proposes several open problems: 1. **Generalization to More General Graphs**: - Non-constant edge weights on $\mathbb{Z}$ - Graphs like $\mathbb{Z}\times\{0,1\}$ - Certain infinite tree families (comparison with [OB12]'s analytic methods) 2. **Deeper Study of $(\alpha_i), (\beta_i)$**: - Support of stationary distribution (appears singular with respect to Lebesgue measure) - Connections with dynamical systems 3. **Fine Properties of Velocity**: - Prove convexity-concavity transition of $p \mapsto v_{p,M}$ - Determine critical value $M_c$ - Study maximum location of $M \mapsto v_{p,M}$ 4. **Connections with Parabolic Anderson Model**: - Clarify precise relationship between MERW and PAM - Exploit intermittency techniques from PAM 5. **Higher Dimensional Generalization**: - MERW behavior on $\mathbb{Z}^d$ - Existence of localization-delocalization phase transitions ## In-Depth Evaluation ### Strengths 1. **Mathematical Rigor**: - All main results have complete proofs - Technical treatment is meticulous (e.g., path counting in Lemma 2.2) - Correctly handles subtleties of infinite dimensions 2. **Methodological Innovation**: - Combinatorial generating function method is novel and powerful - Continued fraction representation provides deep insights - Coupling argument (Theorem 3.4) is elegant 3. **Depth of Results**: - Not only proves existence but provides explicit formulas - Reveals essential role of randomness (Proposition A.1 contrast) - Discovers fine phenomena like discontinuities (Proposition 3.6) 4. **Interdisciplinary Connections**: - Connects combinatorics, probability theory, and mathematical physics - Analogy with Anderson localization is illuminating - Provides new perspective for PAM research 5. **Writing Quality**: - Clear structure, progressing from simple to complex - Toy examples and numerical simulations enhance intuition - Appendix's periodic environment comparison has pedagogical value ### Weaknesses 1. **Scope of Applicability**: - M-nice condition is quite restrictive - One-dimensional results difficult to generalize to higher dimensions - Treatment of non-i.i.d. environments incomplete 2. **Certain Technical Details**: - Proof of Proposition 3.6 (especially $p\to 1$) is quite technical - Stationary distribution properties of $\alpha_i, \beta_i$ insufficiently explored - Phase transition phenomena in Figures 3, 4 lack theoretical explanation 3. **Numerical Verification**: - Numerical simulations relatively simple, mainly illustrative - Finite-size effects not systematically studied - Quantitative information like convergence rates missing 4. **Physics Connections**: - Connections with Anderson model mainly analogical - No Feynman-Kac type representation provided - Physical meaning (e.g., quantum mechanical interpretation) unclear ### Impact 1. **Theoretical Contribution**: - Provides first systematic study of MERW on infinite graphs - Combinatorial methods may apply to other problems - Reveals critical role of randomness in MERW 2. **Methodological Value**: - Generating function-eigenvector connection may inspire new research - Coupling techniques useful for analyzing other processes in ergodic environments - Riccati variable connection deserves deeper exploration 3. **Openness**: - Proposes many valuable open problems - Indicates directions for future research - Likely to attract interest from combinatorialists, probabilists, and physicists 4. **Reproducibility**: - Theoretical results completely verifiable - Numerical simulation methods explicit (via formula 3.21) - Main formulas (e.g., Theorem 2.9) directly applicable ### Applicable Scenarios 1. **Theoretical Research**: - Study of random processes on infinite graphs - Analysis of walk behavior in random environments - Exploration of connections between combinatorial structures and probability 2. **Related Models**: - Potential application to certain branching processes - Connections with random Schrödinger operators worth exploring - Provides template for studying other entropy-maximizing processes 3. **Potential Applications**: - Complex network analysis (e.g., [OB13]'s community detection) - Algorithm design (improvements to MCMC methods) - Physical system modeling (though not detailed in this paper) 4. **Educational Value**: - Demonstrates power of analytic combinatorics - Illustrates subtle role of randomness - Provides example of generalization from finite to infinite ## References The paper cites 27 references, with key works including: 1. **[BDLW09]** Burda et al., "Localization of the maximal entropy random walk" - Original MERW work 2. **[VJ67, VJ68]** Vere-Jones - Ergodic properties of infinite non-negative matrices, foundational theory 3. **[DO24]** Duboux & Offret - Systematic study of MERW on infinite graphs, direct predecessor 4. **[FS09]** Flajolet & Sedgewick, "Analytic Combinatorics" - Standard reference for generating function methods 5. **[Zei04]** Zeitouni - Classical lecture notes on random walks in random environments 6. **[GK05]** Gärtner & König - Survey of parabolic Anderson model --- **Overall Assessment**: This is a high-quality theoretical paper making important contributions to MERW on infinite graphs. The methods are novel, results are profound, and it reveals the critical role of randomness in this model. Despite some limitations (mainly in scope), it establishes solid foundations for further research in this area. The paper is clearly written with rigorous technical treatment, and is recommended for researchers interested in combinatorial probability, stochastic processes, or mathematical physics.