$\displaystyle\hphantom{\;=\;\\{}\left.\vphantom{X^{\left(m\right)}_{n}}\textrm{which
have not been visited before by any other walker}\right\\}$

So every walker visits only finitely many nodes not visited before by any of
the other walkers. But this implies that all walkers together can only visit
finitely many nodes.

###### Corollary 5.14

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[\forall j\in\mathbb{Z}:j\textrm{ is visited
}\infty\textrm{ often by at least one of the walkers}\right]$
$\displaystyle+\;$ $\displaystyle\mathbb{P}\left[\textrm{all walkers have
finite range}\right]\qquad\qquad\qquad\qquad\qquad\qquad\;\;=\;1$

###### Proof

It suffices to show that for every $j\in\mathbb{Z}$, we have

$\displaystyle\begin{split}\mathbb{P}\left[j\textrm{ is visited
}\infty\textrm{ often by at least one of the random walkers}\right]&\\\
+\;\mathbb{P}\left[j\textrm{ is visited only finitely often and all random
walkers have finite range}\right]&=1\end{split}$ (5.1)

To see this, assume that not all random walkers have finite range. Then, if we
have proved Equation 5.1, we know that for every $j\in\mathbb{Z}$, $j$ is
visited infinitely often by one of the random walkers. Thus, conditional on
not all random walkers having finite range, all nodes are visited infinitely
often, which is equivalent to 5.14.

To show Equation 5.1, it suffices in turn to show, for every $j\in\mathbb{Z}$
and $\forall n\geq 0$:

$\displaystyle\begin{split}\mathbb{P}\left[j\textrm{ is visited by at least
one walker at a time }t\geq n\right]&\\\ +\;\mathbb{P}\left[\textrm{no walker
visits }j\textrm{ at a time }t\geq n\textrm{ and all walkers have finite
range}\right]&=1\end{split}$ (5.2)

since the given events are decreasing and increasing respectively, and their
limits correspond to the events in Equation 5.1.

But now, consider the random walkers
$\left(X^{\left(m\right)}_{n+i}\right)_{i\geq 0}$. These form again an edge-
reinforced random walk with $k$ walkers, and since until time $n$, only a
finite number of edge weights can have changed, all but finitely many edges
will still have weight $1$ at time $n$. Thus, we can apply 5.13 to the walkers
$\left(X^{\left(m\right)}_{n+i}\right)_{i\geq 0}$, which directly proves
Equation 5.2 (5.13 only proves Equation 5.2 for $j=0$ but of course we can
relabel the nodes such that any other node gets the label $0$, hence 5.13 is
valid for any choice of node).

###### Lemma 5.15

Assume the edge-reinforced random walk with $k\geq 2$ walkers starts with an
arbitrary initial configuration of the weights $w\left(0,j\right)$. Assume
further that $X^{\left(1\right)}$ and $X^{\left(2\right)}$ meet infinitely
often. Then (almost surely):

  1. (i)

if at least one of the walkers $X^{\left(1\right)}$ and $X^{\left(2\right)}$
does not have finite range, then both $X^{\left(1\right)}$ and
$X^{\left(2\right)}$ do not have finite range.

  2. (ii)

if some integer $z$ is visited infinitely often by at least one of the walkers
$X^{\left(1\right)}$ and $X^{\left(2\right)}$, then both $X^{\left(1\right)}$
and $X^{\left(2\right)}$ visit $z$ infinitely often.

  3. (iii)

if every integer is visited infinitely often by at least one of the walkers
$X^{\left(1\right)}$ and $X^{\left(2\right)}$, then both $X^{\left(1\right)}$
and $X^{\left(2\right)}$ are recurrent.

###### Proof

The proof idea is the following: whenever $X^{\left(1\right)}$ and
$X^{\left(2\right)}$ meet, we can randomly exchange their labels, i.e. we can
randomly decide whether we want to rename $X^{\left(1\right)}$ to
$X^{\left(2\right)}$ and vice versa, and the law of the edge-reinforced random
walk with the two walkers is invariant under such relabelings because the only
distinguishing feature of a random walker is his position. But now, to
construct counterexamples to the two statements in 5.15, we would have to
choose a fixed labeling for infinitely many times at which the walkers meet.
But if we randomize the labeling with a sequence of independent Bernoulli
random variables, then the probability of choosing a certain fixed labeling at
infinitely many points in the sequence is $0$, and since the law was invariant
under random relabeling, it follows that the probability of any such
counterexample is $0$. We continue with the formal proof.

Set $\tau_{1}:=\inf\left\\{n\geq
0:X^{\left(1\right)}_{n}=X^{\left(2\right)}_{n}\right\\}$ and
$\tau_{i+1}:=\inf\left\\{n>\tau_{i}:X^{\left(1\right)}_{n}=X^{\left(2\right)}_{n}\right\\}$.
If $X^{\left(1\right)},X^{\left(2\right)}$ meet infinitely often, then
$\forall n:\tau_{n}<\infty$, but the construction also works if this is not
the case. Let $\left(\omega_{i}\right)_{i\geq 1}$ be a sequence of iid random
variables with
$\mathbb{P}\left[\omega_{i}=1\right]=\frac{1}{2}=\mathbb{P}\left[\omega_{i}=0\right]$
(the $\omega_{i}$ are also independent of $\mathcal{G}_{n}$ for all $n$, i.e.
independent of the edge-reinforced random walk). Define
$\widetilde{X}^{\left(1\right)}_{n}$ and $\widetilde{X}^{\left(2\right)}_{n}$
as follows (with $\omega_{0}=0$ and $\tau_{0}=-1$):

$\displaystyle\widetilde{X}^{\left(1\right)}_{n}:=X^{\left(1,\omega\right)}_{n}$
$\displaystyle=\sum_{i\geq
0}\left(\left(1-\omega_{i}\right)X^{\left(1\right)}_{n}+\omega_{i}X^{\left(2\right)}_{n}\right)\cdot\mathbbm{1}_{\tau_{i}<n\leq\tau_{i+1}}$
$\displaystyle\widetilde{X}^{\left(2\right)}_{n}:=X^{\left(2,\omega\right)}_{n}$
$\displaystyle=\sum_{i\geq
0}\left(\left(1-\omega_{i}\right)X^{\left(2\right)}_{n}+\omega_{i}X^{\left(1\right)}_{n}\right)\cdot\mathbbm{1}_{\tau_{i}<n\leq\tau_{i+1}}$

Note that the sums collapse to a single term. $\omega_{i}=1$ means that we
switch the labels of $X^{\left(1\right)}$ and $X^{\left(2\right)}$ during the
time interval $\left(\tau_{i},\tau_{i+1}\right]$. If we consider
$\left(X^{\left(1\right)},X^{\left(2\right)}\right)$ and
$\left(\widetilde{X}^{\left(1\right)},\widetilde{X}^{\left(2\right)}\right)$
as sequences of pairs of integers, then we have

$\displaystyle\left(\widetilde{X}^{\left(i\right)}_{n}\right)_{1\leq i\leq
2,n\geq 0}$
$\displaystyle\overset{\textrm{d}}{=}\left(X^{\left(i\right)}_{n}\right)_{1\leq
i\leq 2,n\geq 0}$ (5.3)

The equality in distribution follows from the mentioned invariance of the law
of the random walk under relabelings at meeting times which is quite
intuitive, and could be proved formally by looking at cylinder events, for
example.

time$X^{\left(1\right)}$$X^{\left(2\right)}$$\mathbb{Z}$$0$$\tau_{1}=4$$\tau_{2}=16$$\tau_{3}=18$$\tau_{4}=22$$\tau_{5}=28$

time$\widetilde{X}^{\left(1\right)}$$\widetilde{X}^{\left(2\right)}$$\mathbb{Z}$$0$$\tau_{1}=4$$\tau_{2}=16$$\tau_{3}=18$$\tau_{4}=22$$\tau_{5}=28$$\omega_{0}=0$$\omega_{1}=1$$\omega_{2}=0$$\omega_{3}=1$$\omega_{4}=0$$\omega_{5}=1$

Figure 8: Label exchange lemma

The figure above illustrates how the “label exchange” of the two walkers
works. Two sample paths for the two walkers are drawn, together with meeting
points and the result of the label exchange.

We now show that any counterexamples to statements i or iii have probability
$0$:

  1. (i)

let $A$ be the event that one of the walkers
$X^{\left(1\right)},X^{\left(2\right)}$ has finite range while the other one
has infinite range, and that they meet infinitely often. It suffices to show
that $\mathbb{P}\left[A\right]=0$. Denote by $\mathbf{P}$ the probability
measure induced by the edge reinforced random walk alone and by $\mathbf{Q}$
the probability measure induced by the sequence
$\left(\omega_{i}\right)_{i\geq 1}$ alone. Then, by Equation 5.3, we have

$\displaystyle\mathbb{P}\left[A\right]=$
$\displaystyle\int\int\mathbbm{1}_{B}\;\mathrm{d}\mathbf{Q}\;\mathrm{d}\mathbf{P}$
$\displaystyle\textrm{where }B:=$ $\displaystyle\left\\{\textrm{one of
}\widetilde{X}^{\left(1\right)},\widetilde{X}^{\left(2\right)}\textrm{ has
finite range while}\right.$
$\displaystyle\left.\hphantom{\;\\{}\vphantom{\widetilde{X}^{\left(1\right)}}\textrm{the
other has infinite range, they meet infinitely often}\right\\}$

We have to show that the inner integral is $0$ almost surely with respect to
$\mathbf{P}$. Consider fixed walker sequences $X^{\left(1\right)}$ and
$X^{\left(2\right)}$. If one of
$\widetilde{X}^{\left(1\right)},\widetilde{X}^{\left(2\right)}$ should have
finite range while the other has infinite range, then, by definition of
$\widetilde{X}^{\left(1\right)}$ and $\widetilde{X}^{\left(2\right)}$, at
least one of $X^{\left(1\right)},X^{\left(2\right)}$ must have infinite range.
Of course, by definition, we also have that
$\widetilde{X}^{\left(1\right)},\widetilde{X}^{\left(2\right)}$ meet
infinitely often if, and only if, $X^{\left(1\right)},X^{\left(2\right)}$ meet
infinitely often. Hence, the indicator variable in the integral above can only
be $1$ in the case where one of the walkers
$X^{\left(1\right)},X^{\left(2\right)}$ has infinite range and the two walkers
meet infinitely often, so we only need to show that in this particular case,
the inner integral is still $0$ almost surely.

Assume $X^{\left(1\right)}$ does not have finite range (w.l.o.g.). Then, for
every $n$, one can find $i$ such that between times $\tau_{i}$ and
$\tau_{i+1}$ (all $\tau_{i}$ are finite if the two walkers meet infinitely
often), $X^{\left(1\right)}$ visits a node at distance at least $n$ from the
integer $0$. Call these times $\tau_{i_{n}}$ with $i_{n}$ strictly increasing
in $n$ (w.l.o.g.).

Now consider the walkers
$\widetilde{X}^{\left(1\right)},\widetilde{X}^{\left(2\right)}$. One of them
can have finite range only if the following holds. The same argument works for
both walkers, we do it here for $\widetilde{X}^{\left(1\right)}$ w.l.o.g.
$\widetilde{X}^{\left(1\right)}$ can only have finite range if there exists
$N$ such that for all $n\geq N$ we have $\omega_{i_{n}}=1$. Assume to the
contrary that no such $N$ exists. Then we can find arbitrarily large $n$ such
that $\omega_{i_{n}}=0$ which means that the labels of $X^{\left(1\right)}$
and $X^{\left(2\right)}$ are _not_ exchanged in the interval
$\left(\tau_{i_{n}},\tau_{i_{n}+1}\right]$. Since $X^{\left(1\right)}$ visits
a node at distance at least $n$ from $0$ in this time interval, the same holds
then for $\widetilde{X}^{\left(1\right)}$, so $\widetilde{X}^{\left(1\right)}$
would not have finite range.

But the probability that the sequence $\omega_{i_{n}}$ is $1$ for all $n\geq
N$ is $0$ for any $N$ (since the choice of $i_{n}$ only depends on the edge-
reinforced random walk, i.e. is independent of the $\omega_{i}$, and since the
probability of $\omega$ being constantly $1$ on any fixed infinite subset of
the integers is $0$ by the choice of $\omega$). Hence, the probability that
such $N$ exists is $0$, and therefore the probability that
$\widetilde{X}^{\left(1\right)}$ has finite range is $0$ as well, and the same
arguments give that the probability for $\widetilde{X}^{\left(2\right)}$
having finite range is $0$ as well (both with respect to the measure
$\mathbf{Q}$).

So the indicator variable in the integral above is $0$ almost surely w.r.t.
$\mathbf{Q}$, and hence the inner integral is always $0$, which implies that
the outer integral is also $0$ and hence $\mathbb{P}\left[A\right]=0$.

  2. (ii)

similar. Let $A$ now be the event that the integer $z$ is visited infinitely
often by at least one of the walkers $X^{\left(1\right)},X^{\left(2\right)}$,
that they meet infinitely often, and that one of them does _not_ visit $z$
infinitely often. Then, we have again:

$\displaystyle\mathbb{P}\left[A\right]=$
$\displaystyle\int\int\mathbbm{1}_{B}\;\mathrm{d}\mathbf{Q}\;\mathrm{d}\mathbf{P}$
$\displaystyle\textrm{where }B:=$ $\displaystyle\left\\{z\textrm{ visited
}\infty\textrm{ often by at least one of
}\widetilde{X}^{\left(1\right)},\widetilde{X}^{\left(2\right)}\textrm{,}\right.$
$\displaystyle\left.\hphantom{\;\\{}\vphantom{\widetilde{X}^{\left(1\right)}}\textrm{they
meet }\infty\textrm{ often, one of them visits }z\textrm{ only finitely
often}\right\\}$

We see that the indicator variable can be $1$ only if at least one of
$X^{\left(1\right)},X^{\left(2\right)}$ visits $z$ infinitely often, and
w.l.o.g. assume that this holds for $X^{\left(1\right)}$. As before, we can
construct a stricly increasing sequence $i_{n}$ such that in the time interval
$\left(\tau_{i_{n}},\tau_{i_{n}+1}\right]$, $X^{\left(1\right)}$ visits $z$.
Again as before, one of
$\widetilde{X}^{\left(1\right)},\widetilde{X}^{\left(2\right)}$, take
$\widetilde{X}^{\left(1\right)}$ w.l.o.g., can visit $z$ only finitely often
only if $\omega_{i_{n}}=1$ for all $n\geq N$ for some $N$, an event which has
again probability $0$ w.r.t. $\mathbf{Q}$.

  3. (iii)

apply ii to every integer.

###### Definition 5.16

Consider the edge-reinforced random walk with $k$ walkers. Define, for $1\leq
m\leq k$:

  * •

$\overline{X}^{\left(m\right)}:=\limsup_{n\to\infty}X^{\left(m\right)}_{n}$

  * •

$\underline{X}^{\left(m\right)}:=\liminf_{n\to\infty}X^{\left(m\right)}_{n}$

###### Theorem 5.17

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[\forall m:X^{\left(m\right)}\textrm{ is
recurrent}\right]+\mathbb{P}\left[\forall m:X^{\left(m\right)}\textrm{ has
finite range}\right]$ $\displaystyle=1$

###### Proof

We present two variants of the proof. The first is a little less formal than
the second, but hopefully easier to understand. The second variant is as
formal as possible without becoming totally incomprehensible.

Proof Variant 1 (less formal):

We have to show the following: if at least one of the walkers does not have
finite range, then, almost surely, all of them are recurrent. Showing
recurrence of all walkers is equivalent to showing that
$\overline{X}^{\left(m\right)}=\infty,\underline{X}^{\left(m\right)}=-\infty$
for all walkers $m$. Now, if at least one walker does not have finite range,
then we know by 5.14 that every integer is visited infinitely often by at
least one of the walkers. Hence, there must be walkers $m_{1}$ and $m_{2}$
with
$\overline{X}^{\left(m_{1}\right)}=\infty,\underline{X}^{\left(m_{2}\right)}=-\infty$.
For a contradiction, assume there is some walker which is not recurrent.
w.l.o.g. we assume that there is some walker $m_{3}$ with
$\underline{X}^{\left(m_{3}\right)}>-\infty$ (the proof is the same if the
other condition on the $\limsup$ is not met). Since we have
$\underline{X}^{\left(m_{2}\right)}=-\infty$, we can partition the set of
walkers into two non-empty sets:

$\displaystyle P_{1}$ $\displaystyle:=\left\\{m:1\leq m\leq k\textrm{ and
}\underline{X}^{\left(m\right)}=-\infty\right\\}$ $\displaystyle P_{2}$
$\displaystyle:=\left\\{m:1\leq m\leq k\textrm{ and
}\underline{X}^{\left(m\right)}>-\infty\right\\}$

Choose $m_{4}\in\operatorname*{arg\,max}_{m\in
P_{1}}\overline{X}^{\left(m\right)}$ and
$m_{5}\in\operatorname*{arg\,min}_{m\in P_{2}}\underline{X}^{\left(m\right)}$.
Let
$y:=\min\left\\{1,\underline{X}^{\left(m_{5}\right)}\right\\}-1\in\mathbb{Z}$.
By choice of $m_{5}$, all walkers in $P_{2}$ visit $y$ only finitely often.
Therefore, by 5.12, each of them can only visit finitely many nodes not
visited before by any other walker. We know that all nodes are visited
infinitely often by at least one of the walkers, so we must have
$\overline{X}^{\left(m_{4}\right)}=\infty$. If this was not the case, the
walkers in $P_{1}$ would only visit nodes to the left of some fixed integer,
and since the walkers in $P_{2}$ together only visit finitely many new nodes,
this would imply that there is some largest visited integer, a contradiction
to the fact that every integer is visited infinitely often (since at least one
walker does not have finite range).

Now consider $P_{3}:=\left\\{m\in
P_{1}:\overline{X}^{\left(m\right)}=\infty\right\\}\neq\varnothing$ (since
$m_{4}\in P_{3}$) and the walker $m_{5}$. If $m_{5}$ has finite range, then it
is clear that $m_{5}$ will meet any walker in $P_{3}$ infinitely often, but
this is a contradiction to 5.15 i. So $m_{5}$ must have infinite range. This
is only possible if $\overline{X}^{\left(m_{5}\right)}=\infty$. But since the
walkers in $P_{2}$, including $m_{5}$, only visit finitely many nodes not
visited before by any other walker, at least one walker $m_{6}$ in $P_{3}$
must be to the right of $m_{5}$ infinitely often in order to “free the path”
for $m_{5}$. As the walkers in $P_{3}$ are all recurrent, and as $m_{5}$ only
visits nodes to the right of $y$, this implies that $m_{5}$ meets this walker
$m_{6}$ infinitely often, which is a contradiction to 5.15 iii. Hence, we
almost surely arrive at a contradiction.

To summarize: assuming that at least one walker does not have finite range and
that least one walker is not recurrent at the same time leads (almost surely)
to a contradiction. Therefore, the assumption that this can happen must be
wrong (almost surely). This implies that if at least one walker does not have
finite range, then (almost surely) all walkers must be recurrent.

time$X^{\left(m_{2}\right)}$$X^{\left(m_{4}\right)}$$X^{\left(m_{5}\right)}$$P_{1}$$P_{2}$$P_{3}$$\mathbb{Z}$$0$

time$X^{\left(m_{2}\right)}$$X^{\left(m_{6}\right)}$$X^{\left(m_{5}\right)}$$P_{1}$$P_{2}$$P_{3}$$\mathbb{Z}$$0$

Figure 9: Illustration: proof that all walkers recurrent or all have finite
range

Above, the two possible behaviors of the walker $m_{5}$ (which are both, in
fact, almost surely impossible) are shown: either $m_{5}$ has finite range
(indicated by the light green background), but then it would meet $m_{4}$
infinitely often, or $m_{5}$ does not have finite range, but then $m_{6}$
would have to “free the path” for $m_{5}$ (indicated by the light orange
background) and $m_{5}$ would meet $m_{6}$ infinitely often. The relevant
meeting points are circled.

Proof Variant 2 (more formal):

Our goal is to show the following:

$\displaystyle\mathbb{P}\left[\vphantom{X^{\left(m_{1}\right)}}\right.\underbrace{\exists
m_{0},m_{3}:X^{\left(m_{0}\right)}\textrm{ does not have finite range and
}X^{\left(m_{3}\right)}\textrm{ is not
recurrent}}_{=:A}\left.\vphantom{X^{\left(m_{1}\right)}}\right]=0$

The indices of $m$ are chosen in such a way that they agree with proof variant
1, and they therefore do not appear in any logical order in this proof
variant. The proof proceeds by showing that the above event $A$ is subset of a
null set. We first apply 5.14. Since the intersection of $A$ and the event
$\left\\{\textrm{all walkers have finite range}\right\\}$ is empty, we can
conclude that

$\displaystyle A\subseteq$
$\displaystyle\underbrace{\left(A\cap\left\\{\textrm{every integer is visited
}\infty\textrm{ often by at least one of the
walkers}\right\\}\right)}_{B}\cup\;N$ $\displaystyle\textrm{where }N\textrm{
is a null set}$

Hence, it suffices to show that $\mathbb{P}\left[B\right]=0$. $B$ can only
occur if there are walkers $m_{1}$ and $m_{2}$ with
$\overline{X}^{\left(m_{1}\right)}=\infty,\underline{X}^{\left(m_{2}\right)}=-\infty$
since every integer is visited infinitely often (when $B$ occurs).
Furthermore, for the non-recurrent walker $m_{3}$, we necessarily have
$\overline{X}^{\left(m_{3}\right)}\neq\infty$ or
$\underline{X}^{\left(m_{3}\right)}\neq-\infty$ (when $B$ occurs). Hence,

$\displaystyle B\subseteq$ $\displaystyle\underbrace{\left\\{\exists
m_{1},m_{2},m_{3}:\overline{X}^{\left(m_{3}\right)}<\infty,\overline{X}^{\left(m_{1}\right)}=\infty,\underline{X}^{\left(m_{2}\right)}=-\infty\right\\}}_{=:C}$
$\displaystyle\cup\underbrace{\left\\{\exists
m_{1},m_{2},m_{3}:\underline{X}^{\left(m_{3}\right)}>-\infty,\overline{X}^{\left(m_{1}\right)}=\infty,\underline{X}^{\left(m_{2}\right)}=-\infty\right\\}}_{=:D}$

We show w.l.o.g. that $\mathbb{P}\left[D\right]=0$ since the proof for
$\mathbb{P}\left[C\right]=0$ is the same. When $D$ occurs, the two sets
$P_{1}:=\left\\{m:1\leq m\leq k\textrm{ and
}\underline{X}^{\left(m\right)}=-\infty\right\\}$ and $P_{2}:=\left\\{m:1\leq
m\leq k\textrm{ and }\underline{X}^{\left(m\right)}>-\infty\right\\}$ are both
non-empty (these are both random set). Choosing
$m_{5}\in\operatorname*{arg\,min}_{m\in P_{2}}\underline{X}^{\left(m\right)}$
as well as
$y:=\min\left\\{1,\underline{X}^{\left(m_{5}\right)}\right\\}-1\in\mathbb{Z}$,
we see that there is a random integer $y$ which is only visited finitely often
by the walkers in the set $P_{2}$. Hence,

$\displaystyle D\subseteq\bigcup_{y\in\mathbb{Z}}\bigcup_{n\in\mathbb{N}}$
$\displaystyle\overbrace{\left\\{\vphantom{\underline{X}^{\left(m_{2}\right)}}P_{1}\neq\varnothing,P_{2}\neq\varnothing,y\textrm{
not visited by walkers in }P_{2}\textrm{ after time }n,\right.}^{=:E_{y,n}}$
$\displaystyle\left.\hphantom{\\{}\qquad\qquad\qquad\qquad\qquad\;\;\exists
m_{1},m_{2}:\overline{X}^{\left(m_{1}\right)}=\infty,\underline{X}^{\left(m_{2}\right)}=-\infty\right\\}$

It thus suffices to show $\mathbb{P}\left[E_{y,n}\right]=0$. If we set
$\left[k\right]:=\left\\{1,\ldots,k\right\\}$ and
$\mathfrak{P}:=\mathcal{P}\left(\left[k\right]\right)\setminus\left\\{\varnothing,\left[k\right]\right\\}$
where $\mathcal{P}$ denotes the power set, then we can further write

$\displaystyle E_{y,n}\subseteq\bigcup_{P\in\mathfrak{P}}$
$\displaystyle\overbrace{\left\\{\vphantom{\underline{X}^{\left(m_{2}\right)}}P_{1}=P=\left[k\right]\setminus
P_{2},y\textrm{ not visited by walkers in }P_{2}\textrm{ after time
}n,\right.}^{=:F_{y,n,P}}$
$\displaystyle\left.\hphantom{\\{}\qquad\qquad\qquad\qquad\qquad\;\;\;\;\exists
m_{1},m_{2}:\overline{X}^{\left(m_{1}\right)}=\infty,\underline{X}^{\left(m_{2}\right)}=-\infty\right\\}$

and it suffices to show $\mathbb{P}\left[F_{y,n,P}\right]=0$ for all
$y\in\mathbb{Z},n\in\mathbb{N},P\in\mathfrak{P}$. We are now ready to apply
5.12 for every walker in the fixed set $\left[k\right]\setminus P=P_{2}$
(equality if $F_{y,n,P}$ occurs). Since the intersection of $F_{y,n,P}$ and
the event that any walker in $\left[k\right]\setminus P=P_{2}$ returns to $y$
at a time larger than $n$ is empty, we can conclude by 5.12 (as in the proof
of 5.13, only with the random walk started at time $n+1$, and with a subset of
the walkers) that

$\displaystyle F_{y,n,P}\subseteq$
$\displaystyle\overbrace{\left\\{\vphantom{\overline{X}^{\left(m_{1}\right)}}P_{1}=P,P_{2}=\left[k\right]\setminus
P,y\textrm{ not visited by walkers in }P_{2}\textrm{ after time }n\textrm{ and
the walkers}\right.}^{=:G_{y,n,P}}$
$\displaystyle\hphantom{\\{\;}\left.\vphantom{\overline{X}^{\left(m_{1}\right)}}\quad\textrm{in
}P_{2}\textrm{ only visit finitely many nodes not visited before by any other
walker,}\right.$
$\displaystyle\hphantom{\\{\;}\left.\vphantom{\overline{X}^{\left(m_{1}\right)}}\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\;\;\;\exists
m_{1},m_{2}:\overline{X}^{\left(m_{1}\right)}=\infty,\underline{X}^{\left(m_{2}\right)}=-\infty\right\\}$
$\displaystyle\cup\;\widehat{N}\qquad\textrm{ where }\widehat{N}\textrm{ is a
null set}$

and it suffices to show $\mathbb{P}\left[G_{y,n,P}\right]=0$. Choose
$m_{4}\in\operatorname*{arg\,max}_{m\in P_{1}}\overline{X}^{\left(m\right)}$.
If $G_{y,n,P}$ occurs, then we necessarily have
$\overline{X}^{\left(m_{4}\right)}=\infty$. If this was not the case, the
walkers in $P_{1}$ would only visit nodes to the left of some fixed integer,
and since the walkers in $P_{2}$ together only visit finitely many new nodes
(when $G_{y,n,P}$ occurs), this would imply that there is some largest visited
integer, a contradiction to the fact that
$\overline{X}^{\left(m_{1}\right)}=\infty$ when $G_{y,n,P}$ occurs.

Now consider the random set of recurrent walkers $P_{3}:=\left\\{m\in
P_{1}:\overline{X}^{\left(m\right)}=\infty\right\\}\neq\varnothing$ (since
$m_{4}\in P_{3}$ when $G_{y,n,P}$ occurs) and the walker
$m_{5}\in\operatorname*{arg\,min}_{m\in P_{2}}\underline{X}^{\left(m\right)}$.
If $m_{5}$ has finite range, then it is clear that $m_{5}$ will meet any
walker in $P_{3}$ infinitely often. On the other hand, if $m_{5}$ has infinite
range, then $\overline{X}^{\left(m_{5}\right)}=\infty$ since $m_{5}\in P_{2}$.
But since the walkers in $P_{2}$, including $m_{5}$, only visit finitely many
nodes not visited before by any other walker when $G_{y,n,P}$ occurs, at least
one walker $m_{6}$ in $P_{3}$ must be to the right of $m_{5}$ infinitely often
in order to “free the path” for $m_{5}$. As the walkers in $P_{3}$ are all
recurrent, and as $m_{5}$ only visits nodes to the right of $y$, this implies
that $m_{5}$ meets this walker $m_{6}$ infinitely often (when $G_{y,n,P}$
occurs). Therefore, regardless of whether $m_{5}$ has finite range or not,
there is always a recurrent walker $m_{6}\in P_{3}$ which meets $m_{5}$
infinitely often when $G_{y,n,P}$ occurs.

We now apply 5.15 iii to see that $G_{y,n,P}$ is a null set (which concludes
the proof): as done repeatedly in this proof, we find that $G_{y,n,P}$ is a
subset of a countable union of events of the form “some fixed walker is not
recurrent (corresponding to $m_{5}$) and meets some other fixed walker which
is recurrent (corresponding to $m_{6}$) infinitely often”. However, any event
of this form is a null set by 5.15 iii.

##  6 Biased Reinforced Random Walk

Here, we consider biased random walks with reinforcement. We could prove some
results, but there are also still open questions. This section therefore
presents proven results next to open questions and conjectures, and sometimes
also just possible ways to tackle a question, which would have to be pursued
further. In order to limit the length of this thesis, this section will often
only provide proof sketches or skip some proof altogether.

###  6.1 $\lambda^{\ast}$-Biased Edge-Reinforced Random Walk

The $\lambda^{\ast}$-biased edge-reinforced random walk uses the same linearly
reinforced edge weights as the LERRW, but introduces an additional bias in a
certain direction. Here, we consider a biased reinforced random walk on
$\mathbb{Z}$, so the bias can be either to the left or to the right. Formally,
define the $\lambda^{\ast}$-biased edge-reinforced random walk on $\mathbb{Z}$
as the sequence $X_{n}$ of random variables with

$\displaystyle X_{0}$ $\displaystyle=0$
$\displaystyle\mathbb{P}\left[X_{n+1}=x_{n}+1\mathrel{}\middle|\mathrel{}X_{n}=x_{n},\ldots,X_{0}=x_{0}\right]$
$\displaystyle=\frac{\lambda\cdot
w\left(n,x_{n}\right)}{w\left(n,x_{n}-1\right)+\lambda\cdot
w\left(n,x_{n}\right)}$ $\displaystyle w\left(n,z\right)$
$\displaystyle=\underbrace{w\left(0,z\right)}_{=1\textrm{
here}}+\sum_{i=0}^{n-1}\mathbbm{1}_{X_{i}=z,X_{i+1}=z+1}+\mathbbm{1}_{X_{i}=z+1,X_{i+1}=z}$

$0$$j-1$$j$$j+1$$w\left(n,j-1\right)$$w\left(n,j\right)$$\frac{w\left(n,j-1\right)}{w\left(n,j-1\right)+\lambda\cdot
w\left(n,j\right)}\quad$$\quad\frac{\lambda\cdot
w\left(n,j\right)}{w\left(n,j-1\right)+\lambda\cdot w\left(n,j\right)}$ Figure
10: Edge weights and transition probabilities for the biased walk on
$\mathbb{Z}$ at time $n$

In terms of 2.3, we take $W\left(n\right)=1+n$, so the edge weights are being
linearly reinforced, but then we introduce an additional bias by multiplying
the right edge weight with the parameter $\lambda$.

Now, consider $\lambda\in\mathbb{Q}_{>0}$ (the result can later be extended to
all $\lambda\in\mathbb{R}_{>0}$) and a single node, say $0$, the root.
Initially, the weights on both adjacent edges are $1$. Whenever the random
walk leaves $0$ along one edge, it can only return to $0$ by the same edge.
The weight of this edge will then have increased by $2$. If $\lambda=1$, then
this process is equivalent to drawing balls from an urn which initially
contains $1$ black and $1$ white ball and where a ball is replaced with $3$
balls of the same color as the ball which was drawn, i.e. the urn will contain
two more balls of the respective color than before (white balls corresponding
to the left edge, black balls to the right edge). In general, the process is
biased, and the number of balls which are put into the urn has to be adapted:

###### Lemma 6.1

Let $\lambda=\frac{p}{q}$. Consider a node $z\in\mathbb{Z}$ with initial edge
weights $w\left(0,z-1\right)=l_{0}$ and $w\left(0,z\right)=r_{0}$. If the
$\lambda^{\ast}$-biased edge-reinforced random walk is started in $z$, then
the sequence of left turns and right turns of the random walk at $z$ has the
same distribution as the sequence of white and black balls drawn from the
following urn:

  * •

Initially, the urn contains $a_{0}=q\cdot l_{0}$ white and $b_{0}=p\cdot
r_{0}$ black balls

  * •

If a white ball is drawn, it is replaced with $2q+1$ white balls (i.e. $2q$
more white balls than before)

  * •

If a black ball is drawn, it is replaced with $2p+1$ black balls (i.e. $2p$
more black balls than before)

The urn and the edge weights can be coupled such that, writing $\tau_{n}$ for
the time at which $z$ is visited for the $n$-th time,
$w\left(\tau_{n},z-1\right)=\frac{a_{n}}{q}$ and
$w\left(\tau_{n},z\right)=\frac{b_{n}}{p}$.

###### Proof Sketch

Note that, after the $n$-th draw and the $n$-th visit to the node $z$, we have
with the coupling given in 6.1:

$\displaystyle\mathbb{P}\left[X_{\tau_{n}+1}=z+1\mathrel{}\middle|\mathrel{}X_{\tau_{n}}=z,\ldots,X_{0}=x_{0}\right]$
$\displaystyle=\frac{\lambda\cdot
w\left(\tau_{n},z\right)}{w\left(\tau_{n},z-1\right)+\lambda\cdot
w\left(\tau_{n},z\right)}=\frac{\frac{p}{q}\cdot\frac{b_{n}}{p}}{\frac{a_{n}}{q}+\frac{p}{q}\cdot\frac{b_{n}}{p}}$
$\displaystyle=\frac{b_{n}}{q}\cdot\frac{q}{a_{n}+b_{n}}=\frac{b_{n}}{a_{n}+b_{n}}$

###### Lemma 6.2

Consider the $\lambda^{\ast}$-biased edge-reinforced random walk at node
$z\in\mathbb{Z}$ with $\lambda\in\mathbb{Q}_{>0}$. If $z$ is visited
infinitely often, then

  1. (i)

If $\lambda>1$, then $\frac{\lambda
w\left(n,z\right)}{w\left(n,z-1\right)+\lambda w\left(n,z\right)}$ converges
almost surely to $1$

  2. (ii)

If $\lambda<1$, then $\frac{w\left(n,z-1\right)}{w\left(n,z-1\right)+\lambda
w\left(n,z\right)}$ converges almost surely to $1$

###### Proof Sketch

Use 6.1 and Theorem 3.5 with $\mu\left(\left\\{p\right\\}\right)=1$ and
$\nu\left(\left\\{q\right\\}\right)=1$ (or vice versa if $p<q$).

###### Definition 6.3

The $\lambda^{\ast}$-biased edge-reinforced random walk is said to be

  * •

transient if it a.s. visits every node only finitely often

  * •

recurrent otherwise, i.e. if there is at least one node which is visited
infinitely often

###### Lemma 6.4

If the $\lambda^{\ast}$-biased edge-reinforced random walk is recurrent, then
all nodes are visited infinitely often almost surely.

###### Proof

If the random walk is recurrent, then there is at least one node which is
visited infinitely often, say $z$. To show that all nodes are visited
infinitely often, it suffices to show that $z$ being visited infinitely often
implies that both neighbors of $z$ are visited infinitely often (one can then
continue by induction). Assume for a contradiction that one of the neighbors,
say $y$, is visited only finitely often, and let $t$ be the time of the last
visit to $y$ (at time $t+1$, the random walk then necessarily is at $z$). We
can assume w.l.o.g. $y=z+1$ (in the other case, reflect $\mathbb{Z}$ at $z$,
set a new $\lambda^{\prime}=\frac{1}{\lambda}$ and continue as below).

Let $\tau_{1}=t+1,\tau_{2},\tau_{3},\ldots$ be the times at which $z$ is
visited after the last visit to $y$. Then, at each time $\tau_{n}$, we have

$\displaystyle\mathbb{P}\left[X_{\tau_{n}+1}=z+1=y\mathrel{}\middle|\mathrel{}X_{\tau_{n}}=z,\ldots,X_{0}=x_{0}\right]$
$\displaystyle=\frac{\lambda\cdot
w\left(\tau_{n},z\right)}{w\left(\tau_{n},z-1\right)+\lambda\cdot
w\left(\tau_{n},z\right)}$
$\displaystyle=\frac{\lambda\cdot\overbrace{w\left(t+1,z\right)}^{w_{r}}}{\lambda\cdot
w\left(t+1,z\right)+\underbrace{w\left(t+1,z-1\right)}_{w_{l}}+n-1}$
$\displaystyle\implies\mathbb{P}\left[\forall n:X_{\tau_{n}+1}\neq
y\right]=\prod_{n\geq 1}\frac{w_{l}+n-1}{\lambda w_{r}+w_{l}+n-1}$
$\displaystyle\overset{\circledast}{\leq}\exp\left(\sum_{n\geq
1}\left(\frac{w_{l}+n-1}{\lambda w_{r}+w_{l}+n-1}-1\right)\right)$
$\displaystyle\hphantom{\;=\;}=\exp\left(-\sum_{n\geq 1}\frac{\lambda
w_{r}}{\lambda w_{r}+w_{l}+n-1}\right)=0$ $\displaystyle\textrm{where
}\circledast\textrm{ holds since }\forall x\in\mathbb{R}:x$
$\displaystyle\leq\exp\left(x-1\right)$

Hence, the event $y$ being visited only finitely often has probability $0$.

Based on 6.2, it seems reasonable to conjecture that the
$\lambda^{\ast}$-biased edge-reinforced random walk is transient whenever
$\lambda\neq 1$, since at every node, the probability to go in the direction
of bias would converge to $1$ if the node was visited infinitely often. This
intuitively seems to be a contradiction: if the probability to go in one
direction goes to $1$, then every node should be visited only finitely often.
However, we did not manage to prove the following conjecture.

###### Conjecture 6.5

The $\lambda^{\ast}$-biased edge-reinforced random walk is transient for
$\lambda\neq 1$.

Note that for $\lambda=1$, the walk is recurrent since this case corresponds
to the standard LERRW on $\mathbb{Z}$.

####  6.1.1 Some Simulations

Below, the result of some simulations is presented. The
$\lambda^{\ast}$-biased edge-reinforced random walk was simulated in 100
simulations for 1 000 000 steps each, in 1 000 simulations for 100 000 steps
each and in 10 000 simulations for 10 000 steps each.

As can be seen in Figure 11, the simulated speed strongly depends on the
number of steps for which the random walk was simulated. In this case, the
speed decreased with an increasing number of simulated steps. This could
either be an indication that the speed has not yet converged and longer
simulations would be necessary or that the random walk is actually always
recurrent and hence the speed is actually zero (however, it seems intuitively
very likely that it will be transient for large values of $\lambda$). For
$\lambda=1.1$, the speed was almost indistinguishable from $0$. To see if the
walk is really recurrent, it is however also of interest when the root was
visited for the last time, since a speed of $0$ does not necessarily imply
recurrence.

$1$$1.1$$1.2$$1.3$$1.4$$1.5$$1.6$$1.7$$1.8$$0$$2\cdot 10^{-2}$$4\cdot
10^{-2}$$6\cdot 10^{-2}$$8\cdot 10^{-2}$$0.1$$0.12$$\lambda$$\textrm{average
speed}=\frac{\textrm{last position}}{\textrm{number of steps}}$$100$
simulations at $1000000$ steps$1000$ simulations at $100000$ steps$10000$
simulations at $10000$ steps Figure 11: Average speed of the random walk
$1$$1.1$$1.2$$1.3$$1.4$$1.5$$1.6$$1.7$$1.8$$0$$0.2$$0.4$$0.6$$0.8$$1$$\lambda$$\frac{\textrm{last
visit to the root}}{\textrm{total number of steps}}$$100$ simulations at
$1000000$ steps$1000$ simulations at $100000$ steps$10000$ simulations at
$10000$ steps Figure 12: Average last visit to the root by the random walk

Longer or more simulations are necessary to get reliable results (note for
example that in Figure 12, the green curve suddenly goes up for $\lambda=1.6$
which is likely not a property of the model, but a case of variation in the
simulation). However, it is already visible that for $\lambda=1.1$, the last
visit to the root occurred on average relatively late, i.e. at a noticeable
fraction of the total number of simulated steps. Indeed, the last visit to the
root seemed to occur later (compared to the total number of steps) when
simulating the walk for longer, which we would not have expected. Of course,
this could also just be a case of variation in the simulation.

The simulations do unfortunately not present any evidence which would support
6.5, but to argue about properties like recurrence and transience, which only
make sense on an infinite time horizon, is very difficult with the help of
only finite simulations.

####  6.1.2 Stochastic Approximation

To better understand the $\lambda^{\ast}$-biased edge-reinforced random walk
on $\mathbb{Z}$, it might be helpful to approximate it by reinforced walks on
finite circular graphs. We superficially present a basic idea how this could
be done. However, it is completely unclear if the analysis of the walk on a
finite circular graph will provide new insights for the walk on $\mathbb{Z}$.
Since the easiest circular graph is the triangle, we consider the
$\lambda^{\ast}$-biased edge-reinforced random walk on the triangle, defined
as follows:

$\displaystyle r\left(x\right)$
$\displaystyle=\left(x\mathrel{}\operatorname{mod}\mathrel{}3\right)+1\textrm{
the right neighbor of }x\in\left\\{1,2,3\right\\}$ $\displaystyle
l\left(x\right)$
$\displaystyle=\left(\left(x+1\right)\mathrel{}\operatorname{mod}\mathrel{}3\right)+1\textrm{
the left neighbor of }x$ $\displaystyle X_{0}$ $\displaystyle=1$
$\displaystyle\mathbb{P}\left[X_{n+1}=r\left(x_{n}\right)\mathrel{}\middle|\mathrel{}X_{n}=x_{n},\ldots,X_{0}=x_{0}\right]$
$\displaystyle=\frac{\lambda\cdot w\left(n,x_{n}\right)}{\lambda\cdot
w\left(n,x_{n}\right)+w\left(n,l\left(x_{n}\right)\right)}$ $\displaystyle
w\left(n,i\right)$ $\displaystyle=\underbrace{w\left(0,i\right)}_{=1\textrm{
here}}+\sum_{k=0}^{n-1}\mathbbm{1}_{X_{k}=i,X_{k+1}=r\left(i\right)}+\mathbbm{1}_{X_{k}=r\left(i\right),X_{k+1}=i}$
$\displaystyle c_{n,i}$
$\displaystyle=\frac{w\left(n,i\right)}{\sum_{j=1}^{3}w\left(n,j\right)}$

For simplicity, we will assume $\lambda>1$.

We call $\mathbf{c}_{n}$ the vector of normalized edge weights at time $n$,
which is located on the unit simplex and has entries $c_{n,i}$ where
$i=1,2,3$. If we assume that the normalized edge weights were fixed to some
vector $c$ (on the unit simplex), then we get a Markov chain with the
following stationary distribution $\pi_{c}$ (only the value at the node $1$ is
shown, the others follow from the symmetry of the model):

$\displaystyle\pi_{c}\left(1\right)$
$\displaystyle=\left(\lambda^{3}c_{1}c_{2}c_{3}+\lambda^{2}\left(c_{1}^{2}c_{3}+c_{2}c_{3}^{2}\right)+\lambda\left(c_{1}^{2}c_{2}+c_{1}c_{3}^{2}\right)+c_{1}c_{2}c_{3}\right)Z^{-1}$

where $Z$ is the appropriate normalizing constant.

$1$$2$$3$$\frac{\lambda c_{n,1}}{\lambda c_{n,1}+c_{n,3}}$$\frac{\lambda
c_{n,2}}{\lambda c_{n,2}+c_{n,1}}$$\frac{\lambda c_{n,3}}{\lambda
c_{n,3}+c_{n,2}}$$\frac{c_{n,3}}{\lambda c_{n,1}+c_{n,3}}$

Figure 13: Transition probabilities of the $\lambda^{\ast}$-biased ERRW on the
triangle at time $n$

(two arrows are missing for clarity)

We further define the stationary distribution on the edges
$\pi_{c}^{\textrm{edge}}$ simply by looking at the time spent on each edge
when the chain is run starting from the stationary distribution $\pi$. For
example,

$\displaystyle\pi_{c}^{\textrm{edge}}\left(1\right)$
$\displaystyle=\frac{\lambda c_{1}}{\lambda
c_{1}+c_{3}}\cdot\pi_{c}\left(1\right)+\frac{c_{1}}{\lambda
c_{2}+c_{1}}\cdot\pi_{c}\left(2\right)$

We now approximate the evolution of the time-dependent vector $\mathbf{c}_{n}$
of the edge weights:

$\displaystyle 1\ll k\ll n\implies\left(n+k\right)\mathbf{c}_{n+k}$
$\displaystyle\approx n\mathbf{c}_{n}+k\pi_{\mathbf{c}_{n}}^{\textrm{edge}}$
$\displaystyle\iff\mathbf{c}_{n+k}-\mathbf{c}_{n}$
$\displaystyle\approx\frac{k}{n+k}\left(\pi_{\mathbf{c}_{n}}^{\textrm{edge}}-\mathbf{c}_{n}\right)$
$\displaystyle\textrm{therefore approximate with
}\qquad\frac{\textrm{d}}{\textrm{d}t}\widetilde{\mathbf{c}}\left(t\right)$
$\displaystyle=\frac{1}{t}\left(\pi_{\widetilde{\mathbf{c}}\left(t\right)}^{\textrm{edge}}-\widetilde{\mathbf{c}}\left(t\right)\right)$
$\displaystyle\textrm{exponential time change to get
}\qquad\frac{\textrm{d}\mathbf{c}}{\textrm{d}t}$
$\displaystyle=\pi_{\mathbf{c}}^{\textrm{edge}}-\mathbf{c}\qquad\textrm{ with
}\widetilde{\mathbf{c}}\left(t\right)=\mathbf{c}\left(\ln\left(t\right)\right)$

This is called a stochastic approximation: we approximate the random evolution
of the vector of normalized edge weights by a differential equation. This is
possible because the changes in the vector of normalized edge weights get ever
smaller as time increases, and the randomness gets less noticeable by virtue
of the law of large numbers. To argue formally, many additional steps would be
necessary, but this approximation can already give a good intuition on what is
happening.

Without any sort of formal proof by simply looking at Figure 14, we conclude
that the normalized edge weights will eventually converge to the uniform
distribution. This probably also holds for circles with more than three nodes,
showing that the long-run behavior of the biased reinforced random walk on
circles is fundamentally different from the long-run behavior of the walk on
the integers (where at every vertex the quotient of the right edge weight
divided by the left edge weight converges to $1$).

$c_{1}=1$$c_{3}=0$$c_{2}=1$$c_{1}=0$$c_{3}=1$$c_{2}=0$

Figure 14: The vector field of the differential equation on the unit simplex

In blue, three segments of solutions to the differential equation are shown.
In red, orange and green, three actual trajectories obtained by simulating the
$\lambda^{\ast}$-biased edge-reinforced random walk are shown. The red
trajectory results from setting the initial weights to $1$ and running the
simulation for 10 000 steps. For the orange trajectory, the initial weights
were $100,450,450$ and the simulation was run for 100 000 steps; for the green
one, they were $500,2250,2250$ and the simulation ran for 500 000 steps.

This already gives an indication that approximating the wlak on $\mathbb{Z}$
with that on a finite circular graph could be very hard. Indeed, 6.2 shows
that in the long run, the ratio of the adjacent edge weights at every node
behaves fundamentally different for the two models. It could however be
possible to analyze the reinforced walk on finite circular graphs after a
finite amount of time, increasing with the size of the graph, to make the
transition from the circular graphs to $\mathbb{Z}$.

###  6.2 $\lambda^{+}$-Biased Edge-Reinforced Random Walk

Similarly to the multiplicative bias studied above, we can also consider an
additive bias. Define the $\lambda^{+}$-biased edge-reinforced random walk on
$\mathbb{Z}$ as the sequence $X_{n}$ of random variables with

$\displaystyle X_{0}$ $\displaystyle=0$
$\displaystyle\mathbb{P}\left[X_{n+1}=x_{n}+1\mathrel{}\middle|\mathrel{}X_{n}=x_{n},\ldots,X_{0}=x_{0}\right]$
$\displaystyle=\frac{\lambda+w\left(n,x_{n}\right)}{\lambda+w\left(n,x_{n}\right)+w\left(n,x_{n}-1\right)}$
$\displaystyle w\left(n,z\right)$
$\displaystyle=\underbrace{w\left(0,z\right)}_{=1\textrm{
here}}+\sum_{i=0}^{n-1}\mathbbm{1}_{X_{i}=z,X_{i+1}=z+1}+\mathbbm{1}_{X_{i}=z+1,X_{i+1}=z}$

(where we require $\lambda\geq 0$). The problem with the definition of the
$\lambda^{\ast}$–biased edge-reinforced random walk was that it could no
longer be represented as a mixture of Markov chains since the probability of
the occurrence of a certain edge sequence depended on the order in which the
edges appeared in the sequence. This is not the case with the new definition
given above. In other words, when the edge weights are represented by urns at
every node, then the sequence of draws is now exchangeable, while this was not
the case before.

Following [14, Lemma 1 and Lemma 2], the $\lambda^{+}$-biased edge-reinforced
random walk is equivalent to a mixture of MCs (or a RWRE). For shorter
notation, we will adapt the notation of 2.2 as follows: we call
$\mathbb{P}\left[X_{n+1}=x+1\mathrel{}\middle|\mathrel{}X_{n}=x\right]=P_{\mathbf{c}}\left(x,x+1\right)=:\omega_{x}$.
Instead of looking at the distribution of the random conductances, we look
directly at the distribution of the $\omega_{x}$.

$0$$x$$1-\omega_{x}$$\omega_{x}$ Figure 15: A random walk in a random
environment on $\mathbb{Z}$

The mixture of MCs equivalent to the $\lambda^{+}$-biased walk is constructed
by placing independent urns at every node which are coupled with which edges
the random walk takes. Initially, we start with $1$ black and $1+\lambda$ (we
can also have half a ball or any positive real number of balls) white balls,
the black balls representing the edge to the left of the node, the white balls
representing the edge to the right. Now, if a ball is drawn, we take the edge
corresponding to the color and in addition to the drawn ball add two more
balls of the same color (when the random walk returns to the node, the edge
weight will have increased by two). Now, for any nodes to the right of $0$,
the first time the random walk gets there, there will already be $2$ black
balls in the urn, since the edge to the left was already traversed once. For
nodes to the left of $0$, there will already be $2+\lambda$ white balls. So we
have the following urns:

  * •

at nodes $>0$, the urn initially contains $2$ black and $1+\lambda$ white
balls

  * •

at $0$, the urn initially contains $1$ black and $1+\lambda$ white balls

  * •

at nodes $<0$, the urn initially contains $1$ black and $2+\lambda$ white
balls

  * •

whenever a ball of one color is drawn, it is put back together with two more
balls of the same color

With [14, Lemma 1 and Lemma 2], we get that the reinforced random walk with
initial bias is equivalent to the mixture of Markov Chains where the
$\omega_{x}$ are independent with the following distributions (also compare
with [16, Section 5]):

$\displaystyle\textrm{for }x>0\textrm{: }$
$\displaystyle\qquad\omega_{x}\sim\operatorname{B}\left(\frac{1+\lambda}{2},\frac{2}{2}\right)$
$\displaystyle\textrm{for }x=0\textrm{: }$
$\displaystyle\qquad\omega_{x}\sim\operatorname{B}\left(\frac{1+\lambda}{2},\frac{1}{2}\right)$
$\displaystyle\textrm{for }x<0\textrm{: }$
$\displaystyle\qquad\omega_{x}\sim\operatorname{B}\left(\frac{2+\lambda}{2},\frac{1}{2}\right)$

where $\operatorname{B}$ is the beta distribution. We use the following:

###### Lemma 6.6

Let $A\sim\operatorname{B}\left(\alpha,\beta\right)$ with $\alpha,\beta>0$ and
$t\in\mathbb{R}$. Then:

$\displaystyle\mathbb{E}\left[\left(\frac{1-A}{A}\right)^{t}\right]$
$\displaystyle=\begin{cases}\frac{\Gamma\left(\alpha-t\right)\Gamma\left(\beta+t\right)}{\Gamma\left(\alpha\right)\Gamma\left(\beta\right)}&\textrm{
if }-\beta<t<\alpha\\\ \infty&\textrm{
otherwise}\end{cases}\qquad\mathbb{E}\left[\frac{1-A}{A}\right]=\begin{cases}\frac{\beta}{\alpha-1}&\textrm{
if }\alpha>1\\\ \infty&\textrm{ otherwise}\end{cases}$
$\displaystyle\mathbb{E}\left[\left(\frac{A}{1-A}\right)^{t}\right]$
$\displaystyle=\begin{cases}\frac{\Gamma\left(\alpha+t\right)\Gamma\left(\beta-t\right)}{\Gamma\left(\alpha\right)\Gamma\left(\beta\right)}&\textrm{
if }-\alpha<t<\beta\\\ \infty&\textrm{
otherwise}\end{cases}\qquad\mathbb{E}\left[\frac{A}{1-A}\right]=\begin{cases}\frac{\alpha}{\beta-1}&\textrm{
if }\beta>1\\\ \infty&\textrm{ otherwise}\end{cases}$

###### Proof

We have:

$\displaystyle\mathbb{E}\left[\left(\frac{1-A}{A}\right)^{t}\right]$
$\displaystyle=\frac{\Gamma\left(\alpha+\beta\right)}{\Gamma\left(\alpha\right)\Gamma\left(\beta\right)}\int_{0}^{1}\frac{\left(1-x\right)^{t}}{x^{t}}\cdot
x^{\alpha-1}\left(1-x\right)^{\beta-1}\;\mathrm{d}x$
$\displaystyle=\frac{\Gamma\left(\alpha+\beta\right)}{\Gamma\left(\alpha\right)\Gamma\left(\beta\right)}\int_{0}^{1}x^{\alpha-t-1}\left(1-x\right)^{\beta+t-1}\;\mathrm{d}x$
$\displaystyle=\begin{cases}\frac{\Gamma\left(\alpha+\beta\right)}{\Gamma\left(\alpha\right)\Gamma\left(\beta\right)}\cdot\frac{\Gamma\left(\alpha-t\right)\Gamma\left(\beta+t\right)}{\Gamma\left(\alpha+\beta\right)}=\frac{\Gamma\left(\alpha-t\right)\Gamma\left(\beta+t\right)}{\Gamma\left(\alpha\right)\Gamma\left(\beta\right)}&\textrm{
if }-\beta<t<\alpha\\\ \infty&\textrm{ otherwise}\end{cases}$

Hence,

$\displaystyle\mathbb{E}\left[\frac{1-A}{A}\right]$
$\displaystyle=\begin{cases}\frac{\Gamma\left(\alpha-1\right)\Gamma\left(\beta+1\right)}{\Gamma\left(\alpha\right)\Gamma\left(\beta\right)}=\frac{\beta}{\alpha-1}&\textrm{
if }-\beta<1<\alpha\\\ \infty&\textrm{ otherwise}\end{cases}$

The other statements follow from the fact that
$1-A\sim\operatorname{B}\left(\beta,\alpha\right)$.

We can use [17, Theorem 1.7] to analyze transience and recurrence. It only
applies to the situation where the $\omega_{x}$ are iid. We have only iid
variables on the positive half-line as well as iid variables on the negative
half-line, but for a moment we just assume that all $\omega_{x}$ are
distributed as the variables on the positive half-line. The $\sigma$ from [17,
Theorem 1.7] is $\frac{1-\omega_{x}}{\omega_{x}}$ in our case. We have, with
$C_{\lambda}>0$ a constant depending on $\lambda$:

$\displaystyle\mathbb{E}\left[\ln\left(\frac{1-\omega_{x}}{\omega_{x}}\right)\right]=C_{\lambda}\int_{0}^{1}\ln\left(\frac{1-x}{x}\right)x^{\frac{\lambda-1}{2}}\;\mathrm{d}x\begin{cases}>0&\textrm{
if }0\leq\lambda<1\\\ =0&\textrm{ if }\lambda=1\\\ <0&\textrm{ if
}\lambda>1\end{cases}$

Unfortunately, this integral cannot be evaluated easily and in a nice way (in
the general case; for $\lambda=1$ there is a nice representation and probably
also for $\lambda\in\mathbb{Q}$). However, WolframAlpha shows how the integral
behaves. To formally conclude here, a bit more work in analyzing the integral
would be needed.

$\lambda<1$ | $\lambda=1$ | $\lambda>1$
---|---|---
https://bit.ly/3yrjGCG | https://bit.ly/3F00yy3 | https://bit.ly/3IK0jJQ

Hence, [17, Theorem 1.7] implies that the random walk in the environment where
all $\omega_{x}$ are iid is transient to the right when $\lambda>1$, recurrent
when $\lambda=1$, and transient to the left when $\lambda<1$. But now, we are
actually considering the random environment for the $\lambda^{+}$-biased edge-
reinforced random walk. The $\omega_{x}$ with $x\leq 0$ all stochastically
dominate the $\omega_{x}$ with $x>0$ (the probability to go to the right is
higher). Hence, for the case $\lambda>1$, it is immediately (intuitively)
clear that the random walk will still be transient to the right for this
random environment, and still recurrent for $\lambda=1$. For the case
$\lambda<1$ we see that the $\lambda^{+}$-biased edge-reinforced random walk
always returns to the root from the positive half-line. Now, we already know
(e.g. by [16, Section 5]) that the edge-reinforced walk without initial bias
is recurrent. The initial bias makes it only more likely to go to the right,
hence the walk with initial bias will also be recurrent on the negative half-
line for $\lambda<1$ and therefore recurrent as a whole. We therefore get,
even though a formal proof would still be needed:

###### Theorem 6.7

The edge-reinforced random walk on $\mathbb{Z}$ with initial bias $\lambda$ is
recurrent for $0\leq\lambda\leq 1$ and transient for $\lambda>1$.

Next, we can look at the speed in the transient regime. Since the walk is only
transient to the right if it is transient at all, it suffices to look at the
distributions of $\omega_{x}$ for $x>0$ (the finite number of steps spent to
the left of the root $0$ is irrelevant for the speed). We have by 6.6:

$\displaystyle\mathbb{E}\left[\frac{1-\omega_{x}}{\omega_{x}}\right]$
$\displaystyle=\begin{cases}\infty&\textrm{ if }\lambda\leq 1\\\
\frac{2}{\lambda-1}&\textrm{ if }\lambda>1\end{cases}$

Clearly, $\frac{2}{\lambda-1}$ is (strictly) decreasing in $\lambda$ for
$\lambda>1$, and hence, we have
$\mathbb{E}\left[\frac{1-\omega_{x}}{\omega_{x}}\right]<1\iff\lambda>3$. We
now want to use [17, Theorem 1.16]. To get a statement of the type “positive
speed $\iff$ some condition”, we therefore also need to look at the following,
where we use again 6.6:

$\displaystyle\mathbb{E}\left[\frac{\omega_{x}}{1-\omega_{x}}\right]$
$\displaystyle=\infty\textrm{ for all choices of }\lambda$

Hence, by [17, Theorem 1.16]:

###### Theorem 6.8

The edge-reinforced random walk on $\mathbb{Z}$ with initial bias $\lambda$
has positive speed, if, and only if, $\lambda>3$. If this is the case, then
$\frac{X_{n}}{n}\to\frac{\lambda-3}{\lambda+1}$ almost surely. Otherwise,
$\frac{X_{n}}{n}\to 0$ almost surely.

###  6.3 Reinforced Random Walk on Transient Environment

We now look at a special case of the LERRW where the initial edge weights are
not all $1$. Define the edge-reinforced random walk on $\mathbb{Z}$ with
initially $\lambda$-biased environment as the sequence $X_{n}$ of random
variables with

$\displaystyle X_{0}$ $\displaystyle=0$
$\displaystyle\mathbb{P}\left[X_{n+1}=x_{n}+1\mathrel{}\middle|\mathrel{}X_{n}=x_{n},\ldots,X_{0}=x_{0}\right]$
$\displaystyle=\frac{w\left(n,x_{n}\right)}{w\left(n,x_{n}\right)+w\left(n,x_{n}-1\right)}$
$\displaystyle w\left(n,z\right)$
$\displaystyle=\underbrace{w\left(0,z\right)}_{:=\lambda^{z}}+\sum_{i=0}^{n-1}\mathbbm{1}_{X_{i}=z,X_{i+1}=z+1}+\mathbbm{1}_{X_{i}=z+1,X_{i+1}=z}$

where $\lambda>0$. This random walk can again be represented by a mixture of
MCs, but the $\omega_{x}$ are no longer identically distributed (they are
still independent, though).

$0$$z$$1+\lambda^{z-1}$$\lambda^{z}$ Figure 16: Edge weights of the walk on
transient environment at time of first visit to $z>0$

By Figure 16, we get the following distributions for $\omega_{x}$:

$\displaystyle\textrm{for }x>0\textrm{: }$
$\displaystyle\qquad\omega_{x}\sim\operatorname{B}\left(\frac{\lambda^{x}}{2},\frac{1+\lambda^{x-1}}{2}\right)$
$\displaystyle\textrm{for }x=0\textrm{: }$
$\displaystyle\qquad\omega_{x}\sim\operatorname{B}\left(\frac{1}{2},\frac{1}{2\lambda}\right)$
$\displaystyle\textrm{for }x<0\textrm{: }$
$\displaystyle\qquad\omega_{x}\sim\operatorname{B}\left(\frac{1+\lambda^{x}}{2},\frac{\lambda^{x-1}}{2}\right)$

The electrical network corresponding to the random environment puts the
following conductances $\mathbf{c}$ and resistances $\mathbf{r}$ on the edges:

$\displaystyle\textrm{for }z$ $\displaystyle>0\textrm{: }\qquad
c_{\left\\{z,z+1\right\\}}=\prod_{x=1}^{z}\frac{\omega_{x}}{1-\omega_{x}}\qquad
r_{\left\\{z,z+1\right\\}}=\prod_{x=1}^{z}\frac{1-\omega_{x}}{\omega_{x}}$
$\displaystyle\textrm{for }z$ $\displaystyle=0\textrm{: }\qquad
c_{\left\\{0,1\right\\}}=1\qquad r_{\left\\{0,1\right\\}}=1$
$\displaystyle\textrm{for }z-1$ $\displaystyle<0\textrm{: }\qquad
c_{\left\\{z-1,z\right\\}}=\prod_{x=z}^{0}\frac{1-\omega_{x}}{\omega_{x}}\qquad
r_{\left\\{z-1,z\right\\}}=\prod_{x=z}^{0}\frac{\omega_{x}}{1-\omega_{x}}$

The effective resistance between $0$ and $\infty$ is therefore (using the
series law for the negative and positive half-lines and the parallel law to
merge these):

$\displaystyle\mathbf{R}_{\textrm{eff}}=\left(\left(1+\sum_{z\geq
1}\prod_{x=1}^{z}\frac{1-\omega_{x}}{\omega_{x}}\right)^{-1}+\left(\sum_{z\leq
0}\prod_{x=z}^{0}\frac{\omega_{x}}{1-\omega_{x}}\right)^{-1}\right)^{-1}$

Hence, the random walk is recurrent if, and only if:

$\displaystyle\sum_{z\geq
1}\prod_{x=1}^{z}\frac{1-\omega_{x}}{\omega_{x}}=\infty=\sum_{z\leq
0}\prod_{x=z}^{0}\frac{\omega_{x}}{1-\omega_{x}}$

Otherwise, the random walk is transient. To get a better understanding, we
calculate expectations. First, for $x>0$ using 6.6:

$\displaystyle\mathbb{E}\left[\frac{1-\omega_{x}}{\omega_{x}}\right]$
$\displaystyle=\begin{cases}\frac{1+\lambda^{x-1}}{2}\cdot\left(\frac{\lambda^{x}}{2}-1\right)^{-1}=\frac{\lambda^{x-1}+1}{\lambda^{x}-2}&\textrm{
if }\frac{\lambda^{x}}{2}>1\iff\lambda^{x}>2\\\ \infty&\textrm{
otherwise}\end{cases}$

And for $x<0$:

$\displaystyle\mathbb{E}\left[\frac{\omega_{x}}{1-\omega_{x}}\right]$
$\displaystyle=\begin{cases}\frac{\lambda^{x}+1}{\lambda^{x-1}-2}&\textrm{ if
}\lambda^{x-1}>2\\\ \infty&\textrm{ otherwise}\end{cases}$

Hence, if $\lambda>2$:

$\displaystyle\mathbb{E}\left[\prod_{x=1}^{z}\frac{1-\omega_{x}}{\omega_{x}}\right]=\prod_{x=1}^{z}\frac{\lambda^{x-1}}{\lambda^{x-1}}\cdot\frac{1+\frac{1}{\lambda^{x-1}}}{\lambda-\frac{2}{\lambda^{x-1}}}=\prod_{x=1}^{z}\frac{1+\frac{1}{\lambda^{x-1}}}{\lambda-\frac{2}{\lambda^{x-1}}}$

Therefore, the expectation decreases exponentially for $\lambda>2$. This seems
to indicate transience for $\lambda>2$ but a few calculations still remain to
formally conclude. Indeed, for any $\lambda>1$, the expectation
$\mathbb{E}\left[\frac{1-\omega_{x}}{\omega_{x}}\right]$ will eventually be
finite and of order $\frac{1}{\lambda}$ for $x$ large enough, which can
probably be used to show that the walk is transient for all $\lambda>1$. The
final proof is still open, but will hopefully follow in the near future.

##  7 Conclusion

We quickly look at how the considered modifications changed the behavior of
the ERRW.

Type of walk |  Behavior
---|---
$2$ walkers on $3$-node segment |
Proven: the proportion of the left edge weight compared to the total edge
weight forms a martingale at certain stopping times, and converges to a limit
(for linear reinforcement), similar to the case with $1$ walker. Conjectured:
the limit of the left edge weight proportion is a random variable which has a
density w.r.t. the Lebesgue measure on $\left[0,1\right]$, it is not Beta-
distributed.

$k$ walkers on $\mathbb{Z}$ |
Proven: if all but finitely many initial weights are $1$, then, for almost
arbitrary reinforcement, either all walkers are recurrent or all walkers have
finite range a.s. Conjectured: for a certain reinforcement scheme, the $k$
walkers are recurrent if, and only if, $1$ walker is recurrent with the same
reinforcement scheme.

multiplicative bias on $\mathbb{Z}$ |
Proven: if a node is visited infinitely often, then the probability to go in
the direction of bias at that node converges to $1$ (for linear
reinforcement). Conjectured: the walk is transient for any bias $\lambda\neq
1$.

multiplicative bias on triangle |
Unfinished calculation: the edge weights will eventually all be of the same
order, and the walker will move around the circle with a constant speed (for
linear reinforcement).

additive bias on $\mathbb{Z}$ |
Proven (up to details): recurrent for $0\leq\lambda\leq 1$, transient for
$\lambda>1$. Positive speed for $\lambda>3$ (for linear reinforcement).

initial transient edge weights on $\mathbb{Z}$ |
Unfinished calculation: transient for $\lambda>1$ (for linear reinforcement).
Table 1: Overview of results and conjectures on modified reinforced walks

There are two main conclusions which can be drawn from this overview. First,
for reinforced random walks, having multiple random walkers moving in the same
environment which influence each other doesn’t seem to fundamentally change
the behavior in comparison to a single walker. Indeed, after working on this
topic for such a long period of time, the following (vague) conjecture seems
reasonable: if, for a given graph and given reinforcement scheme, the
reinforced random walk is recurrent for a single walker, then it is also
recurrent for any finite number of walkers influencing each other, and vice
versa. There is still a lot of work to do to get in any way closer to prove
some form of this conjecture, but analyzing various toy models seems to
indicate that this could be true. Of course, one would also have to formally
define a reinforcement scheme to make a true mathematical claim, but the
intuitive meaning should be clear.

The second conclusion is that introducing a bias can change the behavior. The
bias, which makes the walk more transient, is sometimes competing with the
reinforcement, which makes the walk more recurrent. This result is insofar
expected as on regular trees, the reinforcement is also competing with the
transient nature of a random walk on a tree. Indeed, depending on the strength
of the reinforcement, there is a phase transition between recurrence and
transience on trees, a result which we find again for the additive bias on
$\mathbb{Z}$.

All in all, the methods to prove the results given here are not new. Adding
multiple walkers and a bias complicates an already complicated model even
more. Therefore, the random walks were only analyzed on very simple graphs,
because the methods used here do not work anymore for more general classes of
graphs. Adding a bias or multiple walkers often destroys the property of
exchangeability which the basic linearly reinforced random walk with a single
walker possesses (the probability of taking a certain path only depends on how
often each edge in the path is traversed, but not on the order of traversals).
This makes the analysis harder and it is no longer possible to represent the
reinforced walk as a RWRE, which was often the tool of choice to prove
previous results. One goal of this thesis was to better understand how
reinforced walks react to variations in the model. Some steps in the right
direction were made by analyzing the behavior on simple graphs. At the same
time, better tools to analzye these complicated models are still missing. The
mathematics here was often adapted from the basic linear reinforcement case
and is thus limited to a very restricted set of graphs.

###  7.1 Outlook

Even though some new results were obtained, many open questions remain. On the
one hand, some proofs and calculations in this thesis still lack some details
or formal precision. A natural next step would be to fill these gaps to be
sure that the unfinished calculations and proof sketches actually show what
they are supposed to show. However, the answers to more interesting questions
are often only conjectured, and no proof idea has been found yet. The
following four main points would be very interesting for future research:

  * •

For the $2$ walkers on a $3$-node segment, which can also be seen as a kind of
modified, $2$-player Pólya urn, does the limit of the proportion of the left
edge weight really have a density w.r.t. the Lebesgue measure? What is the
distribution of the limit?

  * •

For $k$ walkers on $\mathbb{Z}$, is the behavior for $k$ walkers and for a
single walker identical if the same reinforcement scheme is used?

  * •

For linear reinforcement and additional multiplicative bias on $\mathbb{Z}$,
is a single walker transient for any bias $\lambda\neq 1$?

  * •

For general graphs, does the behavior of the reinforced random walk only
depend on the graph and the reinforcement scheme, but not on the (finite)
number of walkers?

In answering these question, another goal would be to find more general
techniques to analyze these types of random walks.

This thesis was really only a starting point in better understanding how
changes to the model of the reinforced random walk will affect its behavior.
While a definitive answer to the last question listed above still seems a long
way off, the other three questions seem easier to deal with and can hopefully
be answered in the near future.

## References

  * [1] Robin Pemantle. A Survey of Random Processes with Reinforcement. Probability Surveys, Vol. 4, pp. 1-79. Institute of Mathematical Statistics and Bernoulli Society, 2007. Accessible at https://arxiv.org/abs/math/0610076.
  * [2] Burgess Davis. Reinforced Random Walk. Probability Theory and Related Fields, Vol. 84, pp. 203-229. Springer-Verlag, 1990. Accessible at https://link.springer.com/article/10.1007/BF01197845.
  * [3] Tom Hutchcroft. Random Walks and Uniform Spanning Trees. Lecture notes. University of Cambridge, 2020. Accessible at http://www.its.caltech.edu/~thutch/ under https://www.dropbox.com/s/9cuw6ay03vld3nj/RW_and_USTs_Public.pdf?dl=0.
  * [4] Omer Angel, Nicholas Crawford and Gady Kozma. Localization for Linearly Edge Reinforced Random Walks. Duke Mathematical Journal, Vol. 163, No. 5, pp. 889-921. Duke University Press, 2014. Accessible at https://arxiv.org/abs/1203.4010.
  * [5] Christophe Sabot and Pierre Tarrès. Edge-Reinforced Random Walk, Vertex-Reinforced Jump Process and the Supersymmetric Hyperbolic Sigma Model. Journal of the European Mathematical Society, Vol. 17, pp. 2353-2378. European Mathematical Society, 2015. Accessible at https://arxiv.org/abs/1111.3991.
  * [6] Margherita Disertori, Christophe Sabot and Pierre Tarrès. Transience of Edge-Reinforced Random Walk. Communications in Mathematical Physics, Vol. 339, pp. 121-148. Springer-Verlag, 2015. Accessible at https://arxiv.org/abs/1403.6079.
  * [7] Rémy Poudevigne-Auboiron. Monotonicity and phase transition for the VRJP and the ERRW. Published on arXiv, 2019. Accessible at https://arxiv.org/abs/1911.02181.
  * [8] Robin Pemantle. Vertex-Reinforced Random Walk. Probability Theory and Related Fields, Vol. 92, pp. 117-136. Springer-Verlag, 1992. Accessible at https://arxiv.org/abs/math/0404041.
  * [9] Persi Diaconis and David Freedman. de Finetti’s Theorem for Markov Chains. The Annals of Probability, Vol. 8, No. 1 (Feb., 1980), pp. 115-130. Institute of Mathematical Statistics, 1980. Accessible at https://projecteuclid.org/euclid.aop/1176994828.
  * [10] Russell Lyons and Yuval Peres. Probability on Trees and Networks. Version of 6 August 2019. Cambridge University Press, 2017. Accessible at https://rdlyons.pages.iu.edu/prbtree/ (online-only corrected edition at https://rdlyons.pages.iu.edu/prbtree/book_corr.pdf).
  * [11] Stanislav Volkov. Vertex-Reinforced Random Walk on Arbitrary Graphs. The Annals of Probability, Vol. 29, No. 1 (Feb., 2001), pp. 66-91. Institute of Mathematical Statistics, 2001. Accessible at https://projecteuclid.org/euclid.aop/1008956322.
  * [12] Robin Pemantle and Stanislav Volkov. Vertex-Reinforced Random Walk on Z has Finite Range. The Annals of Probability, Vol. 27, No. 3 (Jul., 1999), pp. 1368-1388. Institute of Mathematical Statistics, 1999. Accessible at https://projecteuclid.org/euclid.aop/1022677452.
  * [13] Pierre Tarrès. Vertex-Reinforced Random Walk on Z Eventually Gets Stuck on Five Points. The Annals of Probability, Vol. 32, No. 3B (Jul., 2004), pp. 2650-2701. Institute of Mathematical Statistics, 2004. Accessible at https://arxiv.org/abs/math/0410171.
  * [14] Robin Pemantle. Phase Transition in Reinforced Random Walk and RWRE on Trees. The Annals of Probability, Vol. 16, No. 3 (Jul., 1988), pp. 1229-1241. Institute of Mathematical Statistics, 1988. Accessible at https://projecteuclid.org/euclid.aop/1176991687.
  * [15] Russell Lyons and Robin Pemantle. Random Walk in a Random Environment and First-Passage Percolation on Trees. The Annals of Probability, Vol. 20, No. 1 (Jan., 1992), pp. 125-136. Institute of Mathematical Statistics, 1992. Accessible at https://projecteuclid.org/euclid.aop/1176989920.
  * [16] Fabian Michel. Linearly Edge-Reinforced Random Walks. Bachelor’s Thesis. Technical University of Munich, 2020.
  * [17] Fred Solomon. Random Walks in a Random Environment. The Annals of Probability, Vol. 3, No. 1 (Feb., 1975), pp. 1-31. Institute of Mathematical Statistics, 1975. Accessible at https://projecteuclid.org/euclid.aop/1176996444.
  * [18] Pietro Muliere, Anna Maria Paganoni and Piercesare Secchi. A two-color, randomly reinforced urn. Journal of Statistical Planning and Inference, No. 136, pp. 1853-1874. 2006. Accessible at https://www.mate.polimi.it/biblioteca/add/qmox/mox41.pdf.
  * [19] Franz Merkl, Aniko Öry and Silke Rolles. The “Magic Formula” for Linearly Edge-Reinforced Random Walks. Statistica Neerlandica, Vol. 62, No. 3, pp. 345-363. Netherlands Society for Statistics and Operations Research, 2008. Accessible at https://www-m5.ma.tum.de/foswiki/pub/M5/Allgemeines/SilkeRollesPublications/magic-snversion.pdf.
  * [20] Franz Merkl and Silke Rolles. A Random Environment for Linearly Edge-Reinforced Random Walks on Infinite Graphs. Probability Theory and Related Fields, Vol. 138, pp. 157-176. Springer-Verlag, 2007. Accessible at https://link.springer.com/article/10.1007/s00440-006-0016-3.
  * [21] Gady Kozma. Reinforced Random Walk. Published online. 6th European Congress of Mathematics, Kraków. 2012. Accessible at https://arxiv.org/abs/1208.0364.
  * [22] Ewa Damek, Nina Gantert and Konrad Kolesko. Absolute Continuity of the Martingale Limit in Branching Processes in Random Environment. Electronic Communications in Probability, Vol. 24, pp. 1-13. Institute of Mathematical Statistics, 2019. Accessible at https://arxiv.org/abs/1210.7664.
  * [23] Noam Berger and Eviatar Procaccia. Mutually excited random walks. Published on arXiv, 2012. Accessible at https://arxiv.org/abs/1210.7664.
  * [24] Steven Lalley. Random Walks on Infinite Discrete Groups. Lecture notes. Northwestern University Summer School in Probability, 2018. Accessible at https://sites.math.northwestern.edu/~auffing/SNAP/rw-northwestern.pdf.
  * [25] Steven Lalley. One-Dimensional Random Walks. Lecture notes. University of Chicago, 2016. Accessible at http://galton.uchicago.edu/~lalley/Courses/312/RW.pdf.
  * [26] Itai Benjamini and Gady Kozma. Nonamenable Liouville Graphs. Published online. 2010. Accessible at https://arxiv.org/abs/1010.3365.
  * [27] Bruce Hill, David Lane and William Sudderth. A Strong Law for Some Generalized Urn Processes. The Annals of Probability, Vol. 8, No. 2 (Apr., 1980), pp. 214-226. Institute of Mathematical Statistics, 1980. Accessible at https://projecteuclid.org/euclid.aop/1176994772.
  * [28] Henrik Renlund. Reinforced Random Walk. Department of Mathematics, Uppsala University. 2005. Accessible at http://www.diva-portal.org/smash/record.jsf?pid=diva2%3A305167&dswid=6914
  * [29] Russell Lyons and Robin Pemantle. Correction: Random walk in a random environment and first-passage percolation on trees. The Annals of Probability, Vol. 31, No. 1 (Jan., 2003), pp. 528-529. Institute of Mathematical Statistics, 2003. Accessible at https://projecteuclid.org/euclid.aop/1046294319.
  * [30] Elie Aidékon. Transient random walks in random environment on a Galton-Watson tree. Probability Theory and Related Fields, Vol. 142, No. 3-4 (Nov., 2008), pp. 525-559. Springer, 2008. Accessible at https://arxiv.org/abs/0710.3377.
  * [31] Pablo Lessa. Recurrence vs Transience: An introduction to random walks. 2015\. Accessible at http://www.cmat.edu.uy/~lessa/otherwork.html under http://www.cmat.edu.uy/~lessa/resource/randomwalknotes.pdf.
  * [32] Russell Lyons. The Ising Model and Percolation on Trees and Tree-Like Graphs. Communications in Mathematical Physics, Vol. 125, No. 2 (Jun., 1989), pp. 337-353. Springer, 1989. Accessible at https://projecteuclid.org/euclid.cmp/1104179469.
  * [33] Russell Lyons. Random Walks and Percolation on Trees. The Annals of Probability, Vol. 18, No. 3 (Jul., 1990), pp. 931-958. Institute of Mathematical Statistics, 1990. Accessible at https://projecteuclid.org/euclid.aop/1176990730.