\input amstex
\documentstyle{amsppt}
\magnification=1200
\TagsOnRight
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\topmatter
\title
Limit Theorem for the Local Time of\\
Bond-True Self-Avoiding Walk on $\Bbb Z$
\endtitle
\rightheadtext{Bond-True Self-Avoiding Walk on $\Bbb Z$}
\author
B\'alint T\'oth
\footnote""{Work supported by the Hungarian National Foundation
for Scientific Research, grant No. 1902\hfill\hfill\hfill}
\footnote""{Submitted for publication to {\sl The Annals of
Probability}, 17 May 1993\hfill\hfill\hfill}
\endauthor
\affil
Mathematical Institute of the\\
Hungarian Academy of Sciences
\endaffil
\address
{B. T\'oth\newline
Mathematical Institute of the\newline
Hungarian Academy of Sciences\newline
POB 127\newline
H-1364 Budapest, Hungary\newline
e-mail: h1222tot\@huella.bitnet}
\endaddress
\abstract
{
The bond-true self-avoiding walk is a nearest neighbour random
walk on $\Bbb Z$, for which the probability of jumping along a
bond of the lattice is proportional to
$\exp(-g\cdot\text{number of previous jumps along that bond})$.
We prove a limit theorem for the distribution of the local time
process of this walk. A consequence of the main theorem is a
limit law for $n^{-3/2}T_n$ where $T_n$ is the first hitting
time of the lattice site at distance $n$ from the origin.
}
\endabstract
\endtopmatter
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\document

\bigskip
\noindent
{\bf 1. Introduction and Result}

\medskip
In the present paper we consider a `bond-true' self-avoiding
walk (BTSAW)
$X_i$ on the one-dimensional integer lattice
$\Bbb Z$, defined as follows: the walk starts from the origin of
the lattice and at time $i+1$ it jumps to one of the two
neighbouring sites of $X_i$, so that the probability of jumping
along a bond of the lattice is proportional to
$$
\exp (-g\cdot \text{number of previous jumps along that bond}).
$$
More formally, for a nearest neighbour walk $\underline{x}_0^i=
(x_0,x_1,\dots,x_i)$ and a lattice site $y\in\Bbb Z$ we define
$$
\align
r(y|\underline{x}_0^i)&=\#\left\{\,0\le
j<i\,:\,x_j=y-1,\,x_{j+1}=y\,\right\},
\tag 1.1
\\
l(y|\underline{x}_0^i)&=\#\left\{\,0\le
j<i\,:\,x_j=y,\,x_{j+1}=y-1\,\right\},
\tag 1.2
\\
v(y|\underline{x}_0^i)&=r(y|\underline{x}_0^i)+
l(y|\underline{x}_0^i).
\tag 1.3
\endalign
$$
Denoting $\text{e}^{-g}=\lambda\in(0,1)$, the walk
is governed by the law:
$$
\align
\bold P
\big(\,X_{i+1}&=x_i+1\,\big|\!\!\big|
\,\underline{X}_0^i=\underline{x}_0^i\,\big)=
\frac{\lambda^{v(x_i+1|\underline{x}_0^i)}}
{\lambda^{v(x_i+1|\underline{x}_0^i)}+
 \lambda^{v(x_i|\underline{x}_0^i)}},
\tag 1.4
\\
\bold P
\big(\,X_{i+1}&=x_i-1\,\big|\!\!\big|
\,\underline{X}_0^i=\underline{x}_0^i\,\big)=
\frac{\lambda^{v(x_i|\underline{x}_0^i)}}
{\lambda^{v(x_i+1|\underline{x}_0^i)}+
 \lambda^{v(x_i|\underline{x}_0^i)}}.
\tag 1.5
\endalign
$$
The only difference from the `orthodox' site-true self-avoiding
walk (STSAW), (see [APP]), is that here we count the local
time spent on
edges, while the jump probabilities of STSAW are determined by
the local time spent on sites. We expect that the physical
phenomena should be very similar in the two cases. Based on a
renormalization group argument it has been conjectured in [APP]
that the upper critical dimension of STSAW is $d_c=2$. That is:
in more than two dimensions the STSAW behaves diffusively, like
an ordinary random walk, with logarithmic corrections in two
dimensions. Computer simulations of the same authors seem to
agree with this conjecture. It is natural to expect
over-diffusive behaviour below the critical dimension, i.e.
in $d=1$. Unfortunately we do not know about any reliable computer
simulations of the one dimensional problem. We do not know
about the existence of any rigorous results concerning true self
avoiding walks either. However, let us mention here two related
problems: (1) the self-avoiding walk problem (which is, strictly
speaking, not a random walk in the sense of stochastic process
evolving in time), has a long history and there are deep and
technically difficult results concerning it (see e.g. [BS], [HS],
[Bo] and references cited in these papers), and (2) on the other
end of the spectrum are the problems related to self-attracting
rather than self-repelling walks, a typical example being the
so-called reinforced random walk (see e.g. [P], or for a
one-dimensional problem closer to our present paper [D]).


In this paper we prove a limit theorem for the local time
process of the BTSAW considered. Denote by $T_n$ the first
hitting time of the site $n\in \Bbb Z\cap(0,\infty)$:
$$
T_n=\min\left\{\,i\ge0\,:\,X_i=n\,\right\}.
\tag 1.6
$$
The (bond) local time process considered is the following:
$$
S_n(t)=l(n-t|\underline{X}_0^{T_n}),\quad t=0,1,2,\dots
\tag 1.7
$$
Looking at the formal definitions only, in principle, some of
the $S_n(t),\,\,t\ge0$ or the hitting time $T_n$ might be
infinite, but we shall see soon that, with probability one, this
is {\it not\/} the case. Clearly
$$
v(n-t|\underline{X}_0^{T_n})=\left\{\matrix\format\l&\l\\
       2S_n(t)+1\quad&\text{ for }\quad 0\le t<n\\
       2S_n(t)  \quad&\text{ for }\quad n\le t.
                    \endmatrix\right.
\tag 1.8
$$
Let
$$
\omega_n=\inf\{t>n:S_n(t)=0\}.
\tag 1.9
$$
>From the definition of $S_n(\cdot)$ follows that $S_n(t)=0$
for $t\ge\omega_n$ and
$$
T_n=\sum_{t\ge0}v(n-t|\underline{X}_0^{T_n})=
2\sum_{t=0}^{\omega_n}S_n(t)+n.
\tag 1.10
$$

\proclaim{Proposition 1}
$$
\align
\omega_n&<\infty
\tag 1.11
\\
T_n&<\infty
\tag 1.12
\endalign
$$
almost surely.
\endproclaim

Let $W_s,\,s\in\Bbb R_+$ be a standard one-dimensional Wiener
process and $\omega$  the following stopping time:
$$
\omega=\inf\left\{\,s>1\,:\,W_s=0\,\right\}.
\tag 1.13
$$
Our main result is the following theorem
\proclaim{ Theorem 1}
$$
\left(
\frac{\omega_n}{n},
\frac{S_n([ns])}{\sigma\sqrt n}: 0\le s\le\frac{\omega_n}{n}
\right)
\Rightarrow
\left(
\omega, \left|W_{s}\right|:0\le s\le\omega
\right)
\tag 1.14
$$
in $\Bbb R_+\times D[0,\infty)$, where
$$
\sigma^2=\frac
{\sum_{x\in\Bbb Z}x^2\lambda^{x^2}}
{\sum_{x\in\Bbb Z}\lambda^{x^2}}.
\tag 1.15
$$
\endproclaim

Straightforward consequence of Proposition 1 and Theorem 1 is
the recurrence of the random walk considered:

\proclaim{Corollary 1}
The BTSAW visits infinitely often every lattice site, almost
surely.
\endproclaim

\noindent
>From (1.10) and (1.14) directly follows the limit theorem for
the first hitting times:
\proclaim{Corollary 2}
$$
\frac{T_n}{2\sigma
n^{3/2}}\Rightarrow\int_0^{\omega}\left|W_s\right|\text{d}s.
\tag 1.16
$$
\endproclaim

This last limit law shows that the BTSAW behaves {\it
over-diffusively\/} indeed, the suggested rate of diffusion
being $X_t\sim t^{2/3}$.

The paper contains three more sections and an Appendix. In
section 2 we describe the local time process $S_n(\cdot)$ as a
random walk on $\Bbb Z_+$. In section 3 we investigate in more detail
an auxiliary Markov chain arising naturally in the previous
description. Finally in section 4 we prove the results stated
above, by coupling the process $S_n(\cdot)$ to an appropriately
constructed homogeneous reflected random walk. The Appendix is
devoted to the proof of a technical lemma.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bigskip
\noindent
{\bf 2. The Local Time Process as a Markov Chain}

\medskip
The clue of the proof is the observation that, with $n$
fixed, the local time process $S_n(\cdot)$ defined in (1.7) is
a Markov chain on $\Bbb Z_+=\Bbb Z\cap[0,\infty)$. Apparently
this trick has its origin in F.B. Knight's paper [K] and has
been rediscovered several times since then (see e.g. [KKS]).
However, as opposed to the previous applications of this trick,
the Markov process arising in our case will be more complicated
than a branching process [K], or a branching process with random
offspring distribution [KKS].

A finite walk which hits $n$ for the first time at time $i$
$$
0=x_0,x_1,\dots,x_{i-1},x_i=n,\qquad\min\{j:x_j=n\}=i
\tag 2.1
$$
determines uniquely a finite sequence
$$
\align
L(0)&=0
\\ \\
\underline l(t)&=\left\{\matrix\format\l&\l&\r\\
\left(l_0(t),\dots,l_{L(t-1)}(t)\right)
\quad&\text{ if }\quad&1\le t\le n
\\ \\
\left(l_1(t),\dots,l_{L(t-1)}(t)\right)
\quad&\text{ if }\quad& t > n
\endmatrix\right.
\tag 2.2
\\ \\
L(t)&=\sum_{k=0(1)}^{L(t-1)}l_k(t)
\endalign
$$
where $l_k(t)$ is the number of steps $(n-t)\to(n-t-1)$ between
the $k$-th and $(k+1)$-th steps $(n-t)\to(n-t+1)$ performed by
the walk. We shall refer to the sequence (2.2) as the system of
left steps of the walk (2.1). Finiteness of the system of left
steps means that there exists a $t_{\max}>n$ such that
$L(t_{\max})=0$. This correspondence between finite walks hitting
$n$ and finite systems of left steps is {\it one-to-one}: given
the sequence (2.2) one can reconstruct the complete walk (2.1)
univocally.

Let (2.1) be a finite walk hitting $n$ and (2.2) the
corresponding system of left steps. Since $T_n$ is a stopping
time, the probability that the BTSAW coincides with (2.1) till
$T_n$ is
$$
\bold
P\Big(\underline{X}_0^{T_n}=\underline{x}_0^i\Big)
=\prod_{j=0}^{i-1}
\frac{\lambda^{v((x_j+x_{j+1}+1)/2|\underline{x}_0^j)}}
{\lambda^{v(x_j|\underline{x}_0^j)}+
\lambda^{v(x_j+1|\underline{x}_0^j)}},
\tag 2.3
$$
cf (1.4), (1.5).
Written in terms of the $\underline l(t)$-s
$$
\bold
P\Big(\underline{X}_0^{T_n}=\underline{x}_0^i\Big)=
\left[\prod_{t=1}^{n-1}
\Cal{P}_{\!-}\big(L(t-1);\underline l(t)\big)\right]
\Cal{P}_{\!0}\big(L(n-1);\underline l(n)\big)
\left[\prod_{t>n}
\Cal{P}_{\!+}\big(L(t-1);\underline l(t)\big)\right],
\tag 2.4
$$
with the transition probabilities:
\allowbreak
$$
\align
\Cal{P}_{\!-}\big(L;\underline l^{\prime}\big)&=
\prod_{k=0}^{L}\left[\prod_{i=1}^{l^{\prime}_k}
\frac
{\dsize
\lambda^{2(\sum_{m=0}^{k-1}l^{\prime}_{m}+i-1)+1
        }
}
{\dsize
\lambda^{2k}+
\lambda^{2(\sum_{m=0}^{k-1}l^{\prime}_{m}+i-1)+1
        }
}
\right]
\frac
{\dsize
\lambda^{2k}
}
{\dsize
\lambda^{2k}+
\lambda^{2\sum_{m=0}^{k}l^{\prime}_{m}+1
        }
}
\tag 2.5
\\
\Cal{P}_{\!0}\big(L;\underline l^{\prime}\big)&=
\prod_{k=0}^{L}\left[\prod_{i=1}^{l^{\prime}_k}
\frac
{\dsize
\lambda^{2(\sum_{m=0}^{k-1}l^{\prime}_{m}+i-1)
        }
}
{\dsize
\lambda^{2k}+
\lambda^{2(\sum_{m=0}^{k-1}l^{\prime}_{m}+i-1)
        }
}
\right]
\frac
{\dsize
\lambda^{2k}
}
{\dsize
\lambda^{2k}+
\lambda^{2\sum_{m=0}^{k}l^{\prime}_{m}
        }
}
\tag 2.6
\\
\Cal{P}_{\!+}\big(L;\underline l^{\prime}\big)&=
\prod_{k=1}^{L}\left[\prod_{i=1}^{l^{\prime}_k}
\frac
{\dsize
\lambda^{2(\sum_{m=1}^{k-1}l^{\prime}_{m}+i-1)
        }
}
{\dsize
\lambda^{2k-1}+
\lambda^{2(\sum_{m=1}^{k-1}l^{\prime}_{m}+i-1)
        }
}
\right]
\frac
{\dsize
\lambda^{2k-1}
}
{\dsize
\lambda^{2k-1}+
\lambda^{2\sum_{m=1}^{k}l^{\prime}_{m}
        }
}
\tag 2.7
\endalign
$$
Thus, the process  $S_n(\cdot)$ is indeed a Markov chain on
$\Bbb Z_{+}$, homogeneous in the intervals $0\le t<n$ \ and \
$t>n$. \newline
{\sl Remark:\/} In case of STSAW this rearrangement of the
product, i.e. the transcription of (2.3) to (2.4) can not be
performed. This is the step, where the proof of a similar result
for the STSAW fails.

The transition probabilities $\Cal{P}_{\!\pm,0}$ look quite
threatening at the first sight, but we shall see soon, that they
have a transparent interpretation and can be tamed.
In order to see this we define an auxiliary Markov chain on
$\Bbb Z$ which will help understanding better the random walk
$S_n(\cdot)$.

For $z\in\Bbb Z$ let
$$
p(z)=\frac{\lambda^{2z+1}}{1+\lambda^{2z+1}},\quad
q(z)=\frac{1}{1+\lambda^{2z+1}},
\tag 2.8
$$
and for $x,y\in\Bbb Z$
$$
P(x,y)=\left\{\matrix\format\c&\l\\
\dsize\prod_{z=x}^{y}p(z)q(y+1)\quad&\text{ if }\quad x-1\le y
\\ \\
                  0            \quad&\text{ if }\quad x-1 >  y
\endmatrix\right.
\tag 2.9
$$
(When $x=y+1$, the empty product is by definition equal to 1.)
>From $\prod_{z=x}^{\infty}p(z)=0$ follows that $P$ is the transition
matrix of a Markov chain
$\eta_k,\,\,k=0,1,2,\dots$ on $\Bbb Z$.
On the right hand side of (2.5) (resp. (2.7)) we have exactly the
probability distribution of the first $L+1$ steps (resp. the
first $L$ steps) of the Markov chain $\eta_{\cdot}$ starting
form $0$ (resp. starting from $-1$). More precisely
$$
\align
\Cal{P}_{\!-}(L;\underline l)&=\bold P\Big(
\eta_{k+1}-\eta_{k}=l_{k}-1,\,\,\,k=0,1,\dots,L \Big|\!\Big|
\eta_0=0\Big)
\tag 2.10
\\
\Cal{P}_{\!+}(L;\underline l)&=\bold P\Big(
\eta_{k}-\eta_{k-1}=l_{k}-1,\,\,\,k=1,\dots,L \Big|\!\Big|
\eta_0=-1\Big)
\tag 2.11
\endalign
$$
Thus, denoting by $\xi_n(t)$ the $t$-th
step of the random walk $S_n(\cdot)$, i.e.
$$
\xi_n(t)=S_n(t)-S_n(t-1),\qquad t\ge1
\tag 2.12
$$
we get
$$
\bold P\Big(\,\xi_n(t)=x\,\Big|\!\Big|\,S_n(t-1)=k\,\Big)=
\left\{\matrix\format\l&\l\\
P^{k+1}(0,x-1)\quad&\text{ for }\quad t<n,
\\ \\
P^{k}(-1,x-1)  \quad&\text{ for }\quad t>n.
\endmatrix\right.
\tag 2.13
$$
The transition probabilities for \ $t=n$ \ are a little
different,
but this single step will  not have any effect on the limit law
of the local time process.

\demo{Proof of Proposition 1, first part}
As $S_n(0)=0$ and (2.13) are bona fide transition probabilities,
i.e. $\bold
P\left(\xi_n(t)\in[-k,\infty)|\!|S_n(t-1)=k<\infty\right)=1$,
the local times $S_n(t)\in\Bbb Z_+$ are almost surely finite.
$\omega_n<\infty$ will be proved in Proposition 2, section 4.
\enddemo

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bigskip
\noindent
{\bf 3. The Auxiliary Markov chain: Technical Lemmas}

\medskip

In this section we summarize the properties of
the Markov chain $\eta_i$ needed for the proof of Theorem 1.
Denote by $\pi$ the following
probability distribution on $\Bbb Z$:
$$
\pi(x)=\frac{\lambda^{x^2}}
            {\sum_{x\in\Bbb Z}\lambda^{x^2}},
\qquad x\in\Bbb Z
\tag 3.1
$$
\proclaim{Lemma 1}
The unique stationary distribution of the
Markov chain $\eta$ is
$$
\rho(x)=\pi(x+1), \qquad x\in\Bbb Z.
\tag 3.2
$$
There exist constants $C_1<\infty$ and $C_2>0$ such that
for $x=0$ or $x=-1$
the following exponential bound holds:
$$
\sum_{y\in\Bbb Z}   \left|P^k(x,y)-\rho(y)\right|<C_1\text{e}^{-C_2 k},
\tag 3.3
$$
\endproclaim

\demo{Proof}
($\imath$) The identity
$$
P(x,y)=\left\{\matrix\format\c&\l\\
\dsize\frac{1}{\rho(x)}
\left[p(x)\prod_{z=x+1}^{y+1}q(z)\right]\rho(y)
\quad&\text{ for }\quad x-1\le y
\\ \\
                  0
\quad&\text{ for }\quad x-1 >  y
\endmatrix\right.
\tag 3.4
$$
is straightforward. Hence
$$
\sum_{x\in\Bbb Z}\rho(x)P(x,y)=
\left[\sum_{x\le y+1}p(x)\prod_{z=x+1}^{y+1}q(z)\right]\rho(y)=
\rho(y)
\tag 3.5
$$
which proves that $\rho$ is a stationary distribution indeed.

The proof of uniqueness and exponential convergence (3.3) is a
bit lengthy, but consists of standard procedures. First of all
notice that due to stationarity of the distribution $\rho$
inequality
$$
P^k(x,y)\le\frac{\rho(y)}{\rho(x)}.
\tag 3.6
$$
holds, which provides an over-exponential bound, uniform in $k$,
on the tails of the distributions $P^k(x,\cdot)$. In consequence
all the expectations below make sense.

Denote by $\theta_{\pm}$ and $\sigma$ the following stopping
times
$$
\align
\theta_+&=\min\{k\ge0:\eta_k\ge 0\}
\tag 3.7
\\
\theta_-&=\min\{k\ge0:\eta_k\le 0\}
\tag 3.8
\\
\sigma_{\phantom{+}}&=\min\{k\ge1:\eta_k= 0\}
\tag 3.9
\endalign
$$
According to Theorem 6.14 and Example 5.5(a) of [NU]  the
uniqueness of the stationary distribution and the exponential
convergence (3.3) follow from
$$
\bold E\Big(\exp(C_2\sigma)\Big|\!\Big|\eta_0=0\Big)<\infty,
\tag 3.10
$$
with $C_2>0$.
So, our goal is to prove (3.10). In the following expression we
use the fact that the Markov chain $\eta_{\cdot}$ doesn't jump
more than one lattice step to the left:
$$
\align
&\bold E\Big(\text{e}^{C_2\sigma}\Big|\!\!\Big|\eta_0=0\Big)=
\text{e}^{C_2}\sum_{y\ge 0}P(0,y)
\bold E\Big(\text{e}^{C_2\theta_-}\Big|\!\!\Big|\eta_0=y\Big)
\\
&\qquad+\text{e}^{C_2}P(0,-1)\sum_{y\ge 0}
\bold E\Big(\text{e}^{C_2\theta_+}1\!\!1(\eta_{\theta_+}=y)
\Big|\!\!\Big|\eta_0=-1\Big)
\bold E\Big(\text{e}^{C_2\theta_-}\Big|\!\!\Big|\eta_0=y\Big).
\tag 3.11
\endalign
$$
Next we use a special consequence of the structure (2.9) of the
transition kernel $P$. Namely, it is an easy computation to check
that given $\eta_0=x<0$ the random variables $\theta_+$ and
$\eta_{\theta_+}$ are independent and, for $y\ge 0$
$$
\bold E\Big(\text{e}^{C_2\theta_+}1\!\!1(\eta_{\theta_+}=y)
\Big|\!\!\Big|\eta_0=-1\Big)=
\frac{P(0,y)}{1-P(0,-1)}
\bold E\Big(\text{e}^{C_2\theta_+}
\Big|\!\!\Big|\eta_0=-1\Big).
\tag 3.12
$$
>From (3.11), (3.12):
$$
\align
\bold E\Big(\text{e}^{C_2\sigma}\Big|\!\Big|\eta_0=0\Big)=
\text{e}^{C_2}\sum_{y\ge 0}&P(0,y)
\bold E\Big(\text{e}^{C_2\theta_-}\Big|\!\!\Big|\eta_0=y\Big)
\\
&\times\left[1+
\frac{P(0,-1)}{1-P(0,-1)}
\bold E\Big(\text{e}^{C_2\theta_+}
\Big|\!\!\Big|\eta_0=-1\Big)\right].
\tag 3.13
\endalign
$$
>From a dominated convergence argument we can see that
$$
P(-\infty,y)=\lim_{x\to-\infty}P(x,y)=\prod_{z=-\infty}^{y+1}
p(z)q(y+1)
\tag 3.14
$$
is a probability distribution on $\Bbb Z$.
Let $x_1\le x_2$, then for $y\ge x_2-1$
$$
P(x_1,y)=\left[\sum_{z\ge x_2-1}P(x_1,z)\right]P(x_2,y)
\tag 3.15
$$
which implies that the distributions $P(x,\cdot)$ are
stochastically ordered: for $x_1<x_2$ and arbitrary $y_0$
$$
\sum_{y\ge y_0}P(-\infty,y)<
\sum_{y\ge y_0}P(x_1,y)<\sum_{y\ge y_0}P(x_2,y)
\tag 3.16
$$
>From (3.16) follows that
$$
\bold P\Big(\theta_+>k\Big|\!\Big|\eta_0=-1\Big)\le r^k,
\quad\text{ where }\quad r=\sum_{y<0}P(-\infty,y)<1.
\tag 3.17
$$
Hence
$$
\bold E\Big(\exp(C_3\theta_+)\Big|\!\Big|\eta_0=-1\Big)<\infty
\tag 3.18
$$
for $C_3<-\log r$.

On the other hand, since  $p(z)>p(z+1)$, (see (2.8)),
the distributions $P(x,x+\cdot)$ are stochastically ordered in
the opposite sense: for $x_1<x_2$ and arbitrary $y_0$
$$
\sum_{y\ge y_0}P(x_1,x_1+y)=\prod_{z=0}^{y_0}p(x_1+z)>
\prod_{z=0}^{y_0}p(x_2+z)=\sum_{y\ge y_0}P(x_2,x_2+y).
\tag 3.19
$$
Hence, for $y\ge0$
$$
\bold P\Big(\min_{0\le j\le k}\eta_j\le 0
\Big|\!\Big|\eta_0=y\Big)\ge
\bold P\Big(\min_{0\le j\le k}\sum_{i=1}^j\zeta_i\le-y\Big),
\tag 3.20
$$
where the $\zeta_i$-s are i.i.d. random variables with
distribution:
$$
\bold P\Big(\zeta_i=x\Big)=P(0,x).
\tag 3.21
$$
Now using the explicit form of the distribution $P(0,x)$ we find
that
$$
\forall\alpha\in\Bbb R:\qquad
\sum_{x\in\Bbb Z}P(0,x)\text{e}^{\alpha x}<\infty,
\tag 3.22
$$
and
$$
\sum_{y\in\Bbb Z}P(0,x)x<0
\tag 3.23
$$
for any $\lambda\in(0,1)$. From (3.20), (3.21), (3.22) and (3.23)
follows that, if $y\ge0$
$$
\bold E\Big(\text{e}^{C_4\theta_-}\Big|\!\!\Big|\eta_0=y\Big)
\le \text{e}^{\beta y}
\tag 3.24
$$
with some $C_4>0$ and $\beta<\infty$.

(3.10), with $C_2=\min\{C_3,C_4\}$,  follows from (3.13),
(3.18), (3.22) and (3.24).
 \hfill \hfill \qed
\enddemo

The next lemma establishes an over-exponential bound on the rate
of decay of the tails of the distributions $P^k(0,\cdot)$,
uniform in $k$. This bound is much stronger than what we
actually need in the proof of the Theorem.

\proclaim{Lemma 2}
There exists a constant $C_5<\infty$ such that for any $k\ge0$
and $x\ge0$
$$
P^k(0,x+1)\le C_5\lambda^xP^k(0,x).
\tag 3.25
$$
\endproclaim

\noindent
{\sl Remark:\/} A similar bound can be established for the left
tail of the distributions, too, but we do not need it in the
proof of the Theorem.

\demo{Proof}
We prove the lemma by induction on $k$ and $x$. (3.25) clearly
holds for $k=0$ and any $x\ge0$. As, due to (3.1), (3.2) and
(3.3)  $\lim_{k\to\infty}P^k(0,1)/P^k(0,0)=\lambda^3<\infty$,
$$
C_5=\sup_{k\ge0}\frac{P^k(0,1)}{P^k(0,0)}<\infty.
\tag 3.26
$$
Thus, (3.25) holds for $\forall k\ge0$ \ and $x=0$. We proceed
now by induction. Given an arbitrary probability distribution $r$ on
$\Bbb Z$ the following identity holds:
$$
\big[rP\big](x+1)=\frac{p(x+1)}{q(x+1)}q(x+2)\big[rP\big](x)+
q(x+2)r(x+2).
\tag 3.27
$$
Assume (3.25) holds for $(k,x+1)$ and for $(k+1,x)$. Using
(3.27) we get
$$
\align
P^{k+1}(0,x+2)
&=\frac{p(x+2)}{q(x+2)}q(x+3)P^{k+1}(0,x+1)+q(x+3)P^k(0,x+3)
\\
&\le\frac{p(x+2)}{q(x+2)}q(x+3)C_5\lambda^xP^{k+1}(0,x)+
q(x+3)C_5\lambda^{x+2}P^k(0,x+2)
\\
&=C_5\lambda^{x+1}\frac{\lambda q(x+3)}{q(x+2)}\left[
\frac{p(x+1)}{q(x+1)}q(x+2)P^{k+1}(0,x)+
q(x+2)P^k(0,x+2)\right]
\\
&=C_5\lambda^{x+1}\frac{\lambda q(x+3)}{q(x+2)}P^{k+1}(0,x+1).
\tag 3.28
\endalign
$$
Since
$$
\frac{\lambda q(x+3)}{q(x+2)}=
\frac{\lambda(1+\lambda^{2x+5})}{1+\lambda^{2x+7}}<1,
\tag 3.29
$$
(3.28) yields (3.25) for $(k+1,x+1)$.\hfill\hfill\qed
\enddemo

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bigskip
\noindent
{\bf 4. General Formulation and Proofs}

\medskip
In the proofs we use only some of the qualitative features
(formulated in the lemmas of the previous section) and not the
explicit form of the transition probabilities of the random walk
$S_n(\cdot)$. We are going to formulate our main Theorem in
these more general terms.

Let
$$
S_n(t)=\sum_{s=1}^t\xi_n(s)
\tag 4.1
$$
be a space-time inhomogeneous random walk on $\Bbb Z_+$ with the
following law:
$$
\bold P\Big(\xi_n(t+1)=x\Big|\!\Big|S_n(t)=k\Big)=
\pi_n(x|k,t)
\tag 4.2
$$
$$
\sum_{x\ge-k}\pi_n(x|k,t)=1.
\tag 4.3
$$
{\sl Remark:\/} Compare (4.2), (4.3) with (2.13).
The time inhomogeneity and dependence on $n$ of the law of the
random walk is just a nuisance we have to live with. As all the
estimates below will be uniform in $t$ and $n$ this will cause
no real trouble. All the constants arising in various
inequalities below are absolute constants not depending on $n$
or $t$.

We assume the following behaviour of the step distributions
$\pi_n(\cdot|k,t)$: \newline
(1) The step distributions $\pi_n(\cdot|k,t)$ converge in
$\ell_1(\Bbb Z)$, uniformly in $n$ and $t$, exponentially fast
as $k\to\infty$, to an asymptotic distribution $\pi$:
$$
\sum_{x\in\Bbb Z}\left|\pi_n(x|k,t)-\pi(x)\right|<C_1\exp(-C_2k).
\tag 4.4
$$
The asymptotic distribution is symmetric$$
\pi(-x)=\pi(x),
\tag 4.5
$$
and its moments of any order are assumed finite. We
denote by $\sigma^2$ its variance:
$$
\sum_{x\in\Bbb Z}x^2\pi(x)=\sigma^2\in(0,\infty).
\tag 4.6
$$
{\sl Remark:\/} (4.4), (4.5) and the moment conditions should be
compared with (3.3) and the explicit form (3.1). The symmetry
condition (4.5) is not really needed,
$\sum_{x\in\Bbb Z}x\pi(x)=0$ would be sufficient. We assume
(4.5) only for shortening the argument (see the observation
after (4.28) and the rightmost inequality in (A.2)).
\newline
(2) The tails of the distributions $\pi_n(\cdot|k,t)$ are
exponentially
bounded, uniformly in $k,\,\,t$ and $n$, i. e. there are two
constants $C_6<\infty,\,\,\,C_7>0$ such that
$$
\pi_n(x|k,t)\le C_6\exp(-C_7|x|).
\tag 4.7
$$
For technical purposes we assume even more about the decay of
the right tail of the distributions $\pi_n(\cdot|k,t)$: there is
an $x_0\in\Bbb Z$ \ independent of $k,\,\,t$ or $n$ such that for
$x\ge x_0$:
$$
\pi_n(x+1|k,t)<\text{e}^{-C_7}\pi_n(x|k,t).
\tag 4.8
$$
{\sl Remark:\/} Compare (4.7) with (3.6) and (4.8) with
(3.25). \newline
(3) The random walk is not trapped in a bounded domain or in a
domain away from the origin. There is a constant $C_8>0$
independent of $t$ or $n$ such that
$$
\align
&\forall\,\, k\ge0:\quad\sum_{x>0}\pi_n(x|k,t)>C_8>0.
\tag 4.9
\\
&\forall\,\, k >0: \quad\sum_{x<0}\pi_n(x|k,t)>C_8>0.
\tag 4.10
\endalign
$$
The $\omega$-stopping-time of the random walk $S_n(\cdot)$ is
$$
\omega_n=\inf\{t\ge n: S_n(t)=0\}.
\tag 4.11
$$
Denote by  $\theta_{I}$  the exit time from the interval $I
\in \Bbb Z_+$
$$
\theta_{I}=\min\{t\ge 0:S_n(t)\not\in I\}.
\tag 4.12
$$

\proclaim{Lemma 3} ({\it i.}) There exists a constant $C_9>0$,
such that  for any $0\le a< k< b$ in $\Bbb Z_+$
$$
\bold P\Big(S_n(\theta_{(a,b)})\ge b\Big|\!\Big|S_n(0)=k\Big)
>C_9\frac{k-a}{b-a},
\tag 4.13
$$
and for any $0\le a< k< b$ in $\Bbb Z_+$
$$
\bold P\Big(S_n(\theta_{(a,b)})\le a\Big|\!\Big|S_n(0)=k\Big)
>C_9\frac{b-k}{b-a}.
\tag 4.14
$$
({\it ii.}) There exists a constant $C_{10}>0$, such that  for any
$0\le k< b$ in $\Bbb Z_+$
$$
\bold E\Big(\theta_{[0,b)}\Big|\!\Big|S_n(0)=k\Big)
<C_{10}b^3.
\tag 4.15
$$
\endproclaim

\noindent
Since the proof of this lemma is a rather standard application of
submartingale techniques and the optional sampling theorem, (see
[Br]), and has no relevance to the rest of the proofs, we
postpone its sketch  to the Appendix. We should remark
here, that in (4.15) a better bound \ $\sim\!b^2$ \ can be proved
with some more work. However this bound is sufficient for our
purposes.

\proclaim{Proposition 2}
$$
\omega_n<\infty
\tag 4.16
$$
almost surely.
\endproclaim
\demo{Proof} Given Lemma 3 ({\it i.}), (4.14), this is evident.
This statement also completes the proof of Proposition 1.
\hfill\hfill \qed
\enddemo

The following theorem is the natural  general formulation of
Theorem 1:

\proclaim{Theorem 2}
Under the conditions 1, 2 and 3
$$
\left(
\frac{\omega_n}{n},
\frac{S_n([ns])}{\sigma\sqrt n}: 0\le s\le\infty
\right)
\Rightarrow
\left(
\omega, \left|W_{s}\right|:0\le s\le\infty
\right)
\tag 1.17
$$
in $\Bbb R_+\times D[0,\infty)$, where $\sigma^2$ is the
variance of the asymptotic step distribution given in (4.6).
\endproclaim

The outline of the proof is quite simple: due to the exponential
convergence of the step distributions, in the domain above the
threshold
$$
b_n=[n^{\epsilon}]
\tag 4.18
$$
the trajectory will be that of a
homogeneous random walk with step distribution $\pi$, with very
high probability. On the other hand, with help of Lemma 3 ({\it
ii.}), we prove that the total
amount of time spent below the threshold $b_n$ will be rather
small, of order $o(n^{1/2+5\epsilon})$ in a time interval of
order $n^{1+\epsilon}$, with overwhelming
probability. Joining these two arguments we couple a reflected
homogeneous random walk, $Y_n(\cdot)$, with step distribution
$\pi$ to our original random walk $S_n(\cdot)$ so that the
difference of their $\omega$-stopping-times is of order
$o(n^{1/2+5\epsilon})$ and the supremum distance of the two
processes is of order $o(n^{1/4+3\epsilon})$, with probability
converging to 1.

\demo{Proof of Theorem 2}
({\it i.})
Due to (4.4) we can couple to our random walk $S_n(\cdot)$ a
sequence
of  i.i.d. random variables  $\zeta_n(t),\,\,\, t=1,2,\dots$, with
distribution $\pi$, so that
$$
\bold P\Big(\zeta_n(t+1)\not=\xi_n(t+1)\Big|\!\Big|
S_n(t)=k\Big)<C_1\exp(-C_2k).
\tag 4.19
$$
We denote by $\sigma_n(t)$ the amount of time spent above the
threshold level $b_n$, before $t$:
$$
\sigma_n(t)=\#\{0\le s<t:S_n(s)>b_n\},
\tag 4.20
$$
and define the following sequence of sampling times:
$$
\matrix\format\l&\l\\
\tau_n(-1)&=-1
\\
\tau_n(t) &=\min\{s>\tau_n(t-1): S_n(s)>b_n\},\qquad 0\le
t<\infty.
\endmatrix
\tag 4.21
$$
$\tau_n$ is the inverse function of $\sigma_n$ in the sense that
$$
\sigma_n\left(\tau_n(t)\right)=t
\quad\text{ for }\quad 0\le t<\infty.
\tag 4.22
$$
Let
$$
\tilde\xi_n(t)=\xi_n(\tau_n(t-1)+1)
\tag 4.23
$$
and
$$
\tilde\zeta_n(t)=\zeta_n(\tau_n(t-1)+1).
\tag 4.24
$$
As the $\tilde\zeta_n$-s are selected according to an increasing
sequence of sampling times they are still i.i.d. random
variables with the common distribution $\pi$. On the other hand,
due to (4.19)
$$
\forall t\in\Bbb N:\qquad
\bold P\Big(\tilde\xi_n(t)\not=\tilde\zeta_n(t)\Big)<
C_1\exp(-C_2n^\epsilon).
\tag 4.25
$$
We define two `truncated' processes $\tilde S_n(\cdot)$ and
$\tilde Y_n(\cdot)$:
$$
\align
&\tilde S_n(0)=0,\quad
\tilde S_n(t)=\Big(\tilde S_n(t-1)+\tilde\xi_n(t)\Big)\bigvee0,
\tag 4.26
\\
&\tilde Y_n(0)=0,\quad
\tilde Y_n(t)=\Big(\tilde Y_n(t-1)+\tilde\zeta_n(t)\Big)\bigvee0.
\tag 4.27
\endalign
$$
And finally, let the random walk $Y_n$ be defined as follows:
$$
Y_n(0)=0,\quad
Y_n(t)=\left|Y_n(t-1)+\tilde\zeta_n(t)\right|.
\tag 4.28
$$
Due to the symmetry of the distribution $\pi$, $Y_n(\cdot)$ is a
homogeneous random walk reflected at the origin, and $\tilde
Y_n(\cdot)$ differs from $Y_n(\cdot)$ only by the cutoffs of the
overshootings of the origin: using the constructions (4.27) and
(4.28) one can easily check
$$
0\le Y_n(t)-\tilde Y_n(t)\le \max_{0\le s\le
t}\left|\tilde\zeta_n(s)\right|.
\tag 4.29
$$
We also need the $\omega$-stopping times of the processes $\tilde
Y_n(\cdot)$ and $Y_n(\cdot)$:
$$
\align
\omega^{\prime}_n&=\inf\{t\ge n: \tilde Y_n(t)=0\},
\tag 4.30
\\
\omega^{\prime\prime}_n&=\inf\{t\ge n: Y_n(t)=0\}.
\tag 4.31
\endalign
$$
The standard invariance principle holds for $Y_n(\cdot)$
(see [Bi], [L]), and consequently:
$$
\left(
\frac{\omega^{\prime\prime}}{n},
\frac{Y_n([ns])}{\sigma\sqrt{n}}: 0\le s<\infty
\right)
\Rightarrow
\left(
\omega,\left|W_s\right|: 0\le s<\infty
\right)
\quad \text{ in } \quad \Bbb R\times D[0,\infty).
\tag 4.32
$$
Due to the closeness of the $\tilde Y_n(\cdot)$ and $Y_n(\cdot)$
paths, (4.29), the same convergence in distribution is easily
proved for the process $\tilde Y_n(\cdot)$:
$$
\left(
\frac{\omega^{\prime}}{n},
\frac{\tilde Y_n([ns])}{\sigma\sqrt{n}}: 0\le s<\infty
\right)
\Rightarrow
\left(
\omega,\left|W_s\right|: 0\le s<\infty
\right)
\quad \text{ in } \quad \Bbb R\times D[0,\infty).
\tag 4.33
$$
We omit the details of this straightforward step.

We shall prove the Theorem by proving
$$
n^{-1/2}\max_{0\le t\le n^{1+\epsilon}}
\left|S_n(t)-\tilde Y_n(t)\right|
\buildrel{\bold P}\over{\to}0
\tag 4.34
$$
and
$$
n^{-1}\left|\omega_n-\omega^{\prime}_n\right|
\buildrel{\bold P}\over{\to}0.
\tag 4.35
$$
Consider first (4.34):
$$
\align
&
\max_{0\le t\le n^{1+\epsilon}}
\left|S_n(t)-\tilde Y_n(t)\right|\le
\max_{0\le t\le n^{1+\epsilon}}
\left|S_n(t)-\tilde S_n(\sigma_n(t))\right|+
\\
&\qquad\qquad
\max_{0\le t\le n^{1+\epsilon}}
\left|\tilde S_n(\sigma_n(t))-\tilde Y_n(\sigma_n(t))\right|+
\max_{0\le t\le n^{1+\epsilon}}
\left|\tilde Y_n(\sigma_n(t))-\tilde Y_n(t)\right|.
\tag 4.36
\endalign
$$
In order to estimate the three terms on the right hand side of
(4.36) we define the following events:
$$
\align
\Cal A_n&=\Big\{\max_{1\le t\le
n^{1+\epsilon}}\left|\xi_n(t)\right|<n^{\epsilon}\Big\}
\tag 4.37
\\
\Cal B_n&=\Big\{\tilde \xi_n(t)=\tilde \zeta_n(t),\,\,\,
0\le t\le n^{1+\epsilon}\Big\}
\tag 4.38
\\
\Cal C_n&=\Big\{n^{1+\epsilon}-\sigma_n(n^{1+\epsilon})<
n^{\frac12+5\epsilon}\Big\}
\tag 4.39
\\
\Cal D_n&=\Big\{\max\left\{\left|\tilde Y_n(s)-\tilde Y_n(t)\right|:
           0\le s,t\le n^{1+\epsilon},
           |s-t|<n^{\frac12+5\epsilon}\right\}
            <n^{\frac14+3\epsilon}
           \Big\}
\tag 4.40
\\
\Cal E_n&=\Big\{\#\left\{t: 0\le t\le n^{1+\epsilon},\,\,\,\tilde
Y_n(t)=0\right\}< n^{\frac12+\epsilon}\Big\}.
\tag 4.41
\endalign
$$
By construction of the process $\tilde S_n(\cdot)$  we have
$$
0\le S_n(t)-\tilde S_n(\sigma_n(t))\le
b_n+\max_{0\le s\le t}\xi_n(s).
\tag 4.42
$$
So the first term on the right hand side of (4.36) is easily
evaluated:
$$
\bold P\Big(\max_{0\le t\le n^{1+\epsilon}}\left|S(t)-\tilde
S_n(\sigma_n(t))\right|<
2n^{\epsilon}\Big)\ge\bold P\Big(\Cal A_n\Big)\to1
\tag 4.43
$$
as $n\to\infty$.
The convergence on the right hand side of (4.43) is due to the
uniform bound (4.7) on the decay of the tails of step
distributions.

The second term on the right hand side of (4.36) is even simpler:
$$
\bold P\Big(\max_{0\le t\le n^{1+\epsilon}}
\left|\tilde S_n(\sigma_n(t))-\tilde Y_n(\sigma_n(t))\right|=0\Big)\ge
\bold P\Big(\Cal B_n\Big)\to 1
\tag 4.44
$$
as $n\to\infty$,
due to the exponential closeness (4.25).

To estimate the last term, notice that
$$
\Cal C_n\cap\Cal D_n\subset
\Big\{\max_{0\le t\le n^{1+\epsilon}}
\left|\tilde Y_n(\sigma_n(t))-\tilde Y_n(t)\right|
<n^{\frac14+3\epsilon}\Big\},
\tag 4.45
$$
so the estimates
$$
\align
&\bold P\Big(\Cal C_n\Big)\to1
\tag 4.46
\\
&\bold P\Big(\Cal D_n\Big)\to1
\tag 4.47
\endalign
$$
as $n\to\infty$, is still wanted. (4.47) and
$$
\bold P\Big(\Cal E_n\Big)\to1
\tag 4.48
$$
as $n\to\infty$,  are well established facts about homogeneous
random walks.
The proof of (4.47) is based on an adaptation of the
method of proof of Theorem 8.3 of [Bi] (the finiteness of high
moments of the distribution $\pi$ is needed here). The estimate
(4.48) of the number of visits to the origin of the random walk
$\tilde Y_n(\cdot)$ is an easy exercise. As the proofs of (4.47)
and (4.48)  are quite standard, we do not give the details here.

Finally
$$
\bold P\Big(\Cal C_n\Big|\!\Big|\Cal E_n\cap\Cal B_n\Big)\to
1\quad
\text{ as } \quad n\to\infty.
\tag 4.49
$$
is a consequence of Lemma 3 ({\it ii.}), (4.15): notice that in
$\Cal E_n\cap\Cal B_n$ there are altogether less than
$n^{\frac12+\epsilon}$ visits  of $S_n(t),\,\,\,0\le t\le
n^{1+\epsilon}$ to the interval $[0,b_n)$ and Lemma 3 ({\it
ii.}) provides an upper bound on the expectation of the duration
of each of these visits. In consequence, the conditional
expectation of the total time spent below the threshold level
$b_n$ is bounded like
$$
\bold E\Big(n^{1+\epsilon}-\sigma_n(n^{1+\epsilon})\Big|\!\Big|
\Cal E_n\cap\Cal B_n\Big)\le
n^{\frac12+\epsilon}
\max_{0\le k\le b_n}\bold E\Big(\theta_{[0,b_n]}
\Big|\!\Big|S(0)=k\Big)\le
C_{10}n^{\frac12+4\epsilon}.
\tag 4.50
$$
Hence (4.49), via Markov's inequality.

(4.43), (4.44), (4.46), (4.47), (4.48)  and (4.49)  imply (4.34).

In order to prove (4.35) we have to define two more events:
$$
\align
\Cal F_n&=\Big\{\omega^{\prime}_n<\frac{n^{1+\epsilon}}{2}\Big\}
\tag 4.51
\\
\Cal G_n&=\Big\{\omega^{\prime}_n<\omega_n\Big\}.
\tag 4.52
\endalign
$$
>From the weak convergence of (4.33) of $\omega^{\prime}_n/n$
clearly follows
$$
\bold P\Big(\Cal F_n\Big)\to 1,
\tag 4.53
$$
as $n\to\infty$.
To prove
$$
\bold P\Big(\Cal G_n\Big)\to 1
\tag 4.54
$$
as $n\to\infty$, notice that, by construction of $\tilde
S_n(\cdot)$, $\tilde S(\sigma_n(\omega_n))=0$ and consequently,
on $\Cal B_n$ \ $\tilde Y(\sigma_n(\omega_n))=0$, too. Thus, either
$\omega^{\prime}_n\le\sigma_n(\omega_n)<\omega_n$ or
$\sigma_n(\omega_n)\le n<\omega_n$. The first of these
alternatives implies $\Cal G_n$, from the second alternative
follows
$$
\Cal G_n^{\text{c}}\cap\Cal B_n\cap\Cal C_n\cap\Cal D_n\cap\Cal
F_n\subset \Big\{\tilde Y_n(n)<n^{\frac14+3\epsilon}\Big\}.
\tag 4.55
$$
But, due to the weak convergence (4.33), the probability of this
event clearly goes to zero, as $n\to\infty$. Hence (4.54).

Note that, using identity (4.22)
$$
S(\tau_n(\omega^{\prime}_n))=
S_n(\tau_n(\omega^{\prime}_n))-\tilde Y_n(\omega^{\prime}_n)=
S_n(\tau_n(\omega^{\prime}_n))-
\tilde Y_n(\sigma_n(\tau_n(\omega^{\prime}_n))).
\tag 4.56
$$
Thus, due to (4.43) and (4.44), on
$\Cal A_n\cap\Cal B_n\cap\Cal C_n\cap\Cal F_n$ we have
$$
S_n(\tau_n(\omega^{\prime}_n))\le
2 n^{\epsilon}.
\tag 4.57
$$
>From Lemma 3 ({\it i.}) and ({\it ii.}), (4.14) and (4.15),
easily follows, that
$$
\bold P\Big(
\theta_{(0,\infty)}<n^{7\epsilon}\Big|\!\Big|
S_n(0)\le 2n^{\epsilon}
         \Big)\to 1
\tag 4.58
$$
as $n\to\infty$. Note that $\theta_{(0,\infty)}$ is the hitting
time of $0\in\Bbb Z_+$. We conclude, that
$$
\bold P\Big(
\omega_n-\omega^{\prime}_n<2n^{\frac12+5\epsilon}
        \Big|\!\Big|
\Cal A_n\cap\Cal B_n\cap\Cal C_n\cap\Cal F_n\cap\Cal G_n
         \Big)\to 1
\tag 4.59
$$
as $n\to\infty$, which, given (4.43), (4.44), (4.48), (4.49),
(4.53) and (4.54), proves (4.35).
\hfill\hfill \qed
\enddemo

Given the explicit form (2.13) of the transition probabilities
and Lemmas 1 and 2 of section 3, Theorem 1 becomes simply a
concrete case of Theorem 2.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bigskip
\noindent
{\bf Appendix: Proof of Lemma 3.}

\medskip
The proof of (4.13), (4.14) and (4.15) is standard
application of submartingale technique and the optional sampling
theorem (see [Br]), we only sketch the main steps.\newline
({\it i.})
Conditions (4.4), (4.5) and (4.7) imply
$$
\left|\sum_{x\in\Bbb Z}\pi_k(x)x\right|<C_{11}\exp(-C_{12}k)
\tag A.1
$$
with $C_{11}<\infty$ and $C_{12}=C_2/2$, and
$$
\liminf_{k\to\infty}\sum_{x\in\Bbb Z}\pi_k(x)\text{e}^{-C_{12}x}\ge
\sum_{x\in\Bbb Z}\pi(x)\text{e}^{-C_{12}x}>1.
\tag A.2
$$
Here once again we used the symmetry (4.5) of the distribution
$\pi$.
Due to (A.2) we can choose $a_1\in\Bbb Z_+$ and a finite constant
$C_{13}<\infty$ such that for $k\ge a_1$
$$
C_{13}\left(\sum_{x\in\Bbb
Z}\pi_k(x)\text{e}^{-C_2x}-1\right)\ge C_{11}.
\tag A.3
$$
It is straightforward to check that from (A.3) and (A.1)
follows that both
$$
\pm S(t)+C_{13}\exp(-C_{12} S(t)),\qquad 0\le t\le
\theta_{(a_1,\infty)}
\tag A.4
$$
are submartingales.

To prove (4.13) notice first that due to the strong
exponential bound (4.8) on the decay rate of
the right tails, for any $k\in(a,b)\subset\Bbb Z_+$
$$
\bold E\Big(S(\theta_{(a,b)})\Big|\!\Big|
[S(0)=k]\land[S(\theta_{(a,b)})\ge b]\Big)\le
(b+C_{13})
\tag A.5
$$
with some $C_{13}<\infty$. Let $a_2=\max\{a_1, C_{13}\}$. For
$a_2\le a<b$ consider the submartingale
$$
S(t)+C_{13}\exp(-C_{12}S(t))-\left[a+C_{13}\exp(-C_{12}a)\right],
\qquad 0\le t\le \theta_{(a,b)},
\tag A.6
$$
then
$$
\align
&
k+C_{13}\text{e}^{-C_{12}k}-\left[a+C_{13}\exp(-C_{12}a)\right]
\le
\\
&
\bold E\Big(
S(\theta_{(a,b)})+C_{13}\text{e}^{-C_{12}S(\theta_{(a,b)})}-
\left[a+C_{13}\exp(-C_{12}a)\right]\Big|\!\Big|S(0)=k\Big)\le
\\
&\qquad\qquad
(b+C_{13}+C_{13}-a)
\bold P\Big(S(\theta_{(a,b)})>b\Big|\!\Big|S(0)=k\Big)
\tag A.7
\endalign
$$
which implies (4.13) with some constant $C_{15}>0$ for
$a_2\le a< k< b$.
Changing the constant $C_{15}$ to a smaller one
$$
C_9=
\min_{0\le a^{\prime}<a_2}\min_{a^{\prime}< k^{\prime}\le a_2}
\bold P\Big(S(\theta_{(a^{\prime},a_2]})> a_2
\Big|\!\Big|S(0)=k^{\prime}\Big)
C_{15}>0
\tag A.8
$$
the  inequality extends to any $0\le a< k< b$ and (4.13) is
proved.

(4.14) is proved in a very similar way
considering now the submartingale
$$
-S(t)+C_{13}\exp(-C_{12}S(t))-\left[-b+C_{13}\exp(-C_{12}b)\right],
\qquad 0\le t\le \theta_{(a,b)},
\tag A.9
$$
with $a_1\le a<b\le\infty$.
We do not repeat the same arguments.\newline
({\it ii.})
(4.4) and (4.9) imply
$$
0<\underline\sigma^2\le\sum_{x\in\Bbb Z}\pi_k(x)|x|^2
\tag A.10
$$
Choose now $a_4\in\Bbb Z_+$ so that for $k\ge a_4$
$$
2kC_{11}\exp(-C_{12}k)<\frac{\underline\sigma^2}{2}.
\tag A.11
$$
Then, in the domain $k>a_4$ we have
$$
\bold E\Big(S^2(t+1) - \frac{\underline\sigma^2}{2}(t+1)
\Big|\!\Big| S(t)=k\Big)\ge k^2-\frac{\underline\sigma^2}{2}t
\tag A.12
$$
and consequently
$$
S^2(t)-\frac{\underline\sigma^2t}{2}, \qquad
t=0,1,\dots,\theta_{(a_4,b)}
\tag A.13
$$
is a submartingale.
Hence
$$
\bold E\Big(S^2(\theta_{(a_4,b)})-
\frac{\underline\sigma^2}{2}\theta_{(a_4,b)}
\Big|\!\Big|S(0)=k\Big) \ge k^2.
\tag A.14
$$
>From (4.8), similarly to (A.5), we get
$$
\bold E\Big(S^2(\theta_{(a,b)})\Big|\!\Big|
[S(0)=k]\land[S(\theta_{(a,b)})>b]\Big)\le
(b+C_{16})^2.
\tag A.15
$$
(A.14) and (A.15) imply
$$
\frac{\underline\sigma^2}{2}\bold E\Big(\theta_{(a_4,b)}
\Big|\!\Big|S(0)=k\Big) \le (b+C_{16})^2,
\tag A.16
$$
and, finally  (4.13) and (A.16) lead directly to
$$
\bold E\Big(\theta_{[0,b)}\Big|\!\Big|S(0)=k\Big) \le
C_9^{-1}b\left(\max_{0\le k^{\prime}\le a_4}
\bold E\Big(\theta_{[0,a_4]}\Big|\!\Big|S(0)=k^{\prime}\Big) +
\frac{4}{\underline\sigma^2}(b+C_{16})^2\right).
\tag A.17
$$
Due to the non-trapping condition (4.9)
$\max_{0\le k^{\prime}\le a_4}
\bold E\Big(\theta_{[0,a_4]}\Big|\!\Big|S(0)=k^{\prime}\Big)$ is
finite. Thus (A.17) proves (4.15).
\hfill\hfill\qed
\enddemo
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\bigskip
\newpage
\noindent
{\bf Acknowledgement:}
A very pleasant and instructive discussion with Erwin
Bolthausen, about self-repelling random walks, lead me to the
formulation of the problem. Helpful conversations with Endre
Cs\'aki and  P\'eter Major during the preparation of this work
are also gratefully acknowledged.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bigskip
\noindent
{\bf References}
\parindent=1.5cm
\item{[APP]} Amit, D., Parisi, G., Peliti, L.: Asymptotic
             behaviour of the `true' self-avoiding walk.
            {\sl Phys. Rev. B} {\bf 27} 1635-1645, (1983).
\item{[Bi]} Billingsley, P.: {\sl Convergence of Probability
           Measures.\/} J. Wiley \& Sons, New York, 1968.
\item{[Bo]} Bolthausen, E.: On self-repellent one-dimensional
            random walks. {\sl Probab. Th. Rel. Fields\/}
            {\bf 86} 423-441, 1990
\item{[Br]} Breiman., L.: {\sl Probability.\/}, Addison-Wesley,
            Reading, MA, 1968.
\item{[BS]} Brydges, D., Spencer, T.: Self-avoiding walk in 5
            or more dimensions. {\sl Commun. Math. Phys.\/}
            {\bf 97} 125-148 (1985).
\item{[CM]} Cs\'aki, E., Mohanty, S.G.: Excursion and meander in
            random walk. {\sl The Canadian J. of Stat.\/} {\bf
            9} 57-70, (1981)
\item{[D]}  Davis, B.: Reinforced random walk. {\sl Probab. Th.
           Rel. Fields.\/} {\bf 84} 203-229 (1990).
\item{[HS]} Hara, T., Slade, G.: The lace expansion for
           self-avoiding walk five and more dimensions. {\sl
            Reviews in Math. Phys.\/} {\bf 4} 235-327 (1992).
\item{[KKS]} Kesten, H., Kozlov, M.V., Spitzer, F.: A limit law
           for random walk in random environment. {\sl
           Compositio Mathematica\/} {\bf 30} 145-168, 1975.
\item{[K]} Knight, F.B.: Random walks and a sojourn density
           process of Brownian motion. {\sl Transactions of
           AMS\/} {\bf 109} 56-86, (1963)
\item{[L]} Lindwall, T: Weak convergence of probability measures
          and random functions in the function space
          $D[0,\infty)$. {\sl J. Appl. Probab.\/} {\bf 10} 109,
          1973.
\item{[N]} Nummelin, E.: {\sl General Irreducible Markov Chains
           and Non-Negative Operators.\/} Cambridge Univ. Press,
           1984.
\item{[P]} Pemantle, R.: Phase transition in reinforced random
           walk and RWRE on trees. {\sl The Annals of Probab.\/}
           {\bf 16} 1229-1242 (1988).
\medskip

\enddocument
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%