Edge-reinforced random walk on one-dimensional periodic graphs (Q842382)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Edge-reinforced random walk on one-dimensional periodic graphs |
scientific article |
Statements
Edge-reinforced random walk on one-dimensional periodic graphs (English)
0 references
25 September 2009
0 references
Consider an undirected locally finite graph \(G=(V,E)\) with vertex set \(V\) and edge set \(E\). A linearly edge reinforced random walk is the discrete time process on \(V\) that at time \(n\) jumps from \(v\) to a neighbor \(w\) along the edge \(e\) with a probability proportional to \(a_e+i_e(n)\) where \(i_e(n)\) is the number of times \(e\) has been traversed up to time \(n\) and \((a_e)_{e\in E}\) is the collection of initial weights. Now, consider the special case where \(V=\mathbb{Z}\times W\) for some finite graph \(W\) and with the edges \(\{(i,v),(i,w)\}\) if \(\{v,w\}\) is an edge of \(W\) and \(\{(i,w),(i+1,w)\}\) for all \(i\in\mathbb{Z}\). Furthermore, assume that the initial weights are strictly positive and periodic. For example, this includes the \(d\)-ladder graph \(\mathbb{Z}\times\{1,\dots,d\}\subset\mathbb{Z}^2\) with constant initial weights. The authors show (under somewhat weaker conditions on the underlying graph) that the linearly edge reinforced random walk is recurrent (this was known for \(\mathbb{Z}\) and the 2-ladder graph before but is still open for \(\mathbb{Z}^2\)). Furthermore, they give estimates on the position of the random walker and show exponential decay of hitting probabilities. Finally, they show that the process can be represented uniquely as a mixture of positive recurrent Markov chains. The present work generalizes works of [Ann. Probab. 33, No.~6, 2051--2093 (2005; Zbl 1102.82010) and Probab. Theory Relat. Fields 135, No.~2, 216--264 (2006; Zbl 1206.82045)] to a larger class of graphs but uses different techniques that employ reflection symmetry of the underlying graph.
0 references
reinforced random walk
0 references
recurrence
0 references
random environment
0 references
0 references