X 2pt 2pt

Technical University of Munich
Department of Mathematics
Master’s Thesis in Mathematics
Variations on
Reinforced Random Walks
Fabian Michel
Supervisor: Prof. Dr. rer. nat. habil. Nina Gantert
Submission Date: 16/09/2022

Technical University of Munich
Department of Mathematics
Master’s Thesis in Mathematics
Variations on
Reinforced Random Walks
Abwandlungen
selbstverstärkender Irrfahrten
Fabian Michel
Supervisor: Prof. Dr. rer. nat. habil. Nina Gantert
Submission Date: 16/09/2022
final digital version

I confirm that this master’s thesis is my own work and I have documented all
sources and material used.
Ich erkläre hiermit, dass ich diese Arbeit selbständig und nur mit den
angegebenen Hilfsmitteln angefertigt habe.

Fabian Michel, München, 16/09/2022

Abstract

This thesis examines edge-reinforced random walks with some modifications to
the standard definition. An overview of known results relating to the standard
model is given and the proof of recurrence for the standard linearly edge-
reinforced random walk on bounded degree graphs with small initial edge
weights is repeated. Then, the edge-reinforced random walk with multiple
walkers influencing each other is considered. The following new results are
shown: on a segment of three nodes, the edge weights resemble a Pólya urn and
the fraction of the edge weights divided by the total weight forms a
converging martingale. On $\mathbb{Z}$, the behavior is the same as for a
single walker – either all walkers have finite range or all walkers are
recurrent. Finally, edge-reinforced random walks with a bias in a certain
direction are analysed, in particular on $\mathbb{Z}$. It is shown that the
bias can introduce a phase transition between recurrence and transience,
depending on the strength of the bias, thus fundamentally altering the
behavior in comparison to the standard linearly reinforced random walk.

Zusammenfassung

Diese Masterarbeit betrachtet (kanten-)selbstverstärkende Irrfahrten mit
einigen Veränderungen im Vergleich zur gängigen Definition. Es wird eine
Übersicht über bekannte Ergebnisse zum gängigen Modell gegeben und der Beweis,
dass die linear selbstverstärkende Irrfahrt auf Graphen mit beschränktem Grad
und hinreichend kleinen anfänglichen Kantengewichten rekurrent ist, wird
wiederholt. Danach werden selbstverstärkende Irrfahrten mit mehreren Walkern,
die sich gegenseitig beeinflussen, untersucht. Die folgenden neuen Resultate
werden bewiesen: Auf einer Strecke mit drei Knoten ähneln die Kantengewichte
einer Pólya-Urne und der Anteil der Kantengewichte am Gesamtgewicht bildet ein
konvergierendes Martingal. Auf $\mathbb{Z}$ ist das Verhalten das gleiche wie
für einen einzelnen Walker – entweder besuchen alle Walker nur einen endlichen
Teil des Graphen oder alle sind rekurrent. Zum Schluss wird die
selbstverstärkende Irrfahrt mit Bias in eine bestimmte Richtung betrachtet,
vor allem auf $\mathbb{Z}$. Es wird gezeigt, dass der Bias einen
Phasenübergang zwischen Rekurrenz und Transienz verursachen kann, der von der
Stärke des Bias abhängt, und damit das Verhalten im Vergleich zur normalen
linear selbstverstärkenden Irrfahrt grundlegend ändert.

###### Contents

  1. 1 Introduction
    1. 1.1 Literature
    2. 1.2 Main Results
  2. 2 Preliminaries
    1. 2.1 Random Walks
  3. 3 Selected Results
    1. 3.1 Reinforced Random Walks
      1. 3.1.1 Linearly Edge-Reinforced Random Walk
      2. 3.1.2 Vertex-Reinforced Random Walk
    2. 3.2 Urn Models
      1. 3.2.1 Pólya Urn
      2. 3.2.2 Randomly Reinforced Urn
  4. 4 Recurrence of Edge-Reinforced Random Walk
    1. 4.1 Estimating Conductance Ratios
    2. 4.2 Bounding the Error
    3. 4.3 Bounding the Estimate
    4. 4.4 Proof of Recurrence
  5. 5 Reinforced Random Walk with Multiple Walkers
    1. 5.1 A Two-Player Urn
      1. 5.1.1 Alternating Players
      2. 5.1.2 Random Player Selection
    2. 5.2 Model on $\mathbb{Z}$
    3. 5.3 Recurrence or Finite Range on $\mathbb{Z}$
  6. 6 Biased Reinforced Random Walk
    1. 6.1 $\lambda^{\ast}$-Biased Edge-Reinforced Random Walk
      1. 6.1.1 Some Simulations
      2. 6.1.2 Stochastic Approximation
    2. 6.2 $\lambda^{+}$-Biased Edge-Reinforced Random Walk
    3. 6.3 Reinforced Random Walk on Transient Environment
  7. 7 Conclusion
    1. 7.1 Outlook

###### List of Figures

  1. 1 Estimating conductance ratios
  2. 2 Estimating conductance ratios along a deterministic path $\gamma$
  3. 3 Bounding $Q$ with the help of Bernoulli random variables
  4. 4 Edge weights of the line segment at time $n$
  5. 5 Possible walker locations after $2l-1$ steps of a path $\rho$ of length $2l$
  6. 6 Edge weights on $\mathbb{Z}$ at time $n$
  7. 7 Evolution of the supermartingale during 4 steps of the ERRW with multiple walkers
  8. 8 Label exchange lemma
  9. 9 Illustration: proof that all walkers recurrent or all have finite range
  10. 10 Edge weights and transition probabilities for the biased walk on $\mathbb{Z}$ at time $n$
  11. 11 Average speed of the random walk
  12. 12 Average last visit to the root by the random walk
  13. 13 Transition probabilities of the $\lambda^{\ast}$-biased ERRW on the triangle at time $n$
  14. 14 The vector field of the differential equation on the unit simplex
  15. 15 A random walk in a random environment on $\mathbb{Z}$
  16. 16 Edge weights of the walk on transient environment at time of first visit to $z>0$

###### List of Tables

  1. 1 Overview of results and conjectures on modified reinforced walks

### A note on cross-references in this thesis

Cross-references and citations are marked in red, and they are clickable and
directly link to the referenced object in the digital version. Titles,
definitions, theorems, etc. are colored in blue.

##  1 Introduction

The central topic of this thesis is the edge-reinforced random walk (ERRW), a
special type of random walk on a graph. The edges in the graph are weighted,
and the probability to leave a node via one of the incident edges is
proportional to the respective edge weight compared to the weights of the
other incident edges. Each time an edge is crossed, its weight is increased
according to some reinforcement scheme. Thus, it becomes more likely to visit
parts of the graph which have already been visited before again. Next to
reviewing results on this model, two modifications are considered: introducing
multiple random walkers which influence each other and introducing a bias in a
certain direction.

The ERRW is harder to analyze compared to random processes which possess the
Markov property. In contrast to Markov chains (MCs), where the transition
probabilities from one state to another only depend on the current state, but
not on the past, the transition probabilities of the ERRW change over time as
the edge weights are reinforced. The Markov property is lost. However, for a
certain class of ERRWs, namely the linearly edge-reinforced random walk
(LERRW), where the edge weights are increased by a constant increment upon
every traversal, the reinforced random walk is equal in law to a mixture of
MCs, i.e. a MC with random transition probabilities. This equivalence was the
basis for many of the known results for ERRWs, since it allows us to use tools
developed for MCs on the ERRW as well.

The new variations introduced in this thesis, multiple walkers and a bias,
break this connection to MCs as well (at least in most of the considered
cases, if not in all of them). The walk can no longer be represented as a
mixture of MCs, and has to be analyzed using different techniques. The results
presented here indicate that multiple walkers do not fundamentally change the
behavior of the LERRW, while a bias is strong enough to do so.

###  1.1 Literature

The ERRW, as well as its counterpart, the vertex-reinforced random walk
(VRRW), have been studied extensively, the first papers dating back to 1987,
when the model was introduced by Coppersmith and Diaconis. Even before, [9]
showed that the LERRW (if certain assumption are satisfied) has a
representation as a mixture of MCs. Much later, [20] showed that this
representation can be used for the LERRW on any graph, and [19] even gave a
formula for the so-called mixing measure on finite graphs. The mixing measure
simply is the distribution of the random transition probabilities in the
mixture of MCs.

Relatively early, results for the LERRW on trees were obtained. [14, 15, 29]
showed that there is a phase transition between recurrence and transience in
the initial edge weights. The interesting case of $\mathbb{Z}^{d}$ remained
open much longer until [4, 5, 6] showed that for $d\geq 3$, there is again a
transition from recurrence to transience in the initial weights. [7] proved
that this transition is sharp, i.e. there is a certain critical initial edge
weight such that for smaller initial weights, the random walk is recurrent,
and transient for larger weights.

In parallel, the VRRW was analyzed, but with completely different tools (there
is no representation as a mixture of MCs). [8] analyzed the behavior of the
VRRW on finite graphs with the help of a so-called stochastic approximation:
the evolution of the vertex weights is approximated by a differential
equation. [12, 13] proved that the VRRW (with linear reinforcement) gets stuck
on $5$ nodes on $\mathbb{Z}$, a result which could in part be generalized to
arbitrary graphs: [11] showed that the VRRW gets stuck with positive
probability on certain finite subgraphs for almost any graph. The behavior of
the VRRW is thus largely different from the behavior of the ERRW, and it was
therefore unclear how the variations of the ERRW considered here would affect
the random walk.

An overview of results on reinforced processes in general can be found in [1,
21]. These surveys also show that reinforced random walks are closely related
to urn processes, which have a very similar reinforcement component to the
linearly reinforced walks: in most urn models, when a ball of a certain color
is drawn, a fixed number of balls of the same color is added to the urn. This
is also a type of linear reinforcement, and urns have been used on many
occasions to analyze reinforced walks (see, for example, [14, 16]).

Reinforced walks with multiple walkers or with a bias have (to the best of our
knowledge) not been studied yet. There is however, another relevant part of
the literature which deals with Markovian random walks. Markov chains are
still a vital tool to understand the more complicated reinforced walks. [3,
10] are two very good resources for results and techniques which can be
applied to MCs. Finally, the references list additional sources which look at
various aspects of random walks, including more and different models for
reinforced walks.

###  1.2 Main Results

The following results are presented in this thesis. After covering preliminary
definitions in Section 2, some of the most important results on reinforced
random walks, in particular in relation to this thesis, are presented in
Section 3, without proof. Section 4 repeats the proof of one such result: the
recurrence of the LERRW on bounded-degree graphs for small initial weights
(see Theorem 4.4).

Section 5 covers the first new variation to the LERRW: multiple walkers
influencing each other. 5.9 shows that edge weights of the LERRW for $2$
walkers on a segment of $3$ nodes behave similarly to the proportion of balls
in a Pólya urn, and it is conjectured in 5.10 that the limit of the edge
weight proportions will have similar properties to the limit of the proportion
of balls in the urn. Theorem 5.17 considers the ERRW with more general
reinforcement and multiple walkers on $\mathbb{Z}$ and shows that its behavior
is similar to the case with a single walker: either all walkers are recurrent,
or all walkers have finite range.

In Section 6, the LERRW on $\mathbb{Z}$, but with an additional bias is
considered. 6.2 proves that, for a multiplicative bias, the probability to
move in the direction of bias converges to $1$ for nodes which are visited
infinitely often. This might hint at transience, as noted in 6.5. For an
additive bias, the representation as a mixture of MCs is recovered, allowing
us to show a phase transition between recurrence and transience in the bias in
Theorem 6.7, and it is even possible to show positive speed if the bias is
strong enough in Theorem 6.8. Finally, Section 6.3 considers the LERRW with a
strong bias in the initial edge weights: the initial edge weight to the right
of a node $z\in\mathbb{Z}$ is set to $\lambda^{z}$ for some parameter
$\lambda$. The unfinished calculation in Section 6.3 seems to indicate that
the reinforced walk will be transient, i.e. that the initially biased
environment dominates the reinforcement. This is similar in spirit to [7,
Theorem 4], where it was shown that if the initial weights are set to the
conductances of a recurrent MC, then the LERRW is also recurrent. In Section
6.3, we have an initially transient environment. However, there cannot be a
theorem like [7, Theorem 4] for transience, as can already be seen by looking
at Theorem 4.4.

Finally, Section 7 reviews the results on the new variations of the ERRW
obtained in this thesis, and looks at the many open questions which still
remain.

##  2 Preliminaries

Throughout this thesis, random walks on finite and infinite connected graphs
will be considered. All considered graphs will be locally finite, that is, the
number of edges incident to a node is always finite. The following notation is
used in connection with graphs:

######  Definition 2.1 (Graph)

A (possibly infinite) graph $G$ is a tuple $\left(V,E\right)$ of vertices (or
nodes) and edges, with
$E\subseteq\left\\{\left\\{u,v\right\\}\mathrel{}\middle|\mathrel{}u,v\in
V\land u\neq v\right\\}$. Sometimes, it is useful to consider directed edges,
hence we also define the set
$\overrightarrow{E}:=\left\\{\left(u,v\right)\mathrel{}\middle|\mathrel{}u,v\in
V\land\left\\{u,v\right\\}\in E\right\\}$ of directed edges. For
$e=\left(u,v\right)\in\overrightarrow{E}$, we call
$\overleftarrow{e}:=\left(v,u\right)$ the corresponding reversed edge, and we
write $\check{e}=u,\hat{e}=v$, so $e=\left(\check{e},\hat{e}\right)$. We write
$u\sim v$ if $\left\\{u,v\right\\}\in E$.
$\operatorname{dist}\left(u,v\right)$ is the edge length of the shortest path
between the two nodes and $\operatorname{dist}\left(v,e\right)$ is the minimum
of the distances of $v$ to the two endpoints of $e$.

###  2.1 Random Walks

One type of random walk on a graph is the RWRE, which is used as a tool to
analyze reinforced random walks. The RWRE is basically a Markov chain, but
with random transition probabilities, which are also referred to as the
environment. The formal definition is as follows:

######  Definition 2.2 (Random Walk in Random Environment)

Consider a graph $G=\left(V,E\right)$. Let
$\mathbf{c}:=\left(c_{e}\right)_{e\in E}$ be a collection of random variables
over some probability space with $c_{e}>0$. For $v\in V$, we further denote by
$c_{v}:=\sum_{u\in V:u\sim v}c_{\left\\{u,v\right\\}}$ the sum of the
conductances of all adjacent edges, and assume $c_{v}>0$. The environment
$P_{\mathbf{c}}:V\times V\to\left[0,1\right]$ on the graph $G$ is defined by

$\displaystyle
P_{\mathbf{c}}\left(u,v\right):=\frac{c_{\left\\{u,v\right\\}}}{c_{u}}$

The Markov chain (MC) $\left(X_{n}\right)_{n\geq 0}$, conditioned on the
knowledge of $\mathbf{c}$, and starting at $v\in V$, is now defined by

$\displaystyle\mathbb{P}_{v}^{\mathbf{c}}\left[X_{0}=v\right]=1\qquad\mathbb{P}_{v}^{\mathbf{c}}\left[X_{n+1}=t\mathrel{}\middle|\mathrel{}X_{n}=u\right]=P_{\mathbf{c}}\left(u,t\right)$

$X_{n}$ is a random walk taking values in $V$.

The distribution of $\mathbf{c}$ is called $\mathbf{P}$, and is called the
mixing measure, and the probability measure $\mathbb{P}_{v}$ is defined by
setting

$\displaystyle\mathbb{P}_{v}\left[\cdot\right]:=\int\mathbb{P}_{v}^{\mathbf{c}}\left[\cdot\right]\;\mathbf{P}\left(\mathrm{d}\mathbf{c}\right)$

$\left(X_{n}\right)_{n\geq 0}$, distributed according to $\mathbb{P}_{v}$, is
called random walk in random environment (RWRE), or mixture of MCs.

For more background on conductances as well as electrical networks and their
relation to random walks, [10] gives an excellent introduction (in Chapters 1
and 2).

We shall also use the following terminology:

  1. (1)

$\pi_{\mathbf{c}}:V\to\left[0,\infty\right)$ is called a stationary measure
for the MC given by the conductances $\mathbf{c}$ if it satisfies
$\pi_{\mathbf{c}}\left(v\right)=\sum_{u\in V:u\sim
v}\pi_{\mathbf{c}}\left(u\right)P_{\mathbf{c}}\left(u,v\right)$ for all $v\in
V$. $\pi_{\mathbf{c}}$ is further called a stationary distribution if it is a
probability measure. Setting $\pi_{\mathbf{c}}\left(v\right):=c_{v}$ defines a
stationary (and reversible) measure.

  2. (2)

The MC given by $\mathbf{c}$ is called recurrent if
$\mathbb{P}_{v}^{\mathbf{c}}\left[X_{n}=v\textrm{ for infinitely many
}n\right]=1$, and transient otherwise. In the transient case, it holds that
$\mathbb{P}_{v}^{\mathbf{c}}\left[X_{n}=v\textrm{ for infinitely many
}n\right]=0$, so the starting node $v$ is only visited finitely often a.s.,
and $\mathbb{P}_{v}^{\mathbf{c}}\left[\exists n>0:X_{n}=v\right]<1$. In the
recurrent case, it holds that $\mathbb{P}_{v}^{\mathbf{c}}\left[\exists
n>0:X_{n}=v\right]=1$ (obviously). Since the considered MCs are a.s.
irreducible (every node can be reached from every other node with positive
probability), this corresponds to the standard notion of recurrence and
transience.

The MC is further called positive recurrent if the expected return time to the
root is finite, i.e.
$\mathbb{E}_{v}^{\mathbf{c}}\left[\min\left\\{n>0:X_{n}=v\right\\}\right]<\infty$
(this implies recurrence). Positive recurrence is equivalent to the existence
of a (unique) stationary distribution. Note that the existence of a stationary
measure does not imply the existence of a stationary distribution since the
stationary measure may be infinite (if it is finite, it can always be
normalized). Indeed, in the null recurrent case (recurrent, but not positive
recurrent), there exists a unique stationary measure which is infinite.

We next define the ERRW, which is one of the main topics of this thesis. The
ERRW is not a MC since the transition probabilities change over time.

######  Definition 2.3 (Edge-Reinforced Random Walk)

Consider a graph $G=\left(V,E\right)$ and a counting function
$z:\mathbb{N}_{\geq 0}\times E\to\mathbb{N}_{\geq 0}$ where we set
$z\left(0,e\right)=0$ for all $e\in E$. Let $W_{e}:\mathbb{N}_{\geq
0}\to\left(0,\infty\right)$ be weight functions for $e\in E$. We now define
the evolution of $z$ as well as the edge-reinforced random walk (ERRW)
$\left(X_{n}\right)_{n\geq 0}$ on $G$ as follows:

$\displaystyle\textrm{for }n\geq 1:\textrm{
}z\left(n,\left\\{u,v\right\\}\right)=\sum_{i=1}^{n}\mathbbm{1}_{\left(X_{i-1}=u\land
X_{i}=v\right)\lor\left(X_{i-1}=v\land X_{i}=u\right)}$

i.e. $z$ counts the number of edge traversals, and

$\displaystyle\mathbb{P}_{v}\left[X_{0}=v\right]$ $\displaystyle=1$
$\displaystyle\mathbb{P}_{v}\left[X_{n+1}=t\mathrel{}\middle|\mathrel{}X_{n}=u,\ldots,X_{0}=x_{0}\right]$
$\displaystyle=\frac{W_{\left\\{u,t\right\\}}\left(z\left(n,\left\\{u,t\right\\}\right)\right)}{\sum_{s\in
V:s\sim
u}W_{\left\\{u,s\right\\}}\left(z\left(n,\left\\{u,s\right\\}\right)\right)}$

i.e. the probability to make a transition from $u$ to $t$ at time $n$ is
proportional to the weight
$W_{\left\\{u,t\right\\}}\left(z\left(n,\left\\{u,t\right\\}\right)\right)$
associated to the edge $\left\\{u,t\right\\}$, which depends on the number of
traversals of the edge. We set

$\displaystyle
w\left(n,\left\\{u,t\right\\}\right):=W_{\left\\{u,t\right\\}}\left(z\left(n,\left\\{u,t\right\\}\right)\right)$

The random variables $w$ thus describe the evolution of the edge weights to
which the transition probabilities are proportional.

It is also possible to make the edge weight depend on more than just the
number of edge traversals and the edge, but we restrict ourselves to this case
in this thesis which is already quite general. If $W_{e}$ is the same for
every $e\in E$, then we will write $W$ instead of $W_{e}$. One important
choice of $W$ is $W\left(n\right)=1+n$, which corresponds to starting with
initial edge weights $1$ everywhere and incrementing the weight of the
traversed edge by $1$ at every step. We define the linearly edge-reinforced
random walk (LERRW) in a way which is a little more general: the LERRW is the
reinforced random walk where $W_{e}\left(n\right)=a_{e}+n$ for some choice of
initial weights $\left(a_{e}\right)_{e\in E}\in\left(0,\infty\right)^{E}$.

Later, it will be useful to count the number of directed edge traversals. We
therefore also define the following counting function:

$\displaystyle\overrightarrow{z}\left(n,\left(u,v\right)\right)=\sum_{i=1}^{n}\mathbbm{1}_{X_{i-1}=u\land
X_{i}=v}$

Another type of random walk is obtained by using vertex weights instead of
edge weights for reinforcing.

######  Definition 2.4 (Vertex-Reinforced Random Walk)

Consider a graph $G=\left(V,E\right)$ and a counting function
$z:\mathbb{N}_{\geq 0}\times V\to\mathbb{N}_{\geq 0}$ where we set
$z\left(0,v\right)=0$ for all $v\in V$. Let $W_{v}:\mathbb{N}_{\geq
0}\to\left(0,\infty\right)$ be weight functions for $v\in V$. We now define
the evolution of $z$ as well as the vertex-reinforced random walk (VRRW)
$\left(X_{n}\right)_{n\geq 0}$ on $G$ as follows:

$\displaystyle\textrm{for }n\geq 1:\textrm{
}z\left(n,v\right)=\sum_{i=1}^{n}\mathbbm{1}_{X_{i}=v}$

i.e. $z$ counts the number of vertex visits, and

$\displaystyle\mathbb{P}_{v}\left[X_{0}=v\right]=1\qquad\mathbb{P}_{v}\left[X_{n+1}=t\mathrel{}\middle|\mathrel{}X_{n}=u,\ldots,X_{0}=x_{0}\right]=\frac{W_{t}\left(z\left(n,t\right)\right)}{\sum_{s\in
V:s\sim u}W_{s}\left(z\left(n,s\right)\right)}$

i.e. the probability to go from $u$ to $t$ at time $n$ is proportional to the
weight $W_{t}\left(z\left(n,t\right)\right)$ associated to the node $t$, which
depends on the number of visits to the node. We set

$\displaystyle w\left(n,t\right):=W_{t}\left(z\left(n,t\right)\right)$

##  3 Selected Results

Here, we present known results on reinforced random walks to put the following
sections into context.

###  3.1 Reinforced Random Walks

####  3.1.1 Linearly Edge-Reinforced Random Walk

The following relation between LERRW and RWRE is a very important tool to
analyze the LERRW. Many previous results on the LERRW have been proved using
the fact that the LERRW is equal in distribution to a mixture of Markov
chains, i.e. a MC with random transition probabilities. MCs are well
understood, thus this theorem allows us to use the tools we have for MCs, and
apply them to the non-Markovian LERRW.

######  Theorem 3.1 (Reinforced Walk as Mixture of Markov Chains ([4, Theorem
4], [20, Theorem 2.2], [9]))

For a finite graph $G$ with initial weights $\left(a_{e}\right)_{e\in E}$, the
LERRW is equal in law to a RWRE with a uniquely determined mixing measure
$\mathbf{P}$. For any $e\in E$, $\mathbf{P}\left[c_{e}>0\right]=1$. In
particular, if the probability measure corresponding to the LERRW is denoted
by $\mathbb{P}_{v}$, then

$\displaystyle\mathbb{P}_{v}\left[\cdot\right]=\int\mathbb{P}_{v}^{\mathbf{c}}\left[\cdot\right]\;\mathbf{P}\left(\mathrm{d}\mathbf{c}\right)$

with the notation from 2.2.

We next turn to the LERRW on trees. Using Theorem 3.1, one can show that

######  Theorem 3.2 (Phase Transition of Reinforced Walk on Trees ([14, 16]))

Let $T$ be a an infinite tree. Consider the LERRW on $T$ with initial weights
$a>0$. Let $\Delta_{0}$ be the solution to the equation

$\displaystyle\frac{\Gamma\left(\frac{2+\Delta}{4\Delta}\right)^{2}}{\Gamma\left(\frac{1}{2\Delta}\right)\Gamma\left(\frac{1+\Delta}{2\Delta}\right)}=\frac{1}{\operatorname{br}\left(T\right)}$

where $\operatorname{br}\left(T\right)$ is the branching number of the tree
$T$ (a measure of the number of children per node, the branching number is
equal to the number of children for regular trees; see [16, Definition 2.6]
for the exact definition). Then the LERRW on $T$ is

  1. (i)

a.s. transient if $a>\frac{1}{\Delta_{0}}$

  2. (ii)

a.s. recurrent if $a<\frac{1}{\Delta_{0}}$.

The expected return time to the root is always infinite.

The same holds for Galton-Watson trees with $\operatorname{br}\left(T\right)$
replaced by the mean number of children, if the mean is $>1$ and conditioned
upon non-extinction.

On $\mathbb{Z}$, the LERRW is recurrent for any choice of initial weight $a$.

In this thesis, a recurrence result for the LERRW on general graphs will be
shown. It is a part of the following theorem, for which we also need to define
the Cheeger constant. A graph is called nonamenable if there is a constant
$h>0$ such that for any finite set of nodes $A\subseteq V$, $\left|\partial
A\right|\geq h\left|A\right|$ where $\partial A=\left\\{v\in V\setminus
A:\operatorname{dist}\left(v,A\right)=1\right\\}$, i.e. $\partial A$ is the
set of nodes which are outside of $A$, but direct neighbors to a node within
$A$. The Cheeger constant is the largest such constant $h$, and can be defined
as follows:

$\displaystyle h\left(G\right):=\inf\left\\{\frac{\left|\partial
A\right|}{\left|A\right|}:A\subseteq V\textrm{ finite}\right\\}$

######  Theorem 3.3 (LERRW on General Graphs ([4, 5, 6]))

Let $G$ be any graph. Consider the LERRW with initial edge weight $a$ for
every edge. Then:

  1. (i)

for every constant $K$, there exists some $a_{0}>0$ such that if all degrees
of $G$ are bounded by $K$, the LERRW on $G$ is recurrent if
$a\in\left(0,a_{0}\right)$.

  2. (ii)

for every constant $K$, and any $c_{0}>0$, there exists some $a_{0}>0$ such
that if all degrees of $G$ are bounded by $K$, and if $h\left(G\right)\geq
c_{0}$, then the LERRW on $G$ is transient if $a>a_{0}$.

  3. (iii)

for $G=\mathbb{Z}^{3}$ and $G=\mathbb{Z}^{d}$ with any $d\geq 3$, there exists
some $a_{0}>0$ such that the LERRW on $G$ is transient if $a>a_{0}$.

Part i of the theorem above is shown in this thesis in Theorem 4.4. Next to
the above, and next to other results which are not listed here, the following
is known about the LERRW:

  * •

On $\mathbb{Z}^{3}$ and $\mathbb{Z}^{d}$ with any $d\geq 3$, there is a sharp
phase transition between recurrence and transience of the LERRW in the initial
edge weights. If the initial edge weights are all set to a constant $a>0$,
then there is a critical threshold $a_{0}$ such that the LERRW on
$\mathbb{Z}^{d}$ is recurrent if $a<a_{0}$ and transient if $a>a_{0}$. See [7,
Theorem 3].

  * •

On any locally finite graph, if a random walk with given conductances on the
edges is recurrent, then so is the LERRW if these conductances are used as
initial edge weights. See [7, Theorem 4].

  * •

The VRJP (vertex-reinforced jump process) is a continuous-time version of the
LERRW. The process $\left(Y_{t}\right)_{t\geq 0}$ takes values in the vertices
of a graph with conductances $W_{e}$ on the edges. If we are at vertex $v$ at
time $t$, then, conditional on $\left(Y_{s},s\leq t\right)$, the process jumps
to a neighbor $u$ of $v$ at rate $W_{\left\\{v,u\right\\}}\cdot
L_{u}\left(t\right)$ with

$\displaystyle
L_{u}\left(t\right)=1+\int_{0}^{t}\mathbbm{1}_{Y_{s}=u}\;\mathrm{d}s$

Up to an exponential time change, and using independent Gamma-distributed
conductances, this has the same distribution as the following model of a
continuous-time LERRW when looked at at jump times. In order to make the LERRW
continuous, we can add clocks on every edge. The time of an edge runs only
when the process is in a node adjacent to it, and the alarm of an edge rings
at exponential times with the rate of the edge weight (i.e. the rates are
increasing). When an alarm rings, then the process immediately traverses the
corresponding edge.

The VRJP is distributed as a mixture of time-changed Markov jump processes,
just as the LERRW is distributed as a mixture of Markov chains.

The results on the LERRW basically also apply to the VRJP (or the other way
round). See [5] for more details.

  * •

For the LERRW on finite graphs (with arbitrary initial weights), there is a
“magic formula”: The LERRW is a mixture of Markov chains where the mixing
measure can be given explicitly: if the edge weights are normalized to sum to
one, they converge to a random limit on the unit simplex. The law can be given
as a density w.r.t. the Lebesgue measure on the unit simplex, and the LERRW is
distributed as a mixture of (reversible) MCs with the weights chosen according
to this same measure (the weights are not independent across edges). See [19].

The main reason why this is true and also the basis of the proof is partial
exchangeability, i.e. two finite paths have the same probability if the edges
are traversed the same number of times (this is easy to see: the probability
of a path is a product of fractions; for nominators, consider the edges, for
denominators, the vertices, to see that the order of traversals is
irrelevant).

For recurrent LERRWs in general, we can use a de Finetti theorem on MCs, by
considering blocks of excursions from the starting vertex (these are iid
conditioned on some parameter) instead of balls drawn as for the most basic de
Finetti theorem. See [9].

  * •

The RWRE representation for the LERRW also exists for infinite graphs and in
particular transient LERRW (no explicit formula for the mixing measure is
known). See [20].

Just in order to mention that there is more than just linear reinforcement:
there is stronger than linear reinforcement which can lead to being stuck on a
single edge, and there is the once-reinforced random walk (where the edge
weight is only increased on the first visit and then stays constant) which is
even more difficult to analyze, little is known about it.

This thesis adapts the LERRW and adds multiple walkers or a bias to the model.
Section 5 and Section 6 add some results to the list above.

####  3.1.2 Vertex-Reinforced Random Walk

There are some changes in behavior if vertex weights instead of edge weights
are reinforced. A short overview of known results:

  * •

On any complete graph, the linearly vertex-reinforced random walk converges to
uniform vertex occupation (meaning that the time spent at each vertex, divided
by the total time, will converge to a uniform distribution, so the vertex
weights will all be of the same order). On any finite graph fulfilling a non-
degeneracy condition, vertex occupation converges to a rest point of a
differential equation approximating the evolution of the vertex weights. See
[8].

  * •

On $\mathbb{Z}$, the VRRW (linear reinforcement) is eventually trapped on an
interval of $5$ vertices, the middle vertex is visited with frequency
$\frac{1}{2}$, its neighbors with positive frequency, and the two outer
vertices are visited infinitely often but at frequency $0$. See [13].

  * •

On $\mathbb{Z}^{2}$, the VRRW (linear reinforcement) is trapped with positive
probability on $13$ vertices (a diamond with $\frac{1}{2}$-frequency core and
with $0$-frequency boundary) and with positive probability on $12$ vertices
(square with $0$-frequency boundary). See [11]. It still remains an open
question whether the VRRW is trapped with probability $1$.

  * •

On any graph of bounded degree, the VRRW (linear reinforcement) is trapped
with positive probability on finitely many vertices which form a complete
$n$-partite graph with outer boundary such that every vertex in the outer
boundary is not connected to one of the partitions plus one extra node. See
[11].

  * •

On any tree of bounded degree, the VRRW (linear reinforcement) is trapped with
probability $1$ on a finite subgraph. See [11].

  * •

On a tree with $K_{n}$ children for every node on level $n$, where $\sum
K_{n}^{-1}<\infty$, there is a positive probability for the VRRW (linear
reinforcement) to move away from the root on _every single_ step (transience),
but also a positive probability to get trapped (finite range), so there is no
$0$-$1$-law. See [11].

These results show that an apparently small change in the model can
dramatically affect the behavior of the random walk. Instead of being
recurrent or transient, as the LERRW, the VRRW with linear reinforcement has
finite range (gets stuck on a finite subgraph) with positive probability. This
is one of the reasons why it was interesting to study variations to the model
of the ERRW, in order to better understand which changes in the model cause
which effects.

###  3.2 Urn Models

Urn models are closely related to reinforced random walks since they are also
an example of a reinforced random process: usually, balls are drawn uniformly
at random, and more balls of the drawn color are added. Hence, the fraction of
balls of a certain color is reinforced upon drawing a ball of the same color.

####  3.2.1 Pólya Urn

Consider a Pólya urn, starting with $w$ white and $b$ black balls. At every
time step, draw a ball from the urn, and put it back along with $\Delta$ more
balls of the same color. Call $w_{n}$ and $b_{n}$ the number of white and
black balls after the $n$-th draw, so $w_{0}=w$ and $b_{0}=b$. Then:

######  Theorem 3.4 (Pólya Urn ([14, Lemma 1]))

The fraction of white balls $\frac{w_{n}}{w_{n}+b_{n}}$ is a martingale, and
it thus converges to a limit random variable $L$ which is distributed
according to a Beta distribution:

$\displaystyle
L\sim\operatorname{B}\left(\frac{w}{\Delta},\frac{b}{\Delta}\right)$

The sequence of balls drawn is equal in law to a mixture of iid sequences.
Indeed, conditioned on $L$, the sequence of balls drawn is distributed as an
iid sequence where a white ball is drawn with probability $L$.

The fact that the sequence of draws is distributed as a mixture of iid
sequences follows from de Finetti’s theorem, which is applicable since the
draws are exchangeable: the probability of a certain sequence of draws
occurring depends only on the number of white and black balls in the sequence,
but not on their order. This is very similar to what we already saw in Theorem
3.1, and indeed, the same arguments are used in the proof. Another thing to
note is that Theorem 3.4 does not only hold when $w,b$ and $\Delta$ are
integers, but also when they are replaced by any positive real numbers. In
other words, it is also possible to have only a fraction of a ball in the urn.

In Section 5, 5.9 and 5.10 show that something similar to a two-player Pólya
urn (where two players draw balls and do not put them back immediately)
exhibits very similar properties to that of the standard one-player Pólya urn.

####  3.2.2 Randomly Reinforced Urn

Consider the following urn model: initially, the urn contains $b_{0}$ black
and $w_{0}$ white balls. The numbers $b_{n}$ and $w_{n}$ of balls contained in
the urn in the $n$-th step is determined as follows. Draw a ball uniformly at
random from the urn with $b_{n-1}$ black balls and $w_{n-1}$ white balls. If
the ball is black, replace it with $M_{n}$ black balls. If the ball is white,
replace it with $N_{n}$ white balls. $M_{n}$ and $N_{n}$ are series of
independent random variables on the nonnegative natural numbers and all
$M_{n}$ have the common distribution $\mu$, all $N_{n}$ have the common
distribution $\nu$. It is assumed that $\mu$ and $\nu$ both have finite
support. Call $z_{n}=\frac{b_{n}}{b_{n}+w_{n}}$ the fraction of black balls in
the urn. Denote by $B_{n},W_{n},Z_{n}$ the corresponding random variables.

######  Theorem 3.5 (Randomly Reinforced Urn ([18, Theorem 4.1]))

If the following assumptions hold (and $\mu$ and $\nu$ both have finite
support, as stated above)

  1. (i)

$b_{0}>0\quad$ (at least one black ball in the urn at the beginning)

  2. (ii)

$\mu\left(\left\\{0\right\\}\right)=0\quad$ (if a black ball is drawn, it is
replaced by at least one black ball)

  3. (iii)

$\mu\geq_{\textrm{st}}\nu\quad$ ($\mu$ stochastically dominates $\nu$)

  4. (iv)

$\mathbb{E}\left[M_{n}\right]=\int_{\mathbb{N}}x\;\mu\left(\textrm{d}x\right)>\int_{\mathbb{N}}x\;\nu\left(\textrm{d}x\right)=\mathbb{E}\left[N_{n}\right]\quad$
(the expected number of black balls added is bigger than the expected number
of white balls added)

Then $\lim_{n\to\infty}Z_{n}=\lim_{n\to\infty}\frac{B_{n}}{B_{n}+W_{n}}=1$
a.s. (the fraction of black balls converges almost surely to $1$).

Theorem 3.5 covers a large class of urns, including urns with deterministic
reinforcement where a different number of balls is added depending on the
color.

##  4 Recurrence of Edge-Reinforced Random Walk

In this section, we repeat the proof of the known result that the LERRW is
recurrent on any bounded-degree graph for small initial weights. We already
know that the LERRW has an equivalent representation as a RWRE with random
conductances $c_{e}$ on the edges. If we further normalize these conductances
by setting $c_{v_{0}}=1$ where $v_{0}$ is the starting vertex of the LERRW (we
will assume this normalization in the following sections), then we can give a
more precise statement of what we want to show. We consider the weight
function $W\left(n\right)=a+n$ and are interested in the following result,
given in [4, Theorem 2]: if $G$ is a graph with degree at most $K$, if the
LERRW is recurrent on $G$ for any choice of initial weights, and if
$s\in\left(0,\frac{1}{4}\right)$, then there is some $a_{0}>0$, depending on
$s$ and $K$, such that for initial weights $a\in\left(0,a_{0}\right)$ we have
$\mathbb{E}_{v_{0}}\left[c_{e}^{s}\right]\leq
2K\left(C\left(s,K\right)\sqrt{a}\right)^{\operatorname{dist}\left(v_{0},e\right)}$
where $C\left(s,K\right)$ solely depends on $K$ and $s$. In particular, for
$a$ small enough, we have exponential decay in the expected conductances
$c_{e}$ of the random environment corresponding to the LERRW (exponential
decay with increasing distance, and with the conductances raised to the $s$-th
power). As a consequence, we can prove under almost the same assumptions, but
without requiring a priori that the random walk is recurrent, that the LERRW
is recurrent for $a$ small enough.

The proof given here will follow the proof given in [4, Section 2] with only
minor modifications, which hopefully make a proof which was already really
well presented in [4] even easier to understand. So the mathematics presented
here was really done by [4]. The main idea is to estimate the ratios
$\frac{c_{e}}{c_{f}}$ for edges $e$ and $f$ which are incident on the same
vertex by comparing with a corresponding ratio of numbers of edge traversals
of the LERRW, under the assumption that the random walk is recurrent. We then
bound the estimated ratio as well as the error caused by the estimation to
conclude.

###  4.1 Estimating Conductance Ratios

The first step is to construct an estimate of conductance ratios. Our final
goal will be to bound the expectation of $c_{e}^{s}$ for any edge $e$. We
therefore choose an arbitrary directed edge $e\in\overrightarrow{E}$ to begin
with. Next, we will define a path from the starting vertex $v_{0}$ to $e$ and
estimate the conductance ratios along this path, which will result in an
estimate for $c_{e}$. The construction of the path is as follows: for the edge
$e=\left(\check{e},\hat{e}\right)$, we can find the directed edge $e^{\prime}$
through which $\check{e}$ was first reached by the LERRW (or the RWRE,
depending on your point of view). If $e$ is traversed before its corresponding
inverse $\overleftarrow{e}$, then $e^{\prime}\neq e$ as undirected edges.
Since $e^{\prime}$ must have been traversed before its inverse, by its
definition, it is possible to iterate this construction until the starting
vertex $v_{0}$ is reached. This results in a (random) path
$\gamma_{e}=\left(\ldots,e^{\prime\prime},e^{\prime},e\right)$ starting from
$v_{0}$ and ending with $e$ (the path can be a loop if $\hat{e}=v_{0}$). For a
deterministic path $\gamma$, we call $D_{\gamma}$ the event that for the last
edge $e$ of $\gamma$, we have $\gamma_{e}=\gamma$, and that $e$ is traversed
before $\overleftarrow{e}$.

For $e$ such that $e^{\prime}\neq\overleftarrow{e}$, we now estimate the ratio
$\frac{c_{e}}{c_{e^{\prime}}}$ (i.e. the ratio of the conductances of two
edges along one of the paths constructed above) by

$\displaystyle Q\left(e\right)$
$\displaystyle:=\frac{M_{e}}{M_{f}}\qquad\textrm{where
}f:=\overleftarrow{e^{\prime}},\qquad\textrm{an estimate for
}R\left(e\right):=\frac{c_{e}}{c_{e^{\prime}}}$ (4.1)

where $M_{e}$ counts the number of times the directed edge $e$ was crossed in
the right direction before the edge $f$ was crossed in the right direction by
the random walk, if $e$ is crossed before $f$. In this case, $M_{f}$ is set to
$1$. Otherwise, $M_{f}$ counts the number of times $f$ was crossed before $e$,
and $M_{e}$ is $1$. In other words, $M_{e}$ and $M_{f}$ count the numbers of
directed edge crossings of $e$ and $f$ until both edges have been traversed by
the random walk. Since both edges lead out of the same vertex, this can also
be seen as counting the number of departures from $\check{e}$ until both edges
were used.

$v_{0}$$\check{e}$$\hat{e}$$e$$e^{\prime}$$f$$e^{\prime\prime}$${\color[rgb]{0.890625,0.4453125,0.1328125}\definecolor[named]{pgfstrokecolor}{rgb}{0.890625,0.4453125,0.1328125}M_{f}}\;=$
number ofdepartures from $\check{e}$ along
${\color[rgb]{0.890625,0.4453125,0.1328125}\definecolor[named]{pgfstrokecolor}{rgb}{0.890625,0.4453125,0.1328125}f}$until
both $e$ and $f$
used${\color[rgb]{0,0.39453125,0.7421875}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.39453125,0.7421875}M_{e}}\;=$
number ofdepartures from $\check{e}$ along
${\color[rgb]{0,0.39453125,0.7421875}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.39453125,0.7421875}e}$until
both $e$ and $f$
used$\displaystyle{Q\left(e\right)=\frac{{\color[rgb]{0,0.39453125,0.7421875}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.39453125,0.7421875}M_{e}}}{{\color[rgb]{0.890625,0.4453125,0.1328125}\definecolor[named]{pgfstrokecolor}{rgb}{0.890625,0.4453125,0.1328125}M_{f}}}}$,
an estimate for
$\displaystyle{R\left(e\right)=\frac{c_{e}}{c_{e^{\prime}}}}$$\boldsymbol{\gamma}_{\boldsymbol{e}}=\left(e^{\prime\prime},e^{\prime},e\right)$
Figure 1: Estimating conductance ratios

We next define the deterministic set of simple paths (or loops, if one of the
endpoints of $e$ is $v_{0}$) $\Gamma_{e}$ as the set of paths which end with
$e$ or $\overleftarrow{e}$. So, $\Gamma_{e}$ is the set of possible values
which the random path $\gamma_{e}$ (or $\gamma_{\overleftarrow{e}}$, if
$\overleftarrow{e}$ is traversed before $e$) can take. We now have

$\displaystyle\mathbb{E}_{v_{0}}\left[c_{e}^{s}\right]=\sum_{\gamma\in\Gamma_{e}}\mathbb{E}_{v_{0}}\left[c_{e}^{s}\cdot\mathbbm{1}_{D_{\gamma}}\right]\leq\sum_{\gamma\in\Gamma_{e}}\mathbb{E}_{v_{0}}\left[\left(\frac{c_{e}}{c_{\gamma_{1}}}\right)^{s}\cdot\mathbbm{1}_{D_{\gamma}}\right]$

where $\gamma_{1}$ is the first edge of $\gamma$. Recall that we normalized
the environment such that $c_{v_{0}}=1$, so in particular, $c_{\gamma_{1}}\leq
1$ since $\gamma_{1}$ leads out of $v_{0}$.

One of the assumptions we started with was that we already know that the LERRW
is recurrent. This implies that $e$ will be visited a.s. and therefore the
partition into possible paths $\gamma\in\Gamma_{e}$ does indeed cover the
whole probability space. Furthermore, by Theorem 3.1 and [9], the conductances
in the random environment corresponding to the LERRW are uniquely defined and
we can therefore look at $\frac{c_{e}}{c_{\gamma_{1}}}$.

We now want to compare the estimated conductance ratios along the path
$\gamma_{e}$ with the real conductance ratios. If we fix a path $\gamma$
ending in $e$ and $D_{\gamma}$ occurs, then

$\displaystyle\frac{c_{e}}{c_{\gamma_{1}}}=\prod_{f\in\gamma,f\neq\gamma_{1}}R\left(f\right)=\underbrace{\prod_{f\in\gamma,f\neq\gamma_{1}}\frac{R\left(f\right)}{Q\left(f\right)}}_{\textrm{error}}\underbrace{\prod_{f\in\gamma,f\neq\gamma_{1}}Q\left(f\right)}_{\textrm{estimate}}$

By the Cauchy-Schwarz inequality, we have

$\displaystyle\mathbb{E}_{v_{0}}\left[\left(\frac{c_{e}}{c_{\gamma_{1}}}\right)^{s}\cdot\mathbbm{1}_{D_{\gamma}}\right]\leq\mathbb{E}_{v_{0}}\left[\prod_{f\in\gamma,f\neq\gamma_{1}}\left(\frac{R\left(f\right)}{Q\left(f\right)}\right)^{2s}\cdot\mathbbm{1}_{D_{\gamma}}\right]^{\frac{1}{2}}\mathbb{E}_{v_{0}}\left[\prod_{f\in\gamma,f\neq\gamma_{1}}Q\left(f\right)^{2s}\cdot\mathbbm{1}_{D_{\gamma}}\right]^{\frac{1}{2}}$

The above equation allows us to bound the expectation of the error introduced
by the estimate separately from the expectation of the estimate. The following
two sections will bound the two terms on the right hand side. Then, we will be
able to show exponential decay of the edge conductances in the distance to the
starting vertex for graphs on which the LERRW is recurrent, a result which can
subsequently actually be used to show recurrence of the LERRW itself.

###  4.2 Bounding the Error

######  Lemma 4.1 (Error Bound ([4, Lemma 7]))

Let $G$ be a graph, $v_{0}\in V$ the starting vertex, and
$a\in\left(0,\infty\right)$ such that the LERRW on $G$ with initial weights
equal to $a$ is recurrent. Then, for any $e\in E$, any $\gamma\in\Gamma_{e}$,
and any $s\in\left(0,1\right)$:

$\displaystyle\mathbb{E}_{v_{0}}\left[\prod_{f\in\gamma,f\neq\gamma_{1}}\left(\frac{R\left(f\right)}{Q\left(f\right)}\right)^{s}\cdot\mathbbm{1}_{D_{\gamma}}\right]\leq
C\left(s\right)^{\left|\gamma\right|-1}$

where $C\left(s\right)$ is a constant depending solely on $s$ and
$\left|\gamma\right|$ is the length of the path $\gamma$.

Note that the bound of the error given above shows that we have at most an
exponential increase of our error in the length of the path $\gamma$. The
corresponding bound of the estimated ratios will balance this potentially
exponentially increasing error.

###### Proof

$R$ and $Q$ depend in general on the random path $\gamma_{e}$ (which was
defined recursively as the path of first entrance edges in the section above).
For a deterministic path $\gamma$, we can define $R_{\gamma}$ and $Q_{\gamma}$
for edges $f\in\gamma,f\neq\gamma_{1}$ as we defined $R$ and $Q$ for the
random path: if $f\in\gamma$, and if $f^{\prime}\in\gamma$ is the preceding
edge in the path, then $R_{\gamma}\left(f\right)=c_{f}c_{f^{\prime}}^{-1}$,
and $Q_{\gamma}\left(f\right)$ is the ratio of exits from $\check{f}$ along
$f$ and $\overleftarrow{f^{\prime}}$ until both edges have been visited (see
Equation 4.1). We have, for fixed $\gamma$

$\displaystyle\mathbb{E}_{v_{0}}\left[\prod_{f\in\gamma,f\neq\gamma_{1}}\left(\frac{R\left(f\right)}{Q\left(f\right)}\right)^{s}\cdot\mathbbm{1}_{D_{\gamma}}\right]\leq\mathbb{E}_{v_{0}}\left[\prod_{f\in\gamma,f\neq\gamma_{1}}\left(\frac{R_{\gamma}\left(f\right)}{Q_{\gamma}\left(f\right)}\right)^{s}\right]$

This inequality holds since $R_{\gamma}\left(f\right)=R\left(f\right)$ and
$Q_{\gamma}\left(f\right)=Q\left(f\right)$ if $D_{\gamma}$ occurs. The
inequality is a crude bound but sufficient for our purposes.

We want to show a bound on the error of estimating the conductance ratios. It
is therefore necessary to look at the RWRE description of the random walk, and
we will now condition on a particular vector $\mathbf{c}$ of conductances
being chosen. We then show that for every such vector, the bound above holds,
and this will give the desired result. So from now on, assume we have
conductances $\mathbf{c}$. $R_{\gamma}\left(f\right)$ is then also a fixed
number, since it only depends on the conductances. The
$Q_{\gamma}\left(f\right)$, on the other hand, are independent for any two
different edges if we condition on the conductances $\mathbf{c}$. This is
because we just count directed exits from $\check{f}$, and we can couple these
with iid sequences of random variables $\left(Z_{n}^{v}\right)_{n\geq 1}$ for
every node $v$ where $Z_{n}^{v}$ takes values in the edges incident to node
$v$, and is distributed such that an edge $e$ appears with probability
$c_{e}\left(\sum_{f\ni v}c_{f}\right)^{-1}$. These $Z_{n}^{v}$ are iid for
every node, and independent for different nodes.

By the independence of the $Q_{\gamma}\left(f\right)$ (conditioned on
$\mathbf{c}$), we have

$\displaystyle\mathbb{E}_{v_{0}}\left[\prod_{f\in\gamma,f\neq\gamma_{1}}\left(\frac{R_{\gamma}\left(f\right)}{Q_{\gamma}\left(f\right)}\right)^{s}\mathrel{}\middle|\mathrel{}\mathbf{c}\right]$
$\displaystyle=\prod_{f\in\gamma,f\neq\gamma_{1}}\mathbb{E}_{v_{0}}\left[\left(\frac{R_{\gamma}\left(f\right)}{Q_{\gamma}\left(f\right)}\right)^{s}\mathrel{}\middle|\mathrel{}\mathbf{c}\right]$
$\displaystyle=\prod_{f\in\gamma,f\neq\gamma_{1}}\mathbb{E}_{v_{0}}\left[\left(\frac{c_{f}}{c_{f^{\prime}}}\cdot\frac{M_{\overleftarrow{f^{\prime}},\gamma}}{M_{f,\gamma}}\right)^{s}\mathrel{}\middle|\mathrel{}\mathbf{c}\right]$

where $f^{\prime}$ is the edge preceding $f$ in $\gamma$ and $M_{f,\gamma}$ is
defined as $M_{f}$ in Equation 4.1 but with the deterministic path $\gamma$
instead of the random path $\gamma_{e}$. To finish the proof, it is therefore
sufficient to show that, for any edge $f\in\gamma$ preceded by $f^{\prime}$,

$\displaystyle\mathbb{E}_{v_{0}}\left[\left(\frac{c_{f}}{c_{f^{\prime}}}\cdot\frac{M_{\overleftarrow{f^{\prime}},\gamma}}{M_{f,\gamma}}\right)^{s}\mathrel{}\middle|\mathrel{}\mathbf{c}\right]\leq
C\left(s\right)$

where $C\left(s\right)$ does not depend on the conductance vector $\mathbf{c}$
we condition on.

$v_{0}$$\check{f}=v$$\hat{f}$$f$$f^{\prime}$$e$$f^{\prime\prime}$${\color[rgb]{0.890625,0.4453125,0.1328125}\definecolor[named]{pgfstrokecolor}{rgb}{0.890625,0.4453125,0.1328125}M_{e,\gamma}}\;=$
number ofdepartures from $v$ along
${\color[rgb]{0.890625,0.4453125,0.1328125}\definecolor[named]{pgfstrokecolor}{rgb}{0.890625,0.4453125,0.1328125}e}$until
both $e$ and $f$
used${\color[rgb]{0,0.39453125,0.7421875}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.39453125,0.7421875}M_{f,\gamma}}\;=$
number ofdepartures from $v$ along
${\color[rgb]{0,0.39453125,0.7421875}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.39453125,0.7421875}f}$until
both $e$ and $f$
used$\displaystyle{Q_{\gamma}\left(f\right)=\frac{{\color[rgb]{0,0.39453125,0.7421875}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.39453125,0.7421875}M_{f,\gamma}}}{{\color[rgb]{0.890625,0.4453125,0.1328125}\definecolor[named]{pgfstrokecolor}{rgb}{0.890625,0.4453125,0.1328125}M_{e,\gamma}}}}$,
an estimate for
$\displaystyle{R_{\gamma}\left(f\right)=\frac{c_{f}}{c_{e}}}$$\boldsymbol{\gamma}=\left(f^{\prime\prime},f^{\prime},f\right)$
Figure 2: Estimating conductance ratios along a deterministic path $\gamma$

Write $v=\check{f}$, $e=\overleftarrow{f^{\prime}}$ (see Figure 2 for
reference). The law of $M_{e,\gamma}$ and $M_{f,\gamma}$ is determined by the
iid sequence $\left(Z_{n}^{v}\right)_{n\geq 1}$ (since we condition on
$\mathbf{c}$), and does not depend on other edges incident to $v$: it is only
relevant with which probability the two edges appear relative to each other in
the sequence. We can therefore assume w.l.o.g. that only $e$ and $f$ appear in
the sequence $Z_{n}^{v}$ with probabilities $p$ and $q=1-p$, respectively.
Then

$\displaystyle\mathbb{E}_{v_{0}}\left[\left(\frac{c_{f}}{c_{e}}\cdot\frac{M_{e,\gamma}}{M_{f,\gamma}}\right)^{s}\mathrel{}\middle|\mathrel{}\mathbf{c}\right]$
$\displaystyle=\left(\frac{c_{f}}{c_{e}}\right)^{s}\left(\sum_{k\geq
1}k^{s}\cdot\mathbb{P}_{v_{0}}\left[k\textrm{ exits from }v\textrm{ along
}e,\textrm{ then exit }v\textrm{ along }f\right]\right.$
$\displaystyle\hphantom{=\left(\frac{c_{f}}{c_{e}}\right)^{s}(}\left.+\sum_{k\geq
1}k^{-s}\cdot\mathbb{P}_{v_{0}}\left[k\textrm{ exits from }v\textrm{ along
}f,\textrm{ then exit }v\textrm{ along }e\right]\right)$
$\displaystyle=\left(\frac{q}{p}\right)^{s}\left(\sum_{k\geq
1}k^{s}p^{k}q+\sum_{k\geq 1}k^{-s}q^{k}p\right)$
$\displaystyle\overset{\circledast}{\leq}\left(\frac{q}{p}\right)^{s}\left(q^{-s}p+C\left(s\right)qp^{s}\right)=p^{1-s}+C\left(s\right)q^{1+s}\leq
2C\left(s\right)$

Since the bound is independent of $p$ and $q$ and thereby independent of the
choice of the conductances $\mathbf{c}$, this completes the proof, up to
showing $\circledast$. Note that the bound can be improved, dependent on the
value of $s$. We show $\circledast$ using the following observations. If
$X\sim\operatorname{Geo}_{\geq 0}\left(q\right)$ is a random variable with
geometric distribution of parameter $q$, i.e.
$\mathbb{P}\left[X=k\right]=p^{k}q$, then we can write

$\displaystyle\mathbb{E}\left[X^{s}\right]=\sum_{k\geq 1}k^{s}p^{k}q\leq
pq^{-s}$ $\displaystyle\iff\mathbb{E}\left[\left(qX\right)^{s}\right]\leq p$
(4.2)

Now, proving that the inequality in Equation 4.2 holds will show the bound on
the first sum in $\circledast$. Note that the function $f\left(s\right)=x^{s}$
is convex for arbitrary choice of $x>0$. Therefore,
$g\left(s\right)=\mathbb{E}\left[\left(qX\right)^{s}\right]$ is convex in $s$.
As $X$ takes values in the integers, we have that
$\mathbb{E}\left[\left(qX\right)^{s}\right]=q^{s}\mathbb{E}\left[X^{s}\right]\leq\mathbb{E}\left[X\right]<\infty$
for $s\in\left(0,1\right)$. By dominated convergence, $g\left(s\right)$ is
therefore continuous in $s$, and can be continued continuously to the interval
$s\in\left[0,1\right]$. For $s=1$, we have
$g\left(1\right)=q\mathbb{E}\left[X\right]=q\cdot\frac{p}{q}=p$, and for
$s=0$, we have

$\displaystyle\lim_{s\to 0}g\left(s\right)=\lim_{s\to
0}\mathbb{E}\left[\left(qX\right)^{s}\right]=\mathbb{E}\left[\lim_{s\to
0}\left(qX\right)^{s}\right]=\mathbb{E}\left[\mathbbm{1}_{\left\\{X>0\right\\}}\right]=p$

By convexity of $g$, we conclude that $g\left(s\right)\leq p$ for all
$s\in\left(0,1\right)$, which proves Equation 4.2.

For bounding the second sum, let $X\sim\operatorname{Geo}_{\geq
1}\left(p\right)$ be a random variable with geometric distribution of
parameter $p$, but which takes values in
$\mathbb{N}\setminus\left\\{0\right\\}$, so
$\mathbb{P}\left[X=k\right]=q^{k-1}p$ where $k\geq 1$. Then we can write

$\displaystyle q\cdot\mathbb{E}\left[X^{-s}\right]=q\cdot\sum_{k\geq
1}k^{-s}q^{k-1}p=\sum_{k\geq 1}k^{-s}q^{k}p\leq C\left(s\right)qp^{s}$
$\displaystyle\iff\mathbb{E}\left[\left(pX\right)^{-s}\right]\leq
C\left(s\right)$ (4.3)

Now, $g\left(p\right)=\mathbb{E}\left[\left(pX\right)^{-s}\right]$ is
decreasing in $p$ (to see this, note that
$\mathbb{E}\left[\left(pX\right)^{-s}\right]=\frac{p^{1-s}}{1-p}\cdot\operatorname{Li}_{s}\left(1-p\right)$
where $\operatorname{Li}$ denotes the polylogarithm, derive:
https://bit.ly/3BOmLjP, and analyze the derivative: https://bit.ly/3RVn5CA),
so it is sufficient to show that $\lim_{p\to
0}g\left(p\right)=:C\left(s\right)$ exists and is finite. Note that for $p\to
0$, $pX$ converges in distribution to a random variable $Y$ which is
$\operatorname{Exp}\left(1\right)$-distributed (we have that
$\mathbb{P}\left[pX>t\right]\to e^{-t}$ for $p\to 0$). Therefore, $\lim_{p\to
0}g\left(p\right)=\mathbb{E}\left[Y^{-s}\right]=\Gamma\left(1-s\right)<\infty$
for $s\in\left(0,1\right)$. Thus, we can choose
$C\left(s\right)=\Gamma\left(1-s\right)$ in Equation 4.3.

###  4.3 Bounding the Estimate

######  Lemma 4.2 (Estimate Bound ([4, Lemma 8]))

Let $G$ be a graph with degree at most $K$, $v_{0}\in V$ the starting vertex,
and $a\in\left(0,\infty\right)$ such that the LERRW on $G$ with initial
weights equal to $a$ is recurrent. Then, for any $e\in E$, any
$\gamma\in\Gamma_{e}$, and any $s\in\left(0,\frac{1}{2}\right)$:

$\displaystyle\mathbb{E}_{v_{0}}\left[\prod_{f\in\gamma,f\neq\gamma_{1}}Q\left(f\right)^{s}\cdot\mathbbm{1}_{D_{\gamma}}\right]\leq\left(C\left(s,K\right)a\right)^{\left|\gamma\right|-1}$

where $C\left(s\right)$ is a constant depending solely on $s$ and $K$.

Choosing $a$ small enough, the bound above shows that the estimated ratios
decrease exponentially and fast enough to balance the potential error caused
by the estimation given in 4.1.

###### Proof

The idea of the proof is to find iid random variables
$\overline{Q}\left(f\right)$ which stochastically dominate the variables
$Q\left(f\right)$ on all edges of the deterministic path $\gamma$, provided
that $D_{\gamma}$ occurs. It is then much easier to bound the expectation of
the random variables $\overline{Q}\left(f\right)$. We start by fixing $\gamma$
and now want to define $\overline{Q}\left(f\right)$ such that
$Q\left(f\right)\leq\overline{Q}\left(f\right)$ for all
$f\in\gamma,f\neq\gamma_{1}$ on the event $D_{\gamma}$.

For every such edge $f$, we define two independent series of Bernoulli random
variables (also independent of the corresponding series for different edges)
$\left(Y_{j}\right)_{j\geq 0}$ and $\left(Y_{j}^{\prime}\right)_{j\geq 0}$:

$\displaystyle\mathbb{P}\left[Y_{j}=1\right]=\frac{a}{j+1+2a}=1-\mathbb{P}\left[Y_{j}=0\right]\qquad\mathbb{P}\left[Y_{j}^{\prime}=1\right]=\frac{1+a}{2j+1+Ka}=1-\mathbb{P}\left[Y_{j}^{\prime}=0\right]$

Intuitively, and up to some technical details, these variables are used as
follows. Recall that $f^{\prime}$ was the edge through which $\check{f}=v$ was
first reached (which is the edge preceding $f$ in $\gamma$ on the event
$D_{\gamma}$) and we set again $e=\overleftarrow{f^{\prime}}$. We want to
bound $Q\left(f\right)=\frac{M_{f}}{M_{e}}$, hence we want to upper bound
$M_{f}$, the number of exits along $f$ until both edges were used, and we want
to lower bound $M_{e}$. First, $Y_{0}^{\prime}=1$ represents the event that on
the first visit to $v$, we depart along $e$, and sometimes also if
$Y_{0}^{\prime}=0$. $Y_{0}^{\prime}=1$ is thus a lower bound for the departure
along $e$. Now,

  * •

if $Y_{0}^{\prime}=0$, i.e. if the first departure was not necessarily along
$e$, and $e$ was not used yet: then, for $n\geq 1$, on the $n$-th visit to
$v$, we will couple the random walk with the variables $Y^{\prime}$ such that
we depart along $e$ if $Y_{n-1}^{\prime}=1$, and sometimes also if
$Y_{n-1}^{\prime}=0$. $Y_{n-1}^{\prime}=1$ lower bounds the event that $e$ is
crossed.

  * •

if $Y_{0}^{\prime}=1$, i.e. if the first departure was along $e$, and if $f$
was not used yet: then, for $n\geq 1$, on the $n$-th visit to $v$ where $v$ is
left along $f$ or $e$, we will couple the random walk with the variables $Y$
such that we depart along $e$ if $Y_{n-1}=0$, and sometimes also if
$Y_{n-1}=1$. $Y_{n-1}=1$ upper bounds the event that $f$ is crossed.

We now set

$\displaystyle\overline{Q}\left(f\right)$
$\displaystyle=\frac{\overline{M}_{f}}{\overline{M}_{e}}\quad\textrm{where}$
$\displaystyle\overline{M}_{f}$ $\displaystyle=\min\left\\{j\geq
1:Y_{j}^{\prime}=1\right\\}\;\;\textrm{ and
}\;\;\overline{M}_{e}=1\;\;\textrm{ if }\;\;Y_{0}^{\prime}=0$
$\displaystyle\overline{M}_{e}$ $\displaystyle=\min\left\\{j\geq
1:Y_{j}=1\right\\}\;\;\textrm{ and }\;\;\overline{M}_{f}=1\;\;\textrm{ if
}\;\;Y_{0}^{\prime}=1$

First exit not necessarily along $e$,
$Y_{0}^{\prime}=0$$\check{f}=v$$\hat{f}$$f$$f^{\prime}$$e$Weights at the
$n$-th visit to
$v$:${\color[rgb]{0.890625,0.4453125,0.1328125}\definecolor[named]{pgfstrokecolor}{rgb}{0.890625,0.4453125,0.1328125}z\left(t,e\right)}+a\geq
1+a$?$z\left(t,f\right)+a=a$Total weight of adjacent
edges:$2n-1+\deg\left(v\right)a\leq 2n-1+Ka$$\mathbb{P}\left[\textrm{exit
along
}e\right]\geq\frac{1+a}{2n-1+Ka}=\mathbb{P}\left[Y_{n-1}^{\prime}=1\right]$

First exit along $e$,
$Y_{0}^{\prime}=1$$\check{f}=v$$\hat{f}$$f$$f^{\prime}$$e$Weights at the
$n$-th time at which$v$ is exited along $e$ or
$f$:?$z\left(t,f\right)+a=a$Total weight of edges $e$ and
$f$:$z\left(t,e\right)+2a\geq n+2a$$\mathbb{P}\left[\textrm{exit along
}f\right]\leq\frac{a}{n+2a}=\mathbb{P}\left[Y_{n-1}=1\right]$

Figure 3: Bounding $Q$ with the help of Bernoulli random variables

The figure above demonstrates why the indicated coupling is possible. We are
in the situation where $v$ has not yet been exited along both $e$ and $f$. On
the left, the first exit from $v$ was not necessarily along $e$, and we want
to lower bound the probability to exit along $e$ on the $n$-th visit to $v$.
$v$ was first reached by $f^{\prime}$, so the weight of the edge $e$ must
already be at least $1+a$, which yields the desired lower bound of
$\mathbb{P}\left[Y_{n-1}^{\prime}=1\right]$. On the right, the first exit from
$v$ was along $e$, and we want to upper bound the probability to exit along
$f$, if we already know that we exit along one of the two edges $e$ and $f$.
Since we look at the situation that not both edges have been used yet, $f$
cannot have been used yet (also not in reverse direction, at least not on the
event $D_{\gamma}$), so its weight is still $a$. The weight of $e$, on the
other hand must be at least $n+a$ if this is the $n$-th time at which we exit
along one of these two edges (it could be higher, since $e$ might also have
been used in the reverse direction). This yields the upper bound of
$\mathbb{P}\left[Y_{n-1}=1\right]$.

The preceding paragraphs hopefully gave enough details to intuitively
understand how the random walk and the variables $Y$ and $Y^{\prime}$ should
be coupled, and why $\overline{Q}$ is an upper bound for $Q$. If not, the
technical details will be given at the end of the proof. Assuming that we know
that $Q\left(f\right)\leq\overline{Q}\left(f\right)$ for all
$f\in\gamma,f\neq\gamma_{1}$ on the event $D_{\gamma}$, we can now finish the
prove as follows. Let $s\in\left(0,\frac{1}{2}\right)$. We have
$\mathbb{E}\left[\overline{Q}\left(f\right)^{s}\right]=\mathbb{E}\left[\overline{Q}\left(f\right)^{s}\mathbbm{1}_{Y_{0}^{\prime}=0}\right]+\mathbb{E}\left[\overline{Q}\left(f\right)^{s}\mathbbm{1}_{Y_{0}^{\prime}=1}\right]$.

If $Y_{0}^{\prime}=0$, then $\overline{M}_{e}=1$. In addition,

$\displaystyle\mathbb{P}\left[Y_{0}^{\prime}=0,\overline{M}_{f}=n\right]$
$\displaystyle=\mathbb{P}\left[Y_{0}^{\prime}=0\right]\cdot\mathbb{P}\left[Y_{n}^{\prime}=1\right]\cdot\prod_{j=1}^{n-1}\mathbb{P}\left[Y_{j}^{\prime}=0\right]$
$\displaystyle=\underbrace{\frac{\left(K-1\right)a}{1+Ka}}_{\leq\frac{Ka}{1+Ka}}\cdot\underbrace{\frac{1+a}{2n+1+Ka}}_{\leq\frac{1+Ka}{2n}}\cdot\prod_{j=1}^{n-1}\left(1-\frac{1+a}{2j+1+Ka}\right)$
$\displaystyle\leq\frac{Ka}{2n}\cdot\prod_{j=1}^{n-1}\left(1-\frac{1+a}{2j+1+Ka}\right)$

For the terms in the product, we have the following estimate, since $a>0$:

$\displaystyle\frac{1+a}{2j+1+Ka}$
$\displaystyle\geq\min\left\\{\frac{1}{2j+1},\frac{a}{Ka}\right\\}=\min\left\\{\frac{1}{2j+1},\frac{1}{K}\right\\}$
$\displaystyle\implies 1-\frac{1+a}{2j+1+Ka}$
$\displaystyle\leq\exp\left(-\frac{1+a}{2j+1+Ka}\right)\leq\exp\left(-\min\left\\{\frac{1}{2j+1},\frac{1}{K}\right\\}\right)$

Note that
$-\frac{1}{2j+1}=-\frac{1}{2j}+\frac{1}{j\left(4j+2\right)}\leq-\frac{1}{2j}+\frac{1}{4j^{2}}$.
Therefore,

$\displaystyle\prod_{j=1}^{n-1}\left(1-\frac{1+a}{2j+1+Ka}\right)$
$\displaystyle\leq\exp\left(-\sum_{j=1}^{n-1}\frac{1}{2j}+\sum_{j=1}^{n-1}\frac{1}{4j^{2}}+C_{1}\left(K\right)\right)$

where $0<C_{1}\left(K\right)<\infty$ accounts for the fact that for only
finitely many $j\in\mathbb{N}$, we have that
$\min\left\\{\frac{1}{2j+1},\frac{1}{K}\right\\}=\frac{1}{K}$. We conclude,
since $\sum_{j=1}^{\infty}\frac{1}{4j^{2}}<\infty$,

$\displaystyle\prod_{j=1}^{n-1}\left(1-\frac{1+a}{2j+1+Ka}\right)$
$\displaystyle\leq\exp\left(-\sum_{j=1}^{n}\frac{1}{2j}+C_{2}\left(K\right)\right)\leq
e^{C_{2}\left(K\right)}\exp\left(-\frac{1}{2}\ln\left(n\right)\right)$

We can therefore conclude

$\displaystyle\mathbb{P}\left[Y_{0}^{\prime}=0,\overline{M}_{f}=n\right]$
$\displaystyle\leq\frac{Ka}{2n}\cdot e^{C_{2}\left(K\right)}\cdot
n^{-\frac{1}{2}}=C\left(K\right)an^{-\frac{3}{2}}$

This yields, noting that $s\in\left(0,\frac{1}{2}\right)$ and therefore
$s-\frac{3}{2}<-1$:

$\displaystyle\mathbb{E}\left[\overline{Q}\left(f\right)^{s}\mathbbm{1}_{Y_{0}^{\prime}=0}\right]$
$\displaystyle=\sum_{n\geq
1}n^{s}\mathbb{P}\left[Y_{0}^{\prime}=0,\overline{M}_{f}=n\right]$
$\displaystyle\leq\sum_{n\geq
1}C\left(K\right)an^{s-\frac{3}{2}}=C\left(K\right)a\underbrace{\sum_{n\geq
1}n^{s-\frac{3}{2}}}_{<\infty}\leq C\left(s,K\right)a$

If $Y_{0}^{\prime}=1$, then $\overline{M}_{f}=1$. In addition,

$\displaystyle\mathbb{P}\left[Y_{0}^{\prime}=1,\overline{M}_{e}=n\right]$
$\displaystyle\leq\mathbb{P}\left[Y_{n}=1\right]=\frac{a}{n+1+2a}\leq\frac{a}{n}$
$\displaystyle\mathbb{E}\left[\overline{Q}\left(f\right)^{s}\mathbbm{1}_{Y_{0}^{\prime}=1}\right]$
$\displaystyle=\sum_{n\geq
1}n^{-s}\mathbb{P}\left[Y_{0}^{\prime}=1,\overline{M}_{e}=n\right]\leq\sum_{n\geq
1}an^{-1-s}<C\left(s\right)a$

Thus (recall that the random variables $\overline{Q}$ were constructed to be
iid),

$\displaystyle\mathbb{E}_{v_{0}}\left[\prod_{f\in\gamma,f\neq\gamma_{1}}Q\left(f\right)^{s}\cdot\mathbbm{1}_{D_{\gamma}}\right]$
$\displaystyle\leq\mathbb{E}_{v_{0}}\left[\prod_{f\in\gamma,f\neq\gamma_{1}}\overline{Q}\left(f\right)^{s}\cdot\mathbbm{1}_{D_{\gamma}}\right]\leq\mathbb{E}_{v_{0}}\left[\prod_{f\in\gamma,f\neq\gamma_{1}}\overline{Q}\left(f\right)^{s}\right]$
$\displaystyle=\prod_{f\in\gamma,f\neq\gamma_{1}}\mathbb{E}_{v_{0}}\left[\overline{Q}\left(f\right)^{s}\right]$
$\displaystyle=\prod_{f\in\gamma,f\neq\gamma_{1}}\left(\mathbb{E}\left[\overline{Q}\left(f\right)^{s}\mathbbm{1}_{Y_{0}^{\prime}=0}\right]+\mathbb{E}\left[\overline{Q}\left(f\right)^{s}\mathbbm{1}_{Y_{0}^{\prime}=1}\right]\right)$
$\displaystyle\leq\left(C\left(s,K\right)a\right)^{\left|\gamma\right|-1}$

This finishes the proof up to the technical details of the coupling of the
random variables $Y,Y^{\prime}$ and the domination of $Q$ by $\overline{Q}$.

The intuition for how the random variables $Y,Y^{\prime}$ should be coupled
with the LERRW was already given in Figure 3: the events $Y=1$ and
$Y^{\prime}=1$ upper and lower bound the events that a certain edge in the
deterministic path $\gamma$ (which was fixed at the beginning of the proof) is
crossed. We now give the details of the coupling by constructing the LERRW
depending on the values taken by $Y,Y^{\prime}$, and some additional
randomness. If the random walker already did $t$ steps and is at vertex $v$,
then the LERRW proceeds as follows ($v\in\gamma$ shall denote that $v$ is in
the interior of the path $\gamma$, i.e. not one of its endpoints):

  * •

If $v\notin\gamma$, then the next edge is chosen as always in the LERRW:
according to the current reinforced edge weights after the first $t$ steps.
The choice of edge is independent of the variables $Y,Y^{\prime}$.

  * •

If $v\in\gamma$ and the first $t$ steps of the LERRW show that $D_{\gamma}$
does not occur, then, as in the previous case, the next edge is chosen
according to the edge weights independently of $Y,Y^{\prime}$. We can ignore
the values of the variables $Y,Y^{\prime}$ here because we only claimed
$Q\leq\overline{Q}$ if $D_{\gamma}$ occurs. The first $t$ steps of the LERRW
are inconsistent with $D_{\gamma}$ if an edge in $\gamma$ is traversed only
after its inverse or if the first arrival to some node in $\gamma$ was not
through the preceding edge in $\gamma$.

  * •

If $v\in\gamma$ and the value of $Q$ is already determined by the first $t$
steps of the LERRW, then we again ignore $Y,Y^{\prime}$. By $Q$ being
determined we mean that $v=\check{f}$ with $f\in\gamma$ and both $f$ as well
as $e=\overleftarrow{f^{\prime}}$ have already been traversed.

In all remaining cases, we thus have that the first $t$ steps of the LERRW are
are consistent with $D_{\gamma}$ occurring, and that $v\in\gamma$, i.e.
$v=\check{f}$ with $\gamma_{1}\neq f\in\gamma$. Again, call
$e=\overleftarrow{f^{\prime}}$. As we are not in the last case, we have that
$f$ and $e$ have not both been traversed yet. The following cases remain:

  * •

The walker is at $v$ for the first time. All incident edges thus have weight
$a$, except for $e$, which has weight $1+a$. The probability to take $e$ is
$\frac{1+a}{1+\deg\left(v\right)a}\geq\frac{1+a}{1+Ka}=\mathbb{P}\left[Y_{0}^{\prime}=1\right]$.
The LERRW will be coupled as follows: whenever $Y_{0}^{\prime}=1$, the walk
exits along $e$, and sometimes also if $Y_{0}^{\prime}=0$.

  * •

Later visits to $v$, $Y_{0}^{\prime}=0$ (the walk did not necessarily exit
along $e$ after the first visit). If $v$ is visited for the $n$-th time, then
the weight of $e$ is still at least $1+a$, and the total weight of all
incident edges is $2n-1+\deg\left(v\right)a$. The probability to take $e$ is
therefore

$\displaystyle\frac{z\left(t,e\right)+a}{2n-1+\deg\left(v\right)a}\geq\frac{1+a}{2n-1+Ka}=\mathbb{P}\left[Y_{n-1}^{\prime}=1\right]$

where $z\left(t,e\right)$ was the number of undirected traversals of $e$ up to
time $t$. The LERRW will now be coupled such that it takes $e$ if
$Y_{n-1}^{\prime}=1$, and sometimes also if $Y_{n-1}^{\prime}=0$.

  * •

Later visits to $v$, $Y_{0}^{\prime}=1$ (the walk exited along $e$ after the
first visit). $f$ has not been traversed yet since not both $f$ and $e$ have
been traversed already. As the first $t$ steps are consistent with
$D_{\gamma}$, $\overleftarrow{f}$ has also not been traversed yet, and
therefore, the weight of $f$ is $a$. We now decide, independently of
$Y,Y^{\prime}$ and with probabilities corresponding to the current edge
weights, whether one of the edges $f,e$ will be used or not. In the latter
case, the variables $Y,Y^{\prime}$ are ignored again. If $f$ or $e$ is used,
and this happens for the $n$-th time, then $z\left(t,e\right)\geq n$ since $f$
was not traversed yet, and since $e$ was also traversed in the other direction
at least once. The probability to choose $f$ from $f,e$ is

$\displaystyle\frac{a}{z\left(t,e\right)+2a}\leq\frac{a}{n+2a}=\mathbb{P}\left[Y_{n-1}=1\right]$

We couple the LERRW such that if $Y_{n-1}=0$, then $e$ is chosen, and
sometimes also if $Y_{n-1}=1$.

To finish the proof, we give some details on why
$Q\left(f\right)\leq\overline{Q}\left(f\right)$ on $D_{\gamma}$ (fix some edge
$\gamma_{1}\neq f\in\gamma$ with the usual notation). Hence we assume that
$D_{\gamma}$ occurs.

  * •

If $Y_{0}^{\prime}=0$ (the walk did not necessarily exit along $e$ after the
first visit), then only the variables $Y^{\prime}$ are relevant. At every
visit to $v$ (until $e$ is used), one variable $Y^{\prime}$ is considered. By
the coupling given above, $e$ is used at the latest when $Y_{n-1}^{\prime}=1$
for the first time, during the $n$-th visit to $v$. At this point, $f$ can
have been taken at most $n-1$ times. We have

$\displaystyle Q\left(f\right)\leq M_{f}\leq
n-1=\overline{M}_{f}=\overline{Q}\left(f\right)$

  * •

If $Y_{0}^{\prime}=1$ (the walk exited along $e$ after the first visit), then
only the variables $Y$ are relevant. At every visit to $v$ where $f$ or $e$ is
used, one variable $Y$ is considered. $f$ is used at the earliest when
$Y_{n-1}=1$ for the first time, during the $n$-th visit where one of $f,e$ is
used. At this point, $e$ will have been taken at least $n-1$ times. We have

$\displaystyle Q\left(f\right)$
$\displaystyle=\frac{1}{M_{e}}\leq\frac{1}{n-1}=\frac{1}{\overline{M}_{e}}=\overline{Q}\left(f\right)$

###  4.4 Proof of Recurrence

Before we arrive at the final result, we are now able to finish the last
intermediate step:

######  Theorem 4.3 (Exponential Conductance Decay ([4, Theorem 2]))

Let $G$ be a graph with degree at most $K$ such that the LERRW on $G$ is
recurrent for any choice of initial weights, let $v_{0}\in V$ be the starting
vertex, and let $s\in\left(0,\frac{1}{4}\right)$. Then, there is some
$a_{0}>0$, depending on $s$ and $K$, such that for initial weights
$a\in\left(0,a_{0}\right)$ we have

$\displaystyle\mathbb{E}_{v_{0}}\left[c_{e}^{s}\right]\leq
2K\left(C\left(s,K\right)\sqrt{a}\right)^{\operatorname{dist}\left(v_{0},e\right)}$

where $C\left(s,K\right)$ solely depends on $K$ and $s$.

###### Proof

We have

$\displaystyle\mathbb{E}_{v_{0}}\left[c_{e}^{s}\right]$
$\displaystyle=\sum_{\gamma\in\Gamma_{e}}\mathbb{E}_{v_{0}}\left[c_{e}^{s}\cdot\mathbbm{1}_{D_{\gamma}}\right]\leq\sum_{\gamma\in\Gamma_{e}}\mathbb{E}_{v_{0}}\left[\left(\frac{c_{e}}{c_{\gamma_{1}}}\right)^{s}\cdot\mathbbm{1}_{D_{\gamma}}\right]$
$\displaystyle\overset{\textrm{CSI}}{\leq}\sum_{\gamma\in\Gamma_{e}}\mathbb{E}_{v_{0}}\left[\prod_{f\in\gamma,f\neq\gamma_{1}}\left(\frac{R\left(f\right)}{Q\left(f\right)}\right)^{2s}\cdot\mathbbm{1}_{D_{\gamma}}\right]^{\frac{1}{2}}\mathbb{E}_{v_{0}}\left[\prod_{f\in\gamma,f\neq\gamma_{1}}Q\left(f\right)^{2s}\cdot\mathbbm{1}_{D_{\gamma}}\right]^{\frac{1}{2}}$
$\displaystyle\overset{\circledast}{\leq}\sum_{\gamma\in\Gamma_{e}}\left(C\left(2s\right)^{\left|\gamma\right|-1}\right)^{\frac{1}{2}}\left(\left(C\left(2s,K\right)a\right)^{\left|\gamma\right|-1}\right)^{\frac{1}{2}}$
$\displaystyle=\sum_{\gamma\in\Gamma_{e}}\left(\vphantom{C\left(2s,K\right)^{\frac{1}{2}}\sqrt{a}}\right.\underbrace{C\left(2s\right)^{\frac{1}{2}}C\left(2s,K\right)^{\frac{1}{2}}}_{=:C_{0}}\left.\vphantom{C\left(2s,K\right)^{\frac{1}{2}}}\sqrt{a}\right)^{\left|\gamma\right|-1}$

where $\circledast$ holds by 4.1 and 4.2. Now, choose $a_{0}$ such that
$KC_{0}\sqrt{a_{0}}=\frac{1}{2}$ ( 1). Then, for $a<a_{0}$ ( 2), we have,
since any $\gamma\in\Gamma_{e}$ has length at least
$\left|\gamma\right|=\operatorname{dist}\left(v_{0},e\right)+1$ ( 3), and
since there are at most $K^{l}$ paths of length $l$ ( 4):

$\displaystyle\mathbb{E}_{v_{0}}\left[c_{e}^{s}\right]$
$\displaystyle\leq\sum_{\gamma\in\Gamma_{e}}\left(C_{0}\sqrt{a}\right)^{\left|\gamma\right|-1}\overset{\textrm{
\leavevmode\hbox to11.37pt{\vbox
to11.37pt{\pgfpicture\makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{3}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}\vphantom{X_{\left(k\right)}}}{=}\sum_{l\geq\operatorname{dist}\left(v_{0},e\right)+1}\sum_{\gamma\in\Gamma_{e},\left|\gamma\right|=l}\left(C_{0}\sqrt{a}\right)^{l-1}$
$\displaystyle\overset{\textrm{ \leavevmode\hbox to11.37pt{\vbox
to11.37pt{\pgfpicture\makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{4}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{\leq}\sum_{l\geq\operatorname{dist}\left(v_{0},e\right)+1}K\cdot\left(KC_{0}\sqrt{a}\right)^{l-1}=K\cdot\left(KC_{0}\sqrt{a}\right)^{\operatorname{dist}\left(v_{0},e\right)}\cdot\sum_{l\geq
0}\left(KC_{0}\sqrt{a}\right)^{l}$ $\displaystyle\overset{\textrm{
\leavevmode\hbox to11.37pt{\vbox
to11.37pt{\pgfpicture\makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} \leavevmode\hbox
to11.37pt{\vbox to11.37pt{\pgfpicture\makeatletter\hbox{\hskip
5.68657pt\lower-5.68657pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{<}K\cdot\left(KC_{0}\sqrt{a}\right)^{\operatorname{dist}\left(v_{0},e\right)}\cdot\underbrace{\sum_{l\geq
0}\left(\frac{1}{2}\right)^{l}}_{2}=2K\left(KC_{0}\sqrt{a}\right)^{\operatorname{dist}\left(v_{0},e\right)}$

We can now finally prove the result we are actually interested in:

######  Theorem 4.4 (Recurrence on Bounded Degree Graphs ([4, Theorem 1]))

Let $K\in\mathbb{N}_{\geq 1}$. Then, there exists $a_{0}>0$ such that if the
graph $G$ has degree at most $K$, then the LERRW on $G$ with initial weights
set to $a\in\left(0,a_{0}\right)$ is recurrent. The corresponding RWRE is a.s.
positive recurrent, but this does not necessarily imply that the expected
return time to the starting vertex is finite.

###### Proof

The idea is to apply Theorem 4.3 to the LERRW on finite balls of the infinite
graph $G$. Call the starting vertex $v_{0}$ and let
$B_{R}\left(v_{0}\right):=\left\\{v\in
V:\operatorname{dist}\left(v_{0},v\right)\leq R\right\\}$ be the set of
vertices of distance at most $R$ to the starting vertex. Consider the LERRW
$X^{\left(R\right)}$ on the finite ball $B_{R}\left(v_{0}\right)$. Since
$B_{R}\left(v_{0}\right)$ is finite, $X^{\left(R\right)}$ is recurrent for any
choice of initial weights, and Theorem 4.3 is applicable. By Theorem 3.1,
$X^{\left(R\right)}$ is equal in law to a RWRE with random conductances
$\mathbf{c}^{\left(R\right)}=\left(c_{e}^{\left(R\right)}\right)_{e\in
B_{R}\left(v_{0}\right)}$. Denote the mixing measure (giving the distribution
of $\mathbf{c}^{\left(R\right)}$) by $\mu^{\left(R\right)}$. The measures
$\mu^{\left(R\right)}$ are a sequence of measures on the set of possible
conductance vectors.

The following calculation will, next to other results, show that for fixed
initial weights $a$, the measures $\mu^{\left(R\right)}$ are tight (see end of
the proof). So, by Prokhorov’s theorem, there is a subsequence converging to
some measure $\mu$. The first $R$ steps of the LERRW on the whole graph $G$
are equal in law to the first $R$ steps of the LERRW on
$B_{R}\left(v_{0}\right)$. So the LERRW on $G$ has the same distribution as a
RWRE with mixing measure $\mu$.

Fix $s\in\left(0,\frac{1}{4}\right)$ and let $e\in B_{R}\left(v_{0}\right)$ be
an edge in the finite ball of radius $R$. By Markov’s inequality, and by
Theorem 4.3, for initial weights $a$ small enough, we have

$\displaystyle\mu^{\left(R\right)}\left(c_{e}^{\left(R\right)}>Q\right)=\mu^{\left(R\right)}\left(\left(c_{e}^{\left(R\right)}\right)^{s}>Q^{s}\right)\leq\frac{\mathbb{E}\left[\left(c_{e}^{\left(R\right)}\right)^{s}\right]}{Q^{s}}\leq\frac{2K\left(C\left(s,K\right)\sqrt{a}\right)^{\operatorname{dist}\left(v_{0},e\right)}}{Q^{s}}$

Choose $Q=\left(2K\right)^{-\operatorname{dist}\left(v_{0},e\right)}$ and note
that there are at most $K^{l+1}$ edges at distance $l$ from $v_{0}$. Then

$\displaystyle\begin{split}&\mu^{\left(R\right)}\left(\exists e\in
B_{R}\left(v_{0}\right):\operatorname{dist}\left(v_{0},e\right)=l\textrm{ and
}c_{e}^{\left(R\right)}>\left(2K\right)^{-l}\right)\\\ &\leq\sum_{e\in
B_{R}\left(v_{0}\right):\operatorname{dist}\left(v_{0},e\right)=l}\mu^{\left(R\right)}\left(c_{e}^{\left(R\right)}>\left(2K\right)^{-l}\right)\\\
&\leq
K^{l+1}2K\left(C\left(s,K\right)\sqrt{a}\right)^{l}\left(2K\right)^{sl}=2K^{2}\left(2^{s}K^{1+s}C\left(s,K\right)\sqrt{a}\right)^{l}\end{split}$
(4.4)

If we now choose $a_{0}$ such that
$2^{s}K^{1+s}C\left(s,K\right)\sqrt{a_{0}}\leq\frac{1}{2}$ and such that
$a_{0}$ is smaller than the bound given by Theorem 4.3, then, for intital
weights $a\in\left(0,a_{0}\right)$,

$\displaystyle\mu^{\left(R\right)}\left(\exists e\in
B_{R}\left(v_{0}\right):\operatorname{dist}\left(v_{0},e\right)=l\textrm{ and
}c_{e}^{\left(R\right)}>\left(2K\right)^{-l}\right)<2K^{2}\left(\frac{1}{2}\right)^{l}=K^{2}2^{1-l}$

This bound is uniform in $R$, so it holds for all measures
$\mu^{\left(R\right)}$, and in consequence also for the limit $\mu$ (by the
Portmanteau theorem). Since $K^{2}2^{1-l}$ is summable in $l$, Borel-Cantelli
implies that the probability that infinitely many of the events
$\left\\{c_{e}>\left(2K\right)^{-\operatorname{dist}\left(v_{0},e\right)}\right\\}$
occur is $0$. In other words, for all but a finite number of edges,
$c_{e}\leq\left(2K\right)^{-\operatorname{dist}\left(v_{0},e\right)}$ a.s. But
then,

$\displaystyle\sum_{e\in E}c_{e}=\sum_{l\geq 0}\sum_{e\in
E:\operatorname{dist}\left(v_{0},e\right)=l}c_{e}\leq A+\sum_{l\geq
0}K^{l+1}\left(2K\right)^{-l}=A+K\cdot\sum_{l\geq 0}2^{-l}<\infty$

where $A$ accounts for the finitely many exceptions to the $c_{e}$ bound. So
the RWRE is a.s. positive recurrent.

To finish the proof, we will show how tightness follows from the above
calculation for fixed initial weights $a$. Let $\varepsilon>0$. We have to
show there is a compact set $K_{\varepsilon}\subseteq\mathbb{R}_{\geq 0}^{E}$
such that for all $R$, the measure of the complement
$\mu^{\left(R\right)}\left(K_{\varepsilon}^{\textrm{C}}\right)$ is smaller
than $\varepsilon$. If we choose $Q=\left(\lambda
K\right)^{-\operatorname{dist}\left(v_{0},e\right)}$ in Equation 4.4, we get

$\displaystyle\mu^{\left(R\right)}\left(\exists e\in
B_{R}\left(v_{0}\right):\operatorname{dist}\left(v_{0},e\right)=l\textrm{ and
}c_{e}^{\left(R\right)}>\left(\lambda K\right)^{-l}\right)$ $\displaystyle\leq
2K^{2}\left(\lambda^{s}K^{1+s}C\left(s,K\right)\sqrt{a}\right)^{l}$

Thus,

$\displaystyle\mu^{\left(R\right)}\left(\exists e\in
B_{R}\left(v_{0}\right):c_{e}^{\left(R\right)}>\left(\lambda
K\right)^{-\operatorname{dist}\left(v_{0},e\right)}\right)$
$\displaystyle\leq\sum_{l\geq 0}\mu^{\left(R\right)}\left(\exists e\in
B_{R}\left(v_{0}\right):\operatorname{dist}\left(v_{0},e\right)=l\textrm{ and
}c_{e}^{\left(R\right)}>\left(\lambda K\right)^{-l}\right)$
$\displaystyle\overset{\circledast}{=}\sum_{l\geq
1}\mu^{\left(R\right)}\left(\exists e\in
B_{R}\left(v_{0}\right):\operatorname{dist}\left(v_{0},e\right)=l\textrm{ and
}c_{e}^{\left(R\right)}>\left(\lambda K\right)^{-l}\right)$ $\displaystyle\leq
2K^{2}\sum_{l\geq
1}\left(\lambda^{s}K^{1+s}C\left(s,K\right)\sqrt{a}\right)^{l}=\frac{2K^{2}\lambda^{s}K^{1+s}C\left(s,K\right)\sqrt{a}}{1-\lambda^{s}K^{1+s}C\left(s,K\right)\sqrt{a}}$

For $\circledast$, recall that we normalized the conductances to
$c_{v_{0}}=1$, so for any edge $e$ with distance $0$ to $v_{0}$, it holds that
$c_{e}\leq 1$. We can now choose $\lambda$ such that

$\displaystyle\lambda<\left(\frac{\varepsilon}{K^{1+s}C\left(s,K\right)\sqrt{a}\left(2K^{2}+\varepsilon\right)}\right)^{\frac{1}{s}}$

Then

$\displaystyle\mu^{\left(R\right)}\left(\exists e\in
B_{R}\left(v_{0}\right):c_{e}^{\left(R\right)}>\left(\lambda
K\right)^{-\operatorname{dist}\left(v_{0},e\right)}\right)<\varepsilon$

which holds independently of $R$. So we can choose

$\displaystyle K_{\varepsilon}=\prod_{e\in E}\left[0,\left(\lambda
K\right)^{-\operatorname{dist}\left(v_{0},e\right)}\right]$

which is compact. Note that $K_{\varepsilon}$ grows when $\varepsilon$ gets
smaller, because $\lambda$ must also be chosen smaller in this case.

##  5 Reinforced Random Walk with Multiple Walkers

Here, we consider multiple walkers on a single environment influencing each
other.

###  5.1 A Two-Player Urn

We start with a very simple model, the linearly edge-reinforced random walk
with two walkers on a segment of $\mathbb{Z}$ with three nodes.

$0$$-1$$1$$w\left(n,0\right)$$w\left(n,1\right)$ Figure 4: Edge weights of the
line segment at time $n$

####  5.1.1 Alternating Players

We first define the following dynamics:

  * •

There are two walkers $X^{\left(1\right)}$ and $X^{\left(2\right)}$, which
both start at the node in the center, i.e.
$X^{\left(1\right)}_{0}=0,X^{\left(2\right)}_{0}=0$.

  * •

Initially, both edge weights are $1$. We denote the edge weight of the left
edge at time $n$ by $w\left(n,0\right)$, the weight of the right edge by
$w\left(n,1\right)$.

  * •

Whenever an edge is crossed by either of the walkers, its weight is increased
by $1$, so we set $W\left(n\right)=1+n$ in terms of 2.3.

  * •

The walkers move alternately, i.e. at odd time steps, walker $1$ moves (in
particular, walker $1$ moves first at step $1$) and at even time steps, walker
$2$ moves. This implies that the walkers will meet at the node in the center
every four steps.

  * •

When a walker at the node in the center is about to move, he chooses the edge
to traverse with probability proportional to the respective edge weight.

###### Lemma 5.1

The random variables
$\frac{w\left(4n,0\right)}{w\left(4n,0\right)+w\left(4n,1\right)}$ for $n\geq
0$ form a martingale.

###### Proof

We can calculate:

$\displaystyle\mathbb{E}\left[\frac{w\left(4n+4,0\right)}{w\left(4n+4,0\right)+w\left(4n+4,1\right)}\mathrel{}\middle|\mathrel{}w\left(4n,0\right)=a,w\left(4n,1\right)=b\right]$
$\displaystyle=\frac{a}{a+b}\frac{a+1}{a+b+1}\frac{a+4}{a+b+4}+\frac{a}{a+b}\frac{b}{a+b+1}\frac{a+2}{a+b+4}$
$\displaystyle\hphantom{\;=\;}+\frac{b}{a+b}\frac{a}{a+b+1}\frac{a+2}{a+b+4}+\frac{b}{a+b}\frac{b+1}{a+b+1}\frac{a}{a+b+4}$
$\displaystyle=\frac{a}{a+b}\cdot\frac{\left(a+1\right)\left(a+4\right)+2b\left(a+2\right)+b\left(b+1\right)}{\left(a+b+1\right)\left(a+b+4\right)}=\frac{a}{a+b}$

###### Corollary 5.2

$\frac{w\left(n,0\right)}{w\left(n,0\right)+w\left(n,1\right)}$ converges
almost surely for $n\to\infty$

###### Proof

We immediately get from 5.1 that
$\frac{w\left(4n,0\right)}{w\left(4n,0\right)+w\left(4n,1\right)}$ converges
a.s. and then, it is easy to see that also
$\frac{w\left(n,0\right)}{w\left(n,0\right)+w\left(n,1\right)}$ converges.

###### Conjecture 5.3

Define the random variable
$Y:=\lim_{n\to\infty}\frac{w\left(n,0\right)}{w\left(n,0\right)+w\left(n,1\right)}$.
Then $Y\in\left[0,1\right]$ has a density w.r.t. the Lebesgue measure on
$\left[0,1\right]$. $Y$ is not Beta-distributed.

####  5.1.2 Random Player Selection

Consider next the case where at every step, we choose uniformly at random
(independent of all other steps) which of the two walkers moves. 5.4 shows
that the expected time to meet again in the middle, if both walkers start in
the center, is $4$, just as in the previous case. Of course, the difference
now is that the next meeting time is random. We call $\tau_{0}=0$ and
$\tau_{n}=\inf\left\\{k>\tau_{n-1}:X^{\left(1\right)}_{k}=X^{\left(2\right)}_{k}=0\right\\}$.

###### Lemma 5.4

For any $n\geq 0$ and any $l\geq 1$, it holds that
$\mathbb{P}\left[\tau_{n+1}-\tau_{n}=2l\right]=2^{-l}$ and
$\mathbb{E}\left[\tau_{n+1}-\tau_{n}\right]=4$.

###### Proof

We consider a MC consisting of three states and coupled with the edge-
reinforced random walk. The MC is in state $s_{\textrm{center}}$ if both
walkers are in the center, in state $s_{\textrm{mixed}}$ if one walker is in
the center and the other in either of the two outer nodes, and in state
$s_{\textrm{none}}$ if none of the walkers is in the center. It is easy to
verify that this is indeed a MC with the following transition probabilities:

$s_{\textrm{center}}$$s_{\textrm{mixed}}$$s_{\textrm{none}}$$1$$\frac{1}{2}$$\frac{1}{2}$$1$

Let $n\geq 0$. At time $\tau_{n}$, both walkers are in the center and the MC
is therefore in state $s_{\textrm{center}}$. The time $\tau_{n+1}-\tau_{n}$
corresponds to the time needed to return again to the state
$s_{\textrm{center}}$. It is now a standard calculation to show
$\mathbb{P}\left[\tau_{n+1}-\tau_{n}=2l\right]=2^{-l}$. Consequently,

$\displaystyle\mathbb{E}\left[\tau_{n+1}-\tau_{n}\right]$
$\displaystyle=\sum_{l\geq 1}2^{-l}\cdot 2l=\sum_{l\geq
1}l\cdot\left(\frac{1}{2}\right)^{l-1}=\frac{1}{\left(1-\frac{1}{2}\right)^{2}}=4$

We next want to prove, in 5.7, that the fraction of the left edge weight,
$\frac{w\left(\tau_{n},0\right)}{w\left(\tau_{n},0\right)+w\left(\tau_{n},1\right)}$,
is a martingale, as it was in the previous case and as in the one-player urn
with the difference that we look at the fraction not at every time step, but
at certain stopping times. We use two lemmas for the proof and introduce the
following notation:

  1. (1)

We look at the expectation of the proportion of the left edge weight
multiplied by the indicator of the event that the walkers need $2l$ steps to
meet again:

$\displaystyle\mathbb{E}_{a,b,l}:=\mathbb{E}\left[\frac{w\left(\tau_{n+1},0\right)}{w\left(\tau_{n+1},0\right)+w\left(\tau_{n+1},1\right)}\cdot\mathbbm{1}_{\left\\{\tau_{n+1}-\tau_{n}=2l\right\\}}\mathrel{}\middle|\mathrel{}w\left(\tau_{n},0\right)=a,w\left(\tau_{n},1\right)=b\right]$

  2. (2)

We also consider the probability that the last walker which returns to the
center comes from the left node, again intersected with the event that the
walkers need $2l$ steps to meet again:

$\displaystyle L_{n}$ $\displaystyle:=\left\\{\textrm{the walker returning to
the center at time }\tau_{n+1}\textrm{ comes from the left node}\right\\}$
$\displaystyle q_{a,b,l}$ $\displaystyle:=\mathbb{P}\left[L_{n}\textrm{ occurs
and
}\tau_{n+1}-\tau_{n}=2l\mathrel{}\middle|\mathrel{}w\left(\tau_{n},0\right)=a,w\left(\tau_{n},1\right)=b\right]$

###### Lemma 5.5

We have the following recursive equations:

$\displaystyle\mathbb{E}_{a,b,l+1}$
$\displaystyle=\frac{1}{2}\mathbb{E}_{a,b,l}+\frac{1}{\left(a+b+2l-1\right)\left(a+b+2l+2\right)}\left(\mathbb{E}_{a,b,l}-q_{a,b,l}\right)$
$\displaystyle q_{a,b,l+1}$
$\displaystyle=\frac{1}{2}q_{a,b,l}+\frac{1}{4}\cdot\frac{a+b+2l}{a+b+2l-1}\left(\mathbb{E}_{a,b,l}-q_{a,b,l}\right)$

###### Proof

The following notation will be useful. We define a path of the two walkers as
a sequence of the symbols
$1_{\textrm{l}},1_{\textrm{r}},2_{\textrm{l}},2_{\textrm{r}}$ which correspond
to the first (respectively second) walker moving left and right, where we
assume that both walkers start in the center. The set $\textrm{Path}_{2l}$
contains all the paths of length $2l$ (a sequence of $2l$ symbols) such that
the first time at which both walkers are in the center at the same time again
is at the end of the path. Note that any such path must be of even length
since each walker can only be in the center after having made an even number
of movements.

For, $\rho\in\textrm{Path}_{2l}$, we set $x\left(\rho\right)$ to be the number
of traversals of the left edge when the path $\rho$ is taken and we can now
write

$\displaystyle\mathbb{E}_{a,b,l}$
$\displaystyle=\sum_{\rho\in\textrm{Path}_{2l}}\underbrace{\mathbb{P}\left[\textrm{the
walkers move according to
}\rho\mathrel{}\middle|\mathrel{}w\left(\tau_{n},0\right)=a,w\left(\tau_{n},1\right)=b\right]}_{=:\mathbb{P}_{\rho,a,b}}\cdot\frac{a+x\left(\rho\right)}{a+b+2l}$

To prove the recurrence relation, we build paths of length $2\left(l+1\right)$
out of paths of length $2l$.

new step: center walker goes left | new step: center walker goes right
---|---
$0$$-1$$1$$a+x\left(\rho\right)-1$$b+2l-x\left(\rho\right)$ | $0$$-1$$1$$a+x\left(\rho\right)-1$$b+2l-x\left(\rho\right)$
or | or
$0$$-1$$1$$a+x\left(\rho\right)$$b+2l-x\left(\rho\right)-1$ | $0$$-1$$1$$a+x\left(\rho\right)$$b+2l-x\left(\rho\right)-1$
Figure 5: Possible walker locations after $2l-1$ steps of a path $\rho$ of
length $2l$

For any possible path of the walkers, at any uneven time step, there will be
one walker which is in the center and one which is in one of the outer nodes.
The paths in $\textrm{Path}_{2l}$ have the additional condition that at any
even time step (except for the beginning and end), both walkers have to be in
the outer nodes, not necessarily the same one. We can therefore construct all
paths in $\textrm{Path}_{2\left(l+1\right)}$ as follows: for every
$\rho\in\textrm{Path}_{2l}$, we take the path $\rho$ up to time $2l-1$. The
possible walker locations and edge weights after $2l-1$ steps are depicted in
Figure 5. The path $\rho$ now continues with the walker in the outer node
moving back to the center. To get a path of length $2\left(l+1\right)$, the
walker in the center node has to move instead in the next step, and then both
walkers will return to the center in either order. Out of $\rho$, we can thus
construct $4$ new paths of length $2\left(l+1\right)$: we have two choices for
which way the center walker moves in step $2l$, and then two choices for the
order in which the walkers return. Note that we do not construct any path
twice, since any two different paths in $\textrm{Path}_{2l}$ must already
differ somewhere in the first $2l-1$ steps.

Now, we look at how this changes the outcome (the final edge weights) and the
probability of the path. Let $\rho\in\textrm{Path}_{2l}$.

  * •

If the outer walker is on the left after $2l-1$ steps (this is a condition on
$\rho$):

    * –

If the center walker should move left in step $2l$ (this is one choice for
creating the new path): the probability $\mathbb{P}_{\rho,a,b}$ of $\rho$ is a
product over the probability that the walker indicated in $\rho$ is chosen at
the respective step (which is always $\frac{1}{2}$) and the probability that
the walker moves in the direction indicated by $\rho$ (this can either be $1$,
if the walker moves back to the center, or a fraction depending on the edge
weights). In our new modified path of length $2\left(l+1\right)$, the first
difference is that we choose a different walker to move in step $2l$. This
event has probability $\frac{1}{2}$, but this is the same as chosing the
original walker, hence this part is already included in the product giving the
probability $\mathbb{P}_{\rho,a,b}$ of $\rho$.

Next, the probability for the center walker to go left, if he is chosen to
move at step $2l$, is given by $\frac{a+x\left(\rho\right)-1}{a+b+2l-1}$
(compare with Figure 5). This factor is new and has to be added to the
product. In the next step, one of the two walkers is chosen and will move back
to the center. It is irrelevant which one moves, so we get only a new factor
of $1$. Finally, in step $2\left(l+1\right)$, the walker which is still in an
outer node has to be chosen to move back into the center. This happens with
probability $\frac{1}{2}$, and this is the final factor to be added to the
product. Our new path therefore has probability

$\displaystyle\mathbb{P}_{\rho,a,b}\cdot\frac{1}{2}\cdot\frac{a+x\left(\rho\right)-1}{a+b+2l-1}$

The new path will end with the following ratio of the left edge weight divided
by the total edge weights:

$\displaystyle\frac{a+x\left(\rho\right)+2}{a+b+2l+2}$

since the left edge will be traversed twice more by the center walker.

    * –

If the center walker should move right in step $2l$:

$\displaystyle\textrm{new path probability:
}\mathbb{P}_{\rho,a,b}\cdot\frac{1}{2}\cdot\frac{b+2l-x\left(\rho\right)}{a+b+2l-1},\quad\textrm{new
outcome: }\frac{a+x\left(\rho\right)}{a+b+2l+2}$

  * •

If the outer walker is on the right after $2l-1$ steps:

    * –

If the center walker should move left in step $2l$:

$\displaystyle\textrm{new path probability:
}\mathbb{P}_{\rho,a,b}\cdot\frac{1}{2}\cdot\frac{a+x\left(\rho\right)}{a+b+2l-1},\quad\textrm{new
outcome: }\frac{a+x\left(\rho\right)+2}{a+b+2l+2}$

    * –

If the center walker should move right in step $2l$:

$\displaystyle\textrm{new path probability:
}\mathbb{P}_{\rho,a,b}\cdot\frac{1}{2}\cdot\frac{b+2l-x\left(\rho\right)-1}{a+b+2l-1},\quad\textrm{new
outcome: }\frac{a+x\left(\rho\right)}{a+b+2l+2}$

For $\rho\in\textrm{Path}_{2l}$, we write $\textrm{left}\left(\rho\right)=1$
if the outer walker after step $2l-1$ is on the left, and
$\textrm{left}\left(\rho\right)=0$ otherwise. Using the recursive path
construction above, we get that

$\displaystyle\mathbb{E}_{a,b,l+1}=\sum_{\rho\in\textrm{Path}_{2\left(l+1\right)}}\mathbb{P}_{\rho,a,b}\cdot\frac{a+x\left(\rho\right)}{a+b+2l+2}=$
$\displaystyle\sum_{\rho\in\textrm{Path}_{2l}}\mathbb{P}_{\rho,a,b}\cdot\frac{1}{2}\cdot\left(\textrm{left}\left(\rho\right)\cdot\left(\frac{a+x\left(\rho\right)-1}{a+b+2l-1}\cdot\frac{a+x\left(\rho\right)+2}{a+b+2l+2}+\frac{b+2l-x\left(\rho\right)}{a+b+2l-1}\cdot\frac{a+x\left(\rho\right)}{a+b+2l+2}\right)\right.$
$\displaystyle\qquad\;\left.+\left(1-\textrm{left}\left(\rho\right)\right)\cdot\left(\frac{a+x\left(\rho\right)}{a+b+2l-1}\cdot\frac{a+x\left(\rho\right)+2}{a+b+2l+2}+\frac{b+2l-x\left(\rho\right)-1}{a+b+2l-1}\cdot\frac{a+x\left(\rho\right)}{a+b+2l+2}\right)\right)$

Using this expression for $\mathbb{E}_{a,b,l+1}$, we can calculate (a simple,
but longer calculation which we skip here, see https://bit.ly/3trqm2r and
https://bit.ly/391ma2o):

$\displaystyle\mathbb{E}_{a,b,l+1}-\frac{1}{2}\mathbb{E}_{a,b,l}$
$\displaystyle=\sum_{\rho\in\textrm{Path}_{2l}}\mathbb{P}_{\rho,a,b}\cdot\frac{1}{\left(a+b+2l-1\right)\left(a+b+2l+2\right)}\;\cdot$
$\displaystyle\hphantom{=\qquad}\left(\textrm{left}\left(\rho\right)\cdot\frac{x\left(\rho\right)-b-2l}{a+b+2l}+\left(1-\textrm{left}\left(\rho\right)\right)\cdot\frac{a+x\left(\rho\right)}{a+b+2l}\right)$
$\displaystyle=\frac{1}{\left(a+b+2l-1\right)\left(a+b+2l+2\right)}\;\cdot$
$\displaystyle\hphantom{=\qquad}\sum_{\rho\in\textrm{Path}_{2l}}\mathbb{P}_{\rho,a,b}\cdot\left(\textrm{left}\left(\rho\right)\cdot\frac{-a-b-2l}{a+b+2l}+\frac{a+x\left(\rho\right)}{a+b+2l}\right)$
$\displaystyle=\frac{1}{\left(a+b+2l-1\right)\left(a+b+2l+2\right)}\cdot\left(\mathbb{E}_{a,b,l}-\sum_{\rho\in\textrm{Path}_{2l}}\mathbb{P}_{\rho,a,b}\cdot\textrm{left}\left(\rho\right)\right)$
$\displaystyle=\frac{1}{\left(a+b+2l-1\right)\left(a+b+2l+2\right)}\cdot\left(\mathbb{E}_{a,b,l}-q_{a,b,l}\right)$

This proves the first equation. For the second equation, we use the same
strategy. For our newly constructed paths, we have to calculate the
probability that the last walker to move to the center comes from the left
node. Let $\rho\in\textrm{Path}_{2l}$.

  * •

If the outer walker is on the left after $2l-1$ steps (this is a condition on
$\rho$):

    * –

If the center walker should move left in step $2l$ (this is one choice for
creating the new path):

$\displaystyle\textrm{new path probability:
}\mathbb{P}_{\rho,a,b}\cdot\frac{1}{2}\cdot\frac{a+x\left(\rho\right)-1}{a+b+2l-1},\quad\textrm{probability
of }L_{n}\textrm{: }1$

    * –

If the center walker should move right in step $2l$:

$\displaystyle\textrm{new path probability:
}\mathbb{P}_{\rho,a,b}\cdot\frac{1}{2}\cdot\frac{b+2l-x\left(\rho\right)}{a+b+2l-1},\quad\textrm{probability
of }L_{n}\textrm{: }\frac{1}{2}$

  * •

If the outer walker is on the right after $2l-1$ steps:

    * –

If the center walker should move left in step $2l$:

$\displaystyle\textrm{new path probability:
}\mathbb{P}_{\rho,a,b}\cdot\frac{1}{2}\cdot\frac{a+x\left(\rho\right)}{a+b+2l-1},\quad\textrm{probability
of }L_{n}\textrm{: }\frac{1}{2}$

    * –

If the center walker should move right in step $2l$:

$\displaystyle\textrm{new path probability:
}\mathbb{P}_{\rho,a,b}\cdot\frac{1}{2}\cdot\frac{b+2l-x\left(\rho\right)-1}{a+b+2l-1},\quad\textrm{probability
of }L_{n}\textrm{: }0$

Therefore

$\displaystyle q_{a,b,l+1}-\frac{1}{2}q_{a,b,l}$
$\displaystyle=\sum_{\rho\in\textrm{Path}_{2l}}\mathbb{P}_{\rho,a,b}\cdot\frac{1}{2}\;\cdot$
$\displaystyle\hphantom{=\qquad}\left(\frac{a+x\left(\rho\right)-1}{a+b+2l-1}\cdot\textrm{left}\left(\rho\right)+\frac{1}{2}\cdot\frac{b+2l-x\left(\rho\right)}{a+b+2l-1}\cdot\textrm{left}\left(\rho\right)\right.$
$\displaystyle\hphantom{=\qquad(}\left.+\;\frac{1}{2}\cdot\frac{a+x\left(\rho\right)}{a+b+2l-1}\cdot\left(1-\textrm{left}\left(\rho\right)\right)-\textrm{left}\left(\rho\right)\right)$
$\displaystyle=\frac{1}{2}\cdot\sum_{\rho\in\textrm{Path}_{2l}}\mathbb{P}_{\rho,a,b}\;\cdot$
$\displaystyle\hphantom{=\qquad}\left(-\frac{1}{2}\cdot\frac{a+b+2l}{a+b+2l-1}\cdot\textrm{left}\left(\rho\right)+\frac{1}{2}\cdot\frac{a+x\left(\rho\right)}{a+b+2l-1}\right)$
$\displaystyle=\frac{1}{4}\cdot\frac{a+b+2l}{a+b+2l-1}\cdot\sum_{\rho\in\textrm{Path}_{2l}}\mathbb{P}_{\rho,a,b}\cdot\left(\frac{a+x\left(\rho\right)}{a+b+2l}-\textrm{left}\left(\rho\right)\right)$
$\displaystyle=\frac{1}{4}\cdot\frac{a+b+2l}{a+b+2l-1}\cdot\left(\mathbb{E}_{a,b,l}-q_{a,b,l}\right)$

###### Corollary 5.6

The expectation of the proportion of the left edge weight and the probability
that the last walker returning to the center comes from the left coincide,
and:

$\displaystyle\mathbb{E}_{a,b,l}=q_{a,b,l}=\frac{1}{2^{l}}\cdot\frac{a}{a+b}$

###### Proof

We use 5.5. Let us first calculate $\mathbb{E}_{a,b,1}$ and $q_{a,b,1}$. There
are four possible paths of length $2$ which end again with both walkers in the
center: first, we choose which of the two walker moves, and this walker can
than either move left or right and then back to the center. Since it is
irrelevant which walker we choose in the beginning, we can disregard which
walker moves. We thus get:

  * •

With probability $\frac{a}{a+b}\cdot\frac{1}{2}$ the walker which moves in the
first step moves left and is then chosen again to move back to the center in
the next step. In this case, $L_{n}$ occurs and the resulting edge weight
ratio is $\frac{a+2}{a+b+2}$.

  * •

With probability $\frac{b}{a+b}\cdot\frac{1}{2}$ the walker which moves in the
first step moves right and is then chosen again to move back to the center in
the next step. In this case, $L_{n}$ does not occur and the resulting edge
weight ratio is $\frac{a}{a+b+2}$.

We see directly that $q_{a,b,1}=\frac{1}{2}\cdot\frac{a}{a+b}$ and that

$\displaystyle\mathbb{E}_{a,b,1}=\frac{1}{2}\cdot\left(\frac{a}{a+b}\cdot\frac{a+2}{a+b+2}+\frac{b}{a+b}\cdot\frac{a}{a+b+2}\right)=\frac{1}{2}\cdot\frac{a}{a+b}$

The remaining proof is now a simple induction using 5.5, where it should be
noted that $\mathbb{E}_{a,b,l}-q_{a,b,l}=0$ under the induction assumption.

###### Lemma 5.7

The random variables
$\frac{w\left(\tau_{n},0\right)}{w\left(\tau_{n},0\right)+w\left(\tau_{n},1\right)}$
for $n\geq 0$ form a martingale.

###### Proof

We have by 5.6:

$\displaystyle\mathbb{E}\left[\frac{w\left(\tau_{n+1},0\right)}{w\left(\tau_{n+1},0\right)+w\left(\tau_{n+1},1\right)}\cdot\mathbbm{1}_{\left\\{\tau_{n+1}-\tau_{n}=2l\right\\}}\mathrel{}\middle|\mathrel{}w\left(\tau_{n},0\right)=a,w\left(\tau_{n},1\right)=b\right]=2^{-l}\cdot\frac{a}{a+b}$
$\displaystyle\implies$
$\displaystyle\mathbb{E}\left[\frac{w\left(\tau_{n+1},0\right)}{w\left(\tau_{n+1},0\right)+w\left(\tau_{n+1},1\right)}\mathrel{}\middle|\mathrel{}w\left(\tau_{n},0\right)=a,w\left(\tau_{n},1\right)=b\right]=\frac{a}{a+b}\cdot\sum_{l\geq
1}2^{-l}=\frac{a}{a+b}$

###### Lemma 5.8

Assume that $w\left(0,0\right)=a>0,w\left(0,1\right)=b>0$. Then, the random
variables
$M_{n}:=\frac{w\left(\tau_{n},0\right)}{w\left(\tau_{n},0\right)+w\left(\tau_{n},1\right)}$
take values in the set

$\displaystyle
R:=\left\\{\frac{a+2x}{a+b+2l}\mathrel{}\middle|\mathrel{}x\in\mathbb{N}_{\geq
0},l\in\mathbb{N}_{\geq 1},x\leq l\right\\}$

and, for every $r\in R$ and every $n\in\mathbb{N}_{\geq 1}$, we have that
$\mathbb{P}\left[M_{n}=r\right]>0$. The set $R$ is dense in
$\left[0,1\right]$.

###### Proof

It is immediately clear that $M_{n}$ can take only values in the set $R$:
$w\left(\tau_{n},0\right)$ will be equal to $a$ plus the number of crossings
of the left edge until time $\tau_{n}$. Since both walkers are in the center
at time $\tau_{n}$, this number of edge crossings has to be even, hence we can
write $w\left(\tau_{n},0\right)=a+2x$ for some $x\in\mathbb{N}_{\geq 0}$. On
the other hand, the total edge weight also must have increased by an even
number since both walkers have to do an even number of steps before meeting
again in the center.

We now want to construct a sequence of walker steps leading to any possible
outcome $\frac{a+2x}{a+b+2l}$ with positive probability. First, note that
$w\left(\tau_{n},0\right)+w\left(\tau_{n},1\right)=a+b+\tau_{n}$. Since
$\tau_{n}\geq 2n$, we cannot have a sequence of length $2l$ leading to our
desired outcome when $l<n$. In this case, we have to reach
$\frac{a+2x}{a+b+2l}$ by a longer sequence. We have, for any $k$,

$\displaystyle\frac{a+2x}{a+b+2l}=\frac{k\left(a+2x\right)}{k\left(a+b+2l\right)}=\frac{a+2\left(kx+\frac{1}{2}\left(k-1\right)a\right)}{a+b+2\left(kl+\frac{1}{2}\left(k-1\right)\left(a+b\right)\right)}$

To reach our desired fraction, we thus want a sequence of length
$2\left(kl+\frac{1}{2}\left(k-1\right)\left(a+b\right)\right)\geq 2n$. In
addition, $\left(k-1\right)\left(a+b\right)$ and $\left(k-1\right)a$ should
both be even. It thus suffices to choose an uneven $k$ which is large enough
such that $kl+\frac{1}{2}\left(k-1\right)\left(a+b\right)\geq n$. This allows
us to assume w.l.o.g. that $l\geq n$.

What remains to show is that we can construct a sequence of length $2l$ such
that after all $2l$ steps, the walkers meet again in the center for the
$n$-the time and such that the left edge is traversed $2x$ times. Since any
finite sequence of possible walker movements has positive probability, this
concludes the proof. Finding such a sequence is easy: in the first
$2\left(n-1\right)$ steps, one walker moves $\min\left\\{x,n-1\right\\}$ times
to the left node and back, and in the remaining steps (if there are any), the
same walker moves to the right node and back. Then, in the
$\left(2n-1\right)$-th step, the same walker moves to the left node, if the
left edge was not yet crossed $2x$ times, and otherwise to the right node. The
walker then remains there until returning to the center in the $2l$-th step.
In the remaining steps of the complete sequence of length $2l$, the other
walker moves in such a way as to reach a total number of $2x$ left edge
crossings. This leads to the desired fraction at time $\tau_{n}$.

It is easy to see that $R$ is dense in $\left[0,1\right]$. Indeed, choosing
$x=k\cdot p$ and $l=k\cdot q$ for increasing $k$ shows that we can find
sequences in $R$ converging to any rational number, and these are already
dense in $\left[0,1\right]$.

###### Corollary 5.9

$\frac{w\left(n,0\right)}{w\left(n,0\right)+w\left(n,1\right)}$ converges
almost surely for $n\to\infty$, and the limit is identical to the limit of
$\frac{w\left(\tau_{n},0\right)}{w\left(\tau_{n},0\right)+w\left(\tau_{n},1\right)}$.

###### Proof

We use the following notation:

$\displaystyle
F_{n}:=\frac{w\left(n,0\right)}{w\left(n,0\right)+w\left(n,1\right)}\qquad
M_{n}:=F_{\tau_{n}}=\frac{w\left(\tau_{n},0\right)}{w\left(\tau_{n},0\right)+w\left(\tau_{n},1\right)}\qquad
M_{\infty}:=\lim\limits_{n\to\infty}M_{n}$

Let $\varepsilon>0$ and consider the events

$\displaystyle
A_{n}:=\left\\{\left|F_{k}-M_{\infty}\right|>\varepsilon\textrm{ for some
}k\in\left[\tau_{n},\tau_{n+1}\right]\right\\}$

It is sufficient to show that only finitely many of the events $A_{n}$ can
occur a.s. Further set

$\displaystyle
B_{n}:=\left\\{\left|F_{k}-M_{n}\right|>\frac{\varepsilon}{2}\textrm{ for some
}k\in\left[\tau_{n},\tau_{n+1}\right]\right\\}$

Since $M_{n}$ converges a.s. by 5.7, there is some (random) $N\in\mathbb{N}$
such that for all $n\geq N$, it holds that
$\left|M_{n}-M_{\infty}\right|<\frac{\varepsilon}{2}$. For $n\geq N$, the
occurrence of $A_{n}$ implies that $B_{n}$ occurs as well, so it is sufficient
to show that only finitely many of the events $B_{n}$ can occur.

Now, at time $\tau_{n}$, the random walkers must have moved at least $2n$
times, so $w\left(\tau_{n},0\right)+w\left(\tau_{n},1\right)\geq 2n$. If
$\left|F_{k}-M_{n}\right|=\left|F_{k}-F_{\tau_{n}}\right|>\frac{\varepsilon}{2}$
for some $k\in\left[\tau_{n},\tau_{n+1}\right]$, it is therefore necessary
that at least $\varepsilon n$ steps were made by the walkers between time
$\tau_{n}$ and time $k$, since every step changes the value of $F_{k}$ by at
most $\frac{1}{2n}$. Thus

$\displaystyle B_{n}\subseteq\left\\{\tau_{n+1}-\tau_{n}\geq\varepsilon
n\right\\}$

We have

$\displaystyle\mathbb{P}\left[\tau_{n+1}-\tau_{n}\geq\varepsilon n\right]$
$\displaystyle=\sum_{l\geq\left\lceil\frac{\varepsilon
n}{2}\right\rceil}\mathbb{P}\left[\tau_{n+1}-\tau_{n}=2l\right]\overset{\textrm{\autoref{lem:two_pl_urn_rand_meeting_time}}}{=}\sum_{l\geq\left\lceil\frac{\varepsilon
n}{2}\right\rceil}2^{-l}$ $\displaystyle\leq 2^{-\frac{\varepsilon
n}{2}}\sum_{l\geq 0}2^{-l}=2^{1-\frac{\varepsilon n}{2}}$
$\displaystyle\implies\sum_{n\geq
1}\mathbb{P}\left[\tau_{n+1}-\tau_{n}\geq\varepsilon n\right]$
$\displaystyle\leq\sum_{n\geq 1}2^{1-\frac{\varepsilon
n}{2}}=2\cdot\sum_{n\geq 1}\left(2^{-\frac{\varepsilon}{2}}\right)^{n}<\infty$

By Borel-Cantelli, it follows that only finitely many of the events
$\left\\{\tau_{n+1}-\tau_{n}\geq\varepsilon n\right\\}$ can occur, and
therefore also only finitely many of the events $B_{n}$. This concludes the
proof.

The same model with only one random walker results in a standard Pólya urn
where two balls of the drawn color are added after every draw. For the Pólya
urn, the fraction of balls of one of the colors is a martingale and converges
to a limit which is Beta-distributed. We have shown now for the two-player urn
that the fraction of the left edge weight also has a limit, even if it is a
martingale only if looked at at certain stopping times. Simulations and
intuition suggest that the limit should also have a density. However, we
couldn’t prove this so far, so we only give the following conjecture.
Simulations also suggest that the limiting distribution is not a Beta
distribution.

###### Conjecture 5.10

Define the random variable
$Y:=\lim_{n\to\infty}\frac{w\left(n,0\right)}{w\left(n,0\right)+w\left(n,1\right)}$.
Then $Y\in\left[0,1\right]$ has a density w.r.t. the Lebesgue measure on
$\left[0,1\right]$. $Y$ is not Beta-distributed, and its distribution is
different from the distribution of the limit in 5.3.

###  5.2 Model on $\mathbb{Z}$

So far, we have looked at the LERRW with multiple walkers only on a very
simple graph and only with $2$ walkers. We now look at the edge-reinforced
random walk on $\mathbb{Z}$ with an arbitrary finite number of random walkers.
Formally, we have $k$ sequences (for $k$ walkers)
$\left(X^{\left(m\right)}_{n}\right)_{n\geq 0},1\leq m\leq k$ of random
variables with the following dynamics. The transition probabilities depend on
the edge weights $w\left(n,j\right)>0$ for $n\geq 0,j\in\mathbb{Z}$ where $j$
corresponds to the edge from $j$ to $j+1$.

$0$$j-1$$j$$j+1$$w\left(n,j-1\right)$$w\left(n,j\right)$ Figure 6: Edge
weights on $\mathbb{Z}$ at time $n$

If $\mathcal{G}_{n}$ denotes
$\sigma\left(\left\\{X^{\left(m_{2}\right)}_{m_{1}}:0\leq m_{1}\leq n,1\leq
m_{2}\leq k\right\\}\cup\left\\{w\left(m,j\right):0\leq m\leq
n,j\in\mathbb{Z}\right\\}\right)$ i.e. the history of the random walkers and
edge weights up to and including time $n$, then we define, conditioned on
$\mathcal{G}_{n}$, the following transition probabilities:

  * •

A random walker $m$ ($1\leq m\leq k$) which is going to jump is chosen
uniformly at random (independent of $\mathcal{G}_{n}$) amongst the $k$
walkers.

  * •

If the chosen random walker is at position $j$ (i.e.
$X^{\left(m\right)}_{n}=j$), he then jumps

    * –

to the right (i.e. $X^{\left(m\right)}_{n+1}=j+1$) with probability
$\frac{w\left(n,j\right)}{w\left(n,j-1\right)+w\left(n,j\right)}$

    * –

to the left (i.e. $X^{\left(m\right)}_{n+1}=j-1$) with probability
$\frac{w\left(n,j-1\right)}{w\left(n,j-1\right)+w\left(n,j\right)}$

i.e. the jump probabilities are proportional to the corresponding edge
weights.

  * •

If $j^{\ast}$ is the traversed edge ($j^{\ast}=j$ if the walker jumps to the
right, $j^{\ast}=j-1$ if he jumps to the left), then for $i\neq j^{\ast}$,
$w\left(n,i\right)=w\left(n+1,i\right)$ and $w\left(n,j^{\ast}\right)\leq
w\left(n+1,j^{\ast}\right)$, i.e. the weight of the traversed edge may be
increased according to some reinforcement scheme.

We consider schemes where the increment
$w\left(n+1,j^{\ast}\right)-w\left(n,j^{\ast}\right)$ may solely depend on
$j^{\ast}$, and the number of times the edge was crossed up to time $n$. In
other words, $w\left(n,j\right)$ can still be written in terms of the weight
function $W_{e}\left(k\right)$ as defined in 2.3. Some generalizations are
possible, such as making the weight also depend on $n$ (i.e. at which times
the edge was crossed), but will not be considered here.

  * •

The initial edge weights can be chosen arbitrarily, but all of them must be
positive.

  * •

The initial positions of the $k$ walkers can be chosen arbitrarily.

###  5.3 Recurrence or Finite Range on $\mathbb{Z}$

###### Definition 5.11

We say that one of the walkers $m$ ($1\leq m\leq k$)

  * •

is transient, if he visits every integer only finitely often, that is, every
integer appears only finitely often in the sequence
$\left(X^{\left(m\right)}_{n}\right)_{n\geq 1}$

  * •

is recurrent, if he visits every integer infinitely often, that is, every
integer appears infinitely often in the sequence
$\left(X^{\left(m\right)}_{n}\right)_{n\geq 1}$

  * •

has finite range, if he only visits finitely many integers, that is, the
number of distinct integers appearing in the sequence
$\left(X^{\left(m\right)}_{n}\right)_{n\geq 1}$ is finite

###### Lemma 5.12

Assume the edge-reinforced random walk with $k$ walkers starts with an initial
configuration of the weights $w\left(0,j\right)$ such that all but finitely
many of them are $1$. Then, for every random walker $m$ ($1\leq m\leq k$) with
$X^{\left(m\right)}_{0}\geq 0$, we have the following:

$\displaystyle\mathbb{P}\left[X^{\left(m\right)}_{n}=0\textrm{ for some }n\geq
0\right]$ $\displaystyle+\;$
$\displaystyle\mathbb{P}\left[X^{\left(m\right)}_{n}\neq 0\textrm{ for all
}n\geq 0\textrm{ and }X^{\left(m\right)}\textrm{ only visits finitely many
nodes}\right.$
$\displaystyle\hphantom{\mathbb{P}[}\left.\vphantom{X^{\left(m\right)}_{n}}\qquad\quad\textrm{which
have not been visited before by any other walker}\right]=1$

###### Proof

We follow the proof of [2, Lemma 3.0]. Consider a fixed random walker $m$ with
$X^{\left(m\right)}_{0}\geq 0$. We now define:

$\displaystyle F\left(n,j\right)$
$\displaystyle:=\begin{cases}\sum_{i=0}^{j-1}\frac{1}{w\left(n,i\right)}&\textrm{
if }j>0\\\ 0&\textrm{ if }j\leq
0\end{cases}\qquad\qquad\tau^{\left(m\right)}:=\inf\left\\{n\geq
0:X^{\left(m\right)}_{n}\leq 0\right\\}$ $\displaystyle
M^{\left(m\right)}_{n}$
$\displaystyle:=F\left(n\land\tau^{\left(m\right)},X^{\left(m\right)}_{n\land\tau^{\left(m\right)}}\right)$
$\displaystyle H^{\left(m\right)}_{n}$
$\displaystyle:=M^{\left(m\right)}_{n}+\sum_{i=1}^{n}\left(\frac{1}{w\left(i-1,X^{\left(m\right)}_{i-1}\right)}-\frac{1}{w\left(i,X^{\left(m\right)}_{i-1}\right)}\right)\cdot\mathbbm{1}_{X^{\left(m\right)}_{i}>X^{\left(m\right)}_{i-1},i\leq\tau^{\left(m\right)}}$
$\displaystyle\hphantom{\;:=\;}+\sum_{i=1}^{n}\;\sum_{l=1,l\neq
m}^{k}\;\sum_{j=0}^{\infty}\left(\frac{1}{w\left(i-1,j\right)}-\frac{1}{w\left(i,j\right)}\right)\cdot\underbrace{\mathbbm{1}_{\left\\{X^{\left(l\right)}_{i-1},X^{\left(l\right)}_{i}\right\\}=\left\\{j,j+1\right\\},i\leq\tau^{\left(m\right)},j<X^{\left(m\right)}_{i}}}_{=1\textrm{
for at most one pair of }l,j}$

$M^{\left(m\right)}_{n}$ is nonnegative by definition of $F$, and
$H^{\left(m\right)}_{n}\geq M^{\left(m\right)}_{n}\geq 0$ since edge weights
can only increase and therefore, all terms in the sums in the definition of
$H^{\left(m\right)}_{n}$ are nonnegative. $H^{\left(m\right)}_{n}$ is a
martingale: let

$\displaystyle d^{\left(m\right)}_{n}\;$ $\displaystyle:=$ $\displaystyle
H^{\left(m\right)}_{n}-H^{\left(m\right)}_{n-1}$
$\displaystyle=\underbrace{M^{\left(m\right)}_{n}-M^{\left(m\right)}_{n-1}}_{:=e^{\left(m\right)}_{n}}+\underbrace{\left(\frac{1}{w\left(n-1,X^{\left(m\right)}_{n-1}\right)}-\frac{1}{w\left(n,X^{\left(m\right)}_{n-1}\right)}\right)\cdot\mathbbm{1}_{X^{\left(m\right)}_{n}>X^{\left(m\right)}_{n-1},n\leq\tau^{\left(m\right)}}}_{:=f^{\left(m\right)}_{n}}$
$\displaystyle\hphantom{\;=\;}+\underbrace{\sum_{l=1,l\neq
m}^{k}\;\sum_{j=0}^{\infty}\left(\frac{1}{w\left(n-1,j\right)}-\frac{1}{w\left(n,j\right)}\right)\cdot\mathbbm{1}_{\left\\{X^{\left(l\right)}_{n-1},X^{\left(l\right)}_{n}\right\\}=\left\\{j,j+1\right\\},n\leq\tau^{\left(m\right)},j<X^{\left(m\right)}_{n}}}_{:=g^{\left(m\right)}_{n}}$

then we have to show that
$\mathbb{E}\left[d^{\left(m\right)}_{n}\mathrel{}\middle|\mathrel{}\mathcal{G}_{n-1}\right]=0$.
We have:

  * •

if $n-1\geq\tau^{\left(m\right)}$, then $d^{\left(m\right)}_{n}=0$. Hence, it
suffices to consider the case $X^{\left(m\right)}_{n-1}=j>0$ and
$\tau^{\left(m\right)}\geq n$.

  * •

with probability $\frac{1}{k}$, the walker $m$ jumps at time $n-1$. In this
case, $g^{\left(m\right)}_{n}=0$ since no other walker can jump and the
indicator variable in $g^{\left(m\right)}_{n}$ is therefore $0$. If he jumps
to the right (with probability
$\frac{1}{k}\cdot\frac{w\left(n-1,j\right)}{w\left(n-1,j-1\right)+w\left(n-1,j\right)}$),
then $e^{\left(m\right)}_{n}=w\left(n,j\right)^{-1}$ and
$f^{\left(m\right)}_{n}=w\left(n-1,j\right)^{-1}-w\left(n,j\right)^{-1}$,
hence $d^{\left(m\right)}_{n}=w\left(n-1,j\right)^{-1}$. If he jumps left
(with probability
$\frac{1}{k}\cdot\frac{w\left(n-1,j-1\right)}{w\left(n-1,j-1\right)+w\left(n-1,j\right)}$),
then $e^{\left(m\right)}_{n}=-w\left(n-1,j-1\right)^{-1}$ and
$f^{\left(m\right)}_{n}=0$, hence
$d^{\left(m\right)}_{n}=-w\left(n-1,j-1\right)^{-1}$.

  * •

with probability $\frac{k-1}{k}$, the walker $m$ does not jump. In this case,
$f^{\left(m\right)}_{n}=0$ since the indicator variable in
$f^{\left(m\right)}_{n}$ is therefore $0$. The value of
$M^{\left(m\right)}_{n-1}$ now changes (that is, $e^{\left(m\right)}_{n}\neq
0$) if one of the other $k-1$ walkers crosses one of the edges between the
nodes $0$ and $j$. At the same time, $g^{\left(m\right)}_{n}\neq 0$ only in
this exact case. Now assume the walker $l\neq m$ crosses the edge $i$ with
$0\leq i<j$. Then
$e^{\left(m\right)}_{n}=\frac{1}{w\left(n,i\right)}-\frac{1}{w\left(n-1,i\right)}$
and
$g^{\left(m\right)}_{n}=\frac{1}{w\left(n-1,i\right)}-\frac{1}{w\left(n,i\right)}$,
hence $d^{\left(m\right)}_{n}=0$.

  * •

conditioned on $X^{\left(m\right)}_{n-1}=j>0$ and $\tau^{\left(m\right)}\geq
n$ (both events measurable w.r.t. $\mathcal{G}_{n-1}$), we can therefore
conclude

$\displaystyle\mathbb{E}\left[d^{\left(m\right)}_{n}\mathrel{}\middle|\mathrel{}\mathcal{G}_{n-1}\right]$
$\displaystyle=\frac{1}{k}\cdot\frac{1}{w\left(n-1,j-1\right)+w\left(n-1,j\right)}\cdot\left(\frac{w\left(n-1,j\right)}{w\left(n-1,j\right)}-\frac{w\left(n-1,j-1\right)}{w\left(n-1,j-1\right)}\right)$
$\displaystyle=\frac{1}{k}\cdot\frac{1}{w\left(n-1,j-1\right)+w\left(n-1,j\right)}\cdot\left(1-1\right)=0$

(By the same arguments, but only considering $e^{\left(m\right)}_{n}$, we can
show that $M^{\left(m\right)}_{n}$ is a supermartingale.)

As a nonnegative martingale, $H^{\left(m\right)}_{n}$ converges almost surely.

$1$$1$$1$$M^{\left(3\right)}_{0}\;=$$0$$1$$\vphantom{M^{\left(m\right)}_{n}}1$$1$$\vphantom{M^{\left(m\right)}_{n}}+\;1$$1$$\vphantom{M^{\left(m\right)}_{n}}+\;1$$1$$\vphantom{M^{\left(m\right)}_{n}}+\;1$$1$$\vphantom{M^{\left(m\right)}_{n}}+\;1$$1$$\vphantom{M^{\left(m\right)}_{n}}=\;5$$1$$1$$1$

$1$$1$$1$$M^{\left(3\right)}_{1}\;=$$0$$1$$\vphantom{M^{\left(m\right)}_{n}}1$$1$$\vphantom{M^{\left(m\right)}_{n}}+\;1$$1$$\vphantom{M^{\left(m\right)}_{n}}+\;1$$1$$\vphantom{M^{\left(m\right)}_{n}}+\;1$$1$$\vphantom{M^{\left(m\right)}_{n}}+\;1$$2$$\vphantom{M^{\left(m\right)}_{n}}+\;\frac{1}{2}$$1$$\vphantom{M^{\left(m\right)}_{n}}=\;\frac{11}{2}$$1$$1$

$1$$1$$1$$M^{\left(3\right)}_{2}\;=$$0$$1$$\vphantom{M^{\left(m\right)}_{n}}1$$2$$\vphantom{M^{\left(m\right)}_{n}}+\;\frac{1}{2}$$1$$\vphantom{M^{\left(m\right)}_{n}}+\;1$$1$$\vphantom{M^{\left(m\right)}_{n}}+\;1$$1$$\vphantom{M^{\left(m\right)}_{n}}+\;1$$2$$\vphantom{M^{\left(m\right)}_{n}}+\;\frac{1}{2}$$1$$\vphantom{M^{\left(m\right)}_{n}}=\;5$$1$$1$

$1$$1$$1$$M^{\left(3\right)}_{3}\;=$$0$$1$$\vphantom{M^{\left(m\right)}_{n}}1$$2$$\vphantom{M^{\left(m\right)}_{n}}+\;\frac{1}{2}$$1$$\vphantom{M^{\left(m\right)}_{n}}+\;1$$1$$\vphantom{M^{\left(m\right)}_{n}}+\;1$$1$$\vphantom{M^{\left(m\right)}_{n}}+\;1$$2$$\vphantom{M^{\left(m\right)}_{n}}+\;\frac{1}{2}$$2$$\vphantom{M^{\left(m\right)}_{n}}=\;5$$1$$1$

$1$$1$$1$$M^{\left(3\right)}_{4}\;=$$0$$1$$\vphantom{M^{\left(m\right)}_{n}}1$$2$$\vphantom{M^{\left(m\right)}_{n}}+\;\frac{1}{2}$$1$$\vphantom{M^{\left(m\right)}_{n}}+\;1$$1$$\vphantom{M^{\left(m\right)}_{n}}+\;1$$1$$\vphantom{M^{\left(m\right)}_{n}}+\;1$$3$$\vphantom{M^{\left(m\right)}_{n}}=\;\frac{9}{2}$$2$$1$$1$

Figure 7: Evolution of the supermartingale during 4 steps of the ERRW with
multiple walkers

In the figure above, we consider $k=4$ walkers whose positions are indicated
by the circled nodes. The value of $M_{n}^{\left(3\right)}$ is shown for the
first $4$ steps, and the corresponding walker $X^{\left(3\right)}$ is
highlighted in blue.

We just showed this for all walkers $m$ ($1\leq m\leq k$) with
$X^{\left(m\right)}_{0}\geq 0$. Further observe that for such a walker $m$, we
have, on the event
$B^{\left(m\right)}_{n}=\left\\{X^{\left(m\right)}_{n}>X^{\left(m\right)}_{n-1},n\leq\tau^{\left(m\right)},w\left(n-1,X^{\left(m\right)}_{n-1}\right)=1\right\\}$,
that $e^{\left(m\right)}_{n}=w\left(n,X^{\left(m\right)}_{n-1}\right)^{-1}$,
$f^{\left(m\right)}_{n}=w\left(n-1,X^{\left(m\right)}_{n-1}\right)^{-1}-w\left(n,X^{\left(m\right)}_{n-1}\right)^{-1}$,
$g^{\left(m\right)}_{n}=0$ and hence $d^{\left(m\right)}_{n}=1$. Thus, by
convergence, only a finite number of the events $B^{\left(m\right)}_{n}$ can
occur for every such walker $m$.

Now define $\Gamma$ to be the set of edges between two nonnegative integers to
the right of the integer $\max\left\\{X^{\left(m\right)}_{0}:1\leq m\leq
k\right\\}$ for which the initial weight was $1$ (all but finitely many edges
meet the latter criterion), and further define the event

$\displaystyle D_{n}$ $\displaystyle=\left\\{\exists
l:X^{\left(l\right)}_{0}\geq 0\textrm{, an edge in }\Gamma\textrm{ is crossed
between time }n-1\textrm{ and }n\textrm{ for the first time by}\right.$
$\displaystyle\hphantom{\;=\;\\{}\left.\vphantom{X^{\left(l\right)}_{0}}\textrm{any
walker, the crossing walker is }l\textrm{ and
}n\leq\tau^{\left(l\right)}\right\\}$

Clearly, $D_{n}\subseteq B^{\left(m\right)}_{n}$ for some random walker $m$
with $X^{\left(m\right)}_{0}\geq 0$, hence only a finite number of the events
$D_{n}$ can occur.

Now the proof cannot be continued along [2, Lemma 3.0] since the walkers
starting to the left of $0$ and the walkers which reach $0$ can later cross
edges to the right of $0$ without triggering $D_{n}$ and the other walkers can
then follow them without triggering $D_{n}$. So, we only proved that walkers
which never go to $0$ and start to the right of $0$ cannot visit infinitely
many edges which have not been visited before by any other walker.

###### Corollary 5.13

Assume the edge-reinforced random walk with $k$ walkers starts with an initial
configuration of the weights $w\left(0,j\right)$ such that all but finitely
many of them are $1$. Then, we have the following:

$\displaystyle\mathbb{P}\left[\exists m:X^{\left(m\right)}_{n}=0\textrm{ for
some }n\geq 0\right]$ $\displaystyle+\;$ $\displaystyle\mathbb{P}\left[\forall
m:X^{\left(m\right)}_{n}\neq 0\textrm{ for all }n\geq 0\textrm{ and
}X^{\left(m\right)}\textrm{ has finite range}\right]=1$

###### Proof

It is sufficient to show that, conditional on $A^{\textrm{C}}=\left\\{\nexists
m:X^{\left(m\right)}_{n}=0\textrm{ for some }n\geq 0\right\\}$, we have that
the second event $B=\left\\{\forall m:X^{\left(m\right)}_{n}\neq 0\textrm{ for
all }n\geq 0\textrm{ and }X^{\left(m\right)}\textrm{ has finite
range}\right\\}$ occurs a.s. Now, by 5.12, every random walker $m$ separately
either reaches $0$ or some other event $E^{\left(m\right)}$ occurs (by
symmetry, 5.12 can also be applied to random walkers which start to the left
of $0$). But now, if $A^{\textrm{C}}$ occurs, then no random walker reaches
$0$, hence the event $E^{\left(m\right)}$ occurs for every random walker $m$
where

$\displaystyle E^{\left(m\right)}$
$\displaystyle=\left\\{X^{\left(m\right)}_{n}\neq 0\textrm{ for all }n\geq
0\textrm{ and }X^{\left(m\right)}\textrm{ only visits finitely many
nodes}\right.$