\tolerance=10000 \magnification=1000 \voffset=2cm \hoffset=0.7cm \baselineskip=20pt \font\magnifiedtenrm=cmr10 at 12truept \hsize=15.2truecm \vsize=21.5truecm \def\v{\par\noindent} \centerline {\bf DYNAMICAL ANALYSIS OF LOW TEMPERATURE} \centerline {\bf MONTE CARLO CLUSTER ALGORITHMS}\vskip 0.5in \centerline{ by}\vskip 0.4in \centerline {\bf Fabio Martinelli\footnote{}{Dipartimento di Matematica, Universita' "La Sapienza", Pz.A.Moro 2,Roma, Italy.\hskip 1cm e-mail: martinelli@vaxrma.infn.it}} \vskip 4cm {\bf Abstract}\par We present results on the Swendsen-Wang for the Ising ferromagnet in the low temperature case without external field in the thermodynamic limit. We discuss in particular the rate of convergence to the equilibrium Gibbs state in finite and infinite volume, the absence of ergodicity in the infinite volume and the long time behaviour of the probability distribution of the dynamics for various starting configurations. Our results are purely dynamical in nature in the sense that we never use the reversibility of the process with respect to the Gibbs state, and they apply to a stochastic particle system with {\it non-Gibbsian} invariant measure. \bigskip PACS numbers : 05.50=+q, 64.60My, 64.60Qb \vfill \eject {\bf Section 0 \hskip 2cm Introduction}\bigskip In this paper we continue our analysis of the Swendsen-Wang dynamics for the ferromagnetic Ising model (see e.g. [1],[2],[3]) in the low temperature regime, which was begun in [4],[5] in collaboration with E.Olivieri and E.Scoppola. The S-W algorithm, a particular random cluster dynamics reversible with respect to the Gibbs state of the Ising model, is based on the Fortuin--Kasteleyn ([6], [7]) representation of the Ising model, and it has the advantage, with respect to the usual single spin-flip-Glauber dynamics, of updating in a very efficient way the configurations on large scales.\v The algorithm works as follows: starting from a configuration $\sigma$ we construct a new configuration $\sigma'$ in two steps: \item{(i)} First we costruct the ``bond configuration'' $\{\gamma (b)\}$ , b=(x,x$'$), $\vert x-x'\vert =1$ as follows: a bond $(x, x')$ is defined to be ``vacant'',$\gamma (b)=0$, if $\sigma(x)\neq \sigma(x')$; if $\sigma(x)= \sigma(x')$ then the bond $(x,x')$ is defined to be ''occupied'', $\gamma (b)=1$, with probability 1-$\exp (-\beta)$ and ''vacant'' with probability $\exp (-\beta),\quad \beta$ being the inverse temperature. \item{(ii)} Then, given $\{\gamma (b)\}$, we consider the connected sets of sites C, called ''clusters'', in the graph whose edges are the occupied bonds b. The second step consists in updating simultaneously all the spins in every cluster C . The updating is such that all the spins in $C$ become either +1 or -1 with equal probability, independently for each cluster. Homogenous boundary conditions (b.c.)may be taken into account by imposing that the clusters which are connected to the boundary cannot flip and must preserve the same value of the spin as the boundary(e.g. +1). A more detailed construction of S.W. algorithm is given in Sec. 1.\v The above algorithm was introduced three years ago by Swendsen and Wang [1] in order to reduce or even completely eliminate the critical slowing down that greatly hampered Monte Carlo simulations of critical phenomena in ferromagnetic systems of statistical mechanics like Potts models. Their initial ideas were further developedand improved by a number of people (see e.g. [8] and references therein) and made available for models different from the original ones like plane rotators [9] or completely frustrated systems [10].\v This type of stochastic algorithms (known as stochastic cluster algorithms) proved to be very efficient from the numerical point of view (see e.g. [11]) and, because of the greatly reduced computer time, allowed very detailed studies of the statistical properties of the "physical" clusters of the Ising model [12].\v >From a theoretical point of view and in connection with numerical simulations, the central point of this subject is to study the critical behaviour of the dynamics. Unfortunately still very little is known rigorously on this difficult problem, with the exception of a rigorous lower bound on the dynamical critical exponent z obtained by Li and Sokal [13]. However, if one is interested in a rigorous analysis of purely non equilibrium phenomena like the way equilibrium is approached, metastability or large deviations from equilibrium, then the S-W turns out to be a very interesting model of random dynamics for which it is possible to develop new ideas and techniques that can be applied also to different contexts. For example in [4] it was succesfully discussed the approach to equilibrium in a finite but arbitrarily large volume at low temperature and in the presence of a small positive external field, by means of a novel multiscale analysis in space-time borrowed from statistic! al mechanics of disordered system very interesting question is therefore what happens at zero external field and low temperature. A zero temperature analysis shows immediately that in this case the S-W dynamics is very different from a single spin dynamics. In fact, for a traditional single spin algorithm like Metropolis with plus boundary conditions in a box of side L in 2 dimensions, a spin configuration starting from all minuses will become identically equal to plus only in a time of order $L^2$, by a kind of erosion mechanism starting from the boundary of the chosen box. On the contrary, in the S-W dynamics, the same configuration will flip to all pluses in a time of order one. Actually one easily proves (see the discussion after theorem 2.1) that any initial configuration will reach equilibrium, i.e. all pluses, in a time of order log(L). This fact suggests that also the low temperature behaviour, e.g. equal site time correlations at equilibrium, should be different between the two dynamics. To this purpose we recall that there is a very convincing argument by Fisher and Huse [16] (see also Sokal and Thomas [17]) predicting a streched exponential (exp(-$\sqrt t$)) convergence to equilibrium in two dimensions for the Metropolis algorithm, essentially based on the observation that large clusters of the wrong phase survive for a very long time (proportional to their area) under the dynamics. For the S-W dynamics however, big clusters of the wrong phase, which are therefore not attached to the boundary, can be flipped in a single move even without external field. Thus we conjecture that the S-W dynamics should approach equilibrium exponentially fast in time. Although we are not able to prove this here, we show that the convergence is faster than exp(-t$^\alpha$) with $\alpha\,=\,{ln(2)\over ln(3)}$.\v A second very interesting question concerns the behaviour of the dynamics in the infinite volume $\bf Z^d$. In this case the associated Ising model exihibits a phase transition, and a non trivial problem is to study the limit (if it exists) as t tends to infinity of the probability distribution of the dynamics at time t. For the usual Glauber dynamics, like Metropolis or Heath Bath algorithms, absence of ergodicity is proved using the attractivity of the dynamics and the reversibility with respect to the Gibbs measure. Attractivity is equivalent to say that for any time t, if f($\sigma$) is an increasing function of the spin configuration $\sigma$, then the expected value of f over the configuration $\sigma _t$ is an increasing function of the starting configuration. This fact, together with reversibility, is sufficient to prove for example that, starting from all pluses, the expected value of the spin at the origin will always be greater or equal than the magnetization in the plus phase ( $\mu_+$ ), while starting from all minuses the same average will always be smaller or equal than the magnetization in the minus phase $\mu _-$. If the temperature is below the critical point there is spontaneous magnetization and therefore the system is no longer ergodic. It is however well known that it is very difficult to prove this result by purely dynamical methods, i.e. without using the attractivity and reversibility of the dynamics, and, to our knowledge, no rigorous results are available in this direction. A notable exception is represented by the beautiful work of Toom on stochastic cellular automata [18].\v For the S-W dynamics the situation is in some respect more complicate than for a Glauber dynamics, since attractivity does not hold anymore and a detailed analysis of the dynamics in unavoidable.\v As it will become more clear in the sequel, in order to be able to give even a partial answer to the above questions, one is forced to have a good probabilistic control on the occurrence during the time evolution of long paths of vacant bonds. In [4] this control was achieved through the external field h, since each vacant bonds at integer time corresponds to a spin opposite to the field. In the absence of the magnetic field the situation is much more complicate since now a given path of vacant bonds may resist for a long time t with probability $({1\over 2})^t$. Therefore one cannot hope to get, uniformly in the starting configuration, estimates on the probability to observe at time t a path of vacant bonds of length L starting from a given site x, which are exponentially small in L, as it is the case for the Gibbs state at low temperature, unless t is much larger than L. On the other hand, it is a central point of our strategy to think of the dynamics on a given length sc! ale L as being built up by many l In this paper we provide a first solution to the above problems, certainly not the optimal one, for the S-W dynamics by means of a multiscale analysis which avoids completely any kind of Peierls arguments and in general any a priori knowledge about the equilibrium Gibbs measure. This last feature of our approach is in our opinion the most important one, since it allows to treat other models of interacting particle systems which do not have a Gibbsian invariant measure. This is the case of the model introduced in [19] in dimension $d\,\geq \,2$ which will be discussed in section 5. As it has been pointed out by Lebowitz and Schonmann [20], invariant measure of non-equilibrium statistical mechanics should generically be expected to be {\it non-Gibbsian}.\v The paper is organized as follows:\item{} In section 1 we define precisely the dynamics. \item{} In section 2 we prove the basic estimates on the probability of having long paths of vacant bonds and we show the existence in the infinite volume of an infinite cluster starting from a homogeneous configuration (all spins = +1 or -1). \item{} In section 3 we study the rate of convergence to equilibrium in a finite volume . \item{} In section 4 we give a dynamical proof of the existence of a phase transition. \item{} In section 5 we briefly discuss the application of the techniques to another model of an interacting stochastic particle system with a {\it non-Gibbsian} invariant measure. \bigskip {\bf Section 1 \hskip 2cm Construction of the dynamics and notation}\bigskip We start by constructing the dynamics with + boundary conditions in a finite subset of the d-dimensional cubic lattice $ {\bf Z^d}$. We first introduce the notation. \item{\bf i)} $\Lambda$ will denote a generic finite subset of $\bf Z^d$. Given a pair of sites x and y in $\bf Z^d$ we set $\delta (x,y)$ = $\Sigma_{i=1..d}\vert x_i-y_i\vert$, d(x,y)$ \,=\,max_{i=1..d}\vert x_i\,-\,y_i\vert$ and diam($\Lambda$)=$\sup_{x,y\,\in\,\Lambda}\delta (x,y)$. The distance between two sets A, B denoted by d(A,B) is given by : $\min_{x\in A,y\in B}d(x,y)$. \item{\bf ii)} The unordered pair b in $\bf Z^d$ : $b=(x,y)$ with $\delta (x,y)=1$ is called a bond. $\Lambda ^{*}$ is the set of all bonds (x,y) such that either x or y or both belong to $\Lambda$. The set of all bonds in $\bf Z^d$ will be denoted by $\bf Z^{d*}$. \item{\bf iii)} $\sigma\in\{-1,1\}^{\Lambda}$ denotes a generic configuration of plus or minus spins in $\Lambda$ \item{\bf iv)} $ C_{\Lambda}$ is the family of all ''geometric clusters'' $C$ in $\bar \Lambda \,\, =\,\, \{x;\, \exists \, b\,\in \Lambda ^{*}\,;\, x\in b\}$. A geometric cluster $C$ is a subset of $\bf Z^d$ which is connected in the following sense: $\forall x, y\in C$ there exists a chain of nearest neighbor sites in $C$ connecting $x$ to $y$: $$x^1\dots x^n:\quad x^1=x,\quad x^n=y,\quad\delta (x^{i+1},x^{i})=1\quad i=1\dots n-1$$ \item{\bf v)} Given a geometric cluster C, we define the "outermost boundary" of C as the set of sites x not in C such that there exists a nearest neighbor of x in C and there exists a chain of nearest neighbors sites $x_1,\, x_2\, ...\,x_N$ in $\bar \Lambda \backslash C$, with $x_1\,=\,x$ and $x_N\,\in \,\partial \Lambda$ where $\partial\Lambda\, \, = \, \, \{x\in \, \bar \Lambda\backslash \Lambda\}$. \item {\bf vi)} A collection $\gamma\,\equiv \,\{b_1,b_2,...,b_n\}$ of bonds in $\Lambda^*$ is called " a path of bonds containing x " iff x is the endvertex of one of the bonds $b_i$ and the distance between the endvertices of two consecutive bonds is not greater than one. The length of the path $\gamma$, $\vert \gamma \vert$, is set equal to diam(V($\gamma$)) where V($\gamma$) is the set of endvertices of the bonds $\{b_1,b_2,...,b_n\}$.\bigskip Now, given $\Lambda$, let $\nu_b$ and $\xi (C)$ be numbers in $\{0, 1\}$ associated to each bond and to each geometric cluster $C\in C_{\Lambda}$ respectively. Given the numbers $\nu_b \hbox{ and } \xi_C$ we construct out of a configuration $\sigma$ a new configuration $\sigma'$ as follows. >From $\sigma$ we first generate a configuration $\gamma$ of occupied ($\gamma (b)\,=\,1$) and vacant ($\gamma (b)\,=\,0$) bonds, by setting $$\gamma (b)\,\, =\,\, ({1+\sigma_b\over 2})\nu_b $$ where $\sigma_b\,=\,\sigma_x\sigma_y$ if b=(x,y) and $\sigma (x)\,=\,+1$ if $x\,\in\,\partial \Lambda$. The configuration $\gamma$ can be identified as the subset of the occupied bonds in $\Lambda ^{*}$. Sometimes in order to denote the configuration (and the corresponding subset of $\Lambda ^{*}$) $\gamma$ obtained starting from $\sigma$ we use the symbol $\gamma_{\sigma}$ ( $\gamma_{\sigma}$ depends of course on the numbers $\nu_b$ ). We will say that two n.n. sites (x,x$'$) are connected in the bond configuration $\gamma$ if $\gamma (x,x')=1$ i.e. the bond (x,x$'$) is occupied in $\gamma$. The maximal connected components C (with respect to the configuration $\gamma$) are called ''$\gamma$-clusters'' or more simply clusters. They are of course in particular geometric clusters and may reduce to a single site.\par For a geometric cluster $C$ which is also a $\gamma$-cluster we often write: $C\subset\gamma_\sigma$. Now for any $C\subset\gamma_\sigma$ we set: \item{}$\sigma'(x)=1 \quad \forall x\in C$ \hskip 1cm if either $\xi (C)\,=\,0$ or $C\cap\partial\Lambda\not=\phi$ \item{} $\sigma'(x)=-1 \quad \forall x\in C$ \hskip 1cm if $\xi (C)\,=\,1$ and $C\cap\partial\Lambda=\phi$ \hfill(1.1)\v Let us now consider two sequences of numbers $$\omega\equiv\left(\{\nu_b(t)\}_{t\in {\bf N}\, b\in\Lambda^*}\,; \;\{\xi(t,C)\}_{ t\in{\bf N}\, C\in C_\Lambda } \right)$$ that we think as the realization of two mutually independent process with values in $\{0,1\}$ each of which is a collection of independent identically distributed random variables (i.i.d. rv) with distribution: $$\eqalign{\nu_b \,\, &= \,\, 0 \quad \hbox{ with probability exp(-}\beta)\cr\nu_b \,\, &= \,\, 1 \quad \hbox{ with probability 1-exp(-}\beta)}$$\vskip 15pt and Bernoulli distribution with parameter $1\over 2$ for the $\xi(s,C)$.\par Given $\omega$ we finally construct a random flow on $\{-1,1\}^\Lambda$, $\{\phi^{\Lambda,\omega}_t(\cdot)\}_{t\in\,{ N}}$ by applying at each time step $t$ the rule (1.1) with numbers $\nu_b(t),\xi (t,C)$. Sometimes, for notational convenience, we will write: $$\sigma^\omega_t(x)=\phi^{\Lambda,\omega}_t(\sigma)(x)\eqno(1.2)$$ {\bf Remark 1} \item{\bf i)} the boundary condition $+1$ at the boundary of $\Lambda$ are taken into account by the condition that any cluster $C$ touching $\partial\Lambda$ is set equal to $+1$. Other boundary conditions may be considered e.g. periodic or open. \item{\bf ii)} Notice that if $\Lambda' \subset\Lambda$ then one can compare the random flows $\phi^{\Lambda,\omega}_t,\ \phi^{\Lambda', \omega}_t$ as follows: given $\sigma$ in $\Lambda$ one constructs $\hat\sigma$ in $\Lambda'$ by the rule $$\eqalign{ \hat\sigma(x)=\sigma(x)&\qquad\hbox{if}\quad x\in\Lambda'\cr \hat\sigma(x)=+1&\qquad\hbox{if}\quad x\in\partial\Lambda'\cr}$$ The evolutions $\phi^{\Lambda,\omega}_t(\sigma)$ and $\phi^{\Lambda',\omega}_t(\hat\sigma)$ are constructed by means of the same random numbers $(\nu_b(t),\xi (t,C))$ if $b$ and $C$ are in $\Lambda'$. However a cluster $C$ intersecting $\partial \Lambda'$ is set equal to $+1$ for the dynamics $\phi^{\Lambda',\omega}_t$ but may be $-1$ for the dynamics $\phi^{\Lambda, \omega}_t$. This observation will be exploited in a crucial way in the third section. \bigskip It is easy to see that the above defined dynamics satisfies the detailed balance condition for the Gibbs state of the Ising model on $\Lambda$, with + boundary conditions on $\partial \Lambda$, at inverse temperature $\beta$. The proof of this statement can be found for example in [1] [4].\vskip 30 pt {\bf Section 2 \hskip 2cm The basic estimate} \bigskip In this section we will establish a basic estimate on the probability of having a path of vacant bonds of length L containing a fixed point x at a given time t, with t greater than some time scale t(L) related to L. Such an estimate will play a crucial role in establishing the results of the subsequent sections. For simplicity we will discuss only the two dimensional case; the result however holds also in higher dimension.\v Let us first fix some notations. For any integer k we define:\vskip 10pt \item{\bf i)} $L_k \; =\; 4^{k^2}$ \item{\bf ii)} $t_k \; = \; 3^{k}$ \item{\bf iii)} $\Lambda_L(x) \; = \; \{y\in {\bf Z^2};\; d(x,y)\,\leq\,L\}$,\hskip 1cm $\Lambda_L$ = $\Lambda_L(0)$, \hskip 1cm $\Lambda_k$ = $\Lambda_{L_k}$ \item{\bf iv)} Given $\Lambda_L$ with L$>\,L_k$ we denote with the name (k,+)-dynamics in $\Lambda_L$ the algorithm described in the previous section with the following extra condition: $$\xi (s,C)\,=\,0\quad \hbox{ if diam}(C)\,>\,L_k$$ \item{\bf v)} $\Omega_{L,x,t,k,\sigma}$ will denote the event that there exist at time t + $1\over 2$ a path of vacant bonds in ${\bf Z ^2}^* $ of length n $\geq L_k $ containing x for the dynamics in $\Lambda _L $ with + b.c. starting from $\sigma$. $\Omega_{L,x,t,k,\sigma}^k$ will denote the same event but computed for the (k,+)-dynamics in $\Lambda _L $ starting from $\sigma$. \item{\bf vi)} $P_k \, = \, \sup_{L\geq L_k;x \in \Lambda _L;t\geq t_k;\sigma \in \{-1,1\}^{\Lambda _L}}\hbox{max (}P(\Omega_{L,x,t,k,\sigma})\, , \, P(\Omega_{L,x,t,k,\sigma}^k)\,)$\vskip 10pt\noindent For convenience and whenever this will not lead to confusion we will denote with $P(L,x,t,k,\sigma)$ either $P(\Omega_{L,x,t,k,\sigma}^k)\,)$ or $P(\Omega_{L,x,t,k,\sigma})\,)$ without specifying the dynamics for which it is evaluated. \v Then we will prove the following result:\vskip 20pt {\bf Theorem 2.1}\v There exists $\beta _o\, >\,0$, c$>0$, $k_o\,>\,0$ and a$>0$ such that for any $\beta \, \geq \, \beta _o$ there exists a positive constant m($\beta$) with m($\beta$) $\geq \, c$ such that: $$P_k \; \leq \; {1\over L_k^{2a}}\hbox{exp(-m}(\beta)2^k) \quad \forall \, k\,>\,k_o$$ \bigskip Before proving the theorem it is important to understand the case of zero temperature $\beta \,=\,\infty$. In this case no bond is made vacant during the dynamics and the only possibility to observe a path of vacant dual bonds at time $t+{1\over 2}$ is that the same path was already present at any previous time including t=0. The probability of this last event is bounded from above by $({1\over 2})^t$; however if the path in consideration is closed and it separates exactly two different clusters at time t=0, then the above bound becomes exact. This discussion suggests that any bound on $P_k$ will be at most exponential in the time scale $t_k$ with rate constant $m(\beta)$ at most equal to ln(2) and in particular that to obtain a rigorous bound on $P_k$ by means of some kind of Peierls argument should be a very difficult task since the number of paths grows exponentially fast in the length scale $L_k\;>>\;t_k$. One should at this point be puzzled by our choice of the length and time scales ($L_k\,>>\,t_k$), since the above arguments seem to indicate that time scales of the same order the length scales should be more appropriate. As it will appear clear in the course of the proof, it is a central point of our strategy the fact that if the dynamics starts from a configuration with paths no longer than $L_k$ and at a later time $t_k$ a path longer than $L_{k+1}$ is present, then there are at least two pieces of it, each of length greater than $L_k$, that have been created independently one from the other. A proof of this fact requires however that time scales are much smaller than length scales (more precisely : $t_kL_k\,<<\,L_{k+1}$). \par The actual result, although it is sufficient for our purposes, is unfortunately much weaker than the naive guess made on the basis of the above discussion since it is only an exponential of $t_k^{({ln2\over ln3})}$. A substantial improvement seems to require new ideas.\bigskip {\bf Proof} \v For $\beta$ large enough we will show that the quantity $P_{k+1}$ " on scale k+1 " can be estimated in terms of the same quantity " on scale k " P$_k$, by : $$P_{k+1} \; \leq \; L_k^{a}P_k^2 \eqno (2.1)$$ for a suitable positive constant $a$ independent of k and $\beta$. If (2.1) holds and if $f_k\, = \, L_k^{2a}P_k$ then, by explicit computation: $$f_{k+1}\, \leq \, f_k^2 \eqno (2.2)$$ provided k$\geq$5. Thus: $$f_k \, \leq \,(f_{k_o})^{2^{k-k_o}}\eqno (2.3)$$ for any $k_o\,\geq \,5$, i.e. , using the definition of $f_k$: $$P_k \, \leq \, {1\over L_k^{2a}}(L_{k_o}^{2a}P_{k_o})^{2^{k-k_o}}\eqno (2.4)$$ Therefore the theorem follows with $m(\beta)\, = \, -2^{-k_o}log(L_{k_o}^{2a}P_{k_o})$ provided that: $$\lim_{\beta \to \infty }(L_{k_o}^{2a}P_{k_o} )\, < \, 1 \eqno (2.5)$$ for some $k_o\,\geq \,5$.\par To prove (2.5) we first observe that using the Markov property of the dynamics we have:$$P_k\, = \, \sup_{L\geq L_k;x \in \Lambda _L; \sigma \in \{-1,1\}^{\Lambda _j}}P(L,x,t_k,\sigma)\eqno (2.6)$$ Moreover for fixed L and x in $\Lambda _L$ we have that: $$P(L,x,t_{k_o},\sigma) \, \leq \,L_{k_o}^2t_{k_o}e^{(-\beta) }\, +\, L_{k_o}^2({1\over 2})^{t_{k_o}} \eqno (2.7)$$ The r.h.s. of (2.7) is in fact a rough upper bound of the probability that at least one of the $L_{k_o}^2$ bonds b at distance from x smaller or equal to $L_{k_o}$ either was made vacant at some time s+$1\over 2$ smaller than $t_{k_o}$ (i.e. $\nu (b,s+{1\over 2}) \, \leq \, e^{-\beta})$ or that $\sigma _s(b)\, = \, -1\; \forall \, s\leq t_{k_o}$. It is easy to check that indeed the r.h.s. of (2.7) is smaller than 1 if $k_o$ is taken large enough (depending on $a$) and $\beta$ is large enough depending on $k_o$.\v We are therefore left with the proof of the basic recursion inequality (2.1). Using (2.6) it is sufficient to estimate P($\Omega_{L,x,t_{k+1},k+1,\sigma}$), computed either for the dynamics with + b.c. or for the (k+1,+)-dynamics in $\Lambda_L$, with the r.h.s. of (2.1) uniformly in L$\geq L_{k+1}$, $x \, \in \, \Lambda _L$ and in the initial configuration $\sigma$. Thus let us fix L$\geq L_{k+1}$, $x \, \in \, \Lambda _L$, $\sigma \, \in\, \{-1,1\}^{\Lambda_L} $ and one of the two dynamics in $\Lambda_L$ and let us introduce the auxiliary event $\Omega _1$ :\vskip 20pt\noindent $\Omega _1$ = $\{$there exists y in $\Lambda _L$ with d(y,x) $\leq L_{k+1}$ and s in $[t_k,2t_k]$ such that at time s + $1\over 2$ there exists a path of vacant bonds in ${\bf Z ^2}^* $ of length n $\geq L_k $ containing y $\}$.\bigskip {\bf Remark 1} If $\Omega _1^c$ holds then it holds also at integer times $s\in [t_k,2t_k]$. This follows by the simple observation that the number of vacant bonds at time s is always smaller or equal than the same number at time $s+{1\over 2}$.\v Then we write: $$P(\Omega_{L,x,t_{k+1},k+1,\sigma}) \, = \, P(\Omega_{L,x,t_{k+1},k+1,\sigma}\cap \Omega _1)\, + \, P(\Omega_{L,x,t_{k+1},k+1,\sigma}\cap \Omega _1 ^c) \eqno (2.8)$$ where $\Omega _1 ^c$ denotes the complement of $\Omega _1$. Using again the Markov property and the definition of $P_k$ the first term in the r.h.s. of (2.8) is estimated uniformly in x, L, $\sigma$ by: $$t_kL_{k+1}^2P_k^2 \eqno (2.9)$$ In fact if in the event $\Omega_{L,x,t_{k+1},k+1,\sigma}\cap \Omega _1$ we also fix the site y and the time $s \in [t_k,2t_k]$ entering in the definition of the event $\Omega_1$, then we are examining an event that it is contained in the event that at there are two paths of vacant dual bonds each one of length greater than $L_k$, one at time s$+{1\over 2}$ containing y and the other at time $3t_k\, +\, {1\over 2}$ containing x . Since both s and $t_{k+1} -s$ are greater than $t_k$ and $L\geq L_{k+1} \, > \,L_k$ we can use $P_k$ and the Markov property to obtain the estimate $P_k^2$ for the probability of this last event. The factor $t_kL_{k+1}^2$ takes into account the number of choices of y and s.\v We now turn to the estimate of the second term in the r.h.s. of (2.8). For simplicity we first describe the estimate for the case x=0. After that we will explain the (trivial) modifications which are necessary in order to consider the general case.\v {\bf Definition 1} Given an integer L and $l\,\leq \, L$ we set: $$\Lambda_{L \, - \, l} \; = \; \{x\in \Lambda_L ; \hbox{dist}(x,\partial \Lambda_L)\, \geq \, l\}$$ {\bf Definition 2} \item{\bf a)} $\tau _1 \, = \, \hbox{min }\{s>t_k; \, \exists \;y \; \in \Lambda _{L_{k+1}\, - \, (s-t_k)l_k }$ such that at time s + $1\over 2$ there exists a path of vacant bonds in ${\bf Z ^2}^* $ of length n $\geq L_k $ containing y where $l_k\, = \, 4t_kL_k$$\}$. \item{\bf b)} Let $y_1$ be the leftmost and uppermost of the site y's appearing in the definition of the random time $\tau _1$. Then we set : \par $\tau _2 \, = \, \hbox{min }\{s\geq\tau _1; \, \exists \;y \; \in \Lambda _{L_{k+1}\, - \, (s-t_k)l_k} $ with d(y,y$_1$)$\geq (s+2-\tau_1)l_k$ such that at time s + $1\over 2$ there exists a path of vacant bonds in ${\bf Z ^2}^* $ of length $n\geq L_k$ containing y$\}$.\par For convenience the leftmost and uppermost of the sites y's appearing in the definition of $\tau _2$ will be denoted by $y_2$.\bigskip {\bf Remark 2} \item{\bf i)} By direct computation we have that $t_kl_k \, = \, L_{k+1}({9\over 16})^k$ and therefore $t_kl_k \; << \; L_{k+1} $ for k large. \item{\bf ii)} If the event $\Omega_{L,x=0,t_{k+1},k+1,\sigma}\cap \Omega _1 ^c$ holds then $\tau_1 \, >\, 2t_k$ and, more important, $\tau _2\, \leq \,3t_k$. In fact necessarily $\tau _1\, \leq \,3t_k$ since otherwise for any time s between $2t_k$ and $3t_k\,+\,{1\over 2}$ the path of vacant bonds containing x=0 would have length smaller than $L_k$ which is impossible because of $\Omega_{L,x=0,t_{k+1},k+1,\sigma}$. Moreover if the site y$_1$ defined above is such that d(y$_1$,0)$\geq l_kt_k$ then again $\tau _2\, > \,3t_k$ would imply that the path of vacant bonds starting from x=0 at time 3$t_k\, +\, {1\over 2}$ has length smaller than $L_k$. The same occurs if d(y$_1$,0)$\leq t_kl_k$ and $\tau _2\, > \,3t_k$ since $L_{k+1}\, >>\, t_kl_k$.\bigskip We will therefore estimate $P(\Omega_{L,x=0,t_{k+1},k+1,\sigma}\cap \Omega _1^c)$ by: $$ P(\{2t_k\,\leq\,\tau _1 \, \leq \, \tau _2 \, \leq 3t_k\}\; \cap \;\Omega _1^c ) \; \leq$$ $$\Sigma _{s_1=2t_k}^{3t_k}\Sigma _{s_2=s_1}^{3t_k}\Sigma_{x_1 \in \Lambda_{k+1}}\Sigma_{x_2\in \Lambda_{k+1}} P(\{\tau _1 \, =\, s_1;\;y_1\,=\,x_1; \; \tau _2 \, = \, s_2;\;y_2\,=\,x_2\}\; \cap \; \Omega _1^c) \eqno (2.10)$$ The main idea to estimate the r.h.s of (2.10) is to show that, due to the condition expressed by $\Omega _1^c$ and by the definition of $\tau _1$ and of $\tau _2$, the paths $\gamma _1$ and $\gamma _2$ of vacant dual bonds with length greater than $L_k$ starting at times $s_1$ and $s_2$ from $x_1$ and $x_2$ respectively, have been created by the random dynamics starting from the configuration $\sigma_{t_k}$ independently one from the other within the time intervals $[t_k,s_1]$ and $[t_k,s_2]$. If this is the case then each term in the sum (2.10) can be estimated by $P_k^2$ and the theorem follows.\v In order to carry out this program we first prove two simple geometric results on the structure of the configuration $\sigma _t$ for $t\leq \, \tau _2 $.\v Let $\Lambda_{k+1}^s$ denote $ \Lambda_{k+1}\, - \, (s-t_k)l_k$, and let $\Lambda_i$ be the square $\Lambda_{l_k}(y_i)$ i=1,2.\bigskip {\bf Lemma 2.1}\v For any s such that $t_k\,\leq \, s\, < \, \tau _1$ there exists a cluster denoted $C^{\infty}_s(1)$ with the property that its outermost boundary does not intersect $\Lambda_{k+1}^s$ and such that for any $x \, \in \, \Lambda_{k+1}^s$ only one of the following two possibilities holds: \item{\bf 1)} diam($ C_s(x))\, < \, L_k$ \item{\bf 2)} $ C_s(x)$ coincides with $C^{\infty}_s(1)$.\bigskip {\bf Lemma 2.2}\v For any $t_k\,\leq\,s\, < \, \tau _2$ there exists a cluster denoted $C^{\infty}_s(2)$ with the property that its outermost boundary does not intersect $\Lambda_2$ and such that for any $x \, \in \, \Lambda_2$ only one of the following two possibilities holds: \item{\bf 1)} diam($ C_s(x))\, < \, L_k$ \item{\bf 2)} $ C_s(x)$ coincides with $C^{\infty}_s(2)$.\bigskip {\bf Proof of Lemma 2.1}\v Let us first show that for any $s\, < \, \tau _1$ there must exist in $\Lambda_{k+1}^s$ a site x such that diam($ C_s(x))\, > \, L_k$. In fact if for some $s\, \leq \, \tau _1 -1$ and any $x \, \in \, \Lambda_{k+1}^s$ diam($ C_s(x))\, < \, L_k$ then necessarily there exists a site $x_o$ in $\Lambda_{k+1}^s$ such that at time s there exists a path of vacant bonds in ${\bf Z ^2}^* $ of length n $\geq L_k $ containing $x_o$. This fact is of course in contradiction with the definition of $\tau _1$.\v Let us now fix x $ \in \, \Lambda_{k+1}^s$ and let us assume that diam($ C_s(x))\, > \, L_k$. Since $s< \tau _1$ the outermost boundary of $C_s(x)$ cannot intersect the box $\Lambda_{k+1}^s$. We then take as $C^{\infty}_s(1)$ the cluster $C_s(x)$. It remains to show that if $y \, \in \,\Lambda_{k+1}^s$ is any other site such that diam($ C_s(y))\, > \, L_k$ then $C_s(y)$ = $C^{\infty}_s(1)$. This is quite clear since the outermost boundary of $C_s(y)$ cannot intersect $\Lambda_{k+1}^s$ and therefore it must coincides with the outermost boundary of $C_s(x)$ = $C^{\infty}_s(1)$. \bigskip {\bf Proof of Lemma 2.2}\v Let us fix $s\,<\,\tau_2$. Then any site x inside the box $\Lambda_2$ is at distance from $y_1$ greater or equal to $(\tau_2 \,-\,\tau_1 \,+\,2)l_k\,-\,l_k \;\geq\; (s-\tau_1 +2)l_k$. Therefore, by the definition of $\tau_2$, the longest path of vacant bonds at time $s+{1\over 2}$ containing x and intersecting the box $\Lambda_2$ has length smaller than $L_k$. Thus the same proof of Lemma 2.1 applies with the box $\Lambda_{k+1}^s$ replaced by the box $\Lambda_2$. \bigskip {\bf Remark 3} \item{\bf i)}It is clear that the cluster $C^{\infty}_s(i)$ i = 1,2 may coincide with the cluster of the boundary of the chosen box $\Lambda _L$. \item{\bf ii)} If the dynamics under consideration is the (k+1,+)-dynamics in $\Lambda_L$ and if the diameter of $C_s^{\infty}\,\geq\,L_{k+1}$ then necessarily the sign of $C_s^{\infty}$ will be plus. \item{\bf iii)} By construction the outermost boundary of $C_s^{\infty}(1)$ cannot intersect the boxes $\Lambda_i$ i=1,2 for s$<\,\tau_1$.\bigskip The next step consists now in establishing a coupling between the dynamics $\sigma_s$ inside the boxes $ \Lambda_i$ and the (k,+)-dynamics in $\Lambda_i$, for s $\in \, [t_k,\tau_i]$ i=1,2. For this purpose given a site $x$ inside $\Lambda_{k+1}\,-\,l_k$, given $s_o$ $\in \,[t_k,3t_k]$ and given a realization $\omega$ of the basic random variables $\{\nu (s,b)\}_{s\,\in \, [t_k\, ,\, 3t_k]}\; , \; \{\xi (s,C)\}_{s\,\in \, [t_k\, ,\, 3t_k]} $ we define in general $\eta_s^{(x,s_o)}$ as the evolution of the configuration $\sigma_{t_k}$ inside the square $\Lambda_{l_k}(x)$ with the following new set of basic random variables :\vskip 10pt \item{\bf 1)} $\xi(s,C)'\,=\,\xi(s,C)\xi(s,C_s^{\infty})$ if $s\,2l_k$ the two dynamics $\eta_s^{(x_i,s_i)}$ i=1,2 are clearly independent and therefore, using Remark 5, the r.h.s. of (2.11) can be estimated by $P_k^2$ which gives the estimate : $$t_k^2L_{k+1}^4P_k^2 \eqno (2.12)$$ for the r.h.s. of (2.10).\v If we combine now (2.9) with (2.12) we get that : $$P(\Omega_{L,x=0,t_{k+1},k+1,\sigma}) \;\leq\; (t_kL_{k+1}^2\;+\;t_k^2L_{k+1}^4)P_k^2 \eqno (2.13)$$ As we have already anticipated the same estimate can be obtained also for $x\,\neq \,0$. In this last case all the steps that led to the estimate (2.12) are unchanged except that now the square $\Lambda_{k+1}$ has to be replaced by $\Lambda_{k+1}(x)\cap\Lambda_L$ and the same for $\Lambda_{k+1}^s$ and $\Lambda_i$.\v Thus the basic recursion inequality (2.1) is proved with e.g. $a\,=\,18$ and the theorem follows. \par Before closing this section we would like to comment about our particular choice of the boundary conditions (+) for the two dynamics involved in theorem 2.1. Our choice was not at all essential for the result to hold and other b.c like open or periodic ones can be accomodated as well. In these cases the proof is unchanged provided that one defines the quantity P(L,x,k,$\sigma$) appearing in the definition of $P_k$ as the largest between the probability that there exist at time t + $1\over 2$ a path of vacant bonds in ${\bf Z ^2}^* $ of length n $\geq L_k $ containing x for the dynamics in $\Lambda _L $ with the chosen b.c. starting from $\sigma$ and the same quantity computed for the (k,+)-dynamics in $\Lambda_L$ starting from $\sigma$. Rather interesting for later applications are the (p,1-p)-b.c. defined as follows: all the clusters which touch the boundary of $\Lambda_L$ are part of a unique cluster, called the boundary-cluster, which is set equal to +1 with probability p and to -1 with probability 1-p. In this case the random variable $\xi (s,C^{\infty}_s)$ may have Bernoulli distribution with parameter p, as well as Bernoulli distribution with parameter $1\over 2$, depending on whether the cluster $C_s^{\infty}$ touches the boundary of $\Lambda_L$ or not. In both cases the random variables $\xi '(s,C)$ will be distributed according to the Bernoulli distribution of parameter $1\over 2$ and the proof will remained unchanged. There are however limitations that come from those b.c. that naturally produce already in the Gibbs state long paths of vacant bonds like the (+,-) b.c. in two dimensions (i.e. + b.c. in the upper half plane and - b.c. in the lower half plane of $\bf Z^2$ ). The proof in this case breaks down and the reason is that the analogous of estimate (2.7) does not hold anymore. In fact a given bond b may remain vacant for a long time with large probability if its end points belong to two different boundary clusters pinned to opposite sign by the b.c. . It seems however that if one modifies the definition of $P(L,x,t,k,\sigma)$ in such a way that one considers only those paths that do not intersect the long path which joins the opposite sides of $\Lambda_L$ separating the plus phase from the minus phase, then the technique illustrated above can be applied again. Also the case of an ! external magnetic field parallel >From the above proof and particularly from the discussion made right after the theorem it appears that the main reason for connecting length scales with time scales comes from taking in the definition of the quantity $P_k$ the supremum over all possible initial configurations, since for starting configurations with many paths of vacant dual bonds (e.g. a chessboard configuration) it takes a long time to become more regular and to look like a typical configuration of the equilibrium Gibbs state. This suggests that if we start already with a "regular configuration", then the probability of having a long path of vacant dual bonds at time t should decay fast enough in the length of the path already for short times. There is however some problem to solve since in the course of the proof of the theorem and particularly in the estimate of the first term in the r.h.s. of (2.8), we made use of the Markov property thanks to the fact that in the definition of $P_k$ we took the supremu! m over $\sigma$. Thus the followi Let $P_k^+$ be defined as: $$P_k^+\;=\; \sup_{t}\sup_{x,\, L\,>\,L_k}P(L,x,t,k,+)\eqno (2.14)$$ where + denotes the configuration identically equal to plus one .\v Then we have: \bigskip {\bf Theorem 2.2}\v There exists $\beta _o\, >\,0$, c$>0$ and a$>0$ such that for any $\beta \, \geq \, \beta _o$ there exists a positive constant m$_o(\beta$) with m$_o(\beta$) $\geq \, c$ such that: $$P_k^+ \; \leq \; {1\over L_k^{2a}}\hbox{exp(-m}_o(\beta)2^k) \quad \forall k$$ \bigskip {\bf Proof}\v Let $k_o$ be given by theorem 2.1. The above estimate on $P_k^+$ is clearly true as $\beta\,\to\,\infty$ for $k\,<\,k_o$. For $k\,\geq\,k_o$ in analogy with (2.1), we will prove that: $$P^+_{k+1}\,\leq \, L_k^{2a}(P_k^+)^2 \;+\;\hbox{exp(-m}(\beta)2^{k+1}) \eqno (2.15)$$ where the constants m and a are as in theorem 2.1. As in the proof of theorem 2.1 it is easy to see that the result follows from (2.15) with e.g. $m_o(\beta)\,=\,{m(\beta)\over 2}$, if for some fixed $k_1$, e.g. $k_1\,=\,k_o$, we have $P_{k_1}^+ \;\leq\; {1\over L_{k_1}^{2a}}\hbox{exp(-m} _o(\beta)2^{k_1})$. This inequality is certainly true as $\beta \,\to\, \infty$ since we start with a configuration with no vacant bonds. Thus we will concentrate on the proof of the above modified recursion inequality.\v Let us consider $P(L,x,t,k+1,+)$ with $L>L_{k+1}$ fixed and x=0 for simplicity. If $t\,>\,t_{k+1}$ then by theorem 2.1 $$P(L,x,t,k+1,+)\,\leq\, \hbox{exp }(-m(\beta)2^{(k+1)}) \eqno (2.16)$$ If instead $t\,\leq\,t_{k+1}$ then, following the proof of theorem 2.1, we define the random times $\tau_1$ and $\tau_2$ as:\v {\bf Definition 3} \item{\bf a)} $\tau _1 \, = \, \hbox{min }\{s\,\geq\,0; \, \exists \;y \; \in \Lambda{L_{k+1}- sl_k} $ such that at time s + $1\over 2$ there exists a path of vacant bonds in ${\bf Z ^2}^* $ of length n $\geq L_k $ containing y$\}$ where $l_k\, = \, 4t_{k}L_k$ \item{\bf b)} Let $y_1$ be the leftmost and uppermost of the site y's appearing in the definition of the random time $\tau _1$. Then we set : \itemitem{} $\tau _2 \, = \, \hbox{min }\{s\geq\tau _1; \, \exists \;y \; \in \Lambda{L_{k+1}- sl_k} $ with $\delta (y,y_1$)$\geq (s+2-\tau_1)l_k$ such that at time s + $1\over 2$ there exists a path of vacant bonds in ${\bf Z ^2}^* $ of length n $\geq L_k $ containing y$\}$. \item{} For convenience the leftmost and uppermost of the sites y's appearing in the definition of $\tau _2$ will be denoted by $y_2$.\bigskip It is easy to see, following the same arguments explained in Remark 2, that necessarily $$P(L,x=0,t,k,+)\,\leq\, P(\tau_1\,\leq\,\tau_2\,\leq\,t)\,\leq$$ $$\leq \,\Sigma _{s_1\leq t}\Sigma _{s_2=s_1}^{t}\Sigma_{x_1 \in \Lambda_{k+1}}\Sigma_{x_2\in \Lambda_{k+1}} P(\{\tau _1 \, =\, s_1;\;y_1\,=\,x_1; \; \tau _2 \, = \, s_2;\;y_2\,=\,x_2\}) \eqno (2.17)$$ In order to estimate a generic term in the sums in (2.17) we proceed exactly as we did for the estimate of the r.h.s. of (2.10) and obtain the same result as in (2.11) (2.12) : $$P(\{\tau _1 \, =\, s_1;\;y_1\,=\,x_1; \; \tau _2 \, = \, s_2;\;y_2\,=\,x_2\})\,\leq \, (P_k^+)^2 \eqno (2.18)$$ that is the bound: $$t_{k+1}^2L_{k+1}^4P_k^2 \eqno (2.19)$$ for the r.h.s. of (2.17). If we now combine (2.19) together with (2.16) we get (2.15) and the theorem.\bigskip {\bf Remark 8} Exactly as for theorem 2.1 the result of theorem 2.2 applies also for the S-W dynamics with different boundary conditions like open periodic or (p,1-p) b.c. which do not induce by themselves a long path of vacant bonds in the corresponding Gibbs state.\bigskip We conclude with a rather standard application of the above result to the problem of the existence of an infinite cluster containing the origin for the S-W dynamics on the full lattice $\bf Z^d$. Of course on the whole lattice $\bf Z^d$ we need to give a prescription for the updating of clusters of infinite size. We decide to choose the (p,1-p)-rule which corresponds to set an infinite cluster equal to +1 with probability p and to -1 with probability 1-p. Thus the (1,0)-rule should correspond to the + b.c in the finite volume. It is easy to check that the result of theorem 2.2, being uniform in the volume, applies also to the infinite volume case with the (p,1-p)-rule. Then we have :\bigskip {\bf Corollary 2.1}\v There exists $\beta_o\,<\,\infty$ such that for any $\beta\,>\,\beta_o$ there exists c($\beta$) $\in \,(0,1)$ with $lim_{\beta \to \infty}c(\beta)\,=\,1$ such that for any value of p $\in \,[0,1]$, if $\eta (x)\,=\,1 \; \forall x\,\in {\bf Z^d}$, then we have: \item{a)} $$P_{\eta}(\hbox{diam}(C_t^{\infty}(0))\,=\,+\infty)\;\geq\;c(\beta)\quad \forall \,t$$ where $C_t^{\infty}(0)$ denotes the cluster containing the origin at time t + $1\over 2$ for the dynamics starting from $\eta$ in $\bf Z^d$ with the (p,1-p)-rule. \item{b)} For any time t there exists a unique infinite cluster with P=1.\bigskip {\bf Proof}\v \item{a)} We estimate $P_{\eta}(\hbox{diam}(C_t^{\infty}(0))\,<\,+\infty)$ by : $$P_{\eta}(\exists \,b\,\in \,\Lambda_{\bar k}\,;\,\hbox{ b is vacant at time }t\,+\,{1\over 2})\;+$$ $$+\;\Sigma_{k>\bar k}P_{\eta}(\hbox{ there exists a path of vacant bonds of length L }>\,L_{k-1} $$ $$\hbox{containing x, for some x in }\Lambda_{k}) \eqno (2.20)$$ The first term in (2.20) is bounded by : $$(2L_{\bar k})^d[({1\over 2})^{\beta}\,+\,(e^{-\beta})\beta]$$ if $t\,>\,\beta$ and by $\beta e^{-\beta}$ if $t\,\leq \,\beta$, while the second term is small for large $\bar k$ by theorem 2.2. Thus a) follows.\v b) If at time t there exist more than one infinite cluster then there exists a path of vacant bonds of infinite length. That is escluded by theorem 2.2. The existence with P=1 of one infinite cluster is assured by a) and by the ergodicity of the probability distribution at time t.\bigskip {\bf Section 3 \hskip 1cm Rate of convergence to equilibrium in a finite volume}\bigskip In this section we discuss the implication of our basic result theorem 2.1 to one of the most important problems of Monte Carlo algorithms, namely the rate of convergence of the probability distribution of the random dynamics at time t as $t\,\to \, \infty$ to the equilibrium measure given by the Gibbs state in a finite but large volume $\Lambda$. Thus let us fix a box of side 2L centered at the origin $\Lambda_L$, let f : $\{-1,1\}^{\Lambda_L}\,\to\,{\bf R}$ be an arbitrary observable and let $\mu^+_{\Lambda_L}(f)$ and $E_{\sigma}f(\sigma_t)$ denote the expected value of f with respect to the Gibbs state in $\Lambda_L$ with + b.c. and to the S-W dynamics with + b.c. at inverse temperature $\beta$ respectively. Then we will prove the following result:\bigskip {\bf Theorem 3.1}\v There exists $\beta_o\,<\,\infty$ and $c\,>\,0$ such that for any $\beta\,>\,\beta_o$ there exists a positive constant m$(\beta )$ with m$(\beta )\,>\,c$ such that for any t $>\,t(L)\,=\,\hbox{ exp(}ln(3)({ln(L)\over ln(4)})^{1\over 2})$: $$\sup_{\sigma}\vert \mu^+_{\Lambda_L}(f)\,-\,E_{\sigma}f(\sigma_t)\vert \;\leq\;2\vert f\vert_{\infty}\hbox{exp(-m(}\beta)t^{\alpha})$$ where $\alpha \,=\,{\hbox{ln}(2)\over \hbox{ln}(3)}$ and $\vert f\vert_{\infty} \,=\,\sup_{\sigma}\vert f(\sigma)\vert$.\bigskip Before proving the theorem it is important to understand the reason for the restriction on the time : t $>\,t(L)$. In a finite volume at zero temperature the equilibrium measure is totally concentrated on the plus configuration; moreover any initial configuration after a time of the order ln(L) also becomes identically equal to plus one. More precisely : $$\sup_{\sigma}P^{(\beta\,=\,\infty )}(\sigma_t(x)\,\neq \,1 \hbox{ for some x })\,\leq (2L)^d({1\over 2})^t$$ It is also easy to check that for certain anomalous initial configurations (e.g. a chessboard configuration) the above upper bound becomes almost exact. Thus equilibrium is only reached after a time of the order of the logarithm of the volume. At very low but positive temperature the result of theorem 2.1 proves that any configuration after a suitable time becomes almost one in the sense that with large probability a given site x is connected to the boundary of the chosen box; however, due to our choice of the time and length scales, the upper bound on the time necessary for this to happen, is not logarithmic in the volume but only of the form expressed in the theorem.\v {\bf Proof of theorem 3.1}\v The proof follows very closely the pattern of the proof of the same result given in [4] for the S-W dynamics with an external positive field. Let p(L,t) be defined by: $$p(L,t)\,\equiv \,\sup_{\sigma ,\eta}P(\eta_t\,\neq\,\sigma_t) \eqno (3.1)$$ where $\eta_t $ and $\sigma_t$ are coupled together in the sense that $\eta_t\,=\,\phi_t^{\Lambda_L,\omega}(\eta)$ and the same for $\sigma$, where $\omega$ is the same realizations of the random variables $\{\nu (s,b)\}$ and $\{\xi (s,C)\}$ for both. The quantity p(L,t) is in some sense a way to measure the memory of the dynamics of the initial condition. It is in fact easy to see [4] that: $$\sup_{\sigma}\vert \mu^+_{\Lambda_L}(f)\,-\,E_{\sigma}f(\sigma_t)\vert \;\leq\;2\vert f\vert_{\infty} p(L,t)\eqno (3.2)$$ Thus it will be sufficient to prove: $$p(L,t)\;\leq\;\hbox{exp(-m(}\beta)t^{\alpha})\quad \forall \;t\,>\,t(L)\eqno (3.3)$$ Following [*], the above inequality will be proved by means of a multiscale analysis similar to that involved in the proof of theorem 2.1 . Let the length and time scales $L_j$ $t_j$ be as in the previous section: $L_j\,=\,4^{j^2}$ $t_j\,=\,3^j$. Then we will set: $$p_j\;\equiv \;\sup_{(L_j\,\leq L\,\,j_o$ with $j_o$ large enough independently of $\beta$.\v Thus we are left with the proof of the inclusion: $$\Omega_o\;\subset \; \Omega_1 \eqno (3.11)$$ {\bf Lemma 3.1}\v If for any x in $\Lambda_L$ and any s in $[t_j,3t_j]$ diam($C_s(x)$) $\leq$ $L_{j-1}$ then: $$\Phi_{3t_j,t_j}^{\Lambda_j^x,+}(\eta_{t_j})(x)\;=\;\eta_{3t_j}(x) \eqno (3.12)$$ {\bf Proof}\v The proof is similar to Lemma 2.3 and it is by induction. For simplicity we only discuss the case where x coincides with the center of the box $\Lambda_j^x$; the other cases require only minor geometric modifications to the argument.\v Let us assume as induction hypotheses that: $$\Phi_{s,t_j}^{\Lambda_j^x,+}(\eta_{t_j})(y)\;=\;\eta_{s}(y) \eqno (3.13)$$ for any y inside $\Lambda_j^x\,-\,2(s-t_j)L_{j-1}$ and let us show that it propagates also to s+1.\v Let y be given inside $\Lambda_j^x\,-\,2(s+1-t_j)L_{j-1}$; then from the inductive hypothesis, at time s +$1\over 2$ the bond variables inside the box $\Lambda_j^x\;-\;2(s-t_j)L_{j-1}$ for $\eta_s$ and $\Phi_{s,t_j}^{\Lambda_j^x,+}(\eta_{t_j})$ are equal. Therefore if the cluster $C_s(y)$ computed for $\eta_s$ has diameter less than $L_{j-1}$ then necessarily it must coincide with the cluster of y computed for $\Phi_{s,t_j}^{\Lambda_j^x,+}(\eta_{t_j})$ and in this case $\eta_{s+1}(y)\,=\,\Phi_{s,t_j}^{\Lambda_j^x,+}(\eta_{t_j})(y)$ by construction.\v If diam($C_s(y)$)$\,>\,L_{j-1}$ then it must touch the boundary of $\Lambda_L$; on the other hand, again by the inductive hypothesis, also the cluster of y computed for $\Phi_{s,t_j}^{\Lambda_j^x,+}(\eta_{t_j})$ must have diameter greater than $L_{j-1}$. Therefore by construction $\eta_{s+1}(y)\,=\,\Phi_{s,t_j}^{\Lambda_j^x,+}(\eta_{t_j})(y)$ since the random flow $\Phi_{s,t_j}^{\Lambda_j^x,+}$ sets all cluster with diameter greater than $L_{j-1}$ equal to plus one. The Lemma is proved.\bigskip {\bf Section 4 \hskip 1cm Absence of ergodicity in infinite volume at low temperature}\bigskip In this section we apply the result of theorem 2.3 to prove that the S-W dynamics on the whole lattice $\bf Z^d$ is not ergodic at low temperature. Contrary to the case of short range attractive Glauber dynamics like the Metropolis or the Heath Bath algorithms, where the non ergodicity is easily proved using the attractivity of the dynamics, the problem of the ergodicity of the S-W dynamics in the infinite volume at zero external magnetic field is not trivial and moreover, in order to be well defined, it needs a prescription for the updating of clusters of infinite size. In fact, when a constant external field is applied, then any infinite cluster will flip in the direction of the field with probability one; obviously this is no longer true in the absence of the field. The prescription for the updating of an infinite cluster depends of course on which of the various Gibbs state of the Ising model at low temperature we choose as a candidate for the invariant measure for our d! ynamics. For example if we decide $$\mu_{\beta}\;=\;p\mu_+\,+\,(1-p)\mu_{-}\eqno (4.1)$$ where $\mu_{+}$ and $\mu_{-}$ are the extremal states of the two dimensional Ising model.\v We will prove below that this is not the case for p $\neq$ $1\over 2$; more precisely we will show that for p $\neq$ $1\over 2$ it is possible to find two different initial configurations $\sigma $ and $\eta$ such that $E(\sigma_t(0))\,=\,0$ and $\vert (E\eta_t(0))\vert\,>\,c\,>0$ for any integer time t and a suitable constant c depending on $\beta$. It is clear that such a result cannot depend only on the local properties of the dynamics but that it involves a control of the dynamics arbitrarily far away from the origin uniformly in the time t. \v Let $\eta$ and $\sigma$ be given by: $$\eta (x)\;=\;1\quad \forall \,x\,\in {\bf Z^d}$$ $$\sigma (x)\;=\;(-1)^{k} \quad \forall \,x \, \hbox{with } d(0, x)\,\in \,((k-1)^2,k^2]\quad k=1,2...$$ and let P($\xi (s,C)\,=\,1)\,=\,1-p$ whenever diam(C) = $\infty$. Then we have :\bigskip {\bf Theorem 4.1}\v There exists $\beta_o\,<\,\infty$ such that for any $\beta\,>\,\beta_o$ and any p $\in \,[0,1]$ there exists c($\beta$,p) $\in \,(0,1)$ with $\lim_{\beta \to \infty}c(\beta,p)\,=\,\vert 2p-1\vert$ such that: $$\eqalign{{\bf a)}\quad &\vert E(\eta_t(0))\vert\,\geq\;\;c(\beta,p)\quad \forall \,t\cr {\bf b)}\quad &\vert E(\sigma_t(0))\vert\;=\;0\quad \forall \,t}$$ {\bf Proof}\v \item{\bf a)} We write: $$\vert (E\eta_t(0))\vert\;=\;\vert\hbox{(p-(1-p))}\vert P_{\eta}(\hbox{diam}(C(t-{1\over 2},0))\,=\,\infty)\eqno (4.2)$$ and the result then follows from Corollary 2.1 . \item{\bf b)} For simplicity we only describe the two dimensional case. Using (4.2) it is sufficient to prove that $P_{\sigma}(\hbox{diam}(C(t-{1\over 2},0))\,=\,\infty)\;=\;0$ for any t. Let us assume that for any s $\leq \,t\,-\,{1\over 2}$ and any $x\,\in {\bf Z^d}$ $P_{\sigma}(\hbox{diam(}C(s,x))\,=\,\infty)\,=\,0$, let us fix k $>>$ 1 and let $\Lambda_k$ be equal to the anulus $\{x\,; \vert \vert x\vert \vert \,\in \,[(k-1)^2\,+\,{k\over 4},k^2\,-\,{k\over 4}]\}$. Then it is not difficult to see by the same methods used in the proof of Lemmas 2.3 3.1, that we can couple the dynamics starting from $\sigma$ in the whole lattice $\bf Z^d$ with the dynamics in $\Lambda_k$ with ($1\over 2$,$1\over 2$) b.c. in such a way that if the latter did not have a path of vacant bonds of length greater than $k\over 2t$ before time t, then up to time t - $1\over 2$ the two dynamics are identical for all x in $\Lambda_k$ with dist(x,$\partial \Lambda_k )\,>\,{k\over 4}$. Since the starti! ng configuration $\sigma$ is homo {\bf Remark 1} It would be interesting to generalize the above results to different initial conditions e.g. spin configurations with a density of spin-flips either very low or very high. This does not seem to be a trivial question since already for a chessboard spin configuration in two dimension it is not clear whether the dynamics is able to create in a finite time an infinite cluster already at zero temperature.\bigskip We conclude this section with two positive results concerning the long time behaviour of the probability distribution of the algorithm at time t in two dimensions. The first says that, starting from a configuration identically equal to plus or minus one, the time distribution converges weakly to the right mixture of the extremal states, while the second states that this holds no matter which starting configuration we choose, provided that we consider the dynamics given by the ($1\over 2$,$1\over 2$)-rule. \bigskip {\bf Theorem 4.2}\par Let $\eta_t$ denote the evolution at time t according to the (p,1-p)-rule in two dimensions where $\eta$ is identically equalt to either plus or minus one. Let A be a cylindrical event. Then for $\beta$ large enough we have: \item{\bf a)} $\lim_{t\to \infty}P(\eta_t\,\in\,A)\;=\;p\mu_+(A)\,+\,(1-p) \mu_-(A)$. \item{\bf b)} There exists $t_o(A)$ such that for any t$>$ $t_o(A)$ and some positive m: $$\vert P(\eta_t\,\in\,A)\;-\;p\mu_+(A)\,-\,(1-p) \mu_-(A)\vert \;\leq \;\hbox{exp(-m}t^{\alpha})$$ where $\alpha$ is as in theorem 3.1 .\bigskip {\bf Theorem 4.3}\par With the same notations of the previous theorem let p be equal to $1\over 2$. Then we have :\vskip 6pt \item{\bf a)} $\lim_{t\to \infty}P(\sigma_t\,\in\,A)\;=\;{1\over 2}\mu_+(A)\,+\,{1\over 2} \mu_-(A) \quad \forall \;\sigma \;\in\;\{-1,+1\}^{\bf z^2}$ \item{\bf b)} There exists $t_o(A)$ such that for any t$>$ $t_o(A)$ and some positive m: $$\vert P(\sigma_t\,\in\,A)\;-\;{1\over 2}\mu_+(A)\,-\,{1\over 2} \mu_-(A)\vert \;\leq \;\hbox{exp(-m}t^{\alpha})$$ where $\alpha$ is as in theorem 3.1 \bigskip {\bf Proof of theorem 4.2}\par Let $L_k$ and $t_k$ be the usual length and time scales, let $k_o$ be so large that the event A depends only on the spins inside $\Lambda_{k_o-1}$ and let t be such that $t_k\; <\; t\;\leq\; t_{k+1}$ for some $k\,>\,k_o\,+\,1$ . By our standard coupling technique (see Lemmas 2.3 3.1), we can couple the (p,1-p)-rule in the full lattice and the dynamics in $\Lambda_{k-1}$ with (p,1-p)-b.c. starting from $\eta$, in such a way that if for both dynamics, any site x of the box $\Lambda_{k-1}$ and any $s\leq t$ either diam($C_s(x))\,<\, L_{k-2}$ or x belonged to the infinite cluster ( boundary cluster ), then at time t they must coincide inside the box $\Lambda_{k_o}$. Using theorem 2.2 the probability for this not to happen is bounded from above by: $$t_{k+1}(2L_{k-1})^2{1\over L_{k-2}^{2a}}\hbox{exp(-m}_o(\beta)2^{k-2}) \eqno (4.3)$$ Therefore we immediately get that: $$\vert P(\eta_t\, \in \, A)\,-\,P(\eta_t^{\Lambda_{k-1}}\,\in\,A)\vert \;< \; t_{k+1}(2L_{k-1})^2{1\over L_{k-2}^{2a}}\hbox{exp(-m}_o(\beta)2^{k-2}) \eqno (4.4)$$ Moreover, using theorem 3.1, we have: $$\vert P(\eta_t^{\Lambda_{k-1}}\,\in\,A)\;-\;p\mu_+^{\Lambda_{k-1}}(A)\,-\,(1-p) \mu_-^{\Lambda_{k-1}}(A)\vert \;\leq $$ $$\hbox{2exp(-m}(\beta)t^{\alpha})\eqno (4.5)$$ with $\alpha$ as in theorem 3.1 .\v Thus part a) follows from the triangle inequality and the standard fact that : $$\vert \mu_+^{\Lambda_{k-1}}(A)\,-\,\mu_+(A)\vert \;<\;\hbox{exp(-c(}\beta )L_{k-1})$$ as $k\,\to\,\infty$ and the same for $\mu_-^{\Lambda_{k-1}}$.\v b) follows from the above explicit bounds.\bigskip {\bf Proof of theorem 4.3}\v The proof is almost identical to the proof of the previous theorem, although some care has to be paid to the coupling argument. Let $k_o$ and k be as in the proof of theorem 4.2 and let for s $>\,t_{k-1}$ $\; \tilde \sigma_s\,\equiv \, \Phi_{s,t_{k-1}}^{\Lambda_{k-1,p}}(\sigma_{t_{k-1}})$ be the evoluted at time s in the box $\Lambda_{k-1}$ of the configuration $\sigma_{t_{k-1}}$ according to the dynamics which sets the sign of all clusters with diameter greater than $L_{k-2}$ equal to the sign of the cluster of the boundary of the box $\Lambda_{k-1}$. For p=1 this dynamics coincides with the usual (+,k-2)-dynamics. In analogy with Lemma 3.1, let $\Omega_1$ be the event that, for the dynamics in the infinite volume, for any x in $\Lambda_{k-1}$ and any s in [$t_{k-1},t$] either diam($C_s(x))\, \leq\,L_{k-2}$ or the outermost boundary of $C_s(x)$ does not intersect the boundary of the box $\Lambda_{k-1}$; in this last case $C_s(x)$ does not depend on x in the sense that if diam($C_s(y))\,>\,L_{k-2}$ then $C_s(x)\,= \, C_s(y)$ (see e.g. Lemma 2.1) and, with an abuse of notation, it will be denoted $C_s^{\infty}$. If the event $\Omega_1$ occured, then we couple $\tilde \sigma_s$ with the dynamics in the full lattice $\sigma_s$ in the usual way namely : \item{\bf i)} bonds are made vacant at the same time for both and equal clusters which do not touch the boundary of $\Lambda_{k-1}$ do the same thing. \item{\bf ii)} the sign of the boundary cluster for $\tilde \sigma_s$ is the same as the sign of the cluster $C_s^{\infty}$ for $\sigma_s$.\par {\bf Remark 2} It is at this stage that p = $1\over 2$ is important. In fact the cluster $C_s^{\infty}$ may or may not be an infinite cluster; however if p = $1\over 2$ this will not affect its probability distribution .\par With this coupling it is easy to prove, following the proof of Lemma 3.1, that at time t\hskip 0.5cm $\tilde \sigma_t(x)\;=\;\sigma_t(x)$ for any x in $\Lambda_{k_o}$. Thus we get: $$\vert P(\tilde \sigma_t\, \in \, A)\,-\,P(\sigma_t\,\in\,A)\vert \;< \;P(\Omega_1)\;<\; t_{k+1}(2L_{k-1})^2{1\over L_{k-2}^{2a}} \hbox{exp(-m}_o(\beta)2^{k-2}) \eqno (4.6)$$ where we used theorem 2.1 in order to get the last inequality.\v Next we compare $P(\tilde \sigma_t\, \in \, A)$ with $P(\sigma_t^{\Lambda_{k-1}}\,\in\,A)$ where $\sigma_t^{\Lambda_{k-1}}$ is the evoluted at time of $\sigma$ in the box $\Lambda_{k-1}$ with the usual dynamics with ($1\over 2$,$1\over 2$)-b.c. . Using (3.5) we get that: $$\vert P(\tilde \sigma_t\, \in \, A)\;-\; P(\sigma_t^{\Lambda_{k-1}}\,\in\,A)\vert \;<\;p_{k-2}\;<\;\hbox{exp(-m}2^{k-2}) \eqno (4.7)$$ Thus the triangle inequality together with (4.6) (4.7) yelds the analogous of (4.5) and the rest of the proof is the same as the proof of theorem 4.2.\bigskip {\bf Section 5 \hskip 1cm Extension of the results to other models}\bigskip In this final section we briefly discuss the extension of the ideas and results presented in the previous sections to a different model of random cluster dynamics introduced in [19], sharing with the S-W algorithm without external field the property that the updating of clusters of dynamical variables (particles in our case) occurs with a probability independent of the geometry of the cluster.\v The two dynamics are however very different one from the other; the invariant measure of the S-W dynamics is the usual Gibbs measure of the Ising model, while the invariant measure of the second dynamics in dimension greater than two is not the Gibbs state for any absolutely summable interaction (see [19]).\par We do this in order to illustrate with a concrete example the genuine non equilibrium character of our techniques and to show that they work equally well for a dynamics which is not reversible with respect to an apriori probability measure.\par The setting is as follows: at each point x in the box $\Lambda = [-L,L]^d \cap {\bf Z}^d$ we associate an occupation variable $\sigma (x)$ with values 0 or 1; given a configuration $\sigma _t$ at time t in order to define the new configuration $\sigma _{t+1}$ at time t+1 we first consider all connected clusters of particles (sites in which the configuration $\sigma_t $ is equal to one) and we remove each cluster independently with probability 1/2 ; as a second step we create particles in each empty site independently with probability p. \par The above dynamics is similar to a model considered by Swindle and Graannan in [21] although in their model clusters disappear with a rate proportional to their size. We were primarily interested in the long time behaviour of the above stochastic cluster dynamics and in particular in questions like ergodicity, approach to equilibrium, mixing properties of the invariant measure. In turned out that in order to carry out this program it is crucial to have a good control of the range of the interaction namely of the typical size of the clusters. In the one dimensional case we could prove by means of a novel path expansion in space-time, that the probability that the origin belongs to a big cluster consisting of N particles is bounded by a negative exponential in N for any p $\in (0,1)$. As a consequence we can then prove for all p the exponential convergence as t tends to infinity of the distribution of the process at time t to the unique invariant measure together with the ex! ponential decay of correlations o In two or more dimensions the situation changes radically. For any p $\in $(0,1) we prove that the above probability cannot be bounded from above by a negative exponential in the number of sites of the cluster. More precisely, if $p_N(t)$ denotes the probability that the cube $Q_N$ of side N centered at the origin is filled with particles at time t, then we prove that for suitable constants $c_1,c_2,\alpha , \beta$ if t$\geq c_1N$ we have: $$\eqalign{&a) \quad p_N(t)\; \geq \; exp(-c_2N) \quad \forall p>0\cr &b) \quad {1\over N^\beta} \; \geq \; p_N(t) \;\geq \; {1\over N^\alpha} \quad \hbox{ if } 1-p<<1}\eqno (5.2)$$ However the question of an upper bound for the above probability for small values of p remained open, together of course with the problem of existence and uniqueness of the invariant measure in the same range of values of p. It is our goal here to fill this gap by stating results very similar to those already explained for the S-W dynamics; the proofs are however a duplicate of those given in the previous sections, and we will therefore only describe the results and the main ideas.\v Let $C_{\Lambda}$ be the collection of all possible connected subsets I of $\Lambda$. Here I is connected iff for any two sites x and y there exists a path of nearest neighbors sites in I going from x to y.\par Let also $\{\nu (x,s)\}_{x\in \Lambda ,s\in {\bf N}}$ and $\{\xi (I,s)\}_{I\in C_{\Lambda} ,s\in {\bf N}}$ be i.i.d. random variables with values in $\{0,1\}$ with: \centerline{P($\nu (x,s)=1$)=p ,\hskip 1cm P($\xi(I,s)=1$)=$1\over 2$}\bigskip For shortness a realization of the $\nu (x,s)$ ($\xi (I,s)$) variables will be denoted by $\nu$ ($\xi$). On each site x of $\Lambda$ we will associate an occupation variable $\sigma (x)$ taking values in $\{0,1\}$; for shortness the collection of the variables $(\sigma (x))_{x \in \Lambda}$ will be denoted by $\sigma$. Thus $\sigma$ is an element of the configuration space S = $\{0,1\}^\Lambda$. Using the r.v. $\nu \, ,\, \xi$ we now construct on S a random dynamics starting at the configuration $\sigma$ at time t=0 as follows: \item{i)} Given $\sigma^{\Lambda} _t \, \in \, S$ we set for any x$\in \Lambda$: $$\sigma^{\Lambda}_{t+{1\over 2}}(x)=1 \quad \hbox{iff} \quad \sigma^{\Lambda} _t(x)=1 \quad \hbox{and } \xi (I_x,t)=1$$ where $I_x$ is the maximal element of C$_{\Lambda}$ containing x such that $\sigma^{\Lambda}_t(y)=1\,\, \forall \, y\, \in I$. \item{ii)} For any x$\in \Lambda$: $$\sigma^{\Lambda} _{t+1}(x)=0 \quad \hbox{iff} \quad \sigma^{\Lambda} _{t+{1\over 2}}(x)=0 \quad \hbox{and }\quad \nu (t+1,x)=0$$ For shortness we will refer to the first part i) of the updating as the killing of particles and to the second part ii) as the creation of particles. Note that both processes occurs simultaneously (i.e. the updating is parallel) and that the non trivial interaction of the model is all contained in the killing process .\par We will refer to the above rules as the "{\bf basic dynamics in $\Lambda$}". The associated Markov process will always be denoted by $\sigma _t$ omitting the suffix $\Lambda$ for shortness whenever it does not produce confusion. The time t will always take integer values; however sometimes we will consider events involving the values of the process both at time t and at time $t+{1\over 2}$.\par It is very easy to check that in any finite volume $\Lambda$ there exists a unique invariant measure that will be denoted by $\mu _{\Lambda}$.\par Later on in the work, when discussing the approach to equilibrium for the process we will need to compare the dynamics of a given site x produced by two different boxes $\Lambda$ and $\Lambda '$ with $\Lambda ' \subset \Lambda$ both containing x. This will be done by establishing a coupling between the two dynamics according to the following rules: \item{\bf a)} The variables $\nu (x,s)_{x\in \Lambda '}$ are exactly the same variables that one choses for the dynamics in $\Lambda$ i.e. if a particle is created inside $\Lambda '$ for the dynamics in $\Lambda$ then it is created also for the dynamics in $\Lambda$' and viceversa. \item{\bf b)} The value of $\xi (I,s)$ is the same for both dynamics if $I\subset \Lambda '$.\bigskip In some sense the above coupling is the most natural way to restrict the dynamics in $\Lambda$ to $\Lambda '$.\par In one dimension however there is a more efficient way to realize this coupling in such a way that the value of the process at a given site x inside $\Lambda$' will always be equal for the two dynamics.\v We will now state a basic estimate on the probability that the cluster of a given fixed point x at some time t has a diameter greater than L, with t greater than some scale t(L) related to L.\v Let us first fix some notations similar to those used in section 2.\v For any integer k we define: $$p_k\,=\,\sup_{l\geq L_k;x\in\Lambda_L;t\geq t_k;\sigma \in \{-1,1\}^{\Lambda_L}}P(L,x,t,k,\sigma) $$ where $P(L,x,t,k,\sigma) $ is the probability that the cluster of particles containing the site x has diameter greater than $L_k$, where $L_k$ and $t_k$ are as in section 2. Then the following result holds:\bigskip {\bf Theorem 5.1}\v There exists $p_o\,>\,0$ $c\,>\,0$, $k_o\,>\,0$ and $a\,>\,0$ such that for any $p\,<\,p_o$ there exists a constant m $\equiv $ m(p) with m $>$ c such that: $$p_k\;<\;{1\over L_k^{2a}}\hbox{exp(-m}2^k)\quad \forall \;k\,>\,k_o$$ {\bf Corollary 5.1}\v For p sufficiently small there exists a unique invariant measure $\mu$ for the basic dynamics in $\bf Z^d$ such that: \item{\bf a)} Given a cylindrical event A there exists t(A) such that: $$\vert P(\sigma_t\,\in\,A)\;-\;\mu (A)\vert \;<\;\hbox{exp(-mt}^{\alpha})$$ for some positive m and any t $>$ t(A), where $\alpha\;=\;{ln(2)\over ln(3)}$. \item{\bf b)} Let f and g be local observables depending only on the value of the configuration $\sigma (x)$ for x in A and in B respectively with d(A,B) = L, and let $\vert f\vert_{\infty}$ denote the sup norm. If $$ denotes the expression: $$\int d\mu(\sigma)f(\sigma)g(\sigma)\quad -\quad (\int d\mu(\sigma)f(\sigma))(\int d\mu(\sigma)g(\sigma))$$ Then we have: $$\quad \leq \quad \hbox{exp(-m(p)}2^{k(L)})$$ for a suitable positive constant m(p), where k(L) is such that $L_{k}\;\leq \;L\,\,t(L) $ and t(L) = exp($ln(3)({ln(L)\over ln(4)})^{1\over 2}$) . \item{\bf iii)}By combining i) and ii) one approximates the average at time t $>$ exp($ln(3)({ln(L)\over ln(4)})^{1\over 2}$) of a local observable with its average with respect to the equilibrium measure associated to dynamics in the cube of side L, with an error that tends to zero as $L\,\to \,\infty$ uniformly in the initial configuration $\sigma$. \item{\bf iv)} Step iii) immediately implies the convergence as $t\,\to \,\infty$ of the average at time t of any local observable uniformly in the initial configuration and thus also the uniquiness of the invariant measure. It also follows that finite volume equilibrium measure converges weakly to the invariant measure of the process in the infinite volume.\vskip 8pt Part b) follows simply by the explicit bounds that one has in the previous steps.\vfill {\bf References}\vskip 20pt \item{[1]} R.H. Swendsen, J.S. Wang ``Nonuniversal critical dynamics in Monte Carlo simulations'' Phys. Rev. Lett. {\bf 58} 86 (1987). \item{[2]} R.G. Edwards, A.D. Sokal, ``Generalization of the Fortuin-Kasteleyn-Swendsen-Wang representation and Monte Carlo algorithm'', Phys. Rev. D {\bf 38}, No 6, 2009 (1988). \item{[3]}J.Goodman, A.D. Sokal ``Multigrid Monte Carlo method: Conceptual foundations'' Physical Review D {\bf 40} N.6 2035 (1989). \item{[4]} F. Martinelli, E. Olivieri, E. Scoppola ``On the Swendsen and Wang dynamics I. Exponential convergence to equilibrium'' J.Stat. Phys {\bf 62} N. 1/2 117 (1991). \item{[5]} F. Martinelli, E. Oliveri, E. Scoppola, ``On the Swendsen and Wang dynamics II : Critical droplets and homogeneous nucleation at low temperature for the 2 dimensional Ising model'' Journ. Stat. Phys {\bf 62} N. 1/2 135 (1991). \item{[6]} P.W. Kasteleyn, C.M. Fortuin, ``On the random cluster model. I: Introduction and relation to other models'', Physica {\bf 57}, 536 (1972). \item{[7]} P.W. Kasteleyn, C.M. Fortuin J.Phys. Soc. Jpn. Suppl.{\bf 26} 11 (1990) \item{[8]} R.H. Swendsen, J.S. Wang ``Cluster Monte Carlo algorithms'' Physica A {\bf 167} 565-579 (1990) \item{[9]} U.Wolff Phys. Lett. B {\bf 62} 361 (1989). \item{[10]} D.Kandel, R.Ben-Av and E.Domany ``Cluster dynamics for fully frustrated systems'' Phys. Rev. Lett. {\bf 65} 941 (1990) \item{[11]} U.Wolff Phys. Lett. B {\bf 228} 379 (1989). \item{[12]} M.D'Onofrio De Meo,D.W.Heermann, K.Binder ``Monte Carlo study of the Ising model phase transition in terms of the percolation transition of "physical clusters" '' J.Stat.Phys. {\bf 60} No 5/6 585 (1990). \item{[13]} Xiao-Jian-Li, A.D. Sokal, ``Rigorous lower bound on the dynamical critical exponent of the Swendsen--Wang dynamics'', Phys. Rev. Lett. {\bf 63}, 8, 827 (1989). \item{[14]} Von Dreyfus, ``On the effect of randomness in ferromagnetic models and Schr\"oedinger operators'', Ph. D. Thesis New York (1987). \item{[15} Jordao-Neves and R.Schonmann ``Critical droplets and metastability for a Glauber dynamics at very low temperature'' to appear in Comm.Math.Phys. \item{[16]} D.A.Huse and D.S.Fisher Phys. Rev. B {\bf 35} 6841 (1987) \item{[17]} A.D. Sokal and L.E.Thomas " Absence of mass gap for a class of stochastic contour models" Journal Stat. Phys. {\bf 51} 907 (1988) \item{[18]}A.L. Toom ``Stable and attractive trajectories in multicomponents random fields'' in Multicomponenets Random Fields, R.L.Dobrushin and Ya.G.Sinai eds. New York, Marcel Dekker 1980 \item{[19]} F.Martinelli and E.Scoppola ``A simple stochastic cluster dynamics: rigorous results'' CARR reports in math.phys. 24/90 Roma to appear in J.Phys.A: Math. Gen. \item{[20]} J.L. Lebowitz and R.H. Schonamnn ``Pseudo-Free Energies and Large Deviations for Non Gibbsian FKG Measures'' Prob.Th. Rel. Fields {\bf 77} 49 (1988) \item{[21]} G.Swindle and E.Grannan ``A particle system with massive destruction'' J.Phys.A: Math. Gen. {\bf 23} L73 (1990) \bye