%LaTeX Version 2.09 <7 Dec 1989>
\documentstyle[12pt]{article}
\newtheorem{Theorem}{Theorem}
\newtheorem{Lemma}{Lemma}
\begin{document}
\title{Extended application of high noise constructive
criteria for interacting particle systems}
\author{Hans de Jong \\
{\small Institute for Theoretical Physics, University of Groningen}\\
{\small Nijenborgh 4, 9747 AG Groningen, The Netherlands}\\
{\small {\tt dejong@th.rug.nl}}\\
{\small}
\and Christian Maes \\
{\small Aangesteld Navorser NFWO }\\
{\small Institute for Theoretical Physics, University of Leuven}\\
{\small Celestijnenlaan 200D, 3001 Leuven, Belgium }\\
{\small {\tt Christian=Maes\%tf\%fys@cc3.kuleuven.ac.be}}}
\date{\ }
\maketitle
\begin{abstract}
We discuss computational aspects of verifying constructive criteria
for the ergodicity of interacting particle systems. Both discrete
time
(probabilistic cellular automata) and continuous time spin flip
dynamics
are considered. We also investigate how the addition of an exchange
or stirring dynamics influences the criteria and how the study of a
corresponding percolation problem may sometimes improve the usual
ergodicity criteria when considering dynamics on arbitrary graphs.\\ \\
{\bf Key words:} interacting particle systems, probabilistic cellular
automata, ergodicity, constructive criteria, computational aspects,
stirring dynamics, disagreement percolation.
\end{abstract}
\section{Introduction}
\paragraph{}
There are by now quite a number of examples of phase transitions in
interacting particle systems and probabilistic cellular automata. These are
large systems consisting of many individual components that, due to local
interactions
or transition rules, evolve stochastically from given initial data.
After a long time, the system may
or may not have forgotten where it started
from, depending on certain parameters governing the updating.
The ergodic regime is that region in parameter space where,
for all initial data, the
system converges to the same and unique invariant measure. Just like in
equilibrium systems where it concerns the uniqueness of Gibbs states, there
are a number of explicit conditions on the transition rule that, if
satisfied, guarantee that the model is ergodic. We concentrate in this
paper
on constructive criteria that where developed in \cite{MS1},
\cite{MS2} and \cite{MS3}.
In particular we investigate how practical they are and
how we best deal with them. In that sense, the paper has to do with
computational aspects. The
most non--trivial part of it concerns the continuous time case. So far,
there was no example where the constructive criteria went
substantially
beyond the usual (single site) criterion. We analyze this problem here
and give such an example.
\paragraph{}
The outline of the paper is as follows. In the next
section we discuss the discrete time case of spin flip dynamics. Stirring
(a spin exchange mechanism) is added in section 3. Section 4 is devoted to the
relation of the question of ergodicity with a corresponding oriented
percolation problem. Finally, in section 5, we treat the continuous
time case.
\section{Constructive criteria for PCA}
\label{cc for PCA}
\paragraph{}
First, we briefly recall some concepts, definitions and notation
concerning probabilistic cellular automata (PCA, from now on),
ergodicity and coupling. Secondly,
we will state constructive criteria for
exponential
ergodicity of PCA. We then show that certain properties of PCA allow these
criteria to be simplified. Finally, we will use these criteria by hand
and with a computer to get bounds for critical parameter values for three
simple one--dimensional PCA.
\subsection{Introduction to PCA}
\paragraph{Notation.}
$L$ is a countably infinite set. Unless otherwise
specified, we always take $L$ to be the $d$--dimensional hypercubic
lattice {\boldmath $Z^d$}. Attach to every $x \in L$ an Ising spin
$\sigma(x)$. A configuration $\sigma$ on $L$ is a complete characterization
of all of these spins:
\begin{equation}
\sigma : L \longrightarrow \{-,+\}
\end{equation}
The set of all configurations is $\Omega=\{-,+\}^L$ with its usual product
structure.
The set of real valued continuous functions on $\Omega $
is denoted by $C(\Omega )$, it is equipped with the uniform norm
\begin{equation}
\|f\| = \sup_{\sigma \in \Omega} |f(\sigma )|
\end{equation}
$E(\Omega)$ is the set of the probability measures on $\Omega$.
$\sigma^y$ is the configuration that differs from
$\sigma$ only at $y$:
\begin{equation}
\sigma^y(x) = \left \{ \begin{array}{rl}
\sigma(x) & {\rm if} \ x \neq y \\
-\sigma(x) & {\rm if} \ x = y
\end{array}
\right.
\end{equation}
The maximal variation of a function $f\in C(\Omega)$ due to a spin flip at
$x$ is given by \begin{equation}
\delta_x f = \sup_{\sigma \in \Omega} |f(\sigma^x) - f(\sigma)|
\end{equation}
The total oscillation of $f$ is then:
\begin{equation}
|||f||| = \sum_{x \in L} \delta_x f
\label{var norm}
\end{equation}
The subspace of $C(\Omega)$ on which this semi--norm is finite will be
called $D(\Omega)$.
Since $D(\Omega)$ contains the
local functions, it is dense in $C(\Omega)$.
\paragraph{What is a PCA?}
A PCA is a discrete time Markov process $\{\sigma_n\}_{n=0,1,\dots}$
on $\Omega$. It is characterized by transition probabilities
\begin{equation}
\{p_x(\pm|\tau)\}_{x \in L} \label{char}
\end{equation}
local in $\tau\in\Omega$.
$p_x(+|\tau )$ is the probability that the spin
$\sigma(x)$ at place $x$ will be $+$ if the configuration was $\tau$ at the
previous time. Usually $p_x(+|\tau )$ is invariant under equal translations of
$x$ and $\tau$.
At every step all spins
are simultaneously and independently updated, so that for every finite
$\Lambda \subset L$
\begin{equation}
{\rm Prob} [\forall x \in \Lambda:\sigma_n(x) = \upsilon(x) |
\sigma_{n-1} = \tau] =
\prod_{x \in \Lambda} p_x(\upsilon(x)|\tau)
\end{equation}
Hence a PCA defines a map from $\Omega$ into $E(\Omega)$. The
probability measure over the configurations $\sigma$, given the
configuration $\tau$ at the previous time is denoted by $P(d\sigma|\tau)$.
This kernel
induces a mapping from $C(\Omega)$ into itself by
\begin{equation}
(Pf)(\cdot) = \int f(\sigma) P(d\sigma|\cdot)
\end{equation}
and yet another map from $E(\Omega)$ into itself:
\begin{equation}
(\mu P)(f) = \mu(Pf)
\end{equation}
Usually it is clear from the context what ``$P$'' means.
\paragraph{Ergodicity.}
It is interesting to know about the long time behavior of the PCA.
Loosely speaking, a PCA is ergodic if the measure on the configuration space
after infinitely many applications of the PCA--rule is independent of the
initial measure. An ergodic PCA--dynamics ``forgets'' its past.
More precisely
\paragraph{Definition}
{\em A PCA is ergodic iff there is a $\nu \in E(\Omega )$, so
that for all $\mu \in E(\Omega )$
\begin{equation}
\mu P^N {\longrightarrow} \nu \
\mbox{weakly as } \ N \longrightarrow \infty
\label{def ergodicity}
\end{equation}}
\subsection{Theory of constructive criteria}
\paragraph{}
A good way to compare probability measures is to ``couple'' them. In the
constructive criteria below, the influence of the choice of initial
configuration on the long
time behavior of the PCA is investigated by considering a ``coupling''
between the PCA and itself, starting with a pair of
configurations disagreeing at one site only.
\paragraph{Coupling.}
Suppose we have two probability measures $q$ and $\bar{q}$ on one and the same
finite set $W = \{1,2,\dots,n\}$. Then a coupling {\boldmath $q$} of them is a
probability measure on $W \times W$ that has $q$ and $\bar{q}$ as marginals:
\begin{equation}
\begin{array}{rl}
\sum_{j=1}^n \mbox{\boldmath $q$}(i,j) =& \!\! q(i) \nonumber\\
\sum_{i=1}^n \mbox{\boldmath $q$}(i,j) =& \!\! \bar{q}(j)
\end{array}
\end{equation}
We call a coupling optimal if the sum of the off--diagonal elements is
minimal. If $n \geq 4$, there may be more than one optimal
coupling {\boldmath $q$}.
A prescription that is always successful in getting one is:
\begin{equation}
\mbox{\boldmath $q$}(i,j) = \left \{
\begin{array}{rl}
\min\{q(i),\bar{q}(i)\}&{\rm if} \ i=j \\
v^{-1} (q(i)-\mbox{\boldmath $q$}(i,i))
(\bar{q}(j)-\mbox{\boldmath $q$}(j,j))&{\rm if} \ i\neq j
\end{array}
\right.
\label{q_ij}
\end{equation}
$v$ is the variational distance between $q$ and $\bar{q}$:
\begin{equation}
v= \mbox{var}[q,\bar{q}] = \frac{1}{2} \sum_{i=1}^n |q(i) - \bar{q}(i)|
= 1-\sum_{i=1}^n \mbox{\boldmath $q$}(i,i)
= \sum_{i \neq j} \mbox{\boldmath $q$}(i,j)
\label{var dist}
\end{equation}
We see that $v$ equals the sum of the off--diagonal elements of the
optimal coupling.
\paragraph{The coupled PCA.}
The coupling between two PCA's $P$ and $\bar{P}$
is a new PCA {\boldmath$P$} on the product configuration
space $\Omega \times \Omega$.
{\boldmath$P$} is characterized (in the same way as in (\ref{char}) for the
original PCA) by:
\begin{equation}
\{ \mbox{\boldmath $p$}_x(\cdot,\cdot|\tau,\bar{\tau}) \}_{x \in L}
\label{fat p}
\end{equation}
where $\mbox{\boldmath $p$}_x(\cdot,\cdot|\tau,\bar{\tau})$ is the optimal
coupling between $p_x(\cdot|\tau)$ and $\bar{p}_x(\cdot|\bar{\tau})$. So
now we
have a PCA with 4 instead of 2 spin values per site. The ``marginals'' of
the coupled PCA {\boldmath$P$} are the original processes: let
$g(\sigma,\bar{\sigma})=f(\sigma)$ for $f \in
C(\Omega )$, then {\boldmath $P$}$g = Pf$.
{\boldmath $P$} is known as the {\em basic}
coupling. In what follows we will always take the basic coupling of two
PCA with identical transition rules but started from different initial
configurations.
\paragraph{Constructive criteria.}
We need two more definitions. The first quantity expresses the maximal
probability that a single disagreement at time $0$ at site $x$ between
the two initial configurations results in a disagreement between the
spins at $(N,y)$, under the stochastic evolution of the basic coupling:
\begin{equation}
\kappa^N_{yx} = \sup_\tau
{\rm Prob}[\sigma_N(y) \neq \bar{\sigma}_N(y)|(\sigma_0,\bar{\sigma}_0)
=(\tau,\tau^x)]
\label{kappa}
\end{equation}
Secondly, a measure of the cumulative effect of disagreements at all sites
on a spin, $N$ time steps later, is given by
\begin{equation}
\gamma_N = \sup_y \sum_x \kappa^N_{yx}
\label{gamma_N}
\end{equation}
Intuitively, it is clear that if $\gamma_N$ is ``small'', then the influence of
disagreements between the initial configurations is small, or, in other words,
the evolution under the original PCA--rule is
relatively independent of the initial configuration, which is close to
saying that the PCA is ergodic.
The following Theorem of \cite{MS2} makes these statements precise.
\begin{Theorem}
If there is an $N=1,2,\dots$ such that $\gamma_N < 1$ then the PCA is
exponentially ergodic and for all functions $f\in D(\Omega)$
\begin{equation}
\left\| P^{aN+b} f - \int f(\sigma) \nu(d\sigma) \right\| \leq
\frac{\gamma_N^a}{1-\gamma_N} |||P^b f|||
\label{MSCC eq}
\end{equation}
where $\nu$ is the unique invariant measure ($\nu=\nu P$), $a$ is integer
and $b=0, 1, \dots, N-1$.
\label{MSCC}
\end{Theorem}
\paragraph{Remarks.}
\begin{enumerate}
\item Note that $Pf \in D(\Omega)$ whenever $f\in D(\Omega)$ so that the right
hand side in (\ref{MSCC eq}) is finite.
\item These criteria are called constructive because they involve checking an
inequality on explicitly defined quantities that depend on a finite number
of spins only (see (\ref{kappa}) and (\ref{gamma_N})).
\item
As $N$ increases, the criteria become better in a sense which is explained
in \cite{MS2}. In particular, for attractive PCA (see later), some
criterium must be satisfied ($\gamma_N < 1$ for large enough $N$) whenever
the PCA converges fast enough to its unique invariant measure.
\end{enumerate}
\subsection{Simplifications}
\label{Simplifications}
We will investigate three simple one--dimensional PCA: Stavskaya's model,
the asymmetric contact process and a hard--core model. Before
applying the constructive criteria to these PCA we will look at some of
their properties that will simplify the analysis.
\subsubsection{Three simple one--dimensional PCA}
\paragraph{Stavskaya's model.}
Stavskaya's model \cite{T1} is one--dimensional, it has transition rules
\begin{equation}
p_x (+|\sigma(x),\sigma(x+1)) =
\left \{ \begin{array}{rl}
1 & \!\! {\rm if} \ \sigma(x)=\sigma(x+1)=+\\
\lambda & \!\! {\rm otherwise}
\end{array}
\right.
\end{equation}
The all $+$ configuration is invariant under application of the PCA--rule.
If $\lambda$ is close to $1$, it is easy to see that the measure
over the configurations tends to the $\delta$--measure on the all $+$
configuration after infinitely many applications of the PCA--rule,
independently of the initial configuration. On the other hand,
you can use Toom's argument (treated in full generality in \cite{T2}
and specifically for Stavskaya's model in \cite{DKT})
to show that if $\lambda$ is small enough,
a non--zero fraction of $-$ will survive forever, if you start with the all
$-$ configuration. It can be proved that there is a critical
$\lambda^*$ separating ergodic and non--ergodic behavior.
\paragraph{The asymmetric contact process.}\hspace{-2.01355 pt}A
generalization of Stavskaya's model is the asymmetric
contact process. It is
characterized by:
\begin{equation}
p_x (+|\sigma(x),\sigma(x+1)) =
\left \{ \begin{array}{rl}
1 & \!\! {\rm if} \ \sigma(x)=\sigma(x+1)=+\\
1-\delta M & \!\! {\rm if} \ \sigma(x)=+ \ {\rm and} \ \sigma(x+1)=-\\
\delta & \!\! {\rm otherwise}
\end{array}
\right.
\end{equation}
If you interpret $+$ and $-$ as healthy and sick individuals respectively and
$\delta$ and $\delta M$ as the recover and
infection--by--the--right--neighbor
rate, the process can be seen as a discrete time model for the spreading
of an infectious disease through a population. We will always take
$1-\delta M \geq \delta $. The spin flip probability is proportional to
$\delta$.
The all $+$ configuration is again invariant, and it is interesting to see
how
large you can choose $M$ such that there is a $\delta$ for which
this configuration is still the unique attractor of the system. The largest
such $M$ will be denoted by $M^*$. Other interest of the process lies in
the fact that it is a discrete time
approximation of a continuous time process. In Section 5 we will see how
the
analysis of this discrete time approximation can help us to investigate the
behavior of the corresponding continuous time process.
\paragraph{The hard--core PCA.}
This PCA is again one--dimensional and it is defined by:
\begin{equation}
p_x (+|\sigma(x),\sigma(x+1)) =
\left \{ \begin{array}{rl}
\rho & \!\! \mbox{if}\ \sigma(x)=\sigma(x+1)=-\\
0 & \!\! \mbox{otherwise}
\end{array}
\right.
\end{equation}
The name ``hard--core'' comes from the interpretation of putting a particle
on a $+$ site, and having a vacancy on a $-$ site. On the space--time
square lattice, with $\{(t,x)=(-1,1),(0,1),(0,0),(1,0)\}$ as an
elementary square, it is not possible to have two particles as nearest
neighbors. One does however not recover the ``usual'' hard--core or
hard square model as corresponding two--dimensional equilibrium statistical
mechanical model. The difference is that here in some finite space--time
box, not all allowed configurations with the same number of particles have
the same probability of occuring. For the two--dimensional hard--core
model (a zero temperature limit of the Ising anti--ferromagnet in an
external field), \cite{DKS} applied
a computer assisted analysis to investigate the
uniqueness of Gibbs measures with the aid of the so
called Dobrushin--Shlosman constructive criteria.
Recently van den Berg \cite{B} and van den Berg and Steif \cite{BS}
improved on this analysis with a percolation argument.
We define the quantity $\rho^*$ as the largest density
parameter $\rho$ below which the PCA is certainly ergodic.
\subsubsection{Attractivity and anti--attractivity}
\paragraph{Attractivity.}
Although we can apply the constructive criteria to the above PCA directly,
a better
look at them pays off. An important property of Stavskaya's model and the
asymmetric contact process is their attractivity. A PCA is called attractive
if
\begin{equation}
\sigma \geq \bar{\sigma} \Longrightarrow p(+|\sigma) \geq p(+|\bar{\sigma})
\end{equation}
(Of course $\sigma \geq \bar{\sigma}$ means that $\forall x \in L:
\sigma(x) \geq \bar{\sigma}(x)$.)
This order will persist in time under
application of the basic coupling as stated in the following well--known
\begin{Lemma}
In the basic coupling of an attractive PCA with itself,
order is conserved in time:
\begin{equation}
\sigma_0 \geq \bar{\sigma}_0 \Longrightarrow {\rm Prob}[\sigma_N \geq
\bar{\sigma}_N|\sigma_0,\bar{\sigma}_0] = 1, \forall N = 1,2,\dots
\label{attr}
\end{equation}
\end{Lemma}
Attractivity greatly simplifies the expression for $\kappa^N_{yx}$:
\begin{equation}
\kappa^N_{yx} = \sup_{\sigma_0}
\left| {\rm Prob}[\sigma_N(y)=+|\sigma_0] -
{\rm Prob}[\bar{\sigma}_N(y)=+|\sigma^x_0] \right|
\label{kappa attr}
\end{equation}
The proof is a simple consequence of (\ref{attr}).
Therefore, we do not have to look at the basic coupling
in order to determine $\gamma_N$ for an attractive PCA.
By this observation, the number of space--time
configurations to consider, reduces to its square root.
\paragraph{Anti--attractivity.}
The hard--core PCA has a property which is opposite to attractivity:
\begin{equation}
\sigma \geq \bar{\sigma} \Longrightarrow p(+|\sigma) \leq p(+|\bar{\sigma})
\end{equation}
We propose to call this property ``anti--attractivity''.
The order in the basic coupling oscillates:
\begin{equation}
\sigma_0 \geq \bar{\sigma}_0 \Longrightarrow
\left \{
\begin{array}{r}
{\rm Prob}[ \sigma_{2N-1} \leq
\bar{\sigma}_{2N-1}|\sigma_0,\bar{\sigma}_0] = 1\\
{\rm Prob}[ \sigma_{2N} \geq \bar{\sigma}_{2}|\sigma_0,\bar{\sigma}_0] = 1
\end{array}
\right.
\ \ \ (N=1,2,\dots)
\end{equation}
For the same reasons as in the attractive case,
the expression for $\kappa^N_{yx}$ reduces to (\ref{kappa attr}) again.
\subsubsection{The worst initial configuration}
The calculation for $\kappa^N_{yx}$ decreases
if you know for which initial configuration $\sigma_0$ the supremum
in its expression is reached.
For the contact process and Stavskaya's model we know this
``worst'' initial configuration.
\begin{Lemma}
The initial configuration $\sigma_0 \equiv +$ yields the supremum in the
expression for
$\kappa^N_{yx}$ for the asymmetric contact process and Stavskaya's model.
\end{Lemma}
\paragraph{Proof.}
We give the proof for the contact process.
Define for $\sigma_0 \geq \bar{\sigma}_0$:
\begin{equation}
Q^N_y (\sigma_0,\bar{\sigma}_0) =
{\rm Prob}[\sigma_N(y)=+|\sigma_0] - {\rm
Prob}[\bar{\sigma}_N(y)=+|\bar{\sigma}_0]
\end{equation}
We proof by induction that $Q^N_y$ increases under the following types
of ``spin flips'':
\begin{equation}
(\sigma_0(x),\bar{\sigma}_0(x)) = (-,-) \longmapsto (+,-) \ {\rm or} \ (+,+)
\label{actions}
\end{equation}
(We use quotation marks to distinguish these special spin flips.)
This is clear for $N=1$.
Express $Q^N$ in $Q^{N-1}$:
\begin{equation}
Q^N_y(\sigma_0,\bar{\sigma}_0) = \int \!\!\! \int
Q^{N-1}_y(\sigma_1,\bar{\sigma}_1)
\mbox{\boldmath $P$}(d\sigma_1,d\bar{\sigma}_1|\sigma_0,\bar{\sigma}_0)
\end{equation}
By attractivity, the ``spin flips'' on $(\sigma_0,\bar{\sigma}_0)$ cause
{\boldmath $P$}$(d\sigma_1,d\bar{\sigma}_1|\sigma_0,\bar{\sigma}_0)$
to shift some weight from configurations $(\sigma_1,\bar{\sigma}_1)$
to ``spin flipped'' (in the sense of (\ref{actions})) versions of them.
So {\boldmath $P$} will be more concentrated on configurations where,
by the induction hypothesis,
$Q^{N-1}$ is large; thus $Q^N$ increases by ``spin flips''.
One can prove this by checking what happens to
$\mbox{\boldmath $p$}_x(\sigma_1(x),\bar{\sigma}_1(x)|
\sigma_0,\bar{\sigma}_0)$.
For instance, if
$(\sigma_0(0),\sigma_0(1),\ \bar{\sigma}_0(0),\bar{\sigma}_0(1))$ flips
from $(-+,--)$ to $(++,+-)$ then
\begin{equation}
\begin{array}{lrcr}
\mbox{\boldmath $p$}_0(--|\sigma_0,\bar{\sigma}_0) = &1 - \delta
&\longmapsto& 0 \\
\mbox{\boldmath $p$}_0(+-|\sigma_0,\bar{\sigma}_0) = &0
&\longmapsto& \delta M \\
\mbox{\boldmath $p$}_0(++|\sigma_0,\bar{\sigma}_0) = &\delta
&\longmapsto& 1 - \delta M
\end{array}
\end{equation}
Weight is transported from $(-,-)$ to $(+,-)$ and $(+,+)$. Thus a ``spin
flip'' on $(\sigma_0,\bar{\sigma}_0)$ causes ``spin flips'' on
$(\sigma_1,\bar{\sigma}_1)$. The other configurations
$(\sigma_0(0),\sigma_0(1),$ $\bar{\sigma}_0(0),\bar{\sigma}_0(1))$ can be
checked in the same way.
Under the condition $\bar{\sigma}_0 = \sigma_0^x$, $Q^N_y
(\sigma_0,\bar{\sigma}_0)$ obviously reaches its maximum at
$\bar{\sigma}_0 \equiv +$, it coincides with $\kappa^N_{yx}$ \
then. \hfill {\Huge${\bullet}$}
\subsection{Results obtained with the constructive criteria}
\label{Results}
\paragraph{}
In this section we will use the constructive criteria to
get bounds for critical parameter values for Stavskaya's model, the
one--di\-men\-sional asymmetric contact process and the hard--core PCA.
Basically, there are three ways to apply the
criteria to specific PCA. The first is to do the calculations by
hand, this method works only for simple PCA and small $N$.
Much higher order criteria can be obtained by programming the calculations on a
computer. The third method estimates the $\kappa^N_{yx}$ by observing
simulations of the basic coupling on a computer.
\subsubsection{Application of the constructive criteria by hand}
\paragraph{}
With the simplifications of the previous subsection in mind, it is relatively
easy to calculate $\gamma_N$ for $N \leq 3$ by hand,
for the three PCA mentioned before. We give the analytic expressions for
$\gamma_N$
together with bounds for critical parameter values obtained with these
criteria.
\subparagraph{Stavskaya's model.}
\begin{eqnarray}
\gamma_1 = 2(1-\lambda) &\Longrightarrow& \lambda^* \leq 0.5 \\
\gamma_2 = (1-\lambda)^2(3+\lambda) &\Longrightarrow& \lambda^* < 0.4626 \\
\gamma_3 = 4(1-\lambda)^3(1+\lambda) &\Longrightarrow& \lambda^* < 0.4425
\end{eqnarray}
\subparagraph{Asymmetric contact process.}
\begin{eqnarray}
\gamma_1 &=& 1 + \delta(M-1)\\
&\Longrightarrow& M^* \geq 1 \nonumber \\
\gamma_2 &=& 1+2\delta(M-1)+
\delta^2 (1-2M) + \delta^3 M^2\\
&\Longrightarrow& M^*>1.15 \ \ \ (\delta =0.46)\nonumber \\
\gamma_3 &=& 1 + 3\delta(M-1) +3\delta^2(1-2M) +
\nonumber \\
&& \delta^3(-1+3M+4M^2) - 5\delta^4 M^2 + \delta^5(M^2 + M^3)
\nonumber \\
&\Longrightarrow& M^* > 1.26 \ \ \ (\delta = 0.43)
\end{eqnarray}
(In \cite{MS2} and \cite{MS3} there was an error in the expression for
$\gamma_3$.)
\subparagraph{Hard--core PCA.}
\begin{eqnarray}
\gamma_1 = 2 \rho &\Longrightarrow& \rho^* \geq 0.5 \\
\gamma_2 = \rho^2(4-\rho) &\Longrightarrow& \rho^* > 0.5374 \\
\gamma_3 = 2\rho^3(2-\rho)^2 &\Longrightarrow& \rho^* > 0.649
\end{eqnarray}
Calculations by hand become very tedious and unreliable for higher order
criteria. At this point {\sl Mathematica} helps us to get analytic
expressions for $\gamma_N$ for larger $N$. We are, however, mainly
interested
in the paramater values for which $\gamma_N \approx 1$, so we can
better do
calculations with fixed parameters with a conventional programming language
like {\sl Pascal}.
\subsubsection{Calculations of $\gamma_N$ by computer}
\paragraph{}
We have written simple {\sl Pascal} programs for the computation of
$\gamma_N$. Central in our calculations is of course the Markov property
which leads to recursive relations which for the above PCA are
\begin{eqnarray}
{\rm Prob}[\sigma_N(0)=+|\sigma_0(0),\sigma_0(1),\dots,\sigma_0(N)]
= \sum_{\sigma_1(0)=-}^+
\sum_{\sigma_1(1)=-}^+
\dots
\sum_{\sigma_1(N-1)=-}^+ \nonumber \\
{\rm Prob}
[\sigma_N(0)=+|\sigma_1(0),\sigma_1(1),\dots,\sigma_1(N-1)]
\ \prod_{x=0}^{N-1} p(\sigma_1(x)|\sigma_0) \ \ \ \ \ \ \
\label{recursion}
\end{eqnarray}
Some relevant results of these computer--calculations are as follows:
\subparagraph{Stavskaya' model.}
\begin{equation}
\gamma_{28}(\lambda = 0.358) = 0.986 \Longrightarrow \lambda^* <0.358
\end{equation}
\subparagraph{Asymmetric contact process.}
\begin{equation}
\gamma_{24}(M = 1.84) = 0.9993
\Longrightarrow M^*>1.84 \ \ \ (\delta = 0.23)
\end{equation}
\subparagraph{Hard--core PCA.}
\begin{equation}
\gamma_{17}(\rho = 0.83) = 0.9947
\Longrightarrow \rho^* > 0.83
\end{equation}
\subsubsection{Checking the constructive criteria by means of simulations.}
\paragraph{}
The last method to investigate a PCA's behavior with regard to ergodicity is
to look at simulations of the coupled PCA. $\kappa^N_{yx}$ is then obtained
by recording the frequency of the event $\sigma_N(y) \neq \bar{\sigma}_N(y)$
for all relevant different initial configurations $(\sigma_0,\sigma_0^x)$,
and taking the maximum over these frequencies.
\paragraph{}
We will explain this method for the asymmetric contact process in some
more detail. Because of the properties mentioned before, the expression for
$\gamma_N$ reduces to
\begin{equation}
\gamma_N = \sum_{x=0}^{-N} {\rm Prob}[\sigma_N(x)=-|\sigma_0=+^0]
\end{equation}
where $+^0$ is the configuration which is $+$ everywhere except at $x=0$.
In a simulation of the PCA, the configuration at the next time $n$ is obtained
in the following way: draw for each site $x$ a (pseudo--)random number $s$,
with $0 \leq s < 1$, and apply then the rule
\begin{equation}
\begin{array}{rl}
\sigma_n(x) = + &{\rm if} \ s \leq p_x(+|\sigma_{n-1}) \\
\sigma_n(x) = - &{\rm if} \ s > p_x(+|\sigma_{n-1})
\end{array}
\end{equation}
Let the PCA ``run'' many times inside the ``triangle''
\begin{equation}
\{(t,x)|t \in \{1,2,\dots,N\},x \in \{-t,-t+1,\dots,0\} \}
\end{equation}
(everything outside the triangle is $+$), and count each time the number of
$-$ in the configuration $\sigma_N$. $\gamma_N$ is simply the average.
This procedure can easily be programmed on a computer.
We have done that for Stavskaya's model and the contact process.
Significant results are given below.
\subparagraph{Stavskaya's model.}
\begin{equation}
\gamma_{100}(\lambda = 0.331) = 0.98 \pm 0.01
\stackrel{\rm very \ probably}{\Longrightarrow} \lambda^*<0.331
\end{equation}
\subparagraph{Asymmetric contact process.}
\begin{equation}
\gamma_{100}(M=2.22) = 0.976 \pm 0.006
\stackrel{\rm very \ probably}{\Longrightarrow} M^*>2.22 \ \ \ (\delta=0.15)
\end{equation}
\paragraph{}
If you do not know the worst initial configuration, simulation techniques
become much harder to apply. One complication is the large number of
initial configurations to look at, this number increases exponentially in
$N$. Another complication arises when a lot of initial configurations
are (almost) the worst. Because of statistical fluctuations, taking simply
the worst--looking initial configuration will yield an overestimation of
$\kappa^N_{yx}$ and $\gamma_N$. One would have to do an immense number of
simulations
to get rid of this effect. It is preferable to apply ``smart'' methods:
first
simulate all initial configurations equally often, later more and more
concentrate the simulations on the seemingly bad ones.
\paragraph{}
In this technique of checking the MSCC with simulations,
one does finite time observations
and one obtains statements, with well--defined confidence, about the long
time behavior of the PCA.
\section{Combinations of spin flip and stirring processes}
\paragraph{}
If we imagine spin values as indicating different types of molecules,
spin flip processes model chemical reactions and stirring processes can
be seen as models for the motion of the molecules. In some contexts
combinations of spin flip and stirring processes are therefore called
``reaction--diffusion'' processes. We investigate here which implications
the addition of stirring has for the constructive criteria.
At the end of this section we will
compare our results with similar work by Ferrari \cite{F2}.
\paragraph{}
First we will introduce the concept ``mixer'', this is the
stochastic transformation rule that defines the stirring process.
Usually we denote a mixer by an ``$M$''. $M$ is related to the stirring
process as the PCA--rule $P$ is to the spin flip process.
\paragraph{Definition.}
To start with, we need a partition $\{A_i\}_{i \in I}$ of our lattice.
The sets $A_i$ in this partition are finite.
Suppose that for each $i \in I$ we have a probability distribution
$\alpha_i$ on the set ${\cal S}_i$ of permutations on
$A_i$.
We then define the mixer $M$ acting on $f\in C(\Omega)$ as
\begin{equation}
Mf(\sigma) = \int f(\eta) M(d\eta|\sigma)
\label{adjointperm} \end{equation}
where, for every $\sigma\in\Omega, M(d\eta|\sigma)$ is the product
measure $\prod_{i\in I} M_i(\eta|\sigma)$ with marginals
$M_i(\cdot|\sigma)$ on $\{-,+\}^{A_i}$ giving
probability $\alpha_i(q), q\in$ ${\cal S}_i$, to the configuration
\begin{equation}
\eta(x) = \sigma(q(x)), x\in A_i
\label{mixdef}
\end{equation}
\paragraph{Example.}
$M$ interchanges with probability $\frac{1}{2}$ spins in sets of type
$A_i = \{2i,2i+1\}, i \in \mbox{\boldmath $Z$}.$
\paragraph{Remark 1.}
In a stirring process obtained by consecutive application of a
mixer $M$, there is no exchange of spins between different sets $A_i$ of the
partition. To get a more thorough stirring one can take a convex
combination
or a product of $M$ and its ``translates'', instead of the single mixer $M$.
The translate $M'$ of the mixer in the above example is: $M'$ interchanges with
probability $\frac{1}{2}$ spins in sets of type
$A'_i = \{2i-1,2i\}, i \in \mbox{\boldmath $Z$}.$ The results of the analysis
below will not alter if we take such a generalized mixer instead of a single
mixer.
\paragraph{Remark 2.}
Note that within each set of the partition, a mixer conserves the number
of plus spins. So, a stirring process cannot have the same ergodic behavior as
a spin--flip process (see the previous section).
\paragraph{}
The stochastic transformation rule of a spin flip
stirring process is a convex combination of products of mixers and PCA.
We are interested in the long time behavior of these processes.
Although we can directly apply the constructive criteria
to these mixer--PCA to detect
ergodicity, the addition of stirring makes calculations considerably
larger. Fortunately however, we can get criteria for mixer--PCA from the
constructive criteria for the PCA alone, with help of the following
\begin{Lemma}
\begin{equation}
|||M||| \leq \ 1
\end{equation}
\end{Lemma}
\paragraph{Proof.}
Suppose that $x\in A_i$. Take
\mbox{\boldmath $M$} to be the coupled mixer that acts exactly the same on
both configurations, i.e., \mbox{\boldmath $M$} $= \prod_{i\in I}$
\mbox{\boldmath $M$}$_i$ and
\mbox{\boldmath $M$}$_i(\cdot,\cdot|\sigma,\bar{\sigma})$ gives
probability $\alpha_i(q), q\in$ {\cal $S_i$} to the (new)
configuration
$(\tau(y),\bar{\tau}(y))=(\sigma(q(y)),\bar{\sigma}(q(y)))$ (analogous
to (\ref{mixdef})).
\begin{eqnarray}
| Mf(\sigma ^x)-Mf(\sigma)| &=& \Bigl| \int
(f(\bar{\tau})-f(\tau)) \ \mbox{\boldmath $M$}(d\bar{\tau}d\tau|
\sigma^x \sigma )\Bigr| \\
&\leq& \sum \limits_{y \in L} \delta_y f \int
\mbox{\boldmath $1$}(\tau_y \neq \bar{\tau }_y) \ \mbox{\boldmath
$M$}(d\bar{\tau}d\tau| \sigma^x \sigma ) \\
&=& \sum \limits_{y \in A_i} \delta_y f
\sum \limits_{q : q(y)=x} \alpha_i(q)
\end{eqnarray}
Take suprema and sum over $x$:
\begin{equation}
|||Mf||| \leq \sum \limits_{i\in I} \sum \limits_{y \in A_i}
\delta_y
f \sum \limits_{x \in A_i} \ \sum \limits_{q : q(y) = x} \alpha_i(q)
= |||f|||
\end{equation}
\hfill {\Huge $\bullet$}
\paragraph{Remark 1.}
Although we do not need it, equality in the Lemma holds: $|||M||| =
1$.
\paragraph{Remark 2.}
The proof of the Lemma depends crucially on the fact that $M$ is
independent of the
configuration. If it is not, $|||M||| \leq 1$ does not need to be true.
\paragraph{Implications of the constructive criteria and Lemma 3.}
We illustrate what happens
with a few examples.
We find upper bounds for the triple norms of some combinations of PCA and
mixers. The first example is simply the product of a PCA and a mixer:
\begin{equation}
S_1 = PM
\end{equation}
Because
\begin{equation}
|||S_1||| \leq |||P||| \cdot |||M||| = |||P|||
\end{equation}
$S_1$ is ergodic if $\gamma_1 <1$ is satisfied for
the PCA. Here
higher order constructive criteria for the PCA cannot be used to get stronger results.
However, for the example
\begin{equation}
S_2 = MP^5
\end{equation}
it is enough that $\gamma_5 < 1$.
The next mixer--PCA:
\begin{equation}
S_3 = M_1 P^3 M_2^2 P^2
\end{equation}
is ergodic if
\begin{equation}
\gamma_3 \cdot \gamma_2 < 1
\end{equation}
Finally we look at a stochastic transformation rule that chooses randomly
at each time to be a PCA or to be a mixer:
\begin{equation}
S_4 = \lambda M +(1-\lambda )P,\ {\rm with} \ \lambda \in [0,1)
\end{equation}
$S_4$ will be ergodic if the criterion $\gamma_1 <1$ for the PCA is satisfied.
\paragraph{Comparison with Ferrari's results.}
The constructive criteria for pure PCA are better in detecting ergodic
behavior than Ferrari's generalized duality argument of \cite{F2}. This
argument says that a PCA is exponentially ergodic if:
\begin{equation}
r(1-2k) < 1
\end{equation}
with
\begin{equation}
r = \sup_{x,\sigma} |R_x|
\end{equation}
with $R_x$ the neighborhood of $x$ where $p_x(+|\sigma)$ depends on
$\sigma$, and
\begin{equation}
k = \min_{x,\sigma} \{p_x(+|\sigma),1-p_x(+|\sigma)\}
\end{equation}
It is easy to check that already the $\gamma_1 < 1$ criterion is more powerful
than Ferrari's criterion. Higher order constructive criteria are even better.
Both criteria remain valid if we combine our PCA with mixers.
As we have seen, for some combinations it is even possible to use higher
$N$ MSCC.
Both methods fail if the mixer depends on the configuration.
So, we improve on Ferrari's results.
\paragraph{About continuous time.}
Ferrari also considered combinations of spin flip and stirring
dynamics in continuous time \cite{F2}. He shows there that if the spin
flip process satisfies some criterion stronger than the so--called
``$M<\epsilon$''--criterion (see section \ref{continuous time IPS})
the spin flip stirring process is still ergodic. In this section we
have seen that the $\gamma_1<1$ criterion of the spin flip process
alone remains valid if we add stirring. Since this criterion implies
the ``$M<\epsilon$''--criterion for continuous time we also improve
on Ferrari's results for continuous time.
\section{Ergodicity of PCA and oriented percolation}
\paragraph{}
Ergodicity means forgetting about initial conditions. Intuitively, we
can picture this as absence of percolation for paths starting at a
space--time point and running backwards in time thereby connecting points
that have undergone the influence of the initial state. We make this
more precise following an construction analogous to the one made for Markov
fields in \cite{BM}. The main advantage of this approach here is that
it allows to connect quite generally critical behavior in an oriented
percolation problem to phase transitions for PCA.
\subsection{Disagreement percolation for PCA}
\paragraph{}
As we have seen before, the basic coupling for a PCA defines a new PCA on
the product space. Starting at time zero from the pair $(\sigma
,\bar{\sigma })$ of configurations $\sigma ,\bar{\sigma } \in \Omega $, we
obtain a Markov process $(\sigma _N,\bar{\sigma }_N), N= 0, 1, 2,\dots $,
with $(\sigma_0, \bar{\sigma }_0)=(\sigma,\bar{\sigma })$, whose transition
probabilities satisfy
\begin{equation}
{\rm Prob}[\sigma _N(i) \neq \bar{\sigma }_N(i)| \sigma _{N-1} = \xi
,\bar{\sigma }_{N-1} = \bar{\xi }] = {\rm var} [p_i(\cdot|\xi
),p_i(\cdot|\bar{\xi })]
\label{var2}
\end{equation}
the right hand side being the variational distance between the (original)
PCA transition probabilities $p_i(\cdot|\xi )$ and $p_i(\cdot|\bar{\xi })$
for
given $\xi ,\bar{\xi } \in \Omega $, (see (\ref{var dist})). For every
realization
$(\sigma _N(i),\bar{\sigma }_N(i)), i \in \mbox{\boldmath $Z$}^d, N = 0, 1,
2,\dots$, let us now define new variables
\begin{equation}
s_N(i) = \left\{
\begin{array}{l}
1 \ {\rm if } \ \sigma _N(i) \neq \bar{\sigma }_N(i) \\
0 \ {\rm otherwise}
\end{array}
\right.
\label{s}
\end{equation}
We say that the space--time point $(N,i)$ is {\em open} (respectively closed)
if $s_N(i)=1$ (respectively $s_N(i)=0$).
>From (\ref{var2}) we can see that, with probability one
with respect to the basic coupling, the point $(N,i)$ is open only if there
is a point $(N-1,j)$ with $j$ in the neighborhood of $i$, which is also
open. But then, there must be an {\em oriented path of disagreement} from
the point $(N,i)$ to some point $(0,j)$ on the zero--time layer, that is,
a sequence of open points $v_0,v_1,\dots,v_N$ with $v_0 = (N,i)$ and
$v_n=(N-n,j_n)$ such that $j_n$ is in the neighborhood of $j_{n-1},
n=1,\dots,N$. In fact, we have that in the basic coupling
\begin{equation}
{\rm Prob}[\sigma _N(i) \neq \bar{\sigma }_N(i)|\sigma ,\bar{\sigma }] =
{\rm Prob}[(N,i) \leadsto (0,\cdot)|\sigma ,\bar{\sigma }]
\label{path}
\end{equation}
where $(N,i) \leadsto (0,\cdot)$ stands for the event that there is an
oriented path of disagreement from $(N,i)$ to some $(0,j), j \in
L$. Since we have that
\begin{equation}
|P^Nf(\sigma )-P^Nf(\bar{\sigma })| \leq \sum_i \delta_i f \ {\rm Prob}
[\sigma _N(i) \neq \bar{\sigma }_N(i)|\sigma ,\bar{\sigma }]
\label{p min p}
\end{equation}
for functions $f \in D(\Omega)$, we see from
(\ref{path}) that the absence of oriented percolation for the field defined
in (\ref{s}) will imply uniqueness of the invariant state for our PCA. To
make this more precise and to turn this into a simple uniqueness
criterion, we define the quantity
\begin{equation}
q_i = \max_{\xi ,\bar{\xi }} \ {\rm var}[p_i(\cdot|\xi ),p_i(\cdot|\bar{\xi
})]
\label{q}
\end{equation}
which of course always exceeds (\ref{var2}). We can then consider the
product measure $\nu _{\{q_i\}}$ : zero--one variables
$\tilde{s}_N(i)$ are assigned to the vertices of the same space--time
lattice as before:
\begin{equation}
\tilde{s}_N(i) =
\left\{
\begin{array}{l}
1 \ \mbox{with probability}\ q_i \\
0 \ \mbox{with probability}\ (1-q_i)
\end{array}
\right.
\end{equation}
independently for all $i \in L, N= 1, 2, \dots$. For
completeness, we put $\tilde{s}_0(i) = 1$. Now note that because of
(\ref{q}) the $\{s_N(i)\}$ process and the $\{\tilde{s}_N(i)\}$ process can
be coupled in such a way that $s_N(i) \leq \tilde{s}_N(i) $ with
probability
one for every space--time point. This, in turn, implies that (\ref{path})
is dominated by the probability
\begin{equation}
\nu _{\{q_i\}}[(N,i) \leadsto (0,\cdot)]
\label{nu}\
\end{equation}
of {\em independent} oriented percolation (here, an open path is one
on which all of the $\tilde{s}_N(i)$ are 1). Hence, from (\ref{p min p}),
\begin{equation}
\sup_{\sigma ,\bar{\sigma }} |P^Nf(\sigma )-P^Nf(\bar{\sigma })| \leq
\sum_i
\delta _i f \ \nu _{\{q_i\}} [ (N,i) \leadsto (0,\cdot)] \leq c_N |||f|||
\label{p min p 2}
\end{equation}
where
\begin{equation}
c_N=\sup_j
\nu_{\{q_i\}}[(N,j) \leadsto (0,\cdot)]
\label{q_c}
\end{equation}
If the $\{q_i\}$ are
small enough so that
\begin{equation}
c_N \longrightarrow 0\ {\rm as} \ N \uparrow \infty
\end{equation}
then
the PCA is ergodic and converges uniformly to the unique invariant measure.
We have thus proven
\begin{Theorem}
If in {\rm (\ref{q_c})} $c_N \longrightarrow 0$ as $N \uparrow \infty$, then
the PCA
is ergodic and for all
$f\in D(\Omega)$,
\begin{equation}
\|P^N f(\sigma ) - \nu(f)\| \leq c_N |||f|||
\end{equation}
where $\nu $ is the unique invariant measure.
\end{Theorem}
\subsection{Applications}
We have in mind two sorts of applications. The first consists in applying
the uniqueness criterion (\ref{q_c}) to various examples to obtain bounds
on the critical parameters in terms of percolation thresholds. The second
application is to consider PCA on arbitrary graphs and random PCA.
\subsubsection{Examples.}
Naturally, all the information we have on the threshold $q_c$ for
independent oriented percolation can be
translated into information about the ergodic regime of our PCA. This works
best in those cases where in fact (\ref{q}) equals
\begin{equation}
q_i = \max_\xi {\rm var}[p_i(\cdot|\xi ),p_i(\cdot|\xi ^j)]
\label{q_i}
\end{equation}
for all $j$ in the neighborhood of $i$.
If we assume that each neighborhood contains exactly $R$ sites, then the
Dobrushin single--site criterion ($N=1$ in Theorem \ref{MSCC}) gives
\begin{equation}
R \sup_i q_i <1
\label{Peierls}
\end{equation}
while we know from a Peierls--type estimate that this
inequality certainly implies that $c_N\longrightarrow
0$.
In fact the estimate in (\ref{Peierls}) is expected to be rather bad
for low dimensional graphs. Stavskaya's model and
the hard--core PCA are two examples where the situation as in
(\ref{q_i})
occurs and for which $R=2$. In both models the space--time graphs are the
same and they are equivalent to the usual square lattice.
In the figure below,
a part of this space--time graph is depicted. Open points are marked with
open circles. An oriented path of disagreement from $(7,0)$ to $(0,3)$ is
shown.
Defining $q_c$ to be the threshold
for independent site oriented percolation on this space--time
lattice, we certainly have that $q_c \geq p_c(2)$, the threshold for
independent
site percolation on the square lattice. It is rigorously
(and computer--assisted) known that $p_c(2)
\geq 0.54\dots $ (see Menshikov and Pelikh \cite{MP}) so that
(\ref{Peierls}) is indeed {\em strictly} improved by
Theorem 2.
\setlength{\unitlength}{0.333333333333333333in}
\begin{picture}(11,11)(-1,-1)
\multiput(1,9)(1,0){8}{\circle*{0.1}}
\multiput(1,8)(1,0){7}{\circle*{0.1}}
\multiput(1,7)(1,0){6}{\circle*{0.1}}
\multiput(1,6)(1,0){5}{\circle*{0.1}}
\multiput(1,5)(1,0){4}{\circle*{0.1}}
\multiput(1,4)(1,0){3}{\circle*{0.1}}
\multiput(1,3)(1,0){2}{\circle*{0.1}}
\multiput(1,2)(1,0){1}{\circle*{0.1}}
\put(0.5,8.9){\small 0}
\put(0.5,7.9){\small 1}
\put(0.5,6.9){\small 2}
\put(0.5,5.9){\small 3}
\put(0.5,4.9){\small 4}
\put(0.5,3.9){\small 5}
\put(0.5,2.9){\small 6}
\put(0.5,1.9){\small 7}
\put(0.5,0.9){\small $N$}
\put(0.7,0.6){\vector(0,-1){0.7}}
\put(0.9,9.3){\small 0}
\put(1.9,9.3){\small 1}
\put(2.9,9.3){\small 2}
\put(3.9,9.3){\small 3}
\put(4.9,9.3){\small 4}
\put(5.9,9.3){\small 5}
\put(6.9,9.3){\small 6}
\put(7.9,9.3){\small 7}
\put(8.9,9.3){\small $x$}
\put(9.4,9.4){\vector(1,0){0.7}}
\multiput(1,9)(1,0){8}{\circle{0.2}}
\put(2,8){\circle{0.2}}
\put(4,8){\circle{0.2}}
\put(6,8){\circle{0.2}}
\put(7,8){\circle{0.2}}
\put(1,7){\circle{0.2}}
\put(3,7){\circle{0.2}}
\put(4,7){\circle{0.2}}
\put(6,7){\circle{0.2}}
\put(2,6){\circle{0.2}}
\put(3,6){\circle{0.2}}
\put(3,5){\circle{0.2}}
\put(3,4){\circle{0.2}}
\put(2,4){\circle{0.2}}
\put(2,3){\circle{0.2}}
\put(1,2){\circle{0.2}}
\put(1,2){\vector(1,1){1}}
\put(0.99,2.01){\vector(1,1){1}}
\put(0.995,2.005){\vector(1,1){1}}
\put(1.01,1.99){\vector(1,1){1}}
\put(1.005,1.995){\vector(1,1){1}}
\put(2,3){\vector(1,1){1}}
\put(1.99,3.01){\vector(1,1){1}}
\put(1.995,3.005){\vector(1,1){1}}
\put(2.01,2.99){\vector(1,1){1}}
\put(2.005,2.995){\vector(1,1){1}}
\put(3,4){\vector(0,1){1}}
\put(2.99,4){\vector(0,1){1}}
\put(2.995,4){\vector(0,1){1}}
\put(3.01,4){\vector(0,1){1}}
\put(3.005,4){\vector(0,1){1}}
\put(3,5){\vector(0,1){1}}
\put(2.99,5){\vector(0,1){1}}
\put(2.995,5){\vector(0,1){1}}
\put(3.01,5){\vector(0,1){1}}
\put(3.005,5){\vector(0,1){1}}
\put(3,6){\vector(0,1){1}}
\put(2.99,6){\vector(0,1){1}}
\put(2.995,6){\vector(0,1){1}}
\put(3.01,6){\vector(0,1){1}}
\put(3.005,6){\vector(0,1){1}}
\put(3,7){\vector(1,1){1}}
\put(2.99,7.01){\vector(1,1){1}}
\put(2.995,7.005){\vector(1,1){1}}
\put(3.01,6.99){\vector(1,1){1}}
\put(3.005,6.995){\vector(1,1){1}}
\put(4,8){\vector(0,1){1}}
\put(3.99,8){\vector(0,1){1}}
\put(3.995,8){\vector(0,1){1}}
\put(4.01,8){\vector(0,1){1}}
\put(4.005,8){\vector(0,1){1}}
\multiput(1,9)(0,-0.1){70}{\circle*{0.001}}
\multiput(2,9)(0,-0.1){60}{\circle*{0.001}}
\multiput(3,9)(0,-0.1){50}{\circle*{0.001}}
\multiput(4,9)(0,-0.1){40}{\circle*{0.001}}
\multiput(5,9)(0,-0.1){30}{\circle*{0.001}}
\multiput(6,9)(0,-0.1){20}{\circle*{0.001}}
\multiput(7,9)(0,-0.1){10}{\circle*{0.001}}
\multiput(1,2)(0.1,0.1){70}{\circle*{0.001}}
\multiput(1,3)(0.1,0.1){60}{\circle*{0.001}}
\multiput(1,4)(0.1,0.1){50}{\circle*{0.001}}
\multiput(1,5)(0.1,0.1){40}{\circle*{0.001}}
\multiput(1,6)(0.1,0.1){30}{\circle*{0.001}}
\multiput(1,7)(0.1,0.1){20}{\circle*{0.001}}
\multiput(1,8)(0.1,0.1){10}{\circle*{0.001}}
\put(5,0){\bf Fig. 1}
\end{picture}
\subsubsection{PCA on arbitrary graphs}
Let $L$ be an arbitrary (infinite) graph which is locally finite. That is,
every site $i \in L$ has a finite neighborhood consisting of $R_i$
neighbors $j$ for which the right hand side of (\ref{q_i}) is non--zero. One
can ask whether there is an $\epsilon >0$ such that, if
\begin{equation}
q_i \equiv \max_{\xi,\bar{\xi }} \ {\rm var}[p_i(\cdot|\xi
),p_i(\cdot|\bar{\xi })] \leq \epsilon
\label{q_i 2}
\end{equation}
for all $i \in L$, then the PCA has a unique invariant measure. In the
case where the $R_i$ are uniformly bounded, this is certainly so, as
follows already from Dobrushin's single--site condition ($N=1$ in
(Theorem \ref{MSCC})).
But without this restriction, this answer is certainly false in
general
and must depend on the particularities of the graph $L$. In
fact, answering this question goes beyond the constructive
criteria that we discussed before, as these criteria (see Theorem
\ref{MSCC})
always suppose uniform bounds. The situation is reminiscent of the
problem of uniqueness of Gibbs measures on arbitrary graphs. There
the problem was solved by an analysis of Bassalygo and Dobrushin
in \cite{BD} who found a natural condition on the graph for which
the corresponding question to (\ref{q_i 2}) is positive. In that
respect, the Theorem above sheds
some light on this question for PCA. In order to apply it, consider
the oriented percolation
problem on the space--time graph generated by $L$. Put $\nu_q$ the
Bernoulli measure on this graph which makes every space--time point open
(respectively closed) with probability $q$ (respectively $1-q$). Then,
putting all $q_i=q$ in (\ref{q_c}),
\begin{equation}
q_c = \inf \{q \in [0,1]: c_N\longrightarrow 0 \ \mbox{as} \ N \uparrow
\infty \}
\end{equation}
is the usual threshold probability. The answer to the question in (\ref{q_i
2}) is then positive whenever $q_c >0$. It is an
intrinsic property of the space--time graph.
\subsubsection{Random PCA.}
A logical continuation of the previous line of thinking would be to
consider the problem of ergodicity for random PCA (see the analog for
Gibbs measures in \cite{BD}). These are PCA for which the transition
rules $p_i(\pm|\xi)$ depend on random variables (quenched disorder).
This would however lead us too far away from the main subject of this
paper; we prefer to postpone this analysis to later work.
\section{An application of the constructive criteria for
interacting particle systems}
\label{continuous time IPS}
\paragraph{}
Steif's idea \cite{S} to approximate continuous time interacting particle
sytems (IPS) by
PCA is used by \cite{MS2} and \cite{MS3} to obtain ergodicity criteria for
IPS.
We treat a specific example to show how to
improve drastically on the well--known ``$M<\epsilon$'' criterion.
\subsection{Constructive criteria in continuous time}
\paragraph{Brief introduction to IPS.}
An IPS is a continuous--time Markov process $\{\sigma_t\}_{t \geq 0}$
on $\Omega$. It is
characterized by a collection of translation invariant, local, bounded
and nonnegative functions
\begin{equation}
\{c_x(\sigma)\}_{x \in L}
\end{equation}
$c_x(\sigma)$ has to be interpreted as the flip rate of the spin at site $x$
if the IPS is in state $\sigma$:
\begin{equation}
{\rm Prob}[\sigma_t(x) \neq \sigma_0(x)|\sigma_0 = \sigma] = t
c_x(\sigma) + o(t)
\end{equation}
The range $r$ of the IPS is the side length of a minimal hypercube
\begin{equation}
C_{z,r} = \{y \in \mbox{\boldmath $Z^d$}|z_i \leq
y_i \leq z_i + r, i \in \{1,\dots,d\}\}
\label{hypercube}
\end{equation}
in which spin flips do not alter $c_0(\sigma)$.
The construction of the Markov semi--group $S(t)$ on $C(\Omega)$ (the
analogue of $P^N$) is accomplished via the generator $L$ of the
IPS. $L$ acts on local functions as
\begin{equation}
Lf(\sigma) = \sum_{x \in L} c_x(\sigma)[f(\sigma^x)-f(\sigma)]
\end{equation}
Details of this construction can be found in \cite{L}.
Ergodicity is defined analogously as for PCA in (\ref{def ergodicity}).
\paragraph{The $M<\epsilon$ criterion.}
We define
\begin{eqnarray}
M &=& \sum_{x \neq 0} \sup_{\sigma \in \Omega}
|c_0(\sigma^x)-c_0(\sigma)|\\
\epsilon &=& \inf_{\sigma \in \Omega} |c_0(\sigma^x)+c_0(\sigma)| \\
B &=& \sup_{\sigma \in \Omega} c_0(\sigma)
\label{Meps}
\end{eqnarray}
$M$ measures how strongly the flip rates depend on the configuration,
$\epsilon$ represents the part of the behavior of a single spin that
does not depend on the configuration at all and $B$ is just a time
scale factor. It is well--known that $M<\epsilon$ implies ergodicity
\cite{L}. Later we will give a short proof of this criterion.
\paragraph{}
Just like we did in section \ref{cc for PCA} we introduce quantities expressing
the propagation of disagreements under the evolution of the basic coupling of
the IPS.
Define for continuous time $t$,
\begin{equation}
\gamma_t = \sum_{x \in L} \sup_{\sigma \in \Omega}
Q^t_0(\sigma,\sigma^x)
\end{equation}
where
\begin{equation}
Q^t_0(\sigma,\sigma^x) = {\rm Prob}[\sigma_t(0) \neq
\bar{\sigma}_t(0)| (\sigma_0,\bar{\sigma}_0) = (\sigma,\sigma^x)]
\end{equation}
is calculated in the basic coupling $(\sigma_t,\bar{\sigma}_t)$
for IPS with the same flip rates but started from different initial
conditions (see \cite{L} and \cite{M}).
A complication is that the above quantity
$Q^t_0(\sigma,\sigma^x)$
cannot be calculated directly, because in any time interval of nonzero
length, any spin can flip unboundedly often.
However, since the probability that
a lot of spin flips occur in a bounded region in a short time is small,
it is possible to approximate IPS with processes that do not
allow too many spin flips within small time intervals. It turns out
that PCA are suitable approximations.
\paragraph{Approximating IPS by PCA.}
Choose $\delta>0$ small. Given an IPS with rates $c_x(\sigma)$, we define
its $\delta$--approximating PCA ($\delta$--PCA) by taking transition
probabilities
\begin{equation}
p^{(\delta)}_x(+|\sigma) =
\left\{
\begin{array}{rl}
\frac{1}{2} (1-e^{-2\delta c_x(\sigma)})&{\rm if} \ \sigma(x)=-,\\
1-\frac{1}{2} (1-e^{-2\delta c_x(\sigma)})&{\rm if} \ \sigma(x)=+
\label{def delta-PCA}
\end{array}
\right.
\end{equation}
So, to first order in $\delta$, $p^{(\delta)}_x(+|\sigma)$ goes as
\begin{equation}
\left\{
\begin{array}{rl}
\delta c_x(\sigma) &{\rm if} \ \sigma_x=-\\
1-\delta c_x(\sigma) &{\rm if} \ \sigma_x=+
\end{array}
\right.
\label{first order of delta-PCA}
\end{equation}
The reason for not taking (\ref{first order of delta-PCA}) as
definition of the $\delta$-PCA is that (\ref{def delta-PCA})
approximates the IPS slightly better (see \cite{MS2}).
Intuitively, it is clear that the $\delta$--PCA approximates the
IPS. Technical details can be found in \cite{M}, \cite{MS2} and
\cite{S}.
\paragraph{}
Define $\gamma^{(\delta)}_N$ as in (\ref{gamma_N}) but corresponding to
the $\delta$--PCA as in (\ref{def delta-PCA}). Moreover, put
\begin{eqnarray}
E(N,\delta) &=& \min_{n \in \{1,2,\dots\}} E_n(N,\delta) \\
E_n(N,\delta) &=& 2(2nr+1)^d z(N,\delta) + e^{-\epsilon N\delta} \sum_{k
\geq n} \frac{(MN\delta)^k}{k!} \\
z(N,\delta) &=& (e^{MN\delta}-1) \left(\frac{B}{M} -
\frac{1-e^{-2B\delta}}{2(e^{M\delta}-1)} \right)
\end{eqnarray}
\begin{Theorem}
If we can find $(N,\delta)$ such that
\begin{equation}
\gamma^{(\delta)}_N \leq 1 - E(N,\delta)
\end{equation}
then the IPS is uniformly exponentially ergodic, that is,
there are constants $c>0, \lambda\leq \infty $, so that for all $f\in
D(\Omega)$,
\begin{equation}
\left\| S(t) - \int \nu(d\sigma)f(\sigma) \right\|
\leq c e^{-\lambda t} |||f|||.
\end{equation}
where $\nu$ is the unique invariant measure ($\nu L = 0$).
\end{Theorem}
\paragraph{Remark 1.}
Actually, from the original arguments in [MS2], it is clear that
we
can slightly improve the Theorem by replacing $\gamma^{(\delta)}_N$ in
(\ref{gamma_N}) by
\begin{equation}
\gamma^{(\delta)}_{N,n} =
\sum_{x \in C_{nz,nr}} \kappa^{(\delta )\ N}_{0x}
\end{equation}
\paragraph{Remark 2.}
Using the definition of the $\delta$--PCA (\ref{def delta-PCA}) and
$\gamma^{(\delta)}_1$ (\ref{gamma_N}) we easily find
\begin{equation}
\gamma^{(\delta)}_1 = 1 + \delta(M-\epsilon)
\end{equation}
On the other hand $E_2(1,\delta)$ is of order $2$ in $\delta$, so if
$M<\epsilon$, the MSCC for IPS will be fullfilled for $N=1$ and
$\delta$ small enough.
\paragraph{}
For better criteria we have to use higher order MSCC. In order to let
these be effective, we may not take $\delta$ too small because the
terms in $\gamma^{(\delta)}_N$ responsible for making the
$\gamma^{(\delta)}_N$--criterion better than the
$\gamma^{(\delta)}_1$--criterion would vanish then.
\subsection{The continuous--time asymmetric contact process}
\paragraph{Definition.}
The flip rates of the continuous--time asymmetric contact process are
\begin{equation}
c_x(\sigma) = \left\{
\begin{array}{rcl}
0 &{\rm if}& \sigma(x-1)=\sigma(x)=+\\
M &{\rm if}& \sigma(x-1)=-,\sigma(x)=+\\
\epsilon&{\rm if}&\sigma(x)=-
\end{array}
\right.
\end{equation}
It is easy to see that $M$ and $\epsilon$ have the same meaning as in
the $M<\epsilon$ criterion, see (\ref{Meps}).
\paragraph{Approximation by the discrete--time asymmetric contact process.}
The $\delta$--PCA has transition probabilities
\begin{equation}
p^{(\delta )}_x(\sigma) =
\left\{
\begin{array}{rcl}
0 &{\rm if}& \sigma(x-1)=\sigma(x)=+\\
1-\alpha &{\rm if}& \sigma(x-1)=-,\sigma(x)=+\\
\beta&{\rm if}&\sigma(x)=-
\end{array}
\right.
\end{equation}
with
\begin{equation}
\alpha = \frac{1}{2}(1-e^{-2\delta M}),\ \beta =
\frac{1}{2}(1-e^{-2\delta \epsilon})
\end{equation}
We have studied the above PCA, the discrete--time asymmetric contact
process, in subsections \ref{Simplifications} and \ref{Results}.
\paragraph{Calculating $\gamma^{(\delta)}_N$.}
With the help of these subsections
we calculate $\gamma^{(\delta)}_N$ to
second order in $\delta$:
\begin{equation}
1 + N(M-\epsilon)\delta + N(\epsilon^2 - M^2)\delta^2 +
\frac{1}{2}N(N-1)
(\epsilon^2-2\epsilon M)\delta^2 + o(\delta^2)
\end{equation}
$E_3(N,\delta)$ is to second order in $\delta$ equal to
$ 12 N M^2 \delta^2$.
It is discouraging to see that the smallest value of $N$ for which the
coefficient of the second order in $\delta$ of $\gamma^{(\delta)}_N +
E_3(N,\delta)$ becomes negative,
is $26$; we will have to know $ \gamma^{(\delta)}_N$ for
$N$ larger than we have computed it before.
\paragraph{}
We are now facing a similar task as in subsections \ref{Simplifications}
and \ref{Results} of finding a $\delta^*$ such that $M$ can be as large as
possible under the conditions $\epsilon =1$ and $\gamma^{(\delta )}_N
+E(N,\delta ) <1$. The
extra term $E(N,\delta )$ decreases this $\delta ^*$. It turns out that
the hypercube $\{-n,\dots,0\}$ (see (\ref{hypercube})) that roughly contains
the infection will grow so slowly that it becomes feasible to calculate
with a computer all
$\kappa^{(\delta )\ N}_{y0}$ with $y$ in this hypercube for $N$ as
large as $10,000$.
\paragraph{About the calculations.}
For the asymmetric contact process the expression for
$\gamma^{(\delta )}_{N,n}$ simplifies to
\begin{equation}
\gamma^{(\delta )}_{N,n} = \sum_{y=0}^{-n} {\rm
Prob}[\sigma_N(y)=-|\sigma_0=+^0]
\end{equation}
The probability distribution over the configurations on $\{-n,\dots,0\}$
at $t=N$ can be expressed in the distributions at $t=N-1$:
$$ P^{(\delta )\ N}(\sigma_N(-n),\dots,\sigma_N(0)|\sigma_0 = +^0) =$$
$$\sum_{\sigma_{N-1}(-n)=-}^+ \dots \sum_{\sigma_{N-1}(0)=-}^+ \
\prod_{x=-n}^0
p^{(\delta )}_x(\sigma_N(x)|\sigma_{N-1}(x),\sigma_{N-1}(x+1))$$
\begin{equation}
\ P^{(\delta )\ N-1}(\sigma_{N-1}(-n+1),\dots,\sigma_{N-1}(0)|
\sigma_0 = +^0)
\end{equation}
\paragraph{Results.}
We have programmed the above recursion relation on a computer.
Some relevant results are
\begin{equation}
\begin{array}{ccccc|c}
\epsilon& \delta& M& N& n & 1 - \gamma^{(\delta)}_{N,n} - E_n(N,\delta)\\
\hline
1& 3.5\times10^{-3}& 1.066& 10^2& 3 & 4.6\times10^{-4}\\
1& 1.1\times10^{-3}& 1.28 &10^3& 5 & 4.8\times10^{-3}\\
1& 1.65\times10^{-4}& 1.5&10^4& 8& 3.8\times10^{-3}
\end{array}
\end{equation}
(The computation for $N = 10^4$ took a few hours on a
{\sl Sun SPARC station 1+}.)
We conclude that the continuous--time asymmetric contact process
is ergodic for $M<1.5 \epsilon$.
\section*{Acknowledgements}
We like to thank J. van den Berg, A.C.D. van Enter, N.W. Schellingerhout and
M. Winnink for useful discussions. HdJ is grateful to the Institute
for Theoretical Physics in Leuven for warm hospitality and to the ERASMUS
fund for financial support of this visit.
\begin{thebibliography}{MS2}
\bibitem[B]{B}
J. van den Berg,
{\em A Uniqueness Condition for Gibbs Measures, with Application to the
2-Dimensional Ising Antiferromagnet},
Commun. Math. Phys. {\bf 152}, 161--166 (1993).
\bibitem[BD]{BD}
L.A. Bassalygo and R.L. Dobrushin,
Theor. Prob. and Appl. {\bf 31} No. 4, 651 (1986).
\bibitem[BM]{BM}
J. van den Berg and C. Maes,
{\em Disagreement percolation in the study of Markov fields},
To appear in The Annals of Probability.
\bibitem[BS]{BS}
J. van den Berg and J.E. Steif,\
{\em On the hard--core lattice gas model, percolation, and certain loss
networks},
Preprint.
\bibitem[DKS]{DKS}
R.L. Dobrushin, J. Kolafa and S.B. Shlosman,
{\em Phase Diagram of the Two--Dimensional Ising Antiferromagnet
(Computer--Assisted Proof)},
Commun. Math. Phys. {\bf 102}, 89-103 (1985).
\bibitem[DKT]{DKT}
R.L. Dobrushin, V.I. Kryukov and A.L. Toom eds.,
{\em Stochastic cellular systems: ergodicity, memory, morphogenesis},
(Manchester University Press 1990).
\bibitem[F1]{F1}
P.A. Ferrari,
{\em Ergodicity for spin systems with stirrings},
The Annals of Probability Vol. {\bf 18}, No. 4, 1523--1538 (1990).
\bibitem[F2]{F2}
P.A. Ferrari,
{\em Ergodicity for a class of probabilistic cellular automata},
Revista de Matem\'{a}ticas Aplicadas {\bf 12}, 93-102 (1991).
\bibitem[L]{L}
T.M. Liggett,
{\em Interacting Particle Systems},
(Springer-Verlag, New--York, 1985).
\bibitem[M]{M}
C. Maes,
{\em A note on using the basic coupling in interacting particle systems},
Preprint KUL-TF-92/9.
\bibitem[MS1]{MS1}
C. Maes and S.B. Shlosman,
{\em Ergodicity of Probabilistic Cellular Automata: A Constructive
Criterion},
Commun. Math. Phys. {\bf 135}, 233-251 (1991).
\bibitem[MS2]{MS2}
C. Maes and S.B. Shlosman,
{\em When is an Interacting Particle System Ergodic?}
Commun. Math. Phys. {\bf 151}, 447-466 (1993).
\bibitem[MS3]{MS3}
C. Maes and S.B. Shlosman,
{\em Constructive criteria for the Ergodicity of Interacting Particle Systems},
451--461 in
{\em Cellular Automata and Cooperative Systems},
eds. N. Boccara et al,
(Kluwer Academic Publishers 1993).
\bibitem[MP]{MP}
M.V. Menshikov and K.D. Pelikh, Mathematicheskie Zametki {\bf 46} (1989).
\bibitem[S]{S}
J.E. Steif,
{\em The Ergodic Structure of Interacting Particle Systems},
Stanford Mathematics Department Ph.D. Thesis (1988).
\bibitem[T1]{T1}
A.L. Toom,
{\em A family of uniform nets of formal neurons},
Soviet Math. Dokl. Vol. {\bf 9}, No. 6, 1338--1341 (1968).
\bibitem[T1]{T2}
A.L. Toom,
{\em Stable and attractive trajectories in multicomponent systems},
in {\em Multicomponent Random Systems},
eds R.L. Dobrushin and Ya.G. Sinai,
(Dekker, New York, 1980).
\end{thebibliography}
\end{document}