Attracting Edges in Strongly Reinforced Random Walks

Definitions and mathematical statement

A customary model of undirected edge-reinforced random walk on a connected, locally finite simple graph $G=(V,E)$ is as follows. Fix a positive weight function $W:{\mathbb{Z}}_{\geq0}\to(0,\infty)$, and let $N_n(e)$ count traversals of the unoriented edge $e$ before time $n$. Starting at a prescribed vertex, the transition probabilities are \[ \Pr(X_{n+1}=y\mid X_0,\ldots,X_n) =\frac{W(N_n(\{X_n,y\}))}{\sum_{z:\{X_n,z\}\in E}W(N_n(\{X_n,z\}))} \quad (\{X_n,y\}\in E). \] Here $N_0(e)=0$; an indexing starting at one can instead absorb the initial index into the weight function. The strong-reinforcement hypothesis in the record is reciprocal summability, \[ \sum_{k=0}^{\infty}\frac1{W(k)}<\infty. \] The attracting-edge question asks whether \[ \Pr\left(\exists e\in E\ \exists n_0<\infty\ \forall n\geq n_0: \{X_n,X_{n+1}\}=e\right)=1 \] for graphs containing odd cycles, in particular for the triangle $G=C_3$. The edge and the trapping time may depend on the sample path. In the triangle case the customary formulation quantifies over the positive reciprocally summable weight functions and starting vertices.

The source compares this question with the asserted result for bounded-degree graphs having no odd cycles. It does not explicitly repeat the bounded-degree hypothesis for the class containing odd cycles, specify finite versus infinite graphs, impose monotonicity on $W$, or give initial edge weights. Consequently the displayed transition rule provides an explicit conventional model, while the exact general graph class and any further weight or initialization hypotheses must be checked in the cited report. No unrestricted assertion for every locally finite graph or every possible initialization is inferred here.

Short English statement

Under reciprocal summability of the reinforcement weights, must the walk almost surely become trapped on one random edge and alternate between its endpoints, even on a triangle or other graph containing an odd cycle? The full graph class and weight conventions need source review.

Sources

• Local UnsolvedMath registry, permanent ID $30000773$, source code catalogue entry, "Attracting Edges in Strongly Reinforced Random Walks." No individual proposer is supplied.
• Non-Classical Interacting Random Walks (2008), Oberwolfach Reports, DOI 10.4171/owr/2007/27, pp. 1521--1574: https://doi.org/10.4171/owr/2007/27.
• Supplied reference, "Limic--Tarrès, square versus triangle": https://arxiv.org/abs/0712.0958.
• The literature triage checked 2026-08-21 labels the problem partially solved, reports the square and even-cycle cases proved, and says that the triangle case is not settled by the cited methods. Failure of those methods is not itself a verification of present-day openness of the triangle case.