\input amstex
\documentstyle{amsppt}
\TagsOnRight
\parskip 3mm
\pagewidth{36pc}
\pageheight{50pc}
\vcorrection{2cm}
\hcorrection{.5cm}
\define\ep{\epsilon}
\define\p{\phi}
\define\e{\eta}
\define\s{\sigma}
\define\a{\alpha}
\define\r{\rho}
\define\[{\bigl[}
\define\]{\bigr]}
\define\Om{\Omega}
\define\z{\Bbb Z^d}
\define\Z{\Bbb Z^{d+1}}
\define\ci{c(i,\eta)}
\define\de{\delta}
\define\la{\lambda}
\define\De{\Delta}
\topmatter
\title Disagreement percolation in the study of Markov fields
\endtitle
\rightheadtext{Disagreement percolation for Markov fields}
\author J. van den Berg and Chr. Maes
\endauthor
\affil CWI, Amsterdam and Instituut voor Theoretische Fysica, K.U.
Leuven \endaffil
%\address
%J. vdB., CWI, Kruislaan 413, 1098 SJ Amsterdam, the Netherlands\endaddress
%\email jvdberg\@ cwi.nl \endemail
%\address
%C.M., Instituut voor Theoretische Fysica, K.U.Leuven, Celestijnenlaan 200
%D, 3001 Leuven, Belgium\endaddress
%\email FGBDA35\@ BLEKUL11.bitnet \endemail
\thanks C.M. is Aangesteld
Navorser N.F.W.O., Belgium\endthanks
\subjclass
Primary 60K35, 82B43, 82B05 ; secondary 82B26\endsubjclass
\keywords Percolation. (Optimal)
coupling. Markov fields. Uniqueness condition for Gibbs states
\endkeywords
\abstract{ Recently, one of the authors (vdB) has obtained a uniqueness
condition for
Gibbs measures, in terms of disagreement percolation involving two
independent realizations. In the present paper we study the
dependence of Markov fields on boundary conditions by taking a more
suitable coupling. This coupling leads to a new uniqueness condition,
which improves the one mentioned above. We also compare it with the
Dobrushin uniqueness condition.
In the case of the Ising model, our
coupling shares certain properties with the FortuinKasteleyn
representation :
it gives an explicit expression of the boundary effect on a certain vertex
in terms of percolationlike probabilities.}
\endabstract
\endtopmatter
\document
\head 1. Introduction
\endhead
\baselineskip=25pt
In this paper we study the influence of a boundary condition (which we
abbreviate as b.c.) on the
state of a Markov field in terms of disagreement percolation. This
is done by constructing a coupling between two realizations of the
Markov field under different b.c.'s. The effect of the b.c. is then
estimated in terms of percolationlike probabilities. \par
Our main result (Theorems 1 and 2) is a
precise formulation of various properties of this coupling. It allows
us to derive
upper bounds for the boundary effects (Corollary 1) and a new uniqueness
condition for Gibbs measures (Corollary 2). This is presented in Section 2.
Depending on the nature of the interaction, this condition
is sometimes better or worse than other existing criteria for uniqueness.
Section 3 is devoted to applications, examples and comparisons.
Proofs are collected in Section 4.
We start however by reminding the reader of some keyconcepts that
will play a crucial role in our constructions.
\subhead a) Graphs \endsubhead
Take a graph $G$ which is finite, or countably infinite and locally
finite (the last means that every vertex has finitely many edges).
Examples include the triangular lattice, the $d$dimensional hypercubic
lattice (which, with some abuse of notation, we denote by $\z$), and many
others.
The vertex set of
$G$ is denoted by $V$. Vertices are denoted by
$i,j,v,w,\dots$ etc., possibly with a subscript. We use the notation $v \sim
w$ to indicate that two vertices $v$ and $w$ are {\it adjacent}, or {\it
neighbors}, which means that there is an edge
between them. The neighborhood $N_i$ of a vertex $i$ is the set of all
$j \sim i$. For $B \subset V, B$ denotes its cardinality ($B$ is {\it
finite} if $B<\infty$), and the {\it boundary} $\partial B$ of $B$ is the
set of all vertices which are not in $B$ but adjacent to some vertex in $B$.
By a {\it path} we mean a (finite or infinite) sequence of distinct vertices
$v_1, v_2, \dots$ in which the consecutive vertices are adjacent.
For $W\subset V$ not containing vertex $v$, a
{\it path} from $v$ to $W$ is a finite
path whose first vertex is $v$ and whose last vertex is in
$\partial W$.
(Note that, in
contrast to part of the literature, we do not require that the last vertex of
the path itself belongs to $W$).
\subhead b) Percolation \endsubhead
Suppose now that to each vertex a value $0$ or
$1$ is assigned, according to some probability measure $\mu$ on the
product space $\{0,1\}^V$. A vertex with
value $1$ is called {\it open} (depending on the context, people sometimes
call it {\it occupied}, or {\it accessible} 
in this paper, it will represent some sort of
disagreement). Percolation theory deals with the study
of certain {\it open paths}, i.e. paths on
which all the vertices take the value $1$. We say that there is
percolation for $\mu$ if it assigns positive probability to the
event that there exists an infinite open path.
The simplest and most
studied example is where $\mu$ is a Bernoulli measure with density
$p$. In that case, each vertex, independent of all the other
vertices, is open with probability $p$ and
closed ($=0$) with probability $1p$. This measure will be denoted in
this paper by $P_p$.
The {\it critical probability} is then defined by
$$p_c=\inf\{p\in [0,1] :
P_p[\text{there exists an infinite open path}]> 0\}\tag1.1$$
as the {\it treshold} for percolation. Since $p_c$ depends on $G$, we
sometimes write $p_c(G)$. The availability of lower bounds for $p_c$ are
important in this paper. It is known (Hammersley (1957)) that always
%
$$
p_c \geq \frac{1}{\sup_i N_i  1}.\tag1.2$$
%
In many cases strict inequality holds, e.g., for $d > 1$,
%
$$
p_c(\Bbb Z^d) > \frac{1}{2d  1}.\tag1.3$$
%
Asymptotically, the r.h.s. of (1.3) gives the correct
behavior in the sense that
%
$$
2d\, p_c(\Bbb Z^d) \rightarrow 1, \text{ as } d \rightarrow \infty,
\tag1.4$$
%
(see Kesten (1990) for this and more detailed asymptotic results).
However, in low dimensions larger than 1, $p_c$ is considerably bigger
than the
r.h.s. of (1.3), and this will appear to be important in this paper.
For instance, according to an early result
in percolation theory (Harris (1960) combined with Hammersley
(1961)),
%
$$p_c(\Bbb Z^2) \geq \frac{1}{2}\tag1.5$$
%
Strict inequality was proved by Higuchi (1982), i.e.
$p_c(\Bbb Z^2) > 1/2$.
%
This, in turn, was further improved by the lower bound 0.503.. of
T\'oth (1985).
More recently Menshikov and Pelikh (1989) have obtained a computerassisted
proof of the lower bound 0.54.. . Nonrigorous methods suggest that
$p_c \approx 0.593$ for this lattice.
In the above percolation models, the randomness involves the vertices, and
therefore we speak of {\it site percolation}. If, instead, the randomness
involves the edges, we speak of {\it bond percolation}. For further
study, see Kesten (1982) and Grimmett (1989).
\subhead c) Markov fields and Gibbs measures\endsubhead
Let $S$ be a finite set and define $\Omega = S^V$.
Elements of $\Om$ are called {\it configurations}
and will usually be denoted by $\s=(\s(i), i\in V)$ if it
concerns the random field, and by $\e, \e', \dots$ if we consider a
fixed configuration.
We will also use this notation for elements of $S^B$, with $B$ a subset of $V$.
(It will always be clear from the context which set $B$ is meant).
If $A \subset B \subset V$, $\e, \e' \in S^B$, and $\e(i) = \e'(i) $ for all
$i$ in $A$,
we write ``$\e \equiv \e'$ on $A$''.
We consider certain probability measures on $\Om$ (or, more precisely,
on the sigma field generated by the collection of sets
$\{\s \in \Om : \s(i) = s\}, i \in V, s \in S$.
A measure $\nu$ is called a {\it Markov field} if, for each finite
$A \subset V$, and each $\e \in S^A$,
%
$$
\nu[\s\equiv \e \text{ on }A\,\, \s(i), i \in A^c] =
\nu[\s\equiv \e \text{ on }A\,\, \s(i), i \in \partial A],\,
\nu\text{a.s.}\tag1.6$$
%
In many applications the conditional probabilities in the r.h.s of (1.6)
are known and the problem is to `determine' the probability measures $\nu$
which satisfy (1.6). This approach leads to the introduction of a socalled
{\it specification} $(Y_A(\cdot,\e), A \subset V, \e \in S^{\partial
A})$, which is a collection of probability
measures, indexed by the finite sets $A \subset V$ and the possible
configurations $\e$ on $\partial A$. These probability measures are
interpreted as conditional distributions of the configurations on the
finite sets, given the configuration on their boundary. (Of course this
collection of probability measures must satisfy certain
consistency conditions :
see e.g. Georgii (1988) for details).
Denote by $S_\nu^{\partial A}$ the set of all $\e' \in S^{\partial A}$
for which $\nu [\s \equiv \e' \text{ on }\partial A ] > 0$.
Formally, the problem then is to `determine' the Markov fields $\nu$ which
satisfy, for all finite $A \subset V$, all $\e \in S^A$ and all
$\e' \in S_{\nu}^{\partial A}$,
%
$$
\nu[\s\equiv \e \text{ on }A\,\, \s \equiv \e' \text{ on } \partial
A] = Y_A(\e,\e'). \tag1.7 $$
%
These Markov fields are called the {\it Gibbs measures} of the
specification $Y$.
In case $G$ is infinite, a specification may have more than one Gibbs measure,
in which case we say that there is a {\it phase transition}.
(Dobrushin (1968a) is one of the earliest papers where such a phase
transition is rigorously established).
An important problem is to formulate useful conditions under which this does
not occur. In this paper we focus on this problem.
{\bf Remark}. There is a 11 relation between the above mentioned
specifications and socalled nearestneighbor potentials. In fact, in many
applications (especially in the context of statistical physics) one starts
with a given potential function, which, via its {\it Hamiltonian} gives
rise to a specification and its Gibbs measures. The reverse is also true :
for each Markov field a suitable potential function exists (see e.g.
Grimmett (1973)).
However, this relation is not essential for our main results (Section
2) and therefore we will not treat it here in more detail. For the
discussion in Section 3 some familiarity with certain special models,
like
the Ising model, is desirable. For further study and background we refer
the reader to the earlier mentioned
book by Georgii (1988) or (as a gentle introduction) Kindermann and Snell
(1980).
\subhead d) Coupling, variational distance, stochastic domination
\endsubhead
We summarize here some of the tools we need. They
can be found in or reconstructed
from the standard references on coupling, such as
Lindvall (1992).
Let $L$ be a finite set and
let $X_1$ and $X_2$ be two $L$valued random variables
with
distribution $\rho_1$ and $\rho_2$ respectively. The {\it variational
distance} of $X_1$ and $X_2$ (or, equivalently, of $\rho_1$ and
$\rho_2$) is defined by
$$
d(\rho_1,\rho_2)=\frac1{2}\sum_{a\in L}\rho_1(a)\rho_2(a)\tag1.8$$
%
An equivalent definition is
$$
d(\rho_1,\rho_2)= \max_{E \subset L} \rho_1(E)  \rho_2(E).\tag1.9$$
%
If $(\tilde X_1,\tilde X_2)$ is an $L\times L$valued random variable
such that $\tilde X_1$ equals $X_1$ in distribution and $\tilde X_2$ equals
$X_2$ in distribution, then we
call it a {\it coupling} of $X_1$ and $X_2$ (or, with some abuse of
terminology, of $\rho_1$ and
$\rho_2$). It is well known (and easily seen) that
the probability that
$\tilde X_1 \neq \tilde X_2$ is always at least $d(\rho_1,\rho_2)$.
It is also wellknown that there exists an {\it optimal coupling}, for which
equality holds, i.e., if we denote the distribution for such a coupling by
$\tilde \Cal P$, then
$$
\tilde \Cal P[\tilde X_1\neq\tilde X_2] = d(\rho_1,\rho_2).\tag1.10$$
%
Another result we will
use is the following : if the probability distribution $\rho_1$ is a mixture
(or, convex
combination) of $\rho_1'$ and $\rho_1''$, and $\rho_2$ is a mixture of
$\rho_2'$ and $\rho_2''$, say $\rho_1 = \alpha_1 \rho_1' + (1  \alpha_1)
\rho_1''$
and $\rho_2 = \alpha_2 \rho_2' + (1  \alpha_2) \rho_2''$, then
$$
\aligned
d(\rho_1,\rho_2) & \leq
\alpha_1 \alpha_2 d(\rho_1',\rho_2') +
\alpha_1 (1  \alpha_2) d(\rho_1',\rho_2'') \\ & +
(1  \alpha_1) \alpha_2 d(\rho_1'',\rho_2') + (1  \alpha_1) (1  \alpha_2)
d(\rho_1'',\rho_2'') \\
& \leq \max\{d(\rho_1',\rho_2'),
d(\rho_1',\rho_2''),
d(\rho_1'',\rho_2'), d(\rho_1'',\rho_2'')\}.\endaligned \tag1.11$$
%
(The first inequality follows from the definitions and properties
mentioned above, by taking as coupling of $\rho_1$ and
$\rho_2$ the appropriate mixture of optimal couplings between $\rho_1'$ and
$\rho_2'$, between $\rho_1'$ and $\rho_2''$, etc.; the second inequality is
trivial)
A similar result holds for mixtures of more than two distributions.
Now suppose that $L$ is equipped with a total order $\prec$.
This induces, for $n = 1,2, \dots$,
a {\it partial order} (also denoted by $\prec$) on $L^n$:
if $s=(s_1, \dots ,s_n)$ and $s'=(s'_1, \dots ,s'_n)$ then $s \prec s'$
means that $s_i \prec s'_i$ for all $i = 1, \dots, n$.
A realvalued function $f$ on $L^n$ is called {\it increasing} if $x
\prec y$
implies $f(x) \leq f(y)$. If $X$ and $Y$ are $L^n$valued random variables
we say that $X$ is {\it stochastically dominated} by $Y$ if, for each increasing
$f$, $\Bbb E[f(X)] \leq \Bbb E[f(Y)]$. (We also say that then the
distribution of $X$ is dominated by that of $Y$).
A classical result, which goes back to Strassen (1965), says that this
holds
if and only if there exists a coupling of $X$ and $Y$ which is optimal in
the sense defined above (i.e. (1.10) holds) and, moreover, has the property
that
$$
\tilde \Cal P[\tilde X \prec \tilde Y] = 1. \tag1.12 $$
%
The ifpart of this result is obvious, and the `onlyif' part will
only be used in this paper for the case that $n = 1$ (in which
case the proof is easy).
If $L \subset \Bbb Z$ then, unless explicitly stated otherwise, the order
on $L$ will always be the `ordinary' total order inherited from $\Bbb Z$.
If the singlevertex state space of a Markov field $\nu$ is
ordered,
then $\nu$ is called {\it monotone} if, for all finite $A \subset V$ and
all $\e_1 \prec \e_2 \in S_\nu^{\partial A}$, the probability distribution
$\nu[\s \equiv \cdot \text{ on } A \,\, \s \equiv \e_1 \text{ on }
\partial A]$ is dominated by
$\nu[\s \equiv \cdot \text{ on } A \,\, \s \equiv \e_2 \text{ on }
\partial A]$.
\head 2. Main results \endhead
As in the introduction, let $G$ be a finite or countably infinite, locally
finite graph and $S$ a finite set. Let $\nu$ be a Markov field on
$\Om \equiv S^V$.
Define, for each finite $A\subset V$ and each
b.c. $\e \in S_\nu^{\partial A}$ the following
conditional Markov field on $S^A$ :
%
$$
Q_A(\cdot,\e)= \nu[\s\equiv \cdot \text{ on } A\,\,\s\equiv\e\text{
on } \partial A].\tag2.1$$
%
(If $A$ consists of one element $i$ we will write $Q_i$ instead of
$Q_{\{i\}})$.
Now define the parameters
%
$$
q_i=\max_{\e,\e'\in S_\nu^{N_i}}
d(Q_i(\cdot,\e),Q_i(\cdot,\e'))\tag2.2$$
%
which will play a major role in what follows.
For two configurations $\e_1, \e_2 \in S^A$,
a {\it path
of disagreement} is a path of which all vertices $i$ are in $A$ and satisfy
$\e_1(i) \neq \e_2(i)$.
\proclaim{ Theorem 1}
For each finite $A \subset V$ and each pair
$\e_1, \e_2 \in S_{\nu}^{\partial A}$,
there exists a coupling $((\s_1(i),\s_2(i)),
\, i \in A)$ (whose distribution we denote by $\Cal P$) of
$Q_A(\cdot,\e_1)$ and $Q_A(\cdot,\e_2)$ such
that
\noindent
i) The random field $(I(\s_1(i) \neq \s_2(i), i \in A)$
is stochastically dominated by a family $(X_i, i\in A)$ of
independent Bernoulli trials with density $q_i$, where the $q_i$'s are as
defined in (2.2). Here $I(\cdot)$ denotes the indicator function.
\noindent
ii) For each $i\in A$,
$\s_1(i) \neq \s_2(i)$ if and only if there is path of disagreement from $i$
to $\partial A$ ($\Cal P$a.s.).
\endproclaim
We get {\bf extra} properties for this coupling when applied to
monotone Markov fields. This is contained in
\proclaim{Theorem 2}
If $S$ is ordered and $\nu$ is monotone, then, if $\e_1 \prec \e_2$,
the coupling $\Cal P$ of Theorem 1 can be taken in such a way that,
besides (i) and (ii), the following hold:
\noindent
iii) For each $i \in A$, $\s_1(i) \prec \s_2(i)$ ($\Cal P$a.s.).
\noindent
iv) For each $i \in A$,
$$ \aligned
d(Q_A(\s(i)=\cdot,\e_1),Q_A(\s(i)=\cdot,\eta_2)) & \leq \Cal P[\text{
there is a path of disagreement from } i
\text{ to } \partial A)\\
& \leq (S  1) \,d(Q_A(\s(i)=\cdot,\e_1),Q_A(\s(i)=\cdot,\eta_2))
\endaligned\tag2.3$$
%
In
particular, if $S = 2$, we have equality in (2.3).
\endproclaim
Suppose now that $\Lambda\subset A$ is some
set of vertices in $A$ and let $E$ be an event
involving only the vertices in $\Lambda$ (i.e., measurable with respect to
the sigma algebra generated by the $(\s(i), i\in\Lambda)$).\par
Using the same notation as before, we now estimate the difference
in the probabilities of the event $E$ for the two conditional distributions in
Theorem 1.
\proclaim{ Corollary 1}
$$
Q_A(E,\e_1)  Q_A(E,\e_2)\leq
P_{\{q_i\}}[\text{there is an open
path from some vertex in $\Lambda$ to } \partial A]\tag2.4$$
%
where $P_{\{q_i\}}$ is the product measure under
which each vertex is open with probability $q_i$ and is closed with
probability $1q_i$.
\endproclaim
Finally, we turn the situation around. Instead of starting from a
Markov field $\nu$ as we did above, we pick up the discussion that
followed after Eqn. (1.6) and want to say something about the
solutions to (1.7) for prescribed right hand side.
So let Y be a specification as in Section 1, and define, analogously,
to (2.2),
%
$$
p_i =\max_{\e,\e'\in S^{N_i}}
d(Y_i(\cdot,\e),Y_i(\cdot,\e'))\tag2.5$$
%
Our result on uniqueness of Gibbs measures is then
\newpage
\proclaim{ Corollary 2}
If
$$P_{\{p_i\}}[\text{there is an infinite open
path}]=0,\tag2.6$$
%
then the specification $Y$ has at most one Gibbs measure. In
particular (see (1.1)), this holds if
$$\sup_i p_i < p_c. \tag2.7$$
\endproclaim
\head 3. Discussion \endhead
1. Our results were motivated by a uniqueness condition of
van den Berg (1991),
who gave a successful application to certain models (see
Example b) below).
The uniqueness condition given by
Corollary 1 of van den Berg has much in common with our Corollary 2,
with $p_i's$
which are defined by taking the same maximum as in (2.5), but with
the {\it product coupling} (while (2.5) takes an {\it optimal} coupling).
More precisely, the uniqueness condition of van den Berg is the
following :
%
$$\sup_i \max_{\e \neq \e'} \sum_{a\neq
b}Y_i(a,\e)\,Y_i(b,\e') < p_c.\tag3.1$$
%
(In fact, the condition in van den Berg (1991) does not have the
restriction $\e \neq \e'$
in its maximum, but it was pointed out in van den Berg and Steif (1992) that,
for adding this restriction, the proof needs only a minor
adaptation).
In view of the remarks following (1.9), the l.h.s. of (3.1) is larger
than or equal to $p_i$ and hence
our current condition is clearly an improvement of the former. A
shortcoming of the former condition was the existence of natural examples
where $Y_i(.,\e)$ does not depend on $\e$ (so that uniqueness is trivial),
but for which the condition failed. It is clear that the present condition
is satisfied in such examples (since then $p_i = 0$).
It is also useful to
compare our criterion with the more standard Dobrushin (1968b)
singlesite uniqueness condition, which, in our notation, takes the form
$$
\sup_i\sum_j\max_{\eta\equiv\eta'\text{off }j}
d(Y_i(\cdot,\e),Y_i(\cdot,\e'))<1\tag3.2$$
%
(See Georgii (1988) for references
and details).
Here the constraint ``$\eta\equiv\eta'\text{ off }j$'' means that we
consider configurations
$\e,\e'$ which differ only at the vertex $j$.
It may happen that for
every $j\in N_i$ the maximum is actually the same as without this
constraint in which case (3.2) equals $ \sup_i N_i p_i$.
This scenario is likely to occur for systems with a hard core
exclusion
or for certain antiferromagnetic models, see the examples below.
For a regular lattice (and all $p_i$'s equal to a single value $p$),
say $G=\Bbb Z^d$, the Dobrushin condition would then be
$p<1/(2d)$ while our criterion would be $p0$, with the
constraint
that no two particles of opposite sign can be on adjacent vertices.
More precisely, the singlevertex specification is given by
%
$$\aligned
Y_i(s,\e) & = \frac{a}{Z} I(s \e(j) \neq 1 \text{ for all }j \sim
i)\text{ if } s=\pm1\\
& = 1/Z \text{ if } s=0,\endaligned
\tag3.3
$$
%
where $Z=Z(\e,a)$ is a normalizing constant and $I(\cdot)$ denotes the
indicator
function. Calculating (2.5) gives
$p_i=2a/(1+2a)$ if vertex $i$ has at
least two adjacent vertices, and $p_i=a/(1+a)$ if
$i$ has only one adjacent vertex. Thus, by Corollary 2, for $a <
p_c/(2(1p_c))$ there is a unique Gibbs measure for this
specification. It is not difficult to check that in
this model the condition (3.1) gives a result
which is strictly worse.
If $G$ is a graph in which each vertex has $z\geq 2$ neighbors, then
the Dobrushin single site condition (3.2) gives uniqueness for
$a < 1/(z1)$. For $G=\Bbb Z^2, z=4$, this is certainly
improved by our criterion because of (1.5). However, for the hypercubic
lattice in sufficiently large dimension, Dobrushin's condition is better
because of (1.4).
d) {\bf communication networks}.
Here the graph represents a network, at the nodes of which calls are
generated according to independent Poisson processes with rate $\lambda$.
The durations of the calls are independent, exponentially distributed
random variables with mean $T$. For the transmission of a call all
edges (links) of the corresponding node are needed. However, the number
of calls that can be handled simultaneously by a link is at most $n$,
where $n$ is a parameter of the model. A call generated at a node $i$ is
therefore ignored (lost) if, for some $j \sim i$, the sum of the
ongoing calls at $i$ and $j$ is $n$. For more information on such models,
see Kelly (1991), Louth (1990) and Kelbert and Suhov (1990).
The temporal evolution of the finite system is a continuoustime
Markov chain with state space $\{0,\dots,n\}^V$.
It is easy to check that its stationary distribution $\nu$ is given by
$$
\nu(\e) = \frac{1}{Z}\prod_{i \in V}\frac{a^{\e_i}}{(\e_i)!}
I(\e \text{ is feasible}),
\tag3.4$$
%
where $a = \lambda T$, {\it feasible} means that for all $i$ and all
$j \sim i$, $\e_i + \e_j \leq n$, and $Z$ is a normalizing constant.
It is also easy to see that this is the Gibbs measure for the following
specification $Y$ :
$$
\aligned
Y_i(s,\e) &=
\frac{a^s / s!}{\sum_{r=0}^{nm(\e)} a^r / r!}\phantom{[[[[[[[[[[[[}
\text{
if }s \leq nm(\e)\\ &= 0\phantom{ooooooooooooooooooooooo}\text{
otherwise. } \endaligned
\tag3.5$$
%
Here $m(\e) = \max_{j \sim i}\e(j)$.
Note that for $n = 1$ we have the hardcore lattice gas model mentioned
earlier.
Studying the infinite case ($V=\infty$) leads to the question whether the
above
specification has a unique Gibbs measure. Now note that the maximum in
the calculation of the $p_i$'s in (2.5) is obtained when $\e \equiv 0$ and
$\e'(j) = 0$ for all j except one, for which it equals $n$. Hence $\e$
and $\e'$ differ at only one vertex and thus, as explained before, here our
criterion performs better than the Dobrushin criterion.
More explicitly, on $\Bbb Z^d$ our condition (2.7) guarantees
uniqueness when
%
$$
\sum_{k=0}^n \frac{a^k}{k!} < \frac1{1  p_c}.\tag3.6$$
%
The Dobrushin criterion (3.2) for this case is the above inequality,
but with $p_c$ replaced by $1/(2 d)$, which is worse (by (1.3)).
As mentioned before, our bound can especially take
advantage in
$d=2$ of the available lower bounds (1.5) and thereafter for $p_c$.
The criterion (3.1) of van den Berg (1991) is,
for these models with $n > 1$, usually {\it strictly} worse than ours,
since the maximum in (3.1) is not, in general, achieved by the
same pair $\e,\e'$ as above.
2. The {\bf FortuinKasteleyn} (1972) representation
is one of the most appreciated methods connecting problems between
ferromagnetic Potts models and percolation models. To be specific,
we consider the nearestneighbor ferromagnetic Ising model (at
inverse temperature $\beta$) on a graph $G$.
It has $S=\{1,+1\}$ and single site specification
$Y_i(+1,\e)=\frac1{2}(1+\tanh[\beta\sum_{j\sim i}\e(j)])$, where we
sum over all neighbors $j$ of $i$.
On a
finite set $A\subset V$, we take
`plus'  b.c. : put $\e(j)=+1, \forall j\in \partial A$.
Denote by $<\s(v)>_A^+$ the expectation of the spin at a vertex
$v \in A$
for this Ising model in volume $A$. The FKrepresentation involves a
(dependent) bond percolation model on $A \cup \partial A$ for which,
$$
<\s(v)>_A^+=\text{Prob}[\text{there is an open path from } v \text{
to } \partial A]\tag3.7$$
%
Now in our notation, the l.h.s of (3.7) equals
$$
\nu[\s(v) = + \,\, \s \equiv + \text{ on } \partial A] 
\nu[\s(v) =  \,\, \s \equiv + \text{ on } \partial A],$$
which, by the symmetry between + and $$, equals
$$
\nu[\s(v) = + \,\, \s \equiv + \text{ on } \partial A] 
\nu[\s(v) = + \,\, \s \equiv  \text{ on } \partial A].$$
%
Since $S$ has only two values, this last expression is exactly the
variational
distance of $\nu[\s(v) = \cdot \,\, \s \equiv + \text { on } \partial A]$
and
$\nu[\s(v) = \cdot \,\, \s \equiv  \text { on } \partial A]$. Further,
this
is a monotone Markov field, so we may apply part iv) of Theorem 2, which
yields $$
<\s(v)>_A^+=\Cal P[\text{there is a path of disagreement from } v \text{
to } \partial A]\tag3.8$$
%
In other words, we get an expression which is similar in spirit to
(3.7). However, our expression involves site (instead of bond)
percolation,
and we do not know how to make a precise connection with the
FKrepresentation.
3. The {\bf DobrushinShlosman (1985)} constructive uniqueness
criterion
is of the form : ``if the specification is such that a condition $C_V$
holds for some finite volume $V$, then there is a unique Gibbs measure".
It is believed that, for a large class of models, by checking sufficiently
large boxes, uniqueness can be proved in this way whenever it holds (except
in the socalled critical region). In practice the usefulness is, of course,
bounded by computer power : for instance, the computerassisted result for
the 2dimensional Ising antiferromagnet in Dobrushin, Kolafa and Shlosman
(1985) is weaker than the aforementioned result based on the
criterion in van den Berg (1992).
A natural question is whether the notion of disagreement percolation
also leads to some constructive uniqueness criterion. This seems indeed to
be the case for monotone models, but we have not yet carefully studied its
properties, and therefore will not treat this subject here in more detail.
4. The main purpose of this paper is to show how the notion of disagreement
percolation in van den Berg (1992) can be fruitfully combined with coupling
ideas. We have
not searched for the most general or most optimal results. For instance,
throughout this paper we have assumed that the singlesite state space
$S$ is finite. Almost everything goes through unaltered if $S$ is
countably infinite. However, since all our relevant applications
have finite $S$, we have ignored the countably infinite
case. When $S$ is uncountable, new ideas are needed and a proper alternative
of the notion ``path of disagreement'' has to be found.
Another possible direction of improvement is indicated in Remark 2
at the end of the
proof of Theorem 1.
\head 4. Proofs \endhead
\subhead a) Proof of Theorem 1\endsubhead
For convenience, we extend the field to $\partial A$, i.e. we construct
a collection
$(\s_1(i),\s_2(i), \, i \in A\cup \partial A)$.
First, naturally, we set for each $j\in \partial A, \s_1(j)=\e_1(j)$ and
$\s_2(j)=\e_2(j)$.
Before we proceed, we put an arbitrary order on the set
$A$. Next we assign step by step a $\s_1(i),\s_2(i)$ value to the
vertices
$i\in A$. Each step goes as follows. Let $W$ denote the set of vertices
which have already obtained their value ; in particular, $W=\partial A$ at the
beginning. Further let, for each $j\in W, \a_1(j),\a_2(j)\in S$ be the
$\s_1$ and $\s_2$value respectively, which $j$ has obtained.
Now take the smallest (with respect to the above mentioned order on
$A$)
vertex $v\in A\setminus W$ with the property that there exists a $j\in W$
adjacent to $v$, for which $\a_1(j)\neq\a_2(j)$. If no such vertex exists,
we relax the required property and just take the smallest element $v$
of $A\setminus W$. If this last set is empty we have finished our
construction.
Having found the above vertex $v$, consider the following two probability
distributions :
$$
\nu[\s(v)=\cdot\,\,\s(j)=\a_1(j), j\in W],
\nu[\s(v)=\cdot\,\,\s(j)=\a_2(j), j\in W]\tag4.1
$$
%
We take an optimal coupling (as in (1.10)) of these two distributions,
draw
a pair $(a,b)\in S\times S$ according to this distribution, and set
$\s_1(v)=a, \s_2(v)=b$.
We continue these steps until each vertex $i\in A$ has obtained its
$(\s_1,\s_2)$ value.
To see that the random field $(\s_1(i), \s_2(i), i \in A)$
we have now obtained
is indeed a coupling
of $Q_A(\cdot, \e_1)$ and $Q_A(\cdot,\e_2)$
(i.e. that it has the correct marginals), we use induction
on the number of vertices in $A$. If
$A=1$, it follows immediately from the construction.
Suppose that it holds for all $A'\subset V$ with $A'=n$ and $n$
some fixed number. Suppose we now have a set $A\subset V$, for which
$A=n+1$. For a fixed pair of b.c.'s $\e_1,\e_2$ the first
vertex that is chosen in $A$ is unambiguously determined by the order
we have chosen.
Call this vertex $v$ and write $A=A'\cup\{v\}$ with $A'=n$. Once the
earlier described construction of the random field
$(\s_1(i), \s_2(i), i \in A)$, (whose distribution we denote by
$P_A^{\e_1,\e_2}$) is finished, consider the probability
of a certain realization $\a_1$ of $\s_1$:
$$\multline
P_A^{\e_1,\e_2}[\s_1\equiv\a_1\text{ on }A]=\\
\sum_{\a_2(v)\in S_\nu^{\{v\}}} \, P_{A}^{\e_1,\e_2}[\s_1\equiv\a_1\text{ on
}A\,\,\s_1(v)=\a_1(v), \s_2(v)=\a_2(v)]\\ \times
P_A^{\e_1,\e_2}[\s_1(v)=\a_1(v),\s_2(v)=\a_2(v)].\endmultline\tag4.2$$
%
Now the first factor is of the form
$P_{A'}^{\e_1',\e_2'}[\s_1\equiv\a_1\text{ on }A']$,
where $\e_1'$ denotes the configuration for which
$\e_1' \equiv \e_1$ on $\partial A' \setminus \{v\}$, and
$\e_1'(v) = \alpha_1(v)$.
Hence, by the
induction hypothesis, it equals $\nu[\s\equiv\a_1\text{ on }A'\,\,\s\equiv
\e_1'\text{ on }\partial A']$, which, by the definition of $\e'$, equals
$\nu[\s \equiv \a_1 \text{ on } A' \,\, \s \equiv \e_1 \text{ on }
\partial A' \setminus \{v\}, \s(v) = \a_1(v)]$. Finally, by the Markov property,
this equals
%
$$
\nu[\s \equiv \a_1 \text{ on } A' \,\, \s \equiv \e_1 \text{ on } \partial
A, \s(v) = \a_1(v)].\tag4.3$$
%
The second factor in the r.h.s. of (4.2) is determined from the
onestep coupling
procedure described after (4.1) and, by definition, has the correct marginals.
Hence its sum over $\alpha_2(v)$ equals
$\nu[\s(v) = \alpha_1(v) \,\, \s \equiv \e_1 \text{ on }
\partial A]$. Multiplying this with the expression (4.3) yields
$$\nu[\s \equiv \a_1 \text{ on } A \,\, \s \equiv \e_1 \text{ on }
\partial A],$$
as required. Analogously, it can be checked that $\s_2$ has the correct
distribution.
Part i) of the Theorem follows from the observation that, due to the Markov
property, each of the two distributions in (4.1) is a mixture of
distributions of the form $\nu[\s(v)=\cdot\,\,\s\equiv\a\text{
on }N_i], \a\in S_\nu^{N_v}$. Hence, using (1.11), no matter what happened
earlier in
the construction, the probability
that $\s_1(i) \neq \s_2(i)$ is always
at most $q_i$ (with $q_i$ as in (2.2)).
Hence, one can construct a coupling with a Bernoulli field $(X_i, i\in A)$
as defined in the Theorem,
such that, with probability one, $\s_1(i)\neq\s_2(i)$ implies $X_i=1$.
As to part ii), consider the first step in the construction above that the
selected vertex $v$ has {\bf no} neighbor $j$ which has already obtained a
value
$(\a_1(j), \a_2(j))$ with $\a_1(j)\neq\a_2(j)$. Apparently, at that step,
we have $\a_1(j)=\a_2(j)$ for all $j\in\partial (A\setminus W)$ and hence,
using the Markov property, the two distributions in (4.1) which are to be
coupled at that step are equal. Since we take an optimal coupling, the
$\s_1$ and the $\s_2$ value assigned to $v$ are also equal (almost surely).
But
this means that, in the next step, we are in the same situation, i.e. the
$\s_1$ and $\s_2$ value assigned at that step are again equal, etc. Thus, if
$\s_1(i) \neq \s_2(i)$, either $i\in \partial A$, or $i$ has a neighboring
vertex $j$ who obtained his
value in an earlier step and has $\s_1(j) \neq \s_2(j)$.
\qed
{\bf Remarks}
1. The coupling we have constructed here depends on the order
in which we choose to add vertices. There are simple examples where different
orders indeed lead to different couplings (i.e. to different probability
measures $\Cal P$ satisfying Theorem 1). Instead of a fixed chosen order
there are many other possibilities. For instance we could,
at every step in the coupling procedure, choose a vertex $v$
{\it randomly} from the
set $A \cap \partial \{j \in W : \a_1(j) \neq \a_2(j)\}.$
2. A direction of possible improvement is the following : in the proof
of part i) of Theorem 1 we have applied the inequality between the first
and the last expression in (1.11). The reason is that, in our application, we
have little control over the factors $\alpha_i$. However, if, for certain
models, we carefully exploit the little knowledge we do have about these
$\alpha_i$'s, some improvement can be made by using the first
inequality in (1.11).
\subhead b) Proof of Theorem 2 \endsubhead
The proof of part iii) follows from standard arguments :
for the first vertex $v \in A$ which is selected in the procedure described
above in the proof of Theorem 1, we have $W = \partial A$ and hence
$\alpha_1 \equiv \e_1$
and $\alpha_2 \equiv \e_2$ on $W$ so that, by assumption, $\alpha_1 \prec
\alpha_2$. Hence, by the definition of monotone Markov field, the
probability distribution in the l.h.s of (4.1) is dominated by that in
the r.h.s. Therefore, (see (1.12)),
we can take the optimal coupling of these distributions in such a way that
$a \prec b$ (i.e. $\s_1(v) \prec \s_2(v)$) with probability 1.
Now for the next selected vertex $v'$
we have $W = \partial A \cup \{v\}$ and we have again that $\alpha_1 \prec
\alpha_2$ on $W$. So in exactly the same way as for $v$ we get $\s_1(v')
\prec \s_2(v')$ etc.
Finally we prove part iv). The first inequality follows immediately from
part ii) and the
remark just before (1.10). As to the second inequality, let $m$ denote the
maximal element of $S$. Since, by iii), $\s_1(i) \prec \s_2(i)$
($\Cal P$a.s.) we have
%
$$\aligned
\Cal P[\s_1(i) \neq \s_2(i)] &= \Cal P[\cup_{s \in S, s \neq m}(
\s_1(i) \prec s, \s_2(i) \not \prec s)] \\
& \leq \sum_{s \in S, s \neq m} \Cal P[
\s_1(i) \prec s, \s_2(i) \not \prec s)] \\
&= \sum_{s \in S, s \neq m} \Cal P[\s_1(i) \prec s] 
\Cal P[\s_2(i) \prec s] \\
&\leq (S  1)\, d(\s_1(i),\s_2(i)).
\endaligned $$
%
The last inequality follows from (1.9). Using part ii) the result now follows
immediately.
\qed
\subhead c)Proof of Corollary 1\endsubhead
Let $\Cal P$ denote the distribution of the coupling $((\s_1(i),\s_2(i)),
i\in A)$ of Theorem 1. Then, applying the definition of coupling and
Theorem 1, (first part ii) and then part i)),
$$\aligned
Q_A(E,\e_1)  Q_A(E,\e_2)&=\Cal P[E\times\Om]  \Cal P[\Om\times E]\\
&=\Cal P[E\times(\Om\setminus E)]\Cal
P[(\Om\setminus E)\times E]\\
&\leq \max\{\Cal P[E\times(\Om\setminus
E)],\Cal P[(\Om\setminus E)\times E]\}\\
&\leq \Cal P[\s_1(i) \neq \s_2(i) \text{ for some
}i\in\Lambda]\\
&= \Cal P[\text{there is a path of disagreement from }\Lambda \text{ to }
\partial A]\\
&\leq P_{\{q_i\}}[
\text{there is an open path from }\Lambda \text{ to
}\partial A]\endaligned\tag4.4$$
%
\qed
\subhead c) Proof of Corollary 2\endsubhead
Let $\nu_1$ and $\nu_2$ be Markov fields for the specification $Y$. To
reformulate the problem in such a way that Corollary 1 can be applied, we
introduce an auxiliary Markov field
$\mu$, which is a convex combination of $\nu_1$ and $\nu_2$, say
$\mu=\frac1{2}\nu_1 + \frac1{2}\nu_2$. Clearly, $\mu$ is also a Markov field
for
specification $Y$.
It is sufficient to show that for every event $E$ as in Corollary 1,
$\nu_1[E]=\nu_2[E]$. Take a nested sequence $\Lambda = \Lambda_0\subset
\dots\subset\Lambda_n\subset \dots, n=1,2,\dots$ of finite subsets of
$V$ such that $\cup\Lambda _n=V$. We obviously have
$$
\nu_1[E]\nu_2[E]=
\sum_{\e\in S_{\nu_1}^{\partial \Lambda
_n}} \nu_1[\s\equiv\e\text{ on }\partial \Lambda _n]\,Y_{\Lambda_n} (E,\e)

\sum_{\e\in S_{\nu_2}^{\partial \Lambda
_n}}\nu_2[\s\equiv\e\text{ on }\partial \Lambda _n]\,Y_{\Lambda_n} (E,\e).
\tag4.5$$
%
The second factor in both summands is clearly smaller than or equal
to
$$\max_{\e\in S_\mu^{\partial\Lambda_n}} Y_{ \Lambda
_n}(E,\e),\tag4.6a$$
%
and larger than or
equal to
$$\min_{\e\in S_\mu^{\partial \Lambda_n}} Y_{ \Lambda
_n}(E,\e).\tag4.6b$$
%
Hence (since in both summands the sum of the first factor equals 1), we have
$$
\nu_1[E]\nu_2[E]\leq \max_{\e,\e'\in S_\mu^{\partial \Lambda_n}}
Y_{\Lambda_n}(E,\e) 
Y_{\Lambda_n}(E,\e').\tag4.7a$$
%
Noting that in the r.h.s. of (4.7a) we can replace
$Y_{\Lambda_n}(E,\e)$ and
$Y_{\Lambda_n}(E,\e')$ by
$\mu[E \,\, \s \equiv \e \text{ on } \partial \Lambda_n]$
and
$\mu[E \,\, \s \equiv \e' \text{ on } \partial \Lambda_n]$ respectively,
allows us to use Corollary 1 which yields
$$
\nu_1[E]  \nu_2[E] \leq
P_{\{q_i\}}[\text{there is an open path from }\Lambda \text{ to
}\partial\Lambda _n],\tag4.7b$$
%
where
$$q_i=\max_{\e,\e'\in S_\mu^{N_i}}d(Y_i(\cdot,\e),Y_i(\cdot,\e')).\tag4.8$$
%
However, for each $i, q_i\leq p_i$, with $p_i$ as in (2.5). Therefore,
$$
\nu_1[E]\nu_2[E]\leq
P_{\{p_i\}}[\text{there is an open path from }\Lambda \text{ to
}\partial\Lambda_n].\tag4.9$$
%
Under the hypothesis of the Corollary, taking $n\uparrow\infty $ in
(4.9) yields $\nu_1[E] = \nu_2[E]$. \qed
\head References.
\endhead
van den Berg, J. (1991). A uniqueness condition for
Gibbs measures, with application to the 2dimensional Ising
antiferromagnet, preprint, (to appear in {\it Commun. Math. Phys.}).
van den Berg, J. and Steif, J.E. (1992). On the hardcore lattice gas
model, percolation, and certain loss networks, preprint.
Dobrushin, R.L. (1968a). The problem of uniqueness of a Gibbsian
random
field and the problem of phase transition. {\it Functional Anal. Appl.}
{\bf 2} 302312.
Dobrushin, R.L. (1968b). The description of a random field by means
of conditional probabilities and conditions of its regularity. {\it
Theor. Prob. Appl.} {\bf 13} 197224.
Dobrushin, R.L., Kolafa, J. and Shlosman, S.B. (1985).
Phase diagram of the twodimensional Ising antiferromagnet (computer
assisted proof). {\it Commun. Math. Phys.} {\bf 102} 89103.
Dobrushin, R.L. and Shlosman, S.B. (1985). Constructive
criterion for the uniqueness of a Gibbs field, In : {\it Statistical
Mechanics and Dynamical Systems}, eds. Fritz, J., Jaffe, A. and
Sz\'asz, D. (Birkh\"auser, Boston).
Fortuin, C.M. and Kasteleyn, P.W. (1972).
On the random cluster model. I. Introduction and relation to other models,
{\it Physica} {\bf 57} 536564.
Georgii, H.O. (1988). {\it Gibbs measures and Phase Transitions},
De Gruyter Studies in Mathematics, BerlinNewYork.
Grimmett, G. (1973). A theorem about random fields. {\it Bull. London
Math. Soc.} {\bf 5} 8184.
Grimmett, G. (1989). {\it Percolation},
SpringerVerlag.
Hammersley, J.M. (1957). Percolation processes. Lower bounds for the
critical probability. {\it Ann. Math. Stat.} {\bf 28} 790795.
Hammersley, J.M. (1961). Comparison of atom and bond percolation.
{\it J. Math. Phys.} {\bf 2} 728733.
Harris, T.E. (1960). A lower bound for the critical probability in a
certain percolation process. {\it Proc. Cambridge Phil. Soc.} {\bf
56} 1320.
Higuchi, Y. (1982). Coexistence of the infinite (*)clusters : a remark
on the square lattice site percolation.
{\it Z. Wahrsch. Verw. Gebiete}
{\bf 61} 7581.
Kelbert, M.Ya. and Suhov, Yu.M. (1990). Statistical physics and
network theory. Manuscript.
Kelly, F.P. (1991). Loss networks. {\it Ann. Appl. Prob.} {\bf 1}
319378.
Kesten, H. (1982). {\it Percolation theory for mathematicians}.
Birkh\"auser, Boston.
Kesten, H. (1990). Asymptotics in high dimensions for percolation.
in: {\it Disorder in physical systems}, 219240, G.R. Grimmett and
D.J.A. Welsh eds., Clarendon Press, Oxford.
Kindermann, R. and Snell, J.L. (1980). {\it Markov random fields and
their
applications}, Contemporary Math. 1, American Math. Soc., Providence R.I.
Lindvall, T. (1992). {\it Lectures on the coupling method},
Wiley, NewYork.
Louth, G.M. (1990). {\it Stochastic networks: complexity, dependence
and routing}. Thesis Cambridge University.
Menshikov, M.V. and Pelikh, K.D. (1989). {\it Matematicheskie Zametki}
{\bf 46}.
Strassen, V. (1965). The existence of probability measures with
given marginals. {\it Ann. Math. Stat.} {\bf 36} 423439.
T\'oth, B. (1985). A lower bound for the critical probability of the
square lattice site percolation. {\it Z. Wahrsch. Verw. Gebiete} {\bf
69} 1922.
\phantom{ljh/;lkjnc/l kcnxv
vcxbvcbvcb
cbzcbzcbzxcbzbcbzb
bxbczbc}
\phantom{ljh/;lkjnc/l kcnxv
vcxbvcbvcb
cbzcbzcbzxcbzbcbzb
bxbczbc}
\phantom{ljh/;lkjnc/l kcnxv
vcxbvcbvcb
cbzcbzcbzxcbzbcbzb
bxbczbc}
\baselineskip=15pt
$$\aligned
\text{J. van den Berg}
\qquad\phantom{jjjjjjjjjjjjjjjjjjjjjjjjjpppppp}
& \text{Chr. Maes}\\
\text{CWI }
\qquad\phantom{jjjjjjjjjjjjjjjjjjjjjjjjjpppppp}
& \text{Instituut voor Theoretische Fysica}\\
\text{Kruislaan 413}
\qquad\phantom{jjjjjjjjjjjjjjjjjjjjjjjjjpppppp}
& \text{Celestijnenlaan 200D}\\
\text{1098 SJ Amsterdam}
\qquad\phantom{jjjjjjjjjjjjjjjjjjjjjjjjjpppppp}
& \text{3001 Leuven}\\
\text{The Netherlands}
\qquad\phantom{jjjjjjjjjjjjjjjjjjjjjjjjjpppppp}
& \text{Belgium}\\
\text{email : jvdberg \@ cwi.nl}
\qquad\phantom{jjjjjjjjjjjjjjjjjjjjjjjjjpppppp}
& \text{email : fgbda35 \@ blekul11.bitnet}
\endaligned$$
\enddocument