# The most visited sites of biased random walks on trees

Yueyun Hu, Zhan Shi

► To cite this version:

Yueyun Hu, Zhan Shi. The most visited sites of biased random walks on trees. Electronic Journal of Probability, 2015, 20, pp.1-14. 10.1214/EJP.v20-4051 . hal-01214677

HAL Id: hal-01214677

https://hal.sorbonne-universite.fr/hal-01214677

Submitted on 12 Oct 2015

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

Electron. J. Probab. 20 (2015), no. 62, 1–14.
ISSN: 1083-6489 DOI: 10.1214/EJP.v20-4051

# The most visited sites of biased random walks on trees*

Yueyun Hu†

Zhan Shi‡

## Abstract

We consider the slow movement of randomly biased random walk ($X_n$) on a supercritical Galton-Watson tree, and are interested in the sites on the tree that are most visited by the biased random walk. Our main result implies tightness of the distributions of the most visited sites under the annealed measure. This is in contrast with the one-dimensional case, and provides, to the best of our knowledge, the first non-trivial example of null recurrent random walk whose most visited sites are not transient, a question originally raised by Erdős and Révész [11] for simple symmetric random walk on the line.

**Keywords:** Biased random walk on the Galton-Watson tree; branching random walk; local time; most visited site.

AMS MSC 2010: 60J80; 60G50; 60K37.

Submitted to EJP on January 12, 2015, final version accepted on May 29, 2015.

Supersedes arXiv:1502.02831.

## 1 Introduction

We consider a (randomly) biased random walk ($X_n$) on a supercritical Galton-Watson tree $T$, rooted at $\emptyset$. The random biases are represented by $\omega := (\omega(x), x \in T\setminus\{\emptyset\})$, a family of random vectors; for each vertex $x \in T$, $\omega(x) := (\omega(x, y), y \in T)$ is such that $\omega(x, y) \ge 0$ for all $y \in T$ and that $\sum_{y \in T} \omega(x, y) = 1$. For any vertex $x \in T\setminus\{\emptyset\}$, let $\tilde{x}$ be its parent. For the sake of presentation, we modify the values of $\omega(\emptyset, x)$ for $x$ with $\tilde{x} = \emptyset$, and add a special vertex, denoted by $\tilde{\emptyset}$, which is considered as the parent of $\emptyset$, such that $\omega(\tilde{\emptyset}, \tilde{\emptyset}) + \sum_{x: \tilde{x}=\tilde{\emptyset}} \omega(\tilde{\emptyset}, x) = 1$. The vertex $\tilde{\emptyset}$ is, however, not regarded as a vertex of $T$; so, for example, $\sum_{x \in T} f(x)$ does not contain the term $f(\tilde{\emptyset})$.

Assume that for each pair of vertices $x$ and $y$ in $T \cup \{\tilde{\emptyset}\}$, $\omega(x, y) > 0$ if and only if $y \sim x$, where by $x \sim y$ we mean that $x$ is either a child, or the parent, of $y$. Moreover, we define $\omega(\tilde{\emptyset}, \emptyset) := 1$.

<footnote>*Partly supported by ANR project MEMEMO2 (2010-BLAN-0125).</footnote>

<footnote>†LAGA, Institut Galilée, Université Paris XIII, 99 avenue J-B Clément, F-93430 Villetaneuse, France.
E-mail: yueyun@math.univ-paris13.fr</footnote>

<footnote>‡LPMA, Université Paris VI, 4 place Jussieu, F-75252 Paris Cedex 05, France.
E-mail: zhan.shi@upmc.fr</footnote>
Given $\omega$, the biased walk ($X_n$, $n \ge 0$) is a Markov chain taking values on $\mathbb{T} \cup \{\overleftarrow{\emptyset}\}$, started at $X_0 = \emptyset$, whose transition probabilities are

$$P_{\omega}\{X_{n+1} = y | X_n = x\} = \omega(x, y).$$

The probability $P_{\omega}$ is often referred to as the quenched probability. We also consider the annealed probability $P(\cdot) := \int P_{\omega}(\cdot) P(d\omega)$, where $P$ denotes the probability with respect to the environment $(\omega, \mathbb{T})$.

There is an active literature on randomly biased walks on Galton-Watson trees; see, for example, a large list of references in [17]. In this paper, we restrict our attention to a regime of *slow movement* of the walk in the recurrent case.

Clearly, the movement of the biased random walk ($X_n$) is determined by the law of the random environment $\omega$. We assume that $(\omega(x, y), y \sim x)$ for $x \in \mathbb{T}$, are i.i.d. random vectors. It is convenient to view $(\omega, \mathbb{T})$ as a marked tree (in the sense of Neveu [23]).

The influence of the random environment is quantified by means of the random potential process ($V(x)$, $x \in \mathbb{T}$), defined by $V(\emptyset) := 0$ and

$$V(x) := - \sum_{y \in \emptyset, x} \log \frac{\omega(\overleftarrow{y}, y)}{\omega(\overleftarrow{y}, \overleftarrow{y})}, \quad x \in \mathbb{T} \setminus \{\emptyset\}, \qquad (1.1)$$

where $\overleftarrow{y}$ is the parent of $\overleftarrow{y}$, and $\emptyset, x] := [\emptyset, x] \setminus \{\emptyset\}$, with $[\emptyset, x]$ denoting the set of vertices (including $x$ and $\emptyset$) on the unique shortest path connecting $\emptyset$ to $x$. There exists an obvious bijection between the random environment $\omega$ and the random potential $V$.

For any $x \in \mathbb{T}$, let $|x|$ denote its generation. Throughout the paper, we assume

$$\mathbf{E}\left(\sum_{x: |x|=1} e^{-V(x)}\right) = 1, \quad \mathbf{E}\left(\sum_{x: |x|=1} V(x) e^{-V(x)}\right) = 0. \qquad (1.2)$$

We also assume that the following integrability condition is fulfilled: there exists $\delta > 0$ such that

$$\mathbf{E}\left(\sum_{x: |x|=1} e^{-(1+\delta)V(x)}\right) + \mathbf{E}\left(\sum_{x: |x|=1} e^{\delta V(x)}\right) + \mathbf{E}\left[\left(\sum_{x: |x|=1} 1\right)^{1+\delta}\right] < \infty. \qquad (1.3)$$

The random potential ($V(x)$, $x \in \mathbb{T}$) is a branching random walk as in Biggins [6]; as such, (1.2) corresponds to the "boundary case" (Biggins and Kyprianou [9]). It is known that, under some additional integrability assumptions that are weaker than (1.3), the branching random walk in the boundary case possesses some deep universality properties, see [25] for references.

Under (1.2) and (1.3), the biased walk ($X_n$) is null recurrent (Lyons and Pemantle [21], Menshikov and Petritis [22], Faraud [12]), such that upon the system's survival,

$$\frac{|X_n|}{(\log n)^2} \xrightarrow{\text{law}} X_\infty, \qquad (1.4)$$

$$\frac{1}{(\log n)^3} \max_{0 \le i \le n} |X_i| \rightarrow c_1 \quad \text{a.s.,} \qquad (1.5)$$

where $X_\infty$ is non-degenerate taking values in $(0, \infty)$, and $c_1$ denotes a positive constant: both $X_\infty$ and $c_1$ are explicitly known, see [18] and [13], respectively.

For any vertex $x \in \mathbb{T}$, let us define

$$L_n(x) := \sum_{i=1}^{n} \mathbf{1}_{\{X_i=x\}}, \quad n \ge 1,$$
which is the (site) local time of the biased walk at $x$. Consider, for any $n \ge 1$, the non-empty random set

$$ \mathcal{A}_n := \{x \in \mathbb{T} : L_n(x) = \max_{y \in \mathbb{T}} L_n(y)\}. \qquad (1.6) $$

In words, $\mathcal{A}_n$ is the set of the most visited sites (or: favourite sites) at time $n$. The study of favourite sites was initiated by Erdős and Révész [11] for the symmetric Bernoulli random walk on the line (see a list of ten open problems presented in Chapter 11 of the book of Révész [24]). In particular, for the symmetric Bernoulli random walk on $\mathbb{Z}$, Erdős and Révész [11] conjectured: (a) tightness for the family of most visited sites, and (b) the cardinality of the set of most visited sites being eventually bounded by 2. Conjecture (b) was partially proved by Tóth [27], and is believed to be true by many. On the other hand, Conjecture (a) was disproved by Bass and Griffin [5]: as a matter of fact, $\inf\{|x|, x \in \mathcal{A}_n\} \to \infty$ almost surely for the one-dimensional Bernoulli walk. Later, we proved in [16] that it was also the case for Sinai's one-dimensional random walk in random environment. The present paper is devoted to studying both questions for biased walks on trees; our answer is as follows.

**Corollary 2.2.** Assume (1.2) and (1.3). There exists a finite non-empty set $\mathcal{U}_{\min}$, defined in (2.5) and depending only on the environment, such that

$$ \lim_{n \to \infty} \mathbb{P}(\mathcal{A}_n \subset \mathcal{U}_{\min} | \text{non-extinction}) = 1. $$

In particular, the family of most visited sites is tight under $\mathbb{P}$.

So, concerning the tightness question for most visited sites, biased walks on trees behave very differently from recurrent one-dimensional nearest-neighbour random walks (whether the environment is random or deterministic). To the best of our knowledge, this is the first non-trivial example of null recurrent Markov chain whose most visited sites are tight.

In the next section, we give a precise statement of the main result of this paper, Theorem 2.1.

## 2 Statement of results

Let us define a symmetrized version of the potential:

$$ U(x) := V(x) - \log\left(\frac{1}{\omega(x, \overleftarrow{x})}\right), \quad x \in \mathbb{T}. \qquad (2.1) $$

Note that

$$ e^{-U(x)} = \frac{1}{\omega(x, \overleftarrow{x})} e^{-V(x)} = e^{-V(x)} + \sum_{y \in \mathbb{T}: \overleftarrow{y}=x} e^{-V(y)}, \quad x \in \mathbb{T}. \qquad (2.2) $$

It is known (Biggins [7], Lyons [20]) that under assumption (1.2),

$$ \inf_{x: |x|=n} U(x) \to \infty, \quad \mathbf{P}^*\text{-a.s.,} \qquad (2.3) $$

where here and in the sequel,

$$ \mathbf{P}^*(\cdot) := \mathbf{P}(\cdot | \text{non-extinction}), $$

$$ \mathbf{P}^*(\cdot) := \mathbf{P}(\cdot | \text{non-extinction}). $$
Define the *derivative martingale*

$$D_n := \sum_{x: |x|=n} V(x)e^{-V(x)}, \quad n \ge 0. \qquad (2.4)$$

It is known (Biggins and Kyprianou [8], Aïdékon [1], Chen [10]) that (1.3) implies that $D_n$ converges **P**-a.s. to a limit, denoted by $D_\infty$, and that

$$D_\infty > 0, \quad \mathbf{P}^*-\text{a.s.}$$

Define the set of the minimizers of $U(\cdot)$:

$$\mathcal{U}_{\min} := \{x \in \mathbb{T} : U(x) = \min_{y \in \mathbb{T}} U(y)\}. \qquad (2.5)$$

Since $\inf_{x: |x|=n} U(x) \to \infty$ **P**\*-a.s. (see (2.3)), the set $\mathcal{U}_{\min}$ is finite and non-empty.
The main result of the paper is as follows.

**Theorem 2.1.** Assume (1.2) and (1.3). For any $\varepsilon > 0$,<fnref n="1" />

$$\sup_{x \in \mathbb{T}} P_{\omega} \left\{ \left| \frac{L_n(x)}{\frac{n}{\log n}} - \frac{\sigma^2}{4D_{\infty}} e^{-U(x)} \right| > \varepsilon \right\} \to 0, \quad \text{in } \mathbf{P}^*-\text{probability},$$

where $U(\cdot)$ is the symmetrized potential in (2.1), $D_\infty$ the **P**\*-almost sure positive limit of the derivative martingale ($D_n$) in (2.4), and

$$\sigma^2 := \mathbf{E} \left( \sum_{y: |y|=1} V(y)^2 e^{-V(y)} \right) \in (0, \infty). \qquad (2.6)$$

**Corollary 2.2.** Assume (1.2) and (1.3). If $\mathcal{A}_n$ is the set of the most visited sites at time $n$ as in (1.6), then

$$\mathbf{P}^*(\mathcal{A}_n \subset \mathcal{U}_{\min}) \to 1,$$

where $\mathcal{U}_{\min}$ is the set of the minimizers of $U(\cdot)$ in (2.5).

Our results are not as strong as they might look like. For example, Theorem 2.1 does not claim that $P_\omega\{\sup_{x \in \mathbb{T}} \left| \frac{L_n(x)}{\frac{n}{\log n}} - \frac{\sigma^2}{4D_\infty} e^{-U(x)} \right| > \varepsilon\} \to 0$ in **P**\*-probability. It essentially says, in view of Proposition 2.3 below, that for any **fixed** $x \in \mathbb{T}$, $P_\omega\{\left| \frac{L_n(x)}{\frac{n}{\log n}} - \frac{\sigma^2}{4D_\infty} e^{-U(x)} \right| > \varepsilon\} \to 0$ in **P**\*-probability. Corollary 2.2 is much weaker than what Tóth [27] proved for the symmetric Bernoulli random walk on $\mathbb{Z}$: for example, it does not claim that $\mathbb{P}^*-\text{a.s.}$, $\mathcal{A}_n \subset \mathcal{U}_{\min}$ for all sufficiently large $n$; we even do not know whether this is true.

For local time at fixed site of biased random walks on Galton-Watson trees in other recurrent regimes, see the recent paper [15].

An important ingredient in the proof of Theorem 2.1 is the following estimate on the local time of vertices that are away from the root:

**Proposition 2.3.** Assume (1.2) and (1.3). Then

$$\lim_{\varepsilon \to 0} \limsup_{n \to \infty} \mathbb{P}^* \left\{ \max_{x \in \mathbb{T}: U(x) \ge \log\left(\frac{8}{\varepsilon^2}\right)} L_n(x) \ge \frac{\varepsilon n}{\log n} \right\} = 0.$$

In the light of the fact that $\inf_{x: |x|=n} U(x) \to \infty$ **P**\*-a.s. (see (2.3)), Proposition 2.3 allows us, in the proof of Theorem 2.1, to estimate the probability for fixed $x$.

Proposition 2.3 is proved in Section 3; Theorem 2.1 and Corollary 2.2 in Section 4.

Throughout the paper, for any pair of vertices $x$ and $y$, we write $x < y$ or $y > x$ if $y$ is a (strict) descendant of $x$, and $x \le y$ or $y \ge x$ if either $y$ is either a (strict) descendant of $x$, or $x$ itself. For any $x \in \mathbb{T}$, we use $x_i$ (for $0 \le i \le |x|$) to denote the ancestor of $x$ in the $i$-th generation; in particular, $x_0 = \emptyset$ and $x_{|x|} = x$.

<footnote n="1">¹By convergence in **P**\*-probability, we mean convergence in probability under **P**\*.</footnote>
### 3 Proof of Proposition 2.3

Before presenting the proof of Proposition 2.3, we outline the overall strategy. We exploit the relation between the local time at $x$, and the hitting time $T_x$ and the return time $T_\emptyset^+$ (defined respectively in (3.4) and (3.5) below). Probabilities involving these random times are known to have standard one-dimensional formulas ((3.6) and (3.7)). Proposition 2.3 is then proved using large deviation properties away from the mean if the potential $U(x)$ is large. Since $U(x)$ is indeed $P^*$-a.s. large uniformly in the tree depth (as seen in (2.3)), we will be done.

We need some preliminaries. Let

$$ \Lambda(x) := \sum_{y: \vec{y}=x} e^{-[V(y)-V(x)]}, \quad x \in \mathbb{T}, \qquad (3.1) $$

In particular, $\Lambda(\emptyset) = \sum_{x: |x|=1} e^{-V(x)}$. By definition,

$$ 1 + \Lambda(x) = \frac{1}{\omega(x, \vec{x})}. $$

Let $S_i - S_{i-1}$, $i \ge 1$, be i.i.d. random variables whose law is characterized by

$$ \mathbb{E}[h(S_1)] = \mathbb{E}\left[\sum_{x \in \mathbb{T}: |x|=1} e^{-V(x)}h(V(x))\right], \qquad (3.2) $$

for any Borel function $h: \mathbb{R} \to \mathbb{R}_+$.

The following fact, quoted from [18], is a variant of the so-called "many-to-one formula" for the branching random walk.

**Fact 3.1.** Assume (1.2) and (1.3). Let $\Lambda(x)$ be as in (3.1). For any $n \ge 1$ and any Borel function $g: \mathbb{R}^{n+1} \to \mathbb{R}_+$, we have

$$ \mathbb{E}\left[\sum_{x \in \mathbb{T}: |x|=n} g(V(x_1), \dots, V(x_n), \Lambda(x))\right] = \mathbb{E}\left[e^{S_n} G(S_1, \dots, S_n)\right], $$

where $S_i - S_{i-1}$, $i \ge 1$, are i.i.d. whose common distribution is given in (3.2), and

$$ G(a_1, \dots, a_n) := \mathbb{E}[g(a_1, \dots, a_n, \sum_{x \in \mathbb{T}: |x|=1} e^{-V(x)})]. $$

Define a reflecting barrier at (notation: $\mathbb{I}\emptyset$, $x[ := ]\emptyset$, $x]\setminus\{x\}$)

$$ \mathcal{L}_n^{(\gamma)} := \left\{ x : \sum_{z \in \mathbb{I}\emptyset, x} e^{V(z)-V(x)} > \frac{n}{(\log n)^\gamma}, \sum_{z \in \mathbb{I}\emptyset, y} e^{V(z)-V(y)} \le \frac{n}{(\log n)^\gamma}, \forall y \in \mathbb{I}\emptyset, x[ \right\}, \qquad (3.3) $$

where $\gamma \in \mathbb{R}$ is a fixed parameter. We write $x < \mathcal{L}_n^{(\gamma)}$ if $\sum_{z \in \mathbb{I}\emptyset, y} e^{V(z)-V(y)} \le \frac{n}{(\log n)^\gamma}$ for all $y \in \mathbb{I}\emptyset$, $x[.

We recall two results from [18]. The first justifies the presence of the barrier $\mathcal{L}_n^{(\gamma)}$ for the biased walk $(X_n)$, and the second describes the local time at the root.

**Fact 3.2 ([18]).** Assume (1.2) and (1.3). If $\gamma < 2$, then

$$ \lim_{n \to \infty} \mathbb{P}\left(\bigcup_{i=1}^{n} \{X_i \in \mathcal{L}_n^{(\gamma)}\}\right) = 0. $$
**Fact 3.3 ([18]).** Assume (1.2) and (1.3). For any $\varepsilon > 0$,

$$P_{\omega}\left\{\left|\frac{L_n(\emptyset)}{\frac{n}{\log n}} - \frac{\sigma^2}{4D_{\infty}} e^{-U(\emptyset)}\right| > \varepsilon\right\} \to 0, \quad \text{in } \mathbf{P}^*\text{-probability.}$$

We now proceed to the proof of Proposition 2.3. Define

$$T_x := \inf\{i \ge 0 : X_i = x\}, \quad x \in \mathbb{T}, \qquad (3.4)$$

$$T_{\emptyset}^{+} := \inf\{i \ge 1 : X_i = \emptyset\}. \qquad (3.5)$$

In words, $T_x$ is the first hitting time at $x$ by the biased walk, whereas $T_{\emptyset}^{+}$ is the first return time to the root $\emptyset$.

Let $x \in \mathbb{T} \setminus \{\emptyset\}$. The probability $P_{\omega}(T_x < T_{\emptyset}^{+})$ only involves a one-dimensional random walk in random environment (namely, the restriction at $[\emptyset, x]$ of the biased walk $(X_i)$), so a standard result for one-dimensional random walks in random environment (Golosov [14]) tells us that

$$P_{\omega}(T_x < T_{\emptyset}^{+}) = \frac{\omega(\emptyset, x_1) e^{V(x_1)}}{\sum_{z \in \emptyset, x} e^{V(z)}} = \frac{\omega(\emptyset, \emptyset)}{\sum_{z \in \emptyset, x} e^{V(z)}}, \qquad (3.6)$$

$$P_{x,\omega}\{T_{\emptyset} < T_x^+\} = \frac{e^{U(x)}}{\sum_{z \in \emptyset, x} e^{V(z)}}, \qquad (3.7)$$

where $x_1$ is the ancestor of $x$ in the first generation.

**Proof of Proposition 2.3.** By Fact 3.2, for all $\gamma_1 < 2$, we have $\mathbb{P}^*(\cup_{i=1}^m \{X_i \in \mathcal{L}_m^{(\gamma_1)}\}) \to 0$, $m \to \infty$. So it suffices to check that for some $\gamma_1 < 2$,

$$\lim_{b \to 0} \limsup_{m \to \infty} \mathbb{P}^* \left\{ \max_{x < \mathcal{L}_m^{(\gamma_1)} : U(x) \ge \log\left(\frac{8}{b^2}\right)} L_m(x) \ge \frac{bm}{\log m} \right\} = 0.$$

Since $\mathbb{P}^*(U(\emptyset) \ge \log(\frac{8}{b^2})) \to 0$ for $b \to 0$, it suffices to prove that for some $\gamma_1 < 2$,

$$\lim_{b \to 0} \limsup_{m \to \infty} \mathbb{P}^* \left\{ \max_{x \in \mathbb{T} \setminus \{\emptyset\} : x < \mathcal{L}_m^{(\gamma_1)}, U(x) \ge \log\left(\frac{8}{b^2}\right)} L_m(x) \ge \frac{bm}{\log m} \right\} = 0. \qquad (3.8)$$

Let $T_{\emptyset}^{(0)} := 0$ and inductively $T_{\emptyset}^{(j)} := \inf\{i > T_{\emptyset}^{(j-1)} : X_i = \emptyset\}$, for $j \ge 1$. In words, $T_{\emptyset}^{(j)}$ is the $j$-th return time to $\emptyset$. We have, for $n \ge 2$, $c > 0$, $\varepsilon \in (0, 1)$, $1 < \gamma < 2$ and $m(n) = \lfloor cn \log n \rfloor$,

$$\begin{aligned} & \mathbb{P}^* \left\{ \max_{x \in \mathbb{T} \setminus \{\emptyset\} : x < \mathcal{L}_{m(n)}^{(\gamma)}, U(x) \ge \log\left(\frac{8}{\varepsilon}\right)} L_{m(n)}(x) \ge \varepsilon n \right\} \\ & \le \mathbb{P}^* \{T_{\emptyset}^{(n)} \le m(n)\} + \mathbb{P}^* \left\{ \max_{x \in \mathbb{T} \setminus \{\emptyset\} : x < \mathcal{L}_{m(n)}^{(\gamma)}, U(x) \ge \log\left(\frac{8}{\varepsilon}\right)} L_{T_{\emptyset}^{(n)}}(x) \ge \varepsilon n \right\}. \end{aligned}$$

By Fact 3.3, $\frac{T_{\emptyset}^{(n)}}{n \log n} \to \frac{4D_{\infty}}{\sigma^2} e^{U(\emptyset)}$ in $\mathbb{P}^*$-probability, so the portmanteau theorem implies that $\limsup_{n \to \infty} \mathbb{P}^*\{T_{\emptyset}^{(n)} \le m(n)\} \le \mathbb{P}^*\{\frac{4D_{\infty}}{\sigma^2} e^{U(\emptyset)} \le c\}$. Assume, for the time being, that we are able to prove that for some $\gamma < 2$, any $c > 0$ and any $0 < \varepsilon < 1$,

$$\mathbb{P}^* \left\{ \max_{x \in \mathbb{T} \setminus \{\emptyset\} : x < \mathcal{L}_{m(n)}^{(\gamma)}, U(x) \ge \log\left(\frac{8}{\varepsilon}\right)} L_{T_{\emptyset}^{(n)}}(x) \ge \varepsilon n \right\} \to 0, \quad n \to \infty. \qquad (3.9)$$

Then we will have

$$\limsup_{n \to \infty} \mathbb{P}^* \left\{ \max_{x \in \mathbb{T} \setminus \{\emptyset\} : x < \mathcal{L}_{m(n)}^{(\gamma)}, U(x) \ge \log\left(\frac{8}{\varepsilon}\right)} L_{m(n)}(x) \ge \varepsilon n \right\} \le \mathbb{P}^* \left\{ \frac{4D_{\infty}}{\sigma^2} e^{U(\emptyset)} \le c \right\}.$$
Since $n \le \frac{2m(n+1)}{c \log m(n)}$ (for all sufficiently large $n$), this will yield

$$ \limsup_{n \to \infty} \mathbb{P}^* \left\{ \max_{x \in \mathbb{T} \setminus \{\emptyset\}: x \in \mathcal{L}_{m(n)}^{(\gamma)}} L_{m(n)}(x) \ge \frac{2\varepsilon m(n+1)}{c \log m(n)} \right\} \le \mathbb{P}^* \left\{ \frac{4D_\infty}{\sigma^2} e^{U(\emptyset)} \le c \right\}. $$

Let $m \in [m(n), m(n+1)] \cap \mathbb{Z}$. Then $L_{m(n)}(x) \le L_m(x)$ (for all $x \in \mathbb{T}$); on the other hand, if $x \in \mathcal{L}_{m(n)}^{(\gamma_1)}$, then $x \in \mathcal{L}_{m(n)}^{(\gamma)}$ for all $\gamma_1 \in (\gamma, 2)$ and all sufficiently large $n$. Consequently, we will have, for all $c > 0$ and $\varepsilon \in (0, 1)$,

$$ \limsup_{m \to \infty} \mathbb{P}^* \left\{ \max_{x \in \mathbb{T} \setminus \{\emptyset\}: x \in \mathcal{L}_{m(n)}^{(\gamma_1)}, U(x) \ge \log(\frac{8}{\varepsilon})} L_m(x) \ge \frac{2\varepsilon m}{c \log m} \right\} \le \mathbb{P}^* \left\{ \frac{4D_\infty}{\sigma^2} e^{U(\emptyset)} \le c \right\}. $$

Taking $c := 2\varepsilon^{1/2}$ will then yield (3.8) (writing $b := \varepsilon^{1/2}$ there) and thus Proposition 2.3.

The rest of the section is devoted to the proof of (3.9). By (1.5), $\frac{1}{(\log n)^3} \max_{0 \le i \le n} |X_i|$ converges $P^*$-a.s. to a positive constant, and since $\frac{T_{\emptyset}^{(n)}}{n \log n}$ converges in $P^*$-probability to a positive limit, we deduce that $\frac{1}{(\log n)^3} \max_{0 \le i \le T_{\emptyset}^{(n)}} |X_i|$ converges in $P^*$-probability to a positive limit. So the proof of (3.9) is reduced to showing the following estimate: for some $1 < \gamma < 2$, any $c > 0$ and any $0 < \varepsilon < 1$,

$$ \mathbb{P}^* \left\{ \max_{x \in \mathcal{L}_{m(n)}^{(\gamma)}: U(x) \ge \log(\frac{8}{\varepsilon}), 1 \le |x| \le (\log n)^4} L_{T_{\emptyset}^{(n)}}(x) \ge \varepsilon n \right\} \to 0, \quad n \to \infty. $$

For $k \ge 1$, we have

$$ \begin{aligned} & P_{\omega} \left\{ \max_{x \in \mathcal{L}_{m(n)}^{(\gamma)}: U(x) \ge \log(\frac{8}{\varepsilon}), 1 \le |x| \le (\log n)^4} L_{T_{\emptyset}^{(n)}}(x) \ge k \right\} \\ & \le \sum_{x \in \mathcal{L}_{m(n)}^{(\gamma)}: U(x) \ge \log(\frac{8}{\varepsilon}), 1 \le |x| \le (\log n)^4} P_{\omega} \{ L_{T_{\emptyset}^{(n)}}(x) \ge k \}. \end{aligned} $$

The law of $L_{T_{\emptyset}^{(n)}}(x)$ under $P_{\omega}$ is the law of $\sum_{i=1}^n \xi_i$, where $(\xi_i, i \ge 1)$ is an i.i.d. sequence with $P_{\omega}(\xi_1 = 0) = 1 - a$ and $P_{\omega}(\xi_1 \ge k) = a p^{k-1}, \forall k \ge 1$, where

$$ 1 - p := P_{x,\omega}\{T_{\emptyset} < T_x^+\} = \frac{e^{U(x)}}{\sum_{z \in \emptyset, x] \} e^{V(z)}}, \quad (3.10) $$

$$ a := P_{\omega}\{T_x < T_{\emptyset}^{+}\} = \frac{\omega(\emptyset, \overleftarrow{\emptyset})}{\sum_{z \in \emptyset, x] \} e^{V(z)}}. \quad (3.11) $$

[We have used (3.6) and (3.7).]

The tail estimate of $L_{T_{\emptyset}^{(n)}}(x)$ under $P_{\omega}$ is summarized in the following elementary lemma, whose proof is in the Appendix.

**Lemma 3.4.** Let $0 < a < 1$ and $0 < p < 1$. Let $(\xi_i, i \ge 1)$ be an i.i.d. sequence of random variables with $\mathbf{P}(\xi_1 = 0) = 1 - a$ and $\mathbf{P}(\xi_1 \ge k) = a p^{k-1}, \forall k \ge 1$.

Let $0 < \varepsilon < 1$. If $1 - p > \frac{8}{\varepsilon}a$, then

$$ \mathbf{P}\left\{\sum_{i=1}^{n} \xi_i \geq [\varepsilon n]\right\} \leq 6na e^{-\frac{(1-p)\varepsilon n}{8}}. $$
We continue with the proof of (3.9). If $U(x) \ge \log(\frac{8}{\epsilon})$, then $1-p > \frac{8}{\epsilon}a$, so we are entitled to apply Lemma 3.4 to arrive at:

$$ P_{\omega} \left\{ \begin{array}{l} \max_{x < \mathcal{L}_{m(n)}^{(\gamma)} : U(x) \ge \log(\frac{8}{\epsilon}), 1 \le |x| \le (\log n)^4} L_{T_{\emptyset}^{(n)}}(x) \ge \lceil \epsilon n \rceil \\ \\ \le 6n \sum_{x < \mathcal{L}_{m(n)}^{(\gamma)} : 1 \le |x| \le (\log n)^4} \frac{\omega(\emptyset, \overleftarrow{\emptyset})}{\sum_{z \in \emptyset} e^{V(z)}} \exp \left( - \frac{\epsilon n}{8} \frac{e^{U(x)}}{\sum_{z \in \emptyset} e^{V(z)}} \right) \end{array} \right\} $$

We have $\omega(\emptyset, \overleftarrow{\emptyset}) \le 1$. It remains to check the following convergence in $\mathbf{P}^*$-probability (for $n \to \infty$):

$$ \sum_{x < \mathcal{L}_{m(n)}^{(\gamma)}} 1 \le |x| \le (\log n)^4 \frac{n}{\sum_{z \in \emptyset, x]} e^{V(z)}} \exp \left( - \frac{\epsilon}{8} \frac{n e^{U(x)}}{\sum_{z \in \emptyset, x]} e^{V(z)}} \right) \to 0. \quad (3.12) $$

Recall the definition of $\mathcal{L}_{m(n)}^{(\gamma)}: x < \mathcal{L}_{m(n)}^{(\gamma)}$ implies $\frac{e^{V(x)}}{\sum_{z \in \emptyset, x]} e^{V(z)}} \ge \frac{(\log m(n))^{\gamma}}{m(n)}$, which is $\ge \frac{(\log n)^{\gamma-1}}{cn}$ for all sufficiently large $n$ (say $n \ge n_0$). Also, we recall that $e^{U(x)} = \frac{e^{V(x)}}{1+\Lambda(x)}$, with $\Lambda(x) := \sum_{y: \overleftarrow{y}=x} e^{-[V(y)-V(x)]}$ as in (3.1).

For the sum $\sum_{x < \mathcal{L}_{m(n)}^{(\gamma)}}$ on the left-hand side of (3.12), we distinguish two possible situations depending on the value of $\Lambda(x)$. Let $0 < \varrho < 1$. Applying the elementary inequality $\lambda e^{-\lambda} \le c_2 e^{-\lambda/2}$ (for $\lambda \ge 0$) to $\lambda := \frac{\epsilon}{8} \frac{n e^{U(x)}}{\sum_{z \in \emptyset, x]} e^{V(z)}}$, we see that for $n \ge n_0$,

$$ \begin{aligned} & \sum_{x < \mathcal{L}_{m(n)}^{(\gamma)}} 1 \{1+\Lambda(x) \le \left( \frac{n e^{V(x)}}{\sum_{z \in \emptyset, x]} e^{V(z)} \right)^{\varrho} \} \frac{n}{\sum_{z \in \emptyset, x]} e^{V(z)}} \exp \left( - \frac{\epsilon}{8} \frac{n e^{U(x)}}{\sum_{z \in \emptyset, x]} e^{V(z)}} \right) \\ & \le c_2 \sum_{x < \mathcal{L}_{m(n)}^{(\gamma)}} 1 \{1+\Lambda(x) \le \left( \frac{n e^{V(x)}}{\sum_{z \in \emptyset, x]} e^{V(z)} \right)^{\varrho} \} \frac{8}{\epsilon} e^{-U(x)} \exp \left( - \frac{\epsilon}{16(1+\Lambda(x))} \frac{n e^{U(x)}}{\sum_{z \in \emptyset, x]} e^{V(z)}} \right) \\ & \le \frac{8c_2}{\epsilon} \sum_{x < \mathcal{L}_{m(n)}^{(\gamma)}} e^{-U(x)} \exp \left( - \frac{\epsilon}{16} \left( \frac{n e^{V(x)}}{\sum_{z \in \emptyset, x]} e^{V(z)} \right)^{1-\varrho} \right). \end{aligned} $$

Since $\frac{n e^{V(x)}}{\sum_{z \in \emptyset, x]} e^{V(z)}} \ge \frac{1}{c} (\log n)^{\gamma-1}$ (for $x < \mathcal{L}_{m(n)}^{(\gamma)}$ and $n \ge n_0$), this yields, for $n \ge n_0$,

$$ \begin{aligned} & \sum_{x < \mathcal{L}_{m(n)}^{(\gamma)}} 1 \{1+\Lambda(x) \le \left( \frac{n e^{V(x)}}{\sum_{z \in \emptyset, x]} e^{V(z)} \right)^{\varrho} \} \frac{n}{\sum_{z \in \emptyset, x]} e^{V(z)}} \exp \left( - \frac{\epsilon}{8} \frac{n e^{U(x)}}{\sum_{z \in \emptyset, x]} e^{V(z)}} \right) \\ & \le \frac{8c_2}{\epsilon} \exp \left( - \frac{\epsilon}{16c^{1-\varrho}} (\log n)^{(\gamma-1)(1-\varrho)} \right) \sum_{x < \mathcal{L}_{m(n)}^{(\gamma)}} e^{-U(x)}, \end{aligned} $$

which converges to 0 in $\mathbf{P}^*$-probability (recalling that for any $\gamma \in \mathbb{R}$, $\frac{1}{\log n} \sum_{x \in \mathbb{T}: x < \mathcal{L}_{m(n)}^{(\gamma)}} e^{-U(x)}$ converges in $\mathbf{P}^*$-probability to a finite limit; see [18]). So it remains to prove that there exists $\varrho \in (0, 1)$ such that (removing the big exponential term which is bounded by 1)

$$ \sum_{x < \mathcal{L}_{m(n)}^{(\gamma)}} 1 \{1+\Lambda(x) > \left( \frac{n e^{V(x)}}{\sum_{z \in \emptyset, x]} e^{V(z)} \right)^{\varrho} \} \frac{n}{\sum_{z \in \emptyset, x]} e^{V(z)} \to 0, $$

in $\mathbf{P}^*$-probability (for $n \to \infty$). Since $\lim_{r \to \infty} \inf_{|x|=r} V(x) \to \infty$ $\mathbf{P}^*$-a.s. (see (2.3)), it suffices to prove the existence of $\varrho \in (0, 1)$ and $\gamma \in (1, 2)$ such that for all $\alpha > 0$ and
$$n \to \infty, \quad \sum_{x < \mathcal{L}_{m(n)}^{(\gamma)}} \mathbf{1}_{\{1+\Lambda(x) > \left(\frac{n e^{V(x)}}{\sum_{z \in \mathcal{F}, x] e^{V(z)}}}\right)^e\}} \frac{n}{\sum_{z \in \mathcal{F}, x]} e^{V(z)} \mathbf{1}_{\{\underline{V}(x) \ge -\alpha\}} \to 0, \quad (3.13)$$

in $\mathbf{P}^*$-probability, where $\underline{V}(x) := \min_{z \in \mathcal{F}, x]} V(z)$.

To prove this, we first recall that $x < \mathcal{L}_{m(n)}^{(\gamma)}$ implies that for all $y \in \mathcal{F}, x$], we have $\frac{\sum_{z \in \mathcal{F}, y]} e^{V(z)}}{e^{V(y)}} \le \frac{cn}{(\log n)^{\gamma-1}}$ (for $n \ge n_0$) which is bounded by $n$ for all sufficiently large $n$ (say $n \ge n_1$); a fortiori $\bar{V}(y) - V(y) \le \log n$ (with $\bar{V}(y) := \max_{z \in \mathcal{F}, y]} V(y)$). By Fact 3.1, we obtain, for $n \ge n_0 \lor n_1$,

$$ \begin{aligned} & \mathbf{E} \left[ \sum_{x < \mathcal{L}_{m(n)}^{(\gamma)}} \mathbf{1}_{\{1+\Lambda(x) > \left(\frac{n e^{V(x)}}{\sum_{z \in \mathcal{F}, x]} e^{V(z)}\right)^e\}} \frac{n}{\sum_{z \in \mathcal{F}, x]} e^{V(z)} \mathbf{1}_{\{\underline{V}(x) \ge -\alpha\}} \right] \\ & \le \sum_{k=1}^{\lfloor(\log n)^4\rfloor} \mathbf{E} \left[ \sum_{x: |x|=k} \mathbf{1}_{\{\bar{V}(y)-V(y) \le \log n, \forall y \in \mathcal{F}, x\}} \right] \times \\ & \qquad \mathbf{1}_{\{1+\Lambda(x) > \left(\frac{n e^{V(x)}}{\sum_{z \in \mathcal{F}, x]} e^{V(z)}\right)^e\}} \frac{n}{\sum_{z \in \mathcal{F}, x]} e^{V(z)} \mathbf{1}_{\{\underline{V}(x) \ge -\alpha\}} \right] \\ & = \sum_{k=1}^{\lfloor(\log n)^4\rfloor} \mathbf{E} \left[ e^{S_k} \mathbf{1}_{\{S_k^{\#} \le \log n\}} F\left(\left(\frac{n e^{S_k}}{\sum_{i=1}^k e^{S_i}}\right)^e\right) \frac{n}{\sum_{i=1}^k e^{S_i}} \mathbf{1}_{\{\underline{S}_k \ge -\alpha\}} \right], \end{aligned} $$

where $F(\lambda) := \mathbf{P}(1+\sum_{x: |x|=1} e^{-V(x)} > \lambda)$ for $\lambda > 0$, $\bar{S}_k := \max_{1 \le i \le k} S_i$, $\underline{S}_k := \min_{1 \le i \le k} S_i$, and $S_k^{\#} := \max_{1 \le i \le k} (\bar{S}_i - S_i)$ for any $k \ge 1$.

An application of the Hölder inequality, using assumption (1.3), yields the existence of $\delta_1 > 0$ such that

$$ \mathbf{E} \left[ \left( \sum_{x: |x|=1} e^{-V(x)} \right)^{1+\delta_1} \right] < \infty. \quad (3.14) $$

As such, $c_3 := \mathbf{E}[(1 + \sum_{x: |x|=1} e^{-V(x)})^{1+\delta_1}] < \infty$, so $F(\lambda) \le c_3 \lambda^{-1-\delta_1}$ for all $\lambda > 0$. Consequently,

$$ \begin{aligned} & \mathbf{E} \left[ \sum_{x < \mathcal{L}_{m(n)}^{(\gamma)}} \mathbf{1}_{\{1+\Lambda(x) > \left(\frac{n e^{V(x)}}{\sum_{z \in \mathcal{F}, x]} e^{V(z)}\right)^e\}} \frac{n}{\sum_{z \in \mathcal{F}, x]} e^{V(z)} \mathbf{1}_{\{\underline{V}(x) \ge -\alpha\}} \right] \\ & \le c_3 \sum_{k=1}^{\lfloor(\log n)^4\rfloor} \mathbf{E} \left[ \left( \frac{\sum_{i=1}^k e^{S_i}}{n e^{S_k}} \right)^{\varrho(1+\delta_1)-1} \mathbf{1}_{\{S_k^{\#} \le \log n\}} \mathbf{1}_{\{\underline{S}_k \ge -\alpha\}} \right]. \end{aligned} \quad (3.15) $$

**Lemma 3.5.** Let $\delta$ be the constant in assumption (1.3). For all $\alpha > 0$ and $\delta_2 \in (0, \delta \wedge \frac{1}{16})$,

$$ \lim_{n \to \infty} \sum_{k=1}^{\lfloor(\log n)^4\rfloor} \mathbf{E} \left[ \left( \frac{\sum_{i=1}^k e^{S_i}}{n e^{S_k}} \right)^{\delta_2} \mathbf{1}_{\{S_k^{\#} \le \log n\}} \mathbf{1}_{\{\underline{S}_k \ge -\alpha\}} \right] = 0. $$

Since it is possible to choose $0 < \varrho < 1$ such that $\varrho(1 + \delta_1) - 1$ lies in $(0, \delta \wedge \frac{1}{16})$, we can apply Lemma 3.5 to see that (3.15) implies (3.13), and thus yields Proposition 2.3. It remains to prove Lemma 3.5.

**Proof of Lemma 3.5.** Since $\sum_{i=1}^k e^{S_i} \le k e^{\bar{S}_k}$, it suffices to check that

$$ \frac{(\log n)^{4\delta_2}}{n^{\delta_2}} \sum_{k=1}^{\lfloor(\log n)^4\rfloor} \mathbf{E} \left[ e^{\delta_2(\bar{S}_k - S_k)} \mathbf{1}_{\{S_k^{\#} \le \log n\}} \mathbf{1}_{\{\underline{S}_k \ge -\alpha\}} \right] \to 0. $$
Recall the law of $S_1$ from (3.2). By assumption (1.3) and Hölder's inequality, we have

$$ \mathbf{E}(e^{aS_1}) < \infty, \quad \forall a \in (-\delta, 1+\delta), $$

where $\delta > 0$ is the constant in (1.3). In particular, $\mathbf{E}(e^{a|S_1|}) < \infty$ for all $0 \le a < \delta$. Since $0 < \delta_2 < \delta$, we have $\mathbf{E}(e^{\delta_2(\bar{S}_k - S_k)}) \le e^{c_4 k}$ for some constant $c_4 > 0$ and all $k \ge 1$. So $\frac{(\log n)^{4\delta_2}}{n^{\delta_2}} \sum_{k=1}^{\lfloor (\log n)^{1/2} \rfloor} \mathbf{E}[e^{\delta_2(\bar{S}_k - S_k)}] \to 0$. It remains to prove that

$$ \frac{(\log n)^{4\delta_2}}{n^{\delta_2}} \sum_{k=\lfloor (\log n)^{1/2} \rfloor}^{\lfloor (\log n)^4 \rfloor} \mathbf{E} \left[ e^{\delta_2 (\bar{S}_k - S_k)} \mathbf{1}_{\{S_k^{\#} \le \log n\}} \mathbf{1}_{\{\underline{S}_k \ge -\alpha\}} \right] \to 0. $$

We make a change of indices $k = \lfloor (\log n)^{1/2} \rfloor + \ell$. Let $\tilde{S}_\ell := S_{\ell+\lfloor (\log n)^{1/2} \rfloor} - S_{\lfloor (\log n)^{1/2} \rfloor}$, $\ell \ge 0$. Then $(\tilde{S}_\ell, \ell \ge 0)$ is a random walk having the law of $(S_\ell, \ell \ge 0)$, and is independent of $(S_i, 1 \le i \le \lfloor (\log n)^{1/2} \rfloor)$. For $\ell \ge 0$, $\bar{S}_{\ell+\lfloor (\log n)^{1/2} \rfloor} - S_{\ell+\lfloor (\log n)^{1/2} \rfloor} = \max(x, \max_{0 \le j \le \ell} \tilde{S}_j) - \tilde{S}_\ell \ge \max_{0 \le j \le \ell} \tilde{S}_j - \tilde{S}_\ell$, where $x := \bar{S}_{\lfloor (\log n)^{1/2} \rfloor} - S_{\lfloor (\log n)^{1/2} \rfloor}$. So for $k \ge \lfloor (\log n)^{1/2} \rfloor$ and $\ell := k - \lfloor (\log n)^{1/2} \rfloor$, on the event that $\{\underline{S}_k \ge -\alpha\}$, either $\max_{0 \le j \le \ell} \tilde{S}_j \le x$, then $\bar{S}_k - S_k = x - \tilde{S}_\ell = \bar{S}_{\lfloor (\log n)^{1/2} \rfloor} - S_k \le \bar{S}_{\lfloor (\log n)^{1/2} \rfloor} + \alpha$, or $\max_{0 \le j \le \ell} \tilde{S}_j > x$, then $\bar{S}_k - S_k = \max_{0 \le j \le \ell} \tilde{S}_j - \tilde{S}_\ell$. It follows that

$$ \mathbf{E} \left[ e^{\delta_2 (\bar{S}_k - S_k)} \mathbf{1}_{\{S_k^{\#} \le \log n\}} \mathbf{1}_{\{\underline{S}_{\lfloor (\log n)^{1/2} \rfloor} \ge -\alpha\}} \right] \\ \le \mathbf{E} \left( e^{\delta_2 (\alpha + \bar{S}_{\lfloor (\log n)^{1/2} \rfloor})} \right) + \mathbf{P} \left( \underline{S}_{\lfloor (\log n)^{1/2} \rfloor} \ge -\alpha \right) \times \mathbf{E} \left[ e^{\delta_2 (\bar{S}_\ell - S_\ell)} \mathbf{1}_{\{S_\ell^{\#} \le \log n\}} \right]. $$

Since $\mathbf{E}(e^{\delta_2 \bar{S}_{\lfloor (\log n)^{1/2} \rfloor}}) \le e^{c_4 (\log n)^{1/2}}$, we have $\frac{(\log n)^{4\delta_2}}{n^{\delta_2}} \sum_{k=\lfloor (\log n)^{1/2} \rfloor}^{\lfloor (\log n)^4 \rfloor} \mathbf{E}(e^{\delta_2 (\alpha + \bar{S}_{\lfloor (\log n)^{1/2} \rfloor})}) \to 0$. On the other hand, $\mathbf{P}(\underline{S}_{\lfloor (\log n)^{1/2} \rfloor} \ge -\alpha) \le c_5 (\log n)^{-1/4}$ for some constant $c_5 > 0$ and all $n \ge 2$ (see Kozlov [19]); it suffices to prove that

$$ \frac{(\log n)^{4\delta_2 - (1/4)}}{n^{\delta_2}} \sum_{\ell=0}^{\infty} \mathbf{E} \left[ e^{\delta_2 (\bar{S}_\ell - S_\ell)} \mathbf{1}_{\{S_\ell^{\#} \le \log n\}} \right] \to 0. $$

This will be a straightforward consequence of the following estimate (applied to $\lambda := \log n$ and $b := \delta_2$; it is here we use the condition $\delta_2 < \frac{1}{16}$): for any $0 < b < \delta$,

$$ \limsup_{\lambda \to \infty} \mathbf{E} \left( \sum_{\ell=0}^{\tau_\lambda - 1} e^{-b[\lambda - (\bar{S}_\ell - S_\ell)]} \right) < \infty, \quad (3.16) $$

where $\tau_\lambda := \inf\{i \ge 1 : \bar{S}_i - S_i > \lambda\}$.

To prove (3.16), we define the (strictly) ascending ladder times $(H_i, i \ge 0)$: $H_0 := 0$ and for any $i \ge 1$,

$$ H_i := \inf\{\ell > H_{i-1} : S_\ell > \max_{0 \le j \le H_{i-1}} S_j\}. $$

Therefore,

$$ \mathbf{E} \left( \sum_{\ell=0}^{\tau_\lambda - 1} e^{b(\bar{S}_\ell - S_\ell)} \right) = \sum_{i=1}^{\infty} \mathbf{E} \left( \sum_{\ell=H_{i-1}}^{H_i - 1} e^{b(S_{H_{i-1}} - S_\ell)} \mathbf{1}_{\{S_\ell^{\#} \le \lambda\}} \right). $$

We apply the strong Markov property, first at time $H_{i-1}$ to see that

$$ \mathbf{E} \left( \sum_{\ell=H_{i-1}}^{H_i-1} e^{b(S_{H_{i-1}} - S_\ell)} \mathbf{1}_{\{S_\ell^{\#} \le \lambda\}} \right) \le \mathbf{P} \left( S_{H_{i-1}}^{\#} \le \lambda \right) \mathbf{E} \left( \sum_{\ell=0}^{H_i-1} e^{-bS_\ell} \mathbf{1}_{\{S_\ell^{\#} \le \lambda\}} \right), $$
and then successively at times $H_1, H_2, \dots, H_{i-1}$ to see that $\mathbf{P}(S_{H_{i-1}}^{\#} \le \lambda) \le \mathbf{P}(S_{H_1}^{\#} \le \lambda)^{i-1}$. As such,

$$ \mathbf{E}\left(\sum_{\ell=0}^{\tau_{\lambda}-1} e^{b(\bar{S}_{\ell}-S_{\ell})}\right) \le \sum_{i=1}^{\infty} \mathbf{P}\left(S_{H_1}^{\#} \le \lambda\right)^{i-1} \mathbf{E}\left(\sum_{\ell=0}^{H_1-1} e^{-bS_{\ell}} 1_{\{S_{\ell}^{\#} \le \lambda\}}\right). $$

We define $\sigma_{-\lambda} := \inf\{n \ge 0 : S_n < -\lambda\}$. Then $1 - \mathbf{P}(S_{H_1}^{\#} \le \lambda) = \mathbf{P}(\sigma_{-\lambda} < H_1) \ge \frac{c_6}{1+\lambda}$ for some constant $c_6 > 0$ and all sufficiently large $\lambda$, say $\lambda \ge \lambda_0$ (for the last elementary inequality, see for example, Lemma A.1 in [17]). Thus we get that

$$ \mathbf{E}\left(\sum_{\ell=0}^{\tau_{\lambda}-1} e^{b(\bar{S}_{\ell}-S_{\ell})}\right) \le \frac{1+\lambda}{c_6} \mathbf{E}\left(\sum_{\ell=0}^{H_1-1} e^{-bS_{\ell}} 1_{\{S_{\ell}^{\#} \le \lambda\}}\right). $$

Finally, for all small $b > 0$, there exists some positive constant $c_7 = c_7(b) > 0$ such that

$$ \mathbf{E}\left(\sum_{\ell=0}^{H_1-1} e^{-bS_{\ell}} 1_{\{S_{\ell}^{\#} \le \lambda\}}\right) = \mathbf{E}\left(\sum_{\ell=0}^{H_1-1} e^{-bS_{\ell}} 1_{\{\sigma_{-\lambda} > \ell\}}\right) \le \frac{c_7}{\lambda} e^{b\lambda}, $$

by applying [2] (Lemma 6, formula (4.17)) to $(-S_i, i \ge 1)$. This yields (3.16), and completes the proof of Lemma 3.5 and Proposition 2.3. $\square$

## 4 Proof of Theorem 2.1 and Corollary 2.2

*Proof of Theorem 2.1.* Recall that $\lim_{k \to \infty} \inf_{x: |x|=k} U(x) \to \infty$ $\mathbf{P}^*$-a.s. (see (2.3)). In view of Proposition 2.3, we only need to prove that for any fixed $x \in \mathbb{T}$ and $\varepsilon > 0$, when $n \to \infty$,

$$ P_{\omega}\left\{\left|\frac{L_{n}(x)}{\frac{n}{\log n}} - \frac{\sigma^{2}}{4D_{\infty}} e^{-U(x)}\right| > \varepsilon\right\} \to 0, \quad \text{in } \mathbf{P}^*\text{-probability.} $$

According to Fact 3.3, this is equivalent to convergence in $\mathbf{P}^*$-probability $P_{\omega}\{\left|\frac{L_n(x)}{L_n(\emptyset)} - e^{-[U(x)-U(\emptyset)]}\right| > \varepsilon\} \to 0$ (for $n \to \infty$), and thus to the following statement: for any $x \in \mathbb{T}$ and $m \to \infty$,

$$ P_{\omega}\left\{\left|\frac{L_{T_{\emptyset}^{(m)}}(x)}{m} - e^{-[U(x)-U(\emptyset)]}\right| > \varepsilon\right\} \to 0, \quad \text{in } \mathbf{P}^*\text{-probability,} $$

where $T_{\emptyset}^{(m)}$ is as before, the $m$-th return time of the biased walk $(X_i)$ to the root $\emptyset$. This, however, holds trivially as $L_{T_{\emptyset}^{(m)}}(x) - L_{T_{\emptyset}^{(m-1)}}(x), m \ge 1$, are i.i.d. random variables under $P_{\omega}$ with $E_{\omega}[L_{T_{\emptyset}^{(1)}}(x)] = \frac{a}{1-p} = e^{-[U(x)-U(\emptyset)]}$ (see the notation at (3.10)-(3.11) as well as the discussion preceding the equations). Theorem 2.1 is proved. $\square$

*Proof of Corollary 2.2.* Let $\varepsilon > 0$ and $0 < a < \frac{1}{2}$. Let

$$ E_n(\varepsilon, a) := \left\{ \omega : \sup_{x \in \mathbb{T}} P_{\omega}\left(\left|\frac{L_n(x)}{\frac{n}{\log n}} - \frac{\sigma^2}{4D_{\infty}} e^{-U(x)}\right| > \varepsilon\right) < a \right\}. $$

By Theorem 2.1, $\mathbf{P}^*(E_n(\varepsilon, a)) \to 1, n \to \infty$.

Let $x_n \in \mathcal{A}_n$, and let $x_{\min} \in \mathcal{W}_{\min}$. For all $\omega \in E_n(\varepsilon, a)$, we have

$$ P_{\omega}\left(\left|\frac{L_n(y)}{\frac{n}{\log n}} - \frac{\sigma^2}{4D_{\infty}} e^{-U(y)}\right| \le \varepsilon\right) \ge 1 - a, $$
for $y = x_n$ and for $y = x_{\min}$; hence, for all $\omega \in E_n(\epsilon, a)$,

$$P_{\omega}\left(\frac{L_n(x_n)}{\frac{n}{\log n}} \le \frac{\sigma^2}{4D_{\infty}} e^{-U(x_n)} + \epsilon, \frac{L_n(x_{\min})}{\frac{n}{\log n}} \ge \frac{\sigma^2}{4D_{\infty}} e^{-U(x_{\min})} - \epsilon\right) \ge 1 - 2a.$$

By definition, $L_n(x_n) = \sup_{x \in \mathbb{T}} L_n(x) \ge L_n(x_{\min})$. Therefore, for all $\omega$,

$$P_{\omega}\left(\frac{\sigma^2}{4D_{\infty}} e^{-U(x_n)} \ge \frac{\sigma^2}{4D_{\infty}} e^{-U(x_{\min})} - 2\epsilon\right) \ge (1 - 2a) \mathbf{1}_{E_n(\epsilon, a)}(\omega).$$

Taking expectation with respect to $\mathbf{P}^*$ on both sides gives that

$$\mathbf{P}^*\left(\frac{\sigma^2}{4D_{\infty}} e^{-U(x_n)} \ge \sup_{x \in \mathbb{T}} \frac{\sigma^2}{4D_{\infty}} e^{-U(x)} - 2\epsilon\right) \ge (1 - 2a) \mathbf{P}^*(E_n(\epsilon, a)),$$

which converges to $1-2a$ when $n \to \infty$. Since $a > 0$ can be as small as possible, this yields $\frac{\sigma^2}{4D_{\infty}} e^{-U(x_n)} \to \sup_{x \in \mathbb{T}} \frac{\sigma^2}{4D_{\infty}} e^{-U(x)}$ in probability under $\mathbf{P}^*$, i.e., $U(x_n) \to \inf_{x \in \mathbb{T}} U(x)$ in probability under $\mathbf{P}^*$.

Since $\mathcal{U}_{\min}$, the set of the minimizers of $U(\cdot)$, is $\mathbf{P}^*$-a.s. finite, we have $\inf_{x \in \mathcal{U}_{\min}} U(x) < \inf_{x \in \mathbb{T} \setminus \mathcal{U}_{\min}} U(x) \mathbf{P}^*$-a.s., which yields $\mathbf{P}^*(x_n \in \mathcal{U}_{\min}) \to 1, n \to \infty$. $\square$

## A Appendix: Proof of Lemma 3.4

Let $s \in [1, \frac{1}{p})$. Then $\mathbf{E}(s^{\xi_1}) = 1 - a + \frac{a(1-p)s}{1-ps}$. So

$$\mathbf{P}\left\{\sum_{i=1}^{n} \xi_i \ge k\right\} \le \frac{1}{s^k} \mathbf{E}\left[s^{\sum_{i=1}^{n} \xi_i} \mathbf{1}_{\{\sum_{i=1}^{n} \xi_i > 0\}}\right] = \frac{[\mathbf{E}(s^{\xi_1})]^n - [\mathbf{P}\{\xi_1 = 0\}]^n}{s^k}.$$

Observe that

$$[\mathbf{E}(s^{\xi_1})]^n - [\mathbf{P}\{\xi_1 = 0\}]^n = \left(1 - a + \frac{a(1-p)s}{1-ps}\right)^n - (1-a)^n \\ \le n \frac{a(1-p)s}{1-ps} \left(1 - a + \frac{a(1-p)s}{1-ps}\right)^{n-1},$$

where, in the last line, we used $x^n - y^n \le n(x - y)x^{n-1}$ (for $0 \le y \le x$). Hence

$$\mathbf{P}\left\{\sum_{i=1}^{n} \xi_i \ge k\right\} \le s^{-k} n \frac{a(1-p)s}{1-ps} \left(1 - a + \frac{a(1-p)s}{1-ps}\right)^{n-1}. \quad (A.1)$$

First case: $\frac{1}{3} \le p < 1$. We take $s := \frac{1+p}{2p} \in [1, \frac{1}{p})$, so that $\frac{(1-p)s}{1-ps} = \frac{1+p}{p}$; hence by (A.1),

$$\begin{aligned} \mathbf{P}\left\{\sum_{i=1}^{n} \xi_i \ge k\right\} & \le \left(\frac{1+p}{2p}\right)^{-k} n \frac{a(1+p)}{p} \left(1+\frac{a}{p}\right)^{n-1} \\ & = n a \frac{1+p}{p} \left(1+\frac{1-p}{2p}\right)^{-k} \left(1+\frac{a}{p}\right)^{n-1} \\ & \le \frac{2n a}{p} \left(1+\frac{1-p}{2p}\right)^{-k} \left(1+\frac{a}{p}\right)^{n}. \end{aligned}$$

Since $(1+u)^{-1} \le e^{-u/2}$ (for $0 \le u \le 1$) and $1+v \le e^v$ (for $v \ge 0$), applied to $u := \frac{1-p}{2p} \le 1$ and $v := \frac{a}{p}$, we obtain, in case $\frac{1}{3} \le p < 1$,

$$\mathbf{P}\left\{\sum_{i=1}^{n} \xi_i \ge k\right\} \le 6na \exp\left(-\frac{(1-p)k}{4p} + \frac{na}{p}\right).$$
Second and last case: $0 < p \le \frac{1}{3}$. We choose $s := 2 < \frac{1}{p}$, so $\frac{(1-p)s}{1-ps} \le 4$; by (A.1), we obtain:

$$P\left\{\sum_{i=1}^{n} \xi_i \ge k\right\} \le 4na 2^{-k}(1+3a)^{n-1} \le 4na 2^{-k}(1+3a)^n.$$

In view of the inequality $1 + v \le e^v$ (for $v \ge 0$; applied to $v := 3a$), we obtain, in case $0 < p \le \frac{1}{3}$,

$$P\left\{\sum_{i=1}^{n} \xi_i \ge k\right\} \le 4na 2^{-k} e^{3an}.$$

So in both situations, as long as $1-p > \frac{8}{\epsilon}a$, we have, for $k := \lceil \epsilon n \rceil$, $-\frac{(1-p)k}{4p} + \frac{na}{p} \le -n(\frac{(1-p)\epsilon}{4p} - \frac{a}{p}) \le -\frac{(1-p)\epsilon n}{8p} \le -\frac{(1-p)\epsilon n}{8}$, and $2^{-k}e^{3an} \le e^{-n(\epsilon \log 2-3a)} \le e^{-n(\epsilon \log 2-\frac{3\epsilon}{8})}$, which is bounded by $e^{-\frac{\epsilon n}{8}}$ (because $\log 2 \ge \frac{1}{2}$), and a fortiori by $e^{-\frac{(1-p)\epsilon n}{8}}$. Lemma 3.4 is proved. $\square$

**Acknowledgements.** We are grateful to an anonymous referee for a careful reading of the original manuscript and for helpful comments.

## References

[1] Aïdékon, E.: Convergence in law of the minimum of a branching random walk. Ann. Probab. 41, (2013), 1362–1426. MR-3098680

[2] Aïdékon, E., Hu, Y. and Zindy, O.: The precise tail behavior of the total progeny of a killed branching random walk. Ann. Probab. 41, (2013), 3786–3878. MR-3161464

[3] Andreoletti, P. and Debs, P.: The number of generations entirely visited for recurrent random walks on random environment. J. Theoret. Probab. 27, (2014), 518–538. MR-3195824

[4] Andreoletti, P. and Debs, P.: Spread of visited sites of a random walk along the generations of a branching process. Electron. J. Probab. 19, (2014), 1–22. MR-3210543

[5] Bass, R.F. and Griffin, P.S.: The most visited site of Brownian motion and simple random walk. Z. Wahrscheinlichkeitstheorie verw. Gebiete 70, (1985), 417–436. MR-0803682

[6] Biggins, J.D.: Chernoff’s theorem in the branching random walk. J. Appl. Probab. 14, (1977), 630–636. MR-0464415

[7] Biggins, J.D.: Martingale convergence in the branching random walk. J. Appl. Probab. 14, (1977), 25–37. MR-0433619

[8] Biggins, J.D. and Kyprianou, A.E.: Measure change in multitype branching. Adv. Appl. Probab. 36, (2004), 544–581. MR-2058149

[9] Biggins, J.D. and Kyprianou, A.E.: Fixed points of the smoothing transform: the boundary case. Electron. J. Probab. 10, (2005), Paper no. 17, 609–631. MR-2147319

[10] Chen, X.: A necessary and sufficient condition for the non-trivial limit of the derivative martingale in a branching random walk. arXiv:1402.5864

[11] Erdős, P. and Révész, P.: On the favourite points of a random walk. Mathematical Structures – Computational Mathematics – Mathematical Modelling 2, (1984), p. 152–157. Sofia. MR-0790875

[12] Faraud, G.: A central limit theorem for random walk in a random environment on marked Galton-Watson trees. Electron. J. Probab. 16, (2011), 174–215. MR-2754802

[13] Faraud, G., Hu, Y. and Shi, Z.: Almost sure convergence for stochastically biased random walks on trees. Probab. Theory Related Fields 154, (2012), 621–660. MR-3000557

[14] Golosov, A.O.: Localization of random walks in one-dimensional random environments. Comm. Math. Phys. 92, (1984), 491–506. MR-0736407

[15] Hu, Y.: Local times of subdiffusive biased walks on trees. arXiv:1412.4507

[16] Hu, Y. and Shi, Z.: The problem of the most visited site in random environment. Probab. Theory Related Fields 116, (2000), 273–302. MR-1743773
[17] Hu, Y. and Shi, Z.: The potential energy of biased random walks on trees. arXiv:1403.6799

[18] Hu, Y. and Shi, Z.: The slow regime of randomly biased walks on trees. arXiv:1501.07700

[19] Kozlov, M.V.: The asymptotic behavior of the probability of non-extinction of critical branching processes in a random environment. *Theory Probab. Appl.* **21**, (1976), 791–804. MR-0428492

[20] Lyons, R.: A simple path to Biggins' martingale convergence for branching random walk. In: *Classical and Modern Branching Processes* (Eds.: K.B. Athreya and P. Jagers). *IMA Volumes in Mathematics and its Applications* **84**, (1997), 217–221. Springer, New York. MR-1601749

[21] Lyons, R. and Pemantle, R.: Random walk in a random environment and first-passage percolation on trees. *Ann. Probab.* **20**, (1992), 125–136. MR-1143414

[22] Menshikov, M.V. and Petritis, D.: On random walks in random environment on trees and their relationship with multiplicative chaos. In: *Mathematics and Computer Science II* (Versailles, 2002), (2002), pp. 415–422. Birkhäuser, Basel. MR-1940150

[23] Neveu, J.: Arbres et processus de Galton-Watson. *Annales Inst. Henri Poincaré Série B*, **22**, (1986), pp. 199–207. MR-0850756

[24] Révész, P.: *Random Walk in Random and Non-Random Environments*. (Third edition). (2013), World Scientific, Singapore. MR-3060348

[25] Shi, Z.: *Branching Random Walks*, École d'Été de Saint-Flour XLII (2012), in preparation.

[26] Sinai, Ya.G.: The limiting behavior of a one-dimensional random walk in a random medium. *Th. Probab. Appl.* **27**, (1982), 256–268. MR-0657919

[27] Tóth, B.: No more than three favourite sites for simple random walk. *Ann. Probab.* **29**, (2001), 484–503. MR-1825161