Dynamics of vertex-reinforced random walks (Q653301)

Let \(G\) be a set of vertices of a locally finite connected symmetric graph. The authors study a vertex-reinforced random walk (VRRW) \((X_n)_{n\in \mathbb{Z}_+}\) taking values in \(G\). Namely, for \(X_0=v_0\) (\(v_0 \in G\)) and symmetric matrix \((a_{i,j})_{i,j\in G}\) with nonnegative entries, \[ \text{P}(X_{n+1}=j|X_0,\ldots,X_n)= \mathbb{I}_{\{j\sim X_n\}}\frac{a_{X_n,j}Z_n(j)}{\sum_{k\sim X_n}a_{X_n,k}Z_n(k)}, \] where \(i\sim j \Leftrightarrow a_{i,j} >0\), \(Z_n(i)=Z_0(i)+\sum_{m=0}^n\mathbb{I}_{\{X_m=i\}}\) and the values of \(Z_0(i)\) belong to \(\mathbb{R}_+\setminus \{0\}\). It is proved that VRRW eventually localizes with positive probability on subsets which consist of a complete \(d\)-partite subgraph with possible loops plus its outer boundary. Thus an extension of a result by \textit{S. Volkov} [``Vertex-reinforced random walk on arbitrary graphs'', Ann. Probab. 29, No. 1, 66--91 (2001; Zbl 1031.60089)] is obtained. For this purpose, it is shown that any stable equilibrium of a linear symmetric replicator dynamics with positive pay-off on a graph under consideration has a similar localization property. Next, the authors provide a generalization of the results (concerning the asymptotic behavior of the VRRW and replicator dynamics) by \textit{R. Pemantle} [``Vertex-reinforced random walk'', Probab. Theory Relat. Fields 92, No. 1, 117--136 (1992; Zbl 0741.60029)] and by \textit{M. Benaïm} [``Vertex-reinforced random walks and a conjecture of Pemantle'', Ann. Probab. 25, No. 1, 361--392 (1997; Zbl 0873.60044)]. This enables them to demonstrate that, given any neighborhood of a strictly stable equilibrium with support \(S\), one can claim that with positive probability the walk localizes on \(S\cup \partial S\) (here, \(\partial S\) is the outer boundary of \(S\)) and the density of occupation of the VRRW converges, with polynomial rate, to a strictly stable equilibrium in this neighborhood.