\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 Fortuin-Kasteleyn representation : it gives an explicit expression of the boundary effect on a certain vertex in terms of percolation--like 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 percolation--like 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 key--concepts 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 $1-p$. 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 computer-assisted proof of the lower bound 0.54.. . Non-rigorous 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 so-called {\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 1-1 relation between the above mentioned specifications and so-called nearest-neighbor 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 well-known 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 real--valued 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 if--part of this result is obvious, and the `only-if' 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 single--vertex 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 $1-q_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) single-site 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 single--vertex 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(1-p_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/(z-1)$. 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 continuous--time 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}^{n-m(\e)} a^r / r!}\phantom{[[[[[[[[[[[[} \text{ if }s \leq n-m(\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 hard-core 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 Fortuin--Kasteleyn} (1972) representation is one of the most appreciated methods connecting problems between ferromagnetic Potts models and percolation models. To be specific, we consider the nearest--neighbor 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 FK--representation 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 FK--representation. 3. The {\bf Dobrushin-Shlosman (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 so-called critical region). In practice the usefulness is, of course, bounded by computer power : for instance, the computer--assisted result for the 2-dimensional Ising antiferromagnet in Dobrushin, Kolafa and Shlosman (1985) is weaker than the afore--mentioned 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 single-site 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 one--step 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 2--dimensional Ising antiferromagnet, preprint, (to appear in {\it Commun. Math. Phys.}). van den Berg, J. and Steif, J.E. (1992). On the hard-core 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} 302--312. 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} 197--224. Dobrushin, R.L., Kolafa, J. and Shlosman, S.B. (1985). Phase diagram of the two--dimensional Ising antiferromagnet (computer assisted proof). {\it Commun. Math. Phys.} {\bf 102} 89--103. 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} 536-564. Georgii, H.-O. (1988). {\it Gibbs measures and Phase Transitions}, De Gruyter Studies in Mathematics, Berlin--New-York. Grimmett, G. (1973). A theorem about random fields. {\it Bull. London Math. Soc.} {\bf 5} 81-84. Grimmett, G. (1989). {\it Percolation}, Springer--Verlag. Hammersley, J.M. (1957). Percolation processes. Lower bounds for the critical probability. {\it Ann. Math. Stat.} {\bf 28} 790-795. Hammersley, J.M. (1961). Comparison of atom and bond percolation. {\it J. Math. Phys.} {\bf 2} 728-733. Harris, T.E. (1960). A lower bound for the critical probability in a certain percolation process. {\it Proc. Cambridge Phil. Soc.} {\bf 56} 13-20. Higuchi, Y. (1982). Coexistence of the infinite (*)clusters : a remark on the square lattice site percolation. {\it Z. Wahrsch. Verw. Gebiete} {\bf 61} 75-81. 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} 319--378. 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}, 219-240, 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, New--York. 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} 423--439. T\'oth, B. (1985). A lower bound for the critical probability of the square lattice site percolation. {\it Z. Wahrsch. Verw. Gebiete} {\bf 69} 19-22. \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