Pith. sign in

REVIEW 2 major objections 1 minor 20 references

The Clark-Kushner condition for interacting reinforced random walks on finite graphs

T0 review · 2 major / 1 minor · reviewed 2026-06-28 · grok-4.3

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

Pith's one-line read Interacting vertex-reinforced random walks on finite graphs satisfy the Clark-Kushner condition when each transition matrix is irreducible, aperiodic, and Lipschitz continuous in the occupation vector.

desk verdict Extends Clark-Kushner to interacting walks via Poisson decomposition but the uniform Dobrushin bound looks insufficiently justified by the hypotheses. read the letter →

arxiv 2606.05377 v1 pith:I2QTV773 submitted 2026-06-03 math.PR

Fernando P. A. Prado , Rafael A. Rosales This is my paper · ORCID
classification math.PR
keywords vertex-reinforcedrandomwalksClark-KushnerconditionstochasticapproximationPoissonequationDobrushincoefficientgeometricergodicityfinitegraphsinteractingprocesses
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

The paper proves that a large class of interacting vertex-reinforced random walks on finite graphs satisfies the Clark-Kushner condition required for stochastic approximation analysis of the occupation measure. This holds even though the driving noise retains memory of past states rather than forming a martingale difference. The authors decompose the noise by solving the Poisson equation for the occupation-dependent Markov chain and subtracting the increment of a bounded process. A uniform geometric ergodicity bound extracted from the Dobrushin contraction coefficient supplies the needed control and also guarantees that the Poisson solutions remain Lipschitz continuous in the occupation proportions. The hypotheses require only irreducibility, aperiodicity, and Lipschitz continuity of the transition matrices and do not demand strictly positive entries or identical rows across walks.

What carries the argument

The uniform geometric ergodicity bound obtained from the Dobrushin contraction coefficient on the family of transition matrices Q^i(x), which supplies both the contraction rate and the Lipschitz control on the Poisson equation solutions.

What would settle it

An explicit occupation vector x for which at least one Q^i(x) is periodic or reducible, causing the Dobrushin coefficient to lose its uniform contraction and the Poisson solution to fail the required Lipschitz bound.

Watch

Extended reading notes

Core claim

We establish the Clark-Kushner condition for interacting vertex-reinforced random walks on finite graphs, where the transition matrix Q^i(x) of each walk depends on the joint occupation vector x and may have distinct rows. Using the solution of the Poisson equation we decompose the non-martingale noise into a martingale difference minus the increment of a bounded process. The key technical step is a uniform geometric ergodicity bound derived from the Dobrushin contraction coefficient, which simultaneously controls the Lipschitz continuity of the Poisson solution. The result holds whenever each Q^i(x) is irreducible, aperiodic, and Lipschitz continuous in x.

Load-bearing premise

Each transition matrix Q^i(x) remains irreducible and aperiodic for every occupation vector x, so the Dobrushin coefficient produces a uniform positive contraction independent of x.

Editorial extensions

If this is right

  • Stochastic approximation theory applies directly to the long-term dynamics of the joint occupation measure.
  • The analysis covers systems of multiple walks whose transition rows may differ.
  • The condition holds without assuming strictly positive entries in the transition matrices.
  • Arguments previously developed for single self-reinforced walks extend and simplify to the interacting case.

Reading between the lines

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

  • The Poisson decomposition technique could transfer to other non-Markovian reinforcement schemes whose transition kernels admit comparable uniform contraction bounds.
  • Occupation-measure convergence results obtained this way might be combined with existing limit theorems for stationary processes to obtain almost-sure convergence rates.
  • If analogous Dobrushin-type bounds can be established on infinite graphs, the same Clark-Kushner verification would become available for reinforced walks on countable state spaces.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 1 minor

Summary. The manuscript establishes the Clark-Kushner condition for a class of interacting vertex-reinforced random walks on finite graphs. Each walk has a transition matrix Q^i(x) that depends on the joint occupation vector x, may have distinct rows, and is assumed irreducible and aperiodic for every x with x ↦ Q^i(x) Lipschitz. The noise is decomposed via the Poisson equation solution into a martingale-difference term minus the increment of a bounded process (following Gordin), with the key technical step being a uniform geometric ergodicity bound obtained from the Dobrushin coefficient; this bound is also asserted to control the Lipschitz constant of the Poisson solution. The hypotheses do not require strictly positive entries. The result is claimed to generalize and simplify earlier arguments for single self-reinforced walks.

Significance. If the uniform ergodicity and Lipschitz control on the Poisson solution are valid under the stated hypotheses, the work would supply a general tool for applying stochastic-approximation theory to occupation-measure dynamics of interacting reinforced walks on finite graphs. The avoidance of a uniform-positivity assumption is a potential strength relative to prior literature. The significance is limited by the fact that the central technical ingredient (uniform Dobrushin bound) is not obviously implied by the listed hypotheses.

major comments (2)
  1. [Abstract] Abstract (paragraph on hypotheses and key technical ingredient): the assertion that 'a uniform geometric ergodicity bound derived from the Dobrushin contraction coefficient' follows from irreducibility, aperiodicity, and Lipschitz continuity of each Q^i(x) is not justified. On a finite state space every fixed irreducible aperiodic chain is geometrically ergodic, yet δ(Q(x)) = max_{i,j}‖Q(x)(i,·)−Q(x)(j,·)‖_TV can approach 1 along a sequence x_n while remaining strictly less than 1 at each individual x (for example by letting a single transition probability tend continuously to zero). Lipschitz continuity of x ↦ Q^i(x) does not preclude this degeneration, so the geometric rate need not be uniform and the Lipschitz constant of the Poisson solution may become unbounded.
  2. [Abstract] Abstract (paragraph on hypotheses): the claim that the family {Q^i(x)} 'admits a uniform geometric ergodicity bound' under the sole listed conditions is load-bearing for the Clark-Kushner verification. No supplementary hypothesis (e.g., a uniform lower bound on the entries of Q^i(x) or a uniform bound on the Dobrushin coefficient away from 1) is stated, and the manuscript does not appear to supply an independent argument that prevents δ(Q(x)) from approaching 1.
minor comments (1)
  1. [Abstract] Abstract: the phrase 'may have distinct rows' is mentioned but its role in the subsequent arguments is not clarified.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive report. The two major comments correctly note that the abstract asserts a uniform geometric ergodicity bound without supplying an explicit argument or supplementary hypothesis, and that the listed conditions alone do not preclude the Dobrushin coefficient from approaching 1. We address each comment below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Abstract] Abstract (paragraph on hypotheses and key technical ingredient): the assertion that 'a uniform geometric ergodicity bound derived from the Dobrushin contraction coefficient' follows from irreducibility, aperiodicity, and Lipschitz continuity of each Q^i(x) is not justified. On a finite state space every fixed irreducible aperiodic chain is geometrically ergodic, yet δ(Q(x)) = max_{i,j}‖Q(x)(i,·)−Q(x)(j,·)‖_TV can approach 1 along a sequence x_n while remaining strictly less than 1 at each individual x (for example by letting a single transition probability tend continuously to zero). Lipschitz continuity of x ↦ Q^i(x) does not preclude this degeneration, so the geometric rate need not be uniform and the Lipschitz constant of the Poisson solution may become unbounded.

    Authors: We agree that the referee's counter-example is valid and that the abstract's phrasing overstates what follows from the stated hypotheses alone. The manuscript's proof of the Clark-Kushner condition relies on a uniform bound on the Dobrushin coefficient, but this bound is not automatically inherited from irreducibility, aperiodicity and Lipschitz continuity. We will revise the abstract to remove the unqualified claim and will add a short remark (or, if needed, a mild supplementary hypothesis) that ensures sup_x δ(Q(x)) < 1. This revision will also make explicit how the uniform bound controls the Lipschitz constant of the Poisson solution. revision: yes

  2. Referee: [Abstract] Abstract (paragraph on hypotheses): the claim that the family {Q^i(x)} 'admits a uniform geometric ergodicity bound' under the sole listed conditions is load-bearing for the Clark-Kushner verification. No supplementary hypothesis (e.g., a uniform lower bound on the entries of Q^i(x) or a uniform bound on the Dobrushin coefficient away from 1) is stated, and the manuscript does not appear to supply an independent argument that prevents δ(Q(x)) from approaching 1.

    Authors: We concur that the current statement of hypotheses is insufficient to guarantee the uniform bound and that the manuscript does not contain an independent argument preventing degeneration of δ(Q(x)). We will therefore either (i) insert a brief argument showing that the finite-graph structure plus the specific form of the reinforcement prevents δ(Q(x)) from approaching 1, or (ii) add an explicit uniform-Dobrushin hypothesis. In either case the abstract and the statement of main results will be updated to reflect the corrected set of assumptions. revision: yes

Circularity Check

0 steps flagged · score 2.0 of 10

Low circularity: derivation applies standard Markov tools to explicit hypotheses without self-referential reduction

full rationale

The paper decomposes noise via the Poisson equation for Markov chains (Gordin structure) and invokes the Dobrushin coefficient to obtain a uniform geometric ergodicity bound under the stated hypotheses (each Q^i(x) irreducible, aperiodic, and Lipschitz in x). These are external, standard results on finite-state chains; no equation or claim reduces the target Clark-Kushner condition to a fitted parameter, self-defined quantity, or load-bearing self-citation by construction. The note that results generalize prior single-walk arguments is a minor self-citation that does not carry the interacting-case proof.

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

The proof rests on standard Markov-chain assumptions (irreducibility, aperiodicity) and the existence of a uniform Dobrushin contraction that yields both ergodicity and Lipschitz continuity of the Poisson solution; no free parameters or invented entities are introduced.

assumptions (2)
  • domain assumption Each transition matrix Q^i(x) is irreducible and aperiodic for every occupation vector x
    Stated in the hypotheses paragraph of the abstract; required for the Poisson equation to be well-posed and for the Dobrushin bound to apply.
  • domain assumption The family of chains admits a uniform geometric ergodicity bound controlled by the Dobrushin contraction coefficient
    Central technical ingredient invoked to control both mixing and the Lipschitz property of the Poisson solution.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Clark-Kushner condition for interacting reinforced random walks on finite graphs." pith.science (2026). https://pith.science/paper/I2QTV773

@misc{pith2026260605377,
  author       = {Pith},
  title        = {Pith review of: The Clark-Kushner condition for interacting reinforced random walks on finite graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/I2QTV773}},
  note         = {Machine review of arXiv:2606.05377}
}
abstract

We establish the Clark-Kushner condition for a large class of interacting vertex-reinforced random walks on finite graphs, where the transition matrix $Q^i(x)$ of each walk depends on the joint vector $x$ of vertex occupation proportions and may have distinct rows. This allows one to study the dynamics of the vertex occupation measure by using the tools of stochastic approximation theory. However, the standard approach fails because the noise inputs are in our case not a martingale difference: they retain memory of the previous state. Using the solution of the Poisson equation for Markov chains, we decompose the noise into a martingale difference minus the increment of a bounded process -- a structure originating in Gordin's work on limit theorems for stationary processes. The key technical ingredient of our approach is a uniform geometric ergodicity bound derived from the Dobrushin contraction coefficient, which also controls the Lipschitz continuity of the solution of the Poisson equation. Our hypotheses require only that each $Q^i(x)$ be irreducible, aperiodic, and Lipschitz continuous in $x$; in particular, strictly positive entries are not assumed. Our results generalize and simplify previous arguments considered for single self-reinforced vertex-reinforced random walks.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 1 canonical work pages

  1. [1]

    Bena¨ ım

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

    1996

  2. [2]

    Bena¨ ım

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

    1997

  3. [3]

    Bena¨ ım

    M. Bena¨ ım. Dynamics of stochastic approximation algorithms. InS´ eminaire de Probabilit´ es XXXIII, Lecture Notes in Math. 1709, pages 1–68. Springer, 1999

    1999

  4. [4]

    Bena¨ ım, O

    M. Bena¨ ım, O. Raimond, and B. Schapira. Strongly vertex-reinforced random walk on a complete graph.ALEA Lat. Am. J. Probab. Math. Stat., 10(2):767–782, 2013

    2013

  5. [5]

    Bena¨ ım and P

    M. Bena¨ ım and P. Tarr` es. Dynamics of vertex-reinforced random walks.Ann. Probab., 39(6):2178–2223, 2011

    2011

  6. [6]

    Coppersmith and P

    D. Coppersmith and P. Diaconis. Random walks with reinforcement. Unpublished manuscript, 1987

    1987

  7. [7]

    Cotar and D

    C. Cotar and D. Thacker. Edge- and vertex-reinforced random walks with super-linear reinforcement on infinite graphs.Ann. Probab., 45(4):2655–2706, 2017. CLARK-KUSHNER CONDITION FOR INTERACTING REINFORCED RANDOM W ALKS 9

    2017

  8. [8]

    M. I. Gordin. The central limit theorem for stationary processes.Dokl. Akad. Nauk SSSR, 188:739–741, 1969

    1969

Show all 20 references
  1. [9]

    M´ etivier and P

    M. M´ etivier and P. Priouret. Applications of a Kushner and Clark lemma to general classes of stochastic algorithms.IEEE Trans. Inform. Theory, 30(2):140–151, 1984

    1984

  2. [10]

    M´ etivier and P

    M. M´ etivier and P. Priouret. Th´ eor` emes de convergence presque sˆ ure pour une classe d’algorithmes stochastiques ` a pas d´ ecroissant.Probab. Theory Related Fields, 74:403–428, 1987

    1987

  3. [11]

    Maxwell and M

    M. Maxwell and M. Woodroofe. Central limit theorems for additive functionals of Markov chains. Ann. Probab., 28(2):713–724, 2000

    2000

  4. [12]

    Pemantle

    R. Pemantle. Vertex-reinforced random walk.Probab. Theory Related Fields, 92(1):117–136, 1992

    1992

  5. [13]

    F. P. A. Prado, C. F. Coletti, and R. A. Rosales. Two repelling random walks on Z.Stochastic Process. Appl., 160:72–88, 2023

    2023

  6. [14]

    F. P. A. Prado and R. A. Rosales. Interacting vertex-reinforced random walks on complete sub-graphs. Preprint, arXiv:2508.15992, 2025

    2025

  7. [15]

    Pemantle and S

    R. Pemantle and S. Volkov. Vertex-reinforced random walk onZhas finite range.Ann. Probab., 27(3):1368–1388, 1999

    1999

  8. [16]

    R. A. Rosales, F. P. A. Prado, and B. Pires. Vertex reinforced random walks with exponential interaction on complete graphs.Stochastic Process. Appl., 148:353–379, 2022

    2022

  9. [17]

    Seneta.Non-negative Matrices and Markov Chains

    E. Seneta.Non-negative Matrices and Markov Chains. Springer Series in Statistics. Springer, New York, 2nd edition, 1981

    1981

  10. [18]

    Tarr` es

    P. Tarr` es. Vertex-reinforced random walk onZeventually gets stuck on five points.Ann. Probab., 32(3B):2650–2701, 2004

    2004

  11. [19]

    S. Volkov. Vertex-reinforced random walk on arbitrary graphs.Ann. Probab., 29(1):66–91, 2001

    2001

  12. [20]

    W. B. Wu and M. Woodroofe. Martingale approximations for sums of stationary processes.Ann. Probab., 32(2):1674–1690, 2004. (F. P. A. Prado)Departamento de Computa c ¸˜ao e Matem´atica, Universidade de S ˜ao Paulo, Avenida Bandeirantes 3900, Ribeir˜ao Preto, S˜ao Paulo, 14040-9...

    2004

Pith tools

Reviewed June 28, 2026 · model on record in the stance chip above.