%%%%%%%%%%%%%%% 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\logg#1{#1log((#1)^{1\over2})}
%%%%%%%%%%%%%%%%%%%%% 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 METASTABILITY AND TYPICAL EXIT PATHS }
\centerline{\bf IN STOCHASTIC DYNAMICS}
\bigskip
\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 - 00133 ROMA - Italy}\par
E-mail: OLIVIERI@MAT.UTOVRM.IT
\bigskip
{\it (2) Dipartimento di Matematica - Universit\`a di Roma Tre.}\par
{\it V. Segre 2 - 00146 ROMA - Italy }\par
E-mail: SCOPPOLA@ROMA1.INFN.IT, SCOPPOLA@MAT.UNIROMA3.IT
\vskip 1cm
{\bf Abstract}
\bigskip
In this paper we review and discuss results on metastability.
We consider ergodic aperiodic
Markov chains with exponentially small transition probabilities and
we give a complete description of the typical tube
of trajectories during the first excursion outside a general domain $Q$.
\vfill
\eject
\numsec=1\numfor=1
\bigskip
\bigskip
\noindent
{\bf Section 1. Introduction.}
\bigskip
In this review we want to describe some recent results in the theory of
metastability from the point of view of mathematical physics and probability
theory.\par
Mathematically we will deal with the study of some large deviation
problems for families of Markov chains with finite state space and
transition probabilities decaying exponentially fast in a large external
parameter $\b$: the so called Freidlin-Wentzell regime.\par From
physical point of view we analyze a central problem arising in the
dynamical description of phase transitions: the decay from metastable to stable
equilibrium.\par
Phase transitions (like, for instance, liquid-vapour for a fluid or
positive-negative magnetized phase for ferromagnetic systems) are, no doubt,
the most important phenomena in statistical mechanics.
As it is well known all equilibrium aspects are satisfactorily taken into
account in the framework of the `` Gibbs paradigm" ( see, for instance [Ru],
[Si], [Ge]).
On the other hand a general theory of non-equilibrium statistical mechanics
is still lacking and this is one of the main challenges for
contemporary fundamental physics.\par
Certainly metastability and in particular its peculiar dynamical aspects,
play a fundamental role in non-equilibrium statistical mechanics.\par
Let us rapidly introduce the subject.\par
Metastability is a relevant phenomenon
for thermodynamic systems close to a first order phase transition.\par
Suppose to start from a given pure equilibrium phase in a suitable region of
the phase diagram and change the thermodynamic
parameters to values corresponding to a different equilibrium phase; then,
in particular experimental situations, the
system, instead of undergoing a phase transition, can still remain in a
``wrong" equilibrium, far from the ``true" one but actually close to what the
equilibrium would be at the other side of the transition.
This apparent equilibrium, often called ``metastable state", persists untill an
external perturbation or some spontaneous fluctuation leads the system to the stable
equilibrium.\par
Examples of metastable states are supersaturated vapours and solutions, supercooled
liquids and ferromagnets with magnetization opposite to the field.
We will concentrate on this last example.
In this case a metastable state can be obtatined starting from a ferromagnet in
presence of a small negative external magnetic field $h < 0$ by suddenly switching
this field to a small positive value: our system remains with negative
magnetization (opposite to the actual value of $h$) for a time which is long if
the external field is small.\par
We will not provide here a complete list of references on metastability;
we want only to mention the paper by O. Penrose and J.L.Lebowitz
[PL1], (see also [PL2]), where for the first time the theory of the metastable
states has
a rigorous formulation, and the paper by M.Cassandro, A.Galves,
E.Olivieri and M.E.Vares [CGOV] where the so called
``pathwise approach to metastability" has been introduced.
This approach turns out to be the starting point of the recent
developments on the theory of metastability.\par
We summarize, in what follows, the mathematical description of metastability, based
on the pathwise approach, for the simple case of ferromagnetic spin systems on a
lattice.\par
We will give a simple description of our systems by means of the standard Ising
model.
Consider a spin variable $\s (i)$, assuming values $+1$ or $-1$, associated
to each site $i$ in a box $\L\subset {\bf Z}^d$.\par
To any configuration $\s \in \{-1,+1\}^{\L}$ we associate the energy:
$$
H_{\L} (\s) = - {1\over 2} \sum_{i,j\in \L, |i-j|=1}\s(i)\s(j) -{h\over 2}
\sum_{i\in\L}\s(i)
\Eq(1.2)$$
with $h>0$ and we assume, for instance,
periodic boundary conditions on the boundary of $\L$.\par
The Gibbs measure associated to this Hamiltonian, describing the equilibrium
properties of our system, is given by
$$
\m_{\L}(\s)={e^{-\b H_{\L}(\s)}\over Z_{\L}}
\Eq(1.3)$$
where $Z_{\L}$ is the normalization factor called partition function:
$$
Z_{\L}=\sum_{\s\in \{-1,+1\}^\L}e^{-\b H_{\L}(\s)}
$$
and $\b >0$ represents the reciprocal of the absolute temperature.
\par
It is possible to show ( see [Ru], [Si] ) that, for $h >0$ ($h<0$), in the
thermodynamic limit $\L \to {\bf Z}^d$ we get , for every $\b >0$, a unique Gibbs
state with positive (negative) magnetization.\par
We will be interested to the regime in which $h>0$ sufficiently small is
given, $\L$ sufficiently large but finite is given and $\b$ tends to infinity.
In these conditions the Gibbs measure will be concentrated on the unique ground
state for the energy $H$.\par
This configuration of minimal energy is
${\bf +1}$, in which $\s (i)=+1$ for all $i$.
The configuration ${\bf -1}$ ($\s (i)=-1$ for all $i$ )
is only a local minimum
for the Hamiltonian $H_{\L}$ (remember $h>0$)
and it is naturally related to metastability.\par
Let us now define
$E(l)\equiv H_{\L}(\s_{(l)}) - H_{\L}({\bf -1})$ ,
where $\s_{(l)}$ is the configuration in
which the plus spins
are exactly the sites internal to a square of side $l$ drawn in the dual lattice
$ {\bf Z}^d + ({1\over 2}, {1\over 2})$.
We have:
$E(l)= 4l - hl^2$ which is maximum for $l={2\over h}$. This means that
even though an arbitrarily small non-vanishing magnetic field determines the
phase, its effects become relevant only on a sufficiently large scale
($l\ge l_c(h)\sim {2\over h}$),
since only on these large scales the volume energy dominates
the surface energy.\par
A stochastic
dynamics with discrete time
is introduced in our system by means of a
Markov chain on $S = \{ -1, +1\}^{\L}$
with transition probabilities $P(\s ,\s')$
satisfying the detailed balance condition:
$$
\m_{\L}(\s)P(\s,\s')=\m_{\L}(\s')P(\s',\s)
\Eq(1.4)$$
and the ergodicity condition
$$\forall \s ,\,\eta\quad \exists t\in{\bf N}\quad \hbox{such that }\quad
P^t(\s ,\eta)>0\Eq(1.5)$$
where $P^t(.,.)$ is the t-step transition probability. \par
We will denote by $\sigma_t $ the process at time $t$ starting at
$\sigma$ at time $0$.\par
By using the ergodic theorem for Markov chains it is easy to prove that
the $t$-step transition probabilities $P^t(\s,\s') $ converge, as $t$ goes
to infinity, to
the unique invariant measure of the chain that, due to the detailed
balance condition \equ(1.4), turns out to be
the Gibbs measure $\m_{\L}(\s')$. This means that the
mean value of each observable $f$ with respect to the Gibbs measure
$\m_{\L}$, $\m_{\L}(f)=\sum_{\s}f(\s)\m_{\L}(\s)$,
can approximately be evaluated as the mean of the observable on the
process, $Ef(\s_t)$, at large t.
Markov chains satisfying conditions \equ(1.4),\equ(1.5) are
actually used for Monte Carlo simulations.\par
An explicit construction of a Markov chain satisfying the previous
hypotheses can be given, for instance, by the
Glauber-Metropolis algorithm which is defined as follows:
for any
$\sigma \in S $ and any $i$
in $\Lambda$
let
$$\Delta _{i} H(\sigma)\, = \, H_{\Lambda}(\sigma ^{i} )-H_{\Lambda}
(\sigma)\Eq(1.6)$$
with
$$\sigma ^{i}(j) =\cases{\sigma (j) & if $i\ne j$ \cr -\sigma (j) &
if $i=j$ \cr }\Eq(1.7)$$
We consider the following transition probabilities : if $\sigma \not= \sigma'$
$$P(\sigma , \sigma ' ) = \cases { 0 & if $ \quad \sigma '
\not= \sigma^i $ for all $ i \in \Lambda $\cr
{1\over |\Lambda |} \exp\{-\beta (\Delta _{i} H(\sigma)\vee 0)\}
& if $ \quad \sigma ' = \sigma^i $ for some $ i $\cr}\Eq(1.8w)$$
$P(\s,\s)$ is obtained by normalization.\par
We remark that the dynamics given by \equ(1.8w) is not conservative
in the sense that the total magnetization is not a conserved quantity.
Conservative dynamics
(like e.g.
Kawasaki dynamics) are not considered in the present paper; the study
of metastability in the conservative case is more complicated and still
open.
This kind of dynamics are often called stochastic Ising models.
Suppose now to analyze the typical paths of our Markov chain defined by
\equ(1.8w) starting from
${\bf -1}$ in the
above described Freidlin-Wentzell regime ($\L$ large, $h$ small
fixed, $\b$ very large).
For instance we can use a computer simulation and perform a large number of
independent runs (see [ToMi]).
What we see is that, during the evolution, in the sea of minus spins small droplets
of pluses appear but shrinking and disappearing before they are able to become
large.
Only after a very long time, under the effect of a large fluctuation, a cluster
sufficiently large will appear in the sea. Its behavior is then completely
different and it grows without hesitations.
In order to understand this behavior of typical trajectories, let
us compare the shrinking and the growing probabilities for a connected cluster
of spins $+1$ in the sea of $-1$'s in the two dimensional case.\par
First of all each cluster of spins $+1$ becomes rectangular
in a finite time, independent of $\b$,
with a
probability of order one following a sequence of transitions with
$\D_iH(\s)<0$.
Indeed the rectangle is the only shape of a cluster in which there are no spins
with a number of nearest neighbour opposite spins larger than 2
and there are no spins $-1$ for which this number is equal to 2.
Starting from a rectangular cluster of $+1$'s, the cut of a corner has a cost
$\D_iH(\s)=h$ and thus the lost of a row of the rectangle of length $l$
has a cost $h(l-1)$ (the last +1 in the row is lost with cost 0); similarly for a
column.
On the other hand the cost of the addition of a new line to the
rectangular cluster is $\D_iH(\s)=2-h$.
This means that if the minimal size $l$ of the cluster is such that
$h(l-1)>2-h$, i.e. $l\ge l_c=[{2\over h}]+1$,
the cluster tends to grow while if $l\b_c$,
($\b_c \equiv$ the reciprocal of the critical temperature). On the other hand in the
complementary, uniqueness region: $h \neq 0$ and/or $\b <\b_c$, one expects good
ergodic properties. Very intesting and deep results have been obtained in this
field in particular by Holley (see, for instance, the celebrated papers [Ho1,2]).
The methods that have been developed allow to handle the region far away from the
coexistence line; near this coexistence line it turns out to be quite difficult to
prove, for instance, exponential approach to equilibrium.
Consider, in particular, the region $\b >\b_c, h$ small but non-vanishing.
Nucleation phenomena and the behaviour of the system on a scale $l_c(h) = {2\over
|h|}$ (going to infinity as $h$ tends to zero) are certainly to be taken into
account. In other words the local relaxation from metastability to stability has
implications in the global aproach to equilibrium.
In [MOS2,3], by using results on the behaviour of the typical trajectories in a
finite volume regime, the authors where able to prove strong exponential ergodicity
for $\b \gg \b_c$ and $|h| \neq 0$ arbitrarily small in infinite volume. This
paper
represented a breakthrough in the
understanding of the uniqueness regime that now is almost complete
([MO1], [MO2], [MOSch], [SchSh], [CesM])\par
Problems somehow related to metastability arise in many different areas of science
like
biology ([EGJLa]), sociology ([GlHu]), linguistics ([CG], [NiBe]),
paleontology ([NewCoKi])...(see also [GSchm]).
\bigskip
In the present paper we want to collect and discuss results on
metastability in the limit $\b\to \infty$ from
a general point of view.
This means that we will consider ergodic aperiodic
Markov chains $X_t$ with finite state space
$S$ and with transition probabilities satisfying:
\bigskip
{\bf Property ${\cal P}$}
{\it If $x$ and $y$ are
communicating states, i.e. $x\not=y$ and $P(x,y)>0$, then}
$$\exp(-\D(x,y)\b-\gamma\b)\le P(x,y)\le \exp(-\D(x,y)\b+\gamma\b)\Eq(1.1as)$$
{\it where $\D(.,.)$
is a non-negative function on the set of pairs of communicating
states and $\g\to 0$ as $\b\to\infty$.}
\bigskip
This kind of Markov chains appear in many models, not only related to
physical problems.
As it has been shown by
Freidlin and Wentzell [FW], this kind of Markov chains
are also useful to study
the asymptotic properties of diffusion processes describing
small random perturbation of dynamical systems.\par
Similar Markov chains in a non-stationary situation
are also considered in the theory of simulated annealing
and optimization ([Ca1,2], [T2], [Ce]).
\bigskip
Let us now start the discussion of the problem of the first exit from a
general domain $Q\subset S$.
We will denote by $P_x$ the probability distribution
of the process $X_t$ starting from the state
$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.2aa)$$
For any set $Q\subset S$ we will denote by
$Q^c\equiv S\backslash Q$ the complement of $Q$.\par
Many results on the first exit problem have been obtained by Freidlin and
Wentzel [FW]. In particular they found estimates
for the average exit time $E_x\t_{Q^c}$ and the typical point,
on the boundary of $Q$, reached during the first excursion outside $Q$, i.e.
estimates on $P_x(X_{\t_{Q^c}}=y)$.
Our aim
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 sufficiently large $\b$.
We are looking for the minimal
set of exiting trajectories such that the sum of the corresponding
probabilities is of order one as $\b$ goes to infinity.
A state $x$ such that for any $y\not= x$ the quantity
$\D (x,y)$ appearing in \equ(1.1as) is strictly positive is called
a {\it stable state}. For instance in the case of the above defined Metropolis
dynamics any strict local minimum for the energy function H is a stable
state.
Consider the case of a domain $Q$ completely attracted by a unique stable state
$z_0\in Q$; namely every "null cost" trajectory starting in $Q$ ends in $z_0$
where the cost of a trajectory $x_0,x_1,...,x_n$ is given by $\D(x_0,x_1)+
\D(x_1,x_2) +...+\D(x_{n-1},x_n)$. This situation has been analyzed in detail
by Freidlin and Wentzel (see [FW]). It turns out that the typical trajectories
during the first exit from $Q$
i.e. in the interval
of time $[\theta_{\{z_0\}},\t_{Q^c}]$ where, for $D\subset Q$
$$\theta_D= \max\{t<\t_{Q^c};\, X_t\in D\}\Eq(1.bo)$$
are suitable sequences ``against the drift" emerging from $z_0$ and leading
outside $Q$ without hesitations in a finite time independent of $\b$.
The case of a general $Q$ containing several stable states
is much more complicated.
In this general case the last escape
takes place
by visiting a suitable sequence of stable states
$z_1,....,z_n$
and spending suitable random times inside certain domains
$Q_1,...,Q_n$ ({\it permanence sets})
containing $z_1,....,z_n$ respectively.
This means that in order to define our typical exiting tube we have to
consider {\it resistance times} associated to stable states.
These can be considered as a sort of
{\it temporal entropy} that
turns out to be necessary to give rise to an efficient escape mechanism.
Neglecting these random times, during the escape,
would lead to a mechanism
extremely depressed in probability.
These permanence sets are union of suitable sets called {\it cycles}
(see Definition 2.2 below).
The characteristic property of a cycle $A$ is that the process spends
exponentially long time visiting all states in $A$ before leaving it.
Cycles have been introduced by Freidlin and Wentzell, under some particular
hypotheses, and generalization of this definition can be found in [OS2]
and in
[T1], [ChiCho1]
where the cycle decomposition is used in the framework of simulated annealing.
If we consider reversible Markov chains, i.e. if we add to property ${\cal P}$
the
hypothesis of detailed balance condition \equ(1.4), the problem
of the definition of cycles and of the determination of the typical
tube is easier and can be reduced to the discussion of the energy
landscape.
In particular the sequence of sets defining the exiting tube can be obtained
by solving a well defined sequence of variational problems (minimax
problems) relative to the energy function $H$.
It turns out that these variational problems constitute the only model-dependent
work to be done to study the first exit from a general domain in the
reversible case (see [OS1]).
In the general non reversible case, when only property ${\cal P}$ is verified,
the cycles
can be defined, following Freidlin and Wentzell, by means of
a graphical technique.
As far as the problem of the determination of the typical exiting tube is
concerned, one can adopt two different strategies.
Following Catoni and Cerf [CaCe] (see also [ChiCho2]), given a subset $D\subset Q$
and
the cycle decomposition of the set $Q\setminus D$,
one can associate to each path of cycles the probability that the
process visits exactly this sequence of cycles in the time interval
$[\theta_D,\t_{Q^c} ]$. The determination of the typical exiting tube can thus be
reduced to the determination of the cycle paths of large probability.
A different approach to the problem is introduced in [OS2], where the
analysis of the typical exiting paths is obtained by means of
the renormalization procedure
introduced in [S1].
In that paper the long time behavior of the chain $X_t$ was studied by
means of the
construction of
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 stable states 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 states for the original Markov chain $X_t$;
$X^{(1)}_t$ is suitably defined on $S^{(1)}$. $S^{(2)}$ is the set of stable
states for $X^{(1)}_t$ and so on.
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
Given $Q\subset S$ we define its boundary:
$$
\partial Q = \{ x \not\in Q : \exists \; y \in Q : P(y,x) > 0\}
$$
In order to simplify the description of the first exit from the domain $Q$ of a
Markov chain $X_t$ we can
consider a new
auxiliary chain $X^Q_t$ on the state space $Q\cup \partial Q$
which is equivalent to $X_t$ up to its first exit from Q,
but with almost absorbing states in $\partial Q$.
More precisely we define the following
transition probabilities:\par
$$P^Q(x,y) = P(x,y)\quad \hbox{ for any } x\in Q\Eq(2.25)$$
$$P^Q(x,y) = e^{-\beta \D(\partial Q)}P(x,y)
\quad\hbox{ for } x\in \partial Q,\, y\not= x\Eq(2.26)$$
where $\D(\partial Q)>\sum_{y,z\in Q}\D(y,z)$ .\par
To this chain is applied in [OS2] the renormalization procedure
by introducing the sequence of renormalized chains
$X^{(1)}_t,......, X^{(i)}_t,...$ and the corresponding sequence of state
spaces $S^{(1)},......, S^{(i)},...$.
We warn the reader of an abuse of notation:
in what follows we will only consider the chain $P^Q$ but, to semplify
notation, we will omit
the superscript $Q$.\par
Since $\D(\partial Q)>\sum_{y,z\in Q}\D(y,z)$ it is immediate to show that
there exists a step N of the renormalization
iteration such that in Q there are only unstable
states with respect to the corresponding chain $X^{(N)}_t$. More precisely
let $N=N(Q)$ be the level such
that the $(N+1)$-the renormalized Markov chain does not
contain states inside $Q$:
$$N(Q)=\min \{n:\, S^{(n+1)} \cap Q= \emptyset\}\Eq(111)$$
This means that the first
excursion outside $Q$ for the
chain $X^{(N)}_t$ is a sort of ``descent" along the drift. \par
A first rough approximation
of the typical tube of
escape from $Q$ is thus
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 [OS2]
by associating to any state $x^N$
of $S^{(N)}$ a suitable set $Q_{x^N}\subset
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
By iterating this idea the exiting tube of paths can be easily determined.
\bigskip
In the remaining part of the present paper we will summarize the results
proved in [OS1],[OS2] under some additional assumption that
greatly simplify the
exposition.
The paper is organized as follows. In section 2 we recall the construction of
the exiting tube in the reversible case and we state the main results proved
in [OS1].
In sections 3 and 4 we will consider non reversible chains but under a very
strong additional hypothesis that allows us to give a simple
presentation of the results on the first exit.
\bigskip
\numsec=2\numfor=1
\bigskip
\bigskip
{\bf Section 2. The exit problem in the reversible case}
\par
\vskip.5cm
In this section we will consider ergodic aperiodic Markov chains with transition
probabilities satisfying the following:
\vskip.5cm
{\bf Hypothesis M}
{\it There exists a function $ H : S \to { \bf R}^+ $ such that
$$P(x,y)\; = \; q(x,y) \exp(-\b[ H(y) - H(x)]_+)\Eq(3.1)$$
where $q(x,y) \; = \; q(y,x)$ and $ (a)_+$ is the
positive part $(:= a \vee 0 )$ of the real number $a$.}\par
\vskip.5cm
The above choice corresponds to a {\it Metropolis Markov chain
} (see \equ(1.8w)) which is {\it reversible} in the sense of \equ(1.4)
with
$$
\m (x) \propto \exp ( - \b H(x)) \Eq(3.3)
$$
\par
Since the symmetric matrix $q$ is independent of $\b$ we immediately
get, from \equ(3.1), that Propery $\cal P$ is satisfied.\par
\bigskip
{\bf Hypothesis ND}
$$H(x)\not= H(y)\quad \forall x\not= y \Eq(3.3')$$
\bigskip
This hypothesis of {\it non-degeneracy} of the energy function
$H(x)$ is introduced only to simplify the exposition.
It is not at all needed and more general reversible Markov chains satisfying
only the detailed balance condition \equ(1.4) can be
considered (see [OS1]) without any additional difficulty.\par
We observe that we can obtain the validity of \equ(3.3') starting from any
Metropolis Markov chain with an arbitrarily small change in the energy
landscape.
\bigskip
Following the ideas presented in the introduction, we first define the cycles
and we discuss their properties.
In order
to construct the set of typical trajectories
exiting from a cycle $A$ (see Definition 2.2 below)
we will consider in section 2.2
the first descent from any point $y_0$ in $A$ to
the ``bottom"
$F(A)$ of $A$.
As already observed by R. Schonmann (see [Sch1]),
the problem of the typical tube of trajectories during the
first excursion outside a cycle $A$
turns out to be
simply related, via a time reversal transformation,
to the typical tube followed by the process during the first descent to
$F(A)$.
Using this idea in section 2.3 we will define the typical tube of trajectories
exiting from $A$.\par
\bigskip
{\bf 2.1 - Cycles and their properties}
\bigskip
A {\it path} $\o $ is a
sequence $ \o := x_1, \dots , x_N, \; N \in {\bf N}$,
with $ x_j,x_{j+1} ,\; j=1,\dots ,N-1$, communicating states
( i.e. $ P(x_j,x_{j+1}) \; > \; 0 $). We often write $\o : x \; \to y$ to
denote a path joining $x$ to $y$.
\par
A set $Q \subset S$ is
{\it connected} if $\forall \; x,x' \in Q $ there esists a
path $ \o : x \to x'$ all contained in $Q$. \par
We denote by $M$ the set of ``stable" states namely the local minima of the
energy: $x \in M$ iff $ H(x) \leq \min_{ y\in \partial \{x\}} H(y)$.
We say that a state $x$ is {\it downhill
connected} to a state $y$ if there exists a {\it downhill path} $\o\; =( x_0
=x, x_1, \dots , x_k \; =y)$ with $H(x_{i+1}) \leq H(x_{i}), \; i= 0,, \dots,
k-1$.\par
It is useful to conventionally extend every down-hill path up to a final
stable state $y \in M$.\par
On the other side a state $x$ is {\it uphill
connected} to a state $y$ if there exists a path $\o\; =( x_0 =x, x_1, \dots , x_k \;
=y)$ with $H(x_{i+1}) \ge H(x_{i}), \; i= 0,, \dots, k-1$.\par
Notice that the validity of Hypothesis ND does not prevent, in general, the
existence of many different down-hill (or up-hill) paths emerging from the
same point $y$.
Given $ Q \subset S$ we denote by $F=F(Q)$ the minimum set of the energy
on $ Q $ :
$$
F(Q) := \{ y \in Q : \min _{ x \in Q } H(x) = H(y) \} \Eq(3.5)
$$ and by
$U=U(Q)$ the minimum set of the energy
on its boundary:
$$
U(Q) \equiv F(\partial Q):= \{ z \in \partial Q : \min _{ x \in \partial Q }
H(x) = H(z) \} \Eq(3.4) $$
We notice that by Hypothesis ND both $U(Q)$ and $F(Q)$ contain only one state.
\bigskip
{\bf Definition 2.1}
{\it For each pair of states $x,y\in S$ we define their minimal saddle point
${\cal S}(x,y)$ as
follows:\par
Let
$$\bar H_{x,y} \;:=\;\min_{\o : x \to
y} \max _{ z\in \o} H(z).
$$
Then ${\cal S}(x,y)$ is uniquely defined by}
$$
H({\cal S}(x,y))\; = \bar H_{x,y} \Eq(3.5')
$$
\bigskip
This definition is well-posed because of the validity of Hypothesis ND.
\bigskip
By definition we have that that ${\cal S}(x,y)=
{\cal S}(y,x)\; \forall x,y\in S$.
Notice that it may happen that $x = {\cal S}(y,x)$ or $y = {\cal S}(y,x)$.
\bigskip
Given $ x \; \in S, \; Q \; \subset S, \; x \not \in Q$,we define
${\cal S}(x,Q)$ by:
$$\min_{w\in Q} H(
{\cal S}(x,w))= H({\cal S}(x,Q))
\Eq(3.5'')$$
\bigskip
{\bf Definition 2.2}
{\it A connected set $A$ which satisfies : \par \noindent
$$
\max _ {x\in A} H(x) = \bar H
< H(U(A))
$$
is called {\it cycle}.} \par
\bigskip
It is easy to see that, under the reversibility hypothesis for our Markov
chain, the above definition is strictly related to the one given by
Freidlin-Wentzell
(see
[FW] pag. 198).
In the following we will
recall the main properties of cycles (for proofs see [OS1]).
\bigskip
{\bf Proposition 2.1}
{\it
Given a state $ x\in S$ and a real number c the set of all the states connected
to $ x$ by paths with energy always below c either coincides with S or
it is a cycle A with}
$$H(U(A))\geq c$$
{\it Moreover, given two cycles $A_1, \, A_2$, either
1) $A_1\cap A_2=\emptyset$
or \par
2) $A_1 \subset A_2 $ or, viceversa, $A_2 \subset A_1 $}
\par
\bigskip
{\bf Proposition 2.2}\par
{\it If $A$ is a cycle then:\par
\item{i)} for each $x,y,z\in A$ and $w\not\in A$:
$$H({\cal S}(x,y))0 $ there exist $\b_0>0$ and
$k>0$ such that for any $\b>\b_0$ and $\forall x \in A$
$$
P_x(\exp (\b \;[\;H(U(A)) -
H(F(A))\; - \e\;])\; <
\;\t_{\partial A} \; < \; \exp (\b \;[\;H(U(A)) -
H(F(A))\; + \e\;])\;) \; \ge
$$
$$
\ge\; 1 - e^{-k\b}
$$
ii) there exist $\d >0 ,\, \b_0>0$ and $k'>0$ such that
for all $\b>\b_0$ and $\forall x,x' \;\in A$ :
$$
P_x( \t_{x'} \; <\; \t _{\partial A} \; ; \; \t_{x'} \;<\;
\exp (\b [ H(U(A)) - H(F(A))- \d] ) \;\ge\; 1 - e^{-k'\b}
$$
iii) $\forall x \; \in A ,\;\forall \epsilon >0, \;\; y \;\in \; \partial A $
and $\b$ sufficiently large:
$$
P_{x} (\;X_{\t _{\partial A}} = y ) \geq
\exp (-\b [H ( y ) - H(U(A)) + \e]\;) $$}
\vskip.5cm
The property described by point ii) is usually called
the {\it recurrence property} of cycles.
It is the main property characterizing cycles and it means that with
large probability each state
in the cycle is visited by the process before the exit.
A consequence of this property is the asymptotically exponential
distribution of the first exit time.
More precisely
let $A$ be a given cycle.
Given a point $x \in F(A)$ let the time $T_{\b}= T_{\b}(x)$ be defined by
$$
P_x ( \t _{ \partial A} > T_{\b}(x)) \; =\; e^{-1}. \Eq(3.27)
$$
One has that
$T_{\b}$ does not depend on $x \;\in \;A$,
in the sense of
logarithmic equivalence; namely we have $\forall x,y \; \in A $:
$$
\lim _{\b \to \infty} {1 \over\b } \log \left[{T_{\b} (x) \over T_{\b} (y)}\right]
\; = 0 \;\;\;\;\;\;\;\;\;
\lim _{\b \to \infty} {1 \over\b } \log [ T_{\b} (x)]\; = H(U(A)) -
H(F(A)) \Eq(3.27bis)
$$
Moreover
the asymptotic distribution,
( in the
sense of the most probable behaviour), of
the first exit time from $A$ , does not depend on $x \;\in \;A$
in the sense of logarithmic
equivalence.
Namely, $\forall x,y\; \in \; A, \; \e >0$:
$$
\lim _{\b \to \infty} P_x (T_{\b} (y) e^{-\e \b } \; <
\t_{\partial A} \; < \; T_{\b} (y) e^{+\e \b } ) \;\; = \; 1
\Eq(3.27')
$$
\vskip.5cm
{\bf Proposition 2.4}
{\it
Let $T^*_{\b} = T_{\b} (x^*) $ where $x^*$ is a particular point in $A$ chosen once
for all. Then $\forall \; x \;\in \;A, \;\forall \; s\;\in \;{\bf R}^+:$
$$
\lim _{\b \to \infty }
P_x ( {\t _{ \partial A} \;\over T^*_{\b}} > \;s\;) =\; e^{-s}. \Eq(3.29)
$$}
{\it Moreover, for every $x \;\in \; A$ and $\e>0$, if ${\bf E} _x$ denotes average over the
trajectories of the process starting, at $t=0$, from $x$, we have:
$$
\exp (\b \;[H(U(A)) -
H(F(A))- \e]) < {\bf E} _x (\t _{ \partial A}) < \exp (\b [H(U(A)) -
H(F(A)) + \e] \Eq(3.35)
$$}
\vskip.5cm
{\bf 2.2 - The permanence sets $Q_i$ and the standard cascade}
\bigskip
We want to construct now the set of typical trajectories starting from
an arbitrary state $y_0\in A$ and descending to $F(A)$.
Given $y_0$ let us consider a downhill path $\o _1 $ starting from $y_0$.
We stress, once more, that this path is not in general unique. This means that
the whole construction we are defining must be repeated for each path.\par
Let $ x_1$ be
the stable state in $ \o_1$.
If such a point $ x_1$ is $F(A)$
($y_0$ belongs to the ``basin of attraction" of
$F(A)$)
the {\it cascade} is simply given by
$y_0, \omega_1, F(A)$
Let us now suppose that
$ x_1\not= F(A)$.
Let $H_1$ be the energy of the saddle
between $x_1$ and $F(A)$:
$$H({\cal S}(x_1,F(A)))=H_1\Eq(**)$$
and let
$C(x_1,H_1)$ be the cycle containing $x_1$
with states of energy stricly less than $H_1$.
The first {\it permanence set}
$ Q_1$ is
the maximal connected set, containing
$ x_1$, of
points $x$ such that
$$
H({\cal S} ( x, F(A)) ) = H_1
$$
The permanence set
$ Q_1$ turns out to be
the union of the cycle $C(x_1,H_1)$, the saddle ${\cal S}(x_1,F(A))$
and possibly other cycles contained in $A$ and having ${\cal S}(x_1,F(A))$ as
common minimal
saddle in their boundaries. The above definition of permanence set can be used
also in the case in which Hypothesis ND does not hold.
Let $y_1$ be a point in $\partial Q_1$ such that
${\cal S}(y_1,F(A)) \; H( y_{j}), \;\;\;
\;H (F(Q_j))\;\leq \; H( y_{j-1}), \; j=1,\dots N$$
and
$F(Q_1), \dots , F(Q_{N-1})$ are strictly higher, in
energy, than $F(A)$.
\par
With the above definition of standard cascade we can state the result
on typical paths for the first descent to the bottom of the cycle $A$.\par
\vskip.5cm
{\bf Theorem 2.1}\par
{\it Given a cycle A, for every $y_0 \in A$, \par\noindent
i)\par
$$ \exists \; \d >0 \;\; \hbox {such that}\;\;
\lim _{ \b \to \infty}
P_{y_0} (\t _{ F(A)} <
\exp ( \b [ H(U(A)) - H(F(A)) - \d] )=1
$$
\par \noindent
ii)\par
$$
\lim _{ \b \to \infty}
P_{y_0} (\forall \; t \leq \t _{ F(A)} \;:\;
x_t \; \in \;{\cal T} ( y_0, \o_1, y_1,\o_2, \dots , y_{N-1}, \o_N)
$$
$$
\hbox {\rm for some}\; y_0, \o_1, y_1,\o_2, \dots , y_{N-1}, \o_N ) \; =\; 1,
$$
\par \noindent
iii) Moreover,
with probability $\to \; 1$ as $\b \to \infty$, there exists
a sequence $y_0, \o_1, y_1,\o_2,$ $ \dots , y_{N-1}, \o_N $
defining a standard cascade,
such that
our process
starting at $t=0$ from $y_0$, between
$t=0$ and $t= \t _{ F(A)}$,
after having followed the initial downhill path
$\o_1$, visits, sequentially, the sets $Q_1, Q_2, Q_{N-1}$
exiting from $Q_j$ through $y_j$ and then following the path $\o_{j+1}$ before
entering $Q_{j+1}$.\par
For every $\e >0$
with a probability tending to one as $\b \to \infty$ the process
spends inside each $Q_j$ a time
which can be estimated from above and from below by
$ \exp ( \b [ H(U(Q_j)) - H(F(Q_j)) \pm \e] ), j=1,\dots,N-1$.\par
Finally: before exiting from $Q_j$ it can perform an arbitrary sequence
of passages through the cycles belonging to $Q_j$
with the typical behavior described in Proposition 2.3.}
\vskip.5cm
{\bf 2.3 - By reversibility from the typical descent to the typical exit}
\bigskip
Following Schonmann ([Sch1]), we first give some simple general definitions.\par
Given $x, y \;\in \;S$, we denote by $ \O ^* (x,y)$ the set of all paths $\o$
starting from $x$,
visiting $y$ at some finite time $t$ and never visiting $ x$
and $y$ in between :
$$
\O ^* (x,y) := \{ \o = x_1, \dots , x_t
\hbox{ for some } t \; : \; x_1 = x, \; x_t = y,\;;\;
x_2, \dots , x_{t-1} \ne x,y\} \Eq(4.4)
$$
We denote by $R$ the time reversal operator defined on finite paths:
$$
\forall\; \o := ( x_1, \dots ,
x_t )\; :\; R \o := \bar \o :=
( x_t, \dots , x_1) \Eq(4.5)
$$
We naturally define, for every set of paths $\D $,
$$
R\D = \{ \bar \o = R \o \; ; \; \o \; \in \; \D\} .
$$
Let us call $ \t _{xy}$ the last time our process visits the state $x$
before touching, for the first time, $y$, namely :
$$
\t _{xy} \; := \; \max \{ t < \t_y : X_t = x\} \Eq(4.6)
$$
Given a finite path $\tilde\o = \tilde x_1, \dots , \tilde x_t \;$, we say that
our process $\{X_t\}_{t>0}$
{\it starts as} $\tilde\o$ if $X_1 = \tilde x_1, \dots ,
X_t = \tilde x_t $.\par
For any $x,y\in S$ we define a measure on the (infinite) paths
$\o = x_1, \dots , x_t, ... \;$ starting at $x$ ($x_1:= x$),
as follows:\par
if $\o\not\in \O^*(x,y)$ then $\r (\o)=0$\par
if $\o\in \O^*(x,y)$ we set
$\tilde\o_i=\o_i$ for all $i<\inf\{t>0;\, \o_t=y\}$, that is $\tilde\o$
is the finite path given by the first segment of $\o$ before hitting
$y$. Then
$$\r (\o) = P_{x}
( \; \{X_t\}_{t\ge 0} \; \hbox {starts as } \tilde\o \; |
\o \in \O ^* (x,y ))$$
and by $\bar \r (\o)$ the measure on the paths
$\o = x_1, \dots , x_t, ... \;$ given by :
$$\bar \r (\o) = P_{y}
( \; \{X_t\}_{t\ge 0} \; \hbox {starts as } R\tilde\o \; |
\o \in\; \O ^* (y,x)\;)
\;\;\;, \hbox {if}\;\;
\o \; \in \; \O ^* (y,x)
$$
$$
\bar \r (\o)= 0\;\;\;\hbox {otherwise}
$$
In [Sch1] it is proven that,
for every $x,y \; \in \;S $, every $\L \; \subset \; \O ^* (x,y)$,
$$
P_x ( \{X_t\}_{t\in[ \t _{xy}, \t_y]} \; \in \; \L
) = \r (\L) = \bar \r (R\L)=
P_y (\{ X_t\}_{t
\; \in [\t _{yx}, \t_x]} \; \in \; R\L
)\Eq(4.7)
$$
Now we are able to state our main result about the typical trajectories
realizing the escape from a cycle $A$.\par
\vskip.5cm
{\bf Theorem 2.2}\par
{\it Let
$$
\theta_{F(A)}= \max \{ t < \t_{A^c} : X_t\; = F(A).\}
$$
Call $\bar \partial ^- A $ the set of all points $x\; \in A$ uphill connected
to $U(A)$.
Then:\par\noindent
i)\par
$$
P_{F(A)} ( X_{\t_{A^c}} \;= U(A) )
\to\; 1\; \hbox {as }\;\; \b \; \to \;\; \infty \Eq(4.9)
$$
\noindent
ii) \par
\indent
$$
P_{F(A)} ( \exists y_0 \in \bar \partial ^- A,
{\cal T} ( y_0 , \o_1, y_1,\o_2, \dots , y_{N-1}, \o_N)\; :
$$
$$ X_t \in
R{\cal T} ( y_0 , \o_1, y_1,\o_2, \dots , y_{N-1}, \o_N)
\forall t \in [\theta _{F(A)}, \t_{A^c} - 1])\to 1 \hbox {as }
\b \to \infty
$$
iii) \par
\indent
During the first excursion from $F(A)$ to $A^c$, conditioning to
$ X_{ \t _{A^c} -1} = y$
(for some $ y \;\in
\bar \partial ^- A $)
and to follow a particular " anticascade"
$R{\cal T}
( y_0 = y, \o_1, y_1,\o_2, \dots , y_{N-1}, \o_N)$,
with probability
tending to one as $\b \to \infty$ the process ,
between $ \theta_{F(A)}$ and $ \t_{ y} $
visits the
sequence
$Q_{N-1},...,Q_{1}$,
spending in each set
a time which can be estimated from above and from below by
$ \exp ( \b [ H(U(Q_j)) - H(F(Q_j)) \pm \e] ), j=1,\dots,N-1$.} \par
\vskip.5cm
\bigskip
\numsec=3\numfor=1
{\bf Section 3. The renormalization procedure and the cycle decomposition.}\par
\vskip.5cm
In the remaining part of this paper we will consider generic Markov chains
(i.e. non necessarily reversible) but we will add to property ${\cal P}$
the following
very particular hypothesis which greately simplifies the exposition
of results and proofs. The reader can find in [OS2] the general results.
\bigskip
{\bf Hypothesis RI}
{\it There is at most a couple of states $x,y;\, x\not= y$ such that
$\D(x,y)=0$ and moreover
every non trivial
linear combination with integer coefficients of the
not vanishing
quantities $\D(x,y)$ is different from zero.}
\bigskip
{\bf Remark}\par
The rational independence condition in RI is even more strict than the analogous
condition of non-degeneracy ND of the reversible case. The condition that for
a unique pair of states $x,y$ one has $\D(x,y)=0$ is included in RI because it
is conserved (and in any case produced) by the renormalization
procedure.
Again we notice that with an arbitrarily small change of the $\D(x,y)$,
any Markov chain satisfying property ${\cal P}$ can be modified to satisfy
Hypothesis
RI.
\bigskip
\bigskip
Given a chain $X_t$ on $S$
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 function $\D(x,y)$ has been defined in \equ(1.1as) 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$
in the sense of the following:
\bigskip
{\bf Lemma 3.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.1as)
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,
for any $t0\Eq(2.6)$$
i.e. if each path leaving from $x$ has a positive cost.
We will denote by $M$ the set of stable states.\par
We note that by Hypothesis RI we have that there is at most
an unstable state, i.e.$ |S\backslash M|\le 1$. Moreover
again
Hypothesis RI allows us to exclude the
existence of equivalent states, i.e. of states $x,y$ such that $V(x,y)=
V(y,x)=0$, and thus we do not have to discuss the problem in terms of
equivalence classes as it has been done in [OS2].
\bigskip
{\bf 3.1 - Construction of the renormalized chain}
\bigskip
It is immediate to prove, using lemma 3.1, that
the process spends, with large probability,
relatively very short times in the unstable state.
This 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= y} V(x,y)\Eq(2.12)$$
and $ \delta = \d (\b) := 2 \g (\b) |S|$ (see \equ (1.1as)), goes to zero as
$\b$ tends to infinity.\par
We can then
construct a new Markov chain $ X^{(1)}_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=
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 $X^{(1)}_n =X_{\zeta_n}$ is a
homogeneous Markov chain on the state space $S^{(1)}=M$.
For any
pair of states $x,y\in M$ we
denote by $P^{(1)}(x,y)$ the transition probabilities of the chain
$ X^{(1)}_n$;
it is possible to prove
that these transition probabilities satisfy the
same assumptions (property ${\cal P}$ and Hypothesis RI)
verified by the original chain $X_t$.
More precisely
for any $x,y\in M,\quad x\not=y$:
$$\exp\{-\D^{(1)} (x,y) \beta - \gamma' \b \} \leq P^{(1)}(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)=
\bar\D(x,y)-V_1\Eq(2.15)
$$
where $\bar\D(x,y)=
[\D(x,y)\wedge (\D(x,\hat y^0)+\D(\hat y^0,y))]$ if
$\hat y^0:=S\backslash S^{(1)}\not=\emptyset$ and
$\bar\D(x,y)=\D(x,y)$ if $\hat y^0=\emptyset$,
and $\g '\to 0$ as $\b \to\infty$ (see [S1]).\par
Hypothesis RI is also satisfied by the chain $X^{(1)}_t$ since the new
quantities $\D^{(1)}(x,y)$ turn out to be linear combination of the old
quantities $\D (.,.)$ with integer coefficients and there
exists at most one unstable state $x$ for the new chain $X^{(1)}_t$.
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
This procedure of renormalization can be accomplished for more general
Markov chains satisfying only property ${\cal P}$.
In our case, under Hypothesis RI, at most one unstable state can
be removed going from $S^{(n)}$ to $S^{(n+1)}$, i.e. $|S^{(n)}\backslash
S^{(n+1)}|\le 1$. It is also easy to prove that $|S^{(n+2)}|<|S^{(n)}|$.
We will denote by $\hat y^n$ the unstable state of $S^{(n)}$, if any,
i.e. $\hat y^n=S^{(n)} \backslash S^{(n+1)}$. Thus we have:
$S^{(n)}= \cup_{i\ge n} \hat y^i$.
\bigskip
We recall now here the iteration scheme introduced in [S1] (see also [S2]).
{\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\subset 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)$$
$$M^{(k)} = \{x\in S^{(k)}: \forall y\in S^{(k)},\, y\not= x\quad
V^{(k)}(x,y)>0\}\Eq(2.19)$$
$$V_{k+1} = \min_{x\in M^{(k)}, y\in S^{(k)} \, x\not= 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)}\Eq(2.23)$$
$$\D^{(k+1)}(x,y) =
\bar\D^{(k)}(x,y)
- V_{k+1}
\quad \forall x,y\in S^{(k+1)}\Eq(2.24)$$
where $\bar\D^{(k)}(x,y)=
[\D^{(k)}(x,y)\wedge (\D^{(k)}(x,\hat y^k)+\D^{(k)}(\hat y^k,y))]$ if $
\hat y^k\not=\emptyset$
and
$\bar\D^{(k)}(x,y)=\D^{(k)}(x,y)$
if $\hat y^k=\emptyset$.
\bigskip
The main results proved in [S1] can be summarized as follows:
\bigskip
{\bf Theorem 3.1}\par
{\it Let $W\subset S^{(1)}$ and $B\subset W$.
Then for any sufficiently large $\b$ and for any
$x\in
S^{(1)}\backslash W,\, y\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)}_x(X^{(1)}_{\t_{W}}=y)\le
P_x(X_{\t_{ W}}=y)\le
\exp\{ \g' \b\} P^{(1)}_x(X^{(1)}_{\t_{W}}=y)$$
$$\exp\{-\g'\b\}t_1 E^{(1)}_x\t^{(1)}_{W}\le
E_x\t_{W}\le
\exp\{\g'\b\}t_1 E^{(1)}_x\t^{(1)}_{W}$$
$$e^{-\g'\b}\m^{(1)}(B)\le
\m(B)\le
e^{\g'\b}\m^{(1)}(B)$$
for any $B\subset S^{(1)}$ where $\m $ and $\m^{(1)}$ are the invariant
measures of the chains $X_t$ and $X^{(1)}_t$ respectively.
Moreover for any $A\in S\backslash M$
$$\m(A)\le e^{-V_1\b+\g'\b}$$
}
\bigskip
{\bf 3.2 - Tube of paths corresponding to a renormalized path}
\bigskip
By using the previous
construction of renormalized chains
we can immediately define
a correspondence
between trajectories of chains at different levels 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 can associate a path
$\phi^{(n)}$ of the Markov chain $X^{(n)}_t$,
$\phi^{(n)}\in \Phi (S^{(n)})$, which is in a 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 3.1}\par
For each path
$\phi\in\Phi (S)$ we evaluate
the sequence of stopping times $\zeta_n$ and we define a path
$\phi^{(1)}
\in\Phi(S^{(1)})$ by defining
$\phi^{(1)}_i = \phi_{\zeta_i}$.
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 $\psi^{(n)}$ in $S^{(n)}$ of
length $T$ :
$\psi^{(n)}_i,\, i\le T$
we can associate a tube
of trajectories in $\Phi (S)$ as
$${\cal T} (\psi^{(n)}) = \{\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)}))\Eq(2.28biss)$$
where
we say that two quantities $A$ and $B$
are {\it logarithmically 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}\log A = \lim_{\b\to\infty} {1\over \b}\log B \Eq(1.3bbb)$$
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
\bigskip
{\bf Definition 3.2}\par
$$Z^n_k\equiv \z_{\z^{(1)}_{\z^{(2)}_{._{._{\z^{(n-1)}_k}}}}}\quad n=1,2,...
\Eq(2.28bbis)$$
This is a random time with respect to the process $X_t$, corresponding to
the time $k$ for the chain $X^{(n)}$.
These times $Z^n_k$ with large probability are of order $T_n$ in the following
sense:
\bigskip
{\bf Proposition 3.1}\par
{\it For any $N\ge 1$ and
for any sufficiently small positive constant $\a$
there exists a
positive constant $k=k(\a,N)$ such that for any
$x\in 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 sufficiently large $\b$.
}\bigskip
Similar results are obtained in [OS2] in the more general case in which
Hypothesis RI is not assumed.
In order to complete the characterization of the typical tube of paths in
$\Phi(S)$ corresponding to a given path $\phi^{(n)}$, we need to define
the cycles.
In fact it is possible to
associate to each state $x^n\in S^{(n)}$
a cycle
$Q_{x^n}$ for the original chain $X_t$ representing the region of the state
space $S$
corresponding to the state $x^n\in S^{(n)}\subset S$
under the time rescaling $T_n$.
\bigskip
{\bf 3.3 - Cycles associated to renormalized states}
\bigskip
Let us first recall some definition introduced by Freidlin and Wentzell,
in order to discuss the cycle decomposition.
\bigskip
{\bf Definition 3.3 (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
\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
By using this graphic formalism Freidlin and Wentzel in [FW] prove the following
lemmas.
\bigskip
\bigskip
{\bf Lemma 3.2} ( 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.3bbb)$$
}\bigskip
{\bf Lemma 3.3} ( 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.4bbb)$$
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.4}( 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.5bbb)$$
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.2 is easily proved by showing that the quantities $q_i$
satisfy the stationarity equation, Lemmas 3.3 and 3.4 can be proved by
induction over the number of states contained in $B$.
(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.2} (FW )
{ \it \par
For any $\d >0$
there exists $\b_o >0$ such that for any $\b >\b_0$:
$$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)$$
Moreover for any $x\in Q$:
$$ \lim _{\beta \to \infty}{1\over \beta}\log 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
\bigskip
For each $Q\subset S$ let
$g_Q^{\ast}\in G\,(Q)$ be a $Q$-graph minimizing the quantity
$W_Q$ defined in \equ(3.9).
We note that by Hypothesis RI for any set $Q\subset S$ there exists a unique
graph $g^{\ast}_Q$. Indeed if there were two different minimizing graphs
$(g^{\ast}_Q)_1$ and $(g^{\ast}_Q)_2$, denoting by $(g^{\ast}_Q)'_1$
the arrows contained in $(g^{\ast}_Q)_1$ not contained in $(g^{\ast}_Q)_2$
(and the analog for $(g^{\ast}_Q)'_2$)
it would be
$$0=W((g^{\ast}_Q)_1)-W(g^{\ast}_Q)_2))=W((g^{\ast}_Q)'_1)-W((g^{\ast}_Q)'_2)$$
against Hypothesis RI.
\bigskip
For any set $Q$ and $x\in Q$ let
$$R_Q(x)=\{y\in Q^c:\, \exists x\to...\to y\in g^{\ast}_Q\}$$
\bigskip
{\bf Definition of cycles of rank zero}
Single states in $S$ are called cycles of rank zero or 0-cycles.
\bigskip
{\bf Definition of cycles of rank one}
Consider a set $C=\{x_1,...,x_n\}$ contained in $S$ with $n\ge 2$ such that
$x_{i+1}=R_{\{x_i\}}(x_i)$ for each $i=1,...,n-1$ and $x_1=R_{\{x_n\}}(x_n)$.
Such a set is called 1-cycle or cycle of rank one.
Every single state not belonging to one of these 1-cycles constitutes by
itself a 1-cycle.
Thus we can decompose the state space in
1-cycles: $S=\cup_i C_i$.
If $C$ is a 1-cycle we have that
$$|R_C(x)|=1 \quad \hbox{ and }\quad R_C(x)=R_C(y)=R_C\,\quad \forall
x,y\in C\Eq(succicl)$$
This property is immediately verified under our Hypothesis RI.
This means that graphs minimizing the exit from a cycle are made by a unique
tree.
We can then iterate our construction by defining:
\bigskip
{\bf Definition of cycles of rank $k$}
Consider a set $C=\{C_1,...,C_n\}$ contained in $S$ where
$C_i$ are $k-1$ cycles and $i=1...,n;\, n\ge 2$ such that
$R_{C_i}\in C_{i+1}$ for each $i=1,...,n-1$ and $R_{C_n}\in C_1$.
Such a set is called $k$-cycle or cycle of rank $k$.
Every $(k-1)$-cycle not belonging to one of these $k$-cycles constitutes by
itself a $k$-cycle.
Thus we can decompose the state space in
$k$-cycles.
If $C$ is a $k$-cycle we can iteratively verify that
$$|R_C(x)|=1 \quad \hbox{ and }\quad R_C(x)=R_C(y)=R_C\quad \forall
x,y\in C\Eq(suckcicl)$$
The main properties of cycles are summarized in the following.
\bigskip
{\bf Proposition 3.3}
{\it \par
For any set $C$ with $|C|>1$, the following are equivalent:
\bigskip
\item{i)} $C$ is a cycle (of some rank)
\item{ii)} 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)0$ (see proposition 3.1), 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:=\{
X_t\in {\cal T}(\phi^{(n-1)}(x^n,y^n))\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$
we have :
$$P_{x^n}(A_1\cap A_2\cap A_3|G)\ge 1- e^{-K\b} $$
Moreover if $x^n=\hat y^n$
and if we define
$$A_4:=\{\forall y\in Q_{{x^n}}\quad \exists t<\zn
\hbox{ such that } X_t=y\}$$
then we have, for any sufficiently large $\b$
$$P_{x^n}(A_1\cap A_2\cap A_3\cap A_4|G)\ge 1- e^{-K\b}$$
}\bigskip
{\bf Sketch of the proof}
It is sufficient to show that $P_{x^n}(A_i|G)$ are exponentially small for
$i=1,...,4$.
Suppose first that $P_{x^n}(G)\asymp 1$.
The estimate of $P_{x^n}(A_1|G)$ follows from Proposition 3.1.
To estimate $P_{x^n}(A_2|G)$ we first note that, since $Q_{x^n}\cap S^{(n-1)}=
x^n$, we have $\t_{(Q_{x^n})^c}\le Z^{n-1}_{\s ^{(n-1)}}$. On the other hand
$$P_{x^n}(\t_{Q_{x^n}^c}1-e^{-k\b}\Eq(6.1bis)$$
This transition $\hat y^N,z^N$
can be analyzed in terms of paths of the chain $X^{(N-1)}$.
We can proceed as follows: by applying Theorem 3.2 we can associate to
this transition
a cycle $Q_{\hat y^N}$ and the
path $ \phi^{(N-1)}(\hat y^N,z^N)$ in $\Phi(S^{(N-1)})$ defined by
\equ(defpath)
To each transition of this path at level $N-1$
we can associate, again by Theorem 3.2, a
cycle $Q_{\phi^{N-1}_j}$ and a new path.
By iterating this argument we have that the transition $\hat y^N,z^N$
is described by a sequences of cycles:
$$Q_{\hat y^{n_0}},\, Q_{\hat y^{n_1}},..., Q_{\hat y^{n_L}}.$$
Let us analyze the sequence $\hat y^{n_0},
...,\hat y^{n_L}$ arising from the above iteration.
\par
We start with the sequence $\hat y^N,z^N$.
At the first step we consider transitions at level $N-1$ by substituting
to the previous sequence the sequence $\phi^{(N-1)}(\hat y^N,z^N)$.
At the k-th step of the iteration we start by a sequence of transitions
of the chain at level $N-k+1$, ${\bf \hat y^{N-k+1}}=
\{\hat y^{n_i}\}_i$ with $n_i\ge N-k+1$
and we substitute to each couple of consecutive
states $\hat y^{n_i},\, \hat y^{n_{i+1}}$ the sequence of transitions
between states belonging to $S^{(N-k)}$ given by
$\phi^{(N-k)}(\hat y^{n_i},\, \hat y^{n_{i+1}})$.
We obtain in this way a new sequence ${\bf \hat y^{(N-k)}}$
that we call the {\it refinement} of ${\bf \hat y^{N-k+1}}$.
This sequence corresponds to the "typical exit path" for the chain
$X^{(N-k)}_t$.
The final sequence ${\bf \hat y^{0}}=\hat y^{n_0},
...,\hat y^{n_L}$, with $n_0=N$,
arising from the above iteration
will be the refinement of the refinement.....of the refinement of
$\hat y^N,z^N$.
In order to characterize the typical exit path in the time interval
$(\theta_{\hat y^N},\t_{Q^c}]$ we cancel the first term in ${\bf\hat y^0}$
corresponding to the first interval of time $[0,\theta_{\hat y^N}]$,
and we obtain:
$${\bf\hat y}:= \hat y^{n_1},
...,\hat y^{n_L}$$
To this path we can associate the corresponding sequence of permanence
sets:
$${\cal T}_{{\bf\hat y}}:= Q_{\hat y^{n_1}}, Q_{\hat y^{n_1}}, ...,
Q_{\hat y^{n_L}}$$
The result on the typical exiting tube can thus be stated as follows:
\bigskip
{\bf Theorem 4.1}\par
{\it For each positive $a$ there exists a positive constant $K$ such that
for each sufficiently large $\b$
we have:
$$P_{\hat y^N}(\{X_t\}_{t\in (\theta_{\hat y^N},\t_{Q^c}]}
\in {\cal T}_{{\bf\hat y}}
)\ge 1-e^{-K\b}$$
Moreover with probability going to one as $\b\to\infty$ the process visits
sequentially the sequence of sets given by ${\cal T}_{{\bf\hat y}}$ spending inside
each cycle $Q_{\hat y^{n_i}}$ a time which can be estimated from above and from
below by $T_{n_i} e^{\pm a\b}$ and visiting all the states inside the cycle
before the exit from it.}
\bigskip
The proof of this theorem can be obtained by using Theorem 3.2.
\bigskip
Let us now make some remarks on theorem 4.1.\par
Given the sequence ${\bf
\hat y}$ consider
each element $\hat y^{n_j}$
belonging to a portion of the sequence where $n_j$ is monotonocally
decreasing, i.e.
such that
$n_j