# Three Favorite Edges Occurs Infinitely Often for One-Dimensional Simple
Random Walk

Chen-Xu Hao1, Ze-Chun Hu1, Ting Ma1 and Renming Song2

1College of Mathematics, Sichuan University, Chengdu 610065, China
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>

2Department of Mathematics, University of Illinois, Urbana, IL 61801, USA
<EMAIL_ADDRESS>
Abstract: For a one-dimensional simple symmetric random walk $(S_{n})$, an
edge $x$ (between points $x-1$ and $x$) is called a favorite edge at time $n$
if its local time at $n$ achieves the maximum among all edges. In this paper,
we show that with probability 1 three favorite edges occurs infinitely often.
Our work is inspired by Tóth and Werner [Combin. Probab. Comput. 6 (1997)
359-369], and Ding and Shen [Ann. Probab. 46 (2018) 2545-2561], disproves a
conjecture mentioned in Remark 1 on page 368 of Tóth and Werner [Combin.
Probab. Comput. 6 (1997) 359-369].

Keywords and phrases:  Random walk, favorite edge, invariance principle for
one-side local times, Wiener process.

Mathematics Subject Classification (2020) 60F15, 60J55.

##  1 Introduction

Let $(S_{n})_{n\in\mathbb{N}}$ be a one-dimensional simple symmetric random
walk with $S_{0}=0$. Following Tóth and Werner [35], we define for any $i\geq
1$,

$\displaystyle\widetilde{S}_{i}:=\dfrac{S_{i}+S_{i-1}+1}{2},$

which characterizes the edge of $i$-th jump (edge $x$ is between points $x-1$
and $x$), and also define the “local time on the edge $x$ at time $n$” as
follows:

$\displaystyle L(x,n):=\\#\left\\{1\leq j\leq n:\widetilde{S}_{j}=x\right\\}.$
(1.1)

Hereafter, $\\#D$ denotes the cardinality of the set $D$. An edge $x$ is
called a favorite (or most visited) edge of the random walk at time $n$ if

$L(x,n)=\sup_{y\in{\mathbb{Z}}}L(y,n).$

The set of favorite edges of the random walk at time $n$ is denoted by
$\mathcal{K}(n)$. $(\mathcal{K}(n))_{n\geq 1}$ is called the favorite edge
process of the one-dimensional simple symmetric random walk. We say that three
favorite edges occurs at time $n$ if $\\#\mathcal{K}(n)=3$.

######  Theorem 1.1.

For one-dimensional simple symmetric random walk, with probability $1$, three
favorite edges occurs infinitely often.

Theorem 1.1 complements the result in [35] which showed that eventually there
are no more than three favorite edges, and disproves a conjecture mentioned in
[35, Remark 1 on page 368].

For the related problem of the number of favorite sites of one-dimensional
simple symmetric random walks, there are many more references (see Shi and
Tóth [33] for an overview). This problem was posed by Erdős and Révész [16,
17, 18, 32]. Tóth [34] proved that there are no more than three favorite sites
eventually. Ding and Shen [12] proved that with probability 1 three favorite
sites occurs infinitely often.

Besides the number of favorite sites, a series of papers focus on the
asymptotic behavior of favorite sites, see [3, 7, 8, 28]. In addition, there
are a number of papers on favorite sites for other processes including
Brownian motion, symmetric stable process, Lévy processes, random walks in
random environments and so on, see [2, 4, 13, 14, 15, 20, 21, 24, 26, 27, 29].

For papers on favorite sites of simple random walks in higher dimensions, we
refer to [1, 10, 11, 30].

Our proof of Theorem 1.1 is inspired by [12], which in turn was inspired by
[34, 35]. Following [34], we define the number of upcrossings and
downcrossings of the site $x$ by time $n$ to be

$\displaystyle\xi_{U}(x,n):=\\#\\{0<k\leq n:S_{k}=x,S_{k-1}=x-1\\},$
$\displaystyle\xi_{D}(x,n):=\\#\\{0<k\leq n:S_{k}=x,S_{k-1}=x+1\\}$

respectively. It is easy to check that

$\displaystyle\xi_{U}(x,n)-\xi_{D}(x-1,n)=\textbf{1}_{\\{0<x\leq
S_{n}\\}}-\textbf{1}_{\\{S_{n}<x\leq 0\\}}.$ (1.2)

Using (1.1) and (1.2), we can easily get (see [34])

$\displaystyle L(x,n)$ $\displaystyle=$ $\displaystyle\\#\left\\{0<j\leq
n:\widetilde{S}_{j}=x\right\\}$ (1.3) $\displaystyle=$
$\displaystyle\\#\left\\{0<j\leq
n:S_{j}=x,S_{j-1}=x-1\right\\}+\\#\left\\{0<j\leq
n:S_{j}=x-1,S_{j-1}=x\right\\}$ $\displaystyle=$
$\displaystyle\xi_{U}(x,n)+\xi_{D}(x-1,n)$ $\displaystyle=$ $\displaystyle
2\xi_{U}(x,n)+\textbf{1}_{\\{S_{n}<x\leq 0\\}}-\textbf{1}_{\\{0<x\leq
S_{n}\\}}$ $\displaystyle=$ $\displaystyle
2\xi_{D}(x-1,n)+\textbf{1}_{\\{0<x\leq S_{n}\\}}-\textbf{1}_{\\{S_{n}<x\leq
0\\}}.$

For $r\geq 1$, let $f(r)$ be the (possibly infinite) number of times when
there are exactly $r$ favorite edges:

$\displaystyle f(r):=\\#\left\\{n\geq 1:\\#\mathcal{K}(n)=r\right\\}.$

We will show that

$\displaystyle f(3)=\infty\ \ \mbox{with probability}\ 1,$ (1.4)

which implies Theorem 1.1. The idea for the proof comes from [12]. In the
proof, we need a transience result for the favorite edge process of one-
dimensional simple symmetric random walks. To prove this transience result, we
establish an invariance principle for one-side local times of random walks.

We mention in passing that, similar to [12, 34], we could have defined the
following quantity related $f(r)$:

$\widetilde{f}(r):=\\#\left\\{n\geq 1:\widetilde{S}_{n}\in\mathcal{K}(n)\mbox{
and }\\#\mathcal{K}(n)=r\right\\},$

which is the number of times at which a new favorite edge appears, tied with
$r-1$ other favorite edges. Using the recurrence of one-dimensional simple
symmetric random walk, one can easily see that $f(3)=\infty$ a.s. is
equivalent to $\widetilde{f}(3)=\infty$ a.s. See for instance, the paragraph
below [35, Theorem 1.1].

The rest of the paper is organized as follows. In Section 2, we establish an
invariance principle for one-side local times of random walks, and then use it
to prove the transience of the favorite edge process. In Section 3, we set up
the framework for our proof for Theorem 1.1. In Section 4, we give the proof
of Theorem 1.1. We emphasize that the idea for the proof of Theorem 1.1 comes
from [12], and our main contributions are the invariance principle for one-
side local times and the transience of the favorite edge process. In final
section, we give a remark.

##  2 The transience of the favorite edge process

In this section, we study the transience of the favorite edge process and
prove the following:

######  Theorem 2.1.

For any $\gamma>11$, we have

$\displaystyle\liminf_{n\to\infty}\frac{\tilde{U}(n)}{\sqrt{n}(\log
n)^{-\gamma}}=\infty\qquad a.s.,$ (2.1)

where $\tilde{U}(n):=\min\\{|x|:x\in\mathcal{K}(n)\\}$.

To prove the above theorem, we will establish an invariance principle for one-
side local times of random walks in Section 2.2. The proof of Theorem 2.1 will
be given in Section 2.3. In Section 2.1, we give a brief introduction for
invariance principle for (two-side) local times.

###  2.1 Invariance principle for local times

Recall that the (site) local time process of the random walk $(S_{n},n\geq 0)$
is defined by

$\displaystyle\xi(x,n):=\\#\left\\{k:1\leq k\leq n,S_{k}=x\right\\},\
x\in\mathbb{Z},\ n\geq 1.$

Define $\xi^{*}(n):=\sup_{x\in\mathbb{Z}}\xi(x,n).$

Let $(W(t))_{t\geq 0}$ be a one-dimensional standard Brownian motion (Wiener
process). Recall that the local time process $(\eta(x,t))_{t\geq
0,x\in\mathbb{R}}$ of $(W(t))_{t\geq 0}$ is defined by

$\displaystyle\eta(x,t):=\lim_{\varepsilon\downarrow
0}\frac{1}{2\varepsilon}\int_{0}^{t}\textbf{1}_{(x-\varepsilon,x+\varepsilon)}(W(s))ds=\lim_{\varepsilon\downarrow
0}\frac{1}{\varepsilon}\int_{0}^{t}\textbf{1}_{[x,x+\varepsilon)}(W(s))ds.$
(2.2)

Révész [31] established the following strong invariance principle with a rate
of convergence: On a rich enough probability space, as $n\to\infty$,

$\displaystyle\sup_{x\in\mathbb{Z}}|\xi(x,n)-\eta(x,n)|=o(n^{\frac{1}{4}+\varepsilon})\quad
a.s.$ (2.3)

for any $\varepsilon>0$. Csörgő and Horváth [9, Theorems 1 and 2] showed that
the Révész’s result is the best possible.

###  2.2 Invariance principle for one-side local times

Define the one-side local time of the Wiener process by

$\eta_{R}(x,t):=\lim_{\varepsilon\downarrow
0}\frac{1}{2\varepsilon}\int_{0}^{t}\textbf{1}_{[x,x+\varepsilon)}\big{(}W(s)\big{)}ds.$

Then by (2.2), we get that for any $x\in\mathbb{R}$ and $t\geq 0$,

$\displaystyle\eta_{R}(x,t)=\frac{1}{2}\eta(x,t).$ (2.4)

The goal in this subsection is to extend (2.3) to the one-side case, that is,
prove the following result.

######  Theorem 2.2.

On a rich enough probability space $(\Omega,\mathcal{F},P)$, one can define a
Wiener process $(W(t))_{t\geq 0}$ and one-dimensional simple symmetric random
walk $(S_{k})_{k\in\mathbb{N}}$ with $S_{0}=0$, such that for any
$\varepsilon>0$, as $n\to\infty$, we have

$\displaystyle\sup_{x\in\mathbb{Z}}|\xi_{D}(x,n)-\eta_{R}(x,n)|=o(n^{\frac{1}{4}+\varepsilon})\
~{}~{}~{}~{}a.s.$

Before giving the proof of Theorem 2.2, we prove the following lemma.

######  Lemma 2.3.

For any $\varepsilon>0$, we have

$\displaystyle\lim_{n\to\infty}\frac{\sup\limits_{x\in\mathbb{Z}}|\xi_{D}(x+1,n)-\xi_{D}(x,n)|}{n^{\frac{1}{4}+\varepsilon}}=0\quad
a.s.$ (2.5)

Proof. The idea of the proof comes from Csáki and Révész [6, Lemma 5], where
the corresponding problem for (two-side) local times was considered in a more
general setting. First we show that, for all $m\geq 2$ and all $\delta>0$,
there exists a constant $C$ (which may depends on $m$ but not on $n$) such
that

$\displaystyle E(|\xi_{D}(1,n)-\xi_{D}(0,n)|^{m})\leq
Cn^{\frac{m}{4}+\delta}.$ (2.6)

Define

$\displaystyle
T_{k}:=\sum_{i=1}^{k}\left(\xi_{D}(1,\alpha_{i})-\xi_{D}(1,\alpha_{i-1})-1\right),$
(2.7)

where $\alpha_{0}=0$,
$\alpha_{i}=\min\\{j>\alpha_{i-1}:S_{j}=0,S_{j-1}=1\\},\forall i\geq 1$. We
claim that

$\displaystyle E(\xi_{D}(1,\alpha_{1}))=1,\quad
E(\xi_{D}^{m}(1,\alpha_{1}))<+\infty,\forall m\geq 2.$ (2.8)

To prove this claim, we follow Kesten and Spitzer [23, Lemma 2] and define,
for $x,y\in\mathbb{Z}$,
$\tau_{0}(x):=0,\tau_{i}(x):=\min\\{n>\tau_{i-1}(x):S_{n}=x,S_{n-1}=x+1\\},\forall
i\geq 1$. Note that $\alpha_{i}=\tau_{i}(0)$. For $j\geq 0$,

$\displaystyle
M_{j}(x,y):=\sum_{\tau_{j}(x)<n\leq\tau_{j+1}(x)}\textbf{1}_{\\{S_{n}=y,S_{n-1}=y+1\\}}$

is the number of downcrossings to $y$ between the $j^{th}$ and $(j+1)^{th}$
downcrossings to $x$. In particular, $M_{0}(0,1)=\xi_{D}(1,\alpha_{1})$. By
the strong Markov property, we know that the distribution of $M_{j}(0,y)$,
$j\geq 0$, is independent of $j$, and the distribution of $M_{j}(x,y)$, $j\geq
1$, is independent of $j$. Thus we can define for $j\geq 1$,

$\displaystyle p(x,y)$ $\displaystyle:=$ $\displaystyle P(M_{j}(x,y)\neq 0)$
$\displaystyle=$ $\displaystyle P(S_{n}=y,S_{n-1}=y+1~{}\mbox{for some}\ n\
\mbox{with~{}}\tau_{j}(x)<n\leq\tau_{j+1}(x)).$

We claim that, for any $x,y\in\mathbb{Z}$ with $|x-y|=1$, it holds that
$p(x,y)=p(y,x)=1/2$. To prove this claim, it suffices to show that
$p(0,1)=p(1,0)=1/2$. When $\tau_{1}(0)<\infty$, there exists
$n_{0}=\min\\{k\geq 0:S_{k}=1\\}<\tau_{1}(0)$. Then $S_{n_{0}}=1$,
$\\{S_{n_{0}+1}=0\\}\subset\\{M_{0}(0,1)=0\\}$ and
$\\{S_{n_{0}+1}=2\\}\subset\\{M_{0}(0,1)\neq 0\\}$. Since
$P(\tau_{1}(0)<\infty)=1$, we have

$\displaystyle p(0,1)=P(M_{0}(0,1)\neq 0,\tau_{1}(0)<\infty)$
$\displaystyle=P(S_{n_{0}+1}=0,M_{0}(0,1)\neq
0,\tau_{1}(0)<\infty)+P(S_{n_{0}+1}=2,M_{0}(0,1)\neq 0,\tau_{1}(0)<\infty)$
$\displaystyle=P(S_{n_{0}+1}=2)=\frac{1}{2}.$

Similarly, there exists $n_{1}=\min\\{k\geq
0:S_{k}=1,S_{k-1}=2\\}<\tau_{1}(1)$, then

$\displaystyle p(1,0)=P(S_{n_{1}+1}=2,M_{1}(1,0)\neq
0)+P(S_{n_{1}+1}=0,M_{1}(1,0)\neq 0)$
$\displaystyle=P(S_{n_{1}+1}=0)=\frac{1}{2}.$

Combining the claim above with the strong Markov property and the fact
$S_{\tau_{j}(x)}=S_{\tau_{j+1}(x)}=x$, we get

$P(M_{j}(0,1)=k)=\left\\{\begin{array}[]{ll}1-p(0,1)=\frac{1}{2},&\mbox{if}\
k=0,\\\ p(0,1)[1-p(1,0)]^{k-1}p(1,0)=\frac{1}{2^{k+1}},&\text{if}\ k\geq
1.\end{array}\right.$

It follows that

$\displaystyle
E(\xi_{D}(1,\alpha_{1}))=E(M_{j}(0,1))=\sum_{k=1}^{\infty}k\cdot\frac{1}{2^{k+1}}=1,$
$\displaystyle
E(\xi_{D}^{m}(1,\alpha_{1}))=E(M_{j}^{m}(0,1))=\sum_{k=1}^{\infty}k^{m}\cdot\frac{1}{2^{k+1}}<+\infty,$

which implies that (2.8) holds.

It follows from the strong Markov property that $T_{k}$ is a sum of i.i.d.
r.v.’s with mean $0$ and finite moments of all orders. Therefore by Chung [5]
and the $L^{p}$-maximal inequality for martingales, we have

$\displaystyle E(|T_{k}|^{m})\leq C_{1}k^{\frac{m}{2}}$ (2.9)

and for any $\delta_{1}>0$,

$\displaystyle E\left(\max_{k\leq
n^{\frac{1}{2}+\delta_{1}}}|T_{k}|^{m}\right)\leq
C_{2}n^{\frac{m}{4}+\frac{m\delta_{1}}{2}}.$ (2.10)

Note that

$\displaystyle\xi_{D}(1,\alpha_{D_{n}})-\xi_{D}(0,n)\leq\xi_{D}(1,n)-\xi_{D}(0,n)\leq\xi_{D}(1,\alpha_{D_{n}+1})-(\xi_{D}(0,n)+1)+1,$

where $D_{n}=\xi_{D}(0,n)$. Thus on the event $\\{D_{n}+1\leq
n^{\frac{1}{2}+\delta_{1}}\\}$, we have

$\displaystyle|\xi_{D}(1,n)-\xi_{D}(0,n)|\leq\max_{1\leq k\leq
n^{\frac{1}{2}+\delta_{1}}}|T_{k}|+1.$

Hence

$\displaystyle E(|\xi_{D}(1,n)-\xi_{D}(0,n)|^{m})\leq CE\left(\max_{1\leq
k\leq
n^{\frac{1}{2}+\delta_{1}}}(|T_{k}|+1)^{m}\right)+n^{m}P\left(D_{n}+1\geq
n^{\frac{1}{2}+\delta_{1}}\right).$ (2.11)

Let $N_{n}=N(0,n)=\\#\\{k:0<k\leq n,S_{k}=0\\}$, then according to Kesten and
Spitzer [23], $E(N_{n}^{m})=O(n^{\frac{m}{2}})$. Combining this with the fact
that $0\leq D_{n}\leq N_{n}$, we get that $E(D_{n}^{m})=O(n^{\frac{m}{2}})$.
Then by Markov’s inequality, (2.10) and (2.11), letting $\delta_{1}$ be small
enough, we obtain (2.6).

By repeating the argument above and noticing that
$p(-1,0)=p(0,-1)=\frac{1}{2}$, we can obtain the inequality (2.6) with
$\xi_{D}(1,n)$ replaced by $\xi_{D}(-1,n)$.

It is easy to see that for any $x\in\mathbb{Z}$,

$\displaystyle E(|\xi_{D}(x+1,n)-\xi_{D}(x,n)|^{m})\leq
Cn^{\frac{m}{4}+\delta},$ (2.12)

where the constant $C$ does not depend on $x$, because
$\xi_{D}(x+1,n)-\xi_{D}(x,n)$ is stochastically smaller than
$\max(|\xi_{D}(1,n)-\xi_{D}(0,n)|,|\xi_{D}(-1,n)-\xi_{D}(0,n)|)$.

Choosing $m=\frac{2+\delta}{\varepsilon}$, we obtain by Markov’s inequality
that

$\displaystyle
P\Big{(}|\xi_{D}(x+1,n)-\xi_{D}(x,n)|>n^{\frac{1}{4}+\varepsilon}\Big{)}\leq\dfrac{C}{n^{2}}$

and hence

$\displaystyle P\left(\sup_{|x|<(n\log
n)^{\frac{1}{2}}}|\xi_{D}(x+1,n)-\xi_{D}(x,n)|>n^{\frac{1}{4}+\varepsilon}\right)\leq\dfrac{2C(\log
n)^{\frac{1}{2}}}{n^{\frac{3}{2}}}.$

Therefore, by the Borel-Cantelli Lemma, we get that

$\displaystyle\lim_{n\to+\infty}\dfrac{\sup_{|x|\leq(n\log
n)^{\frac{1}{2}}}|\xi_{D}(x+1,n)-\xi_{D}(x,n)|}{n^{\frac{1}{4}+\varepsilon}}=0~{}~{}~{}~{}a.s.$

The law of the iterated logarithm for $S_{n}$ implies that
$\xi_{D}(x,n)=0~{}~{}a.s.$ for $|x|\geq(n\log n)^{\frac{1}{2}}$ and $n$
sufficiently large, hence (2.5) holds.

Proof of Theorem 2.2. This proof is inspired by Révész [31], and Csörgő and
Horváth [9]. Let $(W(t))_{t\geq 0}$ be a Wiener process and define
$\tau_{0}:=0,\tau_{1}:=\inf\\{t:t>0,|W(t)|=1\\},\tau_{n}:=\inf\\{t:t>\tau_{n-1},|W(t)-W(\tau_{n-1})|=1\\},\forall
n\geq 2$. Then $X_{i}=W(\tau_{i})-W(\tau_{i-1})(i\geq 1)$ are i.i.d. r.v.’s
with $P\\{X_{i}=1\\}=P\\{X_{i}=-1\\}=1/2$, and $\tau_{i}-\tau_{i-1}(i\geq 1)$
are i.i.d. r.v.’s with $E(\tau_{i}-\tau_{i-1})=1$ and
$E(\tau_{i}-\tau_{i-1})^{2}<\infty$. Put $\sigma^{2}=E(\tau_{1}-1)^{2}$.
Define $S_{k}=X_{1}+\cdots+X_{k}=W(\tau_{k})$.

Let
$a_{i}(x)=\eta(x,\tau_{v(i)+1})-\eta(x,\tau_{v(i)-1}),b_{i}(x)=\eta_{R}(x,\tau_{v(i)+1})-\eta_{R}(x,\tau_{v(i)-1})(i\in\mathbb{Z}^{+})$,
where $v(1)=\min\\{k\geq
0,W(\tau_{k})(=S_{k})=x\\},v(n)=\min\\{k>v(n-1),W(\tau_{k})(=S_{k})=x\\},\forall
n\geq 2$. Then by (2.4), we have

$\displaystyle b_{i}(x)=\frac{a_{i}(x)}{2}.$ (2.13)

Kesten [22] showed

$\displaystyle\limsup_{n\to\infty}(2n\log\log
n)^{-\frac{1}{2}}\cdot\sup_{x\in\mathbb{Z}}\xi(x,n)=1~{}~{}~{}~{}~{}a.s.$
(2.14)

Csörgő and Horváth [9, (2.7)] says that

$\displaystyle\max_{-n\leq x\leq
n}\left|\sum_{i=1}^{\xi(x,n)}a_{i}(x)-\eta(x,\tau_{n})\right|=O(\log n)\quad
a.s.,$

which together with (2.4) and (2.13) implies that

$\displaystyle\max_{-n\leq x\leq
n}\left|\sum_{i=1}^{\xi(x,n)}b_{i}(x)-\eta_{R}(x,\tau_{n})\right|=O(\log
n)~{}~{}~{}~{}~{}a.s.$ (2.15)

By [9, (2.8)] and (2.13), we have

$\displaystyle P\left\\{\max_{-k\leq x\leq
k}\left|\sum_{i=1}^{k}\left(b_{i}(x)-\frac{1}{2}\right)\right|>C_{1}(k\log
k)^{\frac{1}{2}}\right\\}\leq C_{2}k^{-2}.$ (2.16)

Combining this with the Borel-Cantelli Lemma and then using (2.14), we get
that

$\displaystyle\limsup_{n\to\infty}\frac{\max\limits_{-n\leq x\leq
n}|\sum_{i=1}^{\xi(x,n)}b_{i}(x)-\frac{\xi(x,n)}{2}|}{n^{\frac{1}{4}}\cdot(\log
n)^{\frac{1}{2}}\cdot(\log\log n)^{\frac{1}{4}}}\leq C_{3}~{}~{}~{}~{}~{}a.s.$
(2.17)

Since $\tau_{i}-\tau_{i-1},i\geq 1,$ are i.i.d. r.v.’s with $E\tau_{1}=1$ and
$\sigma^{2}=E(\tau_{1}-1)^{2}<\infty$, by the law of iterated logarithm, we
have

$\displaystyle\limsup_{n\to\infty}\frac{|\tau_{n}-n|}{\sqrt{2\sigma^{2}n\log\log
n}}=1~{}~{}~{}~{}~{}a.s.$ (2.18)

By [9, (2.11)] and (2.4), we have

$\displaystyle\limsup_{n\to\infty}\dfrac{\sup\limits_{x}|\eta_{R}(x,n\pm
g(n))-\eta_{R}(x,n)|}{n^{\frac{1}{4}}\cdot(\log n)^{\frac{1}{2}}\cdot(\log\log
n)^{\frac{1}{4}}}\leq C_{4}\quad a.s.,$

where $g(n)=(4\sigma^{2}n\log\log n)^{\frac{1}{2}}$. (Note that there is a
minor typo in the line below [9, (2.11)], the $-\frac{1}{2}$ there should be
$\frac{1}{2}$.) Thus by (2.18) we have

$\displaystyle\limsup_{n\to\infty}\dfrac{\sup\limits_{x}|\eta_{R}(x,\tau_{n})-\eta_{R}(x,n)|}{n^{\frac{1}{4}}\cdot(\log
n)^{\frac{1}{2}}\cdot(\log\log n)^{\frac{1}{4}}}\leq C_{5}~{}~{}~{}~{}~{}a.s.$
(2.19)

Note that $\xi_{D}(x,n)=0$ if $|x|>n$ and that
$\lim_{n\to\infty}\sup_{|x|>n}\eta_{R}(x,n)=0\ a.s.$ Thus

$\displaystyle\lim_{n\to\infty}\sup_{|x|>n}\dfrac{\xi_{D}(x,n)-\eta_{R}(x,n)}{n^{\frac{1}{4}+\varepsilon}}=0~{}~{}~{}~{}~{}a.s.$
(2.20)

Now by (2.15), (2.17), (2.19), (2.20) and Lemma 2.3, we obtain

$\displaystyle\limsup_{n\to\infty}\dfrac{\sup\limits_{x}|\xi_{D}(x,n)-\eta_{R}(x,n)|}{n^{\frac{1}{4}+\varepsilon}}$
$\displaystyle\leq\limsup_{n\to\infty}\dfrac{\sup\limits_{x\leq
n}|\xi_{D}(x,n)-\frac{\xi(x,n)}{2}|+\sup\limits_{x\leq
n}|\frac{\xi(x,n)}{2}-\sum_{i=1}^{\xi(x,n)}b_{i}(x)|}{n^{\frac{1}{4}+\varepsilon}}$
$\displaystyle\quad+\limsup_{n\to\infty}\dfrac{\sup\limits_{x\leq
n}|\sum_{i=1}^{\xi(x,n)}b_{i}(x)-\eta_{R}(x,\tau_{n})|+\sup\limits_{x\leq
n}|\eta_{R}(x,\tau_{n})-\eta_{R}(x,n)|}{n^{\frac{1}{4}+\varepsilon}}$
$\displaystyle\quad+\lim_{n\to\infty}\sup\limits_{|x|>n}\dfrac{|\xi_{D}(x,n)-\eta_{R}(x,n)|}{n^{\frac{1}{4}+\varepsilon}}$
$\displaystyle\leq\limsup_{n\to\infty}\dfrac{\sup\limits_{x\leq
n}\frac{|\xi_{D}(x,n)-\xi_{D}(x-1,n)|+1}{2}+\sup\limits_{x\leq
n}|\frac{\xi(x,n)}{2}-\sum_{i=1}^{\xi(x,n)}b_{i}(x)|}{n^{\frac{1}{4}+\varepsilon}}$
$\displaystyle\quad+\limsup_{n\to\infty}\dfrac{\sup\limits_{x\leq
n}|\sum_{i=1}^{\xi(x,n)}b_{i}(x)-\eta_{R}(x,\tau_{n})|+\sup\limits_{x\leq
n}|\eta_{R}(x,\tau_{n})-\eta_{R}(x,n)|}{n^{\frac{1}{4}+\varepsilon}}$
$\displaystyle\quad+\lim_{n\to\infty}\sup\limits_{|x|>n}\dfrac{|\xi_{D}(x,n)-\eta_{R}(x,n)|}{n^{\frac{1}{4}+\varepsilon}}$
$\displaystyle=0\ a.s.,$

where we used the following fact

$\left|\xi_{D}(x,n)-\frac{\xi(x,n)}{2}\right|=\frac{|\xi_{D}(x,n)-\xi_{U}(x,n)|}{2}\leq\frac{|\xi_{D}(x,n)-\xi_{D}(x-1,n)|+1}{2}.$

The proof is complete.

###  2.3 Proof of Theorem 2.1

Set

$\displaystyle\eta_{R}^{*}(n):=\sup_{x\in\mathbb{R}}\eta_{R}(x,n),\quad\eta^{*}(n):=\sup_{x\in\mathbb{R}}\eta(x,n),$
$\displaystyle\xi_{D}^{*}(n):=\sup_{x\in\mathbb{Z}}\xi_{D}(x,n),\quad
T_{r}:=\inf\\{n>0:\eta_{R}(0,n)\geq r\\},$ $\displaystyle
I_{R}(h,n):=\sup_{|x|\leq h}\eta_{R}(x,n),$

and

$\displaystyle\mathcal{V}(n):=\\{x\in\mathbb{Z}:\eta_{R}(x,n)=\eta_{R}^{*}(n)\\},\quad\mathcal{U}(n):=\\{x\in\mathbb{Z}:\xi_{D}(x,n)=\xi_{D}^{*}(n)\\}.$

It is easy to see that Theorem 2.1 is a consequence of the following two
propositions.

######  Proposition 2.4.

If $x\in\mathcal{K}(n)$, then $x-1\in\mathcal{U}(n)$.

######  Proposition 2.5.

For any $\gamma>11$, we have

$\displaystyle\liminf_{n\to\infty}\frac{U(n)}{\sqrt{n}(\log
n)^{-\gamma}}=\infty\qquad a.s.,$ (2.21)

where $U(n):=\min\\{|x|:x\in\mathcal{U}(n)\\}$.

####  2.3.1 Proof of Proposition 2.4.

Assume that $x\in\mathcal{K}(n)$, that is, $x$ is a favorite edge at time $n$.
We want to prove that $x-1\in\mathcal{U}(n)$. Let $\xi_{D}(x-1,n)=h$ for some
nonnegative integer $h$. Then by (1.3), we know that
$L(x,n)\in\\{2h-1,2h,2h+1\\}$. We will prove $x-1\in\mathcal{U}(n)$ by
contradiction. Suppose that $x-1\notin\mathcal{U}(n)$. Then for any
$y\in\mathcal{U}(n)$, we have $\xi_{D}(y,n)\geq h+1$.

Case 1. $L(x,n)=2h-1$ or $2h$. By (1.3), we get that for any
$y\in\mathcal{U}(n)$,

$L(y+1,n)\geq 2\xi_{D}(y,n)-1\geq 2(h+1)-1=2h+1.$

This implies that $x\notin\mathcal{K}(n)$, which is a contradiction.

Case 2. $L(x,n)=2h+1$. Now by (1.3), we know that $0<x\leq S_{n}$. For any
$y\in\mathcal{U}(n)$, we have the following two subcases:

Case 2.1. $y\leq 0$ or $y>S_{n}$. Now by (1.3), we get that

$L(y+1,n)=2\xi_{D}(y,n)\geq 2(h+1)=2h+2.$

This implies that $x\notin\mathcal{K}(n)$, which is a contradiction.

Case 2.2. $0<y\leq S_{n}$. Now by (1.3), we get that

$L(y+1,n)=2\xi_{D}(y,n)+1\geq 2(h+1)+1=2h+3.$

This implies that $x\notin\mathcal{K}(n)$, which is a contradiction.

Thus we must have $x-1\in\mathcal{U}(n)$. The proof is complete.

####  2.3.2 Proof of Proposition 2.5.

To prove Proposition 2.5, we need several lemmas. By [3, (5.1)] and (2.4), we
have

######  Lemma 2.6.

For any $\alpha>5$ and $\varepsilon>0$, there exists $n_{0}$ such that, with
probability one, we have

$\displaystyle\eta_{R}^{*}(n)>I_{R}\left(\frac{\sqrt{n}}{(\log
n)^{2\alpha+1+\varepsilon}},n\right)+\frac{1}{2}n^{\frac{1}{2}-\varepsilon},\quad
n\geq n_{0}.$

By [3, Lemma 5.3] and (2.4), we have

######  Lemma 2.7.

For every $\varepsilon>0$

$\displaystyle\sup_{k\in\mathbb{Z}}\sup_{t\leq
n,x\in[k.k+1]}|\eta_{R}(x,t)-\eta_{R}(k,t)|=o(n^{\frac{1}{4}+\varepsilon})~{}~{}~{}~{}a.s.$

######  Lemma 2.8.

$\displaystyle|\eta_{R}^{*}(n)-\xi_{D}^{*}(n)|=o(n^{\frac{1}{4}+\varepsilon})~{}~{}~{}~{}a.s.$

Proof. We have

$\displaystyle\eta_{R}^{*}(n)-\xi_{D}^{*}(n)$ $\displaystyle=$
$\displaystyle\sup_{x\in\mathbb{R}}\eta_{R}(x,n)-\sup_{x\in\mathbb{Z}}\xi_{D}(x,n)$
$\displaystyle=$ $\displaystyle\sup_{x\in\mathbb{R},y\in\mathbb{Z},|x-y|\leq
1}\left[\eta_{R}(x,n)-\xi_{D}(y,n)+\xi_{D}(y,n)\right]-\sup_{x\in\mathbb{Z}}\xi_{D}(x,n)$
$\displaystyle\leq$
$\displaystyle\sup_{x\in\mathbb{R},y\in\mathbb{Z},|x-y|\leq
1}\left(\eta_{R}(x,n)-\xi_{D}(y,n)\right)+\sup_{y\in\mathbb{Z}}\xi_{D}(y,n)-\sup_{x\in\mathbb{Z}}\xi_{D}(x,n)$
$\displaystyle=$ $\displaystyle\sup_{x\in\mathbb{R},y\in\mathbb{Z},|x-y|\leq
1}\left(\eta_{R}(x,n)-\xi_{D}(y,n)\right)$ $\displaystyle\leq$
$\displaystyle\sup_{x\in\mathbb{R},y\in\mathbb{Z},|x-y|\leq
1}\left|\eta_{R}(x,n)-\xi_{D}(y,n)\right|.$

Similarly, we have

$\displaystyle\xi_{D}^{*}(n)-\eta_{R}^{*}(n)\leq\sup_{x\in\mathbb{R},y\in\mathbb{Z},|x-y|\leq
1}\left|\eta_{R}(x,n)-\xi_{D}(y,n)\right|.$

Hence

$\displaystyle\left|\eta_{R}^{*}(n)-\xi_{D}^{*}(n)\right|\leq\sup_{x\in\mathbb{R},y\in\mathbb{Z},|x-y|\leq
1}\left|\eta_{R}(x,n)-\xi_{D}(y,n)\right|.$

Then by Lemma 2.7 and Theorem 2.2, we get

$\displaystyle|\eta_{R}^{*}(n)-\xi_{D}^{*}(n)|$
$\displaystyle\leq\sup_{x\in\mathbb{R},y\in\mathbb{Z},|x-y|\leq
1}|\eta_{R}(x,n)-\eta_{R}(y,n)+\eta_{R}(y,n)-\xi_{D}(y,n)|$
$\displaystyle\leq\sup_{x\in\mathbb{R},y\in\mathbb{Z},|x-y|\leq
1}|\eta_{R}(x,n)-\eta_{R}(y,n)|+\sup_{y\in\mathbb{Z}}|\eta_{R}(y,n)-\xi_{D}(y,n)|$
$\displaystyle=o(n^{\frac{1}{4}+\varepsilon}).$

The proof is complete.

Proof of Proposition 2.5. By Theorem 2.2 we can find a simple symmetric random
walk $S_{n}$ and a Wiener process $W(t)$ on the same probability space such
that for each $\varepsilon>0$,

$\displaystyle\sup_{x\in\mathbb{Z}}|\xi_{D}(x,n)-\eta_{R}(x,n)|=o(n^{\frac{1}{4}+\varepsilon})~{}~{}~{}~{}~{}a.s.$
(2.22)

For any $\alpha>5$ and $\varepsilon>0$, let
$K_{n}=\max_{x\in\mathbb{Z},|x|\leq\sqrt{n}(\log
n)^{-(2\alpha+1+\varepsilon)}}\xi_{D}(x,n)$. By (2.22), Lemmas 2.6 and 2.8,

$\displaystyle\xi_{D}^{*}(n)$ $\displaystyle\geq$
$\displaystyle\eta_{R}^{*}(n)-cn^{\frac{1}{4}+\varepsilon}$
$\displaystyle\geq$ $\displaystyle I_{R}\left(\frac{\sqrt{n}}{(\log
n)^{2\alpha+1+\varepsilon}},n\right)+\frac{1}{2}n^{\frac{1}{2}-\varepsilon}-cn^{\frac{1}{4}+\varepsilon}$
$\displaystyle\geq$ $\displaystyle
K_{n}+\frac{1}{2}n^{\frac{1}{2}-\varepsilon}-2cn^{\frac{1}{4}+\varepsilon}>K_{n}$

for $n$ sufficiently large. Thus the most visited edges of $S_{n}$ must be
larger in absolute value than $\sqrt{n}(\log n)^{-(2\alpha+1+\varepsilon)}$
for $n$ large. For any $\gamma>11$, choosing $\alpha$ and $\varepsilon$ so
that $2\alpha+1+\varepsilon<\gamma$, we obtain (2.21). The proof is complete.

##  3 Preliminaries for the proof of Theorem 1.1

In this section, we make some preparations for the proof of Theorem 1.1. These
preparations are modifications of the corresponding materials from [12] and
[34].

###  3.1 Three consecutive favorite edges

We define the inverse edge local times by

$\displaystyle T_{U}(x,k):=\min\\{n\geq
1:\xi_{U}(x,n)=k\\}\quad\mbox{and}\quad T_{D}(x,k):=\min\\{n\geq
1:\xi_{D}(x,n)=k\\}.$

For any $x\in\mathbb{Z}$, define

$\displaystyle u(x)$ $\displaystyle:=$
$\displaystyle\sum_{n=1}^{\infty}\textbf{1}_{\\{S_{n-1}=x-2,S_{n}=x-1,x\in\mathcal{K}(n),\\#\mathcal{K}(n)=3\\}}$
$\displaystyle=$
$\displaystyle\sum_{k=1}^{\infty}\textbf{1}_{\\{x\in\mathcal{K}(T_{U}(x-1,k)),\\#\mathcal{K}(T_{U}(x-1,k))=3\\}}$
$\displaystyle=$
$\displaystyle\sum_{k=0}^{\infty}\sum_{h=1}^{\infty}\textbf{1}_{\\{x\in\mathcal{K}(T_{U}(x-1,k+1)),\\#\mathcal{K}(T_{U}(x-1,k+1))=3,L(x,T_{U}(x-1,k+1))=h\\}}.$

Thus $f(3)\geq\sum_{x\in\mathbb{Z}}u(x)$.

For $x\in\mathbb{Z}$, $h,k\in\mathbb{N}$, we define

$\displaystyle A_{x,h}^{(k)}$ $\displaystyle:=$
$\displaystyle\left\\{\mathcal{K}(T_{U}(x-1,k+1))=\\{x,x+1,x+2\\},L(x,T_{U}(x-1,k+1))=h\right\\}.$
(3.1)

Here we use $T_{U}(x-1,k+1)$ instead of $T_{U}(x,k+1)$, which was used in
[12], due to the the following two reasons:

  * (i)

If $x>0$, then by the definition of local time on the edge $x$ at the time
$n=T_{U}(x,k+1)$, the set of favorite edges $\mathcal{K}(n)$ is not equal to
$\\{x,x+1,x+2\\}$, since $L(x+1,n)$ and $L(x+2,n)$ are even numbers and
$L(x,n)$ is an odd number.

  * (ii)

$T_{U}(x-1,k+1)$ is useful to obtain the lower bound on the first moment in
Section 4.1.

Note that the definition of $T_{U}(x-1,k+1)$ implies $S_{T_{U}(x-1,k+1)}=x-1$
and $\xi_{U}\left(x-1,T_{U}(k+1,x-1)\right)=k+1$. Thus by (1.3), we have for
$x\geq 1$

$\displaystyle L(x-1,T_{U}(x-1,k+1))=2k+2-\textbf{1}_{\\{0<x-1\\}}.$

Hence

$L(x-1,T_{U}(x-1,k+1))=\left\\{\begin{aligned} &2k+1,&\text{if~{}$x>1$},\\\
&2k+2,&\text{if~{}$x=1$}.\end{aligned}\right.$

Again using (1.3), we can easily see that, when $x\geq 1$, the $h$ in
$A_{x,h}^{(k)}$ has to be even. In the following, we implicitly assume $x>1$,
which implies that $L(x-1,T_{U}(x-1,k+1))=2k+1$, unless explicitly mentioned
otherwise.

We write the events $A_{x,h}^{(k)}$ in terms of $T_{U}(x-1,k+1)$ since the
events defined this way match the form of the Ray-Knight representation to be
discussed later. Let
$K_{h}=\Big{(}\frac{1}{2}(h-2\sqrt{h}),\frac{1}{2}(h-\sqrt{h})\Big{)}$ and
define

$\displaystyle N_{H}:=\sum_{h=8}^{H}\sum_{k\in
K_{2h}}\sum_{x=2}^{+\infty}\textbf{1}_{A_{x,2h}^{(k)}}\quad\mbox{and}\quad
N:=\lim_{H\to\infty}N_{H}=\sum_{h=8}^{+\infty}\sum_{k\in
K_{2h}}\sum_{x=2}^{+\infty}\textbf{1}_{A_{x,2h}^{(k)}}.$ (3.2)

We note that for each $h$, the events $A_{x,h}^{(k)},x\in\mathbb{Z},k\in
K_{h}$ are mutually disjoint. Since $f(3)\geq\sum_{x\in\mathbb{Z}}u(x)$, we
have that $f(3)\geq N$, and thus it is enough to show that $N=\infty$ a.s.

###  3.2 Branching process and the Ray-Knight representation

In the remainder of this paper, we denote by $Y_{n}$ a critical Galton-Watson
branching process with geometric offspring distribution, and by $Z_{n},R_{n}$
two related critical Galton-Watson branching processes with immigration. The
precise definitions of these processes are as follows: Let $(X_{n,i})_{n,i}$
be i.i.d. geometric variables with mean 1, that is, for all $k\geq
0,P(X_{n,i}=k)=\frac{1}{2^{k+1}}$. We recursively define

$\displaystyle Y_{n+1}=\sum_{i=1}^{Y_{n}}X_{n,i},\
Z_{n+1}=\sum_{i=1}^{Z_{n}+1}X_{n,i},\ R_{n+1}=1+\sum_{i=1}^{R_{n}}X_{n,i}.$
(3.3)

One can check that $Y_{n},Z_{n}$ and $R_{n}$ are Markov chains with state
space $\mathbb{N}$ and transition probabilities:

$P(Y_{n+1}=j|Y_{n}=i)=\pi(i,j):=\left\\{\begin{aligned}
&\delta_{0}(j),&\text{if~{}$i=0$},\\\
&2^{-i-j}\frac{(i+j-1)!}{(i-1)!j!},&\text{if~{}$i>0$},\end{aligned}\right.$
(3.4) $\displaystyle P(Z_{n+1}=j|Z_{n}=i)=\rho(i,j):=\pi(i+1,j),$ (3.5)
$\displaystyle P(R_{n+1}=j|R_{n}=i)=\rho^{*}(i,j):=\pi(i,j-1).$ (3.6)

Let $k\geq 0$ and $x$ be fixed integers. When $x-1\geq 1$, we define the
following three processes:

$1$, $(Z_{n}^{(k)})_{n\geq 0}$ is a Markov chain with transition probabilities
$\rho(i,j)$ and initial state $Z^{(k)}_{0}=k$.

$2$, $(Y_{n}^{(k)})_{n\geq-1}$ is a Markov chain with transition probabilities
$\pi(i,j)$ and initial state $Y^{(k)}_{-1}=k$.

$3$, $(Y_{n}^{{}^{\prime}(k)})_{n\geq 0}$ is a Markov chain with transition
probabilities $\pi(i,j)$ and initial state
$Y_{0}^{{}^{\prime}(k)}=Z_{x-1}^{(k)}$.

We assume that the three processes are independent, except that
$Y^{{}^{\prime}(k)}$ starts from $Z_{x-1}^{(k)}$. We patch the above three
processes together to a single process as follows:

$\Delta_{x}^{(k)}(y):=\left\\{\begin{array}[]{ll}Z_{x-1-y}^{(k)},&\text{if~{}$0\leq
y\leq x-1$},\\\ Y_{y-x}^{(k)},&\text{if~{}$x-1\leq y\leq\infty$},\\\
Y_{-y}^{{}^{\prime}(k)},&\text{if~{}$-\infty<y\leq 0$}.\end{array}\right.$
(3.7)

By the Ray-Knight theorem on local times of simple random walk on $\mathbb{Z}$
(c.f. [25, Theorem 1.1]), we know that for any integers $x\geq 2$ and $k\geq
0$,

$\displaystyle(\xi_{D}(y,T_{U}(x-1,k+1)),y\in\mathbb{Z})\overset{{\rm
law}}{=}(\Delta_{x-1}^{(k)}(y),y\in\mathbb{Z}).$ (3.8)

Similarly, when $x-1\leq 0$, we define the processes:

$1$, $(R_{n}^{(k)})_{n\geq-1}$ is a Markov chain with transition probabilities
$\rho^{*}(i,j)$ and initial state $R^{(k)}_{-1}=k$.

$2$, $(Y_{n}^{(k)})_{n\geq 0}$ is a Markov chain with transition probabilities
$\pi(i,j)$ and initial state $Y^{(k)}_{0}=k$.

$3$, $(Y_{n}^{{}^{\prime}(k)})_{n\geq-1}$ is a Markov chain with transition
probabilities $\pi(i,j)$ and initial state
$Y_{-1}^{{}^{\prime}(k)}=R_{-1-x}^{(k)}$.

We assume that the three processes are independent, except that
$Y^{{}^{\prime}(k)}$ starts from $R_{-1-x}^{(k)}$. In this case, we patch the
three processes together as follows:

$\Delta_{x}^{(k)}(y)\triangleq\left\\{\begin{array}[]{ll}Y_{y}^{{}^{\prime}(k)},&\text{if~{}$-1\leq
y<\infty$},\\\ R_{y-x}^{(k)},&\text{if~{}$x-1\leq y\leq-1$},\\\
Y_{x-1-y}^{(k)},&\text{if~{}$-\infty<y\leq x-1$}.\end{array}\right.$ (3.9)

By the Ray-Knight theorem, we get that for the case $k\geq 0,x\leq 1$:

$\displaystyle(\xi_{D}(y,T_{U}(x-1,k+1)),y\in\mathbb{Z})\overset{{\rm
law}}{=}(\Delta_{x-1}^{(k)}(y),y\in\mathbb{Z}).$ (3.10)

###  3.3 Three favorite edges under Ray-Knight representation

For $h\in\mathbb{N}$, define the first hitting times of $[h,+\infty)$ for
$Y_{n}^{(k)}$ and $Z_{n}^{(k)}$ to be $\sigma_{h}^{(k)}$ and $\tau_{h}^{(k)}$
respectively, and the extinction time of $Y_{n}^{(k)}$ to be $\omega^{(k)}$.
That is,

$\displaystyle\sigma_{h}^{(k)}:=\min\\{n\geq 0:Y_{n}^{(k)}\geq
h\\},\tau_{h}^{(k)}:=\min\\{n\geq 0:Z_{n}^{(k)}\geq
h\\},\omega^{(k)}:=\min\\{n\geq 0:Y_{n}^{(k)}=0\\}.\quad$ (3.11)

Using the notation above, we can express $P(A_{x,h}^{(k)})$ in its Ray-Knight
representation form. In the remainder of this section, we let
$\tilde{n}:=T_{U}(x-1,k+1)$ for simplicity. Now, on $A_{x,h}^{(k)}$, we have
that $L(x,\tilde{n})=L(x+1,\tilde{n})=L(x+2,\tilde{n})=h$,
$h>L(y,\tilde{n})=2\xi_{D}(y-1,\tilde{n})+\textbf{1}_{\\{0<y\leq x-1\\}}$ for
$x\geq 2,$ $y\neq x,x+1,x+2$. We have the following five cases:

(1) $y\leq 0,~{}\xi_{D}(y-1,\tilde{n})=\frac{L(y,\tilde{n})}{2}<\frac{h}{2}$;

(2)
$y\in[1,x-2],~{}\xi_{D}(y-1,\tilde{n})=\frac{L(y,\tilde{n})-1}{2}<\frac{h-1}{2}$;

(3)
$y=x-1,~{}\xi_{D}(y-1,\tilde{n})=\frac{L(y,\tilde{n})-1}{2}<\frac{h-1}{2}$;

(4)
$y=x,x+1,x+2,~{}\xi_{D}(y-1,\tilde{n})=\frac{L(y,\tilde{n})}{2}=\frac{h}{2}$;

(5) $y\geq
x+3,~{}\xi_{D}(y-1,\tilde{n})=\frac{L(y,\tilde{n})}{2}<\frac{h}{2}.$

Then by (3.8), we obtain that

$\displaystyle P(A_{x,h}^{(k)})$ $\displaystyle=$ $\displaystyle
P\left(Y_{0}^{(k)}=Y_{1}^{(k)}=Y_{2}^{(k)}=\frac{h}{2},\left\\{Y_{n}^{(k)}<\frac{h}{2},n\geq
3\right\\},\right.$ (3.12)
$\displaystyle\quad\quad\left.\left\\{Z_{n}^{(k)}<\frac{h-1}{2},1\leq n\leq
x-2\right\\},\left\\{Y_{n}^{{}^{\prime}(k)}<\frac{h}{2},n\geq
1\right\\}\right).$

For all the notation above, when the initial state of a process is obvious, we
omit the superscript $``(k)"$ for simplicity. We will also use conditional
probability $P(\cdot|Y_{0}=k)$ to indicate the initial state.

###  3.4 Standard lemmas

In this subsection we recall a few lemmas that will be useful later. In what
follows, $c_{i}$ for $i\geq 1$ and $c$ are all constants.

######  Lemma 3.1.

([12, Lemma 2.2]) We have that

$(1)$ For
$i,j\in\Big{(}\frac{1}{2}(h-10\sqrt{h}),\frac{1}{2}(h+10\sqrt{h})\Big{)}$,
there exists positive constants $c$ and $C$ such that
$ch^{-\frac{1}{2}}\leq\pi(i,j)\leq Ch^{-\frac{1}{2}}$ for all $h\geq 100$.

$(2)$ For $i+j=h$, $\pi(i,j)\leq O(1)h^{-\frac{1}{2}}$.

$(3)$ For $j<i_{1}<i_{2}$, $\pi(i_{1},j)>\pi(i_{2},j)$.

######  Lemma 3.2.

([12, Lemma 2.3]) For any $h\in\mathbb{N}$, it holds that
$E\tau_{h}=EZ_{\tau_{h}}-Z_{0}$. In particular, for any $0\leq k\leq h$, we
have that $E[\tau_{h}|Z_{0}=k]\geq h-k$.

######  Lemma 3.3.

([34, (6.18)]) There exists a constant $C<\infty$ such that, for any $0\leq
k<h$,

$\displaystyle E(Z_{\tau_{h}}|Z_{0}=k)\leq h+Ch^{\frac{1}{2}}.$

##  4 Proof of Theorem 1.1

In this section, we give the proof of Theorem 1.1 by following the idea of
[12]. We spell out some details for the reader’s convenience and point out
some modifications that need to be made.

###  4.1 Lower bound on the first moment.

The following is the counterpart to [12, Lemma 3.1].

######  Lemma 4.1.

Suppose that $Z_{0}=k\in K_{h}=[\frac{h-2\sqrt{h}}{2},\frac{h-\sqrt{h}}{2}]$.
Then there exists a constant $c>0$ such that for any $h>4$,

$E\left(\sum_{n=1}^{\tau_{\frac{h-1}{2}}}\frac{h/2-Z_{n}}{h/2}\right)\geq
c\sqrt{h}.$

Proof. Let $M_{n}=\sum_{s=1}^{n}(Z_{s}-s)-n(Z_{n}-n)$, and let
$\mathcal{F}_{n}=\sigma(Z_{0},Z_{1},...,Z_{n})$. By the proof of [12, Lemma
3.1], we know that $(M_{n})$ is a martingale. By the optional stopping
theorem, we get that

$E\left(\sum_{n=1}^{\tau_{\frac{h-1}{2}}}(Z_{n}-n)\right)=E\tau_{\frac{h-1}{2}}(Z_{\tau_{\frac{h-1}{2}}}-\tau_{\frac{h-1}{2}}),$

and thus

$\displaystyle
E\left(\sum_{n=1}^{\tau_{\frac{h-1}{2}}}\frac{h/2-Z_{n}}{h/2}\right)$
$\displaystyle=$ $\displaystyle
E\tau_{\frac{h-1}{2}}-\dfrac{E\left(\sum_{n=1}^{\tau_{\frac{h-1}{2}}}(Z_{n}-n)+n\right)}{h/2}$
(4.1) $\displaystyle=$ $\displaystyle
E\tau_{\frac{h-1}{2}}-\dfrac{E\tau_{\frac{h-1}{2}}(Z_{\tau_{\frac{h-1}{2}}}-\tau_{\frac{h-1}{2}})}{h/2}-\dfrac{E\frac{(1+\tau_{\frac{h-1}{2}})\tau_{\frac{h-1}{2}}}{2}}{h/2}$
$\displaystyle=$
$\displaystyle\left(1-\frac{1}{h}\right)E\tau_{\frac{h-1}{2}}-\frac{2}{h}E\left[\tau_{\frac{h-1}{2}}Z_{\tau_{\frac{h-1}{2}}}-\frac{1}{2}\tau_{\frac{h-1}{2}}^{2}\right].$

Define the process
$M_{n}^{\prime}=-\frac{1}{4}Z_{n}^{2}+nZ_{n}-\frac{1}{2}n^{2}+\frac{1}{4}n$.
By the proof of [12, Lemma 3.1], we know that $(M_{n}^{\prime})$ is a
martingale. Applying the optional stopping theorem to $(M_{n}^{\prime})$ at
$\tau_{\frac{h-1}{2}}$, we get

$\displaystyle
E\left[\tau_{\frac{h-1}{2}}Z_{\tau_{\frac{h-1}{2}}}-\frac{1}{2}\tau_{\frac{h-1}{2}}^{2}\right]=E\left[\frac{1}{4}Z_{\tau_{\frac{h-1}{2}}}^{2}-\frac{1}{4}\tau_{\frac{h-1}{2}}\right]-\frac{Z_{0}^{2}}{4}=\frac{1}{4}E\left[Z_{\tau_{\frac{h-1}{2}}}^{2}-\tau_{\frac{h-1}{2}}\right]-\frac{Z_{0}^{2}}{4}.$
(4.2)

Combining (4.1), (4.2) and Lemma 3.2, we get

$\displaystyle
E\left(\sum_{n=1}^{\tau_{\frac{h-1}{2}}}\frac{h/2-Z_{n}}{h/2}\right)=\left(1-\frac{1}{2h}\right)E\tau_{\frac{h-1}{2}}-\frac{1}{2h}\left(EZ_{\tau_{\frac{h-1}{2}}}^{2}-Z_{0}^{2}\right)$
$\displaystyle=\left(1-\frac{1}{2h}\right)E\left[Z_{\tau_{\frac{h-1}{2}}}-Z_{0}\right]-\frac{1}{2h}E\left[(Z_{\tau_{\frac{h-1}{2}}}-Z_{0})(Z_{\tau_{\frac{h-1}{2}}}+Z_{0})\right]$
$\displaystyle=\frac{1}{2h}E\left[\left(2h-1-(Z_{\tau_{\frac{h-1}{2}}}+Z_{0})\right)(Z_{\tau_{\frac{h-1}{2}}}-Z_{0})\right].$
(4.3)

Obviously
$Z_{\tau_{\frac{h-1}{2}}}-Z_{0}\geq\frac{h-1}{2}-\frac{h-\sqrt{h}}{2}\geq
c_{1}\sqrt{h}$. Then by Lemmas 3.2 and 3.3, we obtain

$\displaystyle
E\left(\sum_{n=1}^{\tau_{\frac{h-1}{2}}}\frac{h/2-Z_{n}}{h/2}\right)\geq\frac{1}{2h}\cdot\left(2h-1-\frac{h-1}{2}-c_{2}\sqrt{h}-\frac{h-\sqrt{h}}{2}\right)\cdot
c_{1}\sqrt{h}\geq c\sqrt{h}.$ (4.4)

######  Proposition 4.2.

There exists $c>0$ such that $EN_{H}\geq c\log H$ for all $H\in[50,\infty)$.

Proof. By the Ray-Knight representation, (3.2) and (3.12), we know that

$\displaystyle EN_{H}$ $\displaystyle=$ $\displaystyle\sum_{h=8}^{H}\sum_{k\in
K_{2h}}P\left(Y_{0}^{(k)}=Y_{1}^{(k)}=Y_{2}^{(k)}=h,\left\\{Y_{n}^{(k)}<h,\forall
n\geq 3\right\\}\right)$
$\displaystyle\cdot\sum_{x=2}^{+\infty}P\left(\left\\{Z_{n}^{(k)}<h-\frac{1}{2},1\leq
n\leq x-2\right\\},\left\\{Y_{n}^{{}^{\prime}(k)}<h,\forall n\geq
1\right\\}\right).$

It follows that

$\displaystyle EN_{H}$ (4.5) $\displaystyle\geq$
$\displaystyle\sum_{h=50}^{H}\sum_{k\in
K_{2h}}P\left(Y_{0}^{(k)}=Y_{1}^{(k)}=Y_{2}^{(k)}=h,\left\\{Y_{3}^{(k)}\in\left(h-5\sqrt{2h},h-\frac{\sqrt{2h}}{2}\right),Y_{n}^{(k)}<h,\forall
n\geq 4\right\\}\right)$
$\displaystyle\cdot\sum_{x=2}^{+\infty}P\left(\left\\{Z_{n}^{(k)}<h-\frac{1}{2},1\leq
n\leq x-2\right\\},\left\\{Y_{n}^{{}^{\prime}(k)}<h,n\geq 1\right\\}\right)$
$\displaystyle=$ $\displaystyle\sum_{h=50}^{H}\sum_{k\in
K_{2h}}\pi(k,h)\cdot\pi(h,h)\cdot\pi(h,h)\cdot\sum_{m\in(h-5\sqrt{2h},h-\frac{\sqrt{2h}}{2})}\pi(h,m)P\left(Y_{n}^{(m)}<h,\forall
n\geq 1\right)$
$\displaystyle\cdot\sum_{x=2}^{+\infty}P\left(\tau_{h-\frac{1}{2}}\geq
x-1,\left\\{Y_{n}^{{}^{\prime}(k)}<h,\forall n\geq 1\right\\}\right).$

By Lemma 3.1, all the $\pi(\cdot,\cdot)$’s in the display above are of the
order $h^{-\frac{1}{2}}$. Since $Y_{n}$ is a martingale, applying the optional
stopping theorem at $\sigma_{h}\land\omega$, where $\sigma_{h}$ and $\omega$
are defined in (3.11), we get for $m\in(h-5\sqrt{2h},h-\frac{\sqrt{2h}}{2})$,

$\displaystyle P\left(Y_{n}^{(m)}<h,\forall n\geq
1\right)=P\left(Y_{n}^{(m)}~{}\mbox{hits }0\mbox{ before exceeds
}h\right)\geq\dfrac{h-m}{h}\geq c_{3}h^{-\frac{1}{2}}.$ (4.6)

The last two inequalities hold since

$\displaystyle m$ $\displaystyle=$ $\displaystyle
EY_{\sigma_{h}\land\omega}=E\left(Y_{\sigma_{h}}\textbf{1}_{\\{\omega\geq\sigma_{h}\\}}\right)+E\left(Y_{\omega}\textbf{1}_{\\{\omega<\sigma_{h}\\}}\right)$
$\displaystyle\geq$ $\displaystyle
E\left(Y_{\sigma_{h}}\textbf{1}_{\\{\omega\geq\sigma_{h}\\}}\right)$
$\displaystyle\geq$ $\displaystyle h\left(1-P\left(Y_{n}^{(m)}~{}\mbox{hits
}0\mbox{ before exceeds }h\right)\right),$

which implies that

$\displaystyle P\left(Y_{n}^{(m)}~{}\mbox{hits }0\mbox{ before exceeds
}h\right)\geq\dfrac{h-m}{h}\geq c_{3}h^{-\frac{1}{2}}.$ (4.7)

By (4.5) and (4.6), we get

$\displaystyle EN_{H}\geq c_{4}\sum_{h=50}^{H}\sum_{k\in
K_{2h}}h^{-2}\cdot\sum_{x=2}^{+\infty}P\left(\tau_{h-\frac{1}{2}}\geq
x-1,\left\\{Y_{n}^{{}^{\prime}(k)}<h,\forall n\geq 1\right\\}\right).$ (4.8)

By the independence of the processes in the Ray-Knight representation, we have

$\displaystyle\sum_{x=2}^{+\infty}P\left(\tau_{h-\frac{1}{2}}\geq
x-1,\left\\{Y_{n}^{{}^{\prime}(k)}<h,\forall n\geq 1\right\\}\right)$
$\displaystyle\geq\sum_{x=2}^{+\infty}\sum_{l=0}^{h-1}P\left(Z_{n}^{(k)}<h-\frac{1}{2}\mbox{
for }1\leq n\leq x-2,Z_{x-1}=l\right)\cdot P\left(Y_{n}^{(l)}~{}\mbox{hits
}0\mbox{ before exceeds }h\right).$

By the definitions of $(Z_{n})_{n\geq 0}$ and $\tau_{h}$, we obtain

$\displaystyle Z_{0}-Z_{\tau_{h-\frac{1}{2}}}\leq
h-\frac{\sqrt{2h}}{2}-h+\frac{1}{2}=\frac{1-\sqrt{2h}}{2}\leq 0.$ (4.9)

Similar to (4.7), we have $P(Y_{n}^{(l)}~{}\mbox{hits }0\mbox{ before exceeds
}h)\geq\frac{h-l}{h}$, which together with (4.9) and Lemma 4.1 implies that

$\displaystyle\sum_{x=2}^{+\infty}P\left(\tau_{h-\frac{1}{2}}\geq
x-1,\left\\{Y_{n}^{{}^{\prime}(k)}<h,\forall n\geq 1\right\\}\right)$
$\displaystyle\geq\sum_{x=2}^{+\infty}\sum_{l=0}^{h}P\left(\tau_{h-\frac{1}{2}}\geq
x-1,Z_{x-2}=l\right)\cdot\frac{h-l}{h}$
$\displaystyle=E\left(\sum_{l=0}^{h}\sum_{x=2}^{\tau_{h-\frac{1}{2}}+1}\frac{h-l}{h}\cdot\textbf{1}_{\\{Z_{x-2}=l\\}}\right)=E\left(\sum_{n=0}^{\tau_{h-\frac{1}{2}}-1}\frac{h-Z_{n}}{h}\right)$
$\displaystyle\geq
E\left(\sum_{n=0}^{\tau_{h-\frac{1}{2}}-1}\frac{h-Z_{n}}{h}\right)+\left(\frac{h-Z_{\tau_{h-\frac{1}{2}}}}{h}-\frac{h-Z_{0}}{h}\right)$
$\displaystyle=E\left(\sum_{n=1}^{\tau_{h-\frac{1}{2}}}\frac{h-Z_{n}}{h}\right)\geq
c_{5}\sqrt{h}.$ (4.10)

By (4.8) and (4.1), we obtain

$\displaystyle EN_{H}\geq c_{4}\sum_{h=50}^{H}\sum_{k\in K_{2h}}h^{-2}\cdot
c_{5}\sqrt{h}\geq c_{6}\sum_{h=100}^{H}h^{-1}\geq c\log H.$

The proof is complete.

###  4.2 Upper bound on the second moment

In this subsection, we will give an upper bound on the second moment
$EN_{H}^{2}$ following [12]. If we use the $N_{H}$ defined in (3.2)–(3.1), we
could not prove the counterparts of [12, Lemmas 3.3, 3.4]. To overcome this,
we give a variant $\widetilde{N}_{H}$ of $N_{H}$ with
$N_{H}\leq\widetilde{N}_{H}$ a.s. In the remainder of this section, we assume
$x\geq 2$ unless explicitly mentioned otherwise.

For any positive integer $h$, we define

$\displaystyle A_{x,2h}$ $\displaystyle:=$
$\displaystyle\left\\{\mathcal{K}\left(T_{D}(x-1,h)\right)=\\{x,x+1,x+2\\},L\left(x,T_{D}(x-1,h)\right)=2h\right\\}$
(4.11)

and

$\displaystyle\widetilde{N}_{H}:=\sum_{h=50}^{H}\sum_{x=2}^{\infty}\textbf{1}_{A_{x,2h}},\quad\widetilde{N}:=\lim_{H\to\infty}\widetilde{N}_{H}=\sum_{h=50}^{\infty}\sum_{x=2}^{\infty}\textbf{1}_{A_{x,2h}}.$

We claim that

$\displaystyle\cup_{k\in K_{2h}}A_{x,2h}^{(k)}\subset A_{x,2h},$ (4.12)

where $A_{x,2h}^{(k)}$ is defined by (3.1). Suppose that $\omega\in
A_{x,2h}^{(k)}$ for some $k\in K_{2h}$. Define

$\tilde{T}(\omega):=\\{m<T_{U}(x-1,k+1)(\omega):S_{m}=x-1,S_{m-1}=x,\mathcal{K}(m)=\\{x,x+1,x+2\\},L(x,m)=2h\\}.$

By the definition of $A_{x,h}^{(k)}$, we know that $\tilde{T}(\omega)$
consists of one unique element $t(\omega)$. Further by (1.3), we get that
$t(\omega)=T_{D}(x-1,h)(\omega)$. Hence $\omega\in A_{x,2h}$ and thus (4.12)
holds.

By (4.12), we get that $N_{H}\leq\widetilde{N}_{H}$ a.s. Now we study the
second moment of $\widetilde{N}_{H}$ following [12, Section 3.2].

Let $D(n)=\big{(}\xi_{D}(x,n),x\in\mathbb{Z}\big{)}\in\mathbb{N}^{\mathbb{Z}}$
be the random vector that records the number of downcrossings of each site by
time $n$. For $l\in\mathbb{N}^{\mathbb{Z}}$, we use $l(i),i\in\mathbb{Z}$ to
denote the $i$-th component of $l$. For $l\in\mathbb{N}^{\mathbb{Z}}$, define
$B_{x}(l)=\\{\exists n<\infty:D(n)=l,S(n-1)=x,S(n)=x-1\\}$. Note that if
$B_{x}(l)$ happens, there exists a unique $n\in\mathbb{N}$, such that
$D(n)=l,S(n-1)=x$ and $S(n)=x-1$.

Let $\mathcal{P}=\\{l:P(B_{x}(l))>0~{}\mbox{for some}~{}x\\}$. For
$\mathcal{Q}\subset\mathcal{P}$, denote
$B_{x}(\mathcal{Q})=\bigcup_{l\in\mathcal{Q}}B_{x}(l)$. Then by virtue of
(1.3), we have $A_{x,2h}=B_{x}(\mathcal{P}_{x,2h})$, where
$\mathcal{P}_{x,2h}$ is the set of $l\in\mathcal{P}$ such that

$\displaystyle l(x-1)=l(x)=l(x+1)=h,\ l(i)<h\ \mbox{for all}\ i\neq
x-1,x,x+1.$

Let $\mathcal{A}$ be the family of all subsets of $\mathcal{P}$. For any
$x\in\mathbb{Z}$, we define a map $\varphi_{x}:\mathcal{P}\mapsto\mathcal{A}$
by

$\displaystyle\varphi_{x}(l):=\\{l^{*}\in\mathcal{P}:l^{*}(i)<l(i)~{}\mbox{for}~{}i=x,x+1,l^{*}(i)=l(i)~{}\mbox{for}~{}i\neq
x,x+1\\}.$

Following the argument of [12, Lemma 3.3], we can prove

######  Lemma 4.3.

Suppose $x_{1},x_{2}\in\mathbb{Z}$ and $h$ is a positive integer. If
$l_{i}^{*}\in\varphi_{x_{i}}(l_{i})$ with $l_{i}\in\mathcal{P}_{x_{i},2h}$,
$i=1,2$, we have that $B_{x_{1}}(l_{1}^{*})\cap
B_{x_{2}}(l_{2}^{*})=\emptyset$, if $(x_{1},l_{1})\neq(x_{2},l_{2})$. Further,
we have $B_{x_{1}}(l_{1}^{*})\cap B_{x_{2}}(l_{2}^{*})=\emptyset$ if
$(x_{1},l_{1})=(x_{2},l_{2})$ but $l_{1}^{*}\neq l_{2}^{*}$.

The following result is the counterpart of [12, Lemma 3.4].

######  Lemma 4.4.

There exists a constant $c>0$ such that for any $x\geq 2,h\geq
50,l\in\mathcal{P}_{x,2h}$,

$\displaystyle P\big{(}B_{x}(\varphi_{x}(l))\big{)}\geq
chP\big{(}B_{x}(l)\big{)}.$

Proof. We consider $l^{*}\in\varphi_{x}(l)$ such that
$l^{*}(x)\in[h-\frac{\sqrt{2h}}{2},h)$ and
$l^{*}(x+1)\in[h-\frac{\sqrt{2h}}{2},h)$. According to Lemma 3.1 $(1)$ and
$(3)$, there is a constant $c>0$ such that

$\displaystyle\dfrac{P\big{(}B_{x}(l^{*})\big{)}}{P\big{(}B_{x}(l)\big{)}}=\dfrac{\pi\big{(}h,l^{*}(x)\big{)}\cdot\pi\big{(}l^{*}(x),l^{*}(x+1)\big{)}\cdot\pi\big{(}l^{*}(x+1),l(x+2)\big{)}}{\pi(h,h)\cdot\pi(h,h)\cdot\pi(h,l(x+2))}\geq
4c.$

Note that there are about $h/2$ of such $l^{*}\in\varphi_{x}(l)$ that satisfy
the above inequality. Thus by Lemma 4.3, we get that
$P\big{(}B_{x}(\varphi_{x}(l))\big{)}\geq chP\big{(}B_{x}(l)\big{)}.$

With Lemmas 4.3 and 4.4 in hand, we can follow the proof of [12, Proposition
3.5] to get the following result. We omit the details.

######  Proposition 4.5.

We have that $E\widetilde{N}_{H}^{2}=O(\log H)\cdot E\widetilde{N}_{H}$.

######  Corollary 4.6.

We have $EN_{H}^{2}=O(\log^{2}H).$

Proof. By Proposition 4.5 and the Cauchy-Schwarz inequality, we get

$E\widetilde{N}_{H}^{2}\leq O(\log
H)\cdot\left(E\widetilde{N}_{H}^{2}\right)^{1/2},$

which implies that

$E\tilde{N}_{H}^{2}=O(\log^{2}H).$

Since $N_{H}\leq\tilde{N}_{H}$ a.s., the desired result follows immediately.

###  4.3 0-1 law

Recall that $N=\lim_{H\to\infty}N_{H}$. First, we show that $N=\infty$ with
positive probability.

######  Proposition 4.7.

There exists a constant $\delta>0$ such that $P(N=\infty)\geq\delta$.

###### Proof.

By the Cauchy-Schwarz inequality, we get that

$\displaystyle EN_{H}$ $\displaystyle=$ $\displaystyle
EN_{H}\textbf{1}_{\\{N_{H}>\log\log
H\\}}+EN_{H}\textbf{1}_{\\{N_{H}\leq\log\log H\\}}$ (4.13) $\displaystyle\leq$
$\displaystyle\sqrt{EN_{H}^{2}\cdot P(N_{H}>\log\log H)}+\log\log H.$

Combining this with Proposition 4.2 and Corollary 4.6, we get that there exist
constants $c$, $\delta>0$ such that

$\displaystyle P(N_{H}>\log\log H)\geq\dfrac{(EN_{H}-\log\log
H)^{2}}{EN_{H}^{2}}\geq c\dfrac{\log^{2}H}{EN_{H}^{2}}\geq\delta,$

for all sufficiently large $H$. Letting $H\to\infty$, we get that
$P(N=\infty)\geq\delta$. ∎

Recall the definition of $\tilde{U}(n)$ in Theorem 2.1. By Theorem 2.1, we
know that

$\displaystyle\liminf_{n\to\infty}\dfrac{\tilde{U}(n)}{\sqrt{n}(\log
n)^{-\gamma}}=\infty\qquad a.s.,$ (4.14)

where $\gamma>11$.

Using Proposition 4.7 and (4.14), following the argument of [12, Section 3.3]
and applying Kolmogorov’s 0-1 law, we obtain that

$P(f(3)=\infty)=1,$

which completes the proof of Theorem 1.1.

##  5 Remark

In Section 2, we used the transience of the favorite downcrossing site process
to show the transience of the favorite edge process. In fact, from Proposition
2.4, we can see that there is a close relation between favorite edges and
favorite downcrossing sites. A natural question arise:

How about the number of favorite downcrossing sites of one-dimensional simple
symmetric random walk?

In [19], we will consider this question and prove the following result.

######  Theorem 5.1.

For a one-dimensional simple symmetric random walk, with probability 1 there
are only finitely many times at which there are at least four favorite
downcrossing sites and three favorite downcrossing sites occurs infinitely
often.

Acknowledgments This work was supported by the National Natural Science
Foundation of China (Grant Nos. 12171335, 12101429, 12071011, 11931004 and
11871184), the Simons Foundation (#429343) and the Science Development Project
of Sichuan University (2020SCUNL201).

## References

  * [1] Abe, Y. (2015). Maximum and minimum of local times for two-dimensional random walk. Electron. Commun. Probab. 20 22, 14pp.
  * [2] Bass, R. F., Eisenbaum, N. and Shi, Z. (2000). The most visited sites of symmetric stable processes. Probab. Theory Related Fields 116 391-404.
  * [3] Bass, R. F. and Griffin, P. S. (1985). The most visited site of Brownian motion and simple random walk. Z. Wahrsch. Verw. Gebiete 70 417-436.
  * [4] Chen, D., de Raphélis, L. and Hu, Y. (2018). Favorite sites of randomly biased walks on a supercritical Galton-Watson tree. Stochastic Process. Appl. 128 1525-1557.
  * [5] Chung, K. L.(1951). The strong law of large numbers. Proc. Second Berkeley Symp. Math. Statist. Prob. 341-352, Univ. of California Press.
  * [6] Csáki, E. and Révész, P. (1983). Strong invariance for local times. Z. Wahrsch. Verw. Gebiete 62 263-278.
  * [7] Csáki, E., Révész, P. and Shi, Z. (2000). Favourite sites, favourite values and jump sizes for random walk and Brownian motion. Bernoulli 6 951-975.
  * [8] Csáki, E. and Shi, Z. (1998). Large favourite sites of simple random walk and the Wiener process. Electron. J. Probab. 3 14, 31pp.
  * [9] Csörgő, M. and Horváth, L. (1989). On best possible approximations of local time, Statist. Probab. Lett. 8 301-306.
  * [10] Dembo, A. (2005). Favorite points, cover times and fractals. In Lectures on Probability Theory and Statistics. Lecture Notes in Math. 1869 1-101. Springer, Berlin.
  * [11] Dembo, A., Peres, Y., Rosen, J. and Zeitouni, O. (2001). Thick points for planar Brownian motion and the Erdős-Taylor conjecture on random walk. Acta Math. 186 239-270.
  * [12] Ding, J. and Shen, J. (2018). Three favorite sites occurs infinitely often for one-dimensional simple random walk. Ann. Probab. 46 2545-2561.
  * [13] Eisenbaum, N. (1989). Temps locaux, excursions et lieu le plus visité par un mouvement brownien lineaire. Thèse de doctorat, Université de Paris 7.
  * [14] Eisenbaum, N. (1997). On the most visited sites by a symmetric stable process. Probab. Theory Related Fields 107 527-535.
  * [15] Eisenbaum, N. and Khoshnevisan, D. (2002). On the most visited sites of symmtric Markov processes. Stochastic Process. Appl. 101 241-256.
  * [16] Erdős, P. and Révész, P. (1984). On the favourite points of a random walk. In Mathematical Structure–Computational Mathematics–Mathematical Modelling 2 152-157.
  * [17] Erdős, P. and Révész, P. (1987). Problems and results on random walks. In Mathematical Statistics and Probability Theory, Vol. B (Bad Tatzmannsdorf, 1986) 59-65. Reidel, Dordrecht.
  * [18] Erdős, P. and Révész, P. (1991). Three problems on the random walk in $\mathbf{Z}^{d}$. Studia Sci. Math. Hungar. 26 309-320.
  * [19] Hao, C.-X., Hu, Z.-C., Ma, T. and Song, R. Favorite downcrossing sites of one-dimensional simple random walk, In preparation.
  * [20] Hu, Y. and Shi, Z. (2000). The problem of the most visited site in random environment. Probab. Theory Related Fields 116 273-302.
  * [21] Hu, Y. and Shi, Z. (2015). The most visited sites of biased random walks on trees. Electron. J. Probab. 20 62, 14pp.
  * [22] Kesten, H. (1965). An interated logarithm law for the local time. Duke Math. J. 32 447-456.
  * [23] Kesten, H. and Spitzer, F. (1979). A limit theorem related to a new class of self similar processes. Z. Wahrsch. Verw. Gebiete 50 5-25.
  * [24] Khoshnevisan, D. and Lewis, T. M. (1995). The favorite point of a Poisson process. Stochastic Process. Appl. 57 19-38.
  * [25] Knight, F. B. (1963). Random walks and a sojourn density process of Brownian motion. Trans. Amer. Math. Soc. 109 56-86.
  * [26] Leuridan, C. (1997). Le point d’un fermé le plus visité par le mouvement brownien. Ann. Probab. 25 953-996.
  * [27] Li, B., Xiao, Y. and Yang, X. (2019). On the favorite points of symmetric Lévy processes. J. Theoret. Probab. 32 1943-1972.
  * [28] Lifshits, M. A. and Shi, Z. (2004). The escape rate of favorite sites of simple random walk and Brownian motion. Ann. Probab. 32 129-152.
  * [29] Marcus, M. B. (2001). The most visited sites of certain Lévy processes. J. Theoret. Probab. 14 867-885.
  * [30] Okada, I. (2016). Topics and problems on favorite sites of random walks. Availabe at arXiv:1606.03787.
  * [31] Révész, P. (1981). Local time and invariance. in: Analytical Methods in Probability Theory, Proceedings, Oberwolfach, Germany 1980, Lecture Notes in Math. 861 128-145. Springer, Berlin.
  * [32] Révész, P. (1990). Random Walk in Random and Non-Random Environment. World Scientific, Singapore.
  * [33] Shi, Z. and Tóth, B. (2000). Favourite sites of simple random walk. Period. Math. Hungar. 41 237-249.
  * [34] Tóth, B. (2001). No more than three favorite sites for simple random walk. Ann. Probab. 29 484-503.
  * [35] Tóth, B. and Werner, W. (1997). Tied favourite edges for simple random walk. Combin. Probab. Comput. 6 359-369.


Without loss of generality, we assume we have a bistable system, with $f$ the ground truth VF, $M_{\mathrm{train}}=B(A_1)$ and $M_{\mathrm{test}}=B(A_2)$. We aim to construct an infinite family of functions $G=\{g_{\alpha}|\alpha \in I\}$ with zero reconstruction error on $B(A_1)$ but non-zero error on $B(A_2)$. We denote by $\Phi_{g_{\alpha}}$ the evolution operator associated with $g_{\alpha}$. Let $V'=B(A_2) \backslash A_2$. Due to the assumption that $f$ is not topologically transitive on $B(A_2)$, we can choose some non-empty, open subset $V \subseteq V'$. As $M$ is locally Hausdorff, we can define a compact subset $K \subset V$ such that $K$ itself contains an open set. As $V$ is open, we define a bump function $\Lambda \in \mathcal{C}^{\infty}(M)$ [Lee, 2012] that is zero outside of $V$ and equals $1$ on $K$.

The $i$-th component of a VF in $G$ is then defined as

\begin{align}
g_{\alpha,i}(\vx)= f_i(\vx)+ \Lambda(\vx)\cdot \left(- f_i(\vx) +s_{\alpha,i}(\vx)\right), \quad i=1,...,n ,
\end{align}

where $\vx_{\alpha} \in K$. As $K$ contains an open set, there are infinitely many different $\vx_{\alpha}$. By construction, $\mathcal{E}_{\mathrm{gen}}^{B(A_1)}(\Phi_{g_{\alpha}})=0$, since $\Lambda$ is zero outside of $V$, thus zero on $B(A_1)$. On $B(A_1)$, $g_{\alpha}$ has the form $ g_{\alpha,i}(\vx)= f_i(\vx)$ ($f$ has zero generalization error as it is the ground-truth VF). In contrast, on $K$, the VFs in $G$ reduce to

\begin{align}
\end{align}

where we assume $s_{\alpha}$ to be a differentiable VF with an attracting equilibrium point at $\vx_{\alpha}$. This construction is feasible on any compact set $K$ in any dimension. Given that $\Lambda$ is smooth and $s_{\alpha}$ is differentiable, $g_{\alpha}$ remains a member of $\mathcal{X}^1$.

Thus, $G$ forms an infinite family of VFs, each possessing an attracting equilibrium point at distinct positions in $K$. We will denote by $B(A_{\vx_{\alpha}}) \subseteq V$ the basin of attraction of the equilibrium point $\vx_{\alpha}$. All functions $g_{\alpha}$ have an attractor on $B(A_2)$ different from the one of the ground truth VF $f$. Additionally, $B(A_{\vx_{\alpha}}) \cap A_2 = \emptyset$ by construction of $V$ for any $\alpha$. Thus, we constructed the same setting encountered in the proof of Theorem <ref>, case (ii). Using the proof and setting $B(A_{n+1})$ (in the notation of Theorem <ref>, case (ii)) to $B(A_{\vx_{\alpha}})$, we can conclude that

\begin{align}
\mathcal{E}_{\mathrm{gen}}^{B(A_{\vx_{\alpha}})}(\Phi_{g_{\alpha}}) \geq \varepsilon
\end{align}

with $\varepsilon>0$. Since $V \subset B(A_2)$, it follows that $\mathcal{E}_{\mathrm{gen}}^{B(A_2)}(\Phi_{g_{\alpha}})\neq0$ for all $\alpha \in I$.
Consequently, $(\mathcal{X}^1,\mathcal{D})$ is not strictly learnable, since we can construct infinitely many functions in $\mathcal{X}^1$ with non-zero generalization error [For the proof that $(\mathcal{X}^1,\mathcal{D})$ is not strictly learnable, a single VF as constructed above would have sufficed.].