BODY %%%%%%%%%%%%%%% FORMATO \magnification=\magstep1\hoffset=0.cm \voffset=1truecm\hsize=16.5truecm \vsize=21.truecm \baselineskip=14pt plus0.1pt minus0.1pt \parindent=12pt \lineskip=4pt\lineskiplimit=0.1pt \parskip=0.1pt plus1pt \def\ds{\displaystyle}\def\st{\scriptstyle}\def\sst{\scriptscriptstyle} \font\seven=cmr7 %%%%%%%%%%%%%%%% GRECO \let\a=\alpha \let\b=\beta \let\c=\chi \let\d=\delta \let\e=\varepsilon \let\f=\varphi \let\g=\gamma \let\h=\eta \let\k=\kappa \let\l=\lambda \let\m=\mu \let\n=\nu \let\o=\omega \let\p=\pi \let\ph=\varphi \let\r=\rho \let\s=\sigma \let\t=\tau \let\th=\vartheta \let\y=\upsilon \let\x=\xi \let\z=\zeta \let\D=\Delta \let\F=\Phi \let\G=\Gamma \let\L=\Lambda \let\Th=\Theta \let\O=\Omega \let\P=\Pi \let\Ps=\Psi \let\Si=\Sigma \let\X=\Xi \let\Y=\Upsilon %%%%%%%%%%%%%%% DEFINIZIONI LOCALI \let\ciao=\bye \def\fiat{{}} \def\pagina{{\vfill\eject}} \def\\{\noindent} \def\bra#1{{\langle#1|}} \def\ket#1{{|#1\rangle}} \def\media#1{{\langle#1\rangle}} \def\ie{\hbox{\it i.e.\ }} \let\ig=\int \let\io=\infty \let\i=\infty \let\dpr=\partial \def\V#1{\vec#1} \def\Dp{\V\dpr} \def\tende#1{\vtop{\ialign{##\crcr\rightarrowfill\crcr \noalign{\kern-1pt\nointerlineskip} \hskip3.pt${\scriptstyle #1}$\hskip3.pt\crcr}}} \def\otto{{\kern-1.truept\leftarrow\kern-5.truept\to\kern-1.truept}} \def\LS{Logarithmic Sobolev Inequality } \def\LSC{Logarithmic Sobolev Constant } \def\Z{{\bf Z^d}} \def\supnorm#1{\vert#1\vert_\infty} \def\grad#1#2{(\nabla_{\L_{#1}}#2)^2} \def\log#1{#1^2log(#1)} \def\logg#1{#1log((#1)^{1\over2})} \def\eop{\hfill\bbox$\,$} \def\bbox{\vrule height 1.5ex width 0.6em depth 0ex } %%%%%%%%%%%%%%%%%%%%% Numerazione pagine \def\data{\number\day/\ifcase\month\or gennaio \or febbraio \or marzo \or aprile \or maggio \or giugno \or luglio \or agosto \or settembre \or ottobre \or novembre \or dicembre \fi/\number\year} %%\newcount\tempo %%\tempo=\number\time\divide\tempo by 60} \setbox200\hbox{$\scriptscriptstyle \data $} \newcount\pgn \pgn=1 \def\foglio{\number\numsec:\number\pgn \global\advance\pgn by 1} \def\foglioa{A\number\numsec:\number\pgn \global\advance\pgn by 1} %\footline={\rlap{\hbox{\copy200}\ $\st[\number\pageno]$}\hss\tenrm %\foglio\hss} %\footline={\rlap{\hbox{\copy200}\ $\st[\number\pageno]$}\hss\tenrm %\foglioa\hss} % %%%%%%%%%%%%%%%%% EQUAZIONI CON NOMI SIMBOLICI %%% %%% per assegnare un nome simbolico ad una equazione basta %%% scrivere \Eq(...) o, in \eqalignno, \eq(...) o, %%% nelle appendici, \Eqa(...) o \eqa(...): %%% dentro le parentesi e al posto dei ... %%% si puo' scrivere qualsiasi commento; %%% per assegnare un nome simbolico ad una figura, basta scrivere %%% \geq(...); per avere i nomi %%% simbolici segnati a sinistra delle formule e delle figure si deve %%% dichiarare il documento come bozza, iniziando il testo con %%% \BOZZA. Sinonimi \Eq,\EQ,\EQS; \eq,\eqs; \Eqa,\Eqas;\eqa,\eqas. %%% All' inizio di ogni paragrafo si devono definire il %%% numero del paragrafo e della prima formula dichiarando %%% \numsec=... \numfor=... (brevetto Eckmannn); all'inizio del lavoro %%% bisogna porre \numfig=1 (il numero delle figure non contiene la sezione. %%% Si possono citare formule o figure seguenti; le corrispondenze fra nomi %%% simbolici e numeri effettivi sono memorizzate nel file \jobname.aux, che %%% viene letto all'inizio, se gia' presente. E' possibile citare anche %%% 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 \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\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} \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 \footline={\rlap{\hbox{\copy200}\ $\st[\number\pageno]$}\hss\tenrm \foglio\hss} \vskip 1cm \centerline{\bf MARKOV CHAINS WITH EXPONENTIALLY SMALL TRANSITION} \centerline {\bf PROBABILITIES: FIRST EXIT PROBLEM FROM A GENERAL DOMAIN} \bigskip {\bf II. THE GENERAL CASE.} \vskip 1cm \centerline{E.Olivieri$^{(1)}$, E.Scoppola$^{(2)}$} \vskip 1cm {\it (1) Dipartimento di Matematica - II Universit\`a di Roma - Tor Vergata}\par {\it Via della Ricerca Scientifica - 00173 ROMA - Italy}\par E-mail: OLIVIERI@MAT.UTOVRM.IT \bigskip {\it (2) Dipartimento di Matematica - Terza Universit\`a di Roma.}\par {\it V. Segre 2 - 00146 ROMA - Italy }\par E-mail: SCOPPOLA@MAT.UNIROMA3.IT \vskip 1cm \vskip 1cm {\bf Abstract} \bigskip In this paper we consider aperiodic ergodic Markov chains with transition probabilities exponentially small in a large parameter $\b$ . We extend to the general not necessarily reversible case the analysis started in [OS] of the first exit problem from a general domain $Q$ containing many stable equilibria (attracting equilibrium points for the $\b = \infty$ dynamics). In particular we describe the tube of typical trajectories during the first excursion outside $Q$. \bigskip {\bf Keywords : Markov chains, first exit problem, large deviations.} \vfill \eject \bigskip \noindent \numsec=1\numfor=1 {\bf Section 1. Introduction.}\par \bigskip In this paper we extend to the general not necessarily reversible case, the analysis, started in [OS] for the reversible case, of the typical exiting trajectories during the first excursion from a general domain $Q$.\par More precisely let $\{ X^{(\beta)}_t\}_{t=0,1,2,....}$ be a family of Markov chains defined on the finite state space $S$, with transition probabilities $P^{(\beta)}(x,y)$ depending on a positive parameter $\beta$ and satisfying the following conditions: \bigskip \item{1)}{\it ergodicity condition}: $$ \forall x,y \in S\quad \exists \, n \quad \hbox{such that}\quad P^{(\beta ) n}(x,y)>0$$ (where $P^{(\beta) n}(x,y)$ is the n-step transition probability) ;\par \item{2)} {\it property ${\cal P}$}: there exist a function $\Delta (x,y) ,\, x,y\in S$ assuming values: $\D_0=0< \D _1 < \D _2 < .......< \D _n $, for some positive integer n, with $ \D _n < \infty$ and a positive function $\gamma =\gamma (\b )$, with $\gamma \to 0$ as $\b\to\infty$, such that if $x\not= y$ and $ P^{(\beta)}(x,y) >0$, then : $$ exp\{-\D (x,y) \beta - \gamma \b \} \leq P^{(\beta)} (x,y) \leq exp\{-\D (x,y)\b + \gamma \b\}\Eq(1.1)$$ \bigskip We will denote by $X_t(x)$ the Markov chain at time $t\in {\bf N}$ starting from x at time 0; we will omit everywhere the index $\beta$, for notation simplicity.\par We will denote by $P_x$ the probability distribution of the process starting from $x$ at $t=0$ and by $E_x$ the corresponding expectation. Moreover, given any set of states $Q\subset S$, we will denote by $\tau_Q$ the first hitting time to $Q$: $$\tau_Q\equiv\min\{t>0:\, X_t\in Q\}\Eq(1.2)$$ For any set $Q\subset S$ we will denote by $Q^c\equiv S\backslash Q$ the complement of $Q$.\par The aim of this paper is to provide a complete description of the typical behavior of the Markov chain $X_t$ up to the time $\tau_{Q^c}$, for any set $Q\subset S$, and for $\b$ sufficiently large.\par We refer to [OS] for a general discussion of the problem. Here we want only to recall that the results obtained by Freidlin and Wentzell concern only the asymptotics for $\b$ large of the first exit time $\tau_{Q^c}$ and of the first exit point $X_{\tau_{Q^c}}$. The description of the tube of typical trajectories was given by Freidlin and Wentzell ([FW]) only in the case of a domain $Q$ completely attracted by a unique stable equilibrium point.\par It turns out from the analysis of many particular models (see for instance [NSch1], [NSch2], [KO1], [KO2]) that for general domains the typical escape involves the permanence of the process in suitable sets during suitable random times, exponentially diverging in $\b$. This sort of ``temporal entropy" is essential to provide an efficient mechanism of escape.\par In [OS] by exploiting reversibility we were able to reduce the solution of the problem to the analysis of the energy landscape. In particular the decomposition of the space into special sets called ``cycles", which play a crucial role in the theory, was simply obtained in terms of the energy. \par In the present paper to study the general non-reversible case, in order to get the cycles decomposition, we are forced to use graphical methods like those introduced by Freidlin-Wentzell in [FW].\par Our strategy will be to combine this graphical approach with an analysis in terms of increasing scales of time introduced in [S1]. In that paper the long time behavior of the chain $X_t$ was studied by constructing a sequence of {\it renormalized Markov chains} $ X^{(1)}_t, X^{(2)}_t, \dots X^{(j)}_t \dots $ whose state spaces $S^{(1)}, S^{(2)},\dots , S^{(j)}. \dots$ were composed by equilibrium points of increasing stability. These chains provide a rougher and rougher description of our stochastic evolution adapted to the analysis of phenomena taking place in increasing scales of time (exponential in $\b$).\par If $S\equiv S^{(0)}$ is the original state space then $S^{(1)}$ is just the set of stable equilibria for the original Markov chain $X_t \equiv X^{(0)}_t$; $X^{(1)}_t$ is suitably defined on $S^{(1)}$. $S^{(2)}$ is the set of stable equilibria for $X^{(1)}_t$ and so on. In the following Section 2 we will recall all the necessary definitions given in [S1]. In [S1] with this construction of renormalized chains, some results on the typical long time behavior of the original chain $X_t$ were easily obtained. In fact to each exponentially long path of the chain $X_t$, a short path of a chain $X^{(N)}_t$ was associated, with a suitable renormalization index $N$.\par However a detailed description of the behavior of the original chain $X_t$ during each interval of time corresponding to each transition of the chain $X^{(N)}$, was missing in [S1].\par This detailed description turns out to be strictly connected to the problem of the definition of the typical exiting tube. Indeed let $N=N(Q)$ be the level such that the $(N+1)$-the renormalized Markov chain does not contain states inside $Q$: $S^{(N+1)} \cap Q= \emptyset$. This means that the first excursion outside $Q$ for the chain $X^{(N)}_t$ is a sort of ``descent" along the drift. \par As we already sketched in [OS] a first rough approximation of the typical tube of escape from $Q$ is given by the set of typical trajectories followed during the first excursion outside $Q$ by the chain $X^{(N)}_t$.\par It remains the question of ``reading" the result in terms of the paths followed on the original scale of time by our original chain $X_t$. \par This problem of analyzing the set of trajectories of the original chain $X_t$ corresponding to a given trajectory of the chain $X^{(N)}_t$, is solved in the present paper. As noted above this not only will give a full characterization of the typical tube of trajectories followed by the original chain $X_t$ during the first excursion from $Q$; this paper completes the analysis introduced in [S1] based on the renormalization procedure. Namely we will be able to associate to any state $x^N$ of $S^{(N)}$ a suitable set $Q_{x^N}\in S$ , a sort of generalized cycle, representing the set where the original process $X_t$ typically remains in the interval of time corresponding to a jump of the chain $X^{(N)}_t$.\par We will also analyze the typical ``descent" to the ``bottom" of a generalized basin of attraction of a stable equilibrium $x^N \in S^{(N)}$. In this case we can make a comparison with our previous results in the reversible case. The situation when analysing the typical ``ascent" against the drift is more complicated and, of course, in the non-reversible case typical ascents outside a generalized basin $Q$ and typical descents to the bottom of $Q$ are not related by time-reversal. \par It turns out that, similarly to what happens in the reversible case, the typical descent to the bottom of a domain containing many attractors takes place in a way that can be condidered as the natural genaralization of the typical descent to the bottom $x$ of a domain $Q$ completely attracted by the unique stable equilibrium point $x$.The main difference is the following: in the completely attracted domain the system does not ``hesitate" and it always follows the drift up to the arrival to $x$ in a finite time, uniformly bounded in $\b$, whereas in general not completely attracted domain the process tries to follow the drift in finite times as far as possible but sometimes it has to enter into suitable ``permanence sets" $Q_i$, waiting suitable random times $T_i$ and then getting out from $Q_i$ through suitable optimal points. The fact that the permanence times $T_i$ are close to the typical escape times from $Q_i$ and that this escape takes place in the optimal way is the counterpart of the fact that in the completely attracted case the only permanence sets are trivial in the sense that they reduce to single points and the way of getting out from these single points ( after a unitary permanence time!) is optimal in the sense that it is along the drift.\par \bigskip The paper is organized as follows in Section 2 we recall the renormalization procedure and extend previous results. In Section 3 we present the Freidlin-Wentzell (F-W) graphical method by extending to a more general case their definition of cycles. In Section 4 we establish some useful properties of the cycles. In Section 5 we state and prove our main theorem which determines typical trajectories of the original chain $X_t$ corresponding to a single step of the renormalized chain $X^{(N)}_t$. Finally in Section 6 we use the results of previous Sections to give a characterization of the tube of typical trajectories during the first excursion outside $Q$. \bigskip \bigskip \numsec=2\numfor=1 {\bf Section 2. The renormalization procedure.}\par \bigskip In this section we recall the construction of the sequence of renormalized chains introduced in [S1] and we prove some new result.\par Let $\Phi (S)\equiv \{\{\phi_i\}_{i\in {\bf N}}:\, \phi_i\in S\}$ be the set of paths. Following the theory of large deviations, developed in [FW], we define, for each $t\in {\bf N}$, a functional $I_{[0,t]}$ on $\Phi (S)$ associating to each path $\phi\in \Phi(S)$ the value $$I_{[0,t]} (\phi ) \equiv \sum_{i=0}^{t-1}\D (\phi_{i},\phi_{i+1}) \Eq(2.3)$$ where for $x\not= y,\; P(x,y)>0$, the fonction $\D(x,y)$ has been defined in \equ(1.1) and we set $\D (x,x)=0$ for each $x\in S$ and $\D (x,y) = \infty $ if $P(x,y) =0$. This functional is the {\it cost function} of each path $\phi$; we briefly recall now the main results and the construction developed in [S1]. \bigskip {\bf Lemma 2.1}\par {\it Let $\phi$ be a given path starting from x at time 0; then, for $t \in {\bf N}$ \par i) $$P_x(X_s=\phi_s\quad \forall s\in [0,t]) \leq e^{ -I_{[0,t]} (\phi ) \b +\gamma t\b}$$ where $ \g$ is the quantity introduced in \equ (1.1) ii) if $\phi$ is such that $\phi_s\not=\phi_{s+1}$ for any $s\in [0,t]$ then we have also a lower bound: $$P_x(X_s=\phi_s\quad \forall s\in [0,t]) \ge e^{ -I_{[0,t]} (\phi ) \b - \gamma t\b}$$ iii) for any constant $I_0>0$, for any $\alpha >0$ sufficiently small ($\a < \D_1$), for any $t0\Eq(2.6)$$ i.e. if each path leaving from $(x)_{\sim}$ has a positive cost. We will denote by $M$ the set of stable states.\par It is immediate to see that if the set $M$ contains a state $x$ then it contains the whole equivalence class of $x$, namely $M\supset (x)_{\sim}$.\par An immediate consequence of lemma 2.1 is the following:\par \bigskip {\bf Lemma 2.2}\par {\it \item{i)} There exist constants $T_0\in [0,|S|]$ and $\b _0>0$ such that for any $\b >\b _0$ and for any $t>T_0$: $$\sup_{x\in S} P_x(\tau_M>t)\leq a^{[{t\over T_0}]}$$ where $00$ and for any $t\ge e^{\eta\b }$ and $\b$ sufficiently large we have: $$\sup_{x\in S} P_x(\tau_M>t)\leq \exp\{-e^{{\eta\b\over 2}}\}$$ } \bigskip This means that the process spends, with large probability, almost all the time in M. This result suggests that, if we look at the process $X_t$ on a sufficiently large time scale, then it can be described in terms of transitions between states in M; in this way only the behaviour of the process on small times is neglected.\par Indeed we can consider the less stable states in $M$ and we can define a time scale $t_1$ corresponding to this smallest stability: $$t_1\equiv e^{V_1\beta +\delta\b}\Eq(2.11)$$ where $$V_1\equiv \min_{x\in M,\,y\in S,\,x\not\sim y} V(x,y)\Eq(2.12)$$ and $ \delta = \d (\b)$ goes to zero as $\b$ tends to infinity.\par We can then construct a new Markov chain $\bar X_t$ with state space $ M$, corresponding to the original process with a rescaling time $t_1$, by defining a sequence of stopping times $\zeta_1, \zeta_2,...,\zeta_n,... $ such that $\zeta_{n+1}-\zeta_n $ is of order $t_1$ with large probability and $X_{\zeta_n}$ belongs to $M$.\par More precisely we define the sequence of stopping times: $$\zeta_0 \equiv \hbox{min}\{t\ge 0 :\, X_t\in M\}$$ and for each $n\ge 1$: $$\sigma_n \equiv \hbox{min}\{ t>\zeta_{n-1} : \, X_t\not\sim X_{\zeta_{n-1}}\}$$ $$\tau_n \equiv \hbox{min}\{t\ge \sigma_n :\, X_t\in M\}$$ $$\zeta_n = \cases{ \zeta_{n-1}+ t_1\quad &if $ \sigma_n - \zeta_{n-1} > t_1$\cr \tau_n &if $\sigma_n - \zeta_{n-1}\leq t_1$\cr} \Eq(2.13)$$ It is easy to see that the sequence $\bar X_n =X_{\zeta_n}$ is a homogeneous Markov chain. For any pair of states $x,y\in M$ we denote by $\bar P(x,y)$ the transition probabilities of the chain $ \bar X_n$; it is possible to prove ([S1]) that these transition probabilities satisfy the same assumption (property ${\cal P}$) verified by the original chain $X_t$, provided we identify states which are equivalent with respect to the relation \equ(2.5). More precisely for any $x,y\in M,\quad x\not\sim y$: $$\exp\{-\D^{(1)} (x,y) \beta - \gamma' \b \} \leq \bar P(x,y)\equiv P(X_{\zeta_n}=y| \, X_{\zeta_{n-1}}=x)\leq \exp\{-\D^{(1)} (x,y) \beta + \gamma' \b \}\Eq(2.14) $$ The quantities $\D^{(1)}(x,y)$ are defined by: $$\D^{(1)} (x,y)=\inf_{t,\phi:\,\phi_0=x,\,\phi_t=y,\atop \phi_s\not\in M \backslash [(x)_{\sim}\cup (y)_{\sim}]}I_{[0,t]}(\phi) -V_1\Eq(2.15) $$ and $\g '\to 0$ as $\b \to\infty$.\par It is easy to show that the quantities $\D^{(1)}(x,y)$ are invariant with respect to the equivalence relation, i.e. $\D^{(1)}(x,y)=\D^{(1)}(x',y')$ if $x\sim x'$ and $y\sim y'$. In other words equivalent states are not distinguishable in this contruction.\par More precisely let $S^{(1)}\equiv M/_{\sim}\equiv \{\hbox{ equivalent classes in } M\}$ and for any $i\in S^{(1)}$ let $m_i$ be the subset of $M$ given by the states belonging to the equivalence class $i$, that is $M=\cup_{i\in S^{(1)}}m_i$.\par We can define a new chain $X^{(1)}_t$ on $S^{(1)}$ with transition probabilities $$P^{(1)}(i,j)={1\over\bar\m(m_i)}\sum_{x\in m_i}\bar\m (x)\sum_{y\in m_j} \bar P(x,y)$$ where $\bar\m$ denotes the invariant measure of the chain $\bar X_t$. This measure $\bar\m$ is related to the invariant measure $\m$ of the chain $X_t$ (which is strictly positive by the ergodicity condition) by the following relation (see ref. [Kh], Eq. (4.3) page 116) : $$\m (C)={1\over Z} \sum_{x\in M}\bar\m (x) E_x\sum_{t=0}^{\zeta_1}\chi_C(X_t)$$ where $C\subset S$, $ \chi_C $ is the characteristic function of $C$ and $Z$ is a normalization constant.\par Property ${\cal P}$ obviously holds also for the chain $X^{(1)}_t$ with the same function $\D^{(1)}$ and the invariant measure of this new chain is given by $\m^{(1)}(i)=\bar\m(m_i)$ for each $i\in S^{(1)}$. Thus we have a new chain $X^{(1)}_t$ on the state space $S^{(1)}$, to which we can apply again the same analysis, by defining new stable states, a time scale $T_2$, a corresponding chain $X^{(2)}_t$ and so on.\par We recall now here the iteration scheme introduced in [S1]. \bigskip {\bf Notation}: The superscript $^{(k)}$ will denote the various quantities referring to the k-th chain $X^{(k)}_t$; e.g. $\t^{(k)}_Q=\min \{t:\,X^{(k)}_t \in Q\},\quad Q\in S^{(k)}$. \bigskip For any $k\ge 1$ we define the following quantities: for any $\phi : {\bf N}\to S^{(k)}$: $$I_{[o,t]}^{(k)} (\phi) = \sum_{i=0}^{t-1}\D^{(k)}(\phi_i,\phi_{i+1}) \Eq(2.16)$$ $$V^{(k)}(x,y)\equiv \min_{t,\phi:\, \phi_0=x,\,\phi_t=y}I_{[o,t]}^{(k)} (\phi) \quad \forall x,y\in S^{(k)}\Eq(2.17)$$ $$x\sim^{(k)}y\quad\hbox{if and only if}\quad V^{(k)}(x,y)=V^{(k)}(y,x)=0 \Eq(2.18)$$ $$M^{(k)} = \{x\in S^{(k)}: \forall y\in S^{(k)},\, y\not\sim^{(k)}x\quad V^{(k)}(x,y)>0\}\Eq(2.19)$$ $$V_{k+1} = \min_{x\in M^{(k)}, y\in S^{(k)} \, x\not\sim^{(k)} y} V^{(k)}(x,y)\Eq(2.20)$$ $$t_{k+1} = e^{V_{k+1}\b + \delta \b}\Eq(2.21)$$ $$T_1=t_1$$ $$T_{k+1}=t_1t_2......t_kt_{k+1}\Eq(2.22)$$ $$S^{(k+1)}= M^{(k)}/_{\sim^{(k)}}\Eq(2.23)$$ $$\D^{(k+1)}(x,y) = \min_{t,\phi : \phi_0=x, \phi_t=y,\atop \phi_s\not\in M^{(k)} \backslash [(x)_{\sim^{(k)}}\cup (y)_{\sim^{(k)}}] \, \forall s\in [0,t]}I_{[0,t]}^{(k)}(\phi) - V_{k+1} \quad \forall x,y\in S^{(k+1)}\Eq(2.24)$$ \bigskip The main results proved in [S1] can be summarized as follows: \bigskip {\bf Theorem 2.1}\par {\it Let $W\subset S^{(1)}$ and $B\subset W$ and $\bar W$ and $\bar B$ the corresponding sets in $M$ ($\bar W=\cup_{i\in W}\,m_i$ and analogously for $\bar B$). Then for any sufficiently large $\b$ and for any $x\in m_i,\, i\in S^{(1)}\backslash W,\, j\in W$ there is a positive $\g'$ depending on $\g$ and tending to zero as $\b \to \infty$ such that: $$ \exp\{- \g' \b\} P^{(1)}_i(X^{(1)}_{\t_{W}}=j)\le P_x(X_{\t_{\bar W}}\in m_j)\le \exp\{ \g' \b\} P^{(1)}_i(X^{(1)}_{\t_{W}}=j)$$ $$\exp\{-\g'\b\}t_1 E^{(1)}_i\t^{(1)}_{W}\le E_x\t_{\bar W}\le \exp\{\g'\b\}t_1 E^{(1)}_i\t^{(1)}_{W}$$ $$e^{-\g'\b}\m^{(1)}(B)\le \m(\bar B)\le e^{\g'\b}\m^{(1)}(B)$$ for any $B\subset S^{(1)}$. Moreover for any $A\in S\backslash M$ $$\m(A)\le e^{-V_1\b+\g'\b}$$ } \bigskip Since $|S^{(i)}|\le |S^{(i-1)}|$ (actually one can prove that $|S^{(i+1)}|<|S^{(i-1)}|$), the above results provide a useful tool for the evaluation of these quantities when $|S|$ is large, in fact one can consider a time rescaling $T_n$ so large that the corresponding state space $S^{(n)}$ is so small that explicit computations are easy at this level.\par \bigskip In order to control the large deviation phenomena, for the Markov chain $X_t$, taking place during exponentially long times $T_k$, we collect, in the rest of this section, some general and quite easily proved results related to this renormalization procedure. The main statement on the behavior of the chain $X_t$ on exponentially long time intervals will be given in section 5.\par Let us start by the following remark:\par we note that in the construction of the previously recalled renormalized chains, we have to identify equivalent states at each step of the iteration. In fact, due to the time rescaling, the renormalized chain does not have enough resolution to distinguish among equivalent states. This fact implies that chains at different steps of the iteration live on different probability spaces. However we want to define now an application between trajectories of chains at different level of the iteration.\par More precisely, for any integer $n$, to any path $\phi$ of the Markov chain $X_t$, $\phi\in \Phi (S)$, we want to associate a path $\phi^{(n)}$ of the Markov chain $X^{(n)}_t$, $\phi^{(n)}\in \Phi (S^{(n)})$, which is in some sense a projection of the path $\phi$ in the smaller space $\Phi (S^{(n)})$. On the other hand to any path $\phi^{(n)}\in \Phi (S^{(n)})$ we want to associate a set, say a tube, of paths $\phi\in \Phi (S)$ having projection $\phi^{(n)}$. \bigskip {\bf Definition 2.1}\par For each path $\phi\in\Phi (S)$ we evaluate the sequence of stopping times $\zeta_n$ and we define a path $\bar\phi \in \Phi (M)$ given by $\bar\phi_i = \phi_{\zeta_i}$. To each path $\bar\phi\in \Phi(M)$ we can obviously associate a path $\phi^{(1)} \in\Phi(S^{(1)})$ by defining $\phi^{(1)}_s=i$ if $\bar\phi_s\in m_i$.\par Using the same construction we can thus define a sequence of trajectories $\{\phi^{(n)}_i\}_{i\in{\bf N}}$ in the spaces $\Phi (S^{(n)})$ with n=2,3,... \par On the other side, to any given sequence of states in $S^{(n)}$ : $\psi^{(n)}_i,\, i\le T$ we can associate a tube of trajectories in $\Phi (S)$ as $${\cal T} (\psi^{(n)},T) = \{\phi \in \Phi (S) :\, \phi^{(n)}_i= \psi^{(n)}_i\quad \forall i\le T\}\Eq(2.28)$$ By construction this application between trajectories in $\Phi(S)$ and trajectories in $\Phi(S^{(n)})$ is such that $$P^{(n)}(X^{(n)}_s=\phi^{(n)}_s,\,\forall s\le T)\asymp P(X_t\in {\cal T} (\psi^{(n)},T))\Eq(2.28biss)$$ where we say that two quantities $A$ and $B$ are {\it logaritmically equivalent} and we write $A\asymp B$ if they have the same exponential asymptotic behavior in $\b$ namely $$A\asymp B\quad \hbox{ if and only if }\quad \lim_{\b\to\infty} {1\over \b}\ln A = \lim_{\b\to\infty} {1\over \b}\ln B \Eq(1.3)$$ We say that $A$ is {\it logarithmically graeter} than $B$ and we write $A\succeq B $ if and only if $$ \lim_{\b\to\infty}{1\over \b} \ln A\ge \lim_{\b\to\infty}{1\over \b} \ln B\Eq(1.4)$$ \bigskip\bigskip {\bf Definition 2.2}\par With this application we can also define a sequence of random times $Z^{n}_k$ corresponding, on the original time scale, to the times $k$ on the time scale of the chain $X^{(n)}$. More precisely, given a path $\phi\in\Phi(S)$, we have defined a sequence of times $\z_0,....,\z_k,...$ and a path $\phi^{(1)}\in\Phi(S^{(1)})$ associated to it, and, iterating, sequences of times $\z^{(i)}_0,...,\z^{(i)}_k,...$, and paths $\phi^{(i+1)}\in\Phi(S^{(i+1)})$ for each $i=0,1,...$.\par We define: $$Z^n_k\equiv \z_{\z^{(1)}_{\z^{(2)}_{._{._{\z^{(n-1)}_k}}}}}\quad n=1,2,... \Eq(2.28bbis)$$ which is a random time with respect to the process $X_t$. \bigskip {\bf Definition 2.3}\par For each $x\in S^{(n)}$ we can define a set ${\cal E}^n_x$ belonging to the original state space $S$, obtained by associating, at each step of the iteration ($\le n$), to each equivalence class the set of its elements . More precisely if $n=1$: $$ {\cal E}^1_x = m_x\Eq(2.28bis)$$ and, for $j = 1, \dots , n$, if $x\in S^{(j)}$ and $m^{(j-1)}_x$ are the elements of $S^{(j-1)}$ corresponding to the equivalence class $x$, then we set $${\cal E}^j_x\equiv \cup_{x'\in m^{(j-1)}_x}{\cal E}^{j-1}_{x'}\Eq(2.28ter)$$ >From \equ (2.28ter) we construct iteratively ${\cal E}^n_x \subset S $\par If we define $$\bar S^{(n)}=\cup_{x\in S^{(n)}}{\cal E}^n_x \Eq(2.28quater)$$ we have immediately: $$\bar S^{(1)}\equiv M, \qquad \bar S^{(i)}\subseteq \bar S^{(i-1)}\Eq(2.29)$$ and by iteration it is easy to see that: $$X_{Z^{n}_k}\in \bar S^{(n)}\quad \forall n=0, 1,....\Eq(2.30)$$ and $$\t_{\bar S^{(n)}}=Z^n_0\Eq(2.30bis)$$ Indeed \equ(2.30bis) immediately follows from a more general result: \bigskip {\bf Lemma 2.3}\par {\it For any $A\in S^{(n)}$ let ${\cal E}^n_A\equiv \cup_{x\in A}{\cal E}^n_x$, then $$\t_{{\cal E}^n_A}=Z^n_{\t^{(n)}_A}$$ }\bigskip {\bf Proof}\par The straightforward proof comes immediately from definitions \equ (2.28bis), \equ (2.28ter), \equ (2.28quater). \eop \bigskip The results stated in theorem 2.1 allow a control on the expectation of hitting times. We give here some results which enable us to control also in probability these random times.\par We first notice that for any set $Q\subset S$ we can define a chain $X^{Q}_t$ with almost absorbing states in $ Q^c$ as follows: $$P^{Q}(x,y)=P(x,y)\quad \hbox{ if } x\in Q$$ $$P^{Q}(x,y)=P(x,y) e^{-\b \D(Q)} \quad \hbox{ if } x\in Q^c,\, x\not= y \Eq (2.200)$$ where $\D(Q)>\sum_{y,z\in Q}\D(y,z)$ and $P^{Q}(x,x)$ is defined by normalization.\par As far as the first exit from the domain $Q$ is concerned, the two chains $X^{Q}_t$ and $X_t$, are completely equivalent (the superscript $Q$ denotes all the quantities related to the chain $X^{Q}_t$).\bigskip {\bf Proposition 2.1}\par {\it For any $Q\subset S$ and any integer $n$ let $(\bar S^{(n)})^Q$ denote the state space of the $n$-th renormalization of the above defined chain $X^{Q}_t$ ; let $$N=N(Q)\equiv \max \{N:\, Q\cap (\bar S^{(N)})^{Q}\not=\emptyset\}\Eq(2.31)$$ Then: \item{i)} for any $x\in Q\cap (\bar S^{(N)})^{Q}$ $$E_x\t_{Q^c} \asymp T_N$$ (see \equ (1.3) for the definition of $\asymp$) \item{ii)} for any $\a >0$ there exists $k=k(\a)>0$ such that for any $x\in Q\cap (\bar S^{(N)})^{Q}$: $$P_x(T_N e^{-\a\b}\le\t_{Q^c}\le T_Ne^{\a\b})\ge 1-e^{-k\b} \Eq(2.31')$$ } \bigskip {\bf Proof}\par Point i) is an immediate consequence of theorem 2.1. Indeed since the events considered in this proposition belong to the $\s$-algebra ${\cal F}_{\t_{Q^c}}$, generated by the events depending on the process up to time $\t_{Q^c}$, we can consider the chain $X^{Q}_t$ instead of the chain $X_t$, and thus $Q^c\subset (\bar S^{(N+1)})^{Q}$. On the other hand, since $Q\cap(\bar S^{(N+1)})^{Q}=\emptyset$, this implies $Q^c=(\bar S^{(N+1)})^{Q}$. For notation convenience we will omit from now on in this proof the superscript $Q$: only the chain $X^{Q}_t$ is considered here; as we noticed above, the same estimates hold for the chain $X_t$.\par By iterating $N$ times Theorem 2.1 we obtain: $$E_x\t_{Q^c}\asymp t_1.t_2....t_N. E_x^{(N)}\t^{(N)}_{Q^c}\asymp T_N$$ since $Q\cap \bar S^{(N+1)}=\emptyset$ and thus $E_x^{(N)}\t^{(N)}_{Q^c}\asymp 1$.\par To prove ii) we first notice that by using Chebyshev's inequality we have immediately that for every $\a > 0$ there exists $ k>0$ such that: $$P_x(\t_{Q^c}>T_Ne^{\a\b})\le e^{-k\b}.$$ So we need only to prove that $ \forall \a >0$: $$P_x(\t_{Q^c}0\Eq(2.dis)$$ Since $Q^c=\bar S^{(N+1)}$, by \equ(2.30bis) the proposition is thus proved if \equ(2.dis) holds when we replace $\t_{Q^c}$ by $Z^{N+1}_0=Z^N_{\z_0^{(N)}}$. Since $x\in \bar S^{(N)}\backslash \bar S^{(N+1)}$ we have $\z_0^{(N)}\ge 1$ and thus the proposition is proved if we prove the following more general result: \bigskip {\bf Lemma 2.4}\par {\it For any $N\ge 1$ and for any sufficiently small positive constant $\a$ (i.e. such that $t_n e^{-\a\b}>1$ for all $n$) there exists a positive constant $k=k(\a,N)$ such that for any $x\in \bar S^{(N)}$ $$P_x(T_{N} e^{-\a\b}\le Z^{N}_1\le T_{N} e^{\a\b})\ge 1-e^{-k\b}$$ for any $\b$ sufficiently large. }\bigskip {\bf Remark}\par In the application of this lemma we are not interested in making the best choice of the constant $k(\a,N)$. We will prove the lemma with the crude choice $k(\a,N)={\a\over 2^N}$. \bigskip {\bf Proof of lemma 2.4}\par The proof is by induction. We first prove the initial step : $$P_x(t_1 e^{-\a\b}\le\z_1\le t_1 e^{\a\b})\ge 1-e^{-k\b}$$ By applying lemma 2.1 we have immediately: $$P_x(\z_1\le t_1 e^{-\a\b})\le P_x(\s_1l({1\over 2}-p))\le {l p(1-p)\over l^2 ({1\over 2} -p)^2}$$ if $\a$ is sufficiently small (but independent of $\b$) and $l\ge t_n e^{-{\a\b\over 2}}$ we obtain the estimate: $$P_x(Z^{n}_1T_n e^{+\a\b})$. \eop \bigskip We conclude this section with a result referring to the existence of a set of trajectories in $\Phi(S)$ associated to a given path in $\Phi(S^{(n)})$ on which the probability is concentrated. \bigskip {\bf Proposition 2.2}\par {\it Given $\phi^{(n)}\in\Phi(S^{(n)})$ and a time $T$ (independent of $\b$), let ${\cal T}_0(\phi^{(n)},T) \subset {\cal T}(\phi^{(n)},T) $ be defined by: $${\cal T}_0(\phi^{(n)},T)\equiv \{\phi\in {\cal T}(\phi^{(n)},T):$$ $$T_i e^{-\a\b}\le Z^i_k\le T_i e^{\a\b}\; \forall i,k \hbox{ such that } Z^i_k\le Z^n_T\, \hbox{ and } \forall \a \hbox{ sufficiently small}\}.$$ \bigskip Then for any $\phi\in {\cal T}(\phi^{(n)},T)\backslash {\cal T}_0(\phi^{(n)},T)$ we have : $$P(X_t=\phi_t,\quad \forall t\le T)\le e^{-k\b}$$ for some positive $k$ independenf of $\b$. } \bigskip {\bf Proof} \par The proof of this proposition is an easy consequence of lemma 2.4. \eop \numsec=3\numfor=1 \bigskip \bigskip {\bf Section 3. Graphs and cycles} \par \vskip.5cm In this section we recall the main results on the first exit problem proved by Freidlin and Wentzell in [FW], and we give a more general definition of cycles. We note that the results in [FW] are mostly formulated in the continuous case, i.e. for the study of a diffusion process defined by a stochastic differential equation in $\bf R^d$: $$dX_t = b(X_t)dt + \epsilon dW_t\Eq(3.1)$$ where $W_t$ is the d-dimensional Wiener process at time t and $\epsilon$ is very small. ($\epsilon ^2= {1\over \beta}$). The drift term b(.) is such that the deterministic flow $$ dX_t= b(X_t)dt\Eq(3.2)$$ has $\omega$-limit sets contained in a finite number of compact sets $K_1, K_2,.....,K_l$. \par We summarize here their results in the simpler case of a Markov chain satisfying the ergodicity property and {\it property ${\cal P}$} given in the introduction. \par Their analysis is based on the following:\bigskip {\bf Definition 3.1 (B-graphs)} : for any set of states $B\subset S$, a B-graph is a graph consisting of arrows $m\to n$ with $m\in B$ and $n\in S, \, m\not= n$ and satisfying the following properties:\par 1) every state $m\in B$ is the initial point of exactly one arrow \par 2) there are no closed cycles in the graph.\par Condition 2) can be replaced by:\par 2') for any state $m\in B$ there exists a sequence of arrows leading from it to some point $n\in B^c$.\par In other words a graph is a forest of trees with roots in $B^c$ and with branches given by arrows directed to the root (i.e. the set $B^c$ is the target of the sequences of arrows).\par The set of B-graphs is denoted by G(B); for any graph $g\in G(B)$ we define $\pi (g) = \prod_{m\to n \in g} P(m,n)$. \par By using this graphic formalism Freidlin and Wentzel in [FW] prove the following lemmas. \bigskip {\bf Warning}:\par Our notation is opposite with respect to that used in [FW], where a $W$-graph was a graph with target $W$ , i.e. a $W^c$-graph in our notation. \bigskip {\bf Lemma 3.1} ( FW ) \par {\it The invariant measure of the Markov chain $X_t$ : $\m (i),\, i\in S$ is given by : $$\m (i) = {q_i\over \sum_{j\in S} q_j}$$ where $$q_i= \sum_{g\in G\{S\backslash i\}} \pi (g)\Eq(3.3)$$ }\bigskip {\bf Lemma 3.2} ( FW ) \par {\it For any $B\subset S$ let $\tau_B$ be the first hitting time to B, then for any $j\in B$ $$P_i(X_{\tau_B} = j) = {\sum_{g\in G_{ij}(B^c)}\pi (g)\over \sum_{g\in G(B^c)}\pi (g)} \Eq(3.4)$$ where for any $i\in B^c$ and $j\in B$ we denote by $G_{ij}(B^c)$ the set of $B^c$-graphs in which the sequence of arrows leading from $i$ into B ends at the point $j$ (i.e. $i$ belongs to the tree with root $j$). }\par \bigskip {\bf Lemma 3.3}( FW ) {\it \par $$E_i\tau_B = { \sum_{g\in G(B^c\backslash \{i\})}\pi (g) + \sum_{j\in B^c, \, j\not= i} \sum_{g\in G_{ij}(B\backslash \{j\})} \pi (g)\over \sum_{g\in G(B^c)}\pi (g)}=$$ $$= { \sum_{g\in G(i\not\to B)}\pi (g)\over \sum_{g\in G(B^c)}\pi (g)} \Eq(3.5)$$ where $G(i\not\to B)$ is the set of graphs (without closed loops) containing $| B^c| -1$ arrows $m\to n$ each one emerging from a different point $ m\in B^c $ and with $ n\in S, \, m\not= n $ and not containing chains of arrows leading from $i$ into $B$. }\bigskip Lemma 3.1 is easily proved by showing that the quantities $q_i$ satisfy the stationarity equation, Lemmas 3.2 and 3.3 can be proved by induction over the number of states contained in $W^c$. (See [FW], pg.179,182).\par \bigskip By using property ${\cal P}$ these results can be reformulated as follows (see [FW]). Consider the problem of the first exit of our chain $X_t$ from a domain $Q\subset S$ and let $ \t_{Q^c}$ be the first exit time from the domain Q. \par\bigskip {\bf Proposition 3.1} (FW ) { \it \par For any $\d >0$ and for any sufficiently large $\beta $ there exists $\delta >0$ such that $$e^{-\beta (W_Q(x,y)-W_Q + \delta)} \le P_x(X_{\t_{Q^c}} = y) \le e^{-\beta (W_Q(x,y)-W_Q - \delta)}\Eq(3.7)$$ for any $x\in Q$ and $y\in Q^c$, with $$W_Q(x,y) = \min_{g\in G_{xy}(Q)}W(g) \Eq(3.8)$$ $$W_Q = \min_{g\in G(Q)}W(g)\Eq(3.9)$$ $$W(g)\equiv \sum_{m\to n\in g}\D (m,n)\Eq(3.9a)$$ and $\delta \to 0 $ as $\beta\to \infty$. }\bigskip {\bf Proposition 3.2} (FW ) {\it \par For any $x\in Q$ let $Y_x$ be the set of states in $Q^c$ such that there exists al least a graph minimizing \equ(3.9) and containing the sequence of arrows $x\to .......\to y$. Then with probability converging to one as $\beta $ tends to infinity the first exit from the domain Q of the process starting at x take place in $Y_x$.(See theorem 5.2, ch.6 in [FW]).\par }\bigskip {\bf Proposition 3.3} (FW ) {\it \par For any $x\in Q$: $$ \lim _{\beta \to \infty}{1\over \beta}\ln E_x \t_{Q^c} = W_Q - M_Q(x)\Eq(3.10)$$ where $$M_Q(x) = \min_{g\in G(x\not\to Q^c)} W(g) \Eq(3.11)$$ }\bigskip Let us now suppose that the set $Q$ contains a unique stable state $x_0$ completely attracting this set, i.e. for each $y\in Q$ there exists a path $y_0=y,y_1,....,y_n=x_0$ such that $\D (y_1,y_{i+1})=0\quad \forall i0$ for each $y\in Q, z\in Q^c$. Then in this case Freidlin and Wentzell can describe in complete detail the exit from $Q$.\par First of all in this case the quantities \equ(3.4) and \equ(3.5) can be easily estimated as follows (see Th. 2.1 and Th.4.1 ch 4 [FW]): for all $x\in Q$ $$\lim_{\b\to\infty}{1\over\b}\ln E_x \tau_{Q^c} = \min_{y\in Q^c} V(x_0,y)$$ where $V(x_0,y)$ is defined by \equ(2.4), and if there exists a unique state $y_0\in Q^c$ such that $V(x_0,y_0)= \min_{y\in Q^c} V(x_0,y)$ then $$\lim_{\b\to\infty}P_x(X_{\tau_{Q^c}}=y_0)=1$$ Moreover in this case of a domain $Q$ containing a unique stable state, the last escape is described quite precisely and completely in [FW].\par We state now their result in our discrete case of Markov chains (see [FW] Th.2.3, ch 4 for the continuous version of this result).\par We want to notice here that in the continuous case of diffusion processes discussed in [FW], the dynamics corresponding to zero random noise, was given by a dynamical system, that is the unperturbed system was completely deterministic and for each starting point there was a unique deterministic path emerging from it. The tube of typical exiting trajectories was given, in that case, as a neighborhood, in the uniform topology, of such a deterministic path.\par Here, in our present case with finite state space, the situation is different and, even for $\b=\infty$, the system can still be random. This means that there is not a unique deterministic path but several possible paths emerging from the same starting point. Moreover, we do not have to consider a neighborhood since the space is discrete. So the typical exiting tube, in this case, is a finite set of individual paths. \bigskip {\bf Proposition 3.4}\par {\it Let $Q$ be a set of states containing a unique stable state $x_0$ and, for each given $\alpha$ and $\b$, define $$\Phi_{\a\b}\equiv \{ \{\phi_s\}_{s\in {\bf N}}:\, \exists \;T_{\phi}< e^{\alpha\beta}, \phi_0=x_0,\,\phi_{T_{\phi}} \in Q^c,\, \phi_s\in Q,\, \forall s1$, the following are equivalent: \bigskip \item{i)} $C$ is a cycle \item{ii)} for any cycle $C'$ contained in $C$ the succesor set (see \equ(3.15)) satisfies: $$R_{C'}\subset C$$ \item{iii)} there exists $K>0$ such that for every $x\in C$ , $B\subset C,\, x\not\in B$ and $\b$ sufficiently large we have: $$P_x(X_{\t_{C^c\cup B}}\not\in B)W_{C \backslash B}$.\par \bigskip iii)$\to $ ii):\par Suppose ii) is false, i.e. there exists a cycle $C'\subset C$ such that $R_{C'}\not\subset C$. Then by applying again Proposition 3.1 we get that for any $x\in C'$ and $B\subset C\backslash C'$ \equ(4.7) is not verified, since $$P_x(X_{\t_{C^c\cup B}}\not\in B)\ge P_x(X_{\t_{(C')^c}}\in R_{C'}(x) \cap C^c)\ge e^{-\b\d}$$ for any $\d>0$.\par \bigskip iii)$\to$ iv):\par To prove that $E_x\t_{C^c}$ does not depend on $x$, in the sense of logarithmic equivalence, let us apply Proposition 3.3 and proposition 4.2 b). The dependence on $x$ , by \equ (3.10) is in the quantity $M_C(x)$ which involves the set of graphs $G(x\not\to C^c)$. Since $G(x\not\to C^c)\subseteq \cup _{ y\in C} G(\setminus y)$, by Proposition 4.2 b) we get the result. \par To prove \equ(4.8) for any $B\subset C$ and $x\in B$ we consider the following identity $$E_x\t_{C^c} = E_x\t_{C^c}[\chi(X_{\t_{B^c}}\in C) + \chi(X_{\t_{B^c}}\not\in C)]=$$ $$=E_x\t_{B^c}\chi(X_{\t_{B^c}}\not\in C)+ E_x\chi(X_{\t_{B^c}}\in C)(\t_{B^c}+E_{X_{\t_{B^c}}}\t_{C^c})=$$ $$=E_x\t_{B^c}+ E_x\chi(X_{\t_{B^c}}\in C)E_{X_{\t_{B^c}}}\t_{C^c}\Eq(4.9)$$ and, by using that $E_x\t_{C^c}$ is logarithmically equivalent to $E_y\t_{C^c} \; \forall x,y \in C $ , we obtain $$E_x\t_{C^c}(1-P_x(X_{\t_{B^c}}\in C))=E_x\t_{B^c}$$ that is $$E_x\t_{C^c}P_x(X_{\t_{B^c}}\not\in C)=E_x\t_{B^c}\Eq(4.9bis)$$ \equ(4.8) is then a consequence of iii) \bigskip iv) $\to$ iii):\par Suppose now that $E_x\t_{C^c}$ is logarithmically independent of $x\in C$ and that \equ(4.8) is verified. Then by identity \equ(4.9bis) we conclude the proof. \eop \bigskip \vskip.5cm As it has been proved in [OS] for the reversible case, a consequence of the recurrence property of cycles is the exponential distribution of their first exit times. \bigskip {\bf Proposition 4.4} {\it \par If $C$ is a cycle then for any $x,y \in C, \; \d > 0$, we have: $$\lim_{\b\to\infty}P_x(E_y\t_{C^c}e^{-\d\b}\le \t_{C^c}\le E_y\t_{C^c}e^{+\d\b})=1 \Eq(4.10)$$ and the probability distribution of $\t_{C^c}$, when suitably renormalized, is asymptotically exponential as $\b\to\infty$. More precisely let $T_{\b}$ be such that $$\sup_{x\in C} P_x(\t_{C^c}>T_{\b})=e^{-1}\Eq(4.11)$$ then, $\forall \; x \;\in \;C$ $$\lim_{\b\to\infty} {E_x\t_{C^c}\over T_{\b}}=1 \Eq(4.12)$$ and $\forall \; x \;\in \;C, \;\forall \; s\;\in \;{\bf R}^+:$ $$ \lim _{\b \to \infty } P_x ( {\t _{ C^c} \;\over T_{\b}} > \;s\;) =\; e^{-s}. \Eq(4.13) $$ }\bigskip {\bf Proof}\par To prove \equ(4.10) we first prove that if $N=N(C)$ is defined as in \equ(2.31) and if $\bar x\in C\cap(\bar S^{(N)})^c$ then for any $x\in C$ we have: $$P_x(T_N e^{-\d\b}\le \t_{C^c}\le T_N e^{\d\b})\ge P_{\bar x}(T_N e^{-\d\b}\le \t_{C^c}\le T_N e^{\d\b})- e^{-k\b}\Eq(4.13a)$$ Once \equ (4.13a) is proven we get, by applying Proposition 2.1 to the set $C$ : $$\lim_{\b\to\infty}P_x(E_x\t_{C^c}e^{-\d\b}\le \t_{C^c}\le E_x\t_{C^c}e^{+\d\b})=1 \Eq(4.13a')$$ and then \equ (4.10) since $E_x \t_{C^c}$ is logarithmically independent of $x$.\par We have, for $0< \d <\eta$ and $\b$ sufficiently large : $$P_x(T_N e^{-\d\b}\le \t_{C^c}\le T_N e^{\d\b})\ge$$ $$\ge P_x(\{T_N e^{-\d\b}\le \t_{C^c}\le T_N e^{\d\b}\}\cap \{\t_{\bar x}<\t_{C^c}\}\cap \{\t_{\bar x}< T_N e^{-\eta\b}\})\ge$$ $$\ge P_x(\{\t_{\bar x}<\t_{C^c}\}\cap \{\t_{\bar x}< T_N e^{-\eta\b}\}) P_{\bar x}(T_N e^{-\d'\b}\le \t_{C^c}\le T_N e^{\d'\b})\Eq(4.14a)$$ Now, since: $$P_x(\{\t_{\bar x}<\t_{C^c}\}\cap \{\t_{\bar x}< T_N e^{-c\b}\})\ge 1- P_x(\t_{\bar x}\ge\t_{C^c})- P_x(\t_{\bar x}\ge T_N e^{-c\b})\Eq(4.13b)$$ from Proposition 4.3 iii), iv), and Chebishev's inequality we get \equ(4.13a) and then \equ (4.10).\par Once \equ(4.10) is proved, the convergence to an exponential distribution with a renormalization factor independent on $x \in C$ (see \equ(4.11), \equ(4.12), \equ(4.13)) can be proved along the same lines as in [OS]. \eop \bigskip \bigskip We conclude this section by giving some properties of cycles connecting them to the renormalization procedure of section 2. \par More precisely the aim of the remaining part of this section is to associate to each state $x^n\in S^{(n)}$ a cycle $C_{x_n}$ for the original chain $X_t$ representing the region of the state space $S$ corresponding to the renormalized state $x^n$ under the time rescaling $T_n$. The precise statement of this correspondence will the subject of the next section (see in particular Theorem 5.1). \bigskip First of all we will define the {\it generalized basin of attraction} of each state and we will prove their main properties. Finally, by using these properties, we will be able to define the particular cycles $C_{x^n} \; \forall \; x^n \in S^{(n)} $. \par We recall, once again, that the superscript $^{(n)}$ denote quantities related to the chain $X^{(n)}$. We will denote by $x^n,y^n$ elements of the space $S^{(n)}$ and by $m^{(n-1)}_{x^n}$ the set of equivalent states in $M^{(n-1)}\subseteq S^{(n-1)}$ (with respect to the equivalence relation $\sim^{(n-1)}$) corresponding to the equivalence class of $x^n$. \bigskip {\bf Definition 4.1 }:\par For any $n\ge 1$ and for any $x^n\in S^{(n)}$ we define\par the {\it basin of attraction} of $x^n$ as the subset of $S^{(n-1)}$ given by: $$B^{(n-1)}_{x^n}:=\{z^{n-1}\in S^{(n-1)}: \; \exists y^{n-1}\in m^{(n-1)}_{x^n}:\, V^{(n-1)}(z^{n-1},y^{n-1})=0\}$$ {\bf Definition 4.2}\par We say that a state $x\in S$ {\it is connected by a steep path} to $x^n\in S^{(n)}$ if and only if there exists a sequence of states of increasing stability $y^i\in S^{(i)}; \; i=0, \dots, n ,$ such that $y^0=x,\, y^n=x^n $ and $$y^i\in B^{(i)}_{y^{i+1}}\quad \forall i=1,...,n-1\Eq ( 4.3s)$$ {\bf Definition 4.3}\par Given $x^n \in S^{(n)}$, we define the {\it generalized basin of attraction} (GBA) of $x^n$ at level $n$ as the subset of $S$ given by: $$\bar{\cal B}^n_{x^n}:=\{x\in S \hbox{ connected by a steep path to } x^n \}$$ We can also define a GBA for a set of equivalent states (i.e. a "plateau") instead of a single state.\par In the following we will often use the short notation $p^{(n)}$ to denote a plateau $m^ {(n)} _{x^{n+1}}$ for some $x^{n+1}$. We recall that $p^{(n)}$ is made of stable points of $S^{(n)}$ : $p^{(n)} = (x^{n+1}) _{\sim n}$ with $(x^{n+1} \in M^{(n)})$.\par We define: $$\bar{\cal B}^n_{p^{(n)}}=\cup_{y^n\in p^{(n)}}\bar{\cal B}^n_{y^n}$$ \bigskip {\bf Remarks}\par It is immediate to verify that $$\bar{\cal B}^n_{x^n}=\cup_{x_l^{n-1}\in B^{(n-1)}_{x^n}} \bar{\cal B}^{n-1}_{x_l^{n-1}}$$ It is also immediate to verify that for each $x\in {\cal E}^n_{x^n}$ we have $x\in \bar{\cal B}^n_{x^n}$ and that for any $y\in {\cal E}^n_{y^n}$, with $y^n\not= x^n$ we have $y\not\in \bar{\cal B}^n_{x^n}$.\par On the other hand we notice that for any $n\ge 1$ the GBA's $\bar{\cal B}^n_{x^n}$ define a covering of the space $S$ for $x^n\in S^{(n)}$. Different GBA's, say $\bar{\cal B}^n_{x_1^n}$, $\bar{\cal B}^n_{x_2^n}$, whith $x_1^n,x_2^n\in S^{(n)}$, can partially overlap since there may exist "saddle" states decaying to different equilibrium states.\par We used a superscript $^n$ in the definition of GBA's to emphasize that it depends on the index $n$. More precisely if a state belongs to two different state spaces $x\in S^{(n)}$ and $x\in S^{(n+1)}$ then we have ${\cal B}^{n}_x\subseteq {\cal B}^{n+1}_x$. \bigskip {\bf Definition 4.4}\par We will define the {\it strict generalized basin of attraction} (SGBA) of $x^n$, the set given by $${\cal B}^n_{x^n}:= (\cup_{y^n\in S^{(n)},\, y^n\not= x^n} \bar{\cal B}^n_{y^n} )^c$$ For any plateau $p^{(n)}\in S^{(n)}$ we analogously define $${\cal B}^n_{p^{(n)}}:= (\cup_{y^n\in S^{(n)}\backslash p^{(n)}} \bar{\cal B}^n_{y^n} )^c$$ \bigskip {\bf Definition 4.5}\par For any $x\in \bar{\cal B}^n_{x^n}$, we say that the process $X_t$, starting from $x$, {\it falls to the bottom $ x^n$} if the following event takes place: there exists a sequence $y^0, y^1,...$ satisfying \equ (4.3s), with $y^0=x, \, y^n=x^n$ such that $$X_{\t_{\bar S^{(i)}}}\in {\cal E}^i_{y^i}\quad \forall i\le n$$ \bigskip One can show that with large probability starting from any state $x$ the process first reaches the bottom of its SGBA. More precisely : \bigskip {\bf Proposition 4.5} {\it \par Let $ x^n\in S^{(n)}$, for each $x\in{\cal B}^n_{ x^n}$ we have $$P_x(\hbox{ the process falls to the bottom } x^n) \ge 1- e^{-K\b}\Eq(4.0s)$$ which implies: $$P_x(X_{\t_{\bar S^{(n)}}}\in {\cal E}^n_{ x^n})\ge 1-e^{-K\b}\Eq(4.1s)$$ and $$P_x(\t_{\bar S^{(n)}}\preceq T_{n-1})\ge 1-e^{-K'\b}\Eq(4.2s)$$ for some $K,K'>0$ independent of $\b$.\par Moreover, for any $x\in S$ and for any $n\ge 1$ let $x_1^n,\,x^n_2,....,x^n_i$ be the set of all the states in $S^{(n)}$ such that $x\in \bar{\cal B}^n_{x^n_j}$. Then $$P_x(\hbox{ the process falls to the bottom } x^n_j \hbox{ for some } j=1,..i) \ge 1- e^{-K\b} \Eq(4.3stop)$$ }\bigskip {\bf Proof}\par The proof immediately follows from the definition of SGBA. Suppose that the process starting from $x$ does not fall into $x^n$. For each trajectory of the process $X_t$, we can define a sequence of states of increasing stability as follows: $x^0=x$, and for each $i\ge 1$ we take $x^i\in S^{(i)}$ such that $ X_{\t_{\bar S^{(i)}}}\in {\cal E}^i_{x^i}$. If the process does not fall to $x^n$, there must be a state $x^i$ of this sequence such that $i\le n$ and $x^{i-1}\not\in B^{(i-1)}_{x^i}$. This means that the sequence $X^{(i-1)}_s,\, s=0,1,2,..$, that we can construct on the trajectory of the process (see def. 2.1), does not follow a path of zero cost to reach a stable state. By using lemmas 2.1 and 2.2 one can easily complete the proof. Equations \equ(4.2s), \equ (4.3stop) follow from proposition 2.1\eop \bigskip {\bf Remark} If we define the {\it fall to the bottom} $p^{(n)}$ as the following event: there exists a sequence $y^0, y^1,...$ satisfying \equ(4.3s), with $y^0=x, \, y^n\in p^{(n)}$ such that $$X_{\t_{\bar S^{(i)}}}\in {\cal E}^i_{y^i}\quad \forall i\le n$$ then, by using the definition of SGBA of a plateau, it is immediate to prove that with probability of order one the process falls to the bottom $p^{(n)}$, i.e. the statement of proposition 4.5 holds even in the case of a plateau. \bigskip We can prove something more: first of all the mean exit time from a SGBA is exponentially large, namely:\par \bigskip {\bf Proposition 4.6} {\it \par For any $n\ge 1$, for any $x_0^n\in S^{(n)}$ and for any $x_0\in {\cal E}^n_{ x_0^n}$: $$\lim_{\b\to\infty}{1\over \b}\ln E_{x_0}\t_{({\cal B}^n_{x^n_0})^c} = V_1+...+V_n+V^{(n)}_{x_0^n}$$ where $V_i\quad i=1,...,n$ are defined by \equ(2.20) and \equ(2.17) and $$V^{(n)}_{x_0^n}:= \lim_{\b\to\infty} {1\over \b}\ln E_{x_0^n}\t^{(n)} _{(x_0^n)^c}$$ (see \equ(2.17)). The same holds for SGBA of plateaux, i.e. by replacing the single state $x^n_0$ with a plateau $p^{(n)}$ where ${\cal E}^n_{p^{(n)}}=\cup_{x^n\in p^{(n)}}{\cal E}^n_{x^n}$. }\bigskip {\bf Proof }\par We define the set $D:=\cup_{y^n\in S^{(n)},\, y^n\not = x_0^n}{\cal E}^n_{y^n}$. By iteratively applying theorem 2.1 we have that for any $x_0\in {\cal E}^n_{x_0^n}$ $$E_{x_0}\t_{D}\asymp e^{(V_1+...+V_n+V^{(n)}_{x_0^n})\b}$$ To get the theorem we have only to prove that $E_{x_0}\t_{D}\asymp E_{x_0}\t_{({\cal B}^n_{x_0^n})^c}$. By definition $({\cal B}^n_{x_0^n})^c \supseteq D$. Suppose now that $$E_{x_0}\t_{D}\succ E_{x_0}\t_{({\cal B}^n_{x_0^n})^c}\Eq(4.abs)$$ We will prove that this implies $$P_{x_0}(\t_{D}0$ independent of $\b$ and $\y\to 0$ as $\b\to\infty$, against \equ (2.31').\par Indeed if the inequality \equ(4.abs) holds then there exists $d>0$ such that $$E_{x_0}\t_{D} e^{-{d\over 2}\b}\ge E_{x_0}\t_{({\cal B}^n_{x^n_0})^c} e^{{d\over 2}\b}$$ By proposition 2.1 applied to ${\cal B}^n_{x_0^n}$ we have that for any $d>0$ there exists $k(d) > 0$ such that $$P_{x_0} ( \t_{({\cal B}^n_{x^n_0})^c}\le E_{x_0}\t_{({\cal B}^n_{x^n_0})^c} e^{+d\b}) \ge 1-e^{-k(d)\b}\Eq(4.o)$$ To prove \equ(4.con) with $a=d/2$, since $E_{x_0}\t_{D}\succeq T_n$, it is thus sufficient to show that for any $y\in D^c\cap ({\cal B}^n_{x_0^n})^c$ there exists $y^n\not= x^n$ such that $y\in \bar{\cal B}^n_{y^n}$ and thus there exist $y^1,y^2,....,y^n$ such that, if $d$ is sufficiently small (independent of $\b$), we have $$P_y(\t_{{\cal E}^n_{y^n}} {T_n\over n} e^{-{a\over 2}\b})$ are superexponentially small. \par Exactly the same proof holds by replacing the state $x_0^n$ with a plateau $p^{(n)}$ by using the set $D:= S\backslash (\cup_{y^n\not\in p^{(n)}}{\cal E} ^n_{y^n})$. \eop \bigskip In order to relate cycles and GBA we give now two technical lemmas. Their proofs are in the Appendix. The first lemma contains a result on graphs and renormalization. The same result in the reversible and non degenerate case is given in [S2]. Here the presence of equivalent states makes the statement more complicated and the proof much longer. \bigskip {\bf Lemma 4.1} {\it \par For any $k\ge 1$ and for any set $D^k\subset S^{(k)}$ we consider an arbitrary set $D^{k-1}\subset S^{(k-1)} $ such that $$D^{k-1}\subseteq \cup_{x\in D^k}m^{(k-1)}_x\quad\hbox{ and }\quad m^{(k-1)}_x\cap D^{k-1}\not= \emptyset \quad \forall x\in D^k\Eq(4.a2)$$ Let $$Q^k:=S^{(k)}\backslash D^k$$ and $$Q^{k-1}:=S^{(k-1)}\backslash D^{k-1}$$ As in section 3 we define for any $k\ge 0$ $$W^{(k)}_{Q^k}:=\min_{g\in G^{(k)}(Q^k)}\sum_{i\to j\in g}\D^{(k)}(i,j)$$ and let $g^{(k)*}_{Q^k}$ be a graph (not necessarily unique) in $G^{(k)}(Q^k)$ minimizing $W^{(k)}_{Q^k}$.\par Then given a graph $g^{(k)*}_{Q^k}$ we can construct a graph $g^{(k-1)*}_{Q^{k-1}}$ minimizing $W^{(k-1)}_{Q^{k-1}}$ and we have $$W^{(k-1)}_{Q^{k-1}}=W^{(k)}_{Q^{k}}+V_k|Q^k|\Eq(4.oo)$$ Vice-versa, given two sets $D^k$ and $D^{k-1}$ satisfying \equ(4.a2), given a graph $g^{(k-1)*}_{Q^{k-1}}$ minimizing $W^{(k-1)}_{Q^{k-1}}$ we can construct a graph $g^{(k)*}_{Q^{k}}$ minimizing $W^{(k)}_{Q^{k}}$ and satisfying \equ(4.oo). }\bigskip \bigskip The SGBA's share with the cycles the property that with large probability the bottom $x_0$ is visited before the exit from ${\cal B}^n_{x^n_0}$. More precisely: \bigskip {\bf Lemma 4.2} {\it \par For any $n\ge 1$, for any $x_0^n\in S^{(n)}$ and for any $x_0\in $ ${\cal E}^n_{ x_0^n}$ any $({\cal B}^n_{x^n_0}\backslash x_0)$-graph minimizing $W_{{\cal B}^n_{x^n_0}\backslash x_0}$ (see eq. \equ(3.9)) has no arrows exiting from ${\cal B}^n_{x^n_0}$.\par The same holds for each stable plateau, i.e. $p^{(n)}\subset S^{(n)}$ with $V^{(n)}(x^n,y^n)>0$ for each $x^n\in p^{(n)},\, y^n\not\in p^{(n)}$. }\bigskip {\bf Remark}\par We note here that, due to Proposition 3.1, the statement of this lemma is equivalent to the following one: \par For any $n\ge 1$, for any $x_0^n\in S^{(n)}$ and for any $x_0\in {\cal E}^n_{ x_0^n}$ and $x\in {\cal B}^n_{x^n_0}$ we have $$P_x(X_{\tau_{({\cal B}^n_{x^n_0}\backslash x_0)^c}}\neq x_0) 0$.\par We stress that this result is stronger than proposition 4.5. In fact here {\it every} state $x_0\in {\cal E}^n_{ x_0^n}$ is visited before the exit from $ {\cal B}^n_{x^n_0}$. \bigskip \bigskip The following result is an easy consequence of lemma 4.2 :\bigskip {\bf Proposition 4.7} {\it \par Any cycle $C'\subset {\cal B}^{N}_{x_0^N}$ such that ${\cal E}^N_{x_0^N}\not\subset C'$ verifies $$R_{C'}\subset {\cal B}^{N}_{x_0^N}\Eq(4.spirale)$$ The same holds for stable plateaux, i.e. by replacing $x_0^n$ with $p^{(n)}$. }\bigskip {\bf Proof}\par Suppose \equ(4.spirale) is false and let $g^*_{C'}$ be a graph minimizing $W_{C'}$ and containing arrows ending outside ${\cal B}^{N}_{x_0^N}$. Moreover let $x_0'\in {\cal E}^N_{x_0^N}\cap C'^c$. If we consider now a graph $g^*_{{\cal B}^N_{x_0^N}\backslash x_0'}$ minimizing $W_{{\cal B}^N_{x_0^N}\backslash x_0'}$, we can construct a graph $g'$ coinciding with $g^*_{{\cal B}^N_{x_0^N}\backslash x_0'}$ for all the arrows with starting points in $({\cal B}^N_{x_0^N}\backslash x_0') \backslash C'$ and coinciding with $g^*_{C'}$ for the arrows starting in $C'$. The new graph $g'$, because of the argument of proof of Proposition 4.2 a) is indeed a $({{\cal B}^N_{x_0^N}\backslash x_0'})$-graph minimizing $W_{{\cal B}^N_{x_0^N}\backslash x_0'}$; since $g^*_{C'}$ has a unique arrow exiting from ${\cal B}^N_{x_0^N}$, $g'$ itself has an arrow exiting from ${\cal B}^N_{x_0^N}$ against the statement of Lemma 4.2. \eop \bigskip We prove now the main result of this section: \bigskip {\bf Proposition 4.8} {\it \par For any $x^n\in S^{(n)}$ there exists a cycle $C_{x^n} $ for the chain $X_t$ such that $$C_{x^n}\cap \bar S^{(n)} = {\cal E}^n_{x^n}$$ and $$V_{C_{x^n}}= V_1+...+V_n+V_{x^n}^{(n)}$$ $C_{x^n}$ turns out to be the maximum cycle containing ${\cal E}^n_{x^n}$ and contained in the SGBA of $x^n$: ${\cal B}^n_{x^n}$. }\bigskip {\bf Proof}\par For notational convenience we set, in this proof, ${\cal B}^n_{x^n} = B$. \par Suppose that for any $x_0\in {\cal E}^n_{x^n}$ we are able to show that the maximal cycle $C$ contained in $B$ and containing $x_0$ is such that: \item{i)} ${\cal E}^n_{x^n}\subseteq C$ \item{ii)}$V_C= V_B(x_0):=\lim_{\b\to\infty}{1\over \b}\ln E_{x_0}\t_{B^c}$ \par Then, by Proposition 4.6, we get the result. Point i) means that the cycle $C$ is the same for each $x_0\in{\cal E}^n_{x^n}$. To prove i) and ii) we fix $x_o\in {\cal E}^n_{x^n}$ and we consider the maximal rank $k$ of the maximal cycle $C$ contained in $B$: $C\subset B,\quad x_0\in C,\quad C\in {\cal C}^k$, where the maximality of the rank $k$ means that the cycle of rank $k+1$ containing $C$ is not contained in $B$.\par To prove i) we note that, as a consequence of proposition 4.7, the SGBA B is measurable with respect to the family ${\cal C}^k$ of cycles of rank $k$, i.e. $B=\cup_{i\in b}C^k_i$ where $b$ is a suitable set of indices and $C=C^k_j$ for some $j\in b$. Indeed, suppose ab absurdo that there is a $C'\in{\cal C}^k$, $\, C'\not= C$ with $C'\cap B\not= \emptyset$ and $C'\not\subset B$. Then there must be a cycle $C''\subset B$ with $R_{C''}\not\subset B$ against proposition 4.7.\par Thus not only $B$ is measurable with respect to ${\cal C}^k$ but also every $C^k_i\not= C$, $\quad i\in b$ has its successor in $B$: $R_{C^k_i}\subset B$. This means that if i) is not verified, i.e. if $C\not\supset {\cal E}^n_{x^n}$, then again by proposition 4.7, $R_C\subset B$ so that the descendents of $C$ are in $B$ and thus the cycle $C^{k+1}$ of rank $k+1$ containing $C$ is contained in $B$ against the hypothesis of maximality of $C$. This prove that i) holds and that $$R_C\cap B^c\not=\emptyset\Eq(4.4punti)$$ By i) we know that $V_C\le V_B(x_0)$. If now $V_C(x_0)=V_B(x_0)-2 a$ with $a>0$, we would have, using Proposition 2.1, $$P_{x_0}(\t_{B^c}< e^{\b V_C(x_0)+a})< e^{-K\b}$$ with $K=K(a)>0$; but, on the other hand, by \equ (4.4punti) we get: $$P_{x_0}(\t_{B^c}< e^{\b V_C(x_0)+a})\ge$$ $$\ge P_{x_0}(\t_{C^c}1$. \bigskip We can now define the {\it permanence set } $Q_{x^n}$ associated to each $x^n\in S^{(n)}$:\bigskip {\bf Definition 5.1}\par Among this set of cycles $\{C_i\}_{i=1,..,L}$ we will consider the maximal subset $\{C_i\}_{i\in {\cal I}}$, with ${\cal I}\subseteq \{1,...,L\}$ such that for any $i\in {\cal I}$ there exists a sequence $j_1(i),\,j_2(i),...j_m(i) \in {\cal I}$ with $j_1(i)=1,\, j_m(i)=i$, and $R_{C_{j_k(i)}}\cap C_{j_{k+1}(i)}\not=\emptyset$. Then we define the permanence set associated to $x^n$: $$Q_{x^n}= \cup_{i\in {\cal I}} C_i\Eq(5.2)$$ \bigskip The set $Q_{x^n}$ is the set of states visited by the chain $X_t$ in the interval of time corresponding to a transition $x^n\to y^n$ of the chain $X^{(n)}_t$. More precisely let $$\s^{(n-1)}:=\t^{(n-1)}_{(m^{(n-1)}_{x^n})^c}$$ and for any $T>0$ let $$\Phi^{(n-1)}(x^n,y^n,T):=\{\phi^{(n-1)}\in \Phi(S^{(n-1)})\quad\hbox{ such that }$$ $$\phi^{(n-1)}_0\in m^{(n-1)}_{x^n},\, \phi_T^{(n-1)}\in m^{(n-1)}_{y^n},\, \phi_i^{(n-1)}\not\in M^{(n-1)}\, \forall i=1,...,T-1\}$$ and let $Z^{n-1}_t$ be defined by \equ(2.28bbis).\par We have the following: \bigskip \def\zn{Z^{n-1}_{\s^{(n-1)}-1}} {\bf Theorem 5.1} {\it \par For any $a>0$ sufficiently small (see lemma 2.4), we define: $$A_1:=\{\zn\in [T_n e^{-a\b},T_n e^{a\b}]\}$$ $$A_2:=\{ \zn < \t_{(Q_{x^n})^c}\leq Z^{n-1}_{\s^{(n-1)}}\}$$ $$A_3:=\{\exists T,\, \phi^{(n-1)}\in \Phi^{(n-1)}(x^n,\,y^n, T) \hbox{ minimizing } I^{(n-1)}_{[0,T]} $$ $$\hbox{ such that } X_t\in {\cal T}(\phi^{(n-1)},T)\quad \forall t>\zn\}$$ $$G:=\{X_0^{(n)}=x^n,\quad X_1^{(n)}=y^n\}$$ There exists a positive constant $K$, depending on $a$ but independent of $\b$, such that for any sufficiently large $\b$ and for any $x\in {\cal E}_{x^n}^n$ we have : $$P_x(A_1\cap A_2\cap A_3|G)\ge 1- e^{-K\b} $$ Moreover if we add the hypothesis that $$\hbox {there exists } z^n\not= x^n \hbox { such that } P^{(n)}(x^n,z^n)\asymp 1, \Eq (5.2')$$ and if we define $$A_4:=\{\forall y\in C_{m^{(n-1)}_{x^n}}\quad \exists t<\zn \hbox{ such that } X_t=y\}$$ then we have, for any sufficiently large $\b$ and for any $x \in {\cal E}_{x^n}^n$: $$P_x(A_1\cap A_2\cap A_3\cap A_4|G)\ge 1- e^{-K\b}$$ }\bigskip {\bf Proof}\par We will prove that for each $i=1,...,4 $ we have $$P_x(A_i^c|G)\le e^{-K\b}$$ Let $|m^{(n-1)}_{x^n}|=m$, we have $$P_x(G)= \sum_{t=0}^{t_n-1}\sum_{z^{n-1}\in m^{(n-1)}_{x^n}} P_x( \{\s^{(n-1)}>t\}\cap \{X_{t}^{(n-1)}=z^{n-1}\}).$$ $$.\sum_{T}\sum_{\phi^{(n-1)}\in \Phi^{(n-1)}(x^n,y^n,T)}P_{z^{n-1}}(X^{(n-1)}_s =\phi^{(n-1)}_s\quad \forall s\le T)=$$ $$\sum_{t'=0}^{(t_n/m) -1} \sum_{t"=0}^{m-1}\sum_{z^{n-1}\in m^{(n-1)}_{x^n}} P_x( \{\s^{(n-1)}>mt'+t"\}\cap \{X_{mt'+t"}^{(n-1)}=z^{n-1}\}).$$ $$.\sum_{T}\sum_{\phi^{(n-1)}\in \Phi^{(n-1)} (x^n,y^n,T)}P_{z^{n-1}}(X^{(n-1)}_s =\phi^{(n-1)}_s\quad \forall s\le T)\Eq(5.a1)$$ Since $m^{(n-1)}_{x^n}$ is a class of stable equivalent states in $S^{(n-1)}$, we have by definition that for each pair of states in $m^{(n-1)}_{x^n}$ there is a path $\psi^{(n-1)}$ in $S^{(n-1)}$ connecting these states of length at most $m$ with $\psi^{(n-1)}_i\not= \psi^{(n-1)}_{i+1}$ and $I^{(n-1)}(\psi^{(n-1)})=0$, to which we can apply lemma 2.1 ii).\par In this way we obtain the following estimate: $$\sum_{t"=0}^{m-1} P_x( \{\s^{(n-1)}>mt'+t"\}\cap \{X_{mt'+t"}^{(n-1)}=z^{n-1}\})=$$ $$=\sum_{t"=0}^{m-1}\sum_{u^{n-1}\in m^{(n-1)}_{x^n}} P_x( \{\s^{(n-1)}>mt'\}\cap \{X_{mt'}^{(n-1)}=u^{n-1}\}).$$ $$. P_{u^{n-1}}( \{\s^{(n-1)}>t"\}\cap \{X_{t"}^{(n-1)}=z^{n-1}\})\ge$$ $$\ge e^{-\a\b} P_x( \{\s^{(n-1)}>mt'\})\Eq(5.b1)$$ By using \equ(5.b1) from \equ(5.a1) we obtain: $$P_x(G)\ge\sum_{t'=0}^{t_n/m -1} P_x( \s^{(n-1)}>mt') e^{-\a\b}.$$ $$.\sum_{z^{n-1}\in m^{(n-1)}_{x^n}}\sum_{T}\sum_{\phi^{(n-1)}\in \atop \Phi^{(n-1)} (x^n,y^n,T)}P_{z^{n-1}}(X^{(n-1)}_s =\phi^{(n-1)}_s\quad \forall s\le T)\Eq(5.a2)$$ Let us now consider the case $i=1$. We have: $$P_x(A_1^c|G)\le P_x(A_0^c|G)+P_x(A_0\cap A_1^c|G)$$ with $$A_0:=\{t_n>\s^{(n-1)}>t_n e^{-(a/2)\b}\}$$ We remark that $\{ \s^{n-1} > t_n\} \cap G = \emptyset$. \par We can estimate from above, by using the same expansion used to estimate $P_x(G)$ the following probabilities: $$P_x(A_0^c\cap G)=\sum_{t< t_n e^{-(a/2)\b}}\sum_{z^{n-1}\in m^{(n-1)}_{x^n} }P_x(\{\s^{(n-1)}>t\}\cap \{X_{t}^{(n-1)}=z^{n-1}\}).$$ $$.\sum_{T}\sum_{\phi^{(n-1)}\in \atop\Phi^{(n-1)}(x^n,y^n,T)}P_{z^{n-1}}(X^{(n-1)}_s =\phi^{(n-1)}_s\quad \forall s\le T)\le$$ $$\le \sum_{t< t_n e^{-(a/2)\b}}P_x(\s^{(n-1)}>t).$$ $$.\sum_{z^{n-1}\in m^{(n-1)}_{x^n}}\sum_{T}\sum_{\phi^{(n-1)}\in \atop\Phi^{(n-1)} (x^n,y^n,T)}P_{z^{n-1}}(X^{(n-1)}_s =\phi^{(n-1)}_s\quad \forall s\le T)$$ so that $$P(A_0^c|G)\le {\sum_{t< t_n e^{-(a/2)\b}}P_x(\s^{(n-1)}>t)\over \sum_{t'=0}^{t_n/m -1} P_x( \s^{(n-1)}>mt') e^{-\a\b}}\le {\sum_{t< t_n e^{-(a/2)\b}}P_x(\s^{(n-1)}>t)\over \sum_{t'=0}^{t_n/m e^{-(a/4)\b}} P_x( \s^{(n-1)}>mt') e^{-\a\b}} $$ $$\le {e^{-(a/4)\b}t_n\over e^{-\a'\b}t_n}$$ where $\a'\to 0$ as $\b\to\infty$ and we used Proposition 2.1 to get the last inequality .\par Let us consider the probability $P_x(A_0\cap A_1^c|G)$. Since for any $t\in [t_n e^{-(a/2)\b},t_n]$ we have that $$P_x(\{\zn T_{n}e^{a\b}\})\le$$ $$\le P_x(\{\zn t.T_{n-1}e^{(a/2)\b}\})$$ then proceeding like before we have $$P_x(A_0\cap A_1^c\cap G)\le$$ $$\le \sum_{t= t_n e^{-(a/2)\b}}^{t_n-1}\sum_{z^{n-1}\in m^{(n-1)}_{x^n}} P_x(\{\s^{(n-1)}>t\}\cap \{X^{(n-1)}_t=z^{n-1}\}\cap$$ $$[\{Z^{n-1}_tt.T_{n-1}e^{(a/2)\b}\}]).$$ $$\sum_{T}\sum_{\phi^{(n-1)}\in\atop \Phi^{(n-1)} (x^n,y^n,T)}P_{z^{n-1}}(X^{(n-1)}_s =\phi^{(n-1)}_s\quad \forall s\le T)$$ It is not difficult to extend the same argument of the proof of lemma 2.4 to obtain, for any $t \in {\bf N}$ the inequality: $$P_x(t.T_{n-1}e^{-(a/2)\b}\le Z^{n-1}_t\le t.T_{n-1}e^{(a/2)\b})\ge 1-e^{-k\b}$$ with $k=k(a)$, and thus we can prove as before that $P_x(A_0\cap A_1^c| G)$ is exponentially small. \bigskip Let us now go to the case $i=2$. We first observe that, by lemma 2.3, since $\bar{\cal B}^{n-1}_{ m_{x^n}^{n-1} } \cap \bar S ^{n-1} ={\cal E}^{n-1}_{m_{x^n}^{n-1}}$ we have that $Z^{n-1}_{\s^{(n-1)}}\ge \t_{(Q_{x^n})^c}$; thus, by using the same expansion used in the case $i=1$, we have only to prove that $P_x(\t_{(Q_{x^n})^c}<\zn)$ is exponentially small in $\b$.\par We have $$P_x(\t_{(Q_{x^n})^c}<\zn)\le$$ $$\le P_x(X_{\t_{(Q_{x^n})^c}}\not\in (\cup_{i\in {\cal I}} R_{C_i}))+ \sum_{z\in(Q_{x^n}^c\cap(\cup_{i\in {\cal I}}R_{C_i}))}P_z(X_{\t_{\bar S^{(n-1)}}} \in {\cal E}^{n-1}_{m^{(n-1)}_{x^n}})\Eq (5.*)$$ To estimate the first term in the r.h.s. of \equ(5.*) we first note that, by the definition of $C_{x^{n-1}}$ and $Q_{x^n}$, there exists at least an index $i_0\in {\cal I}$ such that $R_{C_{i_0}}\not\in Q_{x^n}$ and a sequence $j_1=1,....,j_k=i_0$ such that $$R_{C_{j_i}}\cap C_{j_{i+1}} \not= \emptyset\Eq(5.r)$$ On the other hand, since $C_i\subset {\cal B}^{n-1}_{m^{(n-1)} _{x^n}}$ for any $i\in {\cal I}$, for any $i\not= \{j_1,...,j_k\}$ there is a sequence satisfying again \equ(5.r) starting with $i$ and ending in $j_1,...,j_k$. By iterating this argument we can conclude that we can choose a sequence of graphs $g^*_{C_i}, \quad i\in {\cal I}$, minimizing, respectively, $W_{C_i}$ such that $$\cup_{i\in {\cal I}}\;g^*_{C_i}=:g_{Q_{x^n}}\Eq(5.m)$$ is a $Q_{x^n}$-graph. As it was noted in the proof of Proposition 4.2 we have, for any $g\in G(Q_{x^n})$: $$W(g)=\sum_{i\in {\cal I}}W(g\lceil_{C_i})$$ and since $g\lceil_{C_i}$ are $C_i$-graphs, we have $$W(g)\ge \sum_{i\in {\cal I}}W(g^*_{C_i})=\sum_{i\in {\cal I}}W_{C_i}$$ This implies that each $Q_{x^n}$-graph minimizing $W_{Q_{x^n}}$ has the form \equ(5.m) and thus $$R_{Q_{x^n}}\subset \cup_{i\in {\cal I}} R_{C_i}\Eq(5.**)$$ By means of the FW results (see lemma 3.2 and Proposition 3.2) we can then estimate the first term in the r.h.s. of \equ(5.*) with an exponentially small quantity.\par The second term in the r.h.s. of \equ(5.*) can be estimated by proposition 4.5 if we remark that, by construction, each point in $(Q_{x^n})^c\cap (\cup_{i\in {\cal I}} R_{C_i})$ belongs to $(\bar{\cal B}^{n-1}_{m^{(n-1)}_{x^n}})^c$. \bigskip Let us now consider the case $i=3$. As in the case $i=1$ we define an auxiliary event $$A'_3:=\{\bar\tau^{(n-1)}\le e^{\eta\b}\}$$ where $\eta$ is arbitrarily small and $$\bar\tau^{(n-1)}:=\min\{t>\s^{(n-1)}-1;\quad X^{(n-1)}_t\in M^{(n-1)}\}$$ We have $$P_x(A_3^c\cap G)\le P_x(A_3'^c\cap G)+P_x(A_3^c\cap A'_3\cap G)\Eq(5.c1)$$ By using the fact that the evnt $A_3'$ depends only on the process $X^{(n-1)}$ after the time $\s^{(n-1)}-1$ and by using again the expansion used to estimate $P_x(G)$, we immediately obtain a superexponentially small estimate of the first term in the r.h.s. of \equ(5.c1) by means of lemma 2.2 ii) applied to the chain $X^{(n-1)}_t$. The second term can be estimated from above as follows: $$P_x(A_3^c\cap A'_3\cap G)\le \sum_{t=0}^{t_n-1}\sum_{z^{n-1}\in m^{(n-1)}_{x^n}} P_x( \{\s^{(n-1)}>t\}\cap \{X_{t}^{(n-1)}=z^{n-1}\}).$$ $$.\sum_{T\le e^{\eta \b}}\sum_{\phi^{(n-1)}\in\atop \bar\Phi^{(n-1)}(x^n,y^n,T)}P_{z^{n-1}}(X^{(n-1)}_s =\phi^{(n-1)}_s\quad \forall s\le T)\Eq(5.c2)$$ where $$\bar\Phi^{(n-1)}(x^n,y^n,T)=$$ $$=\{\phi\in \Phi^{(n-1)}(x^n,y^n,T) \hbox{ such that } I_{[0,T]}^{(n-1)}(\phi)>\min_{\psi^{(n-1)}\in \Phi^{(n-1)}(x^n,y^n,T)}I_{[0,T]}^{(n-1)}(\psi)\}$$ and so, by applying lemma 2.1 iii) we obtain an exponentially small estimate for $P_x(A_3|G)$. \bigskip In the case in which there exists $z^n$ such that $P^{(n)}(x^n,z^n)\asymp 1$, we can also prove that $P_x(A_4^c| G)$ is exponentially small. In fact, in this case, by proposition 4.8 we have that $V_{C_{m^{(n-1)}_{x^n}}}=V_1+...+V_n$ and, with probability exponentially near to one, $\t_{C_{m^{(n-1)}_{x^n}}}\asymp\zn$. The proof thus follows immediately by using proposition 4.3 iv), the Chebyshev inequality and the expansion used to estimate $P_x(G)$.\eop \bigskip {\bf Remark}\par We note that, if $P^{(n)}(x^n,y^n)$ is exponentially small, i.e. if the transition $x^n\to y^n$ is against the flow, with theorem 5.1 we provide estimates from below of probabilities conditioned to an event, $G$, of exponentially small probability. This is the main difficulty of this theorem and for this reason we used in the proof explicit expansions.\par The case $P^{(n)}(x^n,y^n)\asymp 1$ is easier. Indeed the process is "falling" to $y^n$, and we are conditioning to an event of probability of order one. The results proved in th.5.1 can be stated in this case in the following form: \bigskip {\bf Theorem 5.2} {\it \par Let $x^n,\,y^n\in S^{(n)}$ be such that $P^{(n)}(x^n,y^n)\asymp 1$. If we define the following events: $$D_1:=\{T_n e^{-\a\b}\le \t_{(Q_{x^n})^c}\le T_n e^{+\a\b}\}$$ $$D_2:=\{\forall y\in C_{x^n}\quad \exists t<\t_{(Q_{x^n})^c} \hbox{ such that } X_t=y\}$$ $$D_3:=\{X_{\t_{(Q_{x^n})^c}}\in\bar{\cal B}^n_{y^n} \hbox{ and starting from }X_{\t_{(Q_{x^n})^c}},\, \hbox{the process falls to } y^{n}\}$$ $$G:= \{X^{(n)}_0=x^n,\,X^{(n)}_1=y^n\}.$$ Then for any $x\in {\cal E}^n_{x^n}$ we have: $$P_x(D_1\cap D_2\cap D_3|G) \ge 1-e^{-K\b}$$ for some $K>0$ independent of $\b$. }\bigskip {\bf Proof}\par By hypothesis $P_x(G)= P^{(n)}(x^n,y^n)\asymp 1$.\par By proposition 2.1, since the states in ${\cal E}^n_{x^n}$ are the most stable states contained in $Q_{x^n}$, we have immediately $$P(D_1^c|G)< e^{-K\b}\Eq(5.w1)$$ for some $K>0$. \par Since $\t_{(C_{{m^{(n-1)}_{x^n}}})^c}\le \t_{(Q_{x^n})^c}$ by proposition 4.3 iii) we have that $$P_x(D_2^c|G)\le e^{-K\b}\Eq(5.w2)$$ for some $K>0$.\par To get $P(D_3^c|G)< e^{-K\b}$ we notice that the probability that the process, starting from $X_{\t_{(Q_{x^n})^c}}$, visits ${\cal E}^n_{z^n}$ before ${\cal E}^n_{y^n}$, $ z_n \in S^{(n)} , z^n \neq y^n $, when conditioned to the event $G$, is zero. By using proposition 4.5 we conclude the proof of the theorem. \eop \bigskip {\bf Remark}\par The main difference between the statements of th.5.1 and 5.2 is that in th.5.1 we were considering times of the form $Z^{n-1}_t$, in order to be able to iterate the theorem itself to obtain a complete description of the transition $x^n\to y^n$ in terms of the original chain $X_t$.\par Here, in th.5.2 we are considering times of the form $\t_{(Q_{x^n})^c}$, since, as we will show in the following theorem, we will consider the iteration on the stability of the state to which the process is falling. Let $x^n\in S^{(n)}$ and $x\in \bar {\cal B}^n_{x^n}$.\par \bigskip {\bf Theorem 5.3} {\it \par Let $B^{(n-1)}_{x^n}\equiv x^{n-1}_1,....,x^{n-1}_l$. For each of these states $x_i^{n-1}$ there is at least a path $\bar\phi^{(n-1)}(x_i^{n-1})=\{\bar\phi^{(n-1)}_k\}_{k=0,...,T}$ in $ S^{(n-1)}$, with $$\bar\phi^{(n-1)}_0=x_i^{n-1},\, \bar\phi^{(n-1)}_T\in m^{(n-1)}_{x^n}\quad \hbox{ and }\quad P^{(n-1)}(\bar\phi_k^{(n-1)}, \bar\phi^{(n-1)}_{k+1})\asymp 1\Eq(5.z)$$ We define the following event: $$E:=\{\hbox{ there exist } x^{n-1}_i\in B^{n-1}_{x^n} \hbox{ and } \bar\phi^{(n-1)}(x_i^{n-1}) \hbox{ satisfying \equ(5.7) such that }$$ $$ x\in \bar{\cal B}^{n-1}_{x^{n-1}_i},\quad x \hbox{ falls to } x^{n-1}_i\hbox { and } X^{(n-1)}_s=\bar\phi^{(n-1)}_s\quad \forall s=0,...,T\}$$ Then we have $$P_x(E |x \hbox{ falls to }x^n)\ge 1-e^{-K\b}$$ }\bigskip {\bf Proof} \par The proof of this theorem is an immediate consequence of proposition 4.5 and lemmas 2.1 and 2.2. \bigskip \bigskip \noindent \numsec=6\numfor=1 {\bf Section 6 - The tube of exit}\par \bigskip Let us come now to the problem of the determination of the tube of exit. We will use the renormalization procedure and the results of the previous section to define the tube of typical exiting paths in terms of a sequence of permanence sets (see Def. 5.1).\par \bigskip We will use in this section the notation established in the previuos sections. A generic state in $S^{(n)}$ will be denoted by $x^n$, and a path in $S^{(n)}$ will be denoted by $\phi^n$. Since in this section states of different spaces $S^{(n)}$ will appear at the same time, we do not simplify the notation by omitting indices. With boldface letters, e.g. ${\bf y}$, we will denote sequences of states not necessarily belonging to the same state space. \bigskip Let $Q\subset S$ be an arbitrary domain. As it has been done in proposition 2.1 we can substitute our original chain $X_t$ with the chain $X^Q_t$ defined by \equ(2.200). Let $N=N(Q)$ be defined by \equ(2.31). We omit, from now on, the superscript $Q$ since only the chain $X^Q_t$ will be considered in the rest of this section. The characterization of the typical exit of the chain $X^{(N)}_t$ from the domain $Q\cap S^{(N)}$ is an easy problem since this domain does not contain stable states for the chain $X^{(N)}_t$ and so, with large probability, the chain $X^{(N)}_t$ exits from $Q\cap S^{(N)}$ in a time of order one by following a path falling to $Q^c$. \par For any $x^N\in Q\cap S^{(N)}$ we define the set of typical exiting paths starting from $x^N$: $$\Psi^{(N)}(x^N,Q^c):=\bigcup_{T=1}^{\infty}\{\phi_0^N,\phi_1^N,...,\phi_T^N \in S^{(N)}:\,$$ $$ \phi_0^N=x^N,\, \phi^N_T\in Q^c,\, \phi^N_t\not\in M^{(N)}\, \forall t=1,...,T-1 \quad \hbox{ and } I^{(N)}_{[0,T]}(\phi^N)=0\}\Eq(6.1)$$ By lemma 2.2 we have the following inequality: $$P_{x^N}(\exists \phi^N\in \Psi^{(N)}(x^N,Q^c) \,:\, X^{(N)}_t=\phi^N_t \quad \forall t\le T(\phi^N))>1-e^{-k\b}\Eq(6.1bis)$$ where $T(\phi^N)$ is the first hitting time to $Q^c$ of the path $\phi^N$. \par This can be called ``$N$-descent to $Q^c$" (in the reversible case the $N$-th renormalized energy function is decreasing on the paths in $\Psi^{(N)}(x^N,Q^c)$).\par As it was noted in section 2 of [OS], \equ(6.1bis) gives us a first knowledge about the exit of the chain $X_t$ from the domain $Q$, providing, in particular, the results obtained by Freidlin and Wentzell about the mean exit time and the most probable exit point. A first preliminary, quite rough version of the exit tube starting in ${\cal E}^N_{x^N}$ is thus given by the following union of paths: $${\cal T}:= \bigcup_{\phi^N\in \Psi^{(N)}(x^N,Q^c)}{\cal T}(\phi^N,T(\phi^N)) \Eq(6.2)$$ where ${\cal T}(\phi^N,T(\phi^N)) $ is defined in \equ(2.28).\par On the other hand each descending path $\phi^N\in\Psi^{(N)}(x^N,Q^c)$ can be analyzed in terms of paths of the chain $X^{(N-1)}$. An $N$-descent to $Q^c$ for the path $\phi^N$ will be a sequence of descents and ascents for the paths on the smaller scale $N-1$.\par Now we want to use the results of the previous sections to give more details on the typical exiting paths, in order to describe these sequences of descents and ascents up to the first (better zeroeth) level of the renormalization procedure (corresponding to the original chain). In this way we want to narrow the tube ${\cal T}$ as much as possible keeping a good control in probability. This will be achieved by describing, for each path $\{\phi^N\}_{i=1}^T$ appearing in \equ (6.2) the behaviour of the original process $X_t$ on the time intervals corresponding to each transition $\phi^N_i\to\phi^N_{i+1}$ at level $N$. We can proceed as follows: by applying Theorem 5.1 we can associate to each transition $\phi^N_i\to\phi^N_{i+1}$ a permanence set $Q_{\phi^N_i}$ and a set of paths $ \Psi^{(N-1)}$ in $\Phi(S^{(N-1)})$ defined by: $$\Psi^{(N-1)} (m^{(N-1)}_{\phi^N_i},m^{(N-1)}_{\phi^N_{i+1}}) :=\bigcup_{T=1}^{\infty}\{\phi_0^{N-1},\phi_1^{N-1},...,\phi_T^{N-1} \in S^{(N-1)}:\,$$ $$ \phi_0^{N-1}\in m^{(N-1)}_{\phi^N_i},\, \phi^{N-1}_T\in m^{(N-1)}_{\phi^N_{i+1}},\, \phi^{N-1}_t\not\in M^{(N-1)}\, \forall t=1,...,T-1 \quad \hbox{ and}$$ $$ I^{(N-1)}_{[0,T]}(\phi^{N-1})= \D^{(N)}(\phi^N_i,\phi^N_{i+1})+V_N\} \Eq(6.4)$$ To each transition at level $N-1$ we can associate, again by Theorem 5.1, a permanence set $Q_{\phi^{N-1}_j}$ and the set of paths $\Psi^{(N-2)}(\phi^{N-1}_k,\phi^{N-1}_{k+1})$, where, for any $n0$ and for each state $x^n\in S^{(n)}$ we define, as in \equ(5.2a), \equ (5.2b) the following events (sets of paths): $$A_1(x^n,a):=\{\phi\in \Phi(S) :\,\phi_0^{(n-1)}\in m_{x^n}^{(n-1)}\hbox{ and } Z^{n-1}_{\s^{(n-1)}-1}\in (T_n e^{-a\b},T_n e^{a\b})\}$$ $$A_2(x^n):=\{\phi\in \Phi(S):\, \phi_0^{(n-1)}\in m_{x^n}^{(n-1)} \hbox{ and } Z^{n-1}_{\s^{(n-1)}}\ge \t_{(Q_{x^n})^c}> Z^{n-1}_{\s^{(n-1)}-1}\}$$ where $$\s^{(n-1)}= \s^{(n-1)}(\phi):=\t^{(n-1)}_{(m^{(n-1)}_{x^n})^c}$$ The first step of our iterative construction is given by the following expression of ${\cal T}_N(x^N,Q^c)$: $${\cal T}_N(x^N,Q^c)=\bigcup_{{\bf y^N}\in \Psi^{(N)}(x^N,Q^c)} {\cal T}({\bf y^N},T({\bf y^N})) \Eq(6.42)$$ Then we define $${\cal T}_{N-1}(x^N,Q^c,a):=\bigcup_{{\bf y^N}\in \atop\Psi^{(N)}(x^N,Q^c)}\quad \bigcup_{{\bf y^{N-1}}\,ref \,{\bf y^N}}{\cal T}_{{\bf y^N},{\bf y^{N-1}}}$$ where $${\cal T}_{{\bf y^N},{\bf y^{N-1}}}:=\{\phi\in {\cal T}_N(x^N,Q^c):\, \hbox{ for each transition } \phi^{(N)}_i=({\bf y^N})_i\to \phi^{(N)}_{i+1}= ({\bf y^N})_{i+1}$$ $$\hbox{ the path $\phi$ on the corresponding interval of time } [Z^N_i,Z^N_{i+1}] \hbox{ belongs to }$$ $$ A_1(({\bf y^N})_i,a) \cap A_2(({\bf y^N})_i) \hbox{ and } \phi_t\in {\cal T}({\bf y^{N-1}_i},T({\bf y^{N-1}_i}))\quad \forall t>Z^N_i+Z^{N-1}_{\s^{(N-1)}-1}\}$$ \bigskip where ${\bf y^{N-1}_i}$ are the refining paths of ${\bf y^{N-1}}$. \par By iteration $${\cal T}_n(x^N,Q^c,a):=\bigcup_{{\bf y^N}\in \atop\Psi^{(N)}(x^N,Q^c)}\quad \bigcup_{{\bf y^{N-1}}\, ref \,{\bf y^N}}.... \bigcup_{{\bf y^{n}}\,ref \,{\bf y^{n+1}}} {\cal T}_{{\bf y^N},{\bf y^{N-1}}.....{\bf y^{n}}}$$ with $${\cal T}_{{\bf y^N},{\bf y^{N-1}}.....{\bf y^{n}}} := \{\phi\in {\cal T}_{{\bf y^N},{\bf y^{N-1}}.....{\bf y^{n+1}}}:\, \hbox{ for each transition of a refining path of }$$ $$ {\bf y^{n+1}}: \phi^{(n+1)}_i=({\bf y^{n+1}_k})_i\to \phi^{(n+1)}_{i+1}= ({\bf y^{n+1}_k})_{i+1}$$ $$\hbox{ the path $\phi$ on the corresponding interval of time belongs to } $$ $$A_1(({\bf y^{n+1}})_i,a) \cap A_2(({\bf y^{n+1}})_i) \hbox{ and } \phi_t\in {\cal T}({\bf y^{n}_k},T({\bf y^{n}_k}))\quad \forall t>Z^{n+1}_k+Z^{n}_{\s^{(N-1)}-1}\}$$ \bigskip where ${\bf y^{n}_k}$ are the refining paths of ${\bf y^{n}}$. \par Finally we obtain $${\cal T}_0(x^N,Q^c,a):=\bigcup_{{\bf y^N}\in \atop\Psi^{(N)}(x^N,Q^c)}\quad \bigcup_{{\bf y^{N-1}}\,ref \,{\bf y^N}}.... \bigcup_{{\bf y^{0}}\, ref \,{\bf y^{1}}} {\cal T}_{{\bf y^N},{\bf y^{N-1}}.....{\bf y^{0}}}=$$ $$=\bigcup_{{\bf y^N}\in \atop\Psi^{(N)}(x^N,Q^c)}\quad \bigcup_{{\bf y^{N-1}}\, ref \,{\bf y^N}}.... \bigcup_{{\bf y^{0}}\, ref \,{\bf y^{1}}} \{\phi \hbox{ visits the ordered sequence of sets }$$ $$ Q_{{\bf y^0}} \hbox{ and in each set $Q_{y_i^{n_i}}$ spends a time in } [T_{n_i}e^{-a\b},T_{n_i}e^{a\b}]\} \Eq(6.43)$$ \bigskip where we define $Q_{x^0}=x^0$ and $T_0=1$ if $x^0\in S$. \bigskip A first result on the typical exiting tube can thus be stated as follows: \bigskip {\bf Theorem 6.1}\par {\it For each positive $a$ there exists a positive constant $K$ such that for each sufficiently large $\b$ and for each $x\in {\cal E}^N_{x^N}$ we have} $$P_x(X_t\in {\cal T}_0(x^N,Q^c,a))\ge 1-e^{-K\b}$$ \bigskip {\bf Proof}\par The proof follows immediately by Theorem 5.1 if we note that for some positive $K', K''$ $$P_x(X_t\in {\cal T}_n(x^n,Q^c,a))=\sum_{{\bf y^N}\in \atop\Psi^{(N)}(x^N,Q^c)}\quad \sum_{{\bf y^{N-1}}\, ref \,{\bf y^N}}.... \sum_{{\bf y^{n+1}}\, ref \,{\bf y^{n+2}}}$$ $$ P_x(X_t\in {\cal T}_n (x^n,Q^c,a)\,|\,X_t\in {\cal T}_{{\bf y^N}...{\bf y^{n+1}}}) P_x(X_t\in {\cal T}_{{\bf y^N}...{\bf y^{n+1}}})\ge$$ $$\ge (1-e^{-K'\b})P_x(X_t\in {\cal T}_{n+1}(x^n,Q^c,a))$$ and $P_x(X_t\in {\cal T}_N(x^n,Q^c,a))\ge 1-e^{-K''\b}$ by \equ(6.1bis). \eop \bigskip Let us now make some remarks on this theorem.\par Given the sequence ${\bf y}={\bf y^0}$ consider each element $y_j^{n_j}$ belonging to a portion of the sequence where $n_j$ is monotonocally decreasing, i.e. such that $${\cal E}^{n_j}_{y_j^{n_j}}\subset {\cal E}^{n_{j-1}}_{y_{j-1}^{n_{j-1}}} \Eq(6.i)$$ By construction, \equ(6.i) implies that $n_j0$ there exists $K>0$ such that for any $\b$ sufficiently large and for any $x\in {\cal B}^N_{x^N}$} $$P_x(X_t\in{\cal T}(x,x^N))\ge 1-e^{-K\b}$$ If $x\in \bar{\cal B}^N_{x_i^N}\quad i=1,...,j(x)$ then $$P_x(X_t\in\bigcup_{i=1}^{j(x)}{\cal T}(x,x_i^N))\ge 1-e^{-K\b}$$ \bigskip By combining theorems 6.1 and 6.3 we complete our description of the tube of typical paths starting from each point $x$ up to the first exit from $Q$. Indeed if $x\in {\cal B}^N_{x^N}$ for some $x^N\in Q$ then the typical tube is just made of paths which are in ${\cal T}(x,x^N,a)$ up to the time $\t_{{\cal E}^N_{x^N}}$ and from this moment they are in the tube ${\cal T}(x^N,Q^c,a)$. We call it ${\cal T}(x,x^N,a)\circ {\cal T}(x^N,Q^c,a)$. If $x\in \bar{\cal B}^N_{x_i^N}\quad i=1,...,j(x)$ then we have to consider the tube $$\bigcup_{i\in[1,...,j(x)]:x_i^N\in Q}{\cal T}(x,x_i^N,a)\circ {\cal T}(x_i^N,Q^c,a) \bigcup_{l\in[1,...,j(x)]:x_l^N\in Q^c} {\cal T}(x,x_l^N,a)$$ Similarly to what we did before we can extract from the final sequence ${\bf y}$ a sequence ${\bf y'}$ and distinguish between primary and secondary information.\bigskip \bigskip {\bf Aknowledgements}\par We want to thank Gerard Ben Arous, Raphael Cerf and Alain Trouv\'e for stimulating discussions.\par One of us (E.S.) wants to thank the Physics Department of Universit\'a ``La Sapienza" for kind hospitality. \par This work has been partially supported by the grant CHRX-CT93-0411 of the Commission of European Communities.\bigskip \bigskip {\bf Appendix} \bigskip {\bf Proof of Lemma 4.1}\par The proof is organized as follows:\par \item{1)} First we consider a graph $g^{(k)*}_{Q^{k}}$ and we construct a graph $\bar g$ on $S^{(k-1)}$ satisfying property 2') of Definition 3.1 of $B$-graphs. \item{2)} As a second step we extract from $\bar g$ a $Q^{k-1}$-graph on $S^{(k-1)}:\, g^{(k-1)}_{Q^{k-1}}$ \item{3)} We show that $$W^{(k-1)}_{Q^{k-1}}\le W( g^{(k-1)}_{Q^{k-1}})=W^{(k)}_{Q^{k}}+V_k|Q^k| $$ \item{4)} Given a graph $g^{(k-1)*}_{Q^{k-1}}$ we construct a $Q^k$-graph on $S^{(k)}$: $g^{(k)}_{Q^k}$ \item{5)} We verify that $$W^{(k)}_{Q^{k}}\le W( g^{(k)}_{Q^{k}})=W^{(k-1)}_{Q^{k-1}}-V_k|Q^k| $$ \bigskip >From 3) and 5) we immediately obtain \equ(4.oo) and thus we can conclude that the graph $g^{(k-1)}_{Q^{k-1}}$ constructed in 1) and 2) minimizes $W^{(k-1)}_{Q^{k-1}}$ and the graph $g^{(k)}_{Q^k}$ constructed in 4) minimizes $W^{(k)}_{Q^{k}}$. \bigskip 1) By equation \equ(4.a2) we have that $Q^{k-1}$ contains all the unstable states of the chain $X^{(k-1)}_t$, say $S^{(k-1)}\backslash M^{(k-1)}$, and each state in $m_x^{(k-1)}$, if $x\in Q^k$. $Q^{k-1}$ possibly contains some states in $m_x^{(k-1)}$ with $x\in D^k$, but not all of them. \par For any $i\in Q^k$ let $m_i^{(k-1)}$ be the corresponding equivalence class in $S^{(k-1)}$. Given a graph $g^{(k)*}_{Q^k}$ we can now construct a graph $\bar g$ of arrows starting in states in $Q^{k-1}$ as follows:\par \item{i)} To each arrow in $g^{(k)*}_{Q^k}: \, i\to j$ we associate a sequence of arrows $x_1^{k-1}\to...\to x_l^{k-1}$ between states in $S^{(k-1)}$ such that $x_1^{k-1}\in m_i^{(k-1)}, x_l^{k-1}\in m_j^{(k-1)}$, $x^{k-1}_j\in S^{(k-1)}\backslash M^{(k-1)}$ and $x_1^{k-1}\to...\to x_l^{k-1}$ is a path minimizing $\D^{(k)}(i,j)$ (see \equ(2.24) and \equ(2.15)) \item{ii)} For any equivalent class $m_i^{(k-1)}, \; i\in Q^k$ let $i_0^{k-1}$ be a state which is starting point of an arrow constructed in the previous step i). For any other state in $m_i^{(k-1)}$ we can construct a sequence of arrows between points in $m_i^{(k-1)}$ leading to $i_0^{k-1}$. Such a sequence exists by definition of $\sim^{(k-1)}$ and for each one of such arrows the associated function $\D^{(k-1)}$ is zero. \item{iii)} Since $D^{k-1}\subset \cup_{x\in D^k} m_x^{(k-1)}$ it may happen that there are stable states in $Q^{k-1}$ (for the chain $X^{(k-1)}_t$) which werw not touched by the construction i) and ii). They must be equivalent to some state in $D^{k-1}$ and we can then draw a sequence of arrows from each of them to a state in $D^ {k-1}$ with a contribution zero to the quantity $W(\bar g)$. \item{iv)} Let us now consider the states in $Q^{k-1}$ which were not touched by the previous construction, i.e. which are not starting points of any arrow constructed in steps i),ii) and iii). These are unstable states. In this set of states we consider the equivalence classes with respect to the relation $\sim^{(k-1)}$, $c_i^{k-1}$. For each one of such equivalent classes, due to unstability, we can draw an arrow emerging from a state contained in it and ending outside it and corresponding to a zero value of the function $\D^{(k-1)}$. Moreover for each one of these equivalence classes we can find a sequence of such arrows of zero cost and leading to a state in $D^{k-1}$ or to a state considered in i), ii) or iii) (i.e. starting point of an arrow already drown). Inside each equivalence class $c_i^{k-1}$ we can draw arrows between equivalent states as in point ii).\bigskip In this way we have constructed a set of arrows, say $\bar g$, such that at least one arrow emerges from each state in $Q^{k-1}$ and condition 2') of Definition 3.1 of a $Q^{k-1}$-graph for the chain $X^{(k-1)}_t$, is satisfied.\bigskip 2) We will show now that $\bar g$ contains a $Q^{k-1}$-graph: $ g_{Q^{k-1}}^{(k-1)}$. This is a standard proof (see [S2], Th.1). In fact by the previous remark we have only to show that we can satisfy also condition 1) of Definition 3.1 of B-graphs, only by removing arrows in $\bar g$. This can be done with the following prescription: \bigskip a) introduce in the set of states $S^{(k-1)}\backslash D^{k-1}$ in an arbitrary order, $x_1, x_2, \dots$; set $g_0=\bar g$ and i=1\par b) since $g_{i-1}$ satisfies condition 2'), there is at least a sequence of arrows in $g_{i-1}$ leading from $x_i$ to some point in $D^{k-1}$; chose one of these sequences; let $x_i\to x'_i$ be its first arrow \par c) define $g_i$ as the set of arrows constructed starting from $g_{i-1} $ by erasing all the arrows exiting from $x_i$ different from $x_i\to x'_i$\par d) verify that $g_i$ satisfies condition 2') and every $x_j,\, j\le i$ is the initial point of exactly one arrow in $g_i$\par e) make $i\to i+1$ and go back to point b) \bigskip The graph $$ g_{Q^{k-1}}^{(k-1)}\equiv g_i \;\;\;\;\hbox {for }\;\; i =|Q^{k-1}|$$ is by definition a $Q^{k-1}$-graph included in $\bar g$, since it verifies conditions 1) and 2').\par \bigskip 3) By using the definition of $\D^{(k)}(.,.)$ we have: $$W_{Q^{k-1}}^{(k-1)}\le W(g^{(k-1)}_{Q^{k-1}})= \sum_{i\to j\in g^{(k-1)}_{Q^{k-1}}}\D^{(k-1)}(i,j) \le\sum_{i\to j\in \bar g}\D^{(k-1)}(i,j)\le$$ $$\le \sum_{i\to j\in g^{(k)*}_{Q^{k}}}(\D^{(k)}(i,j)+V_k)= W_{Q^k}^{(k)} + V_k |Q^k|$$ \bigskip 4) Let $g^{(k-1)*}_{Q^{k-1}}$ be a $Q^{k-1}$-graph minimizing $W_{Q^{k-1}}^{(k-1)}$. For each $i\in S^{(k)}$ let $m_i^{(k-1)}$ be its equivalent class. If $m_i^{(k-1)}\cap D^{k-1}=\emptyset$ then $i\in Q^k$ and in $g^{(k-1)*}_{Q^{k-1}}$ there is a unique arrow exiting from $m_i^{(k-1)}$. Indeed, if there were two arrows exiting from $m_i^{(k-1)}$ in $g^{(k-1)*}_{Q^{k-1}}$ we could construct a new $Q^{k-1}$-graph, $g'^{(k-1)}$, by changing only arrows starting in $m_i^{(k-1)}$ with $W(g'^{(k-1)})< W(g^{(k-1)*}_{Q^{k-1}})= W^{(k-1)}_{Q^{k-1}}$ contraddicting the fact that $W_{Q^{k-1}}^{(k-1)}$ is the minimum. \par This means that from the graph $g^{(k-1)*}_{Q^{k-1}}$ we can construct a $Q^k$-graph on $S^{(k)}$ by looking, for any $i\in Q^k$, at the sequence of arrows exiting from it and at the first state in $M^{(k-1)} $ hitted by this sequence. The set of transitions starting in states in $Q^k$ constructed in this way is a $Q^k$-graph, $g^{(k)}_{Q^k}$, since $g^{(k-1)*}_{Q^{k-1}}$ was a $Q^{(k-1)}$-graph. \bigskip 5) We have immediately $$W^{(k)}_{Q^k} \le W(g^{(k)}_{Q^{k}})= \sum_{i\to j\in g^{(k)}_{Q^{k}}}\D^{(k)}(i,j) \le$$ $$\le W(g^{(k-1)*}_{Q^{k-1}})- V_k|Q_k|$$ \eop \bigskip {\bf Proof of Lemma 4.2 }\par \bigskip The proof is based on Lemma 4.1.\par For any $x_0\in {\cal E}_{x_0^n}^n$ let $x_0^1\in S^{(1)},\, x_0^2\in S^{(2)}, \,...,\, x_0^n\in S^{(n)}$ be the sequence of renormalized states such that $x_0\in {\cal E}^i_{x_0^i}\; \forall i=1,...,n$.\par Let us first consider the chain at level $n-1$. The stable states of the chain $X^{(n-1)}_t$ contained in ${\cal B}^n_{x_0^n}$, say $y_1^{n-1}, \, y_2^{n-1},...,\,y_k^{n-1}$, are all contained in an equivalence class $m^{(n-1)}_{x_0^n}$, and one of them coincides with $x_0^{n-1}$ i.e. contains the point $x_0$. If we now consider the quantity $W^{(n-1)}_{ B_{x_0^n}^{(n-1)}\backslash x_0^{n-1}}$ we immediately obtain that it vanishes and each $(B_{x_0^n}^{(n-1)}\backslash x_0^{n-1})$-graph on $S^{(n-1)}$ minimizing this quantity has only arrows ending in $x_0^{n-1}$.\par Now, by iteratively applying lemma 4.1 with $k=n-l\quad l=1,2,...,n-1$ and $D^{n-1}=(B_{x_0^n}^{(n-1)}\backslash x_0^{n-1})^c$, $D^{k-1}=\cup_{x\in D^k}m_x^{(k-1)}\backslash x_0^{k-1}$ we conclude the proof of Lemma 4.2 in the case of a single state. \par The proof in the case of a stable plateau $p^{(n)}$ is exactly the same.\eop \vfill \eject \bigskip {\bf References}\par \item{[FW]} M.I.Freidlin, A.D.Wentzell, Random Perturbations of Dynamical Systems, Springer-Verlag 1984 \item{ [KO1]} R.Kotecky, E.Olivieri ``Droplet dynamics for asymmetric Ising model'' Preprint (1992). \item{ [KO2]} R.Kotecky, E.Olivieri ``Shapes of growing droplets- a model of escape from a matastable phase'' in preparation. \item{[NSch1]} E.J. Neves, R.H. Schonmann, ``Behaviour of droplets for a class of Glauber dynamics at very low temperatures'' Comm. Math.Phys. {\bf 137} 209 (1991). \item{[NSch2]} E.J. Neves, R.H. Schonmann, ``Critical Droplets and Metastability for a Glauber Dynamics at Very Low Temperatures'', Prob.Theor.Rel.Fields {\bf 91}, 331 (1992) \item{[OS]} E. Olivieri, E. Scoppola, `` Markov chains with exponentially small transition probabilities: First exit problem from a general domain -I. The reversible case'' Preprint. \item{[S1]} E.Scoppola `` Renormalization group for Markov chains and application to metastability'', Jour. Stat. Phys. {\bf 73}, 83 (1993) \item{[S2]} E.Scoppola `` Renormalization and graph methods for Markov chains'', Proceedings of the Conference "Advances in Dynamical Systems and Quantum Physics" - Capri 1993. In press \item{[T]} A.Touv\'e ``Cycle Decompositions and Simulated Annealing". Preprint LMENS-94 \end