# Local limit theorems and renewal theory with no moments

Kenneth S. Alexander, Quentin Berger

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

## To cite this version:

Kenneth S. Alexander, Quentin Berger. Local limit theorems and renewal theory with no moments. Electronic Journal of Probability, 2016, 21 (66), 10.1214/16-EJP13. hal-01291344v2

HAL Id: hal-01291344

https://hal.science/hal-01291344v2

Submitted on 10 Nov 2016

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_2.png" /></figure>
# LOCAL LIMIT THEOREMS AND RENEWAL THEORY WITH NO MOMENTS

KENNETH S. ALEXANDER AND QUENTIN BERGER

**ABSTRACT.** We study i.i.d. sums $\tau_k$ of nonnegative variables with index 0: this means $\mathbf{P}(\tau_1 = n) = \varphi(n)n^{-1}$, with $\varphi(\cdot)$ slowly varying, so that $\mathbf{E}(\tau_1^\epsilon) = \infty$ for all $\epsilon > 0$. We prove a local limit and local (upward) large deviation theorem, giving the asymptotics of $\mathbf{P}(\tau_k = n)$ when $n$ is at least the typical length of $\tau_k$. A recent renewal theorem in [22] is an immediate consequence: $\mathbf{P}(n \in \tau) \sim \mathbf{P}(\tau_1 = n)/\mathbf{P}(\tau_1 > n)^2$ as $n \to \infty$. If instead we only assume regular variation of $\mathbf{P}(n \in \tau)$ and slow variation of $U_n := \sum_{k=0}^n \mathbf{P}(k \in \tau)$, we obtain a similar equivalence but with $\mathbf{P}(\tau_1 = n)$ replaced by its average over a short interval. We give an application to the local asymptotics of the distribution of the first intersection of two independent renewals. We further derive downward moderate and large deviations estimates, that is, the asymptotics of $\mathbf{P}(\tau_k \le n)$ when $n$ is much smaller than the typical length of $\tau_k$.

## 1. INTRODUCTION

It is classical to study renewal processes $\tau = \{0 = \tau_0, \tau_1, \tau_2, \dots\}$, and in particular the relation between the renewal mass function $\mathbf{P}(n \in \tau)$ and the inter-arrival distribution $\mathbf{P}(\tau_1 = n)$. We assume the inter-arrival distribution $\mathbf{P}(\tau_1 = n)$ is regularly varying: there exists a positive slowly varying function $\varphi(\cdot)$ and $\alpha \ge 0$ such that

$$ (1.1) \qquad \mathbf{P}(\tau_1 = n) = \varphi(n) n^{-(1+\alpha)}. $$

In particular the process is aperiodic. The case receiving the least attention (under the general assumption (1.1)) is $\alpha = 0$, in which $\tau_1$ has no moments and is not in the domain of attraction of a stable law, and that is our focus here. Tauberian theorems are of less use here than in other cases, so our methods are primarily probabilistic. An example with $\alpha = 0$ is the return times of symmetric simple random walk (SSRW) on $\mathbb{Z}^2$, $\tau = \{n, S_{2n} = 0\}$, for which $\mathbf{P}(\tau_1 = n) \xrightarrow{n \to \infty} \pi/n(\log n)^2$, from [19, Thm. 4].

The limiting distributions of $\tau_n$ and related quantities in the $\alpha = 0$ case have been studied in [8, 17, 20, 22, 24, 25, 26]. Defining $r(n) := \mathbf{P}(\tau_1 > n)$, Theorem 4.1 in [8] states that if $r(n)$ is slowly varying, then for any $y > 0$

$$ (1.2) \qquad \mathbf{P}(n r(\tau_n) < y) \to 1 - e^{-y} \quad \text{as } n \to +\infty. $$

Recently in [22], Nagaev proved a strong renewal theorem:

$$ (1.3) \qquad \mathbf{P}(n \in \tau) \xrightarrow{n \to \infty} \frac{\mathbf{P}(\tau_1 = n)}{\mathbf{P}(\tau_1 > n)^2}, $$

and for $\mathbf{P}(\tau_k > n)$, some “upward” large deviation results (meaning for $n$ much larger than the typical size of $\tau_k$) were proved in [24].
1.1. **Renewal theorems.** The assumption (1.1) is very natural: beyond the dimension-2 case, it includes the case $\tau = \{n, S_{2n} = 0\}$, where $(S_n)_{n \ge 0}$ is SSRW on $\mathbb{Z}^d$ for any $d$. One has $\alpha = 1/2$ and $\varphi(n) \xrightarrow{n \to \infty} (4\pi)^{-1/2}$ for $d=1$ (see e.g. [14, Ch. III]); and $\alpha = \frac{d}{2}-1$, $\varphi(n) \xrightarrow{n \to \infty} c_d$ for $d \ge 3$ (see [12, Thm. 4]). Equation (1.1) also includes the case $\tau = \{n, S_n = 0\}$ where $(S_n)_{n \ge 0}$ is an aperiodic random walk in the domain of attraction of a symmetric stable law, see [21, Thm. 8].

The asymptotics of the renewal function $\mathbf{P}(n \in \tau)$ under (1.1) have been widely studied in the literature, including [10], [13], [15], [22], [27]. We recall briefly the results.

First, when $\tau$ is transient and (1.1) holds, we have

$$ (1.4) \qquad \mathbf{P}(n \in \tau) \xrightarrow{n \to \infty} \frac{\mathbf{P}(\tau_1 = n)}{\mathbf{P}(\tau_1 = +\infty)^2}. $$

This is a consequence of Theorem 1 in [5], and is also proved in [16, App. A.5] with elementary methods.

If $\tau$ is recurrent, then

* if $\mathbf{E}[\tau_1] < +\infty$, then the classical Renewal Theorem (see e.g. [2]) gives that

$$ (1.5) \qquad \lim_{n \to \infty} \mathbf{P}(n \in \tau) = \frac{1}{\mathbf{E}[\tau_1]}; $$

* if $\alpha = 1$ in (1.1), and $\mathbf{E}[\tau_1] = +\infty$, Erickson [13, Eq. (2.4)] proved that

$$ (1.6) \qquad \mathbf{P}(n \in \tau) \xrightarrow{n \to \infty} \frac{1}{\mathbf{E}[\tau_1 \wedge n]}; $$

* if $\alpha \in (0, 1)$ in (1.1), Doney [10, Thm. B] proved that

$$ (1.7) \qquad \mathbf{P}(n \in \tau) \xrightarrow{n \to \infty} \frac{\alpha \sin(\pi\alpha)}{\pi} n^{-(1-\alpha)} \varphi(n)^{-1}; $$

* if $\alpha = 0$ in (1.1), then Nagaev [22] showed

$$ (1.8) \qquad \mathbf{P}(n \in \tau) \xrightarrow{n \to \infty} \frac{\mathbf{P}(\tau_1 = n)}{\mathbf{P}(\tau_1 > n)^2}. $$

The condition (1.1) is not best possible for the validity of these strong renewal theorems with infinite mean. Assume simply that $\mathbf{P}(\tau_1 > n) \xrightarrow{n \to \infty} \alpha^{-1}\varphi(n)n^{-\alpha}$ with $\alpha \in (0, 1]$ (and $\mathbf{E}[\tau_1] = +\infty$ if $\alpha = 1$), so that $\tau_1$ is in the domain of attraction of a stable law with index $\alpha$. Garsia and Lamperti [15] showed that (1.7) holds whenever $\alpha \in (\frac{1}{2}, 1)$, and Erickson proved (1.6) in the case $\alpha = 1$. When $\alpha \in (0, \frac{1}{2}]$, some additional conditions on the distribution of $\tau_1$ are necessary for (1.7) to be valid, and sufficient ones were given in [6], [7], [10], [27]. It is only recently that a complete necessary and sufficient condition for the strong renewal theorem (1.7) was proved in simultaneous papers by Caravenna [4] and Doney [11]. A necessary and sufficient condition remains to be found in the case $\alpha = 0$.

Throughout the paper, $c_1, c_2, \dots$ are constants depending only on the distribution of $\tau_1$. Also, we treat certain large quantities at times as if they were integers, to avoid the clutter of integer-part notation; in all cases these can be treated as if the integer-part notation were in use.
Our first result is a local limit and local (upward) large deviation theorem, proved in Section 2, in the case of a recurrent $\tau$. Define $r_n := r(n) := \mathbf{P}(\tau_1 > n)$, which in the $\alpha = 0$ case is slowly varying and satisfies (see [3, Proposition 1.5.9a])

$$ (1.9) \qquad \varphi(n) = o(r_n) \quad \text{as } n \to \infty. $$

In particular we have $\varphi(n) \to 0$.

In [24], it is proved that $\mathbf{P}(\tau_k > n) \sim kr_n$ as $n, k \to \infty$ with $kr_n \to 0$. We improve here this result by establishing a local limit theorem, and extending the range of validity to $k\varphi(n) \to 0$. This extension is significant because $kr_n \to 0$ allows only values of $n$ much larger than the typical value of $\tau_k$; see the remarks following the theorem.

**Theorem 1.1.** If $\tau$ is recurrent and (1.1) holds with $\alpha = 0$, then uniformly for $k$ such that $k\varphi(n) \to 0$, we have

$$ (1.10) \qquad \mathbf{P}(\tau_k = n) \xrightarrow{n \to \infty} k\mathbf{P}(\tau_1 = n)(1 - r_n)^k. $$

Further, there exists a constant $c_1 > 0$ such that for $n$ sufficiently large and all $1 \le k \le n$,

$$ (1.11) \qquad \mathbf{P}(\tau_k = n) \le c_1 k \mathbf{P}(\tau_1 = n)(1 - r_n)^k. $$

Note that, as soon as $k \gg r_n^{-1}$, we have $\mathbf{P}(\tau_k \le n) \le (1 - r_n)^k \to 0$, and $n$ is therefore much smaller than the typical size of $\tau_k$. By (1.9), $k \gg r_n^{-1}$ is consistent with the hypothesis $k \ll 1/\varphi(n)$. Equation (1.10) therefore includes $n$ down to a size much smaller than the typical size of $\tau_k$. Heuristically, (1.10) says that even for much smaller-than-usual $n$, when $\tau_k = n$ it is because there was a single gap of length very close to $n$, among the first $k$ gaps $\tau_j - \tau_{j-1}$; this is unique to $\alpha = 0$.

In comparison, in the case where (1.1) holds with $\alpha \in (0, 1)$, Doney [10, Thm. A] proved that $\mathbf{P}(\tau_k = n) \sim k\mathbf{P}(\tau_1 = n)$ provided that $kr_n \to 0$, and Denisov, Dieker and Shneer [9, Section 9] proved a similar, more general, local large deviation theorem that applies in the $\alpha > 0$ case. If we consider the case $kr_n \to x \in (0, +\infty)$, we have that $n/a_k \to x^{-1/\alpha}$, where $a_k$ is such that $\mathbf{P}(\tau_1 > a_k) \sim k^{-1}$ (so that $\tau_k/a_k$ converges to an $\alpha$-stable distribution with non-degenerate density $g$). Then, Gnedenko's local limit theorem (see [18, § 50]) gives that $\mathbf{P}(\tau_k = n) \sim \alpha^{-1}x^{-(1+1/\alpha)}g(x^{-1/\alpha})k\mathbf{P}(\tau_1 = n)$, in contrast with (1.10) when $\alpha = 0$.

The strong renewal theorem (1.3) from [22] is an easy consequence of Theorem 1.1, as follows. Assume (1.1) with $\alpha = 0$ and let $\theta_n$ satisfy $r_n^{-1} \ll \theta_n \ll \varphi(n)^{-1}$. We write $\mathbf{P}(n \in \tau) = \sum_{k=1}^n \mathbf{P}(\tau_k = n)$, and decompose it according to whether $k$ is smaller or larger than $\theta_n$. Thanks to (1.10), by our choice of $\theta_n$ we have

$$ \sum_{k \le \theta_n} \mathbf{P}(\tau_k = n) \xrightarrow{n \to \infty} \sum_{k \le \theta_n} k \mathbf{P}(\tau_1 = n)(1 - r_n)^k \xrightarrow{n \to \infty} r_n^{-2} \mathbf{P}(\tau_1 = n). $$

For the rest of the sum, we use (1.11) together with $\theta_n \gg r_n^{-1}$, to get that, for $n \ge n_0$

$$ \sum_{k > \theta_n} \mathbf{P}(\tau_k = n) \le c_1 \sum_{k > \theta_n} k \mathbf{P}(\tau_1 = n)(1 - r_n)^k = o(1) r_n^{-2} \mathbf{P}(\tau_1 = n) \quad \text{as } n \to +\infty. $$

These two estimates give (1.3). Combining with (1.4), we obtain the following statement: if (1.1) holds with $\alpha \ge 0$, and $\mathbf{P}(\tau_1 > n)$ is slowly varying (that is, either $\tau$ is transient, or $\tau$ is recurrent with $\alpha = 0$), then (1.3) holds.

The heuristic behind (1.3) may be seen by restating it as $\mathbf{P}(\tau_1 = n | n \in \tau) \sim \mathbf{P}(\tau_1 > n)^2$. This says that given $n \in \tau$, in order to have $\tau_1 = n$ (i.e. no renewals between 0 and $n$), the
trajectory mainly needs to “escape” without renewals at each end, and these two escapes are approximately independent, each with probability near $P(\tau_1 > n)$. This independence in the recurrent case is unique to $\alpha = 0$, since in that case the only renewals that typically occur given $n \in \tau$ are very close to 0 and $n$.

**1.2. Large and moderate downward deviations.** Theorem 1.1 may be viewed as both a local limit theorem and a local large deviation theorem for the case $\alpha = 0$, covering upward deviations (in the sense that $n$ is much larger than the typical size of $\tau_k$) and downward deviations that are not too great. As a complement we now consider estimates for downward deviations of the form $P(\tau_k \le n)$ for $n$ much smaller than the typical size of $\tau_k$, that is $kr_n \to \infty$.

Let $\varphi^*$ denote a slowly varying function conjugate to $\varphi$, that is, such that $x \mapsto x\varphi^*(x)$ is an asymptotic inverse of $y \mapsto y\varphi(y)$, see [3, §1.5.7] for more. For most common slowly varying functions $\varphi$ one has $\varphi^* \sim 1/\varphi$, but this is not true if $\varphi$ is “barely slowly varying,” for example $\varphi(n) = n^{1/\log \log n}$. We will prove the following in Section 1.2.

**Theorem 1.2.** Suppose $\tau$ is recurrent and (1.1) holds with $\alpha = 0$. Let $n \ge k$.

(i) Given $M > 0$ there exists $a_M$, with $a_M \to 1$ as $M \to 0$, such that if $n$ is large and $k\varphi(n) \le M$, then

$$ (1.12) \qquad a_M(1-r_n)^k \le \mathbf{P}(\tau_k \le n) \le (1-r_n)^k. $$

(ii) If $k, n \to +\infty$ with $k\varphi(n) \to +\infty$ and $n/k \to +\infty$, then we have

$$ (1.13) \qquad \mathbf{P}(\tau_k \le n) = \exp \left\{ -(1+o(1)) k r \left( \frac{n}{k} \varphi^* \left( \frac{n}{k} \right) \right) \right\}. $$

(iii) For $n = bk$ with $b \ge 1$, the limit $-I(b) = \lim_{n \to \infty} \frac{1}{n} \log \mathbf{P}(\tau_k \le bk)$ exists, and it is finite if $b \ge \min\{j : \mathbf{P}(\tau_1 = j) > 0\}$. Moreover, it satisfies

$$ I(b) \sim r(b\varphi^*(b)) \quad \text{as } b \to +\infty. $$

This theorem extends the result (1.2) of Darling [8] to the case $y \to +\infty$ as $n \to +\infty$. In particular, (i) allows to recover (1.2) by taking $k = y/r_n$ (since $\{\tau_k \le n\} = \{r(\tau_k) \ge y/k\}$), and moreover extends it to $\mathbf{P}(kr(\tau_k) \ge y) \sim e^{-y}$ as $k \to \infty$, uniformly for $y \ll r_n/\varphi(n)$ (we recall (1.9)).

**1.3. Reverse renewal theorems.** Though (1.1) is very natural, verifying that it holds is often difficult, for example if $\tau = \{n, S_n = 0\}$, with $(S_n)_{n \ge 0}$ an aperiodic random walk in the domain of attraction of a symmetric stable distribution, see [19]. But in that case, a local limit theorem (see [18, § 50]) easily gives the asymptotic behavior of $\mathbf{P}(S_n = 0) = \mathbf{P}(n \in \tau)$. Therefore, one would like to get a general result to infer from $\mathbf{P}(n \in \tau)$ something about the behavior of $\mathbf{P}(\tau_1 = n)$. We call such a result a *reverse renewal theorem*. An additional application of such theorems is given in Section 1.4.

In general, it is not true that regular variation of $\mathbf{P}(n \in \tau)$ implies regular variation of $\mathbf{P}(\tau_1 = n)$, an example being given in Section 4.3. But the average of the values $\mathbf{P}(\tau_1 = n)$ over a relatively short interval may be better behaved. In fact we can obtain a reverse renewal theorem corresponding to (1.3) and (1.4) in the $\alpha = 0$ case, as follows.
Define

$$U_n := \sum_{k=0}^{n} \mathbf{P}(k \in \tau), \quad U_{\infty} := \mathbf{E}[|\tau|] = \sum_{k=0}^{\infty} \mathbf{P}(k \in \tau) \quad \left( = \frac{1}{\mathbf{P}(\tau_1 = \infty)} \text{ if } U_{\infty} < \infty \right),$$

and note that

$$(1.14) \qquad \text{if } U_n \text{ is slowly varying, then } U_n \xrightarrow{n \to \infty} \mathbf{P}(\tau_1 > n)^{-1}.$$

This is trivial if $\tau$ is transient: $|\tau|$ is then a geometric random variable, and $U_n$ converges to $\mathbf{E}[|\tau|] = \mathbf{P}(\tau_1 = +\infty)^{-1}$. In the recurrent case, we refer to Theorem 8.7.3 in [3]; the proof uses standard properties of convolution of Laplace transforms. Note that in the following we do not assume (1.1).

**Theorem 1.3.** Assume that $\mathbf{P}(n \in \tau)$ is regularly varying and $U_n$ is slowly varying. Then there exist $\epsilon_n \to 0$ such that

$$(1.15) \qquad \frac{1}{\epsilon_n n} \sum_{(1-\epsilon_n)n < k \le n} \mathbf{P}(\tau_1 = k) \xrightarrow{n \to \infty} \mathbf{P}(\tau_1 > n)^2 \mathbf{P}(n \in \tau).$$

If also $\mathbf{P}(\tau_1 = n)$ is regularly varying, then

$$(1.16) \qquad \mathbf{P}(\tau_1 = n) \xrightarrow{n \to \infty} \mathbf{P}(\tau_1 > n)^2 \mathbf{P}(n \in \tau).$$

This theorem applies in the recurrent case when $\mathbf{P}(n \in \tau)$ is regularly varying with index $-1$, and in the case of a transient renewal $\tau$. When $\tau$ is transient, we are able to prove the following stronger statement.

**Theorem 1.4.** If $\mathbf{P}(n \in \tau)$ is regularly varying and $\tau$ is transient, then

$$\mathbf{P}(\tau_1 = n) \xrightarrow{n \to \infty} \mathbf{P}(\tau_1 = \infty)^2 \mathbf{P}(n \in \tau).$$

This theorem was proved in [12] in the case where $\tau_1, \tau_2, \dots$ are the return times to the origin of a transient aperiodic random walk, and can be proved via Banach Algebra techniques, using [5, Theorem 1] as suggested in [12, Section 2]. However, we give here an elementary probabilistic proof.

Section 4.1 is devoted to the proof of Theorem 1.4, and Section 4.2 to the proof of Theorem 1.3. Finally, in Section 4.3, we give an example where $\mathbf{P}(\tau_1 = n)$ is not regularly varying but $\mathbf{P}(n \in \tau)$ is, and $U_n$ is slowly varying. This shows that (1.16) cannot hold in the general case of a recurrent renewal, and our Theorem 1.3 is in that sense optimal.

In general, Theorem 1.3 reduces the problem of proving (1.16) to showing that $\mathbf{P}(\tau_1 = k)$ is approximately constant over the interval $((1 - \epsilon_n)n, n]$.

**1.4. Application of reverse renewal theorems: the intersection of two independent renewals.** Let $\tau$ and $\sigma$ be independent renewal processes with inter-arrival distributions satisfying

$$(1.17) \qquad \mathbf{P}(\tau_1 = n) = \varphi(n)n^{-(1+\alpha)}, \quad \mathbf{P}(\sigma_1 = n) = \tilde{\varphi}(n)n^{-(1+\tilde{\alpha})}$$

for some $\alpha, \tilde{\alpha} \ge 0$ and slowly varying functions $\varphi(\cdot), \tilde{\varphi}(\cdot)$. We assume $\alpha \le \tilde{\alpha}$.
We denote the intersection $\rho := \tau \cap \sigma$, which is a renewal process with renewal mass function and renewal function

$$ \mathbf{P}(n \in \rho) = \mathbf{P}(n \in \tau)\mathbf{P}(n \in \sigma), \quad U_n^* = \sum_{k=0}^{n} \mathbf{P}(k \in \rho). $$

These are regularly varying, and their asymptotic behavior is thus known from the results for $\sigma, \tau$ in Section 1.1. In [1] our reverse renewal theorems, 1.3 and 1.4, are applied to help establish the following. If $\rho$ is transient (i.e. $U_\infty^* < \infty$) then

$$ \mathbf{P}(\rho_1 = n) \stackrel{n \to \infty}{\sim} (U_\infty^*)^{-2} \mathbf{P}(n \in \tau) \mathbf{P}(n \in \sigma). $$

If $\rho$ is recurrent and either (i) $\alpha, \tilde{\alpha} \in (0, 1)$ with $\alpha + \tilde{\alpha} = 1$, or (ii) $\alpha = 0, \tilde{\alpha} \ge 1$, then $U_n^*$ is slowly varying, and

$$ (1.18) \qquad \mathbf{P}(\rho_1 = n) \stackrel{n \to \infty}{\sim} (U_n^*)^{-2} \mathbf{P}(n \in \tau) \mathbf{P}(n \in \sigma) \stackrel{n \to \infty}{\sim} \frac{\psi^*(n)}{n} $$

for some (asymptotically known) slowly varying $\psi^*$. In [1], general $0 \le \alpha \le \tilde{\alpha}$ are covered, and Theorems 1.3 and 1.4 here are essential for the cases (i) and (ii). The key step to get from (1.15) for $\rho$ to (1.18) is to show that, due to the regularity (1.17) in $\sigma$ and $\tau$, $\mathbf{P}(\rho_1 = k)$ is approximately constant over short intervals, so that the left side of (1.15) (for $\rho$) is asymptotic to $\mathbf{P}(\rho_1 = n)$.

## 2. PROOF OF THEOREM 1.1

We first prove (1.10), and turn to (1.11) as a second step. We introduce some notations: let

$$ G_i := \tau_i - \tau_{i-1} \quad \text{and} \quad M_k := \max_{1 \le i \le k} G_i. $$

We also let $\hat{G}_1^{(m)}, \dots, \hat{G}_k^{(m)}$ be i.i.d. with distribution $\mathbf{P}(\tau_1 \in \cdot | \tau_1 \le m)$.

### 2.1. Proof of the local limit and local large deviation result (1.10).
The proof is divided into three steps, in which we control several contributions to $\mathbf{P}(\tau_k = n)$.

* Step 1. Contribution of the case of only one jump larger than $(1 - \epsilon)n$, all the other ones being (necessarily) smaller than $n/2$. This gives the right order in Theorem 1.1 when $k \ll \varphi(n)^{-1}$;

* Step 2. Contribution of the case when all jumps are smaller than $n/2$: it is negligible, so there must be one jump larger than $n/2$ (and there can be only one such jump);

* Step 3. Contribution of the case when there is one jump larger than $n/2$, but smaller than $(1 - \epsilon)n$. This is also negligible.

**Step 1:** We show that, for any fixed $\epsilon > 0$, and provided that $k\varphi(n) \stackrel{n \to \infty}{\to} 0$,

$$ (2.1) \qquad \mathbf{P}(\tau_k = n, M_k > (1 - \epsilon)n) = (1 + O(\epsilon)) k \mathbf{P}(\tau_1 = n)(1 - r_n)^k, \quad \text{as } n \to \infty. $$

We have

$$ (2.2) \qquad \mathbf{P}(\tau_k = n, M_k > (1 - \epsilon)n) = k(1 - r_n)^{k-1} \sum_{m=1}^{\epsilon n} \mathbf{P}\left(\sum_{i=1}^{k-1} \hat{G}_i^{(n)} = m\right) \mathbf{P}(\tau_1 = n - m). $$
This gives the upper bound

$$ (2.3) \qquad \begin{aligned} \mathbf{P}(\tau_k = n, M_k > (1-\epsilon)n) &\le k(1-r_n)^{k-1} \max_{(1-\epsilon)n \le j \le n} \mathbf{P}(\tau_1 = j) \\ &\le (1+2\epsilon)k(1-r_n)^k \mathbf{P}(\tau_1 = n), \end{aligned} $$

provided that $n$ is large enough.

In the other direction, (2.2) gives

$$ \mathbf{P}(\tau_k = n, M_k > (1-\epsilon)n) \ge k(1-r_n)^{k-1} \mathbf{P}\left(\sum_{i=1}^{k-1} \hat{G}_i^{(n)} \le \epsilon n\right) \min_{(1-\epsilon)n \le j \le n} \mathbf{P}(\tau_1 = j). $$

Then, using that $\mathbf{E}[\hat{G}_1^{(n)}] = (1-r_n)^{-1} \sum_{x=1}^n \varphi(x) \xrightarrow{n \to \infty} n\varphi(n)$, we have that for $n$ large enough

$$ \mathbf{P}\left(\sum_{i=1}^{k-1} \hat{G}_i^{(n)} \le \epsilon n\right) \ge 1 - \frac{\mathbf{E}[\hat{G}_1^{(n)}]}{\epsilon n} \ge 1 - \frac{2(k-1)\varphi(n)}{\epsilon}. $$

Therefore, since $k\varphi(n) \to 0$, we end up with

$$ (2.4) \qquad \mathbf{P}(\tau_k = n, M_k > (1-\epsilon)n) \ge (1-2\epsilon)k(1-r_n)^k \mathbf{P}(\tau_1 = n). $$

provided that $n$ is large enough.

**Step 2:** We want to show that the main contribution to $\mathbf{P}(\tau_k = n)$ comes when $M_k \ge n/2$. We prove that there exists a constant $c_2 > 0$ such that, if $k\varphi(n)$ is small enough,

$$ (2.5) \qquad \mathbf{P}(\tau_k = n, M_k \le n/2) \le c_2 k^2 \varphi(n) \mathbf{P}(\tau_1 = n)(1-r_n)^k, $$

which is negligible compared to (2.1) when $k\varphi(n) \to 0$. It is sufficient to show that, if $k\varphi(n)$ is small enough,

$$ (2.6) \qquad \mathbf{P}\left(\sum_{i=1}^{k} \hat{G}_i^{(n)} = n; \hat{G}_i^{(n)} \le n/2 \text{ for all } i \le k\right) \le c_2 k^2 \varphi(n) \mathbf{P}(\tau_1 = n) $$

To prove this, we rely on the following lemma, which is a special case of the Fuk-Nagaev inequality, see [23, Theorem 1.1]. We include a proof here since it is short and elementary for our case.

**Lemma 2.1.** Suppose (1.1) holds with $\alpha = 0$. There exist constants $c_3, c_4 > 0$ such that for $n$ large, for all $1 \le m \le n$ and $k \ge 0$,

$$ (2.7) \qquad \mathbf{P}\left(\sum_{i=1}^{k} \hat{G}_i^{(m)} \ge n/2\right) \le \left(\frac{c_3 \, \mathrm{km}\varphi(m)}{n}\right)^{\frac{n}{2m}} \le \left(c_4 k \varphi(n)\right)^{\frac{n}{2m}}. $$

**Proof** The second inequality is a consequence of the fact that $m\varphi(m)$ is asymptotically increasing, so we prove the first inequality.

For any $\lambda > 0$ we have

$$ (2.8) \qquad \mathbf{P}\left(\sum_{i=1}^{k} \hat{G}_i^{(m)} \ge n/2\right) \le e^{-\lambda n/2} \mathbf{E}\left[e^{\lambda \hat{G}_1^{(m)}}\right]^k. $$
There exists a constant $c_5$ such that for any $j \ge 1$

$$ (2.9) \qquad \mathbf{E} \left[ \left( \hat{G}_1^{(m)} \right)^j \right] \le m^{j-1} \mathbf{E}[\tau_1 | \tau_1 \le m] \le c_5 m^j \varphi(m). $$

Hence

$$ \mathbf{E} \left[ e^{\lambda \hat{G}_1^{(m)}} \right] \le 1 + c_5 \varphi(m) (e^{m\lambda} - 1). $$

Now, let us define $\lambda$ by

$$ c_5 \varphi(m) (e^{m\lambda} - 1) = \frac{n}{km}, $$

so that

$$ \mathbf{E} \left[ e^{\lambda \hat{G}_1^{(m)}} \right]^k \le e^{n/m} $$

and

$$ e^{-\lambda n/2} = \left( 1 + \frac{n}{c_5 m k \varphi(m)} \right)^{-n/2m} \le \left( \frac{c_5 k m \varphi(m)}{n} \right)^{n/2m}. $$

Therefore, (2.8) yields

$$ (2.10) \qquad \mathbf{P} \left( \sum_{i=1}^{k} \hat{G}_i^{(m)} \ge n/2 \right) \le \left( \frac{c_5 k m \varphi(m)}{n} \right)^{n/2m} e^{n/m} \le \left( \frac{c_5 e^2 k m \varphi(m)}{n} \right)^{n/2m}. $$

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

To control the probability on the left in (2.6), we decompose it according to the value of the largest $\hat{G}_i^{(n)}$. Let us denote $m_s := 2^{-s}n$ and $J_s = (m_{s+1}, m_s]$. We have

$$ \begin{align} \mathbf{P} \left( \sum_{i=1}^{k} \hat{G}_i^{(n)} = n; \hat{G}_i^{(n)} \le n/2 \text{ for all } i \le k \right) & \nonumber \\ & = \sum_{n/k \le m \le n/2} k \mathbf{P} \left( \hat{G}_1^{(n)} = m, \hat{G}_i^{(n)} \le m \text{ for all } 2 \le i \le k, \sum_{i=2}^{k} \hat{G}_i^{(n)} = n - m \right) \nonumber \\ & \le \sum_{1 \le s \le \log_2 k} \sum_{m \in J_s} k \left( \frac{1 - r_m}{1 - r_n} \right)^{k-1} \mathbf{P} \left( \hat{G}_1^{(n)} = m \right) \mathbf{P} \left( \sum_{i=2}^{k} \hat{G}_i^{(m)} = n - m \right) \nonumber \\ & \le 2k \sum_{1 \le s \le \log_2 k} \sum_{m \in J_s} \frac{\varphi(m)}{m} \mathbf{P} \left( \sum_{i=1}^{k-1} \hat{G}_i^{(m)} = n - m \right) \nonumber \\ (2.11) \qquad & \le 2c_6k \sum_{1 \le s \le \log_2 k} \frac{\varphi(m_{s+1})}{m_{s+1}} \mathbf{P} \left( \sum_{i=1}^{k-1} \hat{G}_i^{(m_s)} \ge \frac{n}{2} \right), \end{align} $$

where in the last inequality we used that there exists $c_6$ such that for sufficiently large $m_s$ and all $m \in J_s$, $\varphi(m) \le c_6 \varphi(m_{s+1})$. Since $n/k \gg n\varphi(n) \to \infty$, all values $m_s$ in (2.11) are sufficiently large in this sense, when $n$ is large.
Since $\varphi$ is slowly varying, given $a \le 1$ we have $\varphi(an)/\varphi(n) \le 1/a$ for $n$ large. With (2.11) and Lemma 2.1 this shows that

$$ (2.12) \qquad \begin{aligned} \mathbf{P} \left( \sum_{i=1}^{k} \hat{G}_i^{(n)} = n; \hat{G}_i^{(n)} \le n/2 \text{ for all } i \le k \right) &\le 2c_6k \sum_{s \ge 1} \frac{2^{s+1}\varphi(n)}{2^{-(s+1)n}} (c_4 k\varphi(n))^{\frac{n}{2ms}} \\ &\le 8c_6k \frac{\varphi(n)}{n} \sum_{s \ge 1} 4^s (c_4 k\varphi(n))^{2s-1} \\ &\le c_2 k^2 \varphi(n) \mathbf{P}(\tau_1 = n), \end{aligned} $$

where we used in the last inequality that $k\varphi(n)$ is small. Hence, (2.6) is proved, and so is (2.5).

**Step 3:** We show that the main contribution to $\mathbf{P}(\tau_k = n)$ comes when not only $M_k \ge n/2$, but when $M_k \ge (1 - \epsilon)n$: we prove that for $n$ large enough,

$$ (2.13) \qquad \mathbf{P} \left( \tau_k = n, n/2 < M_k \le (1-\epsilon)n \right) \le \frac{6}{\epsilon} k^2 \varphi(n) \mathbf{P}(\tau_1 = n) (1-r_n)^k. $$

Indeed, we have that

$$ \mathbf{P} \left( \tau_k = n, n/2 < M_k \le (1-\epsilon)n \right) \le k (1-r_n)^{k-1} \max_{n/2 \le j \le n} \mathbf{P}(\tau_1 = j) \mathbf{P} \left( \sum_{i=1}^{k-1} \hat{G}_i^{(n)} \ge \epsilon n \right). $$

Then, we use that $\max_{n/2 \le j \le n} \mathbf{P}(\tau_1 = j) \le 3\mathbf{P}(\tau_1 = n)$ provided that $n$ is large enough, together with Markov's inequality and the fact that $\mathbf{E}[\hat{G}_1^{(n)}] \le 2n\varphi(n)$ when $n$ is large enough. This yields (2.13).

Combining (2.3)-(2.4) with (2.5) and (2.13), since $\epsilon$ is arbitrary we get that, uniformly for $k$ such that $k\varphi(n) \to 0$, (1.10) holds. $\square$

**2.2. Proof of the uniform bound (1.11).** To prove the uniform bound, we rely on Lemma 2.1, and we decompose the probability according to the value of $M_k$.

Let $n \ge n_0$ and define

$$ \ell_n = \min\{\ell : 2^\ell \ge n\}, \quad \ell_{n,k} := \max\{\ell : c_3 k 2^\ell \varphi(2^\ell) \le \frac{1}{2}n\}, $$

where $c_3$ is the constant from Lemma 2.1.

Then for some (large) $\ell_0$, there exists a constant $c_7 > 0$ such that for all $\ell_0 < \ell \le \ell_n - 2$,

$$ (2.14) \qquad \begin{aligned} \mathbf{P} \left( \tau_k = n, M_k \in (2^{\ell-1}, 2^\ell] \right) &\le k \mathbf{P} \left( G_1 \in (2^{\ell-1}, 2^\ell], \max_{2 \le i \le k} G_i \le 2^\ell, \tau_k = n \right) \\ &\le k (1 - r_{2^\ell})^{k-1} \max_{m \in (2^{\ell-1}, 2^\ell]} \mathbf{P} (\tau_1 = m) \mathbf{P} \left( \sum_{i=1}^{k-1} \hat{G}_i^{(2^\ell)} \in (n - 2^\ell, n] \right) \\ &\le c_7 k (1 - r_{2^\ell})^{k-1} \frac{\varphi(2^\ell)}{2^\ell} \mathbf{P} \left( \sum_{i=1}^{k-1} \hat{G}_i^{(2^\ell)} > \frac{n}{2} \right). \end{aligned} $$

We now have 4 cases according to the value of $\ell$.
**Case 1.** For $\ell_0 \lor \ell_{n,k} < \ell \le \ell_n - 2$ we bound the last probability in (2.14) by 1, and observe that provided $\ell_0$ is large enough, $r_{2^\ell} - r_n \ge \frac{1}{2}\varphi(2^\ell)$, which leads to

$$ (2.15) \qquad \begin{aligned} \mathbf{P}(\tau_k = n, 2^{\ell_0 \lor \ell_{n,k}} < M_k \le 2^{\ell_{n-2}}) &\le 2c_7 k(1-r_n)^k \sum_{\ell=\ell_0 \lor \ell_{n,k}+1}^{\ell_{n-2}} \frac{\varphi(2^\ell)}{2^\ell} \left(1 - \frac{r_{2^\ell} - r_n}{1-r_n}\right)^k \\ &\le 2c_7 k(1-r_n)^k \sum_{\ell=\ell_0 \lor \ell_{n,k}+1}^{\ell_{n-2}} \frac{\varphi(2^\ell)}{2^\ell} e^{-k\varphi(2^\ell)/4} \\ &\le 2c_7 k(1-r_n)^k \frac{\varphi(n)}{n} \sum_{\ell=1}^{\ell_{n-2}} \frac{n}{2^\ell} \frac{\varphi(2^\ell)}{\varphi(n)} e^{-n/8c_3 2^\ell}, \end{aligned} $$

where we used that $2^\ell \varphi(2^\ell)$ is asymptotically increasing in $\ell$. We obtain easily that the last sum remains bounded as $n \to \infty$. In the end, we have a constant $c_8 > 0$ such that for $n \ge n_0$

$$ (2.16) \qquad \mathbf{P}(\tau_k = n, 2^{\ell_0 \lor \ell_{n,k}} < M_k \le 2^{\ell_{n-2}}) \le c_8 k(1-r_n)^k \mathbf{P}(\tau_1 = n). $$

**Case 2.** To handle $\ell = \ell_n - 1, \ell_n$ we have analogously to (2.14), for $n \ge n_0$

$$ (2.17) \qquad \begin{aligned} \mathbf{P}(\tau_k = n, M_k > 2^{\ell_{n-2}}) &\le k(1-r_n)^{k-1} \max_{m \in (2^{\ell_{n-2}}, 2^{\ell_n}]} \mathbf{P}(\tau_1 = m) \\ &\le c_9 k(1-r_n)^k \mathbf{P}(\tau_1 = n). \end{aligned} $$

**Case 3.** We now deal with $\ell_0 < \ell \le \ell_{n,k}$. We bound the last probability in (2.14) using Lemma 2.1. We obtain, analogously to (2.15)

$$ (2.18) \qquad \begin{aligned} \mathbf{P}(\tau_k = n, 2^{\ell_0} < M_k \le 2^{\ell_{n,k}}) &\le 2c_7 k \sum_{\ell=\ell_0+1}^{\ell_{n,k} \land \ell_n} (1-r_{2^\ell})^k \frac{\varphi(2^\ell)}{2^\ell} \left(\frac{c_3 k 2^\ell \varphi(2^\ell)}{n}\right)^{n/2^{\ell+1}} \\ &\le 2c_7 k(1-r_n)^k \sum_{\ell=\ell_0+1}^{\ell_n} \frac{\varphi(2^\ell)}{2^\ell} \left(\frac{1}{2}\right)^{n/2^{\ell+1}} \\ &\le c_{10} k(1-r_n)^k \frac{\varphi(2^{\ell_{n+1}})}{2^{\ell_{n+1}}} \left(\frac{1}{2}\right)^{n/2^{\ell_{n+1}}} \\ &\le c_{11} k(1-r_n)^k \frac{\varphi(n)}{n} \\ &\le c_{11} k(1-r_n)^k \mathbf{P}(\tau_1 = n). \end{aligned} $$

Here the third inequality uses the fact that $n/2^{\ell_{n+1}} \ge 1/4$, and consequently the sum in the second line of (2.18) is of the same order as the $\ell = \ell_n$ term.
**Case 4.** Finally to handle $\ell \le \ell_0$ we have, using Lemma 2.1 and writing $m_0 := 2^{\ell_0}$

$$ (2.19) \qquad \begin{aligned} \mathbf{P}(\tau_k = n, M_k \le 2^{\ell_0}) &\le (1 - r_{m_0})^k \mathbf{P}\left(\sum_{i=1}^k \hat{G}_i^{(m_0)} = n\right) \\ &\le (1 - r_n)^k \left(\frac{1 - r_{m_0}}{1 - r_n}\right)^k \left(\min\left\{\frac{c_3 m_0 \varphi(m_0) k}{n}, 1\right\}\right)^{n/m_0} \\ &\le (1 - r_n)^k e^{-c_{12}k} \left(\min\left\{\frac{c_{13}k}{n}, 1\right\}\right)^{n/m_0}. \end{aligned} $$

Considering separately the cases $k \le n/2c_{13}$ and $n/2c_{13} < k \le n$, we conclude that there is some $c_{14} > 0$ such that for $n$ large,

$$ (2.20) \qquad \mathbf{P}(\tau_k = n, M_k \le 2^{\ell_0}) \le (1 - r_n)^k e^{-c_{14}n} \le c_{15}k(1 - r_n)^k \mathbf{P}(\tau_1 = n). $$

Collecting (2.16),(2.17),(2.18) and (2.20) concludes the proof of (1.11). $\square$

### 3. LARGE DEVIATIONS: PROOF OF THEOREM 1.2

Recall that $G_i = \tau_i - \tau_{i-1}$, and $\hat{G}_1^{(m)}$, $\hat{G}_2^{(m)}$, $\dots$ are i.i.d. with distribution $\mathbf{P}(\tau_1 \in \cdot | \tau_1 \le m)$.

**Proof of (i).** The second inequality is trivial, so we prove the first. Suppose $k\varphi(n) \le M$. Given $0 < \epsilon < 1$,

$$ r_{\epsilon n} - r_n \sim \varphi(n) \log \frac{1}{\epsilon} \quad \text{as } n \to +\infty, $$

so for large $n$,

$$ (3.1) \qquad \mathbf{P}\left(\max_{i \le k} \hat{G}_i^{(n)} \le \epsilon n\right) = \left(1 - \frac{r_{\epsilon n} - r_n}{1 - r_n}\right)^k \ge \exp\left(-2k\varphi(n) \log \frac{1}{\epsilon}\right) \ge \epsilon^{2M}. $$

On the other hand, since $\mathbb{E}[\hat{G}_1^{(m)}] \xrightarrow{m \to \infty} m\varphi(m)$, given $\epsilon > 0$ we have for $n$ large enough

$$ (3.2) \qquad \mathbf{P}\left(\sum_{i=1}^k \hat{G}_i^{(\epsilon n)} \le n\right) \ge 1 - \frac{1}{n} k \mathbb{E}\left(\hat{G}_1^{(\epsilon n)}\right) \ge 1 - 2\epsilon k \varphi(n) \ge 1 - 2\epsilon M. $$

If $M \le 1/3$, we apply (3.2) with $\epsilon = 1$:

$$ (3.3) \qquad \mathbf{P}(\tau_k \le n) \ge (1 - r_n)^k \mathbf{P}\left(\sum_{i=1}^n \hat{G}_i^{(n)} \le n\right) \ge (1 - r_n)^k (1 - 2M). $$

If $M > 1/3$, we take $\epsilon = 1/4M$, and combining (3.1) with (3.2), we obtain for $n$ large enough

$$ \mathbf{P}(\tau_k \le n) \ge (1 - r_n)^k \mathbf{P}\left(\max_{i \le k} \hat{G}_i^{(n)} \le \epsilon n\right) \mathbf{P}\left(\sum_{i=1}^k \hat{G}_i^{(\epsilon n)} \le n\right) \ge \frac{1}{2} \left(\frac{1}{4M}\right)^{2M} (1 - r_n)^k. $$

**Proof of (ii).** Define, for any $\lambda > 0$,

$$ \nu(\lambda) := 1 - \mathbb{E}(e^{-\lambda \tau_1}), $$
so $-\log(1 - \nu(\cdot))$ is non-decreasing and strictly concave. Moreover, it is standard to obtain that

$$ (3.4) \qquad \nu(\lambda) \sim r\left(\frac{1}{\lambda}\right) \to 0, \quad \text{and} \quad \nu'(\lambda) \sim \frac{1}{\lambda}\varphi\left(\frac{1}{\lambda}\right) \to +\infty \quad \text{as } \lambda \searrow 0. $$

We may view (1.13) as a combination of an upper and a lower bound, which we now prove.

*Upper bound in (1.13).* Define

$$ f_n(\lambda) := -n\lambda - k \log(1 - \nu(\lambda)); $$

note the notation suppresses the dependence on $k$. We will use the standard exponential bound

$$ (3.5) \qquad \mathbf{P}(\tau_k \le n) = \mathbf{P}(e^{-\lambda\tau_k} \ge e^{-\lambda n}) \le e^{\lambda n}(1 - \nu(\lambda))^k = e^{-f_n(\lambda)} \quad \text{for all } \lambda > 0. $$

Now, we define $\lambda_n > 0$ by $f'_n(\lambda_n) = 0$, or equivalently,

$$ (3.6) \qquad \frac{\nu'(\lambda_n)}{1 - \nu(\lambda_n)} = \frac{n}{k}, $$

so that $f_n$ achieves its (positive) supremum at $\lambda_n$. Then $\lambda_n \to 0$, since $n/k \to +\infty$. Therefore, thanks to (3.4), we get that

$$ (3.7) \qquad \frac{n}{k} \stackrel{n \to \infty}{\sim} \nu'(\lambda_n) \stackrel{n \to \infty}{\sim} \frac{1}{\lambda_n} \varphi\left(\frac{1}{\lambda_n}\right), $$

which is equivalent to

$$ (3.8) \qquad \frac{1}{\lambda_n} \stackrel{n \to \infty}{\sim} \frac{n}{k} \varphi^*\left(\frac{n}{k}\right). $$

Then, (3.4) gives that $\nu(\lambda_n) \stackrel{n \to \infty}{\sim} r(1/\lambda_n) \gg \varphi(1/\lambda_n)$, which with (3.7) shows that $n\lambda_n \ll k\nu(\lambda_n)$. In the end, we get

$$ (3.9) \qquad f_n(\lambda_n) = (1 + o(1))k\nu(\lambda_n) \stackrel{n \to \infty}{\sim} k r\left(\frac{1}{\lambda_n}\right) \stackrel{n \to \infty}{\sim} k r\left(\frac{n}{k}\varphi^*\left(\frac{n}{k}\right)\right). $$

With (3.5) this lets us conclude

$$ (3.10) \qquad \mathbf{P}(\tau_k \le n) \le \exp\left[-(1 + o(1))kr\left(\frac{n}{k}\varphi^*\left(\frac{n}{k}\right)\right)\right]. $$

*Lower bound in (1.13).* As is standard, we will obtain a corresponding lower bound using a tilted distribution. Let $\epsilon > 0$, and let $\tilde{\lambda}_n$ satisfy (analogously to (3.6))

$$ (3.11) \qquad \frac{\nu'(\tilde{\lambda}_n)}{1 - \nu(\tilde{\lambda}_n)} = (1 - \epsilon)\frac{n}{k}. $$

Then, let $\tilde{\mathbf{P}}, \tilde{\mathbf{E}}, \tilde{\text{Var}}$ denote the probability, expectation and variance with respect to the tilted distribution of the i.i.d. sequence $(G_1, G_2, \dots)$ given by

$$ \tilde{\mathbf{P}}(G_1 \in \cdot) = \frac{\mathbf{E}\left(e^{-\tilde{\lambda}_n \tau_1} \mathbf{1}_{\{\tau_1 \in \cdot\}}\right)}{\mathbf{E}(e^{-\tilde{\lambda}_n \tau_1})}. $$
We estimate

$$ (3.12) \qquad \begin{aligned} \mathbf{P}(\tau_k \le n) &\ge \frac{\mathbf{E}(e^{-\tilde{\lambda}_n \tau_k})}{e^{-(1-2\epsilon)n\tilde{\lambda}_n}} \frac{\mathbf{E}\left(e^{-\tilde{\lambda}_n \tau_k} \mathbf{1}_{\{\tau_k \in ((1-2\epsilon)n, n]\}}\right)}{\mathbf{E}(e^{-\tilde{\lambda}_n \tau_k})} \\ &\ge \exp\left((1-2\epsilon)n\tilde{\lambda}_n + k \log(1-\nu(\tilde{\lambda}_n))\right) \tilde{\mathbf{P}}(\tau_k \in ((1-2\epsilon)n, n)). \end{aligned} $$

Note that (3.8) translates here as

$$ \frac{1}{\tilde{\lambda}_n} \xrightarrow{n \to \infty} (1 - \epsilon) \frac{n}{k} \varphi^* \left( \frac{n}{k} \right), $$

so that $\nu(\tilde{\lambda}_n) \xrightarrow{n \to \infty} r(1/\tilde{\lambda}_n) \xrightarrow{n \to \infty} \nu(\lambda_n)$. As in (3.9), we get that

$$ (3.13) \qquad \mathbf{P}(\tau_k \le n) \ge \exp \left[ -(1+o(1))k \operatorname{r} \left( \frac{n}{k} \varphi^* \left( \frac{n}{k} \right) \right) \right] \times \tilde{\mathbf{P}}(\tau_k \in ((1-2\epsilon)n, n)), $$

and it only remains to show that the last probability converges to 1 as $n \to +\infty$.

It is standard that

$$ (3.14) \qquad \tilde{\mathbf{E}}(G_1) = \frac{\nu'(\tilde{\lambda}_n)}{1 - \nu(\tilde{\lambda}_n)} = (1 - \epsilon) \frac{n}{k}, $$

so we only need to show that $\tilde{\mathrm{Var}}(G_1) = o(n^2/k)$. In fact, we have

$$ (3.15) \qquad \tilde{\mathbf{E}}\left[(G_1)^2\right] = \frac{1}{1 - \nu(\tilde{\lambda}_n)} \sum_{j=1}^{\infty} j \varphi(j) e^{-\tilde{\lambda}_n j} \xrightarrow{n \to \infty} \frac{1}{(\tilde{\lambda}_n)^2} \varphi\left(\frac{1}{\tilde{\lambda}_n}\right) \xrightarrow{n \to \infty} \frac{1}{\tilde{\lambda}_n} (1 - \epsilon) \frac{n}{k}, $$

where the last equivalence is a slight variant of (3.7). Since $k\varphi(n) \to \infty$, by a similar variant of (3.8) we have

$$ \frac{1}{\tilde{\lambda}_n} \varphi\left(\frac{1}{\tilde{\lambda}_n}\right) \sim (1 - \epsilon) \frac{n}{k} \ll n\varphi(n), $$

and therefore $\tilde{\lambda}_n^{-1} = o(n)$. With (3.15) this shows that indeed $\tilde{\mathrm{Var}}(G_1) = o(n^2/k)$.

**Proof of (iii).** The existence of $I(b)$ is standard, and its asymptotics as $b \to \infty$ simply follow from (ii).

## 4. REVERSE RENEWAL THEOREMS

4.1. **Transient case, proof of Theorem 1.4.** Denote $p_\infty := \mathbf{P}(\tau_1 = +\infty) > 0$. We fix $\epsilon > 0$, and $A$ large enough so $\mathbf{P}(\tau_1 > A) \in [p_\infty, p_\infty + \epsilon]$, and hence $\mathbf{P}(A < \tau_1 < +\infty) \le \epsilon$. We then define the events

$$ A_1 = \{\tau \cap (0, A] = \emptyset\} \quad \text{and} \quad A_2 = \{\tau \cap [n - A, n) = \emptyset\}. $$

We claim that if $n$ is large enough,

$$ (1 - \epsilon)\mathbf{P}(\tau_1 \le A) \le \mathbf{P}(A_1^c | n \in \tau) \le (1 + \epsilon)\mathbf{P}(\tau_1 \le A), $$

$$ (4.1) \qquad \begin{aligned} (1 - \epsilon)\mathbf{P}(\tau_1 \le A) &\le \mathbf{P}(A_2^c | n \in \tau) \le (1 + \epsilon)\mathbf{P}(\tau_1 \le A), \\ (1 - \epsilon)\mathbf{P}(\tau_1 \le A)^2 &\le \mathbf{P}(A_1^c \cap A_2^c | n \in \tau) \le (1 + \epsilon)\mathbf{P}(\tau_1 \le A)^2. \end{aligned} $$
Indeed, we can write

$$ (4.2) \qquad \mathbf{P}(\mathcal{A}_1^c \cap \mathcal{A}_2^c | n \in \tau) = \sum_{i=1}^A \sum_{j=1}^A \mathbf{P}(\tau_1 = i) \mathbf{P}(\tau_1 = j) \frac{\mathbf{P}(n - i - j \in \tau)}{\mathbf{P}(n \in \tau)}. $$

Since $\mathbf{P}(n \in \tau)$ is regularly varying, for large $n$, the last ratio is close to 1 uniformly in $i, j \le A$, and the third line in (4.1) follows. The first two lines are proved similarly.

It follows from (4.1) that

$$ \begin{align} \mathbf{P}(\mathcal{A}_1 \cap \mathcal{A}_2 | n \in \tau) &= 1 - \mathbf{P}(\mathcal{A}_1^c | n \in \tau) - \mathbf{P}(\mathcal{A}_2^c | n \in \tau) + \mathbf{P}(\mathcal{A}_1^c \cap \mathcal{A}_2^c | n \in \tau) \nonumber \\ &\le 1 - 2\mathbf{P}(\tau_1 \le A) + \mathbf{P}(\tau_1 \le A)^2 + 3\epsilon \nonumber \\ &\le \mathbf{P}(\tau_1 > A)^2 + 3\epsilon \tag{4.3} \\ &\le (p_\infty + \epsilon)^2 + 3\epsilon. \nonumber \end{align} $$

Therefore for large $n$,

$$ (4.4) \qquad \mathbf{P}(\tau_1 = n) \le \mathbf{P}(\mathcal{A}_1, \mathcal{A}_2, n \in \tau) \le ((p_\infty + \epsilon)^2 + 3\epsilon) \mathbf{P}(n \in \tau). $$

Similarly to (4.3), $\mathbf{P}(\mathcal{A}_1 \cap \mathcal{A}_2 | n \in \tau) \ge p_\infty^2 - 3\epsilon$ and hence

$$ (4.5) \qquad \mathbf{P}(\mathcal{A}_1, \mathcal{A}_2, n \in \tau) \ge (p_\infty^2 - 3\epsilon) \mathbf{P}(n \in \tau). $$

To turn this into a lower bound on $\mathbf{P}(\tau_1 = n)$, we show that conditionally on $\{\mathcal{A}_1, \mathcal{A}_2, n \in \tau\}$, it is very likely that $\tau_1 = n$. More precisely, we claim that there exists $c_{16}$ such that, for $n$ large,

$$ (4.6) \qquad \mathbf{P}(\tau_1 \neq n, \mathcal{A}_1, \mathcal{A}_2, n \in \tau) \le c_{16} \epsilon \mathbf{P}(n \in \tau). $$

With (4.5), this shows that

$$ (4.7) \qquad \mathbf{P}(\tau_1 = n) = \mathbf{P}(\tau_1 = n, \mathcal{A}_1, \mathcal{A}_2, n \in \tau) \ge (p_\infty^2 - 3\epsilon - c_{16}\epsilon) \mathbf{P}(n \in \tau). $$

Since $\epsilon$ is arbitrary, (4.4) and (4.7) complete the proof of Theorem 1.4.

To prove (4.6), we write

$$ \begin{align} \mathbf{P}(\tau_1 \neq n, \mathcal{A}_1, \mathcal{A}_2, n \in \tau) &\le \sum_{i=A+1}^{n/2} \mathbf{P}(\tau_1 = i) \mathbf{P}(n - i \in \tau) \nonumber \\ &\quad + \sum_{i=n/2+1}^{n-A-1} \sum_{j=A+1}^{n-i} \mathbf{P}(\tau_1 = i) \mathbf{P}(\tau_1 = j) \mathbf{P}(n - i - j \in \tau). \tag{4.8} \end{align} $$

For the first sum in (4.8), since $\mathbf{P}(n \in \tau)$ is regularly varying, there is a constant $c_{17}$ such that, provided that $n$ is large, $\mathbf{P}(n - i \in \tau) \le c_{17} \mathbf{P}(n \in \tau)$ for every $i \le n/2$. Hence

$$ (4.9) \qquad \sum_{i=A+1}^{n/2} \mathbf{P}(\tau_1 = i) \mathbf{P}(n - i \in \tau) \le c_{17} \mathbf{P}(n \in \tau) \mathbf{P}(A < \tau_1 < +\infty) \le c_{17} \epsilon \mathbf{P}(n \in \tau). $$
For the second sum in (4.8), we use that $\mathbf{P}(\tau_1 = i) \le \mathbf{P}(i \in \tau) \le c_{17}\mathbf{P}(n \in \tau)$ for $n$ large enough, since $i \in (n/2, n)$. Therefore,

$$ (4.10) \qquad \sum_{i=n/2+1}^{n-A-1} \sum_{j=A+1}^{n-i} \mathbf{P}(\tau_1 = i) \mathbf{P}(\tau_1 = j) \mathbf{P}(n - i - j \in \tau) \le c_{17} \mathbf{P}(n \in \tau) \mathbf{P}(A < \tau_1 < +\infty) \times \sum_{k=0}^{+\infty} \mathbf{P}(k \in \tau) \le \frac{c_{17}}{p_\infty} \epsilon \mathbf{P}(n \in \tau), $$

and the proof of (4.6) is complete.

4.2. **Recurrent case, proof of Theorem 1.3.** The assumptions imply that the index of regular variation of $\mathbf{P}(n \in \tau)$ must be $-1$. Hence we have $\mathbf{P}(n \in \tau) = n^{-1}\ell_n$ with $\ell_n$ a slowly varying function. We can extend $U_n$ and $\ell_n$ to slowly varying functions $U(t)$ and $\ell(t)$ defined on $[1, \infty)$

We now apply standard Tauberian arguments, in particular [3, Corollary 1.7.3] which we use multiple times.

Set

$$ f(s) := \sum_{k=1}^{+\infty} s^k \mathbf{P}(\tau_1 = k), \quad u(s) := \sum_{k=0}^{+\infty} s^k \mathbf{P}(k \in \tau), \quad |s| < 1. $$

It is standard that, for $|s| < 1$

$$ u(s)(1 - f(s)) = 1 \quad \text{so} \quad f'(s) = \frac{u'(s)}{u(s)^2}. $$

Since $U_n$ is slowly varying, we have $u(s) \sim U((1-s)^{-1})$ as $s \nearrow 1$. Similarly, since $u'(s)$ is the generating function of $(n+1)\mathbf{P}(n+1 \in \tau) \sim \ell_n$ as $n \to \infty$, we have $u'(s) \sim (1-s)^{-1}\ell((1-s)^{-1})$ as $s \uparrow 1$. We therefore conclude that

$$ f'(s) \sim \frac{1}{1-s} \frac{\ell(\frac{1}{1-s})}{U(\frac{1}{1-s})^2} \quad \text{as } s \nearrow 1. $$

Since $\ell(t)/U(t)^2$ is slowly varying, it follows that $\sum_{k=0}^n k\mathbf{P}(\tau_1 = k) \sim n\ell_n/U_n^2$ as $n \to \infty$. This means that there is some $\epsilon_n$ decreasing to 0 sufficiently slowly so that

$$ \sum_{k=(1-\epsilon_n)n}^{n} k\mathbf{P}(\tau_1 = k) \stackrel{n \to \infty}{\sim} n\epsilon_n \frac{\ell_n}{U_n^2}. $$

By [3, Theorem 8.7.3] we have $U_n \stackrel{n \to \infty}{\sim} \mathbf{P}(\tau_1 > n)^{-1}$, and (1.15) follows. Equation (1.16) is an immediate consequence.

4.3. **Why not expect a stronger reverse renewal theorem?** In general, regular variation of $\mathbf{P}(n \in \tau)$ (here with index of regular variation $-1$) does not imply regular variation of $\mathbf{P}(\tau_1 = n)$. This shows that (1.16) cannot be true in general under the assumptions used to obtain (1.15). We give here only a description of an example, without proof details.

Let $\sigma$ be a recurrent renewal with inter-arrival distribution of form

$$ (4.11) \qquad \mathbf{P}(\sigma_1 = n) = \varphi(n) n^{-1}. $$
Now, let $\tau_1$ be $2\sigma_1$ or 1, with probability 1/2 each:

$$ \mathbf{P}(\tau_1 = 1) = \frac{1}{2}, \quad \mathbf{P}(\tau_1 = 2m) = \frac{1}{2}\mathbf{P}(\sigma_1 = m), \quad \mathbf{P}(\tau_1 = 2m - 1) = 0 \quad \text{for } m \ge 1. $$

Note that $r_n := \mathbf{P}(\tau_1 > n) \sim \frac{1}{2}\mathbf{P}(\sigma_1 > n)$. Then $\mathbf{P}(\tau_1 = n)$ is not regularly varying, but we will show that the gaps of length 1 have a smoothing effect, and make $\mathbf{P}(n \in \tau)$ regularly varying. More precisely, we claim that

$$ (4.12) \qquad \mathbf{P}(n \in \tau) \stackrel{n \to \infty}{\sim} \frac{\varphi(n)}{2r_n^2 n} \stackrel{n \to \infty}{\sim} \frac{\mathbf{P}(\tau_1 = 2\lfloor \frac{n}{2} \rfloor)}{2\mathbf{P}(\tau_1 > n)^2}, $$

where $\lfloor \cdot \rfloor$ denotes the integer part.

**Proof of (4.12).** We choose $\theta_n, \lambda_n$ satisfying

$$ r_n^{-1} \ll \theta_n \ll \varphi(n)^{-1} \quad \text{and} \quad 1 \ll \lambda_n \ll r_n^{-1/2}, $$

and decompose $\mathbf{P}(n \in \tau)$ into three sums:

$$ (4.13) \qquad \mathbf{P}(n \in \tau) = \sum_{k \le (\lambda_n r_n)^{-1}} \mathbf{P}(\tau_k = n) + \sum_{(\lambda_n r_n)^{-1} < k \le \theta_n} \mathbf{P}(\tau_k = n) + \sum_{k > \theta_n} \mathbf{P}(\tau_k = n). $$

We will show that the main contribution comes from the middle sum, see (4.19), the first and last sum being negligible.

**Middle sum.** We introduce $X_k$ the number of gaps of length 1 in the first $k$ gaps of $\tau$. For $(\lambda_n r_n)^{-1} < k \le \theta_n$, note that $\lambda_n \le k\lambda_n^2 r_n \ll k$ and $k \ll n$, and write

$$ (4.14) \qquad \mathbf{P}(\tau_k = n) = \mathbf{P}\left(X_k - \frac{k}{2} \in \left(-k\lambda_n r_n^{1/2}, k\lambda_n r_n^{1/2}\right); \tau_k = n\right) \\ \qquad \qquad + \mathbf{P}\left(|X_k - \frac{k}{2}| \ge k\lambda_n r_n^{1/2}; \tau_k = n\right). $$

The last probability is small. Indeed, there is a constant $c_{33}$ such that

$$ \mathbf{P}\left(|X_k - \frac{k}{2}| \ge k\lambda_n r_n^{1/2}\right) \le e^{-c_{33}\lambda_n^2 r_n k} \quad \text{for all } k \ge 1; $$

conditioning on $X_k$ we therefore get that

$$ (4.15) \qquad \mathbf{P}\left(|X_k - \frac{k}{2}| \ge k\lambda_n r_n^{1/2}; \tau_k = n\right) \le e^{-c_{33}\lambda_n^2 r_n k} \sup_{1 \le j \le k} \sup_{\frac{n-k}{2} \le m \le \frac{n}{2}} \mathbf{P}(\sigma_j = m). $$

Here the sups are over all possible values of $j = k - X_k$ and $m = (n - X_k)/2$. Applying (1.11) we see that for $n$ large, for all $m \ge (n-k)/2 \ge n/4$ and $j \le k$, we have

$$ \mathbf{P}(\sigma_j = m) \le c_{34}k\mathbf{P}(\sigma_1 = n). $$

Since $e^{-c_{33}\lambda_n^2 r_n k} = o(1) e^{-kr_n}$ as $n \to \infty$, uniformly in middle-sum values of $k$, we get that

$$ (4.16) \qquad \mathbf{P}\left(|X_k - \frac{k}{2}| \ge k\lambda_n r_n^{1/2}; \tau_k = n\right) = o(1)ke^{-kr_n} \frac{\varphi(n)}{n} \quad \text{as } n \to \infty, $$

with the $o(1)$ uniform over middle-sum values of $k$.
For the first probability on the right in (4.14), we use (1.10). Uniformly for $j$ in the interval $\frac{k}{2} + (-k\lambda_n r_n^{1/2}, k\lambda_n r_n^{1/2})$ with $j \equiv n-k \bmod 2$, and for middle-sum values of $k$ (which satisfy $k\varphi(n) \xrightarrow{n \to \infty} 0$ and $k \to +\infty$), we have $j \sim k/2$ and $k \ll n$, so

$$ (4.17) \qquad \begin{aligned} \mathbf{P}\left(\sigma_j = \frac{n-k+j}{2}\right) &= (1+o(1))k\left(1-2r_{(n-k+j)/2}\right)^j \frac{\varphi(n/2)}{n/2} \\ &= (1+o(1))2ke^{-kr_n(1+o(1))} \frac{\varphi(n)}{n}, \end{aligned} $$

since $\mathbf{P}(\sigma_1 > n) \xrightarrow{n \to \infty} 2r_n$. Therefore, since

$$ \mathbf{P}\left(X_k - \frac{k}{2} \in (-k\lambda_n r_n^{1/2}, k\lambda_n r_n^{1/2}) ; X_k \equiv n \bmod 2\right) \to \frac{1}{2} \quad \text{as } n \to \infty, $$

conditioning again on $X_k$ we get that for middle-sum values of $k$,

$$ (4.18) \qquad \mathbf{P}\left(X_k - \frac{k}{2} \in (-k\lambda_n r_n^{1/2}, k\lambda_n r_n^{1/2}) ; \tau_k = n\right) = (1+o(1)) \frac{ke^{-kr_n(1+o(1))}}{n}, $$

with the $o(1)$ uniform over middle-sum values of $k$.

Summing (4.16) and (4.18), we obtain straightforwardly that

$$ (4.19) \qquad \sum_{(\lambda_n r_n)^{-1} < k \le \theta_n} \mathbf{P}(\tau_k = n) = \sum_{(\lambda_n r_n)^{-1} < k \le \theta_n} (1+o(1)) \frac{ke^{-kr_n(1+o(1))}}{n} = (1+o(1)) \frac{\varphi(n)}{2r_n^2 n}. $$

We are therefore left with showing that the two other sums in (4.13) are negligible.

**First sum.** Using (1.11) and (4.11) and conditioning once more on $X_k$, we get that there exists a constant $c_{35}$ such that for $n$ large enough, for any $k \le (\lambda_n r_n)^{-1}$,

$$ \mathbf{P}(\tau_k = n) \le \sup_{1 \le j \le k} \sup_{\frac{n-k}{2} \le m \le \frac{n}{2}} \mathbf{P}(\sigma_j = m) \le c_{35} k \frac{\varphi(n)}{n}, $$

which gives

$$ (4.20) \qquad \sum_{k \le (\lambda_n r_n)^{-1}} \mathbf{P}(\tau_k = n) \le \frac{c_{35}}{(\lambda_n r_n)^2} \frac{\varphi(n)}{n} = o(1) \frac{\varphi(n)}{r_n^2 n}. $$

**Last sum.** Similarly to (4.16)-(4.18) but using (1.11) in place of (1.10), we obtain that there exists $c_{36}$ such that for all $\theta_n < k \le n/2$,

$$ \mathbf{P}(\tau_k = n) \le c_{36} ke^{-kr_n(1+o(1))} \frac{\varphi(n)}{n} \le ke^{-kr_n/2} \frac{\varphi(n)}{n}, $$

the last inequality being valid for $n$ large, since $kr_n \to +\infty$.

For $k \in (n/2, n]$, we use that

$$ \mathbf{P}(\tau_k = n) \le (1 - r_n)^k \le e^{-nr_n/2}. $$

Since $\theta_n \gg r_n^{-1}$, we therefore obtain that

$$ (4.21) \qquad \sum_{k > \theta_n} \mathbf{P}(\tau_k = n) \le \sum_{k > \theta_n} ke^{-kr_n/2} \frac{\varphi(n)}{n} + ne^{-nr_n/2} = o(1) \frac{\varphi(n)}{r_n^2 n}. $$
This completes the proof of (4.12).

☐

**Acknowledgments:** The authors are grateful to V. Wachtel for bringing the work of Nagaev [22] to their attention. We also thank the anonymous reviewer, which pointed out several references, and suggested a shorter proof of Theorem 1.3.

## REFERENCES

[1] K. S. Alexander and Q. Berger, *Local asymptotics for the first intersection of two independent renewals*, preprint, arXiv:1603.05531 [math.PR]

[2] S. Asmussen, *Applied Probability and Queues*, Second Edition, Applications of Mathematics **51**, Springer-Verlag, New York, 2003.

[3] N. H. Bingham, C. M. Goldie and J. L. Teugels, *Regular variations*, Cambridge University Press, Cambridge, 1987.

[4] F. Caravenna, *The strong renewal theorem*, preprint, arXiv:1507.07502 [math.PR]

[5] J. Chover, P. Ney and S. Wainger, *Functions of probability measures*, J. Anal. Math., **25** pp. 255–302, 1973.

[6] Z. Chi, *Strong renewal theorem with infinite mean beyond local large deviations*, Ann. Appl. Probab. **25** (2015), pp. 1513–1539.

[7] Z. Chi, *Integral criteria for Strong Renewal Theorems with infinite mean*, preprint, arXiv:1312.6089v3 [math.PR]

[8] D. A. Darling, *The influence of the maximum term in the addition of independent random variables*, Trans. Amer. Math. Soc. **73**, pp. 95–107, 1952.

[9] D. Denisov, A. B. Dieker and V. Shneer, *Large deviations for random walks under subexponentiality: the big-jump domain*, Ann. Probab., **38** 5, pp. 1946–1991, 2008.

[10] R. A. Doney, *One-sided local large deviation and renewal theorems in the case of infinite mean*, Probab. Theory Relat. Fields, **107**, pp. 451–465, 1997.

[11] R. A. Doney, *The strong renewal theorem with infinite mean via local large deviations*, preprint, arXiv:1507.06790 [math.PR]

[12] R. A. Doney and D. A. Korshunov, *Local asymptotics for the time of first return to the origin of transient random walk*, Stat. Probab. Letters, **81** 5, pp. 363–365, 2011.

[13] K. B. Erickson, *Strong renewal theorems with infinite mean*, Transaction of the American Mathematical Society, **151**, 1970.

[14] W. Feller, *An introduction to probability theory and its applications, Vol. 1*, 2nd edition, Wiley series in probability and mathematical statistics, John Wiley & Sons. Inc., New York-London-Sydney, 1966.

[15] A. Garsia and J. Lamperti, *A discrete renewal theorem with infinite mean*, Comm. Math. Helv. **37**, pp. 221–234, 1963.

[16] G. Giacomin, *Random polymer models*, Imperial College Press, 2007.

[17] B. V. Gnedenko, *Sur la distribution limite du terme maximum d'une série aléatoire*, Ann. Math. **(2)** **44**, pp. 423–453, 1943.

[18] B. V. Gnedenko and A. N. Kolmogorov, *Limit Theorems for Sums of Independent Random Variables*, Addison-Wesley, Cambridge, 1954.

[19] N. C. Jain and W. E. Pruitt, *The range of random walk*, Proc. Sixth Berkeley Symp. Math. Statist. Probab. **3** pp. 31–50, Univ. California Press, Berkeley, 1972.

[20] Y. Kasahara, *A limit theorem for sums of i.i.d. random variables with slowly varying tail probability*, J. Math. Kyoto Univ. **26**, pp. 437–443, 1986.

[21] H. Kesten, *Ratio Theorems for Random Walks II*, J. Analyse Math. **11**, pp. 323–379, 1963.

[22] S. V. Nagaev, *The Renewal Theorem in the Absence of Power Moments*, Theory Probab. Appl., **56** No. 1, pp. 166–175, 2012.

[23] S. V. Nagaev, *Large deviations of sums of independent random variables*, Ann. Probab. **7**, 745-789, 1979.

[24] S. V. Nagaev and V. I. Wachtel, *On sums of independent random variables without power moments*, Sib. Math. J., **49**, No. 6, pp. 1091–1010, 2008.
[25] H. Teicher, *Rapidly growing random walks and an associated stopping time*, Ann. Probab. **7**, pp. 1078-1081, 1979.

[26] S. Watanabe, *A limit theorem for sums of i.i.d. random variables with slowly varying tail probability*, Multivariate Analysis, V, Proc. Fifth Internat. Sympos., Pittsburgh, PA, 1978, pp. 249–261, North-Holland, Amsterdam, 1980.

[27] J. A. Williamson, *Random walks and Riesz kernels*, Pacific J. Math. **25**, pp. 393-415, 1968.

DEPARTMENT OF MATHEMATICS, KAP 108, UNIVERSITY OF SOUTHERN CALIFORNIA, LOS ANGELES, CA 90089-2532 USA

LPMA, UNIVERSITÉ PIERRE ET MARIE CURIE, CAMPUS JUSSIEU, CASE 188, 4 PLACE JUSSIEU, 75252 PARIS CEDEX 5, FRANCE

*E-mail address: quentin.berger@upmc.fr*