%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % This is a Plain TeX file %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \magnification=1200 \scrollmode \baselineskip 15pt \overfullrule=0pt \def\one{{\bf 1}\hskip-.5mm} \def\P{{I\kern-0.3emP}} \def\pa{{\P(A)}} \def\ta{{\tau_A}} \def\bbz{{Z\kern-0.45emZ}} \def\bbr{{I\kern-0.3emR}} \def\bbn{{I\kern-0.3emN}} \def\E{{I\kern-0.3emE}} %\def\mfu{(M, $ $ {\cal F}, $ $ \mu)} \def\ofp{(\Omega ,{\cal F}, \P)} \def\dyn{(T,{\cal V},\P )} \def\ea{{\P(A)^{1 \over 2}}} \def\today{\rightline{\ifcase\month\or January\or February\or March\or April\or May\or June\or July\or August\or September\or October\or November\or December\fi \space\number\day,\space\number\year}} \def \Sup{\mathop{\rm Sup}} %%% formule o figure che appaiono in altri file, purche' sia presente il %%% corrispondente file .aux; basta includere all'inizio l'istruzione %%% \include{nomefile} %%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \global\newcount\numsec\global\newcount\numfor \global\newcount\numfig \gdef\profonditastruttura{\dp\strutbox} \def\senondefinito#1{\expandafter\ifx\csname#1\endcsname\relax} \def\SIA #1,#2,#3 {\senondefinito{#1#2} \expandafter\xdef\csname #1#2\endcsname{#3}\else \write16{???? ma #1,#2 e' gia' stato definito !!!!} \fi} \def\etichetta(#1){(\veroparagrafo.\veraformula) \SIA e,#1,(\veroparagrafo.\veraformula) \global\advance\numfor by 1 % \write15{\string\FU (#1){\equ(#1)}} \write16{ EQ \equ(#1) == #1 }} \def\letichetta(#1){\veroparagrafo.\veraformula \SIA e,#1,{\veroparagrafo.\veraformula} \global\advance\numfor by 1 % \write15{\string\FU (#1){\equ(#1)}} \write16{ Sta \equ(#1) == #1}} \def\tetichetta(#1){\veroparagrafo.\veraformula %%%%copy four lines \SIA e,#1,{(\veroparagrafo.\veraformula)} \global\advance\numfor by 1 % \write15{\string\FU (#1){\equ(#1)}} \write16{ tag \equ(#1) == #1}} \def \FU(#1)#2{\SIA fu,#1,#2 } \def\etichettaa(#1){(A\veroparagrafo.\veraformula) \SIA e,#1,(A.\veroparagrafo.\veraformula) \global\advance\numfor by 1 % \write15{\string\FU (#1){\equ(#1)}} \write16{ EQ \equ(#1) == #1 }} \def\getichetta(#1){Fig. \verafigura \SIA e,#1,{\verafigura} \global\advance\numfig by 1 % \write15{\string\FU (#1){\equ(#1)}} \write16{ Fig. \equ(#1) ha simbolo #1 }} \newdimen\gwidth \def\BOZZA{ \def\alato(##1){ {\vtop to \profonditastruttura{\baselineskip \profonditastruttura\vss \rlap{\kern-\hsize\kern-1.2truecm{$\scriptstyle##1$}}}}} \def\galato(##1){ \gwidth=\hsize \divide\gwidth by 2 {\vtop to \profonditastruttura{\baselineskip \profonditastruttura\vss \rlap{\kern-\gwidth\kern-1.2truecm{$\scriptstyle##1$}}}}} } \def\alato(#1){} \def\galato(#1){} \def\veroparagrafo{\number\numsec}\def\veraformula{\number\numfor} \def\verafigura{\number\numfig} \def\geq(#1){\getichetta(#1)\galato(#1)} \def\Eq(#1){\eqno{\etichetta(#1)\alato(#1)}} \def\teq(#1){\tag{\tetichetta(#1)\hskip-1.6truemm\alato(#1)}} %%%%%this line \def\eq(#1){\etichetta(#1)\alato(#1)} \def\Eqa(#1){\eqno{\etichettaa(#1)\alato(#1)}} \def\eqa(#1){\etichettaa(#1)\alato(#1)} \def\eqv(#1){\senondefinito{fu#1}$\clubsuit$#1\else\csname fu#1\endcsname\fi} \def\equ(#1){\senondefinito{e#1}\eqv(#1)\else\csname e#1\endcsname\fi} %next six lines by paf (no responsibilities taken) \def\Lemma(#1){Lemma \letichetta(#1)\hskip-1.6truemm} \def\Theorem(#1){{Theorem \letichetta(#1)}\hskip-1.6truemm} \def\Proposition(#1){{Proposition \letichetta(#1)}\hskip-1.6truemm} \def\Corollary(#1){{Corollary \letichetta(#1)}\hskip-1.6truemm.} \def\Remark(#1){{\noindent{\bf Remark \letichetta(#1)\hskip-1.6truemm.}}} \let\ppclaim=\plainproclaim \let\EQS=\Eq\let\EQ=\Eq \let\eqs=\eq \let\Eqas=\Eqa \let\eqas=\eqa %%%%%%%%%%%%%%%%%% Numerazione verso il futuro ed eventuali paragrafi %%%%%%% precedenti non inseriti nel file da compilare \def\include#1{ \openin13=#1.aux \ifeof13 \relax \else \input #1.aux \closein13 \fi} \openin14=\jobname.aux \ifeof14 \relax \else \input \jobname.aux \closein14 \fi %\openout15=\jobname.aux %%%%%%%%%%%%%%%%%%%%%%%%%%%% %\BOZZA \hfill{March 5, 1997} \vskip 3truemm \centerline {\bf Inequalities for hitting times in mixing dynamical systems.} \vskip 2truemm \centerline { A. Galves} \centerline {\it Universidade de S\~ao Paulo} \centerline { B. Schmitt} \centerline {\it Universit\'e de Bourgogne} \vskip 4truemm \noindent {\bf Summary.} We prove that a hitting time of a mixing dynamical system can be sharply approximated by an exponential random variable. More precisely, we prove that there exists four strictly positive constants $ {\Lambda}_1, {\Lambda}_2, \beta $, and $C$, such that, if $A$ is a cylinder and $\ta$ is the first time the system visits $A$, then the following uniform upper bound holds $$ \sup_{t > 0} \left\vert \P\left\{\ta > {t \over {\lambda(A) \pa}}\right\} - e^{\displaystyle{- t}} \right\vert \le C \P(A)^{\beta} \ , $$ where $\pa$ is the probability of $A$ and $ \lambda(A) \in \left[\Lambda_1, \Lambda_2 \right]$. \vskip 4truemm \noindent {\sl Keywords.} Mixing dynamical systems, occurrence time of a rare event, exponential law. \vskip 1truemm \noindent {\sl AMS 1991 classification numbers.} 58F08, 58F11, 60F05, 60F10. \vskip 4truemm \noindent {\bf 1. Introduction.} \vskip 2truemm \numsec=1\numfor=1 In this article we obtain a sharp upper bound for the approximation of the law of a hitting time in a mixing dynamical system. We prove that for any cylinder set $A$, the law of its hitting time suitably rescaled, can be uniformly approximated by a mean one exponential law. The distance between the two laws is bounded above by $C{\pa}^{\beta}$, where $\pa$ is the probability of $A$, and $C$ and $\beta$ are two strictly positive constants, independent of $A$. Moreover, we show that the right scaling factor can be written as $\lambda(A) \pa$, where $\lambda(A)$ is bounded below and above by two strictly positive constants $\Lambda_1$ and $\Lambda_2$, respectively, independent of $A$. The pioneer paper in this area is Doeblin (1940), who studied the Poisson approximation for the Gauss transformation. In the context of Markov chains, the convergence of the occurrence time of a rare event to the exponential law was first studied by Bellmann and Harris (1951) and Harris (1953). Then after a long period in which apparently nothing appeared in the area, several papers and books studying the problem for different types of Markov processes were published, starting with Keilson (1979), Aldous (1982), Korolyuk and Sil'vestrov (1984), Cassandro, Galves, Olivieri and Vares (1984), Kipnis and Newman (1985), Cogburn (1985), Lebowitz and Schonmann (1987), among others. Let us quote also two recent papers by Olivieri and Scoppola 1995 and 1996 who present a very elegant treatment of the problem in the context of Markov processes. In the context of dynamical systems the question was considered by Galves and Schmitt (1990), Collet, Galves and Schmitt (1992), Collet and Galves (1993) and (1995). Part of these papers were motivated by the modeling of physical phenomena like metastability or intermittency. In any case, with the exception of Aldous (1982), all the others are only interested in a qualitative result, and don't present sharp upper bounds for the rate of convergence to the exponential law. Recently this was done for reversible and finite Markov chains by Aldous and Brown (1992,1993) and for some interacting Markovian systems by Ferrari, Galves and Landim (1994) and Ferrari, Galves and Liggett (1995). In the present paper, we extend to the non Markovian framework of general mixing dynamical systems, the approach developed in this last paper. This paper is organized as follows. In section 2 we give the definitions and state the main theorem. In sections 3 and 4 we present the lemmata which are used in the proof of the theorem. This proof is given in section 5. \vskip 4truemm \noindent {\bf 2. Definitions and main result.} \vskip 2truemm \numsec=2\numfor=1 Let $\ofp$ be a probability space and $T:\Omega \rightarrow \Omega$ a measurable transformation leaving $\P$ invariant. Let us suppose that the $\sigma$-field $\cal F$ is generated by a finite $\cal F$-measurable partition ${\cal V} =(V_1, \ldots, V_a)$, {\sl i.e.} ${\cal F} =\vee_{n \ge 0}{{\cal F}_n}$, where ${\cal F}_{n} = \vee_{k = 0}^{n-1}{T^{-k}(\cal V)}$. We shall assume that the partition ${\cal V}$ does not contain atoms $V_i$ of probability 0 or 1. A set $A \in {\cal F}_{n}$ is said a {\sl cylinder} of length $n$ relatively to $\cal V$, if $$ A = V_{i_0}\cap T^{-1}(V_{i_1})\cap T^{-2}(V_{i_2}) \cap{\cdots} \cap T^{-(n-1)}(V_{i_{n-1}}) \ , $$ for some sequence $(i_0, i_1, \ldots, i_{n-1}) \in \{1, 2, \ldots, a \}^n$. Let us denote by ${\cal C}_n$ the set of all the $n$-{\sl cylinders}. Let $\phi =(\phi(l))_{l \ge 1}$ be a decreasing sequence of positive real numbers. We shall say that the triplet $\dyn$ is $\phi$-{\sl-mixing} if, for all integers $n \ge 1$ and $l \ge 1$, the following inequality holds $$ \sup_{B \in {\cal F}_n, C \in {\cal F}}{{\left|\P(B \cap T^{-(n+l)}(C))- \P(B)\P(C)\right|}\over{\P(B)\P(C)}} \le {\phi(l)} \ , \Eq(fimix) $$ where in the above expression the supremum is taken over the sets $B$ and $C$, such that $\P(B)\P(C)>0$. Given $A \in {\cal F}$, we define the {\sl entrance time} $\ta: \Omega \rightarrow \bbn$ as follows. For any $\omega \in \Omega$ $$ \ta(\omega) = \inf\{k \ge 0 : T^k(\omega) \in A \} \ . \Eq(entr) $$ The entrance time $\ta$ is a {\sl random variable} defined on the probability space $\ofp$. We recall that the mixing property \equ(fimix) and the ergodic theorem imply that if $\P(A) > 0$, then $\ta$ is $P$-almost surely finite. In the sequence we shall use the standard probabilistic shorthand notation for events defined through random variables. We shall write $\{\ta = m \}$ instead of $\{\omega \in \Omega : \ta(\omega) = m \}$. We shall also write $\{T^k \in A \}$ instead of $\{\omega \in \Omega : T^k(\omega) \in A \}=T^{-k}(A)$. As usual, the mean of a random variable $X$ will be called its {\sl expectation} and denoted by $\E(X)$. We may now state our main result. \vskip 2truemm \noindent{\bf Theorem.} Let $\dyn$ be $\phi$-mixing and let us suppose that the function $\phi:{\bbn}\rightarrow {\bbr}_{+}$ is summable. Then, there exist four strictly positive constants $ {\Lambda}_1, {\Lambda}_2, \beta, C$, such that for any $n$ and any $A \in {\cal C}_n$, there exists $ \lambda(A) \in \left[\Lambda_1, \Lambda_2 \right] $, for which the following inequality holds $$ \sup_{t > 0}\left\vert \P\left\{\ta > {t \over {\lambda(A) \pa}}\right\} - e^{\displaystyle{- t}}\right\vert \le C \P(A)^{\beta} \ . \Eq(mt) $$ \vskip 2truemm \noindent{\bf Remark.} We emphasize the fact that the constants $ {\Lambda}_1, {\Lambda}_2, \beta$, and $C$ are independent of $n$ and $A$. \vskip 4truemm \noindent {\bf 3. Estimates on the probability of a cylinder.} \vskip 2truemm \numsec=3\numfor=1 In what follows we shall always assume that $\dyn$ is $\phi$-mixing, with $\phi$ summable, and that the generating partition $\cal V$ does not contains atoms $V_i$ of probability $0$ or $1$. \vskip 2truemm \noindent {\bf Lemma 1.} There exist three strictly positive constants $c$, $\bar c$, and $\gamma$, such that for any fixed positive integer $n$ and any $A\in {\cal C}_n$ the following inequalities hold $$ \pa \le ce^{\displaystyle{-\gamma n}} \Eq(exp) $$ and $$ \sum^n_{k=1}\P\left( A \cap T^{-k}A \right) \le {\bar c} \pa \ .\Eq(inter) $$ \vskip 2truemm \noindent{\bf Proof.} By definition, any $A\in {\cal C}_n$ can be written as $$ A= \bigcap^{n-1}_{j=0}T^{-j}V_{i_j} \ , $$ for a suitable choice $V_{i_0},\cdots, V_{i_{n-1}}$ of atoms in $\cal V$. Therefore for any $n_0$ and any $n > n_0$, we have the inequality $$ \pa \le \P\left (V_{i_0} \cap T^{-n_0}V_{i_{n_0}}\cap \cdots \cap T^{-[{n\over n_0}]n_0}V_{i _{[{n\over n_0}]n_0}} \right)\ . \Eq(ineq) $$ Using the $\phi$-mixing property in the right hand side of \equ(ineq), we get $$ \P(A) \leq \left[ (1+\phi (n_0))\rho \right] ^{[{n\over n_0}]+1} \ , \Eq(lb) $$ where $$ \rho =\sup\{\P(V_i) : i=1, \ldots, a \}. \Eq(rho) $$ Since, by hypothesis, $\rho < 1$ and the series $\sum_{l= 1}^{+\infty}\phi(l)$ is convergent, there exists an integer $n_0$ such that $$ (1+\phi (n_0))\rho <1\ . $$ This concludes the proof of \equ(exp). \vskip 2truemm To prove \equ(inter), we first observe that $$ \P(A \cap T^{-k} A) \le \P\left(A \cap T^{-n}C^{(n)}_k \right) \ , $$ where $$ C^{(n)}_k = \bigcap^{k-1}_{j=0}T^{-j}V_{i_{n-k+j}} \ . $$ By the mixing property $$ \P\left(A \cap T^{-n}C^{(n)}_k \right) \le (1+\phi(0))\P(A)\P(C^{(n)}_k ) \ . \Eq(mixp) $$ Since $C^{(n)}_k$ is a $k$-cylinder, we can use \equ(exp) in the right hand side of \equ(mixp), to get $$ \P\left(A \cap T^{-n}C^{(n)}_k \right) \le (1+\phi(0))\P(A)ce^{-\gamma k} \ . \Eq(fin) $$ Inequality \equ(inter) follow trivially from \equ(fin). This concludes the proof of lemma 1. \vskip 4truemm \noindent{\bf 4. Bounds for $\ta$.} \numsec=4 \numfor=1 Let us introduce some extra notation. For any positive integer $k$, let $$ X_k = \sum_{l=0}^k \one_A(T^l) \ , \Eq(x) $$ where $\one_A$ is the indicator function of the set $A$. For any $\omega \in \Omega$, $X_k(\omega)$ is the number of times the system visits $A$, during the first $k+1$ steps. We remark that $$ \{\ta \le k \}= \{X_k \ge 1\}\ . $$ \vskip 2truemm \noindent{\bf Lemma 2.} For any positive real number $t$ the following holds $$ \P\left\{\ta \le {t\over{\P(A)}}\right\} \le t+\P(A) \ . \Eq(borni1) $$ \vskip 2truemm \noindent{\bf Proof.} Let $X=X_{[{t\over{\P(A)}}]}$, where $ [{t\over{\P(A)}}]$ is the integer part of ${t\over{\P(A)}}$. Then $$ E(X)= \sum_{l=0}^{[{t\over{\P(A)}}]} E\left(\one_A(T^l)\right) \le t+\P(A) . \Eq(ex) $$ where the last equality follows from the invariance of the measure $\P$ with respect to the transformation $T$. Since $$ \P\left\{\ta \le {t\over{\P(A)}}\right\}= \P\{X \ge 1\}\le E(X) \ , $$ the inequality is proved. \vskip 2truemm \noindent{\bf Lemma 3.} For any positive integer $n$, any cylinder $A \in {\cal C}_n$, and any positive real number $t$ the following holds $$ \P\left\{\ta \le {t\over{\P(A)}}\right\} \ge {t^2 \over {t^2 +C^{\prime}t +[tC^{\prime \prime} +1] \P(A)}}\ , \Eq(borni2) $$ where $C^{\prime}>0$ and $C^{\prime \prime} >0$ are two constants, independent of $n$ and $A$. \vskip 2truemm \noindent{\bf Proof.} Let $X=X_{[{t\over{\P(A)}}]}$. We first remark that $$ E(X)^2 = E(X\one\{X\ge 1\})^2 \le E(X^2) \P\{X\ge 1\} \ , $$ where the last inequality follows from the Schwarz inequality. Therefore $$ \P\left\{ \ta \le {t\over{\P(A)}}\right\} = \P\{X\ge 1\} \ge {E(X)^2 \over{ E(X^2)}}\ . $$ The first equality in \equ(ex) provides a lower bound for the numerator $$ E(X)^2 \ge t^2 \ . $$ To obtain an upper bound for the denominator $E(X^2)$, we decompose it as follows. If ${[{t\over{\P(A)}}]}>n$, then $$ E(X^2)= \sum_{l=0}^{[{t\over{\P(A)}}]}E\left(\one_A(T^l)\right) + 2\sum_{l=1}^{n}\left([{t\over{\P(A)}}]-l+1\right) E\left(\one_A \cap \one_A(T^l)\right) $$ $$+ 2\sum_{l=n+1}^{[{t\over{\P(A)}}]} \left([{t\over{\P(A)}}]-l+1\right) E\left(\one_A \cap \one_A(T^l)\right) \ . \Eq(x2) $$ If ${[{t\over{\P(A)}}]}\le n$, the third term of the decomposition is not present. The upper bound is the same in both cases. The first term of this decomposition is $E(X) \le t+\P(A)$. Using lemma 1 in the second term, we get $$ \sum_{l=1}^{n}([{t\over{\P(A)}}]-l+1) E\left(\one_A \cap \one_A(T^l)\right) \le [{t\over{\P(A)}}]\sum_{k=1}^{n}P\{A\cap{T^{-k}(A)}\}\le c t \ . $$ The mixing property provides upper bounds for the expectations inside the third term $$ E\left(\one_A \cap \one_A(T^l)\right) \le \left(1+\phi(l-n)\right)\ {\P(A)}^2 . $$ Therefore the third term is bounded above by $$ 2\P(A)^2\left (\sum_{l=1}^{[{t \over{\P(A)}}]}l+ {t\over {\P(A)}}\sum_{l=1}^{+\infty}\phi(l)\right) \ . $$ Now we remark that $$ \sum_{l=1}^{[{t\over{\P(A)}}]}l= {1\over 2} {{[{t\over{\P(A)}}]([{t\over{\P(A)}}]+1)}}\ . $$ Finally we use the hypothesis that the series $\sum_{l=1}^{+\infty}\phi(l)$ is convergent to get the upper bound $$ \sum_{l=n+1}^{[{t\over{\P(A)}}]} \left([{t\over{\P(A)}}]-l+1\right) E\left(\one_A \cap \one_A(T^l)\right) \le {{t^2}\over 2}+{{t\P(A)}\over 2}+Kt\P(A)\ , $$ where $K=\sum_{l=1}^{+\infty}\phi(l)<+\infty$. This concludes the proof of Lemma 3. \vskip 2truemm \noindent{\bf Lemma 4.} For all $\alpha \in (0, 1)$,there exists a positive integer $n_0=n_0(\alpha)$, such that, for all $n \ge {n_0}$ and $A \in {\cal C}_n$, the inequalities $$ \Lambda_1 r(A) \le - \log{\P\left\{ \ta > {r(A) \over \pa}\right\}} \le \Lambda_2 r(A) $$ hold, where $ r(A)=\pa ^{\alpha }$, and $\Lambda_1$ and $\Lambda_2$ are two positive constants independent of $\alpha$, $n$, and $A$. \noindent{\bf Proof.} To obtain the lower bound, we first remark that $$ \theta \ge 1 - e^{\displaystyle{-\theta}} \ , \Eq(ge) $$ for all $\theta \ge 0$. Let us take $$ \theta=\theta(A)=-\log {\P\left\{ \ta > {r(A) \over \pa}\right\}}\ . \Eq(theta) $$ Using \equ(ge) and lemma 3, we get $$ {\theta (A) \over r(A)} \ge {1 - e^{\displaystyle{-\theta (A)}} \over r(A)} \ge {1\over{\pa^{\alpha}+C^{\prime} + C^{\prime \prime} + \pa^{(1-\alpha)}}} \ ,\Eq(min) $$ where $C^{\prime}$ and $C^{\prime \prime}$ are the same constants that appear in lemma 3. >From \equ(min) it follows that we can take $$ \Lambda_1 ={1\over{ 2 + C^{\prime } + C^{\prime \prime} }} \ . $$ To obtain the upper bound, we remark that the inequality $$ {\theta \over 2} \le 1 - e^{\displaystyle{-\theta}} \ \Eq(le) $$ holds for all $\theta \in (0, \log 2) $. By lemma 1 and lemma 2, $$ \P\left\{ \ta \le {r(A) \over \pa}\right\} \le 2{\pa}^{\alpha} \le 2 ce^{\displaystyle{-\gamma \alpha n}} \ .\Eq(ag) . $$ Let us take $\theta =\theta(A)$, as in \equ(theta). It follows from \equ(le) and \equ(ag) that $$ - \log{\P\left\{ \ta > {r(A) \over \pa}\right\}} \le 2\P\left\{ \ta \le {r(A) \over \pa}\right\} \le 4{\pa}^{\alpha} \ ,\Eq(L2) $$ for all $n \ge n_0$, where $$ n_0 = n_0(\alpha) = \left[{1 \over {\gamma \alpha}} \log{\left(4c\right)}\right] \ . $$ Therefore, we can take $\Lambda_2 = 4$. This concludes the proof of lemma 4. \vskip 4truemm \noindent{\bf 5. The independence property.} \vskip 2truemm \numsec=5\numfor=1 As the function $\Phi$ is summable, there exists a positive constant $C_{\Phi}$ such that $$ \Phi (l) \le {C_{\Phi} \over l} \ , \Eq(Cfi) $$ for any positive integer $l$. We use this fact in the next lemma. Before, let us introduce an extra notation. For any positive real number $t$ let $$ g_{A}(t)=P\left\{\ta > {t\over{\P(A)}}\right\} \ . $$ \vskip 2truemm \noindent{\bf Lemma 5.} For all $\alpha \in (0, 1)$,there exists a positive integer $n_1=n_1(\alpha)$, such that, for all $n \ge {n_1}$, $A \in {\cal C}_n$ and any real number $s \ge \pa ^{\alpha}$, the following holds $$ \sup_{t>0} \left| g_{A}(t+s)-g_{A}(t)g_{A}(s) \right| \le 2 s^{(1 - \alpha)}{\pa}^{\alpha} + C_{\Phi}{\pa}^{(1-\alpha)^2} \ .\Eq(ind) $$ \vskip 2truemm \noindent{\bf Proof.} Let us start by sketching the idea of the proof. We want to obtain an upper bound to $$ \left\vert \P\left\{X_{[{{t+s}\over \pa}]}=0\right\}- \P\left\{X_{[{t\over \pa}]}=0 \right\} \P\left\{X_{[{s \over \pa}]}=0 \right\}\right\vert \ . \Eq(fact) $$ To do this we want to introduce a gap $\Delta$, between the intervals of time $\left[0, {t\over \pa}\right]$ and $\left[{t\over \pa}, {{t+s}\over \pa}\right]$. This gap would enable us to use the mixing property to express the probability of not reaching the set $A$ during the global interval $$ \left[0, {t\over \pa}\right] \cup \left[{t\over \pa}+\Delta, {{t+s}\over \pa}\right] $$ as the product of the probabilities of not reaching the set $A$ in each of the subintervals $\left[0, {t\over \pa}\right]$ and $\left[{t\over \pa}+\Delta, {{t+s}\over \pa}\right] $. Let us take $$ \Delta = d +n \ , $$ where $n$ is the order of the cylinder $A$ and $d$ is a suitable positive integer. The game is to chose $d$ big enough, to take advantage of the mixing property of the system, and small enough to make the probabilities associated to the intervals with the gap close to the probabilities associated to the original intervals. Let $\alpha$ be a fixed real number, with $0 < \alpha < 1$. Let us define $n_1$ as the smallest positive integer for which inequality $$ {1\over 2c} e^{\displaystyle{{\gamma} n {(1-\alpha)}^2}} \ge n \ , \Eq(n1) $$ holds, where the constants $c$ and $\gamma$ are the same which appear in lemma 1. Let us take $n\ge n_1$ and $A \in {\cal C}_n$ and let us define $d=d(A,\alpha)$ as $$ d = \left[ {1\over 2}\left({s \over \pa}\right)^{1 -{\alpha}}\right] \Eq(defd) $$ Since $s \ge {\pa}^{\alpha}$, a direct computation shows that \equ(n1), \equ(defd), and \equ(exp) in Lemma 1 imply $$ d+n \le \left({s \over \pa}\right)^{1 -{\alpha}} \le {s \over \pa} \ .\Eq(d+n) $$ This is what we need to develop the idea sketched above. Let us call $$ X_{]{t\over \pa}+d+n, {{t+s}\over \pa}]}= X_{[{{t+s}\over \pa}]}-X_{[{t\over \pa}]+d+n} $$ the number of times the system visits the set $A$ between steps ${{t\over \pa}+d+n}$ and ${{t+s}\over \pa}$. By definition $$ \left\vert g_A(t+s)- \P\left\{X_{[{t\over \pa}]}+X_{]{t\over \pa}+d+n, {{t+s}\over \pa}]}= 0 \right\} \right\vert = \P\left\{X_{]{t\over \pa}, {t\over \pa}+d+n]} > 0 \right\} \ . $$ The invariance of $\P$ with respect to $T$ assures that $$ \P\left\{X_{]{t\over \pa}, {t\over \pa}+d+n]}>0 \right\} = \P\left\{X_{d+n-1}>0 \right\} \ . $$ Therefore, lemma 1 implies that $$ \left\vert g_A(t+s) - \P\left\{X_{[{t\over \pa}]}+X_{]{t\over \pa}+d+n, {{t+s}\over \pa}]}=0 \right\} \right\vert \le (d+ n) \pa \ . \Eq(fact1) $$ Also by lemma 1, we have that $$ \left\vert g_A(s) - \P\left\{X_{[d+ n, {s \over \pa}]}=0 \right\}\right\vert\le (d + n)\pa \ . \Eq(fact2) $$ We finally use the mixing property \equ(fimix) to obtain the upper bound $$ \left\vert \P\left\{X_{[{t\over \pa}]}+X_{{}]{t\over \pa}+d+n, {{t+s}\over \pa}]}=0 \right\}- g_A(t) \P\left\{X_{]d+n, {s \over \pa}]}=0 \right\} \right\vert \ \le \Phi(d +1) . \Eq(fact3) $$ By \equ(d+n), the sum of the right hand sides of \equ(fact1) and \equ(fact2) is bounded above by $$ 2 \left({s \over \pa}\right)^{1 -{\alpha}}{\pa}\le 2s^{1- {\alpha}}{\pa}^{\alpha} \ . $$ By \equ(Cfi) and \equ(defd), the right hand side of \equ(fact3) is bounded above by $$ {C_{\Phi} \over d}={C_{\Phi}\pa^{(1-\alpha)} \over{ s^{(1-\alpha)}}}\ . $$ Since $s \ge {\pa}^{\alpha}$, we have the inequality $$ {{C_{\Phi}\pa^{(1-\alpha)}} \over{ s^{(1-\alpha)}}} \le C_{\Phi}{\pa}^{(1-\alpha)^2} . $$ This concludes the proof of lemma 5. \vskip 2truemm In the proof of the theorem we shall use the following version of lemma 5. \vskip 2truemm \noindent{\bf Lemma 6.} For $n \ge {n_1}({\bar \alpha })$), where ${\bar{\alpha}} = 1-{\sqrt{2}\over 2}$, and $A \in {\cal C}_n$, let us take $r= r(A)= \pa ^{\bar{\alpha}}$, and let us define $\theta=\theta(A)=- \log g_{A}(r)$. Then, for any integer $k \ge 1$, the following holds $$ \left\vert g_{A}(kr)- e^{\displaystyle{-\theta k}} \right\vert \le {{(2 + C_{\Phi})\sqrt{\pa}}\over {1 -e^{- {\theta}}}} . $$ \vskip 2truemm \noindent{\bf Proof.} It is enough to prove, by induction, that $$ \left\vert g_{A}(kr) - e^{\displaystyle{-\theta k}}\right\vert \le {(2 + C_{\Phi})\sqrt{\pa}}\left[1+e^{\displaystyle{-\theta}} +\dots+e^{\displaystyle{-\theta(k-2)}}\right] \ , \Eq(geo) $$ is true for any integer $k\ge 1$. The result is trivially true for $k=1$. Let us assume that it holds for $k\ge 2$. By the triangle inequality $$ \left\vert g((k+1)r) - e^{\displaystyle{-\theta (k+1)}}\right\vert \le \left\vert g((k+1)r) - g_{A}(kr)e^{\displaystyle{-\theta}}\right\vert + e^{\displaystyle{-\theta}}\left\vert g_{A}(kr) - e^{\displaystyle{-\theta k}}\right\vert \ . \Eq(triangle)\ . $$ By lemma 5 $$ \left\vert g_{A}(kr) - g_{A}((k-1)r) e^{\displaystyle{-\theta}}\right\vert \le {(2 + C_{\Phi})\sqrt{\pa}} \Eq(primo) $$ Replacing the first term on the right hand side of \equ(triangle) by \equ(primo) and using the hypothesis that the result holds for $k$, we obtain the corresponding inequality for $k+1$. This concludes the proof of lemma 6. \vskip 4truemm \noindent{\bf 6. Proof of the theorem.} \vskip 2truemm \numsec=6 \numfor=1 It is enough to prove that the theorem holds for any cylinder $A \in {\cal C}_n$ with $n \ge \max \{n_0, n_1\}$. Let $r= r(A)= \pa ^{\bar{\alpha}}$, where ${\bar{\alpha}} = 1-{\sqrt{2}\over 2}$, and $\theta=\theta(A)=-\log g_{A}(r)$, and let us define $$ \lambda(A)={\theta \over r} \ .\Eq(lambda) $$ Fix $t>0$ and write $t = k r + v $ where $k = k(r) \ge 0$ is the integer part of $t/r$ and $0\le v = v(r) < r$. $$ \left\vert g_A(t)-e^{\displaystyle{-\lambda(A)t}}\right\vert \le \left\vert g_A(t)- g_A(kr) \right\vert + \left\vert g_A(kr) -e^{\displaystyle{ -\theta k}} \right\vert + \left\vert e^{\displaystyle{kr}}-e^{\displaystyle{-\lambda(A)t}}\right\vert \ . \Eq(too) $$ Stationarity and lemma 1 provides an upper bound for the first term of the sum in \equ(too). $$ \left\vert g_A(t)- g_A(kr) \right\vert \le \left({v \over \pa} +1 \right) \pa \le 2{\pa}^{\bar{\alpha}} \ . \Eq(first) $$ Lemma 6 provides a first upper bound for the second term of the sum in \equ(too). $$ \left\vert g_A(kr) -e^{\displaystyle{ -\theta k}} \right\vert \le {{(2 + C_{\Phi})\sqrt{\pa}}\over {1 -e^{-{\theta}}}} \ .\Eq(second) $$ By (4.8) in lemma 4, the right hand side of \equ(second) is bounded above by $$ {\bar C}{\pa}^{\beta} \ ,\Eq(secondb) $$ where $\beta = {{\sqrt(2) -1 }\over 2}$ and $\bar C$ is a constant independent of $n$ and $A$. Elementary calculus provides a first upper bound for the third term in \equ(too) $$ \left\vert e^{\displaystyle{ -\theta k}}-e^{\displaystyle{-\lambda(A)t}}\right\vert \le {\theta \over r}v \le {\theta} \ .\Eq(third) $$ By lemma 6 $$ \theta \le \Lambda_2 r = \Lambda_2 {\pa}^{\bar \alpha} \ . $$ This, together with lemma 4, concludes the proof of the theorem. \vskip 4truemm \noindent{\bf Acknowledgments.} We thank P. Collet and P. Gabriel for many discussions and comments. A.G. acknowledges friendly hospitality at the D\'epartement de Math\'ematiques de l'Universit\'e de Bourgogne and at the Centre de Physique Th\'eorique de l'Ecole Polytechnique. This work was partially supported by USP-ProInter, CNPq (grant 301301/79), FAPESP ({\sl Projeto Tem\'atico} 95/0790-1), and Pronex (grant 41.96.0923.00). \vskip 4truemm \noindent {\bf References.} \baselineskip 13pt \parskip 2truemm \parindent 0pt D.J.\ Aldous (1982) Markov chains with almost exponential hitting times. {\sl Stochastic Process.\ Appl.\ \bf 13} 305-310. D.\ J.\ Aldous, M.\ Brown (1992) Inequalities for rare events in time-reversible Markov chains~I {\it in} M. Shaked and Y. L. Tong {\sl Stochastic Inequalities} IMS Lecture Notes {\bf 22} 1-16. D.\ J.\ Aldous, M.\ Brown (1993) Inequalities for rare events in time-reversible Markov chains~II. {\sl Stochastic Processes Appl. \bf 44} 15-25. R.\ Bellman and T.\ E.\ Harris (1951) Recurrence times for the Ehrenfest model. {\sl Pacific\ J.\ Math. \bf 1} 179. M. Cassandro, A. Galves, E. Olivieri and M. E. Vares (1984) Metastable behavior of stochastic dynamics: a pathwise approach. {\sl J. Stat. Phys. \bf 35}:603-633. R. Cogburn (1985) On the distribution of first passage and return times for small sets. {\sl Ann.\ Probab.\ \bf 13} 1219-1223. P.\ Collet and A.\ Galves (1993) Statistics of close visits to the indifferent fixed point of an interval map. {\sl J. Stat.Phys.} {\bf 72}, 459-478. P.\ Collet and A.\ Galves (1995) {\sl Asymptotic distribution of entrance times for expanding maps of the interval} in {\sl Dynamical Systems and Applications}, WSSIAA {\bf 4}, 139-152. P.\ Collet, A.\ Galves and B.\ Schmitt (1992) Unpredictability of the occurrence time of a long laminar period in a model of temporal intermittency. {\sl Ann.\ Inst.\ H.\ Poincar\'e, Section A, \bf 57} 3:319-331. W.\ Doeblin (1940) Remarques sur la th\'eorie m\'etrique des fractions continues. {\sl Compositio Math.} {\bf 7} 353-371. P.\ A.\ Ferrari, A.\ Galves and C.\ Landim (1994) Exponential waiting time for a big gap in a one dimensional zero range process. {\sl Ann.\ Probab.\ \bf 22} 1:284-288. A.\ Galves and B.\ Schmitt (1990) Occurrence times of rare events for mixing dynamical systems. {\sl Ann. \ Inst.\ H. \ Poincar\'e}\ {\bf 52} 267-281. T.\ E.\ Harris (1953) First passage and recurrence distributions. {\sl Trans.\ Amer.\ Math.\ Soc.\ \bf 73} 471-486. J.\ Keilson (1979) {\sl Markov Chain Models. Rarity and Exponentiality.} Springer-Verlag. C.\ Kipnis and C.\ Newman (1985) The metastable behavior of infrequently observed, weakly random, one-dimensional diffusion processes {\sl SIAM J. Appl. Math. \bf 45}:972. D.\ V.\ Korolyuk and D.\ S.\ Sil'vestrov (1984) Entry times into asymptotically receding domains for ergodic Markov chains. {\sl Theory Prob.\ Appl.\ \bf 19} 432-442. J.\ L.\ Lebowitz, R.\ H.\ Schonmann (1987) On the asymptotics of occurrence times of rare events for stochastic spin systems. {\sl J.\ Stat.\ Phys.\ \bf 48} 727-751. E.\ Olivieri and E.\ Scoppola (1995) Markov chains with exponentially small transition probabilities: first exit problem from a general domain. I. The reversible case. {\sl J.\ Stat.\ Phys.}\ {\bf 79} 613-647. E.\ Olivieri and E.\ Scoppola (1996) Markov chains with exponentially small transition probabilities: first exit problem from a general domain. II. The general case. {\sl J.\ Stat.\ Phys.}\ to appear. \vskip 5truemm \settabs 2\columns \+ A. Galves & B. Schmitt\cr \+ Instituto de Matem\'atica e Estat\'\i stica & Laboratoire de Topologie \cr \+ Universidade de S\~ao Paulo & Universit\'e de Bourgogne \cr \+ BP 66 281 & BP 400 \cr \+ 05315-970 S\~ao Paulo SP & 21011 Dijon Cedex \cr \+ Brasil & France \cr \+ galves@ime.usp.br & schmittb@satie.u-bourgogne.fr \cr \vfill \end