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
ENDBODY