Pith. sign in

REVIEW 4 major objections 3 minor 2 cited by

Interacting vertex reinforced random walks on complete sub-graphs

T0 review · 4 major / 3 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves that the joint empirical occupation measure of several interacting vertex-reinforced random walks converges almost surely to the set of fixed points of their transition probabilities, and to a single fixed point for almost

desk verdict New interacting reinforcement model with a genuinely useful Lyapunov construction, but Theorem 1(iv) is vacuous as stated and the genericity claim needs repair. read the letter →

arxiv 2508.15992 v2 pith:Y4G2GK7I submitted 2025-08-21 math.PR

Fernando P. A. Prado , Rafael A. Rosales This is my paper · ORCID
classification math.PR MSC 60K3537C10
keywords reinforcedrandomwalkinteractingwalksstochasticapproximationLyapunovfunctionfixedpointconvergenceoccupationmeasurecompetitivedynamicscompletegraphs
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper studies several random walks that reinforce the vertices they visit, with the twist that each walk's next-step probabilities also depend on how often the other walks have visited shared vertices. The central result is a strong law: the vector of cumulative visit proportions converges almost surely to a point where the transition probabilities reproduce themselves, i.e., to a fixed point of the system. For almost every choice of the interaction strengths and intrinsic vertex preferences, convergence is to a single deterministic fixed point rather than merely to a set; the exceptional parameters form a measure-zero set. The proof uses a strict Lyapunov function that decreases along the limiting dynamics unless the process is already at a fixed point, plus non-convergence tests that rule out boundary and linearly unstable limits. Concrete analyses of competing walks on complete graphs, stars, and cycles show which segregated or shared configurations can persist.

What carries the argument

The machine is the strict Lyapunov function L(x) = -Σ η^i_v x^i_v - ½ Σ_v Σ_{i,j∈I_v} ρ^ij_v x^i_v x^j_v, paired with the stochastic approximation representation X(n+1)-X(n) = (F(X(n)) + U(n)) Ξ_n, F = -x + π(x). The gradient inner product factorizes as a sum over walks of g_i(x)⟨φ(x̃^i/π̃^i(x)), x̃^i Γ̃^i(x)⟩, where φ(z) = -z^{-1/α} and Γ̃^i is the generator matrix of a finite Markov chain with invariant measure π̃^i. A spectral-gap inequality bounds this term by -λ Σ_v (x^i_v - π^i_v(x))²/π^i_v(x), strictly negative off Fix(π), turning chain-transitivity of the stochastic approximation limit set into almost-sure convergence to fixed points. The fixed-point linear systems (10), with coeffic

What would settle it

Run the paper's ε = 0 competitive two-walk model on K5 for sufficiently many steps and record the final supports and overlap H(X(n)). Theorem 5 predicts that H(X(n)) → 0 almost surely and that the limit set is contained in the segregated set K of disjoint supports; a single trajectory in which both walks keep positive occupation on a shared vertex with positive probability, or in which the overlap fails to decay to 0, would settle the claim by counterexample.

Watch

Extended reading notes

Core claim

The joint occupation process X(n) satisfies a stochastic approximation recursion whose mean vector field is F(x) = -x + π(x). The fixed-point set Fix(π) is exactly the finite union of the convex solution sets D(S) of the linear system (10) over support patterns S, and Fix(π) is always nonempty. If the coefficient matrix of every such linear system is nonsingular, Fix(π) is finite and X(n) converges almost surely to one of its points; since singular matrices form a null set, this single-point convergence is generic. The argument constructs the strict Lyapunov function L(x) = -Σ η^i_v x^i_v - ½ Σ ρ^ij_v x^i_v x^j_v, whose derivative along the flow is non-positive and vanishes only on Fix(π), v

Load-bearing premise

The symmetry condition ρ^ij_v = ρ^ji_v is load-bearing: the strict Lyapunov descent and gradient inequality use the symmetric quadratic overlap term, so without this mirror symmetry the almost-sure convergence to Fix(π) is not established.

Editorial extensions

If this is right

  • On complete graphs with two competitive walks, ε = 0 yields almost-sure eventual segregation onto disjoint vertex sets, so the overlap H(X(n)) tends to 0 almost surely; for small ε > 0 the walks converge to explicit fixed points with overlap below κ³ε².
  • On star graphs, the competitive dynamics has a phase transition at ε = 1/2: for ε = 0 one walk dominates the center; for 0 < ε < 1/2 a subset of walks shares the center at a frequency ε/(|K|+2ε-1); for 1/2 < ε < 1 all walks share the center symmetrically.
  • On cycles with ε = 0, the limit set is confined to four explicitly described families of fixed points, including a periodic alternating-edge family when m is a multiple of four; with small ε > 0 the process converges to a single fixed point.
  • Any boundary fixed point whose limiting relative transition probability to a zero-occupation vertex exceeds one is almost surely unattainable, and any interior fixed point that is linearly unstable for the vector field is likewise almost surely avoided.
  • For almost all parameter values satisfying the symmetry and positivity assumptions, the joint occupation vector converges almost surely to a single point of Fix(π), not merely to the fixed-point set.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The paper notes, but does not pursue, the resemblance of the α = 1 transition probabilities to Lotka-Volterra maps; that connection suggests replicator-equation stability tools could be used to predict which of several stable fixed points is selected from given initial data.
  • The boundary non-convergence criterion offers a practical screening rule: before solving the linear systems for every support pattern S, one can discard any support whose relative transition odds at a candidate boundary exceed one, sharply pruning the exponential list of patterns.
  • When det R_ρ(S) = 0, the fixed-point components are continua and the paper leaves open whether the empirical process locks onto a random point of the continuum or wanders along it; a focused simulation study on the K3 example with η = ρ^ii = 0 could distinguish these alternatives.
  • The generic single-point convergence result is measured in Lebesgue measure on parameter space, so exactly symmetric regimes such as ε = 0 are exceptional null sets; this suggests that symmetry tuning is precisely where qualitatively different, non-point-convergent behavior can be observed experimentally.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 3 minor

Summary. The paper introduces a general model of m interacting vertex-reinforced random walks, each confined to a complete subgraph of a common graph, with transition probabilities depending on empirical occupation proportions via parameters η, ρ, and α. The main results describe Fix(π) as a finite union of connected sets, prove that the empirical occupation process converges a.s. to the chain-recurrent set/fixed points under certain regularity conditions, and claim generic a.s. convergence to a single fixed point. The authors also prove non-convergence criteria for boundary and interior points and apply them to complete graphs, stars, and cycles. The proofs are built on stochastic approximation theory, a strict Lyapunov function, and explicit fixed-point classifications.

Significance. If the central claims can be made fully correct, the paper would be a substantial contribution to the interacting reinforced random walk literature, generalizing and unifying prior work on two-walk and complete-graph models. The Lyapunov-function construction (Theorem 10), the stochastic approximation setup, and the explicit classifications for complete graphs, stars, and cycles are valuable and go beyond existing results. The paper is self-contained modulo standard external theorems and does not rely on fitted parameters or simulations. However, several load-bearing points, especially the statement and proof of the generic convergence result, are currently not established, so the significance is conditional on a successful revision.

major comments (4)
  1. [Section 2, Theorem 1(iv), Eq. (10)] The quantifier 'for all S∈V' is never satisfiable. V contains tuples S=(S1,…,Sm) with some Si=∅. For such S, system (10) includes ∑_{ℓ∈∅} x^i_ℓ = 1, so D(S)=∅ and the coefficient matrix Rρ(S) has a zero row. Hence det Rρ(S)=0 for every ρ, and Theorem 1(iv) is vacuous. The hypothesis should be restricted to S with all Si nonempty (equivalently D(S)≠∅). This issue propagates to Corollary 1 and Theorem 6.
  2. [Section 4.2, proof of Corollary 1] The proof asserts that f:ρ↦Rρ(S) is a bijection onto M_{d,d}(R) and then uses that the singular matrices form a Lebesgue-null set. This is not valid: Rρ(S) is a linear map into a proper subspace of M_{d,d}(R), and when some Si=∅ it is even a constant map with a zero row. Nullity of the singular set in the ambient matrix space does not imply nullity of its preimage under a non-surjective linear map. One must prove directly that det Rρ(S) is not identically zero as a polynomial in ρ for each relevant S, e.g. by exhibiting one parameter choice for which system (10) has a unique solution. As written, the generic convergence claim is unproved.
  3. [Section 6, proof of Theorem 5] The proof invokes 'items (iii) and (iv) of Theorem 1' to pass from P(L(X)⊂Fix_U)=0 for U≠∅ to P(L(X)⊂Fix_∅)=1. But Theorem 1(iv) is not applicable in this ϵ=0 complete-graph regime: for supports Si with |Si|≥2 and disjoint supports, the coefficient matrix Rρ(S) has zero rows (ρ_ii=0 and the other walk is absent on those vertices), so det Rρ(S)=0. The conclusion may still follow from Corollary 3/Theorem 2, which the authors prove and which applies here, but it is not obtained by the argument given in the proof of Theorem 5.
  4. [Section 6, proof of Theorem 6; also Theorem 7] Theorem 6 applies Theorem 1(iv) after Lemma 9, but no verification of det Rρ(S)≠0 is supplied for the supports contributing to Fix(π)=˜K∪˜Kc1∪˜Kc2. Since Theorem 1(iv) as stated is vacuous, and even the corrected version requires the determinant condition, the conclusion 'X converges almost surely to a single point' is not established for the complete-graph example. The same unverified invocation appears in Theorem 7 for ϵ>0. The authors need either a direct determinant computation for each support in these examples or an alternative argument (e.g., using Theorem 2/Corollary 3 when applicable) to justify L(X)⊂Fix(π).
minor comments (3)
  1. [Proof of Theorem 10, Step 1] The displayed formula π_i^v(x)= x_i^v(∂L(x)/∂x_i^v)^α / N^i(x) has the wrong sign: since ∂L/∂x_i^v <0, the right-hand side is negative for α=1 and non-real for non-integer α. It should be x_i^v(-∂L(x)/∂x_i^v)^α / N^i(x). The subsequent algebra appears consistent with the sign-corrected version, so this is likely a typo.
  2. [Proof of Corollary 1] The statement is about 'almost all (α,η,ρ)', but the proof only varies ρ and treats η and α as fixed. This can be repaired by a Fubini/coarea argument, but as written the parameter space dimension is not handled.
  3. [Throughout] There are several typos and encoding artifacts: 'vetor field' instead of 'vector field', 'T¨oeplitz' instead of 'Toeplitz', 'Departameto' instead of 'Departamento', and occasional missing spaces around citations. These should be cleaned up.

Circularity Check

0 steps flagged · score 1.0 of 10

No circular derivation: central generic-convergence proof is an independent stochastic-approximation/Lyapunov argument; the notable problem is a vacuity gap in the determinant hypothesis, not circularity.

full rationale

The central derivation is self-contained conditional on standard theorems. Theorem 1(i) is a direct algebraic characterization: x=π(x) iff x solves (10), by the normalization argument in §4.1.1. Lemma 2 verifies the stochastic approximation recursion, Lemma 3 imports Benaïm's limit-set theorem, Theorem 10 constructs the Lyapunov function L, and Theorem 1(iv) follows from finiteness of L(Fix(π)) via Lemma 4. Corollary 1 is then a genericity argument over parameter space. No parameter is fitted to the data and the almost-sure statement is not equivalent to an input; no step renames a known result or relies on the authors' previous work to define the model. The citations of [21] and [22] are background/motivation and an auxiliary verification in Theorem 4 (condition (h1)), respectively; the central generic-convergence claim does not reduce to them. The main caveat is a technical vacuity gap, not circularity: V includes S with empty S_i, and for such S the equation Σ_{ℓ∈S_i} x^i_ℓ=1 in (10) reads 0=1, so D(S)=∅ and det Rρ(S)=0. Hence the hypothesis 'det Rρ(S)≠0 for all S∈V' in Theorem 1(iv) is never satisfied, and Corollary 1's proof quantifies 'for each S∈V' while citing the nullity of singular matrices, which does not apply to the empty-S systems. This is fixable by restricting S to nonempty supports and proving the determinant is not identically zero, but as written the generic-convergence claim is not established. This is a correctness risk, not circularity, so the circularity score stays at 1.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The model's parameters (α, η, ρ) are inputs, not fitted quantities; the main theorem holds for almost all choices in the parameter space, so the proof does not depend on specific values. Two external theorems (Benaïm, Pemantle) are imported as axioms. The main internal assumption is the symmetry of interactions, which is essential for the Lyapunov argument.

assumptions (6)
  • standard math Benaïm's stochastic approximation limit set lemma (Theorem 1.2 in [2]) applies to the recursion (27).
    Used in Lemma 3 to assert L(X) is connected and contained in the chain recurrent set.
  • standard math Pemantle's non-convergence theorem for linearly unstable points (Theorem 11 from [18]) is valid under conditions (h1),(h2).
    Used in Theorem 4 and in the examples to discard convergence to unstable fixed points.
  • domain assumption The interaction parameters are symmetric: ρ_ij_v = ρ_ji_v (eq. 7).
    Load-bearing for the Lyapunov function construction in Theorem 10.
  • domain assumption The intrinsic preference dominates negative interactions: η_i_v > Σ_{j:ρ<0} |ρ_ij_v| (eq. 8).
    Ensures the transition probabilities (5) are non-negative and well-defined.
  • domain assumption Conditional independence of W^i(n+1), i∈[m], given F_n (stated below eq. 8).
    Used in the stochastic approximation noise verification and in Theorem 11's condition (h1).
  • domain assumption Each walk's state space is a complete subgraph G_i = (E_i,V_i).
    The model and all fixed point equations (10) are defined for complete subgraphs; extension to non-complete graphs is not treated.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Interacting vertex reinforced random walks on complete sub-graphs." pith.science (2026). https://pith.science/paper/Y4G2GK7I

@misc{pith2026250815992,
  author       = {Pith},
  title        = {Pith review of: Interacting vertex reinforced random walks on complete sub-graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Y4G2GK7I}},
  note         = {Machine review of arXiv:2508.15992}
}
read the original abstract

This article introduces a model for interacting vertex-reinforced random walks, each taking values on a complete subgraph of a locally finite undirected graph. The transition probability for a walk to a given vertex depends on the cumulative proportion of visits by all walks that have access to that vertex. Proportions are modified by multiplication by a real valued interaction parameter and the addition of a parameter representing the intrinsic preference of the walk for the vertex. This model covers a wide range of interactions, including the cooperation (attraction) or competition (repulsion) of several walks at single vertices. We are principally concerned with strong laws for the proportion of visits to each vertex by all walks. We prove that this measure converges almost surely towards the set of fixed points of the transition probabilities. Almost sure convergence to a single fixed point is in fact the generic behaviour as we show this to hold for almost all parameter values of our model. Beyond almost sure convergence, our model provides a general framework that yields a detailed description of the limiting behaviour for any choice of interaction parameters and subgraph geometry. We illustrate this by analyzing interacting walks on complete graphs, stars, and cycles, chosen to highlight the model's broad applicability. The central contribution lies in offering a powerful tool to analyse diverse types of interactions mediated by the intersections of subgraphs. Importantly, our results provide not only convergence criteria, but also conditions under which the empirical proportions of the walks' visits fail to converge to certain boundary points of the space where their trajectory evolves.

Figures

Figures reproduced from arXiv: 2508.15992 by the authors.

Figure 1
Figure 1. A continuum component in Fix(π) for two competing walks on the tree vertex complete graph. In general, the convergence of X to a single point of a continuum component of Fix(π) is an open question. The almost sure accumulation of X along any such continuum is generally also widely open. Still, even in cases where some connected components of Fix(π) are continua, it is possible to provide conditions under which the s… view at source ↗
Figure 2
Figure 2. Possible limits for the vertex occupation by two walks on K5 (left) and K9. ϵ = 0, is determined by setting the occupation of the two blue vertices respectively to a and 1 − a where a ∈ (0, 1). The occupation depicted in K9 is an instance of the limits obtained for ϵ = 4 20 . Blue and green vertices are each occupied at a proportion equal to 6 25 while the red vertex, shared by both walks, is occupied at a proportio… view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Vertex reinforced branching random walks and generalized time-dependent Polya urns

    math.PR 2026-07 conditional novelty 7.0 of 10

    Strongly reinforced vertex-reinforced branching random walks have finite range almost surely and can localize on two sites; for generalized Pólya urns with bounded drawing sequences, one color fixes almost surely exac...

  2. Reinforced random walks with geometric inter-transition times

    math.PR 2026-06 unverdicted novelty 6.0 of 10

    Vertex-reinforced walks with geometric holding times converge almost surely to the same fixed points of x=π(x) as the simultaneous-transition model, via a martingale-plus-geometric-decay decomposition that restores th...

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages · cited by 2 Pith papers

  1. [1]

    Theory Related Fields 159 (2014), no

    Anne-Laure Basdevant, Bruno Schapira, and Arvind Singh, Localization of a vertex reinforced random walk on Z with sub-linear weight , Probab. Theory Related Fields 159 (2014), no. 1-2, 75–115. MR 3201918

    work page 2014

  2. [2]

    Control Optim

    Michel Bena ¨ ım,A dynamical system approach to stochastic approximations , SIAM J. Control Optim. 34 (1996), no. 2, 437–472. MR 1377706

    work page 1996

  3. [3]

    Michel Bena ¨ ım,Vertex-reinforced random walks and a conjecture of Pemantle, Ann. Probab. 25 (1997), no. 1, 361–392. MR 1428513

    work page 1997

  4. [4]

    1709, Springer, Berlin, 1999, pp

    , Dynamics of stochastic approximation algorithms , S´ eminaire de Probabilit´ es, XXXIII, Lecture Notes in Math., vol. 1709, Springer, Berlin, 1999, pp. 1–68. MR 1767993

    work page 1999

  5. [5]

    Michel Bena ¨ ım,On gradient like properties of population games, learning models and self reinforced processes, Dynamics, games and science, CIM Ser. Math. Sci., vol. 1, Springer, Cham, 2015, pp. 117–152. MR 3644912

    work page 2015

  6. [6]

    Michel Bena ¨ ım and Pierre Tarr` es,Dynamics of vertex-reinforced random walks , Ann. Probab. 39 (2011), no. 6, 2178–2223. MR 2932667

    work page 2011

  7. [7]

    Grudsky,Spectral properties of banded Toeplitz matrices, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2005

    Albrecht B¨ ottcher and Sergei M. Grudsky,Spectral properties of banded Toeplitz matrices, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2005. MR 2179973

    work page 2005

  8. [8]

    Amarjit Budhiraja, Paul Dupuis, Markus Fischer, and Kavita Ramanan, Limits of relative entropies associated with weakly interacting particle systems , Electron. J. Probab. 20 (2015), no. 80, 22. MR 3383564

    work page 2015

Show all 27 references
  1. [9]

    Jun Chen, Two particles’ repelling random walks on the complete graph , Electron. J. Probab. 19 (2014), no. 113, 17. MR 3296529

    2014

  2. [10]

    2, 817–842

    Shanshan Chen, Junping Shi, Zhisheng Shuai, and Yixiang Wu, Global dynamics of a Lotka-Volterra competition patch model, Nonlinearity 35 (2022), no. 2, 817–842. MR 4373987

    2022

  3. [11]

    Don Coppersmith and Persi Diaconis, Random walk with reinforcement , Unpublished manuscript, 1987

    1987

  4. [12]

    Codina Cotar and Debleena Thacker, Edge- and vertex-reinforced random walks with super-linear reinforcement on infinite graphs , Ann. Probab. 45 (2017), no. 4, 2655–2706. MR 3693972 INTERACTING VERTEX REINFORCED RANDOM W ALKS 35

    2017

  5. [13]

    Minelli, Synchronization and functional central limit theorems for interacting reinforced random walks , Stoch

    Irene Crimaldi, Paolo Dai Pra, Pierre-Yves Louis, and Ida G. Minelli, Synchronization and functional central limit theorems for interacting reinforced random walks , Stoch. Proc. Appl. 129 (2019), 70–101

    2019

  6. [14]

    Dirk Erhard and Guilherme Reis, Stochastic processes with competing reinforcements , Ann. Appl. Probab. 34 (2024), no. 5, 4513–4553. MR 4801575

    2024

  7. [15]

    de Paula Reis, Interacting edge-reinforced random walks, ALEA Lat

    Nina Gantert, Fabian Michel, and Guilherme H. de Paula Reis, Interacting edge-reinforced random walks, ALEA Lat. Am. J. Probab. Math. Stat. 21 (2024), no. 2, 1041–1072. MR 4770201

    2024

  8. [16]

    MR 1635735

    Josef Hofbauer and Karl Sigmund, Evolutionary games and population dynamics, Cambridge University Press, Cambridge, 1998. MR 1635735

    1998

  9. [17]

    Weiwei Liu, Jie Liu, and Shanshan Chen, Dynamics of Lotka-Volterra competition patch models in streams with two branches , Bull. Math. Biol. 86 (2024), no. 2, Paper No. 14, 47. MR 4685960

    2024

  10. [18]

    Robin Pemantle, Nonconvergence to unstable points in urn models and stochastic approximations , Ann. Probab. 18 (1990), no. 2, 698–712

    1990

  11. [19]

    Theory Related Fields 92 (1992), no

    , Vertex-reinforced random walk, Probab. Theory Related Fields 92 (1992), no. 1, 117–136. MR 1156453

    1992

  12. [20]

    Robin Pemantle and Stanislav Volkov, Vertex-reinforced random walk on Z has finite range , Ann. Probab. 27 (1999), no. 3, 1368–1388. MR 1733153

    1999

  13. [21]

    Fernando P. A. Prado, Cristian F. Coletti, and Rafael A. Rosales, Two repelling random walks on Z, Stochastic Process. Appl. 160 (2023), 72–88. MR 4558974

    2023

  14. [22]

    Rosales, Fernando P

    Rafael A. Rosales, Fernando P. A. Prado, and Benito Pires, Vertex reinforced random walks with exponential interaction on complete graphs, Stochastic Process. Appl. 148 (2022), 353–379. MR 4402635

    2022

  15. [23]

    Thiago Christiano Silva and Liang Zhao, Machine learning in complex networks , Springer, Cham,

  16. [24]

    Anton ´ ın Slav ´ ık,Lotka-Volterra competition model on graphs, SIAM J. Appl. Dyn. Syst. 19 (2020), no. 2, 725–762. MR 4081801

    2020

  17. [25]

    Pierre Tarr` es,Vertex-reinforced random walk on Z eventually gets stuck on five points , Ann. Probab. 32 (2004), no. 3B, 2650–2701. MR 2078554

    2004

  18. [26]

    Neural Netw

    Filipe Alves Neto Verri, Paulo Roberto Urio, and Liang Zhao, Network unfolding map by vertex-edge dynamics modeling, IEEE Trans. Neural Netw. Learn. Syst. 29 (2018), no. 2, 405–418. MR 3757790

    2018

  19. [27]

    Stanislav Volkov, Vertex-reinforced random walk on arbitrary graphs , Ann. Probab. 29 (2001), no. 1, 66–91. MR 1825142 (F. P. A. Prado and R. A. Rosales) Departameto de Computac ¸˜ao e Matem´atica, Universidade de S˜ao Paulo, A venida Bandeirantes 3900, Ribeir˜ao Preto, S ˜ao ...

    2001

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.