# Stochastic processes with competing reinforcements

Dirk Erhard  UFBA
Instituto de Matemática, Campus de Ondina, Av. Adhemar de Barros, S/N. CEP
40170-110
Salvador, Brazil<EMAIL_ADDRESS>and  Guilherme Reis  TUM
Technical University of Munich, Faculty of Mathematics, Boltzmannstrasse 3,
85748 Garching bei München, Germany<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

We introduce a simple but powerful strategy to study processes driven by two
or more reinforcement mechanisms in competition. We apply our method to two
types of models: to non conservative zero range processes on finite graphs,
and to multi-particle random walks with positive and negative reinforcement on
the edges. The results hold for a broad class of reinforcement functions,
including those with superlinear growth. Our strategy consists in a comparison
of the original processes with suitable reference models. To implement the
comparison we estimate a Radon-Nikodym derivative on a carefully chosen set of
trajectories. Our results describe the almost sure long time behaviour of the
processes. We also prove a phase transition depending on the strength of the
reinforcement functions.

###### Key words and phrases:

Reinforced random walk, ant random walk, directed edges, random walk on graphs

###### 2010 Mathematics Subject Classification:

60K35, 60K37, 60G50

##  1\. Introduction

#### Description of the models.

In this work we consider two stochastic processes. Our first model is a _Non
Conservative Zero Range process_ (NCZR) on a finite graph $G$. This process
starts with a finite number of walkers and is described by a field
$(\eta(n))_{n\geq 0}=(\eta_{v}(n):v\in G)_{n\geq 0}$ of natural numbers that
represent the quantity of particles at each vertex $v\in G$ at a given
discrete time $n$. Given three functions
$W_{1},W_{2},W_{3}:{\mathbb{N}}\to{\mathbb{R}}_{+}$ the dynamics of $\eta$ at
time $n+1$ evolves as follows:

  * •

A particle is created at site $v$ with a probability proportional to
$W_{1}(\eta_{v}(n)).$

  * •

A particle is annihilated at site $v$ with a probability proportional
to $W_{2}(\eta_{v}(n))$.

  * •

A particle jumps from $v$ to a neighbour $w$ with a probability proportional
to $W_{3}(\eta_{v}(n))$.

See Section 3 for a complete definition of the NCZR.

In the second model, called the _Multi Particle Ant Random Walk_ (Ant RW),
which itself is an adaptation of a similar model introduced by Erhard, Franco
and Reis in [6], we consider a finite quantity of walkers $(X_{i}(n)\,:\,1\leq
i\leq N)_{n\geq 0}$ that interact through a dynamical environment on a finite
graph $G=(V,E)$, given by a field $\\{c_{n}(\vec{e}),\,n\geq 0\\}_{\vec{e}}$
indexed by the set of oriented edges of $G$. Given $\vec{e}=(e_{-},e_{+})\in
E$, the quantity $c_{n}(\vec{e})$ is the number of jumps of the collection of
walkers $(X_{i})_{i}$ over $\vec{e}$ minus the number of jumps over the
reversed edge $(e_{+},e_{-})$ up to time $n$. We refer to this quantity in the
sequel as the crossing number of the edge $\vec{e}$. Observe that
$c_{n}(\vec{e})$ can be either negative or positive. Assume that the walker
$X_{j}$ is at time $n$ on the vertex $e_{-}$. Then it will jump to $e_{+}$
with a probability proportional to:

  * •

$W_{1}(c_{n}(\vec{e}))$ if $c_{n}(\vec{e})\geq 0$.

  * •

$W_{2}(-c_{n}(\vec{e}))$ if $c_{n}(\vec{e})<0.$

Here, $W_{1}:{\mathbb{N}}\to{\mathbb{R}}_{+}$ and
$W_{2}:{\mathbb{N}}\to{\mathbb{R}}_{+}$ are two given functions that modulate
the behaviour of the model. We refer to Section 4 for a full description of
that process.

Question: For which choices of functions $W_{1},W_{2}$ and $W_{3}$ do the two
models above localise?

To get a better feeling for what we mean by localisation we will provide a
loose statement of our main results for a particular class of functions
$W_{1},W_{2}$ and $W_{3}$. Rigorous statements are deferred to later sections.

To that end fix $p,q,r\in{\mathbb{R}}$ and define the three functions alluded
to above via $W_{1}(k)=k^{p}$, $W_{2}(k)=k^{q}$, and $W_{3}(k)=k^{r}.$ We
introduce the following events which we will use only in the context of the
NCZR:

  * •

${\rm Creat}$ is the event that after some finite time $n$, there are no jumps
or annihilation of particles, only creations.

  * •

${\rm Mon}$ is the event that there is a unique site $w$ such that eventually
for all large $n$ the only transformation in the system takes the form
$\eta_{w}(n+1)=\eta_{w}(n)+1$ (monopoly).

Note that if ${\rm Mon}$ occurs then the system is indeed completely localised
in the sense that there exists a time $m$ such that after $m$ for all sites
$v\neq w\in G$ the number of particles at $v$ does not change. If ${\rm
Creat}$ occurs after some time $m$ particles are only created, never
annihilated and do not swap sites.

######  Theorem 1.1.

One has the following phase transition depending on $p,q,r\in{\mathbb{R}}:$

  1. (1)

if $p\leq 1+\max\\{q,r\\}$ then ${\mathbb{P}}({\rm Creat})=0,$

  2. (2)

if $p>1+\max\\{q,r,0\\}$ then ${\mathbb{P}}({\rm Creat})=1,$ and
${\mathbb{P}}({\rm Mon})=1$.

$u=\max\\{q,r\\}$01-1MonopolyComplement of CreatNot known$p$1-1 Figure 1.
Phase transition diagram.

Notice in Figure 1 that for the case $\max\\{q,r\\}\leq 0$ we assume $p>1$ to
prove that the Monopoly event happens with probability one. Furthermore, the
Monopoly event happens with probability one if $\max\\{q,r\\}>0$ and
$p>1+\max\\{q,r\\}$. In the case $p\leq 1+\max\\{q,r\\}$, Theorem 1.1 says
that the Creation event does not happen almost surely. Observe that Theorem
1.1 does not cover the case $\max\\{q,r\\}\leq 0$ and and
$1+\max\\{q,r\\}<p\leq 1$.

Now we loosely state our main result for the Ant RW with $N\geq 1$ walkers in
the special case that $W_{1}(k)=k^{p}$ and $W_{2}(k)=k^{q}.$ We start with
some loose definitions to provide an idea, precise statements are postponed to
Section 4 :

  * •

We call a circuit $C$ a trapping circuit if there is a walker that eventually
will spin around $C$ forever without leaving it.

Similarly to the previous model we introduce two events that will be used only
in the context of the Ant RW:

  * •

${\rm Monot}$ is the event that for any directed edge $\vec{e}$ the map
$n\mapsto c_{n}(\vec{e})$ is monotone (incresing or decreasing) for large
times.

  * •

${\rm LocTrapp}$ is the event that ${\rm Monot}$ occurs and there are disjoint
circuits $(C_{i})_{1\leq i\leq k}$that are trapping circuits. Moreover, any
circuit that is crossed infinitely many times is a trapping circuit.

Note that if ${\rm LocTrapp}$ occurs, then the walkers eventually localize (or
are trapped) in the circuits $(C_{i})_{1\leq i\leq k}$.

######  Theorem 1.2.

Assume the the graph $G$ has at least two circuits. One has the following
phase transition depending on $p,q\in{\mathbb{R}}:$

  1. (1)

if $p\leq 1+q$ then ${\mathbb{P}}({\rm Monot})=0,$

  2. (2)

if $p>1+\max\\{q,0\\}$ then ${\mathbb{P}}({\rm LocTrapp})=1.$

$q$01-1LocTrappComplement of MonotNot known$p$1-1 Figure 2. Phase transition
diagram.

Notice in Figure 2 that for the case $q\leq 0$ we assume $p>1$ to prove that
the Local Trapping event happens with probability one. Furthermore, the Local
Trapping event happens with probability one if $q>0$ and $p>1+q$. In the case
$p\leq 1+q$, Theorem 1.2 says that the Monotone event does not happen almost
surely. Observe that Theorem 1.2 does not cover the case $q\leq 0$ and and
$1+q<p\leq 1$.

See Theorems 4.1 and 4.3 for a complete statement.

######  Remark 1.3.

The above result implies that trapping in a circuit does not follow alone from
the summability of the inverse of $W_{1}$. By [5] for the edge reinforced
random walk that would be sufficient. Indeed, in the current framework what
matters as well is the relation between the reinforcements we impose on edges
with positive and negative crossing numbers $c_{n}(\vec{e})$. One needs to
guarantee that the walkers have a bias towards choosing edges with positive
crossing numbers.

Before reviewing the literature, we present some figures to illustrate Theorem
1.2.

abcdefghij Figure 3. Example of a finite graph.

Assume that the graph $G$ is as in Figure 3 above, and assume that $p>1+q$.
Then the above theorem states that the set of walkers split the graph into
disjoint subsets in the sense that eventually different groups of walkers spin
around disjoint circuits of the graph. For example it may happen that
eventually the walkers will be stuck in the thick circuits $(g,i,j,h)$ and
$(c,d,f,e)$ in Figure 4, and the missing edges will be crossed only a finite
number of times.

abcdefghij Figure 4. Trapping circuits for $p>1$.

The above models fit in the class of random processes with reinforcement. The
basic models are urn models and its many variants. We refer the reader to the
survey of Pemantle [15] for an overview. Here, we will restrict ourselves only
to those models that are closely related to ours.

There are manifold motivations to study random processes with reinforcement.
One of them is that they can be used to model the behaviour of ants. The
article [11] from the computer science community, studies an algorithm based
on random walks. The algorithm is designed to detect communities on complex
networks and uses the idea that ants learn through the pheromone they leave on
their path. Regarding the probability community, the authors in [8] propose a
model to find a shortest path between two points in a graph through
reinforcement learning. Roughly speaking, the ants perform successive random
walks in the graph and, when it finds the food, its path is reinforced
according to a reinforcement rule. Their methods are based on electrical
network techniques for random walks and on Rubin’s construction.

#### Literature on non conservative zero range process

Non conservative versions of the well known zero range process have attracted
interest in the physics as well as in the mathematics community. To the best
of our knowledge models of similar kind were first introduced in [2] with the
aim to model chemical reactions.

With the goal to understand condensation phenomena the physics paper [1]
considers a model similar to ours. Based on heuristic arguments they developed
a detailed phase diagram depending on the rates of creation, annihilation, and
jump, when the number of sites tends to infinity.

Regarding the mathematics community the article [7] is the most relevant for
our discussion. Motivated by earlier works, in particular by [3, 4], the
authors consider the model on the discrete one dimensional torus with $N$
vertices. They fix functions $b,d\,:\,{\mathbb{R}}_{+}\to{\mathbb{R}}_{+}$
that determine the rate of creation and annihilation, and each particle jumps
independently of all other particles. Sending $N\to\infty$, the authors
established a law of large numbers for the density of particles under an
appropriate rescaling. In particular if $b(s)-d(s)=s^{p}$, for $1<p\leq 3$,
the limiting equation defined on the one-dimensional torus takes the form

$\partial_{t}u=\partial_{xx}u+u^{p}\,.$ (1.1)

This equation is interesting, since under an appropriate boundary condition it
is known that [16, Proposition 28.1] if $p>3$ the equation has a solution
whose $L^{1}$-norm is finite but whose $L^{\infty}$ blows up, whereas for
$p<3$ both norms blow up. In Theorem 1.1 we can observe one part of that
phenomena that is similar in nature. Indeed, if $p$ is large enough, then
there is a unique site on which particles are created and all other sites are
at a stand still (corresponding to a blow-up of the $L^{\infty}$ but not the
$L^{1}$-norm).

The difference to the present work of course is that the particles do not jump
independently of each other (except in the case in which $r=1$), and space is
fixed.

#### Comparison with the Edge Reinforced Random Walk.

The Edge Reinforced Random Walk (ERRW) on undirected graphs is defined in a
similar way as the Ant RW. However, for the ERRW one considers undirected
edges, and typically only a single walker. More precisely, one assigns a
weight $c_{n}(e)$ to each undirected edge $e$, where $c_{n}(e)$ is the number
of times that the walker crossed $e$ irrespective of the direction. In this
case only one reinforcement function $W_{1}$ is needed and the rate to cross
an edge $e$ (in any direction) is given by $W_{1}(c_{n}(e))$. In particular,
if the walker crossed $e$ it increases the chances of crossing it in the
opposite direction. This is not the case for the Ant RW.

The Ant RW shares some similarities with the ERRW on directed graphs but these
two processes are not equal. Indeed, as described in [15], in the ERRW on
directed graphs each directed edge $\vec{e}=(u,v)$ has the crossing number
$c_{n}(u,v)$ defined to be as the number of times $1\leq i\leq n$ such that
$X_{i-1}=u$ and $X_{i}=v$. Observe that for the Ant RW we subtract from
$c_{n}(u,v)$ the number of times $1\leq i\leq n$ such that $X_{i-1}=v$ and
$X_{i}=u$ and we have the relation $c_{n}(u,v)=-c_{n}(v,u)$. As a consequence,
for the Ant RW the probabilities of successive transitions out a vertex $u$
are affected by the edge the RW used to arrive at $u$. This is not the case
for the ERRW on directed edges. Therefore, even though we use directed edges
in our definition of the Ant RW, our model is very different from the ERRW on
directed graphs.

The behaviour of the ERRW depends on the assumption one makes about the
reinforcement function $W_{1}$. Two cases are of particular interest. The case
of superlinear reinforcement, i.e., $\sum_{k}W_{1}(k)^{-1}<\infty$, and the
case of linear reinforcement, i.e., $W_{1}(k)=k$. In the case of superlinear
reinforcement the walker localizes on a single edge, i.e., it eventually only
jumps across that edge. This phenomena does not occur if the reinforcement is
linear. In that case the question of interest is whether the walker is
recurrent or transient [14, 12]. A feature used to study such a question is
that the ERRW with linear reinforcement is partially exchangeable. We point
out that our models are not partially exchangeable due the nature of the
reinforcement mechanism.

In our model we observe and study different phenomenas. Indeed, under suitable
conditions on the relation between $W_{1}$ and $W_{2}$, if $W_{1}$ grows
superlinearly localization happens on a circuit, i.e., on at least three
edges.

As noted in [15, Section 5.1] for the ERRW either on directed graphs and on
trees a direct coupling with a collection of independent Pólya urns are
possible. The behaviour of the ERRW on these classes of graphs are
successfully described through this coupling. However, for more general graphs
this is not possible. A frequent strategy presented in several works is to
implement a comparison of the ERRW with Pólya urns schemes instead of a direct
coupling. A strategy that we also employ as we will explain.

The ERRW with superlinear reinforcement has a long history and it took various
stages of refinement to arrive at the full result. We mention here only some
selected works. The localization result in [10] is derived through a
construction of the ERRW similar to Rubin’s construction. To implement the
comparison with the Pólya urns scheme the author constructs a suitable super
martingale. However, in [10] the reinforcement function is restricted to the
form $W_{1}(k)=k^{p}$. In [9] the authors increased the class of reinforcement
functions for which the same localization result holds using a similar
strategy.

The problem was then finally completely solved in the work of Cotar and Tacker
[5]. The authors prove localization of the ERRW only assuming a superlinear
reinforcement. The techniques in [5] rely on estimates of the probability to
achieve a given configuration for the vector of crossing numbers
$(c_{n}(e))_{e}$ and it does not rely on Rubin’s construction.

The above mentioned methods do not seem to apply directly to our case. The
main reason is that for the ERRW the vector of numbers $(c_{n}(e))_{e}$ are
non negative and monotone in time. This is not satisfied in our case and we
need one additional step before pursuing a comparison with Pólya urns schemes.
On the other hand, our methods do not seem to apply to the ERRW on undirected
graphs. Our technique are designed for models with two or more reinforcement
functions in competition in the case that one reinforcement function dominates
the others.

#### Main ideas of the proof

Erhard, Franco, and Reis [6] introduced the Ant RW with exponential
reinforcement. There it is shown that a single walker eventually localizes in
a circuit. To obtain the result the authors derived a lower bound which is
uniform in the environment for the probability that the walker is trapped in a
carefully chosen circuit. No comparison with Pólya urns was needed. But the
method in [6] relied heavily on the choice of the exponential reinforcement
and does not work for more general reinforcement functions as in Theorem 1.2.
Indeed, for polynomial reinforcement, it can be shown that the probability of
being trapped in any circuit is arbitrarily close to zero as a function of the
environment.

Motivated by the mentioned previous works one can pursue a comparison with
Pólya urns schemes. However, at first sight this strategy seems to not apply
because, as pointed out before, the vector of crossing numbers for the Ant RW
is not monotone and can be negative. The crucial observation is that one can
seek a comparison with Pólya urns schemes conditioned on the event that the
vector of crossing numbers is monotone.

Our main achievement is to present a new way to implement this old strategy.
We do that by introducing a reference (or auxiliary) edge reinforced random
walk on a directed graph. The reference model is constructed via a Pólya urn
scheme which is easier to analyse. The next step is to compare the original
model with the reference model. We do the comparison via the Radon Nikodym
derivative of the two processes. We obtain a lower bound on the Radon Nikodym
derivative that is uniform on a carefully chosen set of trajectories. Then we
can conclude the argument via Borel Cantelli’s Lemma.

The proof for the NCZR then follows by an adaptation of the above arguments.

###  1.1. Structure of the paper

For pedagogical reasons we invert the presentation of the models in the paper.
We start with the simpler NCZR and then we study the Ant RW. The outline of
the article is as follows:

  * •

In Section 2 we introduce important notation and the balls-in-bins process.

  * •

In Section 3 we formally introduce the NCZR process and prove Theorem 1.1.

  * •

In Section 4 we formally introduce the Ant RW and fully state our main
results.

  * •

In Section 5 we prove the results about the Ant RW.

  * •

In the Appendix A we give examples of classes of functions $W_{1}$ and $W_{2}$
that satisfy our various assumptions.

##  2\. Preliminaries

In this section we fix some notation, terminology, and we review some results.

###  2.1. Natural numbers

We write ${\mathbb{N}}=\\{0,1,2,\cdots\\}$ for the set of natural numbers. For
$n\in{\mathbb{N}}$ we define the set $[n]=\\{1,\cdots,n\\}.$

Let $a,b\in{\mathbb{N}}$ with $a<b.$ We write $\llbracket a,b\rrbracket$ for
the discrete interval $\\{i\in{\mathbb{N}}\,:\,a\leq i\leq b\\}.$ We write
$\llbracket a,\infty)$ for the discrete interval
$\\{i\in{\mathbb{N}}\,:\,a\leq i\\}.$

###  2.2. Undirected and directed graphs

We start with graphs and its basic objects. An undirected graph $G$ is a pair
$(V,E)$ where $V$ is a countable set of vertices and $E$ is a set of unordered
pairs of $V$. Given two vertices $v$ and $w$ we write $v\sim w$ if the pair
$\\{v,w\\}$ forms an edge. The degree of $v$ in $G$, $\deg_{G}(v),$ is the
number of edges $\\{v,w\\}$ with $w\in V.$ All graphs considered in this work
are locally finite, connected, without parallel edges and without loops. We
associate to $G$ the following quantity

$\Delta(G)=\max_{v\in V}\deg_{G}(v),$ (2.1)

which is the maximum degree of $G$.

A directed graph $D$ is also a pair $(V,\vec{E})$ but in this case $\vec{E}$
is a set of ordered pairs of $V$. We define the outer degree of $v\in V$ via:

  * •

$\deg_{D}^{\rm out}(v)=|\\{(v,w)\in\vec{E}\,;\,w\in V\\}|.$

For an undirected graph $G=(V,E)$ we often identify each non-oriented edge
with two oriented edges. More specifically, we define the directed graph
$\vec{G}$ where $V(\vec{G})=V(G)$ and
$\vec{E}(\vec{G})=\\{(v,w),\,(w,v)\,:\,\\{v,w\\}\in E(G)\\}.$

###  2.3. Circuits and paths

We introduce some objects for directed graphs. The definitions for undirected
graphs are similar and will be omitted.

Let $D=(V,\vec{E})$ be a directed graph. We say that a collection of vertices
$C=(u_{0},\ldots,u_{\ell-1})$ is a circuit of length $\ell$ with starting
point $u_{0}$ if (1) $u_{i}\neq u_{j}$ for $0\leq i\neq j\leq\ell-1$ , (2)
$(u_{i},u_{i+1})\in\vec{E}$ for $0\leq i\leq\ell-2$ and if moreover (3)
$(u_{\ell-1},u_{0})\in\vec{E}$. We also identify two circuits $C$ and
$C^{\prime}$, if one can be obtained from the other by a rotation. This
defines an equivalence relation, and any circuit $C$ is identified with its
equivalence class. We write $C(D)$ for the total number of circuits in the
directed graph $D$.

A path in $D$ is a map $\pi\,:\,{\mathbb{N}}\to V$ such that
$(\pi(i),\pi(i+1))\in\vec{E}$, for all $i\in{\mathbb{N}}$.

Let $X$ be a set and $f:{\mathbb{N}}\to X$ a function. For
$a,b\in{\mathbb{N}}$ and $a<b$ one defines the restriction $f_{a}^{b}$ as the
map $n\in\llbracket a,b\rrbracket\mapsto f(n)$. Similarly, we write
$f_{a}^{\infty}$ for the restriction of $f$ to the interval $\llbracket
a,\infty)$.

###  2.4. Lattice version of a directed graph

Given a directed graph $D$ as above, we consider a finite family of random
walks on $D$ such that two distinct walkers never jump at the same time. It is
convenient to describe all random walks as a single object. For that reason we
introduce the lattice version of $D.$

We fix a directed graph $D=(V,\vec{E})$ and a number $N\in{\mathbb{N}}$ of
particles. We write $D^{N}$ for the lattice version of $D$ of dimension $N$
and it is the graph with vertex set

$V^{N}=\\{\vec{v}:=(v_{1},\ldots,v_{N}):\,v_{1},\ldots,v_{N}\in V\\}\,,$

and edge set

$\begin{split}\vec{E}^{N}=\\{(\vec{v},\vec{w})\in V^{N}\times
V^{N}:&\,\exists\,j\in\\{1,2,\ldots,N\\}\\\ &\text{ s.t.
}v_{i}=w_{i}\,\forall\,i\neq j\text{ and
}(v_{j},w_{j})\in\vec{E}\\}.\end{split}$

Observe that the standard lattice ${\mathbb{Z}}^{N}$ is the lattice version of
${\mathbb{Z}}.$ The collection of random walks will be described as a single
(random) trajectory $\pi\,:\,{\mathbb{N}}\longrightarrow V^{N}.$

###  2.5. Markov chains and stopping times

Let $(Z_{n})_{n\in{\mathbb{N}}}$ be a discrete time Markov chain and
$({\mathcal{F}}_{n})_{n\in{\mathbb{N}}}$ be its natural filtration. For
$k\in{\mathbb{N}}$ we define the shift operator ${\mathcal{S}}_{k}$ which
associates $(Z_{n})_{n\in{\mathbb{N}}}$ with $(Z_{n})_{n\geq k}\,,$ i.e.
$({\mathcal{S}}_{k}\circ Z)_{n}=Z_{n+k}$ for all $n\in{\mathbb{N}}$.

Given a stopping time $\tau$ and $k\in{\mathbb{N}}$ we define the stopping
time $\tau\circ{\mathcal{S}}_{k}$ which is the original stopping $\tau$ seen
as a function of $(Z_{n})_{n\geq k}.$ The above construction makes also sense
if we replace $k$ by another stopping time that is finite almost surely.

###  2.6. Balls-in-Bins with feedback

We introduce an essential example of a reinforcement process for this work.

Let $S$ be a finite set. We consider a vector evolving in time
$(\eta_{v}(n);\,v\in S)_{n\in{\mathbb{N}}}.$ We can interpret $\eta_{v}(n)$ as
the number of balls in bin $v\in S$ at time $n$. In our examples we will
choose $S$ as either the set of vertices of a finite graph or the set of
neighbours of a fixed vertex. To throw a ball into the bin $v$ (creation of a
ball) at time $n$ corresponds to the following transition

$\eta_{w}(n+1)=\begin{cases}\eta_{v}(n)+1,&\text{if }w=v,\\\
\eta_{w}(n),&\text{otherwise.}\end{cases}$

We fix a feedback (reinforcement) function $f:{\mathbb{N}}\to(0,+\infty).$
Conditioned on $(\eta_{u}(n);\,u\in S)$ the above transition occurs with
probability

$\frac{f(\eta_{v}(n))}{\sum_{w\in S}f(\eta_{w}(n))}.$

We introduce the following events:

  * •

${\rm Mon}$ is the event that there exists a unique site $w$ and a time
$m\in{\mathbb{N}}$ such that $\eta_{w}(n+1)=\eta_{w}(n)+1$ and
$\eta_{v}(n+1)=\eta_{v}(n)$ for $v\neq w$ (monopoly) and for all $n\geq m$.

To simplify notation, given a generic function $g:{\mathbb{N}}\to(0,\infty)$
we write

$\Sigma(g):=\sum_{k=0}^{\infty}g(k).$ (2.2)

The following result that can be found in [13] is one of the cornerstones of
our proof. After a successful comparison with a Pólya urn scheme it allows us
to conclude the desired result.

######  Theorem 2.1 (Rubin’s construction).

For the Balls-in-Bins process with feedback function $f$ the following holds
irrespective of the initial conditions: If $\Sigma(f^{-1})<\infty$ then
${\mathbb{P}}({\rm Mon})=1$ (monopolistic regime).

##  3\. Non conservative zero range process

In this section we provide a precise definition of the NCZR, and prove Theorem
1.1. This should be seen as a warm up for the proof of the corresponding
result for the Ant RW.

We fix a finite graph $G=(V,E)$. For a vertex $v\in G$ we define the following
operations on elements $\eta=(\eta_{w};\,w\in G)\in{\mathbb{N}}^{V}$:

  * •

We define $\eta^{+v}=(\eta_{w}^{+v};w\in G)$ via

$\eta^{+v}_{w}\;=\;\left\\{\begin{array}[]{cl}\eta_{w}\,,&v\neq w\,,\\\
\eta_{v}+1\,,&v=w\,.\\\ \end{array}\right.$

  * •

If $\eta_{v}\geq 1$, we define $\eta^{-v}=(\eta_{w}^{-v};w\in G)$ via

$\eta^{-v}_{w}\;=\;\left\\{\begin{array}[]{cl}\eta_{w}\,,&v\neq w\,,\\\
\eta_{v}-1\,,&v=w\,.\\\ \end{array}\right.$

  * •

If $\eta_{v}\geq 1$ and $u\sim v,$ we define $\eta^{vu}=(\eta_{w}^{vu};w\in
G)$ via

$\eta^{vu}_{w}\;=\;\left\\{\begin{array}[]{cl}\eta_{w}\,,&w\notin\\{v,u\\}\,,\\\
\eta_{u}+1\,,&u=w\,,\\\ \eta_{v}-1\,,&v=w\,.\end{array}\right.$

We proceed to define a Markov chain $H=(H(n);\,n\in{\mathbb{N}})$ with state
space ${\mathbb{N}}^{V}$. We assume that $H(0)$ is non-zero, and we fix
parameters $p,q,r\in{\mathbb{R}}$. The transition probabilities are given by

$\begin{split}{\mathbb{P}}\big{[}H(n+1)=\eta^{+v}|H(n)=\eta\big{]}&=\frac{\eta_{v}^{p}}{\sum_{w\in
V}\big{[}\eta_{w}^{p}+\eta_{w}^{q}+\deg(w)\eta_{w}^{r}\big{]}}\,,\\\
{\mathbb{P}}\big{[}H(n+1)=\eta^{-v}|H(n)=\eta\big{]}&=\frac{\eta_{v}^{q}}{\sum_{w\in
V}\big{[}\eta_{w}^{p}+\eta_{w}^{q}+\deg(w)\eta_{w}^{r}\big{]}}\,,\\\
{\mathbb{P}}\big{[}H(n+1)=\eta^{vu}|H(n)=\eta\big{]}&=\frac{\eta_{v}^{r}}{\sum_{w\in
V}\big{[}\eta_{w}^{p}+\eta_{w}^{q}+\deg(w)\eta_{w}^{r}\big{]}}\,.\end{split}$

Hereafter we adopt the convention that $0^{p}=1$. This is only necessary to
guarantee that our process will not be stuck in the zero configuration. But we
still have $0^{q}=0$ and $0^{r}=0$.

The event ${\rm Mon}$ is defined as in Section 2.6 with
$(H(n);\,n\in{\mathbb{N}})$ instead of $(\eta(n);\,n\in{\mathbb{N}}).$ The
rigorous definition of ${\rm Creat}$ is the following: there exists
$m\in{\mathbb{N}}$ such that for each $n\geq m$ there exists a vertex $v(n)\in
G$ with $H(n+1)=H(n)^{+v(n)}.$

With the above definitions in mind we now prove Theorem 1.1.

#### Proof of Theorem 1.1.

The strategy of the proof is the following. We construct an auxiliary balls-
in-bins process $K^{\tau}$ associated to $H$ and to a finite stopping time
$\tau$. Depending on the parameters $p,q,r\in{\mathbb{R}}_{+}$ it is then
possible to compare $K^{\tau}$ and $H$ in such a way that it allows to deduce
the desired result from Theorem 2.1.

Let $\tau$ be a finite stopping time. The auxiliary process
$K^{\tau}=(K^{\tau}(n);\,n\geq 0)$ is defined through:

  1. (1)

For $n\in[0,\tau]$ we set $K^{\tau}(n)=H(n).$

  2. (2)

For $n>\tau$, $K^{\tau}$ evolves like a balls-in-bins process with feedback
function $k\in{\mathbb{N}}\mapsto k^{p}$, i.e., accordingly to the following
probability transitions: for any $v\in G,$

$\begin{split}{\mathbb{P}}\big{[}K^{\tau}(n+1)=\eta^{+v}|K^{\tau}(n)=\eta\big{]}&=\frac{\eta_{v}^{p}}{\sum_{w\in
V}\eta_{w}^{p}}\,.\end{split}$

Our next step is to relate the processes $H$ and $K^{(\tau)}$ via a Radon-
Nikodym derivative on the set of trajectories

${\mathcal{A}}^{+}=\\{(\eta(m);\,m\in{\mathbb{N}})\,:\,\forall\,n\in{\mathbb{N}},\,\eta(n)\in{\mathbb{N}}^{V},\,\exists\,v(n)\in
V;\,\eta(n+1)=\eta(n)^{+v(n)}\\}.$ (3.1)

In plain words, trajectories in ${\mathcal{A}}^{+}$ neither perform walker
steps nor annihilate particles. Note that, recalling the notation from Section
2.3,

${\rm Creat}=\\{\eta:\,\exists\,n\in{\mathbb{N}}\,\text{ s.t.
}\eta_{n}^{\infty}\in{\mathcal{A}}^{+}\\}\,.$ (3.2)

Let $\eta=(\eta(m);\,m\in{\mathbb{N}})\in{\mathcal{A}}^{+}$. For a finite
stopping time $\tau$ and $m\in{\mathbb{N}}$ with $m\geq\tau$ we write
$\eta_{\tau}^{m}:=(\eta(n);\,\tau\leq n\leq m),$ and with a slight abuse of
notation we also write that $\eta_{\tau}^{m}\in{\mathcal{A}}^{+}$. Similar
definitions hold for $H$ and $K^{\tau}$. For any
$\eta_{\tau}^{m}\in{\mathcal{A}}^{+}$ we define

$\frac{dH}{dK}(\eta_{\tau}^{m}):=\frac{{\mathbb{P}}(H_{\tau}^{m}=\eta_{\tau}^{m})}{{\mathbb{P}}(\big{(}K^{\tau}\big{)}_{\tau}^{m}=\eta_{\tau}^{m})}.$
(3.3)

The following Lemma is crucial because it will allow us to compare the
original model with a Pólya urn scheme.

######  Lemma 3.1.

In the above setting the following holds irrespective of the choice of $H(0):$

  * •

If $p>1+\max\\{q,r,0\\}$ then there exists
$\delta=\delta(|V|,\Delta(G),p,q,r)>0$ such that

$\inf\bigg{\\{}\frac{dH}{dK}(\eta_{0}^{m});\,m\in{\mathbb{N}},\,\eta_{0}^{m}\in{\mathcal{A}}^{+}\bigg{\\}}\geq\delta.$
(3.4)

  * •

If $p\leq 1+\max\\{q,r\\}$ then for any $\epsilon>0$ there exists
$m_{0}=m_{0}(\epsilon,p,q,r,\Delta(G))$ such that for all $m\geq m_{0}$

$\sup\bigg{\\{}\frac{dH}{dK}(\eta_{0}^{m});\,\eta_{0}^{m}\in{\mathcal{A}}^{+}\bigg{\\}}<\epsilon.$
(3.5)

We postpone the proof of Lemma 3.1 to Section 3.1. Assuming Lemma 3.1 we
finish the proof of Theorem 1.1.

First case: assume $p>1+\max\\{q,r,0\\}.$

We define the following stopping time

$\tau=\inf\\{n\geq 0\,:\,H_{0}^{n}\notin{\mathcal{A}}^{+}\\}.$ (3.6)

Note that on the event $\\{\tau=\infty\\}$ we actually have $H\in{\rm Creat}$.
With this in mind our goal is to show that for some shift $\tau^{\prime}$ of
$\tau$ the event $\\{\tau^{\prime}=\infty\\}$ holds with probability one with
respect to the law of $H.$

We define recursively:

  1. (1)

$\tau_{0}=0$,

  2. (2)

If $\tau_{k}=\infty$ then $\tau_{k+1}=\infty$,

otherwise, $\tau_{k+1}=\tau\circ{\mathcal{S}}_{\tau_{k}}$ (see Section 2).

We want to show that ${\mathbb{P}}_{H(0)}\big{(}\exists\,k\geq
1\,:\,\tau_{k}=\infty\big{)}=1.$ To that end we will show that $\sum_{k\geq
0}{\mathbb{P}}_{H(0)}(\tau_{k}<\infty)<\infty$ and the result then follows
from Borel-Cantelli’s lemma.

Fix $m\in{\mathbb{N}}$. For simplicity, in the calculations below we identify
$\big{(}K^{0}\big{)}_{0}^{m}$ with $K_{0}^{m}$ (here $K^{0}$ refers to the
process defined above with $\tau=0$). In the fourth line of (3.7) below we use
Lemma 3.1. Recall that the bound (3.4) is uniform in all configurations
$\eta_{0}^{m}\in{\mathcal{A}}^{+}.$ In the fifth line of (3.7) we use that
$K^{0}\in{\mathcal{A}}^{+}$ almost surely (cf. Theorem 2.1). Then we obtain

$\begin{split}{\mathbb{P}}_{H(0)}(\tau_{1}\geq
m)&\geq{\mathbb{P}}_{H(0)}(H_{0}^{m}\in{\mathcal{A}}^{+})\\\
&=\sum_{\eta_{0}^{m}\in{\mathcal{A}}^{+}}{\mathbb{P}}_{H(0)}(H_{0}^{m}=\eta_{0}^{m})\\\
&=\sum_{\eta_{0}^{m}\in{\mathcal{A}}^{+}}\frac{dH}{dK}(\eta_{0}^{m}){\mathbb{P}}_{H(0)}\big{(}K_{0}^{m}=\eta_{0}^{m}\big{)}\\\
&\geq\delta{\mathbb{P}}_{H(0)}\big{(}K_{0}^{m}\in{\mathcal{A}}^{+}\big{)}\\\
&=\delta.\end{split}$ (3.7)

In particular, sending $m\to\infty$, we obtain that
${\mathbb{P}}_{H(0)}(\tau_{1}<+\infty)<1-\delta.$ Note that all the estimates
above are uniform in the starting configuration, i.e.,

$\sup\\{{\mathbb{P}}_{\eta}(\tau_{1}<+\infty);\,\eta\in{\mathbb{N}}^{V}\\}\leq
1-\delta.$

As induction hypothesis on $k$ assume that

$\sup\\{{\mathbb{P}}_{\eta}(\tau_{k}<+\infty);\,\eta\in{\mathbb{N}}^{V}\\}\leq(1-\delta)^{k}.$
(3.8)

Using the strong Markov property we derive

$\begin{split}{\mathbb{P}}_{H(0)}(\tau_{k+1}<\infty)&={\mathbb{P}}_{H(0)}(\tau_{k+1}<\infty,\,\tau_{k}<\infty)\\\
&={\mathbb{E}}_{H(0)}\big{[}\mathds{1}_{\\{\tau_{k}<\infty\\}}{\mathbb{P}}_{H(\tau_{k})}(\tau_{1}<\infty)\big{]}\\\
&\leq{\mathbb{E}}_{H(0)}\big{[}\mathds{1}_{\\{\tau_{k}<\infty\\}}(1-\delta)\big{]}\leq(1-\delta)^{k+1}.\end{split}$

Hence, by the Borel Cantelli lemma we deduce that

${\mathbb{P}}_{H(0)}\big{(}\exists\,k\geq 1\,:\,\tau_{k}=\infty\big{)}=1\,.$

However, on the event $\\{\exists\,k\in{\mathbb{N}}\text{ s.t.
}\tau_{k}=\infty\\}$ we have $H\in{\rm Creat}$. This shows that
${\mathbb{P}}({\rm Creat})=1$. To continue, we define

$\begin{split}{\mathcal{B}}^{+}&=\left\\{\eta\in{\mathcal{A}}^{+}:\,\exists\,w\in
G\text{ s.t. }\forall
n\in{\mathbb{N}}:\,\eta_{v}(n+1)=\begin{cases}\eta_{v}(n)+1,&\text{if }v=w\\\
\eta_{v}(n),&\text{otherwise.}\end{cases}\right\\}\,.\end{split}$ (3.9)

In the same manner as in (3.2) it holds that

${\rm Mon}=\\{\eta:\,\exists\,n\in{\mathbb{N}}\text{ s.t.
}\eta_{n}^{\infty}\in{\mathcal{B}}^{+}\\}.$

Since $p>1$ we can change ${\mathcal{A}}^{+}$ by ${\mathcal{B}}^{+}$ in (3.7)
together with Theorem 2.1 to deduce that ${\mathbb{P}}({\rm Mon})=1$.

Second case: assume that $p\leq 1+\max\\{q,r\\},$ and let $\epsilon>0$. By
Lemma 3.1 there exists $m\in{\mathbb{N}}$ such that (3.5) holds. Therefore,
for any $m\in{\mathbb{N}}$ we have the following bound

$\begin{split}{\mathbb{P}}_{H(0)}(H_{0}^{m}\in{\mathcal{A}}^{+})&=\sum_{\eta_{0}^{m}\in{\mathcal{A}}^{+}}{\mathbb{P}}_{H(0)}(H_{0}^{m}=\eta_{0}^{m})\\\
&=\sum_{\eta_{0}^{m}\in{\mathcal{A}}^{+}}\frac{dH}{dK}(\eta_{0}^{m}){\mathbb{P}}_{H(0)}\big{(}K_{0}^{m}=\eta_{0}^{m}\big{)}\\\
&\leq\epsilon{\mathbb{P}}_{H(0)}\big{(}K_{0}^{m}\in{\mathcal{A}}^{+}\big{)}=\epsilon.\end{split}$
(3.10)

Therefore, sending $\epsilon\to 0$ we conclude that
${\mathbb{P}}_{H(0)}(H_{0}^{\infty}\in{\mathcal{A}}^{+})=0.$

Using appropriate stopping times as in the first part of the proof allows us
to conclude.

###  3.1. Estimating the Radon-Nikodym derivative

In this section we prove Lemma 3.1.

We start with a brief idea of the proof. The expression $\frac{dH}{dK}$ is a
product and we can turn it into a exponential of a sum, using for example the
inequality $1+x\leq e^{x}$. The sum obtained in this way can be controlled by
using the total number of particles. It then turns out that the new sum will
behave like $\sum_{n}1/n^{s}$ where $s=p-\max\\{q,r\\}$ and the convergence or
divergence of this sum will provide the result.

Let $(\eta(n);\,n\in{\mathbb{N}})\in{\mathcal{A}}^{+}$. From definition (3.3)
we obtain the expression

$\begin{split}\frac{dH}{dK}(\eta_{0}^{m})&=\prod_{k=0}^{m-1}\frac{\sum_{w\in
G}\eta_{w}(k)^{p}}{\sum_{w\in
G}[\eta_{w}(k)^{p}+\eta_{w}(k)^{q}+\deg(w)\sigma_{w}(k)^{r}]}\\\
&=\prod_{k=0}^{m-1}\frac{1}{1+\frac{\sum_{w}\eta_{w}(k)^{q}}{\sum_{w}\eta_{w}(k)^{p}}+\frac{\sum_{w}\deg(w)\eta_{w}(k)^{r}}{\sum_{w}\eta_{w}(k)^{p}}}.\end{split}$
(3.11)

Define $N_{\eta}(k):=\sum_{w\in G}\eta_{w}(k)$, which is the total number of
particles of the configuration $\eta(k)\in{\mathbb{N}}^{V}.$ Observe that
there exists a constant $C$ depending on $|V|$, $\Delta(G)$, $p$, $q$, and $r$
such that

$\begin{split}C^{-1}N_{\eta}(k)^{s}&\leq\sum_{w}\eta_{w}(k)^{s}\leq
C(N_{\eta}(k)^{s}\mathds{1}_{s\geq 0}+\mathds{1}_{s<0}),\,\text{ for
}s=p,\,q,\,\text{ and }\\\
C^{-1}N_{\eta}(k)^{r}&\leq\sum_{w}\deg(w)\eta_{w}(k)^{r}\leq
C(N_{\eta}(k)^{r}\mathds{1}_{r\geq 0}+\mathds{1}_{r<0})\,.\end{split}$ (3.12)

First case: assume that $p>1+\max\\{q,r,0\\}.$ From the inequality
$1/(1+x)\geq e^{-x}$, (3.11), and (3.12) we obtain that

$\begin{split}\frac{dH}{dK}(\eta_{0}^{m})&\geq\exp\bigg{(}-\sum_{k=0}^{m-1}\frac{\sum_{w}\eta_{w}(k)^{q}}{\sum_{w}\eta_{w}(k)^{p}}-\sum_{k=0}^{m}\frac{\sum_{w}\deg(w)\eta_{w}(k)^{r}}{\sum_{w}\eta_{w}(k)^{p}}\bigg{)}\,.\end{split}$
(3.13)

Applying (3.12) we see that

$\sum_{k=0}^{m-1}\frac{\sum_{w}\eta_{w}(k)^{q}}{\sum_{w}\eta_{w}(k)^{p}}\leq\sum_{k=0}^{m-1}C^{2}\frac{N_{\eta}(k)^{q}\mathds{1}_{q\geq
0}+\mathds{1}_{q<0}}{N_{\eta}(k)^{p}}\,$ (3.14)

and a similar estimate holds for the second term in the exponential in (3.13).
Observe that the total number of particles $N_{\eta}(k)$ increases by one unit
at each time because $\eta\in{\mathcal{A}}^{+}$. Thus, the condition on $p$ is
enough to conclude (3.4).

Second case: assume that $p\leq 1+\max\\{q,r\\}$. We will assume that
$\max\\{q,r\\}=q$ because the proof for the other case is similar. We first
treat the case that $\max\\{q,r\\}\leq p$. Using (3.12) in (3.11) we obtain
that

$\frac{dH}{dK}(\eta_{0}^{m})\leq\prod_{k=0}^{m-1}\frac{1}{1+C^{-2}N_{\eta}(k)^{q-p}}.$

Observe that for $x\in(0,2]$ it holds that $1/(1+x)\leq e^{-x/2}.$ Since
$q-p\leq 0$ we have that $C^{-2}N_{\eta}(k)^{q-p}\leq 2$ (we can enlarge $C$
if needed). Therefore,

$\frac{dH}{dK}(\eta_{0}^{m})\leq\exp\bigg{(}-\frac{1}{2}\sum_{k=0}^{m-1}C^{-2}N_{\eta}(k)^{q-p}\bigg{)}.$

The sum on the RHS diverges since $p-q\leq 1,$ and as consequence the bound
goes to $0$ as $m\to\infty.$ If on the other hand $p<q=\max\\{q,r\\}$, then we
estimate

$\begin{split}\prod_{k=0}^{m-1}\frac{1}{1+C^{-2}N_{\eta}(k)^{q-p}}&=\exp\left\\{-\sum_{k=0}^{m-1}\log(1+C^{-2}N_{\eta}(k)^{q-p})\right\\}\\\
&\leq\exp\left\\{-\sum_{k=0}^{m-1}\log(C^{-2}N_{\eta}(k)^{q-p})\right\\}\\\
&=\exp\left\\{-\sum_{k=0}^{m-1}\Big{(}\log(C^{-2})+(q-p)\log(N_{\eta}(k))\Big{)}\right\\}\,.\end{split}$

Again using that $k\mapsto N_{\eta}(k)$ is strictly monotone increasing, we
see that the right hand side above converges to zero when $m$ tends to
infinity. We therefore can conclude.

##  4\. The Ant random walk

In this section we give a precise definition of the Ant RW. We end the section
with the full statement of Theorem 1.2.

We fix a graph $G=(V,E)$ and we assume that the graph is not a tree, i.e., it
has at least one circuit. We further fix $N\in{\mathbb{N}}$, the total number
of walkers.

#### Definition of the model.

The Ant RW is a process in discrete time

$(\vec{X}(n);\,n\in{\mathbb{N}})=(X_{i}(n);\,i\in[N]\,,n\in{\mathbb{N}})$

which takes values in $V^{N}.$ For $n\geq 0,$ let
${\mathcal{F}}_{n}=\sigma(\vec{X}(m);\,0\leq m\leq n)$ be the natural
filtration associated to the process $\vec{X}$.

For any $(u,v)\in\vec{E}$ and $n\geq 0$, let

$\begin{split}c^{(i)}_{n}(u,v):=&\sum_{m=1}^{n}\big{(}\mathds{1}_{[(X_{i}(m-1),X_{i}(m))=(u,v)]}-\mathds{1}_{[(X_{i}(m-1),X_{i}(m))=(v,u)]}\big{)}.\end{split}$

In plain words, $c^{(i)}_{n}(u,v)$ is the number of times the walker $X_{i}$
jumped from $u$ to $v$ minus the number of times $X_{i}$ jumped from $v$ to
$u$ in the time interval $\llbracket 0,n\rrbracket$. The (collective) crossing
number of the edge $(u,v)$ at time $n$ is defined by

$c_{n}(u,v)=\sum_{i=1}^{N}c^{(i)}_{n}(u,v).$

Observe that at time $0$, $c_{0}(u,v)=0$ for all $(u,v)\in\vec{E}.$

We further fix two reinforcement functions
$W_{1},W_{2}:{\mathbb{N}}\to(0,+\infty)$, and we define
$W:{\mathbb{Z}}\to(0,+\infty)$ via

$W(k)=\begin{cases}W_{1}(k),&\text{if }k>0,\\\ W_{2}(-k),&\text{if }k\leq
0,\end{cases}$

and we emphasize that we assume $W_{i}(k)\neq 0$ for any $k\in{\mathbb{N}}$,
$i=1,2$.

The dynamics of the Ant RW is described as follows. We choose an arbitrary
(but fixed) distribution for the starting point $\vec{X}(0)\in V^{N}$. Assume
that the process is defined in the time interval $\llbracket 0,n-1\rrbracket$.
At time $n$ we select an index $i\in[N]$ uniformly at random, independent of
the past. Independent of the selection of $i$, conditioned on
${\mathcal{F}}_{n}$, one has that $X_{i}(n)=u$ with probability

$\displaystyle\frac{W(c_{n-1}(X_{i}(n-1),u))}{\displaystyle\sum_{w:w\sim
X_{i}(n-1)}W(c_{n-1}(X_{i}(n-1),u))}.$ (4.1)

Observe that the joint process $(\vec{X}(n),c_{n}(\cdot,\cdot);\,n\geq 0)$ is
a discrete time Markov chain. We denote by ${\mathbb{P}}$ the law of the above
process when started from the configuration $(\vec{X}(0),c_{0}(\cdot,\cdot))$.
In the future it will be convenient to condition the process on a given
configuration $\xi=(\vec{X}(m),c_{m}(\cdot,\cdot))$, for a possible random
time $m,$ and start afresh from there. In that case we write
${\mathbb{P}}_{\xi}$ for the law of the new process.

#### Long time behaviour

We introduce more objects in order to fully state our main result.

Let $V^{\infty}$ be the set of vertices $v\in V$ that are visited infinitely
many times by $\vec{X}$. Let $G^{\infty}=(V^{\infty},E^{\infty})$ be the
induced graph by $V^{\infty}$, i.e., $\\{u,v\\}\in E^{\infty}$ if
$\\{u,v\\}\in E$ and $u,v\in V^{\infty}$.

Fix a circuit $C$, and a representative $(u_{0},u_{1},\cdots,u_{\ell-1})$ of
$C$ (recall from Section 2 that $C$ actually denotes an equivalence class).

We introduce two events:

  * •

${\rm Monot}$ is the event that there exists $m\in{\mathbb{N}}$ such that
$n\geq m\mapsto c_{n}(u,v)$ is a monotone function, for all $(u,v)\in\vec{E}$.

  * •

${\rm LocTrapp}$ is the event that there exists $m\in{\mathbb{N}}$, such that

a) the vector of crossing numbers $(c_{n}(u,v);\,n\geq m,\,(u,v)\in\vec{E})$
is monotone,

b) there exists $K\leq N$ and disjoint circuits $(C_{i};\,i\in[K])$ such that

$V^{\infty}=\bigcup_{i=1}^{K}V(C_{i})\,\,\,,\,\,E^{\infty}=\bigcup_{i=1}^{K}E(C_{i})\,.$

As an immediate consequence of the definition of LocTrapp, the walkers are
trapped in the circuits $C_{i}$ in the sense that they are not allowed to
visit any other edges for large times. Furthermore, since the vector of
crossing numbers is monotone, a group of walkers trapped in the circuit
$C_{i}$ are forced to spin in the same direction.

Before proceeding we make some remarks about the above events. In particular,
we compare them with their counterpart in the context of the balls-in-bins
process (cf. Section 2.6).

The event LocTrapp resembles the event Mon. Here the analogy is between
creation of particles and crossing circuits. We observe also that LocTrapp is
a generalization of the trapping event one finds in [6].

Now we introduce the assumptions we will make about the reinforcement
functions. Define ${\mathcal{P}}_{\leq}$ as the class of functions
$f:{\mathbb{N}}\to(0,\infty)$ with the following property: for every
$i\in{\mathbb{N}}$ there exists a constant $C_{i}=C_{i}(f)\in{\mathbb{R}}_{+}$
such that

$\begin{split}\forall\,\,(a_{1},\cdots,a_{i})\in{\mathbb{N}}^{i}\,\,\,,\,\,\sum_{j=1}^{i}f(a_{j})\leq
C_{i}f\bigg{(}\sum_{j=1}^{i}a_{j}\bigg{)}.\end{split}$ (4.2)

Similarly, we define ${\mathcal{P}}_{\geq}$ as the class of functions that
satisfy (4.2) with a lower bound instead of upper bound. For the next result
we further assume that $W_{2}$ satisfies:

$\exists\,C=C(W_{2})\,:\,\forall\,M\in\llbracket-N,+N\rrbracket,\,W_{2}(n+M)\leq
CW_{2}(n),\,\forall\,n\in{\mathbb{N}}.$ (4.3)

For $g:{\mathbb{N}}\to(0,+\infty)$ we write $\Sigma(g)=\sum_{n\geq 0}g(n)$.

######  Theorem 4.1.

Assume that $W_{1}\in{\mathcal{P}}_{\leq}$, $W_{2}\in{\mathcal{P}}_{\geq}$,
$W_{2}$ satisfies (4.3), and that $\Sigma(W_{2}/W_{1})=\infty$, then

${\mathbb{P}}({\rm Monot})=0\,.$

We prove Theorem 4.1 in Section 5. We show in Proposition 4.4 examples of
functions in the classes ${\mathcal{P}}_{\geq}$ and ${\mathcal{P}}_{\leq}$ and
of those satisfying (4.3).

Next we will state our main theorem for the regime
$\Sigma(W_{2}/W_{1})<\infty$. In this case our result holds under a more
general condition on the pair $(W_{1},W_{2})$. If in particular,
$W_{1}\in{\mathcal{P}}_{\geq}$ and $W_{2}\in{\mathcal{P}}_{\leq}$, then this
condition will be satisfied.

We proceed to state the general condition. Given a vector
$\phi\in{\mathbb{Z}}^{d}$ we define the two quantities

$\Upsilon^{+}(\phi)=\sum_{i:\phi(i)>0}W_{1}(\phi(i)),\quad\text{and}\quad\Upsilon^{-}(\phi)=\sum_{i:\phi(i)\leq
0}W_{2}(-\phi(i)).$ (4.4)

These quantities are related to our model due the following observation.
Assume that at a given time $n$, the walker $X_{k}$ is on a vertex $v$ of
degree $d$ and that $(c_{n}(v,w))_{w\sim v}=(\phi_{n}(i))_{i\in[d]}$. Then,
the probability of $X_{k}$ to walk over an edge with a positive crossing
number in the next step is precisely given by

$\frac{1}{1+\frac{\Upsilon^{-}(\phi_{n})}{\Upsilon^{+}(\phi_{n})}}.$ (4.5)

It is therefore natural to impose a control on the ratio
$\frac{\Upsilon^{-}(\phi_{n})}{\Upsilon^{+}(\phi_{n})}$.

As it turns out we do not need to control all possible vector functions of the
form $\\{(\phi_{n})_{n\geq 1}:\,\phi_{n}\in{\mathbb{Z}}^{d}\\}$ but only those
that arise from a vector of crossing numbers.

Recall the definition of $\Delta=\Delta(G)$ in (2.1).

######  Definition 4.2.

We denote by $\Phi$ the set of all functions $(\phi_{n})_{n\geq 0}$ satisfying

  * (1)

There is a $d\in[1,\Delta]$ such that for all $n\geq 0$ we have that
$\phi_{n}\in{\mathbb{Z}}^{d}$.

  * (2)

$\sum_{j=1}^{d}\phi_{n}(j)\in\llbracket-N,+N\rrbracket\qquad(\mathrm{flow\,property})\,.$

  * (3)

For any time $n\geq 0$ there are $j_{1},j_{2}\in[d]$ such that
$\phi_{n}(j_{1})>0$, and $\phi_{n+1}(j_{1})=\phi_{n}(j_{1})+1$ as well as
$\phi_{n}(j_{2})\leq 0$ and $\phi_{n+1}(j_{2})=\phi_{n}(j_{2})-1$. Moreover,
for all $j\notin\\{j_{1},j_{2}\\}$ one has that $\phi_{n+1}(j)=\phi_{n}(j)$.

Here, the second item reflects Equation (5.16). The last item reflects the
fact that exiting a vertex $v$ through the edge $(v,w)$ increases $c_{n}(v,w)$
by one, whereas entering the vertex $v$ through the edge $(w,v)$ diminishes
$c_{n}(v,w)$ by one, and the crossing numbers associated to all other edges
going out of $v$ remain constant.

Our general condition on the pair $(W_{1},W_{2})$ is that

$\sup_{\phi\in\Phi}\sum_{n=0}^{+\infty}\frac{\Upsilon^{-}(\phi_{n})}{\Upsilon^{+}(\phi_{n})}<\infty.$
(4.6)

At first sight it seems difficult to verify that (4.6) holds in practice.
However, in Proposition 4.4, we show that in many cases of interest (4.6)
actually is satisfied.

######  Theorem 4.3.

Assume that (4.6) holds. Without further assumptions on $W_{1}$ and $W_{2}$ we
have that ${\mathbb{P}}({\rm Monot})=1$. As a consequence of (4.6) we have
that $\Sigma(W_{1}^{-1})<\infty$ and ${\mathbb{P}}({\rm LocTrapp})=1$.

The next result gives examples of functions $W_{1}$ and $W_{2}$ that satisfy
Assumptions (4.2), (4.3) and (4.6).

######  Proposition 4.4.

The following holds:

  * (a)

Assume that $\Sigma(W_{1}^{-1})<\infty$, and that $W_{2}$ is non-increasing,
then $(W_{1},W_{2})$ satisfies (4.6).

  * (b)

Let $p,q\in{\mathbb{R}}_{+}.$ Define
$W_{1},W_{2}:{\mathbb{N}}\to{\mathbb{R}}_{+}$ via

$W_{i}(k)=\begin{cases}k^{p}+1&\text{if }i=1,\\\ k^{q}+1&\text{if
}i=2.\end{cases}\,$

Then $W_{1}$ and $W_{2}$ belong to
${\mathcal{P}}_{\leq}\cap{\mathcal{P}}_{\geq}$ and satisfy (4.3). If $p-q>1$,
then $(W_{1},W_{2})$ satisfies (4.6). Moreover, the same conclusions hold if
$W_{1}$ is a polynomial of degree $p$ and $W_{2}$ is a polynomial of degree
$q$.

  * (c)

For fixed $p,q\in{\mathbb{R}}_{+}$ define $\log^{+}k=log\,k\vee 1$, and let

$W_{1}(k)=k(\log^{+}k)^{p}+1,\quad\text{and}\quad W_{2}(k)=(\log^{+}k)^{q}\,.$

If $p-q>1$, then $(W_{1},W_{2})$ satisfies (4.6).

  * (d)

If $W_{1}\in{\mathcal{P}}_{\geq}$, $W_{2}\in{\mathcal{P}}_{\leq}$, $W_{2}$
satisfies (4.3), and $\Sigma(W_{2}/W_{1})<\infty$, then (4.6) holds.

  * (e)

If $W_{1}(k)=e^{\beta k}$ and $W_{2}(k)\leq e^{\alpha k}$ with
$\alpha,\beta\in(0,\infty)$ and $\beta>\Delta(G)\alpha$. In this case the pair
$(W_{1},W_{2})$ satisfies (4.6).

######  Remark 4.5.

We expect that Theorem 4.3 holds for the functions in item (e) of Proposition
4.4 with $\beta$ and $\alpha$ only satisfying $\beta>\alpha$.

We present the proof of Proposition 4.4 in Appendix A.

###  4.1. A remark about the result for an infinite graph

Let $G$ be an infinite graph. The goal of this short section is to explain
which assumptions one additionally needs to impose on $G$ in order to extend
our main results, by combining the results of the current articles with the
techniques of [6].

Firstly, one needs to impose that $G$ has a bounded degree.

Secondly, one needs to assume that $G$ is sufficiently connected and that it
has sufficiently many circuits. More precisely, one needs to impose that there
exists a sequence $(B_{n})_{n\in{\mathbb{N}}}$ of subgraphs of $G$ such that

  1. (1)

$B_{n}\subset B_{n+1},$

  2. (2)

$G=\cup_{n\in{\mathbb{N}}}B_{n}$,

  3. (3)

$B_{n+1}\setminus B_{n}$ is connected and it has at least one circuit.

Call ${\mathcal{G}}$ the class of graphs satisfying the above assumptions. It
is simple to check that ${\mathbb{Z}}^{d}\in{\mathcal{G}}$ with $d\geq 2$ and
the usual graph structure.

Then the following is true:

Assume that $G\in{\mathcal{G}}$, (4.6) holds and $\Sigma(W_{1}^{-1})<+\infty.$
Then ${\mathbb{P}}({\rm LocTrapp})=1.$

##  5\. Proofs for the Ant RW

The strategy of the proof is identical to the proof of Theorem 1.1 (cf.
Section 3). We construct an auxiliary multi particle random walk
$\vec{Y}^{\tau}$ associated to $\vec{X}$ and to a finite stopping time $\tau$.
Depending on the choices of the reinforcement functions $W_{1}$ and $W_{2}$ it
is possible to compare $\vec{Y}^{\tau}$ and $\vec{X}$ in such a way that both
processes have the same support. An analogue of Theorem 2.1 will provide a
description of the trajectories of $\vec{Y}^{\tau}$ and from this we deduce
the desired result.

Our first step in the construction of $\vec{Y}^{\tau}$ is to define a suitable
oriented graph $D_{\tau}=(V_{\tau},\vec{E}_{\tau})$ such that
$(v,w)\in\vec{E}_{\tau}$ if and only if $c_{\tau}(v,w)>0$. Eventually
$\vec{Y}^{\tau}$ will take values in $D_{\tau}$.

For each $n\in{\mathbb{N}}$ we define the set of end points of $\vec{X}$ at
time $n$ as

${\rm End}_{n}=\\{X_{j}(n)\,:\,j\in[N]\\}\,.$ (5.1)

Motivated by the flow property following Equation (5.16), which we will
introduce in the forthcoming Section 5.1, we define the following set of
vertices for each time $n\in{\mathbb{N}}:$

$S_{n}=\\{v\in V\,:\,\exists\,w\in V\,\text{ s.t. }|c_{n}(v,w)|\geq N+1\\}\,.$
(5.2)

Let $\tau$ be the first time such that ${\rm End}_{n}\subset S_{n}.$ Further,
let ${\mathcal{T}}_{f}$ be the collection of stopping times that are finite
almost surely with respect to the law of $\vec{X}$. For each
$\rho\in{\mathcal{T}}_{f}$ we write
$\tau_{\rho}=\tau\circ{\mathcal{S}}_{\rho},$ where we recall that
${\mathcal{S}}$ denotes the shift operator.

Provided that $\tau$ is finite we define $D_{\tau}=(V_{\tau},\vec{E}_{\tau})$
as the directed graph given by:

$\begin{split}V_{\tau}=&{\rm End}_{\tau}\cup\\{v\in V:\,v\notin{\rm
End}_{\tau},\text{ and }\exists\,w\sim_{G}v\,;\,c_{\tau}(v,w)\neq 0\\}\,,\\\
\vec{E}_{\tau}=&\\{(v,w)\in V_{\tau}^{2}:\,c_{\tau}(v,w)>0\\}\,.\end{split}$
(5.3)

If $(v,w)\in\vec{E}_{\tau}$, then we also write $v\sim_{D_{\tau}}w$. Observe
that if $\tau$ is finite, then by definition $X_{j}(\tau)\in S_{\tau}$ for all
$j\in[N].$

######  Lemma 5.1.

Assume that $G$ has at least one circuit. Let $\rho\in{\mathcal{T}}_{f}.$ Then
$\tau_{\rho}$ is finite with probability one with respect to the law of
$\vec{X}.$ Furthermore, $\deg_{D_{\tau_{\rho}}}^{\rm out}(v)\geq
1\,\forall\,v\in V_{\tau}$. In particular, each connected component of
$D_{\tau_{\rho}}$ has at least one circuit.

We prove Lemma 5.1 in Section 5.1. We proceed to define $\vec{Y}^{\tau}$
assuming the validity of the above result. The same construction can also be
done with $\tau_{\rho}$ in place of $\tau$. Here we write $c_{\tau}$ for the
vector of crossing numbers associated to $\vec{Y}^{\tau}$. In particular,
$c_{\tau,n}(v,u)$ is the crossing number of the edge $(v,u)$ at time $n$
associated to the process $\vec{Y}^{\tau}$.

The auxiliary process $\vec{Y}^{\tau}=(\vec{Y}^{\tau}(n);\,n\geq 0)$ is
defined via:

  1. (1)

For $n\in[0,\tau]$ we set $\vec{Y}^{\tau}(n)=\vec{X}(n)$ and
$c_{\tau,n}(\cdot,\cdot)=c_{n}(\cdot,\cdot).$

  2. (2)

For $n\geq\tau,$ $\vec{Y}^{\tau}$ evolves like a multi particle reinforced
random walk on a directed graph with reinforcement function $W_{1}$:

a) We select an index $j\in[N]$ uniformly at random.

b) Conditioned on $Y^{\tau}_{j}(n)=v\in D_{\tau}$ and ${\mathcal{F}}_{n}$, we
set $Y^{\tau}_{j}(n+1)=w\in D_{\tau}$ with probability

$\frac{W_{1}(c_{\tau,n}(v,w))}{\displaystyle\sum_{u:v\sim_{D_{\tau}}u}W_{1}(c_{\tau,n}(v,u))}\mathds{1}\\{v\sim_{D_{\tau}}w\\}.$

c) If $(Y^{\tau}_{j}(n),Y^{\tau}_{j}(n+1))=(v,w)$ we update the crossing
number as follows:

$c_{\tau,n+1}(\bar{v},\bar{w})=\begin{cases}c_{\tau,n}(\bar{v},\bar{w})+1,&\,\text{if
}(\bar{v},\bar{w})=(v,w),\\\
c_{\tau,n}(\bar{v},\bar{w}),&\,\text{otherwise}.\end{cases}$

######  Remark 5.2.

Since $\deg_{D_{\tau}}^{\rm out}(v)\geq 1$ for all $v\in D_{\tau}$ by Lemma
5.1 we have that $\vec{Y}^{\tau}$ is defined for all times.

As in Section 3 we relate the processes $\vec{X}$ and $\vec{Y}^{\tau}$ via a
Radon-Nikodym derivative on a special set of trajectories. Recall the lattice
version $D^{N}_{\tau}$ defined in Section 2 and that a path
$\pi:\llbracket\tau,+\infty)\to V^{N}_{\tau}$ represents a possible trajectory
of $\vec{Y}^{\tau}.$ The special set of trajectories is given by

${\mathcal{A}}^{\uparrow}_{\tau}=\\{\pi_{\tau}^{\infty}:=\pi:\llbracket\tau,+\infty)\to
V^{N}_{\tau};\,\pi_{\tau}^{\infty}\text{ is a trajectory }\\}\,.$ (5.4)

Observe that if $\pi_{\tau}^{\infty}\in{\mathcal{A}}_{\tau}^{\uparrow}$, on
the event $\\{(\vec{Y}^{\tau})_{\tau}^{\infty}=\pi_{\tau}^{\infty}\\}$ the
crossing numbers $n\geq\tau\mapsto|c_{\tau,n}(\cdot,\cdot)|$ are non-
decreasing.

Now we are ready to define the Radon-Nikodym derivative. To that end recall
the notation introduced in Section 2.3. To simplify notation we identify
$(\vec{Y}^{\tau})_{\tau}^{m}$ with $\vec{Y}_{\tau}^{m}$. For any
$\pi_{\tau}\in{\mathcal{A}}_{\tau}^{\uparrow}$ and any $m\geq\tau$ we define

$\frac{d\vec{X}}{d\vec{Y}}(\pi_{\tau}^{m})=\frac{{\mathbb{P}}(\vec{X}_{\tau}^{m}=\pi_{\tau}^{m})}{{\mathbb{P}}(\vec{Y}_{\tau}^{m}=\pi_{\tau}^{m})}\,.$
(5.5)

The following Lemma is the central piece of our results. Its proof can be
found in Section 5.2.

######  Lemma 5.3.

Assume that the graph $G$ has at least one circuit. The following holds almost
surely:

  * •

Assume that $W_{1}\in{\mathcal{P}}_{\leq}$, $W_{2}\in{\mathcal{P}}_{\geq}$,
$W_{2}$ satisfies (4.3), and that $\Sigma(W_{2}/W_{1})=\infty$. Then for any
$\epsilon>0$ there exists $m_{0}=m_{0}(\epsilon,W_{1},W_{2},\Delta(G))$ such
that for all $m\geq m_{0}$

$\sup\bigg{\\{}\frac{d\vec{X}}{d\vec{Y}}(\pi_{\tau}^{m});\,\pi_{\tau}^{m}\in{\mathcal{A}}_{\tau}^{\uparrow}\bigg{\\}}<\epsilon\,.$
(5.6)

  * •

Assume that (4.6) holds for the pair $(W_{1},W_{2})$. Then

$\exists\,\delta=\delta(|V|,\Delta(G),W_{1},W_{2})\,:\,\inf\bigg{\\{}\frac{d\vec{X}}{d\vec{Y}}(\pi_{\tau}^{m});\,m\in{\mathbb{N}},\,\pi_{\tau}^{m}\in{\mathcal{A}}_{\tau}^{\uparrow}\bigg{\\}}\geq\delta\,.$
(5.7)

######  Remark 5.4.

Lemma 5.3 remains unchanged if we substitute $\tau$ by
$\tau\circ{\mathcal{S}}_{\rho}$ for any finite stopping time $\rho$.

Next, we describe the support of the process $\vec{Y}^{\tau}.$

To that end, we define the directed graph
${\mathcal{D}}_{\tau}^{\infty}=({\mathcal{V}}_{\tau}^{\infty},\vec{{\mathcal{E}}}_{\tau}^{\infty})$
via

$\begin{split}{\mathcal{V}}_{\tau}^{\infty}&=\\{v\in V_{\tau}\,:\,v\text{ is
visited infinitely often by }\vec{Y}^{\tau}\\}\,,\\\
\vec{{\mathcal{E}}}_{\tau}^{\infty}&=\\{(v,w)\in({\mathcal{V}}_{\tau}^{\infty})^{2}\,:\,(v,w)\in\vec{E}_{\tau}\\}\,.\end{split}$
(5.8)

By Remark 5.2 we have that ${\mathcal{D}}_{\tau}^{\infty}\neq\emptyset.$

We define the following event:

  * •

$\\{\vec{Y}^{\tau}\in{\mathcal{C}}^{\uparrow}_{\tau}\\}$ is the event that
$\vec{Y}^{\tau}\in{\mathcal{A}}_{\tau}^{\uparrow}$ and such that there exist
$m\geq\tau$, and $K\leq N$, and disjoint circuits $(C_{i};\,i\in[K])$ in
$D_{\tau}$ satisfying

$\bigcup_{i=1}^{K}C_{i}={\mathcal{D}}_{\tau}^{\infty}\,.$

Here, the last identity has to be understood in the sense that the edge and
vertex sets of both graphs coincide.

As a consequence of the definitions we obtain that

$\begin{split}{\rm Monot}&=\\{\pi\,:\,\exists\,\rho\in{\mathcal{T}}_{f}\text{
s.t.
}\pi_{\tau_{\rho}}^{\infty}\in{\mathcal{A}}^{\uparrow}_{\tau_{\rho}}\\}\,,\\\
{\rm LocTrapp}&=\\{\pi\,:\,\exists\,\rho\in{\mathcal{T}}_{f}\text{ s.t.
}\pi_{\tau_{\rho}}^{\infty}\in{\mathcal{C}}^{\uparrow}_{\tau_{\rho}}\\}\,.\end{split}$

######  Lemma 5.5.

Let $\rho\in{\mathcal{T}}_{f}$ and
$\tau_{\rho}=\tau\circ{\mathcal{S}}_{\rho}.$ If $G$ has at least one circuit
then for any choice of $W_{1}$, we have that
${\mathbb{P}}(\vec{Y}^{\tau_{\rho}}\in{\mathcal{A}}^{\uparrow}_{\tau_{\rho}})=1.$
Furthermore, if $\Sigma(W_{1}^{-1})<\infty$, then
${\mathbb{P}}(\vec{Y}^{\tau_{\rho}}\in{\mathcal{C}}^{\uparrow}_{\tau_{\rho}})=1.$

If the graph $G$ has only one circuit, then

$\\{\vec{Y}^{\tau_{\rho}}\in{\mathcal{A}}^{\uparrow}_{\tau_{\rho}}\\}=\\{\vec{Y}^{\tau_{\rho}}\in{\mathcal{C}}^{\uparrow}_{\tau_{\rho}}\\}\,,$
(5.9)

and in particular, the above events occur with probability one.

The above result resembles the phenomena observed in Theorem 2.1. The proof of
Lemma 5.5 is also based on Theorem 2.1 and the reader will find it in Section
5.3.

Assuming Lemmas 5.1, 5.3 and 5.5 we show how to prove Theorem 4.1 and Theorem
4.3.

###### Proof of Theorem 4.1.

We are assuming that $W_{1}\in{\mathcal{P}}_{\leq}$,
$W_{2}\in{\mathcal{P}}_{\geq}$, $W_{2}$ satisfies (4.3) and that
$\Sigma(W_{2}/W_{1})=\infty$. Then the relation

${\mathbb{P}}(\exists\,\rho\in{\mathcal{T}}_{f}\,:\,\vec{X}_{\tau_{\rho}}^{\infty}\in{\mathcal{A}}^{\uparrow}_{\tau_{\rho}})=0\,,$
(5.10)

can be deduced as in (3.10) from the upper bound in (5.6). ∎

###### Proof of Theorem 4.3.

We assume that (4.6) holds. According to Lemma 5.3 the lower bound in (5.7)
holds. We will proceed to show that

${\mathbb{P}}(\exists\,\rho\in{\mathcal{T}}_{f}\,:\,\vec{X}_{\tau_{\rho}}^{\infty}\in{\mathcal{A}}^{\uparrow}_{\tau_{\rho}})=1\,,$
(5.11)

and hence proving that the vector of crossing numbers induced by $\vec{X}$ is
eventually monotone.

Motivated by (5.11) we define recursively:

  1. (1)

$\sigma_{0}=0$, $\bar{\tau}_{0}=0$

  2. (2)

If $\sigma_{k}=\infty$ then $\sigma_{k+1}=\infty$ and
$\bar{\tau}_{k+1}=+\infty$,

otherwise, $\bar{\tau}_{k+1}=\tau\circ{\mathcal{S}}_{\sigma_{k}}$

$\sigma_{k+1}=\inf\\{n\geq\bar{\tau}_{k+1}\,:\,\vec{X}_{\bar{\tau}_{k+1}}^{n}\notin{\mathcal{A}}^{\uparrow}_{\bar{\tau}_{k+1}}\\}\,.$
(5.12)

As in Section 3 it is enough to show that $\sum_{k\geq
0}{\mathbb{P}}_{\xi_{0}}(\sigma_{k}<\infty)<\infty$. Since the arguments
employed to prove that mimic the ones already used in Section 3 we just sketch
the main steps.

Recall that, assuming that the graph $G$ has at least one circuit, the walker
$\vec{Y}^{\tau}$ is well defined for all times.

Fix $m\in{\mathbb{N}}$. In (5.13) below we use (5.7) in the fourth line,
whereas in the last line we use that
$\vec{Y}^{\tau}\in{\mathcal{A}}^{\uparrow}_{\tau}$ almost surely (cf. Lemma
5.5). We obtain

$\begin{split}{\mathbb{P}}_{\xi_{0}}(\sigma_{1}\geq
m)&\geq{\mathbb{P}}_{\xi_{0}}(\vec{X}_{\tau}^{m}\in{\mathcal{A}}^{\uparrow}_{\tau})\\\
&=\sum_{\pi_{\tau}^{m}\in{\mathcal{A}}^{\uparrow}_{\tau}}{\mathbb{P}}_{\xi_{0}}(\vec{X}_{\tau}^{m}=\pi_{\tau}^{m})\\\
&=\sum_{\pi_{\tau}^{m}\in{\mathcal{A}}^{\uparrow}_{\tau}}\frac{d\vec{X}}{d\vec{Y}^{\tau}}(\pi_{\tau}^{m}){\mathbb{P}}_{\xi_{0}}(\vec{Y}_{\tau}^{m}=\pi_{\tau}^{m})\\\
&\geq\delta{\mathbb{P}}_{\xi_{0}}(\vec{Y}_{\tau}^{m}\in{\mathcal{A}}^{\uparrow}_{\tau})\\\
&=\delta.\end{split}$ (5.13)

We can now conclude as in Section 3.

If the graph $G$ has exactly one circuit, we leave to the reader to check that

$\\{\vec{X}_{\tau_{\rho}}^{\infty}\in{\mathcal{A}}^{\uparrow}_{\tau_{\rho}}\\}=\\{\vec{X}_{\tau_{\rho}}^{\infty}\in{\mathcal{C}}^{\uparrow}_{\tau_{\rho}}\\}\,.$
(5.14)

We assume now that $G$ has at least two circuits.

From (4.6) we have that $\Sigma(W_{1}^{-1})<+\infty.$ Recall that under our
assumptions the lower bound in (5.7) holds. Our goal is to prove that

${\mathbb{P}}(\exists\,\rho\in{\mathcal{T}}_{f}\,:\,\vec{X}_{\tau_{\rho}}^{\infty}\in{\mathcal{C}}^{\uparrow}_{\tau_{\rho}})=1\,.$
(5.15)

In order to prove (5.15) we will use Lemma 5.5 which asserts that

${\mathbb{P}}(\vec{Y}^{\tau_{\rho}}\in{\mathcal{C}}^{\uparrow}_{\tau_{\rho}})=1\,.$

Recall that
${\mathcal{C}}^{\uparrow}_{\tau}\subset{\mathcal{A}}^{\uparrow}_{\tau}$. Then
repeating the argument in (5.13) with ${\mathcal{C}}^{\uparrow}_{\tau}$
instead of ${\mathcal{A}}^{\uparrow}_{\tau}$ we obtain the corresponding lower
bound and as consequence the result.

∎

###  5.1. The stopping time $\tau$ is finite

In this section we prove Lemma 5.1.

Our first goal is to prove that given $\rho\in{\mathcal{T}}_{f}$ the stopping
time $\tau_{\rho}=\inf\\{n\geq\rho\,:\,{\rm End}_{n}\subset S_{n}\\}\,$ is
finite almost surely.

The proof is inspired by calculations that can already be found in [6, Section
3].

First case: assume that $S_{\rho}=\emptyset$, i.e., for all pairs $(u,v)\in
V^{2}$ we have that $|c_{\rho}(u,v)|\leq N.$ Using that $G$ has at least one
circuit, we fix a circuit $C^{*}$ in $G$ and consider the following event:

  1. (1)

For each $i\in[N]$, the walker $X_{i}$ follows a shortest path that connects
$X_{i}(\rho)$ to $C^{*}.$ The crossing numbers decrease at most by $1$ for
each walker.

  2. (2)

Then the walker $X_{i}$ gives $N+3$ turns around $C^{*}.$ This increases the
crossing numbers of $C^{*}$ by $N(N+3)$.

Let $\rho^{\prime}-\rho$ be the time needed for that event. Recall that at
time $\rho$ the crossing numbers for edges in the circuit are at least $-N$.
When all the walkers arrive at $C^{*}$ these crossing numbers decrease by at
most $-N$. At time $\rho^{\prime}$ the crossing number of $C^{*}$ are
increased by $N(N+3)$. Therefore, at time $\rho^{\prime}$ the crossing numbers
for the edges in the circuit $C^{*}$ are at least $N(N+3)-N-N=N^{2}+N$ which
is greater than $N$ for any $N\geq 1$. That is,
$S_{\rho^{\prime}}\neq\emptyset$ and ${\rm End}_{\rho^{\prime}}\subset
S_{\rho^{\prime}}.$ Observe also that, since we started with bounded crossing
numbers, the above event has a probability that is uniformly lower bounded by
a positive constant depending only on $N$ and the degrees of the graph (cf.
[6, Proposition 3.7]).

Second case: assume that $S_{\rho}\neq\emptyset.$ If ${\rm End}_{\rho}\subset
S_{\rho}$ we can conclude because in that case one simply has that
$\tau_{\rho}=\rho$. Otherwise, the set $I=\\{i\in[N]\,;\,X_{i}(\rho)\notin
S_{\rho}\\}$ is non empty. Without loss of generality we write
$I=\\{1,\cdots,K\\}$ for $1\leq K\leq N$. We employ a strategy that works as
follows:

  1. (1)

First we force the walker $X_{1}$ to follow a shortest path that connects
$X_{1}(\rho)$ to $S_{\rho}$ while all the other walkers are forced to stay
put. This will ensure that there exists a time $n_{1}$ such that
$X_{1}(\rho+n_{1})\in S_{\rho+n_{1}}$.

  2. (2)

In case $K\geq 2$, if $X_{2}\in S_{\rho+n_{1}}$ there is nothing to do,
otherwise we apply the first step to $X_{2}$ and $S_{\rho+n_{1}}$.

  3. (3)

We iterate until the set $I$ is fully exhausted.

The above strategy ensures that there exists a time $n$ such that
$X_{i}(\rho+n)\in S_{\rho+n}$ for all $i\in[N]$.

We now argue why the first step of the strategy works and can be employed with
a probability that is lower bounded from below uniformly in the environment. A
similar strategy has already been employed in [6, Lemma 3.2] and therefore we
refrain from giving a detailed proof here. Since $G$ is connected, there
exists a shortest path $\pi=(\pi(1),\cdots,\pi(\ell))$ connecting
$X_{1}(\rho)$ to $S_{\rho}$, and we force the walker $X_{1}$ to follow $\pi$.

Claim: $X_{1}(\rho+\ell)\in S_{\rho+\ell}.$

By the definition of a shortest path we have that $\pi(i)\notin S_{\rho}$ for
$i=1,\cdots,\ell-1$ and $\pi(\ell)\in S_{\rho}$. This immediately implies, by
the definition of $S_{\rho}$, that $|c_{\rho}(\pi(i),\pi(i+1))|\leq N$ for
$i=1,\cdots,\ell-1$. Recall that there exists $w$ such that
$|c_{\rho}(\pi(\ell),w)|\geq N+1$. In particular, $w\neq\pi(i)$ for
$i=1,\cdots,\ell-1$. As consequence, when the walker $X_{1}$ arrives at
$\pi(\ell)$ we have that $|c_{\rho+\ell}(\pi(\ell),w)|\geq N+1$ because the
edge $\\{w,\pi(\ell)\\}$ is not crossed by $X_{1}$ (recall that we force all
other walkers to stay put). And the claim is proved since
$X_{1}(\rho+\ell)=\pi(\ell).$ Since the crossing numbers of $\pi$ are bounded
by $N$, the probability of following this path is uniformly lower bounded in
the initial environment (but it depends on $N$).

Now we apply the second step and when we finish the iteration the final lower
bound will still be uniform in the environment because the number of walkers
is finite.

Similar calculations as in (3.8) show that $\tau_{\rho}$ is finite almost
surely.

Our second goal is to prove that $v\in D_{\tau}\implies\deg_{D_{\tau}}^{\rm
out}(v)\geq 1$.

The proof relies on flow properties induced by the vector of crossing numbers.
This idea was already used in [6].

For each $j\in[N]$ we define the individual flow by

$F_{n}^{(j)}(v)=\sum_{w:w\sim_{G}v}c_{n}^{(j)}(v,w).$

Then [6, Lemma 3.4] implies that $F_{n}^{(j)}(v)\in\\{-1,0,+1\\}$ for all
times and we have the following cases:

  1. (1)

$F_{n}^{(j)}(v)=+1$ if $v$ is the starting point of $X_{j}$ but is not the end
point.

  2. (2)

$F_{n}^{(j)}(v)=-1$ if $v$ is the end point of $X_{j}$ but is not at the same
time the starting point.

  3. (3)

$F_{n}^{(j)}(v)=0$ in all other cases.

We define the total flow at vertex $v\in V$ by

$F_{n}(v)=\sum_{j=1}^{N}F_{n}^{(j)}(v),$ (5.16)

and we directly have the following:

  1. (1)

$F_{n}(v)\in\llbracket-N,+N\rrbracket,$ for all $v\in V(G)$ and for all $n\geq
0.$

  2. (2)

$F_{n}(v)\geq 0$ if $v$ is not an end point of any of the walkers $X_{j}$ at
time $n.$

With the above facts at hand we proceed to show that $\deg_{D_{\tau}}^{\rm
out}(v)\geq 1$ for all $v\in D_{\tau}$. First of all note that by the
definition of the stopping time $\tau,$ $S_{\tau}\subset V_{\tau}.$

First case: $v\notin{\rm End}_{\tau}$. Then by definition of $V_{\tau}$ (cf.
(5.3)) there exists $u\sim_{G}v$ such that $c_{\tau}(v,u)\neq 0.$ The
condition $F_{\tau}(v)\geq 0$ enforces that there exists $w\sim_{G}v$ with
$c_{\tau}(v,w)>0.$ We prove that $w\in V_{\tau}$ resulting in
$\deg_{D_{\tau}}^{\rm out}(v)\geq 1$:

  * •

If $w\in{\rm End}_{\tau}$ then $w\in V_{\tau}$ by definition.

  * •

If $w\notin{\rm End}_{\tau}$ we use that $c_{\tau}(w,v)\neq 0$ which implies
$w\in V_{\tau}.$

Second case: $v\in{\rm End}_{\tau}$. Then by definition of $\tau$, $v\in
S_{\tau}$. As a consequence, there exists $w\sim_{G}v$ such that
$|c_{\tau}(v,w)|\geq N+1.$ Since $F_{n}(v)\in\llbracket-N,N\rrbracket$, there
exists $u\sim_{G}v$ with $c_{\tau}(v,u)>0.$ The proof that $u\in V_{\tau}$ is
the same as in the first case. That is, in any case we have that
$\deg_{D_{\tau}}^{\rm out}(v)\geq 1.$

Our third goal is to prove:

each connected component of $D_{\tau_{\rho}}$ has at least one circuit.

This is a variation of a standard result in basic combinatorics which asserts
that a graph $G$ with $\min_{v}\deg_{G}(v)\geq 2$ has at least one circuit. We
prove the above claim for completeness.

Fix a connected component $D\subseteq D_{\tau}$ and an arbitrary vertex
$v_{0}\in D$. Since $\deg_{D_{\tau}}^{\rm out}(v_{0})\geq 1$, there exists
$v_{1}\in D$ such that $v_{1}\sim_{D_{\tau}}v_{0}$. Note that
$c_{\tau}(v_{0},v_{1})>0$. In the same way we see that there exists $v_{2}\in
D$ with $c_{\tau}(v_{1},v_{2})>0$. Since
$c_{\tau}(v_{2},v_{1})=-c_{\tau}(v_{1},v_{2})<0<c_{\tau}(v_{0},v_{1})$ we can
conclude that $v_{0}\neq v_{2}$. One may now in the same fashion construct a
sequence $v_{0},v_{1},v_{2},\ldots$ of vertices in $D$ such that for all
$i\geq 0$ one has that $c_{\tau}(v_{i},v_{i+1})>0$ and such that $v_{i}\neq
v_{i+2}$, i.e., that sequence does not immediately backtrack. Since the
oriented graph $D_{\tau}$ is finite, there will be eventually a repetition in
the sequence, i.e., there exist two indices $i_{1}$ and $i_{2}$ with
$|i_{1}-i_{2}|\geq 3$ such that $v_{i_{1}}=v_{i_{2}}$ so that the sequence
$v_{i_{1}},v_{i_{1}+1},\ldots,v_{i_{2}}$ forms a circuit. Thus, we can
conclude.

###  5.2. Estimative of the Radom-Nikodym derivative - Ant RW

In this section we prove Lemma 5.3.

The proof follows along similar lines as the one in Section 3.1. Again we will
turn the expression $\frac{d\vec{X}}{d\vec{Y}}$ into an exponential of a sum,
and estimate that exponential. In the case that
$W_{1}\in{\mathcal{P}}_{\leq}$, $W_{2}\in{\mathcal{P}}_{\geq}$ (cf. (4.2)) the
sum obtained in this way can be controlled by using the total flow of the
crossing numbers. It then turns out that the new sum will behave like
$\Sigma(W_{2}/W_{1}).$ For more general reinforcement functions we assume
(4.6).

Let $\pi_{\tau}^{m}\in{\mathcal{A}}_{\tau}^{\uparrow}$. In particular
$\pi_{\tau}^{m}$ is a path, hence for every
$k\in\llbracket\tau,m-1\rrbracket$, there exists a $j\in[N]$ such that
$\pi_{k}(i)=\pi_{k+1}(i)$ for all $i\neq j$, and
$(\pi_{k}(j),\pi_{k+1}(j))\in\vec{E}_{\tau}$. In the following computation we
write $v_{k}^{\pi}$ instead of $\pi_{j}(k)$, i.e., $v_{k}^{\pi}$ is the only
coordinate of $\pi_{k}$ which changes from time $k$ to $k+1$. A
straightforward computation shows that

$\begin{split}\frac{d\vec{X}}{d\vec{Y}}(\pi_{\tau}^{m})&=\prod_{k=\tau}^{m-1}\frac{\displaystyle\sum_{w;c_{k}(v^{\pi}_{k},w)>0}W_{1}(c_{k}(v^{\pi}_{k},w))}{\displaystyle\sum_{w;c_{k}(v^{\pi}_{k},w)>0}W_{1}(c_{k}(v^{\pi}_{k},w))+\displaystyle\sum_{w;c_{k}(v^{\pi}_{k},w)\leq
0}W_{2}(-c_{k}(v^{\pi}_{k},w))}\\\
&=\prod_{k=\tau}^{m-1}\frac{1}{1+\frac{\displaystyle\sum_{w;c_{k}(v^{\pi}_{k},w)\leq
0}W_{2}(-c_{k}(v^{\pi}_{k},w))}{\displaystyle\sum_{w;c_{k}(v^{\pi}_{k},w)>0}W_{1}(c_{k}(v^{\pi}_{k},w))}}.\end{split}$
(5.17)

Now we split the analysis in cases, depending on the assumptions about $W_{1}$
and $W_{2}.$ We start with the simplest case.

Case 1: $(W_{1},W_{2})$ satisfies (4.6).

From (4.4), and the inequality $1/(1+x)\geq e^{-x}$ applied to the right hand
side in (5.17) we immediately obtain that

$\begin{split}\frac{d\vec{X}}{d\vec{Y}}(\pi_{\tau}^{m})&=\prod_{k=\tau}^{m-1}\frac{1}{1+\frac{\Upsilon^{-}(c_{k}(v_{k}^{\pi},\,\cdot\,))}{\Upsilon^{+}(c_{k}(v_{k}^{\pi},\,\cdot\,))}}\\\
&\geq\exp\bigg{(}-\sum_{k=\tau}^{m-1}\frac{\Upsilon^{-}(c_{k}(v_{k}^{\pi},\,\cdot\,))}{\Upsilon^{+}(c_{k}(v_{k}^{\pi},\,\cdot\,))}\bigg{)}\,.\end{split}$

It remains to estimate the sum inside the exponential. To that end we write

$\sum_{k=\tau}^{m-1}\frac{\Upsilon^{-}(c_{k}(v_{k}^{\pi},\,\cdot\,))}{\Upsilon^{+}(c_{k}(v_{k}^{\pi},\,\cdot\,))}=\sum_{v\in
V(D_{\tau})}\sum_{k=\tau}^{m-1}\frac{\Upsilon^{-}(c_{k}(v,\,\cdot\,))}{\Upsilon^{+}(c_{k}(v,\,\cdot\,))}\mathds{1}_{\\{v^{\pi}_{k}=v\\}}\,.$
(5.18)

Recall the definition of $\Phi$ in Definition (4.2). Fix a vertex $v$ and let
$n_{1}(v)$, $n_{2}(v)$, $\ldots$ be the sequence of times at which the path
$\pi_{\tau}^{m}$ visits $v$. Since the state space of $\pi_{\tau}^{m}$ is
$D_{\tau}^{N}$ we can conclude that $(c_{n_{i}(v)}(v,\cdot))_{i}$ belongs to
$\Phi$. Hence, by Assumption (4.6) the inner sum in (5.18) is uniformly
bounded from above, and since $|V|$ is finite the same is true for the sum on
the left hand side of (5.18). Hence, we can conclude.

Case 2: $W_{1}\in{\mathcal{P}}_{\leq}$, $W_{2}\in{\mathcal{P}}_{\geq}$,
$W_{2}$ satisfies (4.3) and $\Sigma(W_{2}/W_{1})=\infty$.

Define the positive and negative flow (cf. (5.16)) at $v^{\pi}_{k}$ by

$\begin{split}F_{k}^{+}(v^{\pi}_{k})&=\displaystyle\sum_{w;c_{k}(v^{\pi}_{k},w)>0}c_{k}(v^{\pi}_{k},w)\,,\\\
F_{k}^{-}(v^{\pi}_{k})&=\displaystyle\sum_{w;c_{k}(v^{\pi}_{k},w)\leq
0}-c_{k}(v^{\pi}_{k},w)\,.\end{split}$

By (4.2) there exists a constant $C=C(\Delta(G),W_{1},W_{2})$ such that

$\begin{split}\displaystyle\sum_{w;c_{k}(v^{\pi}_{k},w)>0}W_{1}(c_{k}(v^{\pi}_{k},w))&\leq
CW_{1}(F_{k}^{+}(v^{\pi}_{k}))\,,\\\
\displaystyle\sum_{w;c_{k}(v^{\pi}_{k},w)\leq
0}W_{2}(-c_{k}(v^{\pi}_{k},w))&\geq
C^{-1}W_{2}(F_{k}^{-}(v^{\pi}_{k}))\,.\end{split}$ (5.19)

Using (5.19) in (5.17), the relation
$F_{k}^{+}(v_{k}^{\pi})-F_{k}^{-}(v_{k}^{\pi})=F_{k}(v_{k}^{\pi})$ and that
$W_{2}$ satisfies (4.3), we see that there exists a constant
$\bar{{\mathcal{C}}}$ such that

$\frac{d\vec{X}}{d\vec{Y}}(\pi_{\tau}^{m})\leq\prod_{k=\tau}^{m-1}\frac{1}{1+C^{-2}\frac{W_{2}(F_{k}^{-}(v_{k}^{\pi}))}{W_{1}(F_{k}^{+}(v_{k}^{\pi}))}}\leq\prod_{k=\tau}^{m-1}\frac{1}{1+\bar{{\mathcal{C}}}\frac{W_{2}(F_{k}^{+}(v_{k}^{\pi}))}{W_{1}(F_{k}^{+}(v_{k}^{\pi}))}}.$

Observe that for $x\in(0,2]$ it holds that $1/(1+x)\leq e^{-x/2}.$ If $x>2$ we
have that $1/(1+x)\leq 1/3$. Define the set of indices

$I_{m}=\\{\tau\leq k\leq
m-1\,:\,\bar{{\mathcal{C}}}\frac{W_{2}(F_{k}^{+}(v_{k}^{\pi}))}{W_{1}(F_{k}^{+}(v_{k}^{\pi}))}\leq
2\\}\,.$

Therefore,

$\frac{d\vec{X}}{d\vec{Y}}(\pi_{\tau}^{m})\leq
3^{-|I_{m}^{\complement}|}\exp\bigg{(}-\frac{1}{2}\sum_{k\in
I_{m}}\bar{{\mathcal{C}}}\frac{W_{2}(F_{k}^{+}(v_{k}^{\pi}))}{W_{1}(F_{k}^{+}(v_{k}^{\pi}))}\bigg{)}.$
(5.20)

As $m\to\infty$ then either $|I_{m}|\to\infty$ or
$|I_{m}^{\complement}|\to\infty$ (or both tend to infinity). Since,
$\Sigma(W_{2}/W_{1})=\infty$, using similar arguments as in (5.18) we can
conclude in any case.

###  5.3. The support of $\vec{Y}^{\tau}$

In this section we prove Lemma 5.5.

The strategy of the proof is to use a collection of independent balls-in-bins
processes (cf. Section 2.6) to provide an alternative construction of the
process $\vec{Y}^{\tau}.$ Then we use Theorem 2.1 to describe the long time
behaviour of $\vec{Y}^{\tau}$.

For each $v\in V_{\tau}$ we consider the balls-in-bins process
$\vec{\eta}^{v}:=(\eta^{v}_{w}(n);(v,w)\in\vec{E}_{\tau})_{n\in{\mathbb{N}}}$
with initial number of balls given by $\eta^{v}_{w}(0)=c_{\tau}(v,w)$ and
reinforcement function $W_{1}.$ Observe that $\eta^{v}(w)(0)\geq 1$ by
definition of $D_{\tau}$ and that the process $\vec{\eta}^{v}$ consists of
$\deg_{D_{\tau}}^{\rm out}(v)\geq 1$ bins.

For the alternative construction of the process $\vec{Y}^{\tau}$ from time
$\tau$ onwards assume that $\vec{Y}^{\tau}(\tau)=\vec{v}\in D_{\tau}^{N}$. We
first choose $i\in[N]$ uniformly at random. It means that the walker $Y_{i}$
will jump. Since $Y_{i}(\tau)=v_{i}$ we throw a ball in a bin according to the
law of $\vec{\eta}^{v_{i}}$. If this ball is thrown in the bin corresponding
to $w$ then we set $Y^{\tau}_{i}(\tau+1)=w.$ In particular, this means that
$\eta^{v}_{w}(1)=\eta^{v}_{w}(0)+1=c_{\tau,\tau}(v,w)+1=c_{\tau,\tau+1}(v,w).$
We continue the process in this way. It is easy to see from the definition of
ball-in-bins dynamics (cf. Section 2.6) that we generate a process with the
same law as the process $\vec{Y}^{\tau}$ defined in Section 5.

We proceed to prove Lemma 5.5. From now on we drop the dependency on $\tau.$
Recall the definition of ${\mathcal{D}^{\infty}}$ in (5.8).

Assume that $G$ has exactly one circuit. We claim that each walker $Y_{j}$,
$1\leq j\leq N$, is trapped in the unique circuit $C_{*}$ of $G$. Indeed,
since $Y_{j}$ is non-backtracking and the graph $G$ is finite, it must close a
circuit which is $C_{*}$. If $Y_{j}$ would leave $C_{*}$ then since it is non-
backtracking it would need to eventually close a circuit which however would
be different from $C_{*}$. This is impossible by the assumption that $G$ has
only one circuit. Note at that point that all balls-in-bins process that we
use to emulate the dynamics of $\vec{Y}$ will have only one bin, since each
bin in the construction of the processes $\vec{Y}$ corresponds to an edge
whose corresponding crossing number is positive and therefore the trajectory
of $\vec{Y}$ is restricted to a circuit. In particular, the monopolistic and
leadership events coincide with the realization of the balls-in-bins
processes.

Assume now that $G$ has at least two circuits. Our goal is to describe the
graph ${\mathcal{D}}^{\infty}$. Our first step is to prove that
${\mathcal{D}}^{\infty}$ is a union of circuits. We further specialize this
description depending on the regime of $W_{1}$.

First step: ${\mathcal{D}}^{\infty}$ is the union of circuits. Let $\Gamma$ be
the collection of circuits of ${\mathcal{D}}^{\infty}$ that are crossed
infinitely often. We also define

$\Gamma_{v}=\\{C\in\Gamma\,:\,v\in C\\}\,.$

Claim: we have that $\Gamma_{v}\neq\emptyset$ for every
$v\in{\mathcal{D}}^{\infty}$.

Indeed, if $v\in{\mathcal{D}}^{\infty}$ there exists a walker $Y_{j}$ that
visits $v$ infinitely often since the number of walkers are finite. If
$Y_{j}(n)=v$ the first return to $v$ after time $n$ generates a circuit
because $Y_{j}$ is non-backtracking: it uses an outer edge to leave $v$, and
uses an inner edge to return to $v$. That is, each visit of $Y_{j}$ to $v$
corresponds to a complete visit to some circuit containing $v$. Since the
number of circuits is finite there exists a circuit $C_{v}$ with $v\in C_{v}$
that is visited infinitely often by $Y_{j},$ which is enough to conclude the
argument. As consequence of the claim, we have that
${\mathcal{D}}^{\infty}=\cup_{C\in\Gamma}C.$

Second step: here we need to assume that $\Sigma(W_{1}^{-1})<\infty.$

Our goal is to prove that the union
${\mathcal{D}}^{\infty}=\cup_{C\in\Gamma}C$ is  disjoint. To do that, it is
enough to prove that $|\Gamma_{v}|=1$ for any $v\in{\mathcal{D}}^{\infty}$.
Indeed, let $C,C^{\prime}\in\Gamma$ with $C\cap C^{\prime}\neq\emptyset$. For
$v\in C\cap C^{\prime}$, $|\Gamma_{v}|=1$ immediately implies that
$C=C^{\prime}.$

Now we prove that $|\Gamma_{v}|=1$ for a fixed $v\in{\mathcal{D}}^{\infty}.$
Let $C_{1},\,C_{2}\in\Gamma$ with $v\in C_{1}\cap C_{2}$ and $C_{1}\neq
C_{2}.$ Then there exist vertices $w_{1}$ and $w_{2}$ such that $(v,w_{1})$ is
an edge of $C_{1}$ but not of $C_{2}$ and $(v,w_{2})$ is an edge of $C_{2}$
but not of $C_{1}$. In particular, $(v,w_{1})\in\vec{{\mathcal{E}}}^{\infty}$
and $(v,w_{2})\in\vec{{\mathcal{E}}}^{\infty}$ with $w_{1}\neq w_{2}$ (recall
that our graph does not have multiple edges). However, each visit of $\vec{Y}$
to $v$ corresponds to a realization of a balls-in-bins process with
reinforcement function $W_{1}$. Since $\Sigma(W_{1}^{-1})<\infty$, Theorem 2.1
asserts that we are in the monopolistic regime. This is a contradiction with
the fact that the bin corresponding to $(v,w_{1})$ receives infinitely many
balls as well as the bin corresponding to $(v,w_{2})$. Hence, $C_{1}=C_{2}$.

##  Appendix A Proof of Proposition 4.4

Proof part (a):

By assumption $\sum_{k\geq 0}W_{1}(k)^{-1}<\infty$ and $W_{2}$ is non-
increasing. Consider an element $(\phi_{n})_{n\in{\mathbb{N}}}\in\Phi$, and
denote by $d$ its dimension, i.e., $\phi_{n}\in{\mathbb{Z}}^{d}$ for all $n$.
Since $W_{2}$ is non-increasing one has in particular that $W_{2}(-k)\leq
W(0)$ for all $k\leq 0$. Hence,

$\Upsilon^{-}(\phi_{n})=\sum_{i:\phi(i)\leq 0}W_{2}(-\phi_{n}(i))\leq
dW_{2}(0),$ (A.1)

for all $n\in{\mathbb{N}}$. To estimate the positive part, we first note that
for any $n$ and $i$ such that $\phi_{n}(i)>0$ one has that

$\Upsilon^{+}(\phi_{n})=\sum_{j:\phi(j)>0}W_{1}(\phi_{n}(j))\geq
W_{1}(\phi_{n}(i)).$

Moreover, by the definition of the sequence $(\phi_{n})_{n\in{\mathbb{N}}}$
for any $n\geq 0$ there exists $i=i(n)\in\\{1,2,\ldots,d\\}$ such that
$\phi_{n+1}(i)=\phi_{n}(i)+1$. Thus, we see that

$\sum_{n=1}^{\infty}\frac{1}{\Upsilon^{+}(\phi_{n})}\leq\sum_{n=1}^{\infty}\frac{1}{W_{1}(\phi_{n}(i(n)))}.$
(A.2)

To continue, for $k\in{\mathbb{N}}$ we define the quantity $L_{k}$ via

$L_{k}=\big{|}\\{n\in{\mathbb{N}}:\,\phi_{n}(i(n))=k\\}\big{|},$

and we note that $L_{k}\leq d$, since the vector $\phi_{n}$ has $d$ components
and one entry is updated at each time enforcing that at most in $d$ instances
of time one has a component at level $k$. We therefore can conclude that

$\displaystyle\sum_{n=1}^{\infty}\frac{1}{W_{1}(\phi_{n}(i(n)))}$
$\displaystyle=\sum_{n=1}^{\infty}\sum_{k\geq
0}\frac{1}{W_{1}(\phi_{n}(i(n)))}\mathds{1}_{\\{\phi_{n}(i(n))=k\\}}$
$\displaystyle=\sum_{k\geq 0}\frac{L_{k}}{W_{1}(k)}$ $\displaystyle\leq
d\sum_{k=1}^{\infty}\frac{1}{W_{1}(k)}<\infty,$

where the last inequality uses that $\Sigma(W_{1}^{-1})<\infty$. Combining
this with (A.1) and (A.2) allows us to conclude that (4.6) holds.

Proof of part (b).

We show that (4.6) is satisfied. To that end we denote by $C$ a
proportionality constant that might change from occurrence to occurrence. We
consider a function $(\phi_{n})_{n\in{\mathbb{N}}}\in\Phi$ as in the first
part of the proof. We note that for any index $\alpha>0$, any
$j\in{\mathbb{N}}$ for any collection of positive numbers $a_{1},\ldots,a_{j}$
one has that

$\frac{1}{C}\Big{(}\sum_{i=1}^{j}a_{i}\Big{)}^{\alpha}\leq\sum_{i=1}^{j}a_{i}^{\alpha}\leq
C\Big{(}\sum_{i=1}^{j}a_{i}\Big{)}^{\alpha},$ (A.3)

where $C$ above only depends on $\alpha$ and $j$. To continue, we define

${\mathcal{F}}_{+}(\phi_{n}):=\sum_{\begin{subarray}{c}i:\,\phi_{n}(i)>0\end{subarray}}\phi_{n}(i),\quad{\mathcal{F}}_{-}(\phi_{n}):=\sum_{\begin{subarray}{c}i:\,\phi_{n}(i)\leq
0\end{subarray}}\phi_{n}(i),$

and we note that the second item in Definition 4.2 implies that for any $n$
one has that
${\mathcal{F}}_{+}(\phi_{n})+{\mathcal{F}}_{-}(\phi_{n})\in\llbracket-N,+N\rrbracket$.
Therefore, (A.3) yields the estimate

$\frac{\Upsilon^{-}(\phi_{n})}{\Upsilon^{+}(\phi_{n})}\leq
C\frac{(-{\mathcal{F}}_{-}(\phi_{n}))^{q}}{{\mathcal{F}}_{+}(\phi_{n})^{p}}\leq
C\frac{(N+{\mathcal{F}}_{+}(\phi_{n}))^{q}}{{\mathcal{F}}_{+}(\phi_{n})^{p}}\leq
C\frac{1}{{\mathcal{F}}_{+}(\phi_{n})^{p-q}}\,,$ (A.4)

To finish the proof it only remains to note that the sequence
$({\mathcal{F}}_{+}(\phi_{n}))_{n\in{\mathbb{N}}}$ is a sequence of positive
numbers satisfying
${\mathcal{F}}_{+}(\phi_{n+1})={\mathcal{F}}_{+}(\phi_{n})+1$ for all
$n\in{\mathbb{N}}$.

Proof of part (c).

First of all note that by the monotonicity of the logarithm, we have that for
some constant $C$

$\Upsilon^{-}(\phi)\leq C\log\Big{(}-{\mathcal{F}}_{-}(\phi_{n})\Big{)}^{q}.$

Moreover, one may show that there exists a universal constant $C$ such that

$\sum_{i:\,\phi_{n}(i)>0}W_{1}(\phi_{n}(i))\geq
CW_{1}({\mathcal{F}}_{+}(\phi_{n})),$ (A.5)

and we may conclude as in part (b).

Proof of part (d).

The assumptions $W_{1}\in{\mathcal{P}}_{\geq}$,
$W_{2}\in{\mathcal{P}}_{\leq}$, and $W_{2}$ satisfies (4.3) guarantees that
the proof of part (d) is exactly the same as in part (b).

Proof of part (e).

Consider again an element $(\phi_{n})_{n\in{\mathbb{N}}}\in\Phi$, and denote
by $d$ its dimension, i.e., $\phi_{n}\in{\mathbb{Z}}^{d}$ for all $n$. Recall
that $W_{2}(k)\leq e^{\alpha k}$ for all $k\in{\mathbb{N}}$, and note that
$k\mapsto e^{\alpha k}$ is increasing. Then we have, for all
$n\in{\mathbb{N}}$, that

$\begin{split}\Upsilon^{-}(\phi_{n})&=\sum_{i:\phi(i)\leq
0}W_{2}(-\phi_{n}(i))\\\ &\leq\sum_{i:\phi(i)\leq
0}\exp(\alpha(-\phi_{n}(i)))\\\ &\leq d\exp\bigg{(}\alpha\sum_{i:\phi(i)\leq
0}(-\phi_{n}(i))\bigg{)}\,.\end{split}$

Using that $W_{1}(k)=e^{\beta k}$ is convex, we obtain that

$\begin{split}\Upsilon^{+}(\phi_{n})&=\sum_{i:\phi(i)>0}W_{1}(\phi_{n}(i))\\\
&=\sum_{i:\phi(i)>0}\exp(\beta\phi_{n}(i))\\\ &\geq
d\exp\bigg{(}\frac{\beta}{d}\sum_{i:\phi(i)>0}\phi_{n}(i)\bigg{)}\,.\end{split}$
(A.6)

Therefore, as in part (b) we obtain

$\frac{\Upsilon^{-}(\phi_{n})}{\Upsilon^{+}(\phi_{n})}\leq\frac{\exp(\alpha(N+{\mathcal{F}}_{+}(\phi_{n})))}{\exp\big{(}\frac{\beta}{d}({\mathcal{F}}_{+}(\phi_{n}))\big{)}}$
(A.7)

Since $N$ is fixed and ${\mathcal{F}}_{+}(\phi_{n})\to\infty$, as
$n\to\infty$, the sum of (A.7) over $n$ is finite if $\beta>d\alpha$. We are
done because $\Delta(G)\geq d$.

## Acknowledgements

D. E. gratefully acknowledges financial support from the National Council for
Scientific and Technological Development - CNPq via a Universal grant
409259/2018-7, and a Bolsa de Produtividade 303520/2019-1. D. E. moreover
acknowledges support by the Serrapilheira Institute which supported this work
(grant number Serra - R-2011-37582). G. R. was supported by a Capes/PNPD
fellowship 888887.313738/2019-00. The authors are grateful to T. Franco and A.
Teixeira for fruitful discussions about the topic of the paper. The authors
are also grateful to the anonymous referees for their valuable input.

## References

  * [1] A G Angel, M R Evans, E Levine, and D Mukamel.  Criticality and condensation in a non-conserving zero-range process.  Journal of Statistical Mechanics: Theory and Experiment, 2007(08):P08017–P08017, 2007.
  * [2] Ludwig Arnold.  Mathematical models of chemical reactions.  In Michiel Hazewinkel and Jan C. Willems, editors, Stochastic Systems: The Mathematics of Filtering and Identification and Applications, pages 111–134, Dordrecht, 1981. Springer Netherlands.
  * [3] Douglas Blount.  Comparison of stochastic and deterministic models of a linear chemical reaction with diffusion.  Ann. Probab., 19(4):1440–1462, 1991.
  * [4] Douglas Blount.  Law of large numbers in the supremum norm for a chemical reaction with diffusion.  Ann. Appl. Probab., 2(1):131–141, 1992.
  * [5] Codina Cotar and Debleena Thacker.  Edge- and vertex-reinforced random walks with super-linear reinforcement on infinite graphs.  Ann. Probab., 45(4):2655–2706, 07 2017.
  * [6] Dirk Erhard, Tertuliano Franco, and Guilherme Reis.  The Directed Edge Reinforced Random Walk: The Ant Mill Phenomenon.  https://arxiv.org/abs/1911.07295, 2019.
  * [7] Tertuliano Franco and Pablo Groisman.  A particle system with explosions: Law of large numbers for the density of particles and the blow-up time.  Journal of Statistical Physics, 149(4):629–642, 2012.
  * [8] Daniel Kious, Cécile Mailler, and Bruno Schapira.  Finding geodesics on graphs using reinforcement learning.  arXiv e-prints, October 2020.
  * [9] V. Limic and P. Tarrès.  Attracting edge and strongly edge reinforced walks.  Ann. Probab., 35(5):1783–1806, 2007.
  * [10] Vlada Limic.  Attracting edge property for a class of reinforced random walks.  The Annals of Probability, 31(3):1615 – 1654, 2003.
  * [11] Tianren Ma, Zhengyou Xia, and Fan Yang.  An ant colony random walk algorithm for overlapping community detection.  Lecture Notes in Computer Science Intelligent Data Engineering and Automated Learning–IDEAL 2017, pages 20 –– 26, 2017.
  * [12] Franz Merkl and Silke W. W. Rolles.  Linearly edge-reinforced random walks, volume Volume 48 of Lecture Notes–Monograph Series, pages 66–77.  Institute of Mathematical Statistics, Beachwood, Ohio, USA, 2006.
  * [13] Roberto Oliveira.  Balls-in-bins processes with feedback and Brownian motion.  Combin. Probab. Comput., 17(1):87–110, 2008.
  * [14] R. Pemantle.  Phase transition in reinforced random walk and RWRE on trees.  Ann. Probab., 16(3):1229–1241, 1988.
  * [15] Robin Pemantle.  A survey of random processes with reinforcement.  Probab. Surveys, 4:1–79, 2007.
  * [16] Pavol Quittner and Philippe Souplet.  Superlinear parabolic problems.  Birkhäuser Advanced Texts: Basler Lehrbücher. [Birkhäuser Advanced Texts: Basel Textbooks]. Birkhäuser Verlag, Basel, 2007.  Blow-up, global existence and steady states.