Lecture Notes in Mathematics Edited by A. Dold and B. Eckmann
724
David Griffeath
Additive and Cancellative Interacting Particle Systems
Springer-Verlag Berlin Heidelberg New York 1979
Author David Griffeath Dept. of Mathematics University of Wisconsin Madison, Wl 53706 USA
AMS Subject Classifications (1970): 60 K35 ISBN 3-540-09508-X Springer-Verlag Berlin Heidelberg New York ISBN 0-387-09508-X Springer-Verlag NewYork Heidelberg Berlin This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically those of translation, reprinting, re-use of illustrations, broadcasting, reproduction by photocopying machine or similar means, and storage in data banks. Under £354 of the German Copyright Law where copies are made for other than private use, a fee is payable to the publisher, the amount of the fee to be determined by agreement with the publishel © by Springer-Verlag Berlin Heidelberg 1979 Printed in Germany Printing and binding: Beltz Offsetdruck, Hemsbach/Bergstr. 2141/3140-543210
Preface These notes are based on a course given at the University of W i s c o n s i n in the spring of 1978.
The subject is (stochastic) interacting particle systems, or
more precisely, certain continuous time M a r k o v processes with state space S = {all subsets of Z d } .
This area of probability theory has been quite active
over the past ten years : a list of references, by no m e a n s comprehensive, found at the end of the exposition.
m a y be
In particular, several surveys on related
material are already available, a m o n g them Spitzer (1971), D a w s o n
(1974b),
Spitzer (1974b), Sullivan (1975), Georgii (1976), Liggett (1977) and Stroock (1978). There is rather little overlap between the present treatment and the above articles, and where overlap occurs our approach is s o m e w h a t different in spirit. Specifically, these notes are based on 9raphical representations of particle systems, an approach due to Harris (1978).
The basic idea is to give explicit
constructions of the processes under consideration with the aid of percolation substructures.
While limited in applicability to those systems which admit such
representations, Harris' technique m a n a g e s to handle a large number of interesting models.
W h e n it does apply, the graphical approach has several advantages over
alternative methods.
First, since the systems are constructed from "exponential
alarm clocks, " the existence problem does not arise.
Also, the uniqueness problem
can be handled with m u c h less difficulty than for more general particle systems. Another appealing feature is the geometric nature of the representation, which leads to "visual" probabilistic proofs of m a n y results. coupling.
Finally, there is the matter of
O n e of the basic strategies in studying particle systems is to put two or
more processes on a joint probability space for comparison purposes.
Graphical
representations have the property that processes starting from arbitrary initial configurations are all defined on the s a m e probability space, in such a w a y that natural couplings are often e m b e d d e d in the construction. conceptual simplification in m a n y arguments.
This is a major
Altogether, Harris' approach makes
the material easily accessible to a gifted graduate student having a familiarity with the elementary theory of M a r k o v chains and processes. The development is divided into four chapters.
Chapter I contains basic
notation, general concepts and a discussion of the major problems in the field of interacting particle systems.
It also includes a description of the percolation
substructures which are used to define the processes w e intend to study. is devoted to additive systems. Harris (1978).
Chapter II
The "lineal" additive systems were introduced by
%Ve also consider "extralineal" additive systems.
and pointwise ergodic theorems are proved.
General ergodic
A m o n g the specific models treated in
some detail are contact processes, voter models and coalescing random walks. Chapter Ill deals with cancellatlve systems, a second large class of models which admit graphical representation.
There are analogous general ergodic theorems for
IV
this class.
S p e c i f i c t o p i c s i n c l u d e an a p p l i c a t i o n to the s t o c h a s t i c I s i n g m o d e l ,
a n d l i m i t t h e o r e m s for g e n e r a l i z e d v o t e r m o d e l s a n d a n n i h i l a t i n g r a n d o m w a l k s . C h a p t e r IV w e d i s c u s s t h e u n i q u e n e s s p r o b l e m for a d d i t i v e a n d c a n c e l l a t i v e W e h a v e c l o s e n to p r e s e n t t h i s m a t e r i a l l a s t ,
In
systems
since uniqueness questions seem
r a t h e r e s o t e r i c in c o m p a r i s o n with the important p r o b l e ms of e r g o d i c t h e o r y .
The
g r a p h i c a l a p p r o a c h s h o w s how n o n u n i q u e n e s s can a r i s e w h e n t h e r e is " i n f l u e n c e from
oo .
"
A g r e a t d e a l o f t h e m a t e r i a l i n t h e s e n o t e s h a s a p p e a r e d in r e c e n t r e s e a r c h p a p e r s by m a n y a u t h o r s .
At t h e e n d o f e a c h s e c t i o n i s a p a r a g r a p h e n t i t l e d " N o t e s "
w h i c h i d e n t i f i e s t h e s o u r c e s of t h e r e s u l t s c o n t a i n e d t h e r e i n .
All r e f e r e n c e s a r e t o
t h e B i b l i o g r a p h y w h i c h f o l l o w s C h a p t e r IV. I w o u l d l i k e t o a c k n o w l e d g e my g r a t i t u d e to many m a t h e m a t i c i a n s for t h e i r contributions, T. H a r r i s ,
especially
R. H o l l e y ,
M. Bramson,
H. K e s t e n ,
D. D a w s o n ,
T. L i g g e t t ,
Sheldon Goldstein,
L. G r a y ,
F. S p i t z e r a n d D. S t r o o c k .
Let me
a l s o t h a n k t h e v a r i o u s S o v i e t m a t h e m a t i c i a n s w h o s e p i o n e e r i n g work o n c l o s e l y r e l a t e d d i s c r e t e t i m e s y s t e m s w a s a m a j o r s o u r c e of i n s p i r a t i o n for t h e c o n t i n u o u s time theory. Finally,
A s a m p l i n g o f t h e i r p u b l i c a t i o n s i s i n c l u d e d in t h e B i b l i o g r a p h y .
my t h a n k s go out to R i c h a r d A r r a t i a ,
S t e v e G o l d s t e i n and Arnold N e i d h a r d t
f o r t h e i r m a n y c o m m e n t s and c o r r e c t i o n s a s t h e s e n o t e s w e r e t a k i n g s h a p e .
David Griffeath Madison, Wisconsin A u g u s t , 1978
CONTENTS Page iii
Preface
CHAPTER I : INTRODUCTION. 1.
Preliminaries
Z.
Percolation substructures
CHAPTER
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
II : A D D I T I V E
......................
1 9
SYSTEMS.
i.
The general construction . . . . . . . . . . . . . . . . . . . . . . .
14
Z.
Ergodic t h e o r e m s for extralineal additive s y s t e m s . . . . . . . . . .
19
3.
Lineal additive s y s t e m s
Z6
4.
Contact systems:
basic properties
5.
Contact systems:
limit t h e o r e m s in the nonergodic c a s e . . . . . .
6.
C o n t a c t s y s t e m s in several d i m e n s i o n s
7.
Voter m o d e l s
8.
Biased voter m o d e l s
9.
Coalescing random walks
I0.
CHAPTER
....................... .................
...............
............................. ......................... ......................
Stirring a n d exclusion s y s t e m s
III : C A N C E L L A T I V E
...................
Z9 38 44 46 55 58 63
SYSTEMS.
I.
The general construction
......................
Z.
Extralineal cancellative s y s t e m s with pure births . . . . . . . . . .
71
3.
Application to the stochastic Ising m o d e l
74
4.
Generalized voter m o d e l s
......................
76
5.
Annihilating r a n d o m w a l k s . . . . . . . . . . . . . . . . . . . . . .
80
..............
66
CHAPTER IV : UNIQUENESS AND N O N U N I Q U E N E S S . 1.
Additive and cancellative pregenerators . . . . . . . . . . . . . . .
89
Z.
Uniqueness theorems
9Z
3.
Nonuniqueness
........................
examples
......................
98
Bibliography
101
Subject index
107
CHAPTER
I.
I: I N T R O D U C T I O N
Preliminaries. Throughout the exposition w e wlll use the following notation: Z d = the x,y,z S=
d-dimensional
c Zd
integer lattice
(d >- i) ;
are called sites.
{all subsets of Z d } ,
S O = {all finite subsets of Z d } , S
= {all infinite subsets of Z d } . oo
A, B, C ¢ S are called confi~uratlons.
A
A(x) = i
if
x ~ A,
= 0
if
x~/A.
Write
will always be a finite confi~uratlon,
IAI
Is the cardinality of A
i.e.
A ~ SO ;
.
Important finite configurations are tile n - b o x
bn(X ) centered at x ~ Z d :
bn(X) = {Y = (YI' "'" 'Yd ) : IY2 - x~l -< n for 1 -< 2 -< d} , and the block
[x,y]
C Z
, x,y ¢ Z :
[x,y] = { z : x - < z ~ < y } O n e useful abuse of notation is to write
x
instead of
{x}
for the singleton
configuration at site x ; w e will do this w h e n e v e r it is convenient. T = [0, co) is the (continuous) r,s,t,u
~ T
time parameter set;
aretimes.
Our objects of study will be certain continuous time processes,
or particle processes. A (£t)t~ T '
Here
A ~t
l.e.
A t0 = A •
Such a process will be written as
or simply
(~A) .
is the configuration of the process at tlme We
S-valued M a r k o v
t ,
say that there is a particle at site x
and
A
at time
is the initial state, A t if x c ~t "
Other notations for particle processes are
(~]A)and
(~A) .
of particle processes will be called a .particle system.
A family
P and
{(%A); A e S}
E will be the
probability l a w and expectation operator respectively governing such a system. S o m e additional notation: = {all probability m e a s u r e s on tL, v ~ ~ 8A ~ M
S} ;
are often called dlstributions.
is the m e a s u r e concentrated at A ( S •
Bernoulli product m e a s u r e such that ~t0 = 6)~ ,
cylinder sets
Any
For
Z s ( { A : x ~ A}) = #
t[ ( D
{A : A n A -- A 0 } , A 0 C A ~ S O .
~ U ( A ) = tt({A : A A
A 8A " ~t = ~t
thus
for all x .
is the
Thus
In fact, by inclusion-exclusion,
~5 : S0-
A = ~))
For each
[0,i]
,
.
A particle process started from an initial distribution
t~ ) ;
~8 e ~
is uniquely determined by its restriction to
is uniquely determined by its zero function
(~
0 -< 8 -< i ,
U
will typically be written as
t -> 0 , the distribution
~pt ~ ~
of ~
is
given by
uPt(.) = P ( ~
e .) ,
wlth zero function U.pt ~t~ : The transition m e c h a n i s m s be prescribed in terms of ~
c=
Intuitively,
c(A,A')
for the M a r k o v systems w e propose to study m a y
rates
{c(A,A') : A A
A' ~ S O } •
represents a n exponential rate at w h i c h the configuration of
particles "tries to jump" to A' from A ; w e require A ~ A' ¢ S O to ensure that the configuration of the infinite s y s t e m c h a n g e s at only finitely m a n y sites at a n y one time.
The precise formulation of j u m p rates will be deferred until Chapter 4.
In the important special case w h e r e c h a n g e s in configuration can only occur at one site at a t i m e ,
{([A)}
is called a spin system.
Such a s y s t e m is described by its
f l i p rates
Cx(A) = c ( A , A A x )
;
roughly, A P(~dt(X) / A(x)) .
Cx(A)dt ~
We now introduce three simple particle systems : the basic one-dimensional c o a l e s c i n g and a n n i h i l a t i n g random walks and c o n t a c t p r o c e s s e s . (1.1)
Example.
s i t e of A ,
Basic coalescing random walks.
Particles,
o n e s t a r t i n g from e a c h
e x e c u t e c o n t i n u o u s t i m e s i m p l e r a n d o m w a l k s o n Z s u b j e c t to a n i n t e r -
f e r e n c e m e c h a n i s m : w h e n e v e r a p a r t i c l e jumps to a s i t e which is a l r e a d y o c c u p i e d , the two particles at that site coalesce into one.
By a c o n t i n u o u s t i m e s i m p l e
random walk we mean a motion which w a i t s a mean-1 e x p o n e n t i a l time at e a c h position,
a n d t h e n j u m p s o n e u n i t to t h e l e f t or r i g h t ,
each with probability
~Z •
The p a r t i c l e m o t i o n s i n t h e c o a l e s c i n g r a n d o m w a l k s a r e i n d e p e n d e n t e x c e p t for t h e interference mechanism.
This s y s t e m may b e c o n s t r u c t e d w i t h t h e a i d o f a g r a p h i c a l
representation as follows.
Start with the s p a c e - t i m e diagram
Z × T •
For e a c h
site x ~ Z from
draw an infinite sequence of arrows with 6's on the tail: 6 > , I TZ Z x x+l 1 ( x , T I I , x ) to ( x + I , T I , x ) , (x, 1 , x ) to ( x + I , T I , X ) , e t c . T h e v a l u e s T1, x ,
Z 1 T1, x - ~1, x ' " " " a r e t a k e n to b e i n d e p e n d e n t e x p o n e n t i a l v a r i a b l e s w i t h m e a n ½ . S i m i l a r l y put a r r o w s w i t h Z (x, TZ,x)
6's
on t h e t a i l :
to (x-l, T Z,x), etc. for each
< 6 from ( x , ' r ~ x ) t o ( x - l , ~ , x ) , x-I x x ~ Z , where the T Z , x occur at rate 1 .
A generic realization is s h o w n in figure i .
Say there is a path up from
(y, s) t_. 9
(x, t) if there is a chain of u p w a r d vertical and directed horizontal edges in the resulting diagram which leads from through a
6 •
"percolation")
(i.2)
The
6's
without passing
(vertically)
m a y be thought of as obstructions to the flow (or
of liquid.
Now
define
A ~t = {x : there is a path up from
A little thought reveals that A.
(y, s) to (x,t)
(y,0)
to (x,t)
for s o m e
y ~ A} •
(~A) is the basic coalescing r a n d o m walks starting from
to'~ ~6
r
!6 4--..-
6 6
J~
6 -4
6
6
:~ -3
-I
3
4
figure i.
6 ,6 6
[5
-4
d
I-3
-Z
0
Z figure ii.
(1.3)
Example.
Basic annihilating random walks.
This is the same as the first
model, except that w h e n a particle jumps to a slte which is already occupied the two particles at that slte annihilate one another.
Thls second system can be defined
using the same random graph, or percolation substructure, as in of (I.Z)
If instead
take
A ~]t = {x : the number of paths up to (x,t) from (A,0) is odd} ,
(1.3)
then
we
(i.i).
(~]A) is the basic annihilating random walks starting from A .
(1.4) Problems. figure i,
For the realization of the percolation substructure shown in
and with
{(~A)} and
{(~]A)} defined by
(I.2) and
(1.3) respectively,
is 0 ~ ~Z ? Is 0 ~ Z ? It is obvious from the intuitive descriptions that tO T]to is a trap (= absorbing state) for {(~A)} and {( A)} . Explain howthis follows from (I.Z) and (~Z) and
(1.5)
(1.3). H o w m a n y changes of the infinite configuration take place in (~]Z) between
Example.
t--0
and t = s > 0 ?
Basic contact systems.
In thls case
{(~A)} is a spin system
with flip rates
xcA
Cx(A ) = 1 : klAn
{x-l,x+l} I
x/A.
A ' and k > 0 is a parameter. W e m a y think of the site x as infected w h e n x ~ ~t A healthy w h e n x / ~t " Thus infected sites recover at constant rate 1 , while healthy sites are infected at a rate proportional to the number of infected neighbors. the parameter k is an infection index. representations. {x} × T •
Contact processes also admit graphical
N o w three types of graphical device are attached to each
First, a sequence of 6's is put d o w n at rate 1 (i.e. with independent
exponential mean-i times between successive killing infection if it is present.
6's ).
These will have the effect of
Next, a sequence of directed arrows :
Is put d o w n at rate k , and finally a sequence of arrows at rate X .
Thus
> x-I x is also put d o w n
< x x+l The resulting percolation substructure wlll look something like figure ii.
Defining ~A by (I.Z) , in terms of thls second substructure, w e obtain the basic
contact system.
(i. 6)
Problem.
infected.
Let
(~)
be the basic contact process starting with only the origin
S h o w that for all sufficiently small positive k , the infection dies out
with probability one. These notes will be devoted exclusively to particle systems which can be constructed from exponential random variables with the aid of percolation substructures.
In thls w a y w e circumvent the first major problem in the theory of random
interacting particle systems : I. Existence : W h e n is there a system
{(~A)} with given jump rates c ?
A great m a n y systems do not admit graphical representations in terms of percolation substructures, and for these the existence problem is nontrivial.
A second funda-
mental question is :
If. Uniqueness :
W h e n is there a unique particle system
{(~A)} with given jump
rate s ? Even for the models w e will study, a precise formulation and treatment of this problem requires technical machinery ; w e therefore defer uniqueness questions until Chapter 4. O n c e the system is well-defined, interest centers on:
III. Ergodic theory :
W h a t is the asymptotic behavior of the processes
(~A) as
t~oo? W e n o w discuss the broad outlines of problem Ill.
A familiar property of M a r k o v
processes is their "loss of memory" under appropriate assumptions on the transition mechanism.
Starting from measure
~ , it is c o m m o n for ~pt to converge to an
equilibrium, or Invariant measure v as t ~ notion is that of w e a k convergence:
lira ~t({A: A N A =
. For particle systems the appropriate
lim ~tt = v
A0} ) = v({A : A n A =
(t c T o__[ t = 0,I, --.) if
A0} ) VA 0 C A,
By inclusion-exclusion, this last is equivalent to :
S0 .
7 l i m ¢ ~ t ( A ) = CV(A) t~o0 Say t h a t
v
VA ~ S O
i s i n v a r i a n t for t h e s y s t e m
{(~A)}
if v P t = v
p a r t i c l e s y s t e m s we study will a l m o s t a l w a y s be F e l l e r , ~ pt
~pt
as
~
~
for e a c h f i x e d
Any F e l l e r s y s t e m h a s a t l e a s t o n e e q u i l i b r i u m . mea
P- C t
that
ft
1 =T
p C t' - - v
as
{(~A)} .
t ~ T •
define the Cesaro
~pS d s
~ ~ ~ ,
v
for s o m e s u b s e q u e n c e
is invariant.
We have seen that
equilibrium.
t ~ T •
0
t' --oo ,
s y s t e m is c a l l e d e r g o d i c
~ •
Choose
v
such
U s i n g t h e F e l l e r p r o p e r t y , it
Let ~ b e t h e s e t o f a l l i n v a r i a n t m e a s u r e s
~ /9
if $ = {v}
t' .
so is
in the c a s e of a Feller s y s t e m .
for s o m e
v c ~ ,
i.e.
The
if it has a unique
This i s e q u i v a l e n t t o
(1.7)
3v ~ N : lira ~ C t = v t~oo
Say t h a t
The
in the sense that
To s e e t h i s ,
S i s c o m p a c t (in t h e d i s c r e t e p r o d u c t t o p o l o g y ) ,
is e a s y to c h e c k that for
tE T •
7
sure s
Since
for e a c h
{(~A)}
V~ ~
is s t r o n g l y e r g o d i c if
(1.8)
3 v ~ N : lira
~apt= V
¥~
~ •
•
t~co
Clearly strong ergodicity implies ergodicity. will invariably derive
(1.8)
rather than
(1.7)
When proving ergodic theorems we in t h e s e n o t e s .
no k n o w n e x a m p l e of a p a r t i c l e s y s t e m w h i c h s a t i s f i e s
(1.7)
H o w e v e r , t h e r e is but not
(1.8).
For
c o n v e n i e n c e we will u s u a l l y omit the word "strong" in the s t a t e m e n t of e r g o d i c i t y results.
(1.9)
Problems.
Prove that
(1.7)
i s e q u i v a l e n t to e r g o d i c i t y .
n e e d o n l y b e c h e c k e d for d e l t a m e a s u r e s
p = 6A ,
ergodicity.
x E S}
Find a Feller family
an equilibrium
v,
such that
{(~);
(1.7)
h o l d s but
A( S ,
Show that
to e n s u r e strong
on a c o m p a c t s t a t e s p a c e
(1.8)
(1.8)
does not.
S ,
and
8
(l.10)
Problem.
Let
{(Xt)}
be a Feller family on a c o m p a c t state space
invariant me as ur e for the family.
S h o w that the stationary process
ergodic if there is a set of states
Sv C
lira
6 ct=
t~oo
S h o w that
(~)
{(cA)}
ifwhenever
extremals, measures. v ~ ~
is Birkhoff
such that v(Sv) = 1 and Vx
~ S V
X
6 pt= v x
Vx
( S
v
nonergodic if it has more than one equilibrium,
v = cv0 + (l-c)v I for s o m e
v0 = v = vI , invariants.
v
an
is mixing if V(Sv) = 1 and lira t~oo
Call
S
(~)
S , v
i.e. if v
v 0 , V l ~ ~9 and
0 < c<
v ~ ~9 is extreme i,
then
cannot be written as a nontrivial convex combination of
According to C h o q u e t theory, any
v ~ ~9 m a y be written as a mixture of
so for nonergodic systems one wants to find all the extreme invariant Also,
if
(or
in this regard, ~ C t) -- v
as
~L is said to be in the d o m a i n of attraction of t~oo .
O n e tries to identify, as far as possible,
the d o m a i n of attraction of each equilibrium. In s o m e cases w e will be able to prove pointwise ergodic theorems. C
be the class of continuous functions
f : S-- R
(with the s u p r e m u m
Let
norm topology).
Pointwise ergodicity is an almost sure version of Cesaro convergence : t p(l for
/0
f(~s~)ds-
~S fay)= 1
~L in the d o m a i n of attraction of v ( ~9 •
Vf,
In case
is occupied converges almost surely to the
(I.Ii)
Notes.
,
f(A) = A(x) , for example,
this type of result asserts that the proportion of time b e t w e e n site x
C
0 and
t in w h i c h the
v-probability that x
is occupied.
The idea of constructing continuous time particle systems with the
aid of percolation substructures is due to Harris (I~9Y-8); more references to the origins of percolation theory can be found at the end of the next section. (i.i), (i. 3) and (1.5) will be studied in later sections, annotations until then. of Z
and
Examples
so w e defer the relevant
For more details on general particle systems,
the structure
~9 etc. , consult the survey articles mentioned in the preface.
Many
of
the other papers in the Bibliography deal with models w h i c h do not fit the framework
of t h e s e n o t e s ; t h e r e a d e r i s r e f e r r e d to t h o s e a r t i c l e s for a s a m p l i n g of a p p r o a c h e s to t h e f u n d a m e n t a l p r o b l e m s of e x i s t e n c e , 2.
u n i q u e n e s s and e r g o d i c i t y .
Percolation substructures. In thls section w e construct the general percolation substructures w h i c h will be
u s e d to define particle systems. infinite index set.
Write
For e a c h
x ~ Zd ,
I = {(i, x) : i ~ I } • x
"exponential alarm clock" w h i c h g o e s off at rate
1 2 Ti, x ' ~i, x ' • • • n+l n Ti,X - Ti,x ' X . l~x
n -> i
(~i,
Wi,x(y)~
(i, x)
k. -> 0 . l,X
there corresponds
M o r e precisely,
an
let
in Z d X T
V i,x c S O ,
corresponding to the ~Ari,x : Z d ~ S O
and a m a p
(i, x)
clock is
such that
I {y : w i , x(y) / {y} } I < ~ ,
as follows.
such that
To e a c h
be a finite or d e n u m e r a b l y
X = O) , are independent exponentially distributed with rate
The graphical m e c h a n i s m
(z .1)
structure.
Ix
be a n infinite s e q u e n c e of increasing times such that the
determined b y a set
"birth") ;
let
First,
label each point
(y, ni,x ) such that
y ~ Vi , x
with a
~
(for
t h e s e w i l l r e p r e s e n t s p o n t a n e o u s s o u r c e s of l i q u i d in t h e p e r c o l a t i o n s u b S e c o n d , d r a w a d i r e c t e d a r r o w from e a c h z/y
and
z ~ W i,x(y)
{@,{y}} .)
y / W i , x(y) .
Finally,
.
label
( y , Tni,x ) to e v e r y
n (No arrow e m a n a t e s from ( y , T i , x ) n (y, Ti,x)
witha
6
(for " d e a t h " )
( z , ~ xi ,) n if if
The r a n d o m graph o b t a i n e d in t h i s m a n n e r w i l l be c a l l e d t h e
percolation substructure,
and w i l l be d e n o t e d
i n t r o d u c e t h e maps 9 / i , x : S ~ S (2.2)
9/i,x(A)=
~ = e(k; V,W) •
(k ; V, W ) -
It is c o n v e n i e n t to
g i v e n by [ U yeA
W i , x ( y ) ] O Vi, x
9 / t , x ( A ) may be t h o u g h t of a s t h e s e t of s i t e s " w e t t e d " by l i q u i d e i t h e r at A or spontaneously when the 9 / i , x (A)A A E S O .
( i , x)
clock goes off.
(2.1)
implies
To e n s u r e t h a t t h e c o n s t r u c t i o n of ~ m a k e s s e n s e for our p u r p o s e s ,
we m a k e two a s s u m p t i o n s on t h e r a t e s : for e a c h
(z .3)
Note that
y ~ (i,~X) zd ki,x< i , x (" - y )
°° '
y c Zd ,
10
(Z . 4 )
~,
X. < 1,x
(i, x) :
w i , x(Y) / {y} Condition
(2.3)
ensures
a finite total rate at which each site is wetted either by
o t h e r s i t e s or s p o n t aneously,
while
site wets other sites or is labelled
(Z.5)
Examples.
k0, x =- I,
P
Vi, x ---~ and
W i , x ( y ) : {y}
k l,x ~ k Z , x =- k '
ensures
for Examples
W.~,x
for y /
x .
Vi,x ~ 9
and
W l , x ( X ) = {x,x+l} , W 2,x(x) = (x-l,x} A percolation substructure extralineal if Vi,x / @
(1.1)
given by
W i,x
and
(i,x) c I •
and
{1.3)
Wl,x(X)= (i • 5) P
In Example
has
{x+l} has
of the form:
W i , x ( y ) = {y}
{o,1 , z}
Ix ~-
W 0,x{x) = ~ ,
for y /
x .
is called lineal if Vi, x -n ~
P : ~(k; V , W )
for s o m e
a finite total rate at which each
6 .
The s u b s t r u c t u r e
Ix --- {i,2} , k.l,x -:i2 ' Wz, x(X): {x-l},
(2.4)
P
and
is said to be local if there is an
L < co such that
(Z.6)
diam{y
Condition with a
(2.6)
~ or
~ Z d : y e 9/i,x(Zd-y) or W i , x ( y ) /
V(i,x) c I •
says that the set of sites at the tails or heads of arrows or labelled
6 has diameter at most I , k.1,x -= k i ,
invariant if Ix
{y}} -< L
W i , x(y) ~- ~Ari(Y-X ) + x •
L
w h e n any clock goes off.
V.1,x = x + V.z
(translate by
x)
P
is translation
and
Intuitively, translation invariance m e a n s that the s a m e
type of percolation m e c h a n i s m
applies at each site x .
Note that the substructures
in (Z. 5) are lineal, local and translation invariant. As i n E x a m p l e s (x, t) in ~
up from
(= arrowed)
(x,t)
t -> 0 ,
say there is a p a t h u p
to (x,t) .
M o r e generally,
(y, s) to (x,t)
(y,s)
without
( y , s) ~ D 1 t o s o m e
D 1 to
DZ ,
(x,t)
~ Dg •
set
f~t = { ( y ' s )
For our construction
labelled
of particle
[~ i n
systems,
P,
to
By convention there is always a path
there is a path up from
if t h e r e i s a p a t h u p f r o m s o m e
from
(= increasing in T ) and
edges w h i c h lead from
6 on the interior of an u p w a r d edge•
D 1, D Z ~ Z d X T For
(1.5),
if there is a chain of alternating "upward"
"directed horizontal" having a
(i.i), (1.3) and
0 < s -< t} ,
a key ingredient
f~ =
U t>O
f~t
will be the quantities
,
11
(z. 7)
N~t(B) = the n u m b e r of paths up from
(A,O) U f~t to (B,t) in f~ . AA
Given any
@(k; V , W )
A
A
k i , x -= k i , x ,
V i , x --- V i , x
A
A
@(A;V,W)
, there is a dual substructure
d e f i n e d by
and
A
z c W i , x ( y ) <.
>
y~ Wi,x(Z)
Thus the dual substructure reverses the directions of all arrows. consider
~t = the restriction of ~ A
time run "down" from Pt '
('En, x" n -> i) .
i.e. letting
0 = t to t = 0 , and reversing the direction of all arrows in ~t
A
A
= ~
A
restricted to Z d x [0, t ]
on the s a m e
This follows from the time reversibility of the sequences Evidently
{3
path up from
(y,s)
(z.8)
to (x,t)
in @t }
a
=
By reversing time,
and
A
w e obtain a realization of
probability space.
to Z d x [0, t] •
Fix t < co ,
{3
path d o w n f r o m
A
(x,0)
to (y,t-s)
A
in ~t }
a n o b s e r v a t i o n w h i c h w i l l be c r u c i a l for t h e a n a l y s i s to c o m e .
P - a.s.,
The d u a l s u b s t r u c t u r e s
/k
Pto
c o r r e s p o n d i n g to t h e
~to Of f i g u r e s
i and
i i a r e s h o w n in f i g u r e s
iii and
iv
respectively. (2.9)
Problems.
Let e
be the extralineal substructure with
I -z {I,Z} , X
XI,x = Kx ' XZ,x = kx' otherwise.
Vl,x : {x} ,
A
1 , k x=
x
Z
(b)
:
{([A)} .
for all t -~ 0
the M a r k o v chain
configuration Problem.
flip rates
W i , x ( y ) = {y}
Now
consider the special case where
d = i,
For this model s h o w that if A ~ S O , then
A (a) It ~ SO
(Z.10)
and
{x ~(x)>0}
Describe the particle system X
~ ' W z , x (x) =)Z
Put
~t :
K
VZ,x:
([A) t
P - a.s., m a k e s only instantaneous visits to each
A c SO .
The basic voter model
(d : I) is the spin system
{([A)}
with
12
_%. 6
6 6
--
6 ; 6
-6 -3
-Z
Z figure iii.
--9,6
6
6
,6
-4
-3
-Z
3 figure iv.
13
1 IA n Cx(A) = 5-
{x-i, x+l)} I
x / A
= ~ -1 i AC n { x - l , x+l} I
x c A
^ S h o w t h a t t h e v o t e r m o d e l may b e d e f i n e d a s i n ( 1 . Z ) , but in t e r m s of ~ , s u b s t r u c t u r e for t h e
(Z.11)
Notes.
@ of E x a m p l e
the dual
(1.1).
L i n e a l p e r c o l a t i o n s u b s t r u c t u r e s w e r e i n t r o d u c e d b y H a r r i s (1978);
w e r e f e r t h e r e a d e r t o t h a t p a p e r for more d e t a i l s o f t h e f o r m a l c o n s t r u c t i o n .
The
i d e a b e h i n d t h i s t y p e o f r a n d o m g r a p h g o e s b a c k t o t h e p i o n e e r i n g work o n p e r c o l a t i o n by B r o a d b e n t a n d H a m m e r s l e y (1957). tions with particle systems,
s e e C l i f f o r d a n d S u d b u r y (1973),
S h a n t e a n d K i r k p a t r i c k (1971), c h a i n i n P r o b l e m s (Z. 9)
For more o n p e r c o l a t i o n t h e o r y a n d i t s c o n n e c -
Toom (1968) a n d V a s i l e v (1969) •
is due to Blackwell
are a t the end of Section II. 7.
H a m m e r s l e y (1959),
(1958).
The i n s t a n t a n e o u s
R e f e r e n c e s for t h e v o t e r m o d e l
CHAPTER II: ADDITIVE SYSTEMS 1.
The g e n e r a l c o n s t r u c t i o n . Let @= @(X;V,W) b e a p e r c o l a t i o n s u b s t r u c t u r e .
For t-> 0 ,
A~ S ,
with
NA(B) as i n ( I . 2 . 7 ) , define ~tA = {x : NA(x) > 0}
(i.i) Then
{(~A)}
is an
system induced by
S-valued M a r k o v family, called the (canonical.) additive particle A ~ . If ~t = B and the (i, x) clock goes off, then according to
(i.I), configuration
B jumps to ~/i,x(B)
(cf. (I.Z.Z)).
An additive system is
called lineal, extralineal, local a n d / o r translation invariant if the underlying of the corresponding type.
(i.2)
Proposition.
A particle system that A C
{(%A)}
Proof.
then
A,B c S ,
A ;- N t (x) > 0
t -> 0
B o__[r N t (x) > 0 .
(additivity)
[3
is called m o n o t o n e if for every pair A, B c S
Corollary.
B ~t
such
for all t-> 0 .
Every additive system
By additivity,
if B D A
{(~A)}
is monotone.
then
B A B-A ~t = £t U ~t D
A ~t
for all t-> 0 .
[]
In order to apply s o m e of the basic facts from Chapter I, w e want be Feller.
To guarantee this, one needs a very mild hypothesis on
has influence from times
.
B there is a joint probability space on which A ~t C
(1.3)
is an additive system,
A B = ~t U ~t
NA U B t (x) > 0 <
Proof.
is
The term "additive" is explained by
If {(~A)}
AUB ~t
~
tI ~- tZ -> ...
co t__oo(x, t) if there are n o n - e m p t y such that
sets
~ .
{( A)}
to
Say that
A I, A Z , • • • and
15
(i) for each yea
n >-- i,
there is a path up from
(Y,tn)
to (x,t)
for all
n"
and
lira lYnl :
(ii)
oo
for s o m e
Y
n~oo
If, in addition,
lira n--oo
(iii)
then
P
the
A n
IAnl
n
~ A
n
can be c h o s e n so that
= oo ,
is said to have strong influence from
co to (x, t) .
Influence from
co to
(x, t) w h i c h is not strong is called w e a k influence.
(1.4)
Proposition.
If e
is a substructure such that
P(strong influence from
then the additive
Proof. as
Write
A n-
A .
Bn ~ Z d
A {(~t)}
system
A A ~0t (A) = P(~t N A If A n - - A ,
as
n~oo
A {~t n N
.
A
oo to (x,t)) : 0
~ Zd ,
t -> 0 ,
induced
by
= ~) .
It suffices to s h o w that
An A ~0t (A)--~0t(A )
B n~
Bn= AN
then there are
P
Vx
is Feller.
SO
such that A n N
B n and
Now
= J ~ } A {C A N
A = Jg} C
= {3
path up from exactly one of (A n N or
(A A B e O) n ' c
As
n--co,
{3
to
B n , 0)
(A,t)]
path up from
c (B n ,
O) t o
(A, t)}
.
these last events converge to C
{3
path up from C
(B n, 0) to (A,t) V n }
{strong influence from
co to (x,t)
Thus the claim follows from the hypothesis.
We the models
will discuss
substructures
in this chapter
x~
A}.
[]
with influence
and the next will have
for s o m e
from
co in Chapter
no influence
from
oo .
IV,
but all
In fact,
if
16
(1.5)
sup
~
k.
y c zd
Y ~ ~/('i, ''?()ZI ~ d_y)
=
M
<
co ,
1,x
o__[r~/i,x(y ) = )~ and
(1.6)
Q
i s l o c a l or t r a n s l a t i o n i n v a r i a n t ,
t h e n i n f l u e n c e from co c a n n o t o c c u r . chapter satisfy
(1.5)
and
(1.6),
The s p e c i f i c a d d i t i v e s y s t e m s
A { ( I t )}
s o t h e y a r e F e l l e r by P r o p o s i t i o n ( 1 . 4 ) .
in t h i s The
h y p o t h e s i s of (t.4) will be a s s u m e d of g e n e r a l a d d i t i v e s y s t e m s until further n o t i c e .
(1.7)
Problems.
Prove t h e a b o v e a s s e r t i o n t h a t
P ( i n f l u e n c e from oo t o
(x,t)) = 0 Vx,t
.
(1.5)
and
(1.6)
imply
G i v e a n e x a m p l e of a s u b s t r u c t u r e
w i t h s t r o n g i n f l u e n c e from oo for w h i c h t h e c a n o n i c a l a d d i t i v e s y s t e m d e f i n e d by
(1.1)
{([A)}
i s no__ttF e l l e r .
W e n o w p r o c e e d t o d e r i v e t h e d u a l i t y e q u a t i o n for a d d i t i v e s y s t e m s .
Adjoin
/%
an isolated point for all times
A to
SO ,
A ~ S (@ i n c l u d e d ! ) AB TA , B ~ S O , o n ~
and write Let
~
~ ,
A N A/ and define
by
i f no s u c h
Next, introduce the family
By c o n v e n t i o n ,
b e t h e d u a l s u b s t r u c t u r e for
A B TA = i n f { t - > 0 : 3 p a t h u p f r o m ( : oo
S = SO U A .
t
(B,O)
to
~t
in
i ~}
e x i s t s ).
^B A {(~t ); B ~ S 0} of S-valued M a r k o v chains, called the
dual processes for {(~)} , and given by AB ~t = {X : 3 path up from (B,0) to (x,t) Jn ~} = A
AB t < TA
AB t_>TA
Finally, introduce "C~ = inf{t >--0 : ~tB = ~ }
AB
Note that ~ finite.
and
A
(= co if no such
are both traps for
t exists).
AB A B AB (~t) ' so at most one of T ~ and T~
is
Our first theorem will be the main tool in the study of additive systems.
17 To s t a t e i t ,
we i n t r o d u c e t h e n o t a t i o n Ct~ =
~ ~
~
(1.8)
,
Ac
S,
Theorem
induced by
P,
A~
SO ,
S,
B~
~ pt ,
Bc
A
(Pt
=
6APt (P
et(A)=~(
hA= ~),
SO . A
( A d d i t i v e d u a l i t y equation.) L e t {(~)} be t h e a d d i t i v e s y s t e m AB {(~t ); B ~ S O } t h e c o r r e s p o n d i n g d u a l s y s t e m . For e a c h t -> 0
(pt(B) = (Pt (A)
(1.9)
M o r e generally,
A E
if
(1.10)
•
A
is the expectation
t~(B)= E[ ^- ~ (~S)]
o p e r a t o r for t>- 0,
For ~8 = Bernoulli product measure with density we
(1.11)
^
I ~
@t (B)= E[(I-(~)
Z(
P ,
~ ,
B(
SO
•
8 ,
]
A
Proof.
Let
zdx [0,t]
~t and
: zd×
According to
Pt be the forward and reverse percolation substructures on
[%',?]
(I.Z.8),
which were discussed
copies of
these joint substructures
(~A)0_<s_
and
toward the end of Chapter I • AB ( ~ s ) 0 --< s --
in such a way that
P-a.s.
In fact, both events are
{~
P - a.s.
a path b e t w e e n
The first duality equation respect to
~ :
equivalent to
(1.9) follows.
(A, O) U ~t and
To g e t
(B,t)} .
(1.10),
integrate
(1.9)
with
18
~o~CB)= f ~th(B)~ (dA) AB
f ~t (A)~ (dA)
=
A:Af]A:~
Ac Since
~
O(A)
=
)IA[
(1-0
AAB
)~
=
,
P(~t
: A)~(A):
B A E[~C~A
)]
•
SO (I.II) f o l l o w s from
As e a s y c o n s e q u e n c e s
(I.I0) .
of the duality equation,
[]
w e obtain t w o results on the
ergodic theory of general additive systems.
(1.12) v0
and
Corollary.
A {(~t)}
Let
be additive.
v I such that
6 ~ pt -- v 0
T h e zero functions for v 0
and
V0 (i.13)
Proof.
There are extreme invariant m e a s u r e s
~
A
6 z d pt
and
vI
t-- oo
v I are Vl
A A
(A) = P ( T A
= co) ,
~
A AA (A) = P ( T ~
According to the remarks on c o n v e r g e n c e
that for a n y
as
< co ) .
in Chapter I, it suffices to note
A ~ SO , t~ (A)=
A A.A. P(T A >t)
A A - AI P ( T A : co)
and Zd
as
t--o0 .
argument
(1.14) v 0
(I. 15)
The fact that v 0
(cf. Problem
Problem.
->~->~
A
v 1
.
Corollary.
A A
and
(1.14)).
A
AA
v I are extreme follows from a n e a s y monotonicity []
Use Corollary
(1.3)
Conclude that
v 0 and
The a d d i t i v e s y s t e m
t o s h o w t h a t if
[~ ~ $ ,
then
v 1 are extreme equilibria. {([A)}
is ergodic if and only if
19
AA
(I.i6)
AA
~(T~
(a A b
^ Ti
denotes the m i n i m u m
< ~): I
of a and
Pr___oof. From the previous corollary,
S •
so
.
b .)
~t c
,A c ~t
_Zd ~t
so t h a t
~
-> ~tA -> ~tZ d
[]
A f e w words about additive processes starting from arbitrary ~ ~ ~ order at this point.
Note that while
it does not represent prescribed,
(~)
(I.I) defines
([A)
= ~t
on
are in
simultaneously for all A ,
for nondeterministic initial distributions.
When
~i is
a straightforward w a y to get such a representation is to enlarge the
underlying probability space to support a i-distributed r a n d o m subset ~
for
A v say, w e conclude that ~t ~ ¢t '
If v 0 = v I = v ,
establishing ergodicity.
~
w e see that (1.16) is equivalent to v 0 = v I •
By Corollary (1.3), on the other hand , all t > 0 , A ~
VA
{¥ = A} •
¥
On o c c a s i o n s w h e r e w e c o n s i d e r s u c h a p r o c e s s
and set (~
) ,
it
will be assumed without further comment that this construction has been carried out.
(i.17)
Notes.
Lineal additive processes are studied by Harris (1978);
Berteln and Galves
(1978).
Graphical duality has appeared in one form or another
in Broadbent and H a m m e r s l e y Toom
(1957), Clifford and Sudbury
(1968) and Vasilev (1969).
Leontovich
Z.
(1970).
Holley and Liggett (1975), Holley and
Stroock and Williams
Monotone
(1973), Harris (1978),
For another more analytical approach to duality,
the reader is referred to Harris (1976), Stroock (1976d), Holley,
see also
(1977) and Vasershtein and
(= attractive) systems are discussed by Holley (197Zb).
Ergodic theorems for extralineal additive systems. In this section w e derive general ergodic theorems for extralineal additive
systems. measure
v c ~
(z.i) where
A particle s y s t e m and a constant
{(~tA)} ~ > 0
~IPt({A : A n A = A0} ) cA
-
is called exponentially er@odic if there is a such that, for every
~ ~ • , A 0 O A ~ SO ,
v({A: A n A = A0}) I -< c A e - ~ t
is a positive constant depending only on
A .
,
20
(Z .Z)
Theorem.
e(k;V,W)
•
A
Let
{(~t)}
be an extralineal
additive
system
with substructure
If
(Z.3)
inf Y ~ Zd
~ (i,x):
ki
~X
=
~ > 0
Y~ % , X then the system is exponentially ergodic.
Proof.
Condition
at each
site
y
dual process
(Z.3)
states
that a
with rate at least
goes to
A
By duality, for any
[3 a p p e a r s
K > 0 .
Thus,
with rate at least
A A B AB P(T~ A T A
(Z.4)
In fact,
A(
S,
~ .
(Z.l) holds with
in the substructures from any non-empty It f o l l o w s
¢~ = K
f~ a n d finite
that
-~t
> t) --< e
B c SO , t ~ T •
B ~ SO ,
A AAB AAB ~t(B) = P(T~ --< t) + P(~t N A =
AB A B )Z , t < ~)~ A T A ).
Rearranging,
@A(B)
A/XB P(T~
-
=P
Now
apply
(Z.4)
<
~)
NA:9,
A
~ ( t < A B < co)
Vl (B) -
and use inclusion-excluslon
Corollary.
AB
to get
I~
(Z. 5)
AB
(B) I -< Ze -Kt
,
to finish the proof of (Z .I) .
[]
Any translation invariant extralineal additive system is
exponentially ergodic.
Proof.
(2.3)
is automatic in the translation invariant case.
[]
Our next result asserts that in m a n y cases the unique invariant Theorem
(Z. Z) has exponentially decaying correlations.
v
in
A
the
21
(2.6) and
Theorem.
Given a local extralineal substructure
(2.3), let {(~A)}
be the additive system induced by @ .
equilibrium for {(~A)} (2.7)
which is guaranteed by Theorem
I~v(BU C)-
where
c
and
d(B,C)=
Proof.
B,C~
SO .
(Z.8)
P(TjZ
/%
U C
(k; V,W) ,
sideof
AAB
(Z.7)
A AC
< co) - P(T~ < o o ) p ( ~
/k
@Z be two independent copies of ~
the two processes are independent.
With
.
ABUC N O W manufacture a copy of (~t
B and
C •
equals
f~l to define
/k s
(~t) and
(= oo ifno such
A
until "[L and
~1 thereafter.
on
a t} •
and
ABUC
P(T L < TA
jumps by
(the t h e o r e m i s t r i v i a l if
^A ABU P(~L < XA
C
) -< ~ ( L
) .
I LrJ (Z.3) p=-~
denotes the greatest
ensure that at each jump time K
> 0 .
Assuming
we conclude that
d(B~C)
J
jumps occur before
Ld(B,C)j --< (l-p) []
C}
Observe that there must be at
U C I by time
p = 1) ,
~BU
A
i n t e g e r l e s s t h a n r .) C o n d i t i o n s (1.5) a n d ^B U (~t C) g o e s t o A w i t h p r o b a b i l i t y a t l e a s t
as desired.
Under this
Thus
A A
i s m a j o r i z e d by
L dl\, clj
~i P
{~TL AC
(2.8)
t exists).
starting from B use
p~
~B AC = ~t U ~t
since
(I.Z.6), define
AAB AC AA B A AC P ( ~ < co, 7• < oo)= P(~G~ < oo) p ( y ~ < co),
representation,
least
and
/k
) by letting the flow
while the flow starting from C uses PZ
so that
SO ,
< oo)[ .
Use
L as in
A ~B ~C T L = min{t : d(~t' ~t )-< L}
C
B,C
^ C ; note that this is no__~tthe standard graphical representation, (~t)
to define
ABU ~t
(2.2), then
is the distance between
By (1.13), t h e l e f t
AAB
Let @i and
B, y c C}
(I. 5)
If v is the unique
~ V ( B ) ¢ v ( C ) I -< c e - a d ( B ' C )
~ are c o n s t a n t s d e p e n d i n g only on
min{Ix-y I : x~
Fix
~ which satisfies
-
< (l_p)-i e
P
L
T~)
d(B,C) ,
p<
1
PZ
22
When ergodic,
(Z.9)
P
satisfies
in the sense
Theorem.
(2.3),
described
{(~t')}
Let
be its unique equilibrium.
the induced
toward
additive
the end of Section
satisfy the hypotheses
Then for each l
Proof.
mixing. any
of T h e o r e m
(Z.Z), and let v
t
S
~$
by the procedure outlined at the end of Section II.I.
implies that the stationary process By Birkhoff's Theorem,
f ~ Ll(v) .
(Z.4)
I.l.
(Z. i0) holds for any translation invariant extralineal additive system.
Define
(I.l.10)
is also pointwise
f( C , ~ ~ ~ ,
t~oo In particular,
system
Now
for each
(~t)
it follows that x c Zd ,
is Birkhoff ergodic, (Z .10 ) holds in case
Problem
and in fact g = v , for
A , B e S , the duality construction and
show t h a t P(~
(x) fl ~ (x)) -< P(N (x) = 0 ,
NA
(x) > 0)
AAx AX --/{t --< P ( ~ A T A > t ) --< e By a routine
Borel-Cantelli argument,
P(~A(x) = ~B(x)
V s u f f i c i e n t l y large t ) =
1
Hence
P([A(x) = I t ( x ) Let Z
V
s u f f i c i e n t l y large
be the class of functions
f : S~ R
To finish the proof of (Z.9)
For f c $
•fA
A~ S •
w e conclude that
v V s->t}<~ )= f([s)
for f ~ ~ , ~ = 6A ,
P - a.s .
note that
t
--t 0 f([ ) ds = ~-
f([ ) ds + ~- ff A t f([ ) ds I
--
x e Zd ,
which depend on only finitely m a n y sites
(the so-called tame or cylinder functions.)
,f= m i n { t : f($
t) = 1
lira
T f
t
f(~sv) d s =
f fdv
23
as
t--oo ,
t h e l a s t e q u a l i t y by v i r t u e o f ( Z . 9 )
to
C a n d from
6A t o g e n e r a l
arguments.
(Z.ll)
[~ = v •
The e x t e n s i o n s from
a r e a c c o m p l i s h e d by m e a n s o f e a s y a p p r o x i m a t i o n
[]
Problem.
theorem,
~
for
Give an e x a m p l e s h o w i n g t h a t under the h y p o t h e s e s of the l a s t
p o i n t w i s e e r g o d i c i t y n e e d n o t h o l d for g e n e r a l
s t a r t s from a r b i t r a r y
f ~ Ll(v
when the process
A~ S •
Our n e x t t a s k w i l l b e t o i d e n t i f y t h e c l a s s o f a d d i t i v e s p i n s y s t e m s , particular t h o s e for which Theorems
(Z.Z),
(Z.6)
and
c a n only c h a n g e c o n f i g u r a t i o n at one s i t e at a t i m e , for all
( i , x) .
W's
Kx ,
VO,x=
{x} ,
Vi,x=
to x
and
~
otherwise.
0 ,
C i , x ~ SO .
appears at x , w h e n the
IVi , x l -<- 1
Vy ,
W i , x (y) = { x , y }
for s o m e
then necessarily
If a p r o c e s s
c a n b e c h o s e n t o b e of t h e form
W0,x(y)= {y} and for i /
apply.
W i t h o u t l o s s of g e n e r a l i t y we c a n a s s u m e
kO,x= Also, the
(Z.9)
in
(i•x) x
by removing
Thus
=
{y}
=
9
Y ~ Ci,x
y~'Ci, x,
and (it) rates
ki,x
(i)
rates
and finite sets
Cx -> 0 w i t h w h i c h a
Ci,x ' i/ 0 ,
such that
clock g o e s off an arrow is directed from every site of C i, x - {x}
is labelled with a i= 0 .
6 if x /
Ci
It is convenient to redefine
,X
T h e n if our process is in state A ,
occurs with rate
Cx +
while if x ~ A
i ,X ,
y:x/C
@ i s d e t e r m i n e d by
y/x
~ ki x i ~ Ix: A n C i , x / f~
a flip occurs at x
with rate
'
with
x/A,
Ix
a flip at x
24
l,X i C Ix: An
Conditions
(I.Z .3) and
.
(I.Z.4) =
are covered by the requirement that
~k
kx
<
~
Zd
Yx~
i,x
The flip rates m a y be consolidated in the form
(Z.IZ)
Cx(A) = Kx(l-A(x)) + k x A ( X ) + (I-ZA(x))
~
>~i,x
A N i~ Ix:
Ci,x/~
Condition
(1.5) is equivalent to
(Z.13)
sup x,A
A particle system (Z.IZ)
for s o m e
{(~A)}
Cx(A ) <
K x >- 0 , kl, . x >- 0 and
extralineal otherwise.
In the translation invariant case The hypothesis
(Z.3)
Problems.
system if its flip rates have the form
C i ,x ~ S O .
It is lineal if K x ~ 0 ,
The local property is
sup d i a m [ { x } x
(Z .14)
proximity
is called a
U ( [_J Ci,x) ] < oo i~ Ix Kx =- K ,
I -n I , x
Ci
~x -n x + C i and
k i, x -= k i "
holds if inf ~ > 0 . x x C h e c k the various assertions m a d e about proximity systems.
In particular, verify that every additive spin s y s tem is a proximity system. by e x a mp le that distinct substructures additive system, s a m e j u m p rates. a substructure
i.e. that distinct
~i and
(k I ; V I,WI)
~Z
can give rise to the s a m e
and
(k Z ; V Z , W Z) can induce the
Prove that any additive system has a representation in terms of
~(X;V,W)
such that either V i , x :
If {(~ At )] is a proximity system, coalescing branching processes.
~
or W i , x ( y ) = {y} V y
A •
.
on ~
are
a particle in the dual tries to
C i, x ~ $0 "
Whenever
attempt to o c c u p y the s a m e site they coalesce into one. sends the whole process to
^B (~t)
then its dual processes
At rate ki, x
replace itself with particles situated on
x
Show
two particles
At rate
In keeping with Corollary
Kx
a particle at
(1.15), ergodicity
25
of the proximity system is equivalent to eventual absorption of the corresponding coalescing branching system at either @ (Z. 15)
Problem.
+X X
with probability one.
be an extralineal proximity process such t h a t
{(~)}
Let
or A
and
> 0 forall x , X
K x
inf x
> 0
Kx+Xx S h o w by example that the convergence
Prove that the system is (strongly) ergodic. need not be exponential. A
(2.16)
Problem.
Let { ( ~ ) }
be a (one dimensional) basic voter model w i t h
spontaneous birth at the origin, i.e.
c0(A) = K(I-A(0))
+
A(0)
the e x t r a l i n e a l proximity system with flip r a t e s
+
(F1 -A(0))IAn {-I,i}[,
1
Cx(A)= A(x)+ (~--A(x))IAD {x-l,x} I for some
K > 0 .
. x>~0,
Prove that the system is (strongly) ergodic.
The final result of this section is a correlation inequality for proximity systems. (2.17)
Theorem.
K
{(~A)}
cA(Bu C)-
Proof.
By d u a l i t y ,
CA(B) cA(c)
A~
S,
B, C c
SO , t e T •
it s u f f i c e s to c h e c k t h e e q u i v a l e n t i n e q u a l i t i e s
AB
(Z.I8)
i s a p r o x i m i t y system, then
[J
C
~t
AB
/"C
(A) -> ~t(A)~t (A) •
To do this, w e use a strategy similar to the one which proved Theorem (Z. 6). w e fix B and
C,
and construct independent copies of (~B) and A
independent substructures
Namely,
(?tC) by using
A
~I and @? to define them.
But n o w w e introduce a
different representation of process interpretation. from
(~zxtB-U C ) , by making use of the coalescing branching AB Namely, whenever a particle from (~t) collides with one
AC (~t) ' the former survives and the latter dies.
mechanism is indistinguishable from coalescence,
Since this collision
w e do in fact obtain a copy of
26 AB U C (It-)
with the key property AB U C AB AC It C It U ~t
(Z.19)
In terms of our construction,
Vt ~ T
.
(Z.18) is equivalent to
AB U C AB AC P([t • A = ~) -> P(([t U It ) ~ A = ~) ,
an immediate consequence of (Z .Z0)
Problems.
(Z.19) •
[]
S h o w by example that the correlation inequalities of the last
theorem do not hold for all additive systems.
For which additive
{(~A)}
other than
proximity systems are the inequalities valid? (Z.ZI) Notes.
A result closely related to Theorem (Z.Z) m a y be found in
Schwartz (1977).
For versions of
(Z.Z) in the spin system setting, see Holley and
Stroock (1976d) and (in discrete time) Vasershtein and Leontovich (1970).
The
discrete time analogue of Theorem (Z. 6) is proved by Bramson and Griffeath (1978a); similar but more sophisticated inequalities for the stochastic Ising model (cf. (III.3)) have been obtained by Holley and Stroock (1976b). R. Arratia (private communication) has s h o w n that v
satisfies a strong form of exponential mixing
w h e n the hypotheses of (Z. 6) are satisfied.
Pointwise ergodic theorems for
particle systems were first obtained by Harris (1978);
w e note that Theorem (Z. 8)
can also be proved by generalizing the criterion he gives for lineal additive systems. Lineal proximity systems and coalescing branching processes were introduced by Holley and Liggett (1975).
Problems
(Z.15) and
(Z.16) are adapted from Holley
and Stroock (1976a) and Schwartz (1977) respectively.
Harris (1977) has proved a
much more general version of Theorem (2.17) by an entirely different method.
3.
Lineal additive systems. If the percolation substructure ~(k; V , W )
so that no
~'s appear, then w e abbreviate
is lineal, i.e. if Vi, x-:
~ = {~(X,W) •
Additive systems induc-
ed by lineal substructures have the important property that spontaneous creation is impossible.
In other words,
)~ is a trap so that 6@
is invariant.
In
27
biological contexts such systems might be termed "biogenetic" (as opposed to "abiogenetic").
Ergodicity is therefore equivalent to w e a k convergence to
6@ from
any initial state, and the ergodic theory of lineal systems turns out to be m u c h more delicate than that of extralineal ones.
The remaining sections of this chapter will
be devoted to the study of specific lineal additive systems voter models,
coalescing random walks) in some detail.
(e.g.
contact processes,
But first, w e note a few
simplifications which take place in the duality theory for the lineal case,
and prove
an ergodic theorem for lineal proximity processes.
(3 .i)
Theorem.
ture ~ ( k , W ) , substructure systems.
Let
{([A)}
AB {(It ); B ~ S} ~(k,W)
For each
.
Let
t e T ,
(3.1)
be the lineal additive system induced by a substructhe lineal additive system induced by the dual
tA
~0
and
-'B ~ot
be the zero functions
of the respective
A, B e S ,
~tA(B) = ~~tB (A)
There is an extreme invariant measure
v I c h~
such that
8 d-- vl as Z
t~oo .
Moreover,
{(~A)}
ergodic <.--:-~- v I = 6~
< Proof. AB (~t) all {~An
In the lineal case
AA A :" P ( ~ < ® ) =
S =)~ ,
B = ]O} and
VA ~ So •
TA AB = co P - a.s.
is simply the process induced by ~ B ~ S , and
I
.
for all B ~ S O , and so A B In this case (~t) can be defined for
(3.1) holds because on the joint substructure the events {~B N A = 9}
are both
{~{ path between
P - a.s.
(A,0)
and
equivalent to
(B,t)} .
The remaining assertions are simply the specialization of Corollaries (1.15) to the lineal case. A
If {(~
(I.IZ) and
[]
)} is a lineal proximity system,
then its dual
AA {(~t )} is the lineal
system of coalescing branching processes determined by the k. 's and ix the form
W. 's of l,X
28
W i , x ( y ) : Ci, x :
y = x
y/x
{y}
An ergodic theorem for lineal proximity systems is easily obtained by exploiting the branching interpretation of their duals.
(3 .z)
Theorem.
form (Z.iZ)
Let {([A)} be a lineal proximity system, with flip rates of the
(with K
x
~- 0).
= inf k x, x~ Zd
Tf L > 0 and
Set
m=
sup x ~ zd: kx>0
~ i~ I x
X
]Ci,x 1 x
m < i , then the system is exponentially ergodic.
invariant case the system is also ergodic if m = 1 and
In the translation
C i, x = Ci = ~
for s o m e
i;
in fact,
(3.3)
1 - ~(_A)
where
c
is a positive
Sketch of proof: process tions
-<
constant
clair
-1
depending
The dual process
(~tA)
only on
,
tc
T,
A~
SO,
(k, W) .
can be imbedded in a spatial branching
(~A) , where the latter ignores the coalescence mechanism.
~ > 0 , m < 1 ensure that
(~tA)
Galton-Watson process, and since ~ {(~
~ ~ ~
)} follows.
The condi-
dies out more quickly than a subcritical C % tA , the exponential ergodielty of
In the translation invariant case
(] ~
1) is a Galton-Watson
process, so (3.3) is a consequence of the same comparison and a well-known rate of extinction result for nontrivial critical branching processes.
W e leave the details
of the proof, and s o m e complementary results, as an exercise. (3.4)
Problems.
x ¢ Zd
and
(a)
m<
or
i,
Fill in the details of the last proof.
S h o w that if X
x
> 0
for all
29
(b)
inf x ~ Zd
and
~ Xi, x > 0 i c Ix :
m = 1 ,
Ci, x=~ then {(~A)} is still ergodic. (3.5)
Problems.
that ~
A lineal substructure
coincides with
is self-dual.
~ (i, W )
is called .self-dual if W = W
so
P . A lineal additive system is self-dual if its substructure
S h o w that the basic contact systems of (I.i.5) are self-dual.
Thus
these systems m a y be thought of as either proximity systems or coalescing branching systems.
1 k -< ~- .
Apply Theorem (3 .Z) to prove ergodicity for any
Find other
examples of self-dual additive systems.
(3.6)
Notes.
Lineal additive systems are discussed,
in varying degrees of
generality, by Harris (1976, 1978), Holley and Liggett (1975), Holley and Stroock (1976d), and (in discrete time) Vasershtein and Leontovich (1970). for Theorem (3.2) is in Holley and Liggett (1975); detailed presentation of (3.2) and
4.
The prototype
see Liggett (1977) for a more
(3.3) .
Contact systems : basic properties. In this section w e study two families of translation invariant lineal proximity
systems in considerable detail : the basic (one-dimensional) the one-sided (one-dimensional)
contact systems.
contact systems,
and
The former were described in
Example (I.l. 5) ; recall that they were formulated as models for the spread of an infection.
When
w e will write
w e want to exhibit the dependence on the infection parameter
~A = ~ A X,t "
XO, x-= i ' ~l,x ~- k Schematically,
P
•
The one-sided model is defined by taking
C O , x -= J~ and
C l,x = {x-l,x}
Ix --- {0, i}
(K x -=0)o
has :
6 at each from
x
with rate 1
x-I to x
with rate k .
Thus a site can only be infected by its left neighbor, right.
in (Z.iZ)
k ,
Denote these systems as
so the infection spreads to the
{(~¢,A)} = {(~+,+A)} ,~,~
X -> 0 .
30
The main feature of contact systems is that they exhibit a critical phenomenon:
there is a k, ,
w h e n the infection rate k k > k~ . values,
0 < k, < oo ,
is less than
k;:. ,
such that ergodicity (= recovery)
while infection persists forever if
To distinguish b e t w e e n the two models, the two-sided value will be denoted by
which have different critical
k~ , the one-sided value by
Our first tasks will be to prove that the critical p h e n o m e n o n obtain bo un ds on
(4.1)
takes place,
+ k~ •
and to
and
+ k~..
Let
-{([A t) } be t h e b a s i c c o n t a c t s y s t e m with p a r a m e t e r k
k%
Proposition.
occurs
a n d write Z
p k , t = P(0 ~ [ k , t ) (4.2)
Pk :
(Vk,l =
lira 5 z P t
,
lira = v t~co Pk,t k,l
).
is i n f e c t e d } )
({0
Then
t~eo (4.3)
pkl ,t -< pkz ,t
and so
Pk
if
k I -< k z ,
is an increasing function of k •
tc T ,
If
k. : s u p { k : Pk = 0 } the systems with Letting
PX, + t'
k < k, PX+ and
are ergodic,
while those with
k > k,
are nonergodic.
k *.+ be defined similarly in terms of the one-sided systems
{({x'A)} , the analogous assertions hold.
Proof.
Property
0 -< k I < k Z < oo . define
[<,t
(4.2) Let
follows from T h e o r e m P
(3.1) .
be the substructure of Example
in terms of P
by
(i.i) .
Now
augment
arrows of the s a m e types which arrive at each site x the a u g m e n t e d of ~
via
substructure
(i.I) .
To s h o w
~ .
The system
(I.I.5)
P
(4.3), fix with
k = kI ,
and
by adding additional
with rates
k Z - k I > 0 ; call
{ ( [ A • t) } can be represented in terms
O b s e r v e that
~A c kI, t in the joint realization,
[A
A~
k Z , t
which yields
S
t~ T '
(4.3).
Hence
'
PX
is increasing in k .
If
31
k < k¢ ,
then
invariant,
Pk-- V k , l
so are the
( {0
is infected}) = 0 .
6Z P ~ , t ~ T,
is infected}) > 0 ,
this case.
whence
(3 .i) .
v I / 69 .
W i t h p k , k ¢ , PX and k~
Proposition.
2k - 2 pk--< 2 k _ 1 =
whence k¢ -> 1 ,
0
Thus
k+ > 2
Proof.
We
are translation v k,l = 69
If k > i¢ , then
Clearly the system is nonergodic in []
d e f i n e d a s in Proposition (4.1) ,
X-
and
k>Z,
=0 whence
@
k >I,
+_< k - 3 Pk k 1
X-
treat the basic case; the one-sided argument is similar, and will be
left as an exercise.
By duality, AA0
~(Rx
PX = P(TX,• = co)= where
and
The proof for the one-sided systems is analogous. +
(4.4)
6Z
and their limit v k , l "
In this case the system is ergodic by T h e o r e m vx, i({0
Since
,t-
Lk,t > 0
A0 A0 TX, 9 i s the h i t t i n g time of 9 for [ k , t '
Vt) ,
and RX, t and
L k,t
are defined
i
on
{'[X,)Z> t}
by A0 : x ~ It } '
Rk,t = max{x AX
Think of (It) Dk,t=
Lk,t : min{x
as a coalescing branching process.
A0 : x ~ It } "
Whenever
R X , t - L X , t > 0 , R k , t m o v e s one unit to the right at rate k ,
least one unit to the left at rate
1 .
one unit to the right at rate
Thus
creases by at least
1 .
1 at rate
Z ,
Lk,t
m o v e s one unit left at rate k ,
D t increases by
whenever
D t -> 1 .
1 at rate 3X , w he r e a s the process dies out at rate
PX -< P0(Xn -> 0
Yn)
anda_!t
,
1 .
1 at rate ZX , From value
0 ,
It follows that
at least
and deD t goes to
32
where
(Xn) i s a d i s c r e t e t i m e M a r k o v c h a i n o n t h e s t a t e s p a c e
{-1,0,1,
Z, . . . }
with transition probabilities
Px x+l
k - l+k
POI
Zk - l+Zk
P-I-I
=
i Px x-i - l + k
'
'
PO-I-
x >~ 1 ,
1 l+Zk
i
the t o t a l probability equation :
Consider
Vn)
P o ( X n _> 0
(4.5) =
Since
X n
Z__~X [Pl(Xn > 0 Vn) + PI(Xn = 0 for some n)Po(Xn ->0 I+ZX
i s a r a n d o m w a l k w h e n r e s t r i c t e d to
x ~ t ,
¥n)]
the famous gambler's ruin
formula implies that
PI (Xn = 0
S u b s t i t u t e in
(4.5)
for P X "
(4.6)
for s o m e
a n d s o l v e for
n)
I
- k
k > i
=
k-
I
P0(Xn >- 0 Vn) ,
the desired upper bound
[]
Problem.
D e r i v e t h e b o u n d s on
PX+ a n d
X .+
g i v e n in P r o p o s i t i o n ( 4 . 4 ) .
W e n o w t u r n t o o n e of t h e d e e p e s t r e s u l t s i n t h e t h e o r y o f p a r t i c l e s y s t e m s : t h e p e r m a n e n c e o f i n f e c t i o n for c o n t a c t s y s t e m s w i t h s u f f i c i e n t l y l a r g e no k n o w n p r o o f t h a t
X* < co w h i c h i s t r u l y e l e m e n t a r y ,
H o l l e y a n d L i g g e t t (1978)
comes the closest.
k .
There is
but a r e m a r k a b l e method of
We sketch their approach,
referring
t o t h e i r p a p e r for m o s t of t h e d e t a i l s .
(4.7)
Theorem.
With
PX ' X , ,
i
~I
whence
X, ~ Z,
and
+ X,
defined as in Proposition
i 4
PX - > ~ + ~
PX
Zk
k > Z ,
and +
I
[I
P~ ->g+ 4 7 - T
I
k>4
,
(4.1) ,
33
whence
k + < 4 The basic and one-sided cases are analogous,
Sketch of proof. former.
The idea is to find a translation invariant
[~({A : 0 ¢ A}) > 0 A ~ S0 .
and
~,t(A)
= P([~,t N A = @)
This clearly proves nonergodicity;
(4.8)
Vk,l({O
such that
is decreasing in t for all
in fact
is infected}) ~> 1 - ~M(0) > 0 .
For the remainder of the discussion notation.
~ = ~k
so w e discuss the
k
will be fixed, and often suppressed from the
By self-duality of the basic contact process
(cf. (3.5))
and
(i.i0) ,
(A) = E [ ~ ( E t A ) ] ¢t
It t h e r e f o r e s u f f i c e s to c h e c k t h a t d E[~0[~ ( [A) ] d-~
(4.9)
t
-< 0 =
Unfortunately, however,
VA
~ SO .
0
no product m e a s u r e
~0
satisfies
(4.9)
a renewal m e a s u r e w h i c h works provided
k
for all A .
There i__ss, The
is large enough. oo
renewal m e a s u r e
~f ~ ~
is determined by a probability density
f = (fk)k= 1
co
such that m =
~ kf k < co . k=l abilities given by
~f is translation invariant,
~f({A : A(x) = A(X+Yl) . . . . .
A(z) = 0 for all other
A(X+Yl+...+yn)
with cylinder prob-
= I,
z ~ [x,x+Yl+O..+yn])
n
= m -I
~ f 2,=i Y2,
The m e t h o d of H o l l e y and L i g g e t t i s to c h o o s e equality in case
(4.9)
A = [x,y]
for a r b i t r a r y
A with
for s o m e
x -~ y ,
~ = ~{ so c h o s e n .
(fk)
so t h a t
(4.9)
holds with
and t h e n to p r o v e t h e i n e q u a l i t y The a l l - i m p o r t a n t s e c o n d part of
34
the program is rather involved, and Liggett (1978). contact process k ¢ [ 0, n-l]
so w e will omit it, and refer the reader to Holley
To find the desired
f,
note that w h e n
grows one unit at either end with rate
recovers at rate
i.
k,
Thus, equality in
A = [ 0, n-l] , the while an infected site
(4. 9 ) is equivalent to the
equation n-I
[~b([0,n-l]
- {k}) - ~ ( [ 0 , n - 1 ] ) ]
k=0
(4.10)
=
k[~bc([0,n-1]) - ~ ( [ 0 , n ] ) ]
+ X[~a([0,n-1])
- ~([-l,n-l])]
.
co
Put
Fn
~
fk
Then
°
(4. i0 ) b e c o m e s
k : n+l (4.11)
ZkF n =
n-i ~
FkFn. k,
n -> 1
(F 0 =
i).
k:0
To
the
find
Fn ,
introduce the generating function
E(x) =
~ n=0
Fn xn .
(4.11)
is
equivalent to
z x(r(×)
- l) : x r Z ( x )
,
or
r ( x ) --
! F n = n!(2n) (n+l)!
O n e can solve for F to get k -> 2
.
Over
this
k - 4 k Z - Zkx
parameter
(Zk)-n
which
is s u m m a b l e
for
range, co
k Since
b ( { A : 0 ~ A}) = m -I ,
(4.1Z)
Problem.
0 (4.8)
yields the lower bound on
[]
PK "
S h o w that analogous computations for the one-sided systems give
(Note that + both the upper and lower bounds for Pk are precisely the s a m e as those for PZX " + + It is an intriguing and open question as to whether X, > ZX, , X, < Zk, , or rise to the inequality for
perhaps
X%+ = z k . . )
p~
w h i c h is stated in T h e o r e m
(4.7)
°
35
2X-2 .5
i
X,
2
3 X figure v.
•
.
'
o
7
1
,
-
-
•
.
.
.
.
.
7
.5
J
2
X~ 3
4
5
I
6
I
!
7 X
figure vi.
36
To s u m m a r i z e ,
we
h a v e seen that
pk= lim P(O ~ ~Z is increasing in k ,
0
x ' t ) = p(~ ' t ~
t--oo
equals
0
for k -< 1 ,
Vt)
and is strictly positive for k >-Z .
In
fact,
PX
is s a n d w i c h e d b e t w e e n the two curves s h o w n in figure v .
While we have
drawn
PX
to be continuous at X = k~ , there is no k n o w n rigorous basis for this.
The analogous graphs for the one-sided s y s t e m s are s h o w n in figure vi. Theorem
(4.7)
gives the best k n o w n upper b o u n d s for X%
and
k +% •
In
contrast, there is a technique for improving the lower b o u n d s of Proposition (4.4). We
illustrate this with our next result.
Proposition.
(4.13)
Let k,
and
k +, be the critical values for the basic and one-
sided contact s y s t e m s respectively.
k, > 1 + ~ - 7 -
Proof.
~ 1.16
6
Then
and
X+ > ~ *-
'
~
Z.41
W e derive the first b o u n d ; the s e c o n d is left as an exercise.
By self-
duality, it suffices to prove that 0 P ( T X , ] ~ = co) = 0 w h e n e v e r
Set
( ~ ( A ) = P ( T,A ..@ =~~ ).
and note that
time M a r k o v chain obtained by looking at Also, by translation invariance, (~({x, x+Z)}) --- (7(. -- .), etc.
(A)
ZX o(.) - I + ZA
(B)
~('') : ~
(c) (D)
1
o
1 +437 6
is a harmonic function forthe discrete
{(~X, t)} at its j u m p times
w e can write
or(x) -~ (~(.) ,
The following total probability equations are obtained
k
~(') +i-%--f ~(" "') ' 1 1 +zx
~('")-
2 3 + zx
T I, T Z , • • •
(~({x,x+l]) =- o('-) ,
o(..) ,
~('-')-
O b s e r v e next that
k -<
~(.)+
x
+
~
a(---)
1
~(" ") + T 7 - ~
x__ i +zk
~( . . . .
) '
2X
~(" - ") + % - - 7 - F
(~ is strongly subadditive:
~( .... ) "
37
o(A I U A Z) < O(Al) + (~(AZ) - o(A I A AZ) In f a c t ;
A I , A Z • S0
vI v1 (~(A I U A Z) - o ( A I) = ~o ( A I ) - g (A I U -A-z)
by d u a l i t y ,
= VI({A : A n A I= ]~, A n ( A ~ n A 2 ) / @ } ) -- vI({A : A n (AI~]Az) = 9, A n ( A I A A Z) / @ } ) _ v = _ v1 = ~ (A I D A Z) I(A2) o(A2) o(A I [3 AZ) . I n particular, (~(. . . . ) --< o(..) + (~(. -- .) - (~(.) and Substituting into
(C) and
(D) w e get the n e w inequalities
(C')
g ( . _ . ) _ < l - k ~(.) + X 1 + x ~
(D')
~(''') -< 3 - 2k
Z(l-X) ~(..)+
Nowif
0 < k<
I+437
--
(~(.... ) -< Zo(...) - (~(..) .
x o(..) + ]-7-% o(.-.),
1 ~(" -- ")
~
(= the positive root of 3 + k -
6
3k 2
0) --
the ;
positive combination : (k+Z) (3+k-3k Z) (A) + Zk (I+K) (3-Zk) (B)
+ 2xZ(l+k) (C') + 2kZ(3-Zk) (l+k) (D') yields (k+2)(3+k-3k Z) a ( - ) -< 2"k(3+k-3k Z) (~(.) ,
so that
~(.) must equal
0 .
This completes the proof•
W e remark that better
bounds can be obtained if one is willing to handle larger systems of inequalities. (4 14)
Problem.
Derive the bound
k+ > ~
by applying the same method to the
one-sided systems. (4.15)
Notes.
Contact processes were first studied systematically by Harris
(1974), although work on closely related systems,
especially in discrete time, had
been carried out by Soviet probabillsts for several years•
See especially
Dobrushin (1971), Stavskaya and Pyatetakli-Shapiro (1968), T o o m (1968), Vasilev (1969) and Vasilev et al. (1975).
[
Versions of Proposition (4.4) m a y be
found in Harris (1974) and Holley and Liggett (1975).
Permanence of contact
systems for large X was proved by Harris (1974) ; his method was based on comparison with discrete time systems and appeal to the percolation techniques of
38
Hammersley
(1959)
and T o o m
(1968).
The computations for Proposition (4.13) are
taken from Griffeath (1975).
5.
Contact systems : limit theorems in the nonergodic case. In this section w e study the limiting behavior of nonergodic contact systems.
{(~A)}
will be the basic system,
prescribed.
{(~:'A)}
the one-sided system,
Our first result is a "complete convergence theorem" for
unfortunately the method of proof only works for i > k +
with X {(~A)} ;
-
o
(5.1)
Theorem.
Let
be the basic (one-dimensional) contact system with + If k > k. (= the critical value for the one-sided system),
{(~$)}
infection parameter k . then for any
where
~ c ~ ,
= inf{t ~ T : ~t = 9 }
In particular,
Proof.
69
and
(= =
if no such
t exists).
v I are the only extreme invariant measures for {(~A)} .
It w i l l b e c o n v e n i e n t to e s t a b l i s h s o m e p r e l i m i n a r y r e s u l t s in t h e form o f t w o
lemmas. A
(5.Z)
Lemma.
If {(~t)}
so that v I / 6 9
is nonergodic,
$
then Vl(S0) = 0; also
v1 (5.3)
lira
sup
q
(A) =
0 ,
N--~ A : I A I = N so t h a t (5.4)
lim
sup
N--~
A:IAI=N
The s a m e r e s u l t s h o l d for
Sketch of proof.
{(It,A)}
If A ~ S O ,
the translates of A
A/9
have the s a m e
P(~
< =) =
.
,
then
Vl({A} ) c a n n o t be p o s i t i v e ,
Vl-probability.
therefore suffices to check that c = v I ({9}) = 0 .
since all
To s h o w Vl(S0) = 0 , it v1 Since ( ~ t ) is stationary,
39
Vl([-n,n]) = c +
-c
~A/@
A(
+ _~ /
= c+
[-n, n] )v I (dA)
~Z([-n, n])Vl(dA )
(l-c)~Z([-n,n])
•
v1 Let t--~
toget
c~
{[-n,n]) - c •
Nowlet
n--~
to force c = 0 .
The proof
of (5.3) is s o m e w h a t technical, so w e omit it, and refer the reader to Harris (1974). Property (5.4) is equivalent to (5.3) by self-duality. apply to the one-sided process.
(5.5)
Lemma.
For A ~
SO ,
[]
t < T~,
L t A = min {x: x (
Forany
x¢
Z,
(5.6)
=
LtA ~ -co
Proof.
RtA= max{x:
on
A Rt ~
and
P - a.s.
(y,O)
on
A ~} {T]~ =
•
by monotonicity and the definitions of L xt and
[L? ,
NtY(z) > 0 for s o m e
pathupfrom
~tA }
T ~x }
{t<
x R t , it remains to check the opposite inclusion. Then
x~
A ~ SO ,
~tx c S tz f]
Since
ETA},
x[- L tx 'RtJ
sZN
then for any
(5.7)
define
t~ T ,
Stx
+ If k > k ~ ,
Very similar arguments
y c Zd .
If y = x ,
Suppose then
Z x x z ~ ~t N [L t , Rt] •
z ~ ~t "
to (z,t) intersects a p a t h u p f r o m
(x,O)
If y < x , to (Lt,t) .
thena By
following the latter path up to the intersection point, and then following the former, w e get a path up from
(x,0)
applies if y > x by using
to (z,t) . R xt instead.
Hence
x
z ~ St .
The s a m e argument
This completes the proof of (5.6).
We
remark that the nearest neighbor nature of the infection m e c h a n i s m is crucial in constructing the composite path, for otherwise paths can "jump over one another. " Turning to the proof of (5.7), w e introduce
A
•N = min{t ~ T : For N -> IAI , A TN < =
I~AI
= N}
(= co if no such
t exists),
N -> 1 .
since ]~ is a trap, a standard M a r k o v process argument s h o w s that
P - a.s.
on
A {T~=
~ } •
Hence
40
P(lim inf RtA < co, ~ =
= 7's~
co)
I~IB
(0,~o) B:
A
t , T~=~) ~ ds, ~ A A : B)P(liminfRB<~t~oo TN
N P(TN =
To get the result for R At '
(5.8)
lim
we check
sup
B:IBI:N
N---
that
B R t
P(liminf
B T9=~)=
0
t-=
> R t+, B = the right hand edge of the one-sided process defined o n the s a m e R tB -
Now
substructure by using only positive-oriented arrows, H e n c e w e n e e d only c h e c k condition processes
R+'B-t
(for {(~+,A)}) t
+ oo
P - a.s.
(5.8)
on
completes the proof.
Proof of T h e o r e m A~
•
(5.1) .
on
{T;' B = co } C
for the one-sided system.
+,B {T 9 = co }
{4
= o: } .
For those
so an application of
(5.4)
[]
The first step is to s h o w that for each
B ~ S - {9} ,
SO ,
(5.9) B
Note that if additivity,
p(
.A_= EZ n A f o r a l l large t I
p([Bn
T9 :
while for
= co)=
choosing soonas
= ,
x~
then B~ S
x
T9 =o~
x ~ B •
If
B(
--i S0
this follows
= co) = 1 by
(5.4) . (5.6)
so that
x = ~ , T)~
w e see from
A C [R~,LI] .
Applying
(5.7), w e obtain
Thus if
= co ,
then
that [ B N A = ~ Z f] A (5.9) •
Next,
write
(5.1o)
Suppose we can show (5.11)
T h e n letting t ~
lira
in
p(~
from
we have
lira P(T 9 N ~ B
for some
~--~)
na
= 91
(5.10), and using
lim ~0 ( A ) = P(
= ~ ) = ~o
(a)
.
(5.9) ,
< ~)~0]~(A) + p(
= o~)~0 (A) .
The desired c o n v e r g e n c e theorem follows by inclusion-exclusion.
It therefore
as
41
suffices to check
(5.12)
(5.11), or equivalently
lim
P($
z
n A=
~,
~
> t) = P ( T @ =
~)¢
Vl (A)
.
t~oo
For
s < t,
C
-> P ( T ~ >
s)¢tZ_s(A)
•
So lim inf P(~+~ n A = 9 ,
> s) z PC
> s)e
CA) •
-< s) >- P(
-< s)~0
t ~
Similarly,
lim inf P(
f] A = @,
(A) .
t~Qo
But we know t h a t lira
lira t~,
P(~
z
~o ( A ) ;
Cl A = . g ,
Vl
~o (A) ,
so
> s ) = P(
> s)~o
(A) .
t--~
Let L =
lira
lira
s ~
P(~ZNA=
g,
Tt~ > s) .
Then L = P ( T ~ = ~ ) ~ 0 V l ( A ) ,
so
t~m
to g e t (5.1Z) a n d f i n i s h the proof we n e e d
L=
lira P ( ~ " Cl A = , g ,
.B > t ) .
t ~
But t h i s i s c l e a r , 0 -<
since
lira S --~
__<
lim
lira [ P ( ~ Z N A = @, ¢
> S ) - P(~Zf] A =
@, ¢
> t)]
t--°° P(s < ~
< ~) = 0 .
[]
S--O~
Using
of the s a m e observations one can prove a corresponding
some
"complete pointwise ergodic theorem" for
{(~A)} . L
(5.13) k •
A
Theorem.
Let
{(~t)}
+ If k > k~ , then for any I
be the basic contact system
(d = I) with parameter
~ ~ • , fE C ,
t
Y f0 fC~s~)ds- fC~l as t--~ - f fdv as t--~ S
P-
a.s.
on
{Y~ < =} ,
P- a.s. on
{~-- °}
42
Proof.
The first assertion is obvious.
To prove the second, w e proceed as for
Theorem (Z.9).
Problem (I.l.10) applies to v I , by Theorem (5.1) and L e m m a vI Thus the stationary process (It) is Birkhoff ergodic, and so
(5.2).
p(~ ft f(~sv1) d s - - f 0
fdVl)= 1
Fix B ~ S , f ~ $ = {cylinder functions} . P(T~=~o)=I
forany
A~
So,
p(f(~sB)= f(~l)
Defining
the fact that
together imply
for all large s I T ~ =
Tf<~
o~)= I .
P - a.s.
on
{¢=~}
.
{T7 = co } , w e can argue just as in the proof of Theorem (Z.9) to get
the desired convergence w h e n f~ C
Property (5.9),
and v(So~)= 1
7f= m i n { t : f(%sB)= f(~l)},
Thus , on
Vf ~ LI(vl)
S
are straightforward.
~ = 6B , f ~ $ .
The extensions to general ~
and
[]
Next, w e mention an application of the graphical representation which is based on the same observation that w a s used in the proof of (5.6). proves that the basic contact system
{(~A)}
Harris (1978)
satisfies a more general collection of
correlation inequalities than those in Theorem (Z. 17), namely : (5.14)
P(~An
A,B,C~D~ beautiful
(5.15)
S,
C=
t~ T •
]~, ~BF] D =
Hethengoes
9 ) - > cA(c)~tB(D)
onto showthat
(5.14) has a simple but
consequence.
Theorem.
Let
{(~A)}
be a nonergodic basic contact system
(d = I) .
Then lim inf t~oD
Proof.
o
P(O c ~ t ) > 0 .
If the system is nonergodic, then
s
0
= %,i(0 is infected) = P(T@ : co) > 0 ,
and Z P(O ~ ~ ) =
Let Z + = {0,1,Z, • "" } •
0 P ( T ~ > t ) -> a
Vt
.
By s y m m e t r y
P(O ( ~tZ + ) = P ( ~ O n Z+ / ~ )
s -> ~-
Vt
43
Positive taking
correlation A= D=
of
Z+ ,
{ ~ A N C / ~f}
C = B = {0} ,
and
{~B fl D / J~}
is equivalent
to
(5.14) ;
we get Z
Z+ 0 Z+ s ~t ' ~ n /~)->--~--
P(O¢
Z+ N t (0) > 0
S i n c e p a t h s c a n n o t jump o v e r o n e a n o t h e r , 0 i m p l y N t (0) > 0 . Hence
lira i n f
way down to the critical
We conclude and one-sided
and
Theorem
(5.1)
The present result is of interest constant.
this section
one-dimensional
lastthree theorems hold forthe for any
+ k > k. ,
We remark that for
P(O ~ I t ) _ s 2 •
. 0 + Nt (Z)
> 0 together
Z P ( 0 ~ [+~) > i _
lira i n f
as desired.
Yt
yields because
[]
with a brief survey of further results contact •
+,A}
i(%k,t)
systems. .
First,
Intact,
for the basic
we note that none of the
if A ~
S O then
~UAPt--6)~
k : in the nonergodie case the set of infected sites wanders off to the right
if it does not die out.
By taking A
to be a countable disjoint union of larger and
larger blocks which are farther and farther apart, and by taking k > k +, , get examples
where
along one subsequence Liggett only
all the
it applies
6f{ and
(1978)
6APt
does not converge
and to
69
as
t ~
one
, but rather converges
can
to
v1
along another.
has shown that both the basic and one-sided
systems
v I as extreme invariant measures for al__/lparameter values
convergence to v I from "nice" initial measures
Z
have
k •
Also,
takes place in both systems for
all parameter values, as a special case of a result to be mentioned in the next section.
The questions of convergence and pointwise ergodicity for the basic
systems with X
just above
(5.16)
Theorem
Notes.
X. , and starting from arbitrary Z ~ ~ , remain open.
(5.1) is proved in Griffeath (19T8a).
A similar discrete
time result w a s obtained by Vasilev (1969), using the contour method of percolation theory. cation).
The proof of (5.1) which w e give here is due to Liggett (private c o m m u n i There is a sketch of this proof in the introduction of Liggett (1978) ; it has
the advantage of leading to (a) Liggett's theorem that ~
is one-dimensional in the
44
nonergodic case,
6.
and
(b) T h e o r e m
(5.13)
(which is taken from Griffeath (1979)).
C o n t a c t s y s t e m s i n several dimensions. There are m a n y w a y s to generalize the basic contagion model studied in the
last section. d >- 1 .
consider here only the most natural generalization to Z d ,
By the basic
system on i >- i,
We
Zd
and
with
d-dimensional
contact system w e m e a n the lineal proximity
Ix -: {0,i, .-- ' Zd} , k 0 ,x -: I '
C i , x = { x , y i}
for i -> 1 ' where
mediately adjacent to site x .
In words,
C 0 ,x a @ , k i , x =- k
the Yi are the
Zd
for
sites im-
infected particles recover at rate 1 ,
while infection takes place at a rate proportional to the n u m b e r of infected neighbors.
(x
and
y
in Z d
are neighbors if Ix-yl = 1 .)
constant for the rate of infection is given by the parameter Less is k n o w n about several-dimensional of a critical k d case.
in each dimension
d
The proportionality
X .
contact systems,
but the existence
can be proved just as in the one-dimensional
In fact, using s o m e of the methods already discussed,
one obtains the
following results.
(6.1)
Theorem.
parameter
k ,
d If X~ = S U p { X
d k > k~ ,
Let and set
PX =
Vl( 0
d-dimensional
is infected).
Then
PX
contact system with is increasing in k •
: PX = 0} , then the system is ergodic for k < k
,
nonergodic for
and
(6.g)
Proof.
{(~A t)} be the basic
I d < g gd-i -< k~ The argument for everything except
(6.2)
is very similar to the proof of
Proposition (4.1), so w e omit it.
To get the left hand inequality in (6.Z),
the m et ho d of Proposition (4.13).
Namely,
suffices to prove that A g(A) = P(Tx,j~ = co) ,
(A)
Zdk g({0}) = l + Z d k
(B)
~({0, el})=
since
0 P ( T k , 9 = ~) = 0 w h e n e v e r and note that
°(t0'elJ)[l
{(~A,t )},~ 1 k < "Zd-i
is self-dual, "
it
Let
(~ satisfies the total probability equations
' Zd
l+(Zd-l)kl
apply
a({O})+
I+(Zd-I)XX
~, (~({0,el,eZ]) j=z
45
(Here w e have m a d e use of the translation invariance of subadditivity,
a •)
Also, by strong
so from
(B) w e get
(l-(Zd-l)i) (~({0, el} ) -< (l-(Zd-l)k) or({0}) If k <
1
Zd-i '
then
~({0, el} ) -< (~({0}) . ZdX (5({0}) -< l + Z d k
a({0}) = o ,
which implies
Substituting into (A) , w e find that
~({0})
the desired result.
The right hand bound in (6.Z) is
obtained by comparison with the one-dimensional systems. 0 stochastic process ( I t ) on Z by 0 d t = {x ~ Z : ~ x k = x for s o m e k--i O n e can check that if [ O = A , a 0 at x f l i p s t o a case
Namely,
0 (xI, ... ,Xd) ~ ~k t }
then a i flips to a 0 with rate at most
dklAn
1 with rate at least
d = Z will help m a k e this clear.)
{x-l,x+l} I •
Thus the contagion in
than that in the basic one-dimensional system with parameter {{O = )~} = { ~ , t
= )~ } '
(6.3)
1 , while
( A picture of the (~O)
di .
is stronger Since
T h e o r e m (4.7) yields
,,g In particular,
define a
Zdk
- 2- +
k ->
k.d < 2
Problem.
By p u s h i n g t h e " s t r o n g subadditivity m e t h o d " f a r t h e r ,
show that
Z X. -> .359.
Virtually all of the k n o w n dimension-independent results for nonergodic contact systems are due to Harris (1976, 1978) ; unfortunately his methods require regularity assumptions on the initial state. (n= 0,I, ...) if A~] b n ( X ) / 9 it is n - d e n s e for s o m e
lira n~ Note that
6A
n •
Say that A e
for all x ~ Z d
A measure
~ ~ ~
So is n-dense
(bn(X) as in (I.l)).
A
is dense if
is called regular if
sup [ ~ ( b n ( X ) ) - [L(0~})] : 0 x~ Z d
is regular if A
is dense,
and that any translation invariant it is
46
regular.
The convergence theorem of Harris states that for any parameter value
if {([A)]
is a basic
d-dimensional
contact system
k ,
(or any of a large class of
contact systems which includes the one-sided system on
Z) , and if ~ is
regular, then pt
-~({#})6~+(l-~({~})v
I
as
t-~
.
This implies that the only translation invariant equilibria are mixtures of vI ,
but it is not k n o w n whether there are additional nontranslation invariant
equilibria w h e n dimension
d -> Z .
d -> Z
very large k . on
6]~ and
Zd
Pointwise ergodic convergence to v I has been proved in
only for initial measures
6A
with
A
dense,
and then only for
Finally, there is a growth rate theorem : for basic contact systems
with sufficiently large infection rates
k :
0
l~x,tl
P(limt_o~inf - - t
0
> 0 I T~ = ~) = i .
O n e can s h o w that the growth is of order at most open for d -> Z .
(6.4)
Notes.
(6.Z)
but the exact order remains
This concludes our discussion of contact processes.
The lower b o u n d in (6.Z)
Liggett (19 ?5).
td ,
is due to Harris (1974)
It improves a result of Dobrushln
is from Holley and Liggett (1978).
in Griffeath (1975).
(1971).
Problem (6.3)
and Holley and
The upper bound in is based on a computation
The rest of the results mentioned in this section m a y be found
in Harris (1974, 1976,
1978), except for s o m e refinements in Griffeath (1978).
Similar techniques were applied to discrete time systems by Vasershtein and Leontovich
?.
(1970).
Voter models. This section is devoted to the study of lineal proximity systems with the
property that
IC i, xl = 1 for all i ( I x ,
the so-called voter models.
According to
(Z.IZ), such a system has flip rates which can be written in the form
Cx(A) = kxA(X) + (I-ZA(x))
~ z ( A
(Xz, x -> 0 ).
k z,x
To simplify matters , w e will treat only translation invariant voter
47
models,
w h o s e f l i p r a t e s c a n b e w r i t t e n i n t h e n o r m a l i z e d form
(7.1)
Cx(A) = k[i(x) + (I-ZA(x))
for some probability density
~ z~ A
p = (Pz; z ~ Z d) and
"voter model, " w e think of the sites of Z d
is influenced by voter y
k > 0 .
, To explain the n a m e
as occupied by persons w h o are either
in favor of or opposed to some proposition (say "voter" at x
pz_x ]
1 = "for" , 0 = "against" ).
with weight
Py-x '
The
and changes opinion
at a rate proportional to the s u m of weights of voters with the opposite opinion. particular, the "total consensus" states
6@
and
In
6zd are both traps for the system.
Since w e are interested in asymptotic behavior of the model,
and the factor k
may
be removed by a change of time scale, w e will a s s u m e henceforth that k = I . foremost question for the voter models is : independence, " i.e.
a product measure
The
Starting from a state of "individual Z(~ , does the interaction lead to
"eventual unanimity" or not? The dual systems for voter models are coalescing branching systems in which each branching tries to replace a particle by another single particle. these are coalescinq random walks.
Particles attempt to execute independent
continuous time random walks with mean-I density
In other words,
exponential holding times and transition
p , but coalesce upon collision.
In particular, the one-particle dual
process is merely a random walk with density
p .
We
say that p is recurrent or
transient according to which property this random walk enjoys.
The basic
d-dimensional voter model is the system such that 1 Pz = z-~ =
i.e.
Izl = l
0
otherwise ,
the voter model whose one particle dual is simple
d-dimensional --
Given a density that if (XtI) and
then
(
times.) if ~
-
p , define the symmetrization (XZ)
-p of p by
Pz -
Pz
random walk. +
P-z
Z
are independent continuous time walks with density
) is a random walk with density
Note p ,
-p ( a n d m e a n ~- e x p o n e n t i a l h o l d i n g
The f u n d a m e n t a l r e s u l t for v o t e r m o d e l s i s t h a t e v e n t u a l u n a n i m i t y o c c u r s
is recurrent,
but disagreement
persists
if p
is transient.
Thus the basic
48
voter model b eh av es one w a y in dimensions one and two, dimension three or
more.
(7.Z)
Let
but entirely differently in
These assertions are m a d e precise as follows.
A Theorem.
with flip rates of p .
{(It)}
(7.1) for s o m e irreducible density
If -p is recurrent,
Zd
be the (translation invariant) voter model on p .
Let ~
be the symmetrization
then
pt (7.3)
~
for any initial measure
-- (I- 8) 6)~ + ~6zd [, such that ~
as
t~
({z}) ~ 1 - ~ .
If p
is transient,
then
corresponding to each ~ c (0, I) there is a distinct translation invariant equilibrium v v 8 , with ~ 8 ( { z } ) -= I - (~ butno___tta mixture of 6}~ and 6zd, suchthat
(?.4)
~pt
Moreover,
Proof.
each
v8
as
t -~o
.
v(} is mixing with respect to translations in Z d .
If ~[~({z}) = I - ~
for all z c Z d ,
i /kx Ct~({X}) = E[¢Z(~ t )] = 1 - @
for all t ( T ,
one particle dual is a r a n d o m walk.)
lim
P([t~(x)/
then by since
To prove
(I.I0),
iX ~t = {z}
(?.3)
[~(y)} = 0
for s o m e
z .
(The
it suffices to s h o w that
~
Vx,y
Zd .
t~co
E q u i v a l e n t l y we c h e c k t h a t (7.5)
lim t~co
~t~({x,y})=
i- e
Vx,y
A key fact about coalescing
random walks is that
t~
I if A / ~ ,
, and always at least
Nt A.
so that
¢ Zd .
= I =
t *i i s
nonincreasing
as
1 exists
P - a.s.
lim t~oo
Thus A{X, ~({x,y))= AEL~[r(~t Y})]
(7.6) "1
A ~{X,y}
= (-8) P(Nt Assume
-p recurrent.
density
p until a collision occurs,
Let t~oo
in (?.6)
Since
to get
(It{x' Y})
(?.5).
A
= i) + E L ~
(It
~
t{x,y}
= 2]
acts as two independent r a n d o m walks with
w e have Next,
~A(X,y}),
AP(I'JQo .'h.{X, y} = I) = 1
assume
~
transient.
for all x , y ( zd . Letting
t--~
49 in
(1.11), AA
~0 0)N ~ lira ~t (A) = ~[(i] t~co so tx0 pt
converges
to a measure
v0
such that AA
v0 (7.7)
Clearly
~
v0
To s e e t h a t
is a translation v0
~[(I-0)
(A) =
invariant
is not a mixture of
d o e s no_._~th o l d f o r ~ = ~0"
]
equilibrium 6~f a n d
But f o r
vo
N
such that
6zd
^ ^ {x, y}
(7.5)
^ ^ {~, y} = i)+ (I-0)ZP(N
(i-0)- 0(I-0) P ( N ~
9 ( ~ { x , y}
0 ~ (0,i) and
( { z } ) =- 1 - 0 •
we need only check that
,, ^{x, y}
provided
vo
x/y,
({x,y})= (I-0) P(N
=
~
= Z) > 0 .
= Z)
= Z) / 1 - 0
This last probability is positive
since p is transient.
To finish the proof, it remains only to s h o w that v 0 is
spatially mixing, i.e.
for each
(7.8)
lim
v0
[9
B,C
~ S O - {)~} ,
(B U (z+C)) - ~V0(B)~
v 0
(C)] = 0
]zl-~ By duality, the quantity in brackets equals AB C ~[(I_o)~B U (z+C) N ] ] E[(I-0) N ~ ]
E[(1-O)
Recall from Theorem (Z.17) that copies of
^B
(~t) and
~c
(
--
(~B U C) can be constructed from independent
) in such a w a y that
u
if
~sn~s
--
For the remainder of the proof w e will be referring to that construction. Thus w e AB U C AB AC can assume that N = N + N if the two independent processes never interact.
Hence
50
ve
[~p
v8 (BU C)-¢p -< P( -<
N
~
by
is transient,
z+C,
(7.9)
we get
Problem.
/ f~
B
x~
t )
C
?(~x,y}
(T.8),
for s o m e
A A {x, y} P(N = 1)
~
xe
Since p
v8 (B)cp (C)I
ll-0
_--
as ly-xl
Hence,
oo
and the proof is f i n i s h e d .
replacing
C
[]
Are there one-dimensional translation invariant voter models with
equilibria other than
6~
and
6zd
?
Holley and Liggett (1975) discuss voter models in more detail.
Letting
e
denote the set of extreme invariant measures for a given irreducible model, they prove ~ge: {6@, 6zd} is transient. it here.
if ~ is recurrent, while ~ge : {v 8 , 0-< e -< I}
The argument for the recurrent case is simple enough that w e can give
Namely,
if b ¢ ~9 then using duality,
~ b ( x ) = ~t~(x)= where
~ Pt(x,y)~(y) y~ Z d
Pt(X, y) = P ( [ ~ = y ) .
particle random walk. Thus
(7.3)
when
applies,
The p r o o f t h a t
Thus
x(
~(x)
Z
t~ T
i s a h a r m o n i c f u n c t i o n for t h e o n e
By t h e C h o q u e t - D e n y t h e o r e m so that
Zd
~Z(x)
is a constant function.
is a mixture of the e x t r e m e m e a s u r e s
~9e : {v 0 , 0 -< 0 _< 1}
5,0 a n d
6 Zd "
in the t r a n s i e n t c a s e is one of the tour de
f o r c e s o f t h e t h e o r y o f p a r t i c l e s y s t e m s ; w e r e f e r t h e r e a d e r to H o l l e y a n d L i g g e t t (1975).
In b o t h t h e r e c u r r e n t and t r a n s i e n t c a s e s ,
s u f f i c i e n t c o n d i t i o n s for an a r b i t r a r y a given invariant measure.
b ~ ~
In p a r t i c u l a r ,
to b e l o n g t o t h e d o m a i n of a t t r a c t / o n o f t h e y s h o w that if ~
is any translation invariant ergodic initial measure, 8 = 1 - ~(0)
.
In a d d i t i o n ,
they a l s o give n e c e s s a r y and
then
is t r a n s i e n t and
[~pt~v 0 ,
where
they treat nontranslation invariant voter models,
where the dual systems are coalescing Markov chains. The q u a l i t a t i v e d i f f e r e n c e b e t w e e n t h e r e c u r r e n t a n d t r a n s i e n t v o t e r m o d e l s l e a d s to d i f f e r e n t s o r t s o f q u e s t i o n s for t h e t w o c a s e s .
When ~
is recurrent,
s e e k s t o u n d e r s t a n d t h e i m p l i c a t i o n s o f c o n v e r g e n c e t o a m i x t u r e of In t h e r e c u r r e n t c a s e c l u s t e r i n g t a k e s p l a c e ,
6~
and
one
6zd ,
so that interest centers on cluster
51
description.
Given
A c S ,
be connected by a path in Z d
say that x
and
y
are in the same cluster if they can
w h o s e vertices are either entirely in A
Ac .
Thus, the clusters of configuration
Ac .
O n e relevant quantity for systems which cluster is the asymptotic m e a n
cluster size.
Let C(A) , A ~ S ,
C(A) =
lie n--~
A
or entirely in
are the connected components of A
or
be given by
(Zn) d l{clusters of A
in bn(0)} I
provided the limit exists (undefined otherwise) •
For the one-dimensional basic ~8 Z8 ' the asymptotic growth of C(~ t ) can be derived
voter model starting from explicitly.
First w e need a general result which states that mixing is preserved by
local additive systems at any time to the limit as
t~
t < ~o .
, as can be seen from voter models in the recurrent case.
(7.10)
Lemma.
{(~A)}
the additive syatem induced by @ .
mixing for each
Proof.
Fix
Note that this fact does not carry over
Let @
be a local percolation substructure which satisfies If ~ ~ ~
~pt
is mixing, then
(1.5) , is
t~ T .
B,C
~ S O , t ( T and a mixing measure
~ •
By duality w e need to
show
lie
u (z+C))]
_ A
B
AEL~
(gt
I = 0
Izl--" To do this w e use the construction from the proof of Theorem and
/k
PZ
be independent copies of ~ .
translate of ~Z Z "
by
z ~ Zd .
Note that
with
Define
= z +
L as in (I.Z.6) .
Now
.
(Z. 6).
/k z
.'k
In addition, let ~Z = z + ~Z (~B)
in terms of ~I and
Introduce
m a k e a copy of
~L = m i n { t : d( ([%B U (z+C))
let ~l
be the
~tz + C
in terms of
'~t
'
by letting the flow
A
which starts from B use
Thus,
/~Z
@i while the flow starting from
z + C uses @Z
until T L
A
and
@i thereafter.
~[~(~B)~AZ(~t Z
TL > t .
With this representation
+C)] = AE[~ ~ ( < ) ] A BE[~p(~ t-Az+C)]
and ~ B U ( z + C ) = ~tBU Az+C~t
Thus the above absolute difference is majorized by A
AB
E[¢b([ t U (z
+~G))
-
A
Z
k(~'B)¢~(z+~'tC)] + P(TL < t)
if
52
As
Iz] ~
, the first term tends to 0 since
tends to 0 b e c a u s e
(7.ii)
P
Since
is mixing, and the second term
does not have influence from ~
[]
A
Theorem.
Let
lim t~ ~
Proof.
~
Say t h a t
{(~t)}
be the basic voter model on
~.0 Pt - a.s.
q-i-
1
A h a s an e d g e at
x +~- ,
Ac S ,
l{edges of A
(by Lemma (7.10))
D
o ~
(0,1)
n--~ vo
C(l t
1 .
if A(x) / A(x+l) .
Birkhoff's theorem yields
1
h a s an e d g e at ~- )
Since V0
in [-n, n] } pt
has a positive
,
Zn
= C([t
I {edges of It~0
) = [P([t
Z,
I {clusters of A
in [-n,n]} I by at most
lira
It f o l l o w s t h a t
xe
gO [{edges of It in [-n,n] }[ VO Zn = P(~t
density of edges for
0 e (0, i) ,
in P-probability.
ZO (1-0)
Because of the linear nature of Z ,
differs from
For
g0 C(~ t )
VOPt i n h e r i t s m i x i n g from VO
lira n~
Z •
Vo
Vo
)
in [-n,n]}l
(0) / [ t
v 0
(1))] - 1 0
pt
- a.s.
Computations
s i m i l a r to s o m e from t h e proof of Theorem (7. Z) y i e l d P([t
~0
~0 (0)/ It (I)) = Z [ P ( 0 / It
) - P([t
n {0,i} = ¢f)]
,, ^ { 0 , i}
: Z[(l-8) - ((I-0) - O ( 1 - O ) P ( N t
-- z))]
~{0,I) = Z0(I-8)P(N t
= Z)
The l a s t p r o b a b i l i t y is t h e p r o b a b i l i t y t h a t a c o n t i n u o u s t i m e s i m p l e r a n d o m w a l k 1
w i t h m e a n - ~-
holding times stays positive until time
t g i v e n t h a t it s t a r t s at
U s i n g the r e f l e c t i o n p r i n c i p l e and t h e l o c a l c e n t r a l l i m i t t h e o r e m , A A {0.1)
P (N t
The desired result follows.
1
= Z)
[]
dnt
as
t ~co
we h a v e
1 .
53
When
~
is transient, interest centers on the equilibria v 8 ,
for the voter model.
Given a translation invariant measure
o ~ (o,I),
b ~ N , let
~
be
-distributed, and set
(C(x) - E[£ (x)]) Sn(~)
=
x ~ bn(0 )
is said to have w e a k correlations if lira
n~co and s t r o n g
Var (Sn(~)) < co , nd
correlations i f Var (Sn(~)) d n
lim n--~
(For reasonable measures
M
the above limit exists. ) Product measures, and more
generally, measures with exponentially decaying correlations have w e a k correlations.
For this class one can prove a central limit theorem of the usual sort :
n - d / Z Sn(~) converges in distribution to a m e a n - 0 normal random variable. Thus, for example, the unique equilibrium v of any translation invariant extralineal additive system satisfies this central limit theorem, by virtue of Theorem (Z. 6). O n e of the most interesting properties of the v , 8 voter model is that they have strong correlations.
~ c (0, I) , for a "transient" We
prove this for the basic
voter model on Z 3
(7.1Z)
Theorem.
Vs.distributed,
Let
{(~A)} be the basic 3-dimensional voter model.
n--~
at
Var(Sn(~)) 5 n
3y8(1-~) -
]' f
(¥ ~ .65046Z67) , and
dudv
4n U,V
~ BI(0)
Y is the probability that simple random walk on Z 3
returns to 0
lu-v]
BI(0) is the cube of side Z in R 3 centered
The familiar formula for the variance of a s u m yields
Var(Sn(~)) =
'
starting at 0 never
O.
Proof.
is
Q ~ (0, I) , then
lim
where
If ~
~, ~ [E[~(x)~(y)] - E[~(x)] E[~(y)] ] x , y ~ bn(0 )
54
For
x/y
we compute:
E l i (x) [ (y)] - E[[ (x)] E[[ (y)] E[(l-£ (x))(I-£ (y))] - E[(I-~ (x))] E[(l-~ (y))]
A.A{X,y}
= E/N
]
(1-0) g
-
~,~ ~ { x , y }
= (l-u)~(l~
= i)) - (i-0) z
,,., { x , y } O (I-O)P(N = i) .
=
For x : y ,
A ~ {x,y}
= i) + ( I - 0 ) Z ( I - P ( N
E[[ (x) ~ (y)] - E[[(x)] E[[(y)] : 0(I-0) •
Thus,
A A {x,y}
Var(Sn(%))= 0(l-0)[(Zn)3 + A A {x, y}
Recall that P ( N
~Yx
x
;
P(N
b~n(
O)
Y
= I) is simply the probability that a random walk governed by
and starting from x-y • Z 3 ever hits the origin. voter model,
= I)]
Since
{([A)} is the basic
~ = p , and this probability is k n o w n to be asymptotically A A{X, y} P(N = 1)~
(7.13)
3Y
1
4?7
Ix-y I
as
Ix-yl-
Therefore,
Var(Sn(~)) 3yO(I-O) n-5 ~yx b~n(O) 5 ~-" 47r n
x
M a k e the change of variables u = xn' Var(Sn(~)) n
5
V=n Y
;y
to get
3¥ 0(i-0) n-6 --
1
t x-y ]
1 u, v ~ BI(0)
lu-vl
"
The right side is a Riemann
approximationto the desired integral.
are left to the reader.
[]
A more careful analysis of v 8
Further details
leads to a central limit theorem in spite of the strong
correlations : it can be proved that n - 5 / Z Sn(~) converges in distribution to a normal variable.
An even more interesting development deals with the
"macroscopic dependency structure" of ~ . s u m of side Zn centered at Bkn for some
Define Sn(~) in terms of the block k ~ 0 . Then
S n and
S n have an
55
asymptotic non-zero correlation as
n ~co
if ~
See Bramson and Griffeath (1978a)
is "renormalized" properly.
.
This leads to a limiting field ~co for more on
renormalizing the voter model.
(?.14)
Notes.
Voter models were studied independently by Clifford and Sudbury
(1973) and Holley and Liggett (1975).
Clifford and Sudbury discovered the
qualitative dichotomy between the recurrent and transient cases, and Liggett first determined the structure of ~ •
Theorem
whereas Holley
(7.11) is from Bramson and
Griffeath (1978b) ; nothing is k n o w n about the rate of clustering w h e n R. Arratia supplied the proof of L e m m a
(?.I0) (private communication).
d = Z . A proof of
the central limit theorem for random fields with exponentially decaying correlations m a y be found in M a l y s h e v (1978a).
See D a w s o n
Fleischmann
(1975).
Theorem
(1978), D a w s o n
and Ivanoff (19Z8), Durrett (1978)and
(1978) for related results in other contexts.
random walks used in this section (e.g.
8.
(Z.IZ) is due to Bramson and Griffeath
The asymptotics for
(7.13)) are derived by Spitzer (1976).
Biased voter models. The voter models of the previous section were symmetric in O's and
since they satisfied
Cx(A ) = Cx(A c) .
called "biased voter models. " favors
Similar systems with a uniform asymmetry are
Without loss of generality w e a s s u m e that the bias
l's , and define the biased voter model on
probability density
p to be the spin system
"against" "against. "
and
y
is
to the basic cases,
with parameter
k > 1 and
with flip rates
~ zc A
Pz-x
is influenced by voter y
"for", but only with weight
For simplicity,
Zd
{(~A)}
Cx(A) = A(x) + (k - (l+k)A(x)) In this model the voter at x
l's,
with weight
Py-x
if x
is
k Py-x
if x
"for" and
y
is is
throughout the rest of this section w e restrict attention
where 1 Pz : ~
Izi : I
The percolation substructure for {(~A)}
(Pz = 0
otherwise. )
m a y be described schematically as:
56
x 6 <
x+z
x <
x+z
at rate
1 -Zd
at rate
k-I Zd
(Izl --
Thus t h e dual s y s t e m
{(~A)}
is a coalescing branching s y s t e m with a r a n d o m w a l k
part and a nearest neighbor branching part : P x
x+z >
6
1)
has
I -ad
at rate
(Izl = I) x
x+z
W e now s h o w how
A A
{(~t )}
.
k-I
at r a t e
Zd
may be u s e d to g a i n i n f o r m a t i o n a b o u t t h e e q u i l i b r i a for
{(etA)}. (8.1)
Theorem.
The only extreme invariant m e a s u r e s for the basic
biased voter m o d e l are
Proof.
We
lythat
~(A)=
69
and
6zd .
need to s h o w that if c
that M t = ~ ( ~ A )
whenever
d-dimensional
~ ~ $ , then ~ = c 6 9
A/~,
for s o m e constant
is a martingale for given
+ (l-C)6zd , c •
Todo
~ ~ ~9 , A ~ S 0 ,
or equivalent
so, observe
since
E[Mt] = ~ogPt(A)= ~oIa(A)= M 0 • Clearly
M t is b o u n d e d ,
soif
A ~(A,A')=
wA m i n { t : ~t
O
A'
} is finite with
/k
P-probability one for A / @ , then by the martingale stopping theorem a n d monotonicity of
{(~A)} ,
~g(A) = M0 = E[~(~Q(A,A,)) Reversing the roles of A
and
A'
] --<
w e see that ~
is constant on
S O - {)~ } .
It therefore remains only to c h e c k that
A AA P(~t
O
A'
for s o m e
t)=
I
VA,A'
~ SO
Now it is q u i t e c l e a r t h a t ~.~ 0 (~t D A
for s o m e
t) > 0
VA' ~ S 0 ,
{)Z}
57
since the r a n d o m w a l k and branching m e c h a n i s m s from
{0} .
m a k e a b o x covering
A'
By monotonicity and a standard M a r k o v process argument,
accessible
it therefore
suffices to s h o w
P(0 ~ EtA
for arbitrarily large t) : i
VA
~ S O - {]~}
This last property is verified by finding a recurrent M a r k o v chain that X t C
~?
for all t .
To define
(Xt) ,
w e start at s o m e
(Xt) on
Zd
such
and follow a
z c A
r a n d o m w a l k arrow w h e n e v e r it occurs, but a branching arrow only if it takes us closer to 0 .
follows a path u p in P .
It is recurrent since it has a drift toward
the selective following of the branching. b a s e d on the fact that
0
c a u s e d by
A rigorous proof of recurrence can be
( IX t A "[b IZ) is a supermartingale,
time of a sufficiently large reader.
since it
The resulting chain is obviously i m b e d d e d in (~tA) ,
d-sphere centered at 0 .
where
Tb
is the hitting
Details are left to the
[]
It is intuitively clear that if a biased voter process then its configuration will converge to Z d
as
t ~co
(EtA ) does not die out,
In o n e d i m e n s i o n this is
quite e a s y to prove.
(8. Z ) any
Proposition. ~
Let
{(~A)}
be the basic biased voter m o d e l o n
T h e n for
~ ,
lira Et = Z t~ Proof.
Z .
Note that ~
is a block
P-
[L t, R t ] ,
independent r a n d o m w a l k s with drift k - 1 whenever
Rt - Lt > 0 .
> 0 toward
on
L t and -~
and
~
{TIt=
6A,
6 A , A e SO . A ~ S ,
.}
.
R t evolve like +co
The claim follows easily for g = 6 x
result holds for a n y m e a s u r e extends the result to a n y
where
a.s.
respectively,
By additivity the
A simple approximation a r g u m e n t
and h e n c e to arbitrary ~ c I]I .
[]
As an i m m e d i a t e c o n s e q u e n c e w e obtain the w e a k e r c o n v e r g e n c e result :
(8.3)
Corollary.
pt
For the basic biased voter m o d e l on
P
(~j~ < co) 6 g
+
p(~
=
o,) 6 z
Z ,
VI~
~
58
The law of large numbers when
d = 1 .
fact
For
d - Z ,
(~O] { O;u : ~})
linearly with
t .
shows
that
the analogue
Itx
grows linearly
of Proposition
(8.Z)
given nonextinction still holds,
and in
b e c o m e s essentially a solid "blob" w h o s e radius grows
In the limiting case of total bias
has proved such a t h e o r e m
("k = ~'') , Richardson (1973)
H e shows that there is a norm
11 11 on R d
such that
Ya>O
where
B
{x ~ Zd
=
:
r
l<X<~o
(8.4)
0 ~t c
3t 0 < ~ : p(B(l_a)t c
llxlq<
r}
B(l+s)t ) >- i - s
Vt > tO
Analogous results for the models with
.
are the subject of two forthcoming papers by Bramson and Griffeath.
Notes.
The basic biased voter models restricted to S O were introduced by
Williams and Bjerknes (1972) as models for cancer growth.
Their simulations and
conjectures led to a great deal of work on growth rates of S0-valued particle systems;
see Mollison (1977) for a survey of these and related problems•
(1977) has studied the basic biased voter models on
Schwartz
S , and is the source of
Theorem (8.1).
9.
Coalescing random walks. The lineal additive systems k n o w n as coalescing random walks have already
appeared as duals for voter models. density
Such a system is determined by a probability
p = (py, y ~ Z d) ; its percolation substructure has the representation:
I = Zd X
W
Z~X
Zd ,
i
(y) = {z}
z, x
:
Pz-x
if y = x
The intuitive description w a s given in Example this section w e reverse perspectives,
,
Vz
(= {y}
,x
-=
~
"
'
otherwise).
(I.l.l) and in Section (II.7).
In
and derive s o m e properties of coalescing
random walks by using the voter model as an auxilliary system. To begin, there is the question of ergodicity. measure
6~
more rare.
O n e expects a limit
starting from any initial state, since extant particles b e c o m e more and This is confirmed by our first result.
59 (9.1) density
Proposition. p .
A
Let
{(It)}
random walks with transition
Then pt
Proof.
be the coalescing
By m o n o t o n i c i t y ,
as
69
t--~
V~ ~
it suffices to check that Zd P([t 9 x):
lira
Yxc
0
Zd .
t~oo
The d u a l s y s t e m i s t h e c o r r e s p o n d i n g v o t e r m o d e l , Zd P([t 9 x): iX
If [t = A , q (A) :
>~ y~A
IA I = k , V f~ z~ A
£j yc A c >~ z~A
and
A AX P([t /}~)
t h e c a r d i n a l i t y of t h e v o t e r p r o c e s s b e c o m e s I
Pz-y
Pz-y = q(A) .
and b e c o m e s
Thus
k +l
k - i at rate
(l~tl) jumps like at simple random walk with
c
absorption at 0 after exponential holding times with rate at least Z . A
AZ
P(T~ < ~o ) :
at rate
1,
and the proposition follows.
Zd Since the distribution of It whether an individual site,
walks at arbitrarily large times,
[]
converges to
the origin say,
Hence
6~ ,
i t i s n a t u r a l to a s k
is visited by the coalescing
or w h e t h e r t h e r e i s a l a s t v i s i t .
random
This "recurrence"
question is settled by our next result. (9 .Z)
Theorem.
If
{([t)}a
is the coalescing
r a n d o m w a l k s o n Zd
with density
p ,
then Zd P(lim sup It
(0) = 1) = 1 .
t~oo
The p r o o f r e l i e s o n a l e m m a , w h i c h w i l l i m p l y t h a t t h e e x p e c t e d a m o u n t of Zd time that 0 is occupied by (It ) is infinite. T h i s p r e l i m i n a r y r e s u l t , s t a t e d for the voter model,
i s of i n t e r e s t i n i t s o w n r i g h t .
(9.3)
Let
t--> 0 ,
Lemma.
{ (AA I t )}
b e t h e v o t e r m o d e l on Zd w i t h d e n s i t y
p .
T h e n for
60 A A0 )-I P ( [ t /JZ)_> ( l + t Proof.
AS already noted,
A0 It = A , I -< IAI < ~ ,
when
the voter process
increases or decreases by one particle at the s a m e exponential rate 2 2 Pz-y " Clearly q(A) < I-A_I . Let (Zt)t >_ 0 be a birth and y~ A c z~ A death process on {0, I, Z, • • • } with absorption at 0 , and with transition from
q(li) =
k to k-I or k+l
(k-> I) at the s a m e exponential rate
note that since this process jumps at least as fast as more quickly.
_>
(Hint:
(Zt) at 1,
(Problem
Problem.
(9.4).)
Hence
-I u(t)= (l+t) ,
S h o w that the function
(Zt) is a G a l t o n - W a t s o n
Then
u(0) = I and
completing the proof.
u(t) defined above satisfies
du Z ~ - = -u
process.)
Zd Proof of T h e o r e m (9.Z). Let T t = m i n { s -> t : 0 ~ ~s } , and note that Zd {lira sup ~t (0)= I} = lira lira {Tt~ It,u]} . For 0 -< t < u , b y t h e t ~ ~ t~ u--~
Markov
property and monotonicity, u
s[J
~
Sd(o )
t
ds] =
]u
f
P(T t
dr, ~ Tt zd ~ dA) E[ fo u - r ~2(0) ds]
t
u
t
Zd
7 P( t dr.
Thus
P(q:t * I t , u ] )
last l e m m a ,
t,
[t'u])E[~ 0
u
dAl u
= P(Tte
For each fixed
and
p(zt/o).
Let u(t) denote the right side of this last inequality.
(9.4)
Start
Thus
P(i~t°/s) du Z d--t- = -u
k .
A0 (%t) ' it will be absorbed
°
Zd ~s (0) ds]
Zd
(01 ds]
.
u Zd E[]" ~s (0) ds] t -> u Zd E[]0 ~s (0) ds]
the left side tends to 1 as u ~ o
•
since by duality and the
61 =
E[;
zd
Zd
~o
~s (0)ds] = fo
P ( O e ~s ) ds
~o
~
j£ Zd Thus P(limsup ~t (0)=i)= t ~
lim
~
lim P(Tt~ [t,u])= i,
a s = oo
and the proof is
U ~¢o
t~
finished.
(l+s)- 1
P(~: / ~ ) d s >- JO
[]
W i t h more c a r e o n e c a n e x t e n d T h e o r e m ( 9 . 2 ) t o c o a l e s c i n g r a n d o m w a l k s s t a r t i n g from a n y d e n s e c o n f i g u r a t i o n A . the case where
p is transient;
The r e a l c o n t e n t o f t h e t h e o r e m l i e s in
t h e r e i s a m u c h s i m p l e r a n d more g e n e r a l r e s u l t
if p is recurrent: (9.5)
Problem.
Show that for p irreducible recurrent, A
P ( l i m s u p ~t (0) = 1 ) = 1
VA/
t~co
(p
i r r e d u c i b l e m e a n s t h a t t h e g r o u p g e n e r a t e d by
{y e Zd : py > 0}
i s a l l o f Zd
o)
W e c o n c l u d e t h i s s e c t i o n w i t h c l u s t e r s i z e r e s u l t s for c o a l e s c i n g r a n d o m walks on Z .
To k e e p m a t t e r s s i m p l e ,
we start from
d i s t a n c e from t h e o r i g i n t o t h e f i r s t n o n - n e g a t i v e s i t e prove
a
d i s t r i b u t i o n l i m i t t h e o r e m for
(9.6) Theorem.
5z x
Let such that
D+(~ Z ) x c ~(
be the .
We
D+ (~Z)
With D+ defined as above, Z D+ (~Z) P( __ -< ~ ) 4t
lira t--= Proof.
Write
n = n(t) = L a Q ' - t - 3
1 -
c~
-
(
ks3
e
f
4~
s 4
ds .
0 i s t h e g r e a t e s t i n t e g e r in
s •)
By duality,
D+(~)
_
P(
_
<
~]-T-
- c~)=
z
P(~
N
[O,n] / )~)
A A[ 0 , n] = P(~t / The k e y o b s e r v a t i o n i s t h a t with jump rate (Yt) .
Z ,
(]~,~0,n]
starting at
] _ 1)
n,
9 ) •
i s a s i m p l e r a n d o m w a l k on
and with a b s o r p t i o n at
-1 .
The r e f l e c t i o n p r i n c i p l e for r a n d o m w a l k s t a t e s t h a t i f
{ 0 , 1 , • • "}
Call this process
(Xt) i s s i m p l e r a n d o m
62 w a l k on
Z
w i t h jump r a t e
Z , s t a r t i n g at
0,
then
P(Yt -> 0) : P(X t -< n) - P(X t _> n+2)
L=
xt :
P(
-<
-
4 z-7
J
-
)
qT J +
xt -
p(
__
47i-
z
->
)
4 zt
4-f{
A c c o r d i n g to t h e c e n t r a l l i m i t t h e o r e m , the r i g h t s i d e c o n v e r g e s to ~ a u Z u Z 1 427T
(/ -co
)e
Z- du
:
2.
q-Z
e
Z
du
.
0
a
47
D+ (Cz) Since
P(---
P(¥t-> 0),
47-
s=
4Z
u
givesthe
[]
desired result.
(9. T)
the c h a n g e of v a r i a b l e s
Problems.
meaninterparticle
7
Define the mean interparticle distance d i s t a n c e s of ~Zlbn(O) .
D([t)
as a l i m i t of t h e
U s e t h e m e t h o d of Theorem (T.11)
to
prove t h a t D ( ~ z) (9.8)
lira t ~ oo
-
in
~-
P-probability.
r7
Show t h a t
E " D[ + (~C t )
]
--
as
~
t ~ o~,
4 t
so t h a t if D0([ Z)
b e t w e e n t h e p a r t i c l e s i m m e d i a t e l y s u r r o u n d i n g t h e o r i g i n in (9.9)
lira E[ -D0- ( []Z ) ~
_
t--oo
i s the d i s t a n c e
~Z ,
4 X/T
E x p l a i n t h e d i s c r e p a n c y b e t w e e n t h e c o n s t a n t s in ( 9 . 8 )
and
( 9 . 8 ) c o n t i n u e s to hold if
where
(~Z)
then
is r e p l a c e d by
,
is any t r a n s l a t i o r
6~ .
i s r e p l a c e d by
i s any t r a n s l a t i o n i n v a r i a n t m e a s u r e w i t h
I
where
~
(9.9)
~
Show t h a t
i n v a r i a n t mixing m e a s u r e e x c e p t (~t~ ) ,
Show t h a t
(~)
(9.9).
c o n t i n u e s to h o l d if (~tZ)
D0(A)~ (OA) <
(9.10) (1975)
Notes.
C o a l e s c i n g r a n d o m w a l k s w e r e i n t r o d u c e d by H o l l e y and L i g g e t t
as d u a l p r o c e s s e s for v o t e r m o d e l s .
G r i f f e a t h (1978b); Theorem (9.6) (1978b),
P r o p o s i t i o n (9.1)
They are s t u d i e d in t h e i r o w n r i g h t by
and T h e o r e m (9.Z)
and t h e r e s u l t s in P r o b l e m s (9 .7)
are from t h a t p a p e r .
a r e due to Bramson and G r i f f e a t h
who a l s o o b t a i n s i m i l a r t h e o r e m s for the b a s i c v o t e r m o d e l on
Z .
63
i0.
and exclusion
Stirrin@
systems.
Our final section on additive systems deals with a class of models called random stirrings. For simplicity w e discuss only the translation invariant situation. Let W i , 0 ' i ~ I0 , be permutations of Z d which leave all but a finite number of sites fixed.
~ ki,0 < ~ Let ~ be the i translation invariant lineal percolation substructure determined by the X i, 0 and Wi, 0 "
The rate for W i, 0 is X i , 0 ' where
Then the additive system
Clearly the dual
{ (~A)} induced by
9
is a random stirrin9.
{(~tB)} for any such system is another random stirring, namely the
-lx = the inverse of W i ,x one constructed from permutations ~fi, x = W .i, also easy to see that the product measures I ~ B I = I Sl
for all
S~
SO ,
t ~ O,
%
qt ( B ) = (1We
by
o)lSl
~0
are equilibria.
Z
with density
In fact, since
(1.11),
: ~o~O(B) .
n o w derive a convergence theorem for random stirrings.
measure
It is
It states that any
0 which satisfies a certain mixing condition is in the
domain of attraction of
~0
(I0.I)
{(~A)} be a random stirring. Given b ~ ~ , a s s u m e that
q~(x)
Theorem. -~ 1 - 0 ,
Let
and
(IO.Z)
that
lim
sup
R--~° A c where pt
~bO
Proof.
S0 ' R =
I~(A)
n,R SO
- -~-- ~ ( x ) l = 0 , x c A
{A ~ S O : IAI = n and y-x >- R,
Vx, y ¢ A , y / x ] . Then
as t ~ o ~
By duality equation (i.I0), for each
_ l_O)l ll +
sup
_<
B c SO ,
s BI ,R)
A c S~ B] , R The hypotheses
on
prove the theorem,
b
state
that the above
it therefore
suffices
supremum
to check
that
tends
to
0
as
R - - co .
To
64
(10.3)
lira P ( ~ ? /
S~ BI , R ) = 0
for each
R
.
Rewrite this last probability as
<
Y, x,ye
B
Ay ~ P(I [ t -
I < R),
x/y so t h a t
(10.3) will follow from the f a c t t h a t
(10.4)
lim P ( i ~ Y - ~ t t~
I < R)=
x Zd {(X t)} on by
To get (I0.4), define M a r k o v chains
Counting measure is invariant for { (X$)} , transient.
In either case
Yx,ye
0
Zd .
wy-x Ay AX "'t : [t - ~t "
so the chains are null recurrent or
lim P(IxtY-Xl < R) = 0 , so the proof is finished. t~
The most important random stirrings are the additive exclusion systems, where each W.l,X
permutes exactly two sites.
These models m a y be interpreted
as systems of particles performing independent random walks, but subject to an exclusion rule : whenever a particle attempts to jump to a site which is already occupied it is not allowed to do so.
(Note that (~:) is not the motion of an
individual particle under this interpretation. )
Liggett has studied the additive
exclusion systems, and a number of more general models, in a long series of beautiful papers. survey of his work.
The reader is referred to Liggett (1977) for a self-contained O n e basic theorem states that the extreme equilibria for any
additive exclusion system are precisely { ~i ; 0 -< # -< 1 } .
Also, a result
similar to (i0.i) states that ~ p t
~
~#
as t-- o~ whenever
invariant and (spatially) ergodic with density
(10.5)
Problem.
is translation
@ .
S h o w that any additive exclusion system is self-dual.
other random stirrings are self-dual?
Which
[]
65
(i0.6)
Notes.
for systems on Z
Lee (1974) introduced random stirrings and proved Theorem (I0.i) •
H e also considered analogous processes on R
(19 ?6) has additional remarks on stirrings.
Harris
Spitzer (19?0) first formulated exclu-
sion models, and proved self-duality in the additive case.
A detailed analysis was
subsequently carried out by Liggett (1973 , 1974, 1975, 1976) and by Spitzer (1974a).
CHAPTER III:
CANCELLATIVE SYSTEMS
I. The general construction. This chapter is devoted to a second class of particle systems which, additive ones,
can be defined by m e a n s of percolation substructures.
~ = ~(k;V,W),
Tit = {x : N
{ (BAt)}
Given
i f w e define
(i.I)
then
like the
is another
(x) is o d d }
,
S-valued M a r k o v family,
called the (canonical) I
cancellative particle system induced by off, then
@ .
(1.1) implies that configuration
If
~]A : B
(Since
W i , x (y) = {y}
B
B~ <
t h e n a r e s u l t similar to P r o p o s i t i o n ( I I . 1 . 4 ) conditions
(II . 1 . 5 )
and
(II . 1 . 6 )
s p e c i f i c m o d e l s in t h i s c h a p t e r . o b v i o u s a n a l o g u e of
clock goes
~vi, x
for a l l b u t a f i n i t e n u m b e r of s i t e s
difference makes sense even when
(i, x)
B jumps to
¢i,x(B)= [ n Wi,x(y)] yc
and the
.)
If
9
y ,
this symmetric
h a s no i n f l u e n c e from
ensures that
are again s u f f i c i e n t ,
{(BA)}
is Feller.
~ , The
and will apply to all of the
Our f i r s t r e s u l t for c a n c e i l a t i v e s y s t e m s i s t h e
( I I . 1.Z). A
Proposition.
(i.2)
AAB ~]t
Proof.
If
{0It)}
is a c a n c e l l a t i v e s y s t e m ,
A B ,6 : nt A ~t A ~t
x ( Bt A ~t A ~ t
>
<
;- N
A A B(x )
-= I
(rood Z)
B [f (x)) + Nt(x) -= i
A A B <.---> x ~ ~]t
Unlike the additive systems, monotone.
S,
<--m N (x) + N t (x) + N ~ ( x ) -= 1
A At] B B AN (N t (x) - N t (x)) + (N t (x) - N t
<
A,B~
then
t-~ 0 •
(rood Z) (rood Z)
[]
t h e m o d e l s w e w i l l n o w s t u d y are t y p i c a l l y n o t
T h i s i s c l e a r l y t h e c a s e for o n e o f t h e s i m p l e s t c a n c e l l a t i v e s y s t e m s :
t h e a n n i h i l a t i n g r a n d o m w a l k s o f E x a m p l e (I • 1 . 3 ) . the following exercise.
Another e x a m p l e is given in
67 (1.3)
Problem.
determined by
Let p
p
and
be a transition density on
k > 0
is the spin system
Cx(A) = k [A(x) + (l-gA(x))
Zd .
The a n t i - v o t e r
{(~tA)}
with flip rates
~
model
pz_x]
z ~ Ac Show that such a model is cancellative, D u e to t h e l a c k of m o n o t o n i c i t y ,
and determine
new techniques
9 .
will have to be developed.
Fortunately there is still a duality equation, although the general dual system AA { (~t)} i s more c o m p l i c a t e d t h a n i n t h e a d d i t i v e s e t t i n g . We now proceed to develop this duality theory. section,
General ergodicity results will be proved in the next
and then several specific cancellative
systems will be studied in some
detail. Let processes
{02 A ) }
be defined by
(~B) ,
B ~ SO ,
A an isolated point.
(1.1)
will have state space
The s e c o n d f a c t o r s p a c e
plays an important role in cancellative has
for given
systems.
P (X;V,W)
•
The d u a l
"~= (S O x { 0 , 1 } )
{0,1}
is necessary
Say t h a t t h e
U [A} ,
because
parity
( i , x) - f l o w i n
P
pure births if
ki, x > 0 , for s u c h
(i,x) ,
the labels
Vi,x/~ ~
and
are called
Wi,x(y
pure births.
) = {y}
Vy
;
To d e f i n e /k
introduce the modification
~(~,
V, ~ r )
of t h e d u a l s u b s t r u c t u r e
/k
/k
P(X,V,W)
such
that ~i,x
= Zk i,x = k.
1pX
if
(i,x)
has pure births in
~
,
otherwise.
Define "~t = { ( x , s ) ,
0 < s -< t :
~B ~A = i n f { t -
0:
3
a pure birth occurs at
odd n u m b e r of p a t h s u p from
Now let ~B=
( nAB t,
e )
0 ~ t < --A *
(1.4) =
A
~B
Td~ --< t < ¢ °
(x,s) (B,O)
in 7} to ~ t
,
in 7 )
68 where AB q t = { x : 3 odd n u m b e r of p a t h s up from B
s t --- n u m b e r of p a t h s up from
(Recallthat
St=
{(x,s),
(B,0)
0 < s-< t :
to
(B,0)
to
St i n ~
(x,t)
in ~}
,
(rood Z) .
a birth occurs at
(x,s) in ~ }
The
l)
duality equation for cancellative systems m a y be stated as follows. (1.5)
Let
Theorem.
{(~B),B~ s o } t>O,
{ (T]B)} b e t h e c a n c e l l a t i v e
t h e c o l l e c t i o n of d u a l p r o c e s s e s
A~ S ,
Let
defined by
(1.4) .
£
J
T h e n for e a c h
B~ S O ,
P(I~]An B I even)-- ~(l~tB N AI+ s B
Proof.
system induced by
Pt(k ; V,W)
and
Pt(k ; V,W)
even,
~TB~
> t)
+ ~1 ~P ( ~ ~B
_< t )
be the forward and reverse percola i
tion substructures Acopyof in
~t
Pt'
on
Zd × [ 0 , t ]
:
Zd x [ ~ , t ]
t h e r e s t r i e t i o n of P ( X ;
as follows : at each location
V,W) ( x , s)
constructed to
zd×
(i.e.
the
[~0's
are ignored),
(~Asl0 -< s -< t and
and only the
~l'S
t} : {l~t B N AI + eB
0 or w i t h a
a r e p u r e b i r t h s i n Pt Thus
Moreover,
even, ~TBA > t} P - a . s . ,
((A, 0) U 8t ) and
(B,t),
use the fact that
I n O n B t even
I {Y ~ B : N A(y) NA(B)
> P ( ~ B _< t) = 0
1 .
equivalent to
{ a n e v e n n u m b e r of p a t h s b e t w e e n
If
[3 w i t h a
are r e a l i z e d on the joint s u b s ~ u c t u r e
{ llqtA N Bleven, N TB>
To s e e t h i s ,
can be embedded
t h e n we o b t a i n t h e d e s i r e d v e r s i o n of Pt "
(~sB/0 _< s-< t
since both events are a.s.
[0,t],
w h e r e a pure b i r t h o c c u r s i n -~t '
f l i p a f a i r c o i n t o d e c i d e w h e t h e r to s u b s c r i p t t h e l a b e l If a l l of t h e c o i n f l i p s a r e i n d e p e n d e n t ,
as in Chapter I.
we're done.
odd}l even
even
AB B I~]t n A I + st even,
Otherwise,
write
P - a.s.
AB ~t, > t} .
69
{IT]At N B l e v e n ,
~TBA -< t} : (En F N G) O (EN F C n G c)
where
E : {T B--< t} ,
F=
{~Bl'S occur at T AB}
,
G = {odd number of paths to (B,t) from ((A,0) U ~t) - (zd,TAB)} •
The key observations, which follow from the construction ~ are that i are conditionally independent given E , and that P(F IE) = 2- " P ( E N F N G) + P ( E N F c N G c) = I [ p ( E N
F
and
G
W e conclude that
G) + P ( E N Ga)]
i
= 2- s (s) • []
The d e s i r e d d u a l i t y e q u a t i o n f o l l o w s i m m e d i a t e l y .
The quantities
systems that the zero functions
p l a y t h e r o l e for c a n c e l l a t i v e In o r d e r to p r o v e
~Pt(B) did in the additive case.
~
ergodic theorems using Theorem (1.5), w e need to k n o w that any
~. i s
uniquely determined by its cylinder set probabilities of the form To see this, w e observe that {p~ is determined
~ ( B ) = ~t({A : IAN B I even}) . by ~ b
according to the formula
(1.6)
~(B):z-IBI
~
[Z~(A)-I]
,
B~
So
•
ACB
(i. 7)
Problem.
Derive equation
The states
(@,0) and
(1.6) .
(~,I)
are both traps for
(~B),
number of paths up from (B,0) to (x,t) in ~
then for any
is even
V x c Zd ,
s >- t, number of paths up from (B,0) to (x,s) in ~
P - a.s.
sinceif
State
hitting times;
~
is also a trap.
~
W e let T0B,
dearly at most one is finite.
~B
"cI
and
iseven ~B
TA
Vx~
Zd
be the respective
For convenience, we also put
70
?B
= ~BA TO
~IB T A ~TAB .
Two e a s y c o n s e q u e n c e s
of T h e o r e m (1.5) c o n c l u d e t h i s
section. (1.8)
Corollary.
v ( r~
such that
Let
A
{O]t" )}
be cancellative.
pt ILl
as
V
~
There is an invariant measure
['P(T 0 < ~ ) + ' P ( ~
t ~°°
where
CV(B)=
Proof.
Integrating the duality equation with respect to
,
= co)] and using the fact 2
~l 1 E (B) = ~-
whenever
) ~ / B e SO ,
~t1
•t
g (B) : E[~I_ ( { A :
we g e t
IAn ~'B!
+ 8B even}), ~ B > t]
2
4~- P(T A --< t)
--< t ) + F
= ~('~
Let
t - - o~
(1.9)
for each
(I.11)
Proof:
--< t )
a n d do s o m e a l g e b r a to f i n i s h t h e p r o o f .
Corollary.
(1.10)
> t) + FP(TA
tim t ~°~
Let
{ (A)
}
be cancellative.
(
= ( A , 0 ) ) - P(
•
[] If
= (A,I))] = 0
A
B ~ S O , then
{ (~]A)}t is ergodic.
~ ( ~ B < co) = 1
The d u a l i t y e q u a t i o n c a n b e r e w r i t t e n a s
In particular, ergodicity holds if
VB ~ S O
71
q~ ( B ) = ~ (
-
2-
A
+ ~
/
> t)+
~
-
•
[ #(~B = (A, a), IA n A I + s even)
a=0,1
lAnAI
_ ~p(rl t~B = (A , ~ ) ,
%ssuming
(1.10),
the last
Bxists for each
B ,
~ote that condition
(1.1Z)
Notes.
systems
zancellative
Z.
(1.11)
"Q : 0
(1.9)
Extralineal
the dual to
(2.I)
"
A •
t~=
•
Thus
This proves
odd)]
.
A ~ t (B)
lira
ergodicity.
Finally,
[]
systems
due to Hoiley
generalizes
and Stroock
the theory of spi
(1976a).
The graphical
In particular,
approach
to
is new.
systems
The analogue
Let
(2.Z)
of
of cancellative
to t h e a d d i t i v e
Theorem.
as
(1.10) .
inf A~ SO
{(A)
with pure births.
case,
need not be ergodic. A .
0
on one of their results.
cancellative
In contrast {ire systems
implies
duals,
is based
systems
to
and is independent
Our treatment
with
Corollary
sum tends
+ s
translation
One needs
of Theorem
}
the presence
(II • Z . 2 )
be cancellative.
2 purebirth (i,z):
invariant
extralineal
cancella-
of pure births to send
in the present
setting
is
If
k. = 1,z
~ > 0 ,
Ia n Vi, zlOdd then the system
Proof.
Condition
rate at least ~B T < =
is exponentially
(Z.2)
ensures
2 K from any state
P - a.s.
,
ergodic.
In f a c t ,
(II.2.1)
that the dual process other than
and the duality
equation
(@,0), yields
( ~ t ~) (@,1)
Q=ZK
holds with
goes to and
A .
A Thus
with
•
72
: I 0{B) 7( C <
10tA(B) - L~V(B)[
7oB <
-< 7(t <
~) +
Pl-{Tf < o)I ½7
(t < ~T AB .- =) + 7 ( 7
B>
t)
5 -2~t 5 ~('$B > t) < ~-e _< ~-
The rest is routine.
(2.3)
Corollary.
exponentially
Proof.
k -> ki, 0
i(
Io : V i , o ~
z ( Zd in
We
Any t r a n s l a t i o n
invariant cancellative
9 ,
such that
(Z.Z) .
Wi,o(y)=
Vy
For any
A~
IA n Vi,z! = IA f] (z + Vi,o) I = I .
say
i -> I
V0
,X
= {x}
w e can take
that there is a single pure birth m e c h a n i s m J
W.
occurring at rate
SO
we
Thus
:
{z}
Ci, x ( S O .
spin s y s t e m one m u s t allow both
z / C i , x, z=
But n o w , V i,
it is c o n v e n i e n t to redefine
ix0 : {i c Ix : V i , x = )$ } '
As in the additive case,
z ~ Ci, x
: {9}
for prescribed sets
KX -> 0 .
at e a c h
to be of the form
l,X
Wi,x(Z) : {x,z}
(2.4)
{y}
[3
One can assume
site x ,
{ O] A) }
with pure births is
n o w determine the general form of the flip rates for cancellative spin
systems.
before,
system
ergodic.
Pick
c a n find a
for
[]
X I
x
= JJ
x¢
z/x
Ci,x
to get the m o s t general cancellative and
V, = {x} l~X '
by r e m o v i n g
i= 0 .
llx : {i ~ Ix : Vi, x : {x} } ,
i -> I . Then,
As
denoting
the flip rates for
so i n d u c e d h a v e the form
C x ( i ) = Kx +
~
hi. x i0 : x I(AO C i , x ) h { x } [ o d d i~
+
E
hi, x i1 • x " I ( A • Ci, x ) A { x } l e v e n i~
73
T o ensure that there is n o influence from
~x
=
~
co ,
k. l,X
let
,
i• Ix assume
(2.5)
sup ki, x < ~o , x
and also
(II. 1.6).
T h e n T h e o r e m (Z.1) a p p l i e s i f
(g.6)
inf X The duals
(~]t)
branching processes
for t h e s e s p i n s y s t e m s
with parity.
replace itself with particles already occupied, This describes 0
and
Finally, (Z.7) Ci,x/
With rate
located at
"annihilation"
t h e e v o l u t i o n of
may b e t h o u g h t of a s a n n i h i l a t i n g
ki
Ci, x
"
AB
a particle at
At e a c h s i t e of
takes place, (~t)
,
,x
(a)
Cj, x
Show that one can assume i ~ Ix0 ,
if
j ~ I x1'
Ci,x
/ {x}
ic
ixl e f f e c t s
A
at rate
Vi ,
and
in t h e g e n e r a l r e p r e s e n t a t i o n
D e r i v e t h e f o l l o w i n g r e s u l t s for c a n c e l l a t i v e
modifying the additive versions
x¢
AB nt
ZK x
(Z.4)
of
If
~ ~ •
If ( Z . Z )
is spatially mixing and
holds and
unique equilibrium
systems by
proved previously.
s p a t i a l l y m i x i n g for e a c h (ii)
which is
spin systems.
Problem.
(i)
Ci, x
t r i e s to
simply flips back and forth between
tB
a flip occurring each time a clock indexed by AB a particle at x • n t s e n d s t h e e n t i r e p r o c e s s to Problem.
AB x c nt
so the site becomes unoccupied.
1,
cancellative (Z.8)
Kx > 0
P v
f~
is local,
then
bpt
is
t < is local and translation
for
{ ( A)}
invariant,
then the
has exponentially decaying
correlations.
(Z.9)
Notes.
For a n o t h e r a p p r o a c h to t h e t h e o r y of c a n c e l l a t i v e
Holley and Stroock S t r o o c k (1976a).
(1976d).
Theorem
(Z.1)
generalizes
spin systems
see
a r e s u l t from H o l l e y a n d
74
3.
Application
to the stochastic
The basic
Isin@ m o d e l .
d-dimensional
stochastic
Isinq model is the spin system
on
Zd
with flip rates
Cx(A ) : [I + exp {- 0Ux(A)}] -I ,
(3.1) where
Ux(A ) = 4 ( 2 A ( x ) - l)(d - ] AN Nx[) (N x = {Y ~ Z d : ly-xl = I}) .
0 ~- 0
is a parameter.
This system
{(~]tA )}
is
one of the simplest and most widely studied models for the evolution of a physical system with two possible states per site (e.g. solid or liquid, "spin up" or "spin down" in a piece of iron, etc.). Background and motivation for the choice (3.1) will be found in the papers mentioned in the Notes of {(nO) } here.
for arbitrary values of
0
(3.3) .
The construction
requires methods which will not be discussed
For certain parameter values, however, the stochastic Ising model has a
cancellative representation, and in these cases our methods apply. with flip rates
The systems
(3.i) are important because the Gibbs measures with potential U
are equilibria for them.
~ c ~
is such a measure if
~
has positive cylinders
and
(3 .z)
~([A, {x}] I [ A , A ] ) = [I + exp{0Ux(A)}] -I ,
where Given
[A,A] : {Be S: such a
and put
~:
[~ , A U x,
B• A:
if we write
A• A} ,
forall finite
xA = A A x
then for
A
A : N
for the configuration
C A C Z d - {x} . X
"A f l i p p e d
at
as above,
~ ( [ A , X ] ) C x ( A ) : b ( [ A , ~ ] ) ~([xA,{x}]
I
[A,A])
: ~([xA,K]) ~([A, {x}] l [xA,A]) = [L([xA,A]) Cx(xA) Roughly, then, the flow from
0
to
1
equals
site w h e n the stochastic Ising model is started in
the flow from .
1 to
0
at each
This suggests
that the
x"
75 A
Gibbs measure
~
is invariant for
{(~]t)} ,
a fact w h i c h can be proved rigorously•
It turns out that the stationary process starting from
~
is time reversible, i.e.
has the s a m e d y n a m i c s whether time runs b a c k w a r d s or forwards. S u p p o s e n o w that for every
~ - 0 .
this, take Cz,x (3.1).
d = 1 .
T h e n the stochastic Ising m o d e l is cancellative
Indeed, it {s simply a voter m o d e l with pure births•
• x ~- (I + e4~) -I ,
I0x = {I,Z} ,
Ix = ~ '
= {x + I} ' X 1 ,x = k 2 , x = ~1 - (i + e 48)-I . Moreover,
since
C l , x = {x - I} ,
Then
K = (I + e48) -I > 0 ,
(2.4)
{( A)}--
In particular, there is only one equilibrium for the m o d e l , G i b b s state v
with potential
decaying correlations. transition w h e n
U .
By Problem (Z. 8 it) ,
so there is only one v
has exponentially there is no p h a s e
d = 1 . d = Z
is m u c h more interesting.
O n s a g e r asserts that there is more than one Gibbs m e a s u r e Q >
coincides with
is exponentially ergodic.
In the language of statistical physics,
The situation w h e n
and only if
To see
Q~
= arc sinh 1 ~ .88 .
m o d e l is therefore nonergodic.
For
~ >
A f a m o u s result of
~
~,
with potential
U
if
the stochastic Ising
This is one of the simplest e x a m p l e s of a translation
invariant local spin s y s t e m with strictly positive flip rates w h i c h is nonergodic. It is not k n o w n whether such a s y s t e m exists in one dimension. computation s h o w s that the representation if and only If mechanisms
Z-dimensional stochastic Ising m o d e l has a cancellative e -<
affecting each site
~n 3 4 ~
• ~ Z2
.Z7 •
6 r--
For
8
in this range, the
m a y be described pictorially as follows :
at rate Z ( l + e 48) 6
A straightforward
-l
i
- 2
'
e a c h at rate
6 6
T
1
3
1 e4Q)-i I + e 8 # -I - Z (I+ - ~(i )
e a c h at rate
~8
1 _ ~-( i I + e 4 9 )-I + ~1( l + e 8 0 ) -I
rV
76
A r o u t i n e c h e c k s h o w s t h a t t h e s e r a t e s g i v e r i s e to t h e f l i p r a t e s
(3.1)
W h i l e t h e l a s t t w o r a t e s of t h e s u b s t r u c t u r e a r e a l w a y s n o n - n e g a t i v e , pure birth is only non-negative
if
~ _< 2n4 3
just as in one dimension, that {( A)} unique Gibbs measure
When
~ < ~n 3
when
d = Z .
t h e r a t e of w e conclude,
is exponentially ergodic, that there is a
v with potential U , and that v has exponentially decaying
correlations. (3.3)
Notes.
A b e a u t i f u l i n t r o d u c t i o n to t h e I s i n g m o d e l i s G r i f f i t h s (197Z);
n i c e t r e a t m e n t o f more g e n e r a l G i b b s a n d M a r k o v r a n d o m f i e l d s , S t o c h a s t i c I s i n g m o d e l s w e r e f i r s t s t u d i e d b y G l a u b e r (1963).
see
for a
P r e s t o n (1974).
More recent applica-
t i o n s of t h e d y n a m i c a l m o d e l s to t h e e q u i l i b r i u m t h e o r y m a y b e f o u n d i n H o l l e y (1974) a n d H o l l e y a n d S t r o o c k ( 1 9 7 6 b , 1976c) • time-reversible
by S t a v s k a y a
Z-dimensional
(1975) a n d H o l l e y a n d S t r o o e k ( 1 9 7 6 a ,
b y L o g a n (1974).
Ising model were obtained
1976b).
Generalized voter models. If t h e s u b s t r u c t u r e w h i c h g i v e s r i s e to
cancellative
{(nt)}
has no pure births,
For s p i n s y s t e m s of t h i s t y p e t h e r e i s a c a n c e l l a t i v e
that that
(~B)
i s d o m i n a t e d by a c r i t i c a l or s u b c r i t i c a l hits
result formally, (4.1)
Theorem. K --- 0 . x L=
( ~ , 0)
or
(f~, 1)
even) .
a n a l o g u e of T h e o r e m (II • 3 . Z ) .
Both t h e s t a t e m e n t a n d t h e p r o o f a r e v i r t u a l l y i d e n t i c a l : AB (l~]t [)
then the
duality equation simplifies to P(I~]AN B]even)= P(I~]AtBN AI+ SB
with
between
spin systems and Gibbs random fields are discussed
The r e s u l t s of t h i s s e c t i o n d e a l i n g w i t h t h e
4.
The c o n n e c t i o n s
the hypotheses
Galton-Watson
eventually with probability one.
imply
process,
so
We state the
but omit the proof. Let ((~tA)} b e a c a n c e l l a t i v e
spin system having flip rates
Set inf Xx , xc Zd
m =
sup x ~ zd: k >0 x
~ i~ I x
Xi'xk x
[Ci,x]
(Z.4)
77 If
L > 0
and
lation invariant
m < 1 ,
then the system
is exponentially
case the system is also ergodic if
m :
1
ergodic. and
Ci,x
In t h e t r a n s : C i = j~
for
i .
some
A particularly simple family of systems without pure births to which (4.1)
does not apply consists
models,
where
to take
I
x
ICi,x I = 1
= Zd .
of the
(translation
for all
i .
invariant)
generalized
As i n t h e a d d i t i v e
After some manipulation,
case,
Theorem
voter
it is convenient
the flip rates for generalized
voter
models can be written in the form
2 Cx(A) : Zk--(l+ (I-2A(x)) [ 2 Pz-x +If) N A Pz-x ] ) ze (x+I 0) r] A ze (x
(4.2)
for s o m e and
k > 0 ,
I1 of Z d
probability density
Problems.
I 1 = J~ .
that
( I I . 7)
(4.Z)
from
(2..4) .
has a cancellative
What other systems
I0
By a constant change
X = I .
Show how to get
voter models of section with
and disjoint subsets
such that I0 U II = support p = {z : Pz > 0} .
of time scale, one can a s s u m e
(4.3)
p = (Pz ; z ( Z d) ,
Show also that any of the
representation
have both additive
of the form
and cancellative
(4.Z)
represents-
tions ? The generalized Problem (1.3).
When
"voter component" on
Z1 ,
{ ( n tA) }
where
voter models for which I0/J~
and
and an "anti-voter
A0 = { e v e n i n t e g e r s } are both traps.
{ 0]tA)}
should result.
irreducible,
"
For the basic
(4.2)
We now prove this,
i.e.
and sufficient
to be ergodic.
the group spanned
density,
anti-voter
model
it is clear that
A I = {odd i n t e g e r s }
does not have traps,
we give a necessary
with flip rates
and
models of
the configurations
If w e m o d i f y t h e m o d e l b y t a k i n g
then the resulting
In fact,
component.
This is because
are the anti-voter
we can think of the model as having a
p is the simple random walk transition
is not ergodic.
ergodicity
I1/Jg
I0 = ~
1 P-1 = P2 = Z- ' so it seems
plausible
as an application
condition
we assume
p is all of
that
of Corollary
for a generalized
To a v o i d t r i v i a l i t i e s , by the support of
for example,
Zd .
(3.4).
voter model that
p is
78
(4.4)
Theorem.
some irreducible m
,
Let
{( A)}
density
z c I0 U I1 ,
be cancellative,
p .
with flip rates
of the form ( 4 . 3 )
for
T h e s y s t e m i s e r g o d i c if t h e r e a r e i n t e g e r s
only finitely many non-zero,
such that
Z
(4.5)
~ m z.z : 0
and
~ m z is odd. z ( I1
the s y s t e m i s n o n e r g o d i c .
Otherwise
i P-I = PZ : Z-
Note that the system having
is ergodic, since w e can apply
the theorem with m_l = Z , m Z : 1 . Proof.
The dual processes
for generalized voter models are annihilating
(~B)
r a n d o m walks with parity~
w e will verify (1.10) for these processes.
The argument
is based
(
s -> 0 ,
on comparison
of
which ignore the annihilation state space occupancy
and basic of sites.
) with processes rule after time
probability
) :
s •
) ,
Naturally we must enlarge the
s p a c e to a l l o w for m u l t i p l e
Using a more elaborate
, sa
(but finite)
graphical representation,
this can be
done in such a way that
(4.6)
~B ~B s~]t = ~]t
(4.7)
AB ~t
Let
~
behaves
be the extended
PBA(t):
P(~
for
s,
like independent
state
space for the
1
: (A,0)),
t s
PBA(t):
~(
random walks after time
AB (s~t)
: (A,1))
. .
s •
Write Define
0
sPBA(t)
and
s
pl
BA
v
analogously to
(i.10)
(4.8)
s~~ B t ,
in terms of
where
A
is a generic element of
S .
we want to show that
lira t--~
1
~ f{/A~
I p % A ( t )- pBA(t) l : 0 So v
The s u m may be e x t e n d e d
to
A e S ,
and majorized by
VB~
SO
According
79
+ 7A ~ ~s(t )
Is P B° A(t)
1 - sPBA(t) I
+~ s (t)+2s (t)
1
Z
3
To estimate the first two sums w e use the "fundamental coupling inequality" : if X1 a n d measure
XZ a r e ( g e n e r a l ) r a n d o m v a r i a b l e s g o v e r n e d b y a j o i n t p r o b a b i l i t y P,
a n d if
~1
and
lib- ~all -~ P ( x l / x z ) . s
~Z
are their respective
using ( 4 . 5 ) ,
+ ~ g ( t ) -~ Z • P ( t h e d u a l h a s a c o l l i s i o n b e t w e e n t i m e s
dual has a collision after
s ) •
AB (~t)
Since
which disappear with each collision,
apply the M a r k o v property at time
(4.9)
i.e.
lim t--~
i f t h e a n a l o g u e of
AB 10~]t ] = IBI
forall
lira s~
s to
s
t •
and
t>
s,
t ) -~ g • P ( t h e
h a s f i n i t e l y m a n y p a r t i c l e s t w o of s s s u p ()il(t)~_ + ~, (t)) = 0 . Next, t->s Z
s ~'3 (t) •
It follows that (I.i0) holds if
0 ]~ 7 A ¢ ~ [ 0PBA(t) - 0p IB ACt) [ = 0
(4.8)
then
t h e c o n c l u s i o n i s t h a t for
ms
~l(t)
laws,
h o l d s for t h e t o t a l l y i n d e p e n d e n t
B ~ ~,
process.
Clearly
Also,
o
0 P B A (t) = ~({0
= A} f] E0)
and 1 v iB 0 P B A ( t ) = P({0~t = A} N E1 ) ,
where
E0
(and E l)
are respectively the events that the total number of displace-
ments from I1 through time (and odd). in
t
by the
IBI independent random walks is even
Using these observations and
(4.9) is majorized by
(4.7), it is not hard to see that the sum
80
(4.i0)
0 E I P o z (t) - p l o z ( t ) z ~ Zd
]BI!
Consider
A = Zd x
coordinate.
{0,1}
as an additive
The one particle
walk which
starts
at
dual performs
( x , s) c A b y
1 ~0 i) p 0 z ( t ) = Pr(X ' = z) .
and ]B
be t h e s u b g r o u p o f
to
( 0 ~ i ) c ]B .
~
variation
abelian in
~,
norm in
B ,
group. so
yo
But
(4.11)
(4.10) tends
the proof of ergodicity (0,1)/
")-~/~
in the same irreducible
on a countable communicate
{(i,0)
when
then any
A 0 = { z : e z = 0} ,
we note that
A1 :
0
(4.5)
b ~ B
")11-o
Problem.
as
set of states (0,1) c B
holds for
to
Denoting '
: i ~ 11} , (4.5)
the = z)
and l e t
is equivalent
as
holds.
of a continuous
says that
x=
t--~
t--~
(0,0)
,
(0,0) y:
for each If
(4.5)
does
has a unique representation
{z : s z : 1} .
It i s e a s y
to check
time random walk and
(0,1)
(0,1)
.
B c SO .
Thus the This completes
not hold,
i.e.
if
b = ( z , Sz) . that
A0
and
Define A1 are
The proof is finished.
[]
S h o w that an anti-voter model is ergodic if and only if its density
p has odd period in Z d , i.e.
(4.13)
.
p o z ( t ) = Pr(X
The h y p o t h e s i s
traps for {( A)} , so the system is nonergodic.
(4. IZ)
~
in the second
0
: i c I 0} U { ( i , l )
generated by T •
II~(×t~ x, y
a random walk on
(X x , a)),
]Let ~ =
mod Z
Now it is well known that
(4.11) for any
group with addition
Notes.
zd/grp(I I -'I I) = an odd positive integer.
This section is adapted from Griffeath (1977).
Our approach to
generalized voter models is based on the treatment of anti-voter models of Holley and Stroock (1976d). Anti-voter models were first studied by Matloff (1977).
5.
Annihilating
random walks.
For lineal
(e $) to
~,
cancellative
of the duals
(Zts)
systems
are identically
and we get the symmetric
duality
P(q n Bleven)=
{(~tA)}
0,
the second
coordinate
so we can discard t h e m
processes
~
reduces
equation
Aleven)
S.
S0
81
[ u s t a s in t h e a d d i t i v e l i n e a l s e t t i n g , on a l l o f
(5.1)
S •
W e s t a t e t h e a n a l o g u e o f T h e o r e m (II • 3.1) ,
Theorem.
structure
P ,
t h e d u a l c a n b e e x t e n d e d to a M a r k o v f a m i l y
Let
{(TIt ); AB
substructure
•
{iDA)}
be the c a n c e l l a t i v e s y s t e m i n d u c e d by a l i n e a l s u b -
B { S}
For e a c h
(5.Z)
the l i n e a l c a n c e l l a t i v e s y s t e m i n d u c e d by the dual t > 0 ,
~A(B)
There is an i n v a r i a n t m e a s u r e
but omit the e a s y proof.
A,B c S,
at l e a s t one f i n i t e ,
AB = $ t CA)
•
v { ~
such that
~!
pt
~
v
as
t ~o
Moreover,
ergodic
{( A)}
<
>
<' >
v = 6@ /XA
A
P(T~
< ~o) = 1
VA{
S0 .
The r e m a i n d e r o f t h i s s e c t i o n w i l l b e d e v o t e d to o n e o f t h e s i m p l e s t t y p e s o f lineal cancellative system: Example (I.1.3), arbitrary.
the annihilatinq random walks.
except that the transition density
Alternatively,
T h e s e a r e d e f i n e d a s in
p = ( P z ; z ~ Zd)
can be
t h e y a r e t h e e x t e n d e d d u a l s y s t e m s for v o t e r m o d e l s in
their cancellative representations.
They s h a r e m a n y f e a t u r e s w i t h t h e c o a l e s c i n g
r a n d o m w a l k s o f S e c t i o n (II • 9 ) , b u t i n t e r e s t i n g and s o m e t i m e s s u r p r i s i n g d i f f e r e n c e s arise. Let u s f i r s t p r o v e e r g o d i c i t y .
1ust a s for t h e c o a l e s c i n g r a n d o m w a l k s ,
expects collisions to yield a limiting measure of In f a c t ,
t h e t w o t y p e s o f r a n d o m w a l k s w i t h i n t e r f e r e n c e for g i v e n
defined on the same substructure
E r g o d i c i t y of
(5.3) density
6j~ s t a r t i n g from a n y
{0]A)}
Proposition. p.
t h e n f o l l o w s from t h a t o f Let
quantities
{(DA)}
{(~tA)}
,A
Z
~ { ~ •
p can clearly be
<
for a l l
t
( P r o p o s i t i o n (II • 9.1) ) :
be the annihilating random walks with transition
Then
V
Since
in such a way that
A
A
D£" C [£',
pt
~
one
as
t-- ~
Vb ( ~ .
and the distribution of the latter tends to
6@,
the
82
P (A C n A) P(A C [A) are of interest for large case.
t .
Here w e c o m p u t e the limit only in one very special
Arratia (private communication)
tends to Z- IAI
has recently proved that the a b o v e ratio
for the basic models in any dimension A
(5.4)
Proposition.
Let
lim t--~ Proof.
A
{(~[~)} and
r a n d o m walks respectively on
Then
P (0 e n Z)
1
P(0 ~ [ Z )
2.
d ,
and for arbitrary transition function
Zd P(0 ~ ~qt ) "
P(O ~ It where
(~:)
{(nt~)} be basic coalescing and annihilating
Z .
In any dimension
Zd
d .
P(It~Ol°dd) P([~: / 9'1
)
'
is the corresponding voter process starting at
I intuitively clear that this ratio should always tend to ~- ,
proved by R. Arratia for d > l .
p ,
When
d = 1 and
{0} .
It s e e m s
a fact which has been
I P-I = Pl = 2- ' the reflection
principle yields f]
1
L
4-gi-
P
,
(cf. T h e o r e m
(II. 7.11)), w h i c h proves the claim.
(5.5)
Problem.
walks,
compute
1
ICoddl - ' - ~ '
"
as
t--o
z4~t []
For the basic one dimensional annihilating and coalescing r a n d o m
P({0,1}c n z) lira t~co
p({0,1}
C
~Z)
Next w e derive asymptotics for the m e a n interparticle distance in the basic annihilating r a n d o m walks on (II • 9.7),
Z .
The result is similar to one of the Problems
but a curious distinction arises.
83
(5.6) Theorem
Theorem.
Let
b = bf
be a renewal m e asure
(II • 4. ~) ) such that the distribution of f ;~f is aperiodic.
for the m e a n interparticle distance in A is the basic one-dlmensional
(5.Z)
(5.~/)
holds
there are mixing translation
invariant
in
for any product invariant
mixing,
:
D ( , t ~)
The integrated form of
Manipulating
D (A)
If
(~]~)
annihilating r a n d o m walks starting from
measures
(5.2)
~ /
6fff ,
~
k~ ,
0 { (0,1)
such that
(II. 7.11) ,
then
.
(5.7)
However, does
one first shows
not hold
that if
then
,~)]-1
[P(O c
~ ~
P-probability.
measure
Using the same method as in Theorem
is translation
Write
(provided it is well-defined).
D (ntb) - : 2~J-~-~ ~-
lim t~
In particular,
Proof.
(defined as in the proof of
P
-
a.s.
is
this we get
A0
12, P(rlt ~ }~) =
-
P(0 c ~t~)
~ [ ~ 1 ~ AO Nt)-2-
1 '
A0 ~t / ~ ]
"
1
Choose
g(t) = o(t 4) ,
such that
g(t) ~co 1
,
t~
and estimate
A0
A0
-<47-~(o< I~tI -~g(t))
(5.8)
+
(l~%vl)
1
SUp [x,y]
Recall that
as
is a rate Z
" y-x
We
A0
/~).
simple r a n d o m walk starting at 1 and with --
absorotion at 0 .
A
'~'l~pl~([x,y])-~-I~-{-P(~t > g(t)
A0
have already noted that ~jt P(~t /~f) -- ~/-~-
--i
as
t ~ co , while the reflection principle and central limit theorem imply that the first term on the right side of (5.8)
tends to 0
as
t-- ~ •
To conclude that
84
1
lim
q~- P(O ~ I]~) = Z
A0 P(~]t / 9 ) :
lim
1
z47-
it suffices to check that
(5.9)
1
llm n ~ ¢ ~
Let on
~
be
~l-distributed,
A ~ SO .
and write
NA(OJ) = I ~o N A I = t h e n u m b e r o f r e n e w a l s
Define
p n = ~ { N [ l , n _ l ] evenl~(0): i} , and note that
n -> 1 ,
(pn) satisfies the renewal equation n-1 Pn = a n + E k:l
(f ~ f)k Pn-k '
¢o
=~
By h y p o t h e s i s
fn k:n theorem asserts that
where
an
¢o
kEl= ~
Pn--
f ¢ f
is aperiodic,
and so the renewal
oo
~k=
f~
m l -- Z--m = Z-
as
n--=
k =~jl k'(f ~f)k The rest of the proof of
(5.9) is routine.
the aperiodicity condition, and s h o w
(5.7) for any renewal
example of a mixing translation invarlant with
b8
,
By working harder one can dispense with ~ .
To get an
[~ such that (5.9) does not hold, start
~ c (0,l) - { } } , and consider the "border measure"
~(~
defined by
N
~8(A)=
~(~{A : A(x-l) : A(x) , x ~ A }
There is a "border equation" which connects
~t~
and
AbL ~t "
It is based on the
observation that the "borders" between voters of opposite opinion execute annihilating random walks. x,y~
Z,
Thus, for any
[z ~ M
and its corresponding
t->O, N
P(l~t ~ N [x+l,y] Using this equation
and Theorem
i All f~ I e v e n ) = P(~]t (x) = ~ t ( y ) ) "
(II. 7.11),
it is easy to see that
~ ( • ,
85
lira E[ D(~]t ) t--~o --~-~----] =
if
1 6 / ~-
8 ~ (0, I) ,
D( lim
t ~o~
E[
0)] __
4t
~ - Z~(I-~)
The proof is finished.
/
2~-~--
[]
Something like the renewal assumption is apparently necessary in Theorem (5.6) in order to guarantee a certain uniformity of the spacing of the particles.
The
result is especially interesting because it gives an example of limiting behavior which is insensitive to density but feels some of the other structure of the initial ~ . To conclude our discussion of annihilating random walks, question of "site recurrence" :
w e consider the
is the origin occupied at arbitrarily large times?
The easy Problem (If • 9.5) asserts that the answer is yes for irreducible recurrent coalescin@ random walks whenever is altogether different. and let where
A
A / @ •
For annihilating
To see this, let d = 1 , choose
be an initial configuration of the form A =
1 < x I <Xl+l < x Z < xz+l < .-.
By letting
p irreducible recurrent,
{l,Xl,Xl+l, Xz,Xz+l, "''} , xi+ 1 - x i
sufficiently fast, one can ensure that for all sufficiently large starting at x. and
x.+l
1
every site of to A ,
Z
tend to
i the particles
annihilate one another before either has a chance to
1
collide with any other particle. to one eventually,
(~]A) , the situation
The remaining odd number of particles will reduce
which will perform a recurrent random walk from then on. will be visited infinitely often.
By adding a single particle at 0
the recurrence property is changed completely.
visited only finitely often.
Thus
N o w every point of
Z
is
The annihilating case is evidently m u c h more delicate
than the coalescing case.
(5.10)
Problem.
Let
infinite configurations
{([A)} A, B
be the basic one-dimensional voter model.
Find
such that
Tl t f
f(~
) ds ~
f(]~)
P- a.s.
Vf~C,
~o t
]
P(+ J
t~
f( fl ds
fails to converge)=
i
for some
C .
0
(Hint :
one approach is to use the "border equation" and the discussion of the last
86
paragraph. )
Thus,
in contrast to the biased voter model,
the pointwise ergodic
behavior of the unbiased voter m o d e l is unstable. Starting from "nice" initial states with any transition density matters simple, (II. 9.Z)
(5.11) p .
A , the annihilating r a n d o m w a l k s
p in any d i m e n s i o n
let us consider
A = Zd ,
d
are point recurrent.
(~]A)
To k e e p
in w h i c h c a s e a theorem corresponding to
c a n be proved.
Theorem.
Let
{(~]A)} b e a n n i h i l a t i n g r a n d o m w a l k s on
Zd
with density
Then
P(lim sup
Zd ~]t (0):
i):
i .
t ~co
The p r o o f i s s o m e w h a t i n v o l v e d ,
so we will only s k e t c h it.
p r o c e e d by c o m p a r i s o n with the c o a l e s c i n g c a s e .
In T h e o r e m ( I I . 9 . Z )
s h o w n that the e x p e c t e d a m o u n t of t i m e t h a t t h e v o t e r p r o c e s s absorption is infinite.
The idea is to
(~O)
It follows that the expected a m o u n t of time
it w a s
l i v e s before (~O)
s p e n d s in
states of odd cardinality before absorption is also infinite, and this is precisely the Zd expected a m o u n t of time that 07 t ) occupies 0 . H o w e v e r the estimates on P(T t ~ [t, u] ) w h i c h were used for the coalescing w a l k s only yield
P(lim sup
Thus w e n e e d a
0 - I l a w to finish the proof.
is spatially mixing,
lim
0y
O n e approach is to s h o w that
Zd (~t )
in the sense that
lyl
where
Zd nt (0) = i) > 0
is the shift
-
P(F N ~ Y G ) =
P(F)P(G)
~
oY(x) = x + y ,
able with respect to the process
(~tzd ) .
and
F
Taking
and
G
are any events m e a s u r -
E x : {lim sup
Zd Tit (x)= i}
t~co
E =
(-'I Ex and noting that E = B Y E for all y , w e get P(E) = 0 or 1 . x~ Zd ' The p r o o f i s c o m p l e t e d by s h o w i n g t h a t if P(Eo) > 0 , t h e n P(E) > 0 , a n d h e n c e
P(E O) = P(E) = 1 .
Note t h a t we make u s e of the t r a n s l a t i o n i n v a r i a n c e of
6zd
in t h i s a r g u m e n t . Another approach,
which works when
p i s t r a n s i e n t r e l i e s on t h e f o l l o w i n g
87
0 - 1
law.
(5.1Z)
Lemma.
density
p,
Let
{(Nt~)} ~
be annihilating
random walks
on
with a transient
Zd
and denote
A__ {lira sup ~]A(0)-- i} . t ~oo
Then
P(E A) : 0
or
i
for each
p(EAU
p(E A)
Ac
S,
and
Proof. from
For each x ,
all walks
processes however,
x ~
(H A)
zd
,
B)_
independent
and governed
can be represented
(~t {x))- = (Xtx)
are independent.
i.e.
E A-x
and
S,
Bc S O •
(< ) be a random walk with density
let
on this
that this is not the standard
EA
A~
We
by a joint probability space
graphical
s h o w that for any
differ by a P-null set.
p(EAU
B) = p ( E A)
( X tx ;
t -> 0 ,
0 - I A~
z ~ Z d)
S ,
law applies: B c S0 .
P •
way. e.g.
x~ A,
The
Note, the
processes
E A -x '
EA
It will follow that, up to ~
E A does not depend on the trajectories of any finite number of walks hence the Kolmogorov
starting
law
in the obvious
representation:
p
(Xt) , and
This will also yield
Fix a particular
of the independent
walks.
realization
For
Ac
S,
y ~ Zd ,
let
m
nA be the total number of arrivals 0 s nA < = effects"
Now suppose
which determine
at
0
x0 ~ A
by particles
in
(~]A) .
Thus
is removed.
This sets off a "chain of x0 t h e v i s i t s o f (X t ) to 0 b e f o r e i t
First of all, x1 collides with some other "living" walk (X t ) m u s t b e s u b t r a c t e d f r o m n A . Next, x1 x0 t h e v i s i t s o f (X t ) t o 0 from the collision time with (X t ) u n t i l t h e n e x t xZ x0 collision with a living walk (X t ) m u s t b e a d d e d t o n A . This is because (X t ) x1 no longer annihilates (X t ) . The chain continues in this manner, with alternating positive forever.
and negative
If w e c o n s i d e r
nA_ x .
contributions, the unique
either indefinitely,
trajectory
formed by those
or until a walk lives portions
of the walks
X.
(X~ 1) w h i c h
are involved
in the chain of effects,
one can check
that as a
88
P-stochastic
p r o c e s s it i s s i m p l y a r a n d o m w a l k g o v e r n e d by
assumed transient,
s o it v i s i t s
0
only finitely often.
a l t e r n a t i n g p o s i t i v e a n d n e g a t i v e c o n t r i b u t i o n s to time on with
P-probability one.
Hence
nA_ x
p .
This w a l k i s
In o t h e r w o r d s ,
n A - hA_ x
are a l l
0
the from s o m e
i s i n f i n i t e i f a n d o n l y if
nA i s .
This c o m p l e t e s t h e p r o o f .
(5.13) Problem.
A s s u m e that
p
With
is recurrent.
EA
defined as above,
use
the standard graphical representation, and Proposition (I.Z) in particular, to s h o w that p(E A) : p ( E A U
whenever
A~
S ,
B c S 0 o A D B : £f
(5.14)
Problem.
1 Z
product measure.
1 Z
Let
(It E)
B)
and
IBI
is even.
be the basic voter process on Z
starting from
Does the voter at the origin change opinion infinitely
often?
(5.15)
Notes.
Annihilating random walks were f i r s t c o n s i d e r e d by Erdos and Ney
(1974), w h o c o n j e c t u r e d t h a t t h e b a s i c o n e d i m e n s i o n a l p r o c e s s recurrent.
(~]Z-0)
was site
T h e i r c o n j e c t u r e w a s c o n f i r m e d in v a r i o u s n e a r e s t n e i g h b o r s e t t i n g s by
A d e l m a n (1976),
L o o t g i e t e r (1977)
for g e n e r a l t r a n s i t i o n d e n s i t y
a n d S c h w a r t z (19~/8).
p and dimension
t h e a p p r o a c h h e r e i s b a s e d on t h a t p a p e r . annihilating random walks r e s p e c t to t h e
"~=
G r i f f e a t h (1978b),
0 "
The r e c u r r e n c e q u e s t i o n
d i s s t u d i e d in G r i f f e a t h (1978b);
H o l l e y a n d S t r o o c k (1976d)
identified the
{0] A) ; A c SO} a s d u a l p r o c e s s e s for v o t e r m o d e l s w i t h basis.
Theorem (5.6)
i s t a k e n from B r a m s o n a n d
where additional results on the
d i m e n s i o n a l s y s t e m may b e f o u n d .
"dispersion"
of the b a s i c one
CHAPTER
IV:
UNIQUENESS
AND
NONUNIQUENESS
i. Additive and cancellative pregenerators. This final chapter deals with the uniqueness problem for additive and cancellative systems : When
do the local dynamics of {(~A)}
and
{( A)}
uniquely determine the
particle system? We
will concentrate on the additive case ; the analogous results for
cancellative systems will usually be left as exercises.
To formulate uniqueness
questions rigorously, one makes use of the generator of a M a r k o v process ; w e will a s s u m e throughout this chapter that the reader is familiar with generators. Let ~ induced by
~ .
configuration that =
~A
be a percolation substructure,
A
Recall that w h e n the is replaced by
denotes those
L.) ~A A ~ SO
precgenerator
' and G : ~
and consider the additive system
i'th clock at x
~/i,x(A) (as defined in (I. 2.2)).
f:S~ R
i n d u c e d by
Gf(A)= (Our assumptions on
~
~
~ ki,x[f(~i,x(A)) i,x
ensure that
G e of G
Similarly, clock at ~[i, x (B) G :~ ~ C
x
,
Define the additive
as
Gf ~ C
- f(i)]
for each
there is a unique additive system with substructure extension
R e m e m b e r also
which depend only on sites in A
C = {continuous f : S-- R } • C
goes off at rate ii, x '
P
f¢ ~
.)
We
say that
if there is a unique
which is the generator of a M a r k o v process.
consider the cancellative system induced by
goes off at rate
ki, x '
P
When
the i'th
configuration A ~ S is replaced by
(cf. the first paragraph of (III • 1 ). ) induced by
P •
The cancellative pregenerator
is
Gf(A) =
ki, x [ f(~[i,x(A)) - f(A)] i,x
(Again, our assumptions on
ensure that
cancellative system wlth substructure
G f ~ C .)
There is a unique
~ if there is a unique extension
which is the generator of a M a r k o v process.
G e of G
90
In Chapters
Z and
(i.1)
3 w e m a d e the assumption
P ( i n f l u e n c e from ~ ) : 0
to ensure that {(%A)}
and
{(hA)}
be Feller.
If (1.1)
genuine alternatives to the canonical definitions
d o e s not h o l d ,
( I I . 1.1)
and
(III.l.1)
then arise.
In the additive setting,
~
(l.Z)
= {x: NtA(xl > 0 o~
s~onginfluenceto
(×,t) from ~ }
and
(1.3)
A = {x : NA(x) > 0 or influence to (x,t) from ~ }
also define systems with pregenerator
G •
The s i m p l e s t n o n u n i q u e n e s s e x a m p l e s
a r i s e in t h i s m a n n e r .
(i. 4)
Problem.
Consider flip rates on Z of the form Cx(A) = x Z [A(x) + ( l - Z A ( x ) ) A ( x + l ) ]
x -> 1
: 0 Show that rates.
(II.l.1)
and
(1.3)
x-<0 define distinct additive spin systems with these flip
N o t e t h a t jZ i s a t r a p for t h e c a n o n i c a l s y s t e m
{([A)} ,
b u t n o t for
{(~)} (1.5)
Problems.
Prove that {(ETA)} and
{(~tA)} ~ as defined by (I.Z) and
(1.3) respectively, are always Feller systems. uniqueness, the canonical system
{(%A)}
Conclude that in the case of
given by
(II .1.1)
O b s e r v e t h a t w h e n w e a k i n f l u e n c e from oo arises,
is always Feller.
and
are
distinct.
(1.6)
Problem.
Give an example where
coincide with the canonical
Uniqueness,
{([A)} .
like ergodicity,
Say t h a t t h e r e i s a n e x p l o s i o n from
{(~A)} , as defined by
Is {([A)}
(I.Z) , does not
Feller in this case?
can be s t u d i e d with the aid of dual p r o c e s s e s . (x 0 ' 0)
at time
t in ~
if t h e r e a r e s i t e s
91
x 0,x I, .--
in (i)
Zd
and times
there is a path from
(ii)
lim n~
(iii)
IXnl = -
lim
t
(1.1)
is clearly
equivalent
by
special
systems
@ when
(1.1)
discussed
holds.
processes
v B (It)
introduce
and
the first explosion
and
vB (~]t)
them to the trap
precisely A
at time
Z
B ~ SO ,
3
and
from
m
systems
for all of the
one can define
the minimal dual ~
•
To
VB m ,
at
t
( B , 0) ).
from some
Define Z
v
Let
obtain uniqueness
in terms of the dual substructure
as in Chapters vB
and cancellative
3 .
P ,
time
explosion
~o i f t h e r e i s n o e x p l o s i o n
vB (It)
of the additive
substructure
v B 0Gt ) ,
VB "c = i n f {t :
(1.8)
= 1 •
We will thereby
in Chapters
Given any percolation
(:
to
goal is to prove uniqueness
induced
n->l,
,
(no explosions)
Our immediate
for each
(x n , t n)
= t <
(i.7)
do so,
(x 0 , t o ) t o
n
n~co
Condition
such that
0 = t o < t 1 _< t Z -< . . .
G
and
(x,0),
x~
B}
the minimal dual processes 3
for times
be the "Q-matrix"
vB t < T , operator
and send
for the
v
minimal dual system functions
of denumerable
introduce
;
Gf
is defined
the functions
fB(A)
fB (A)
S,
processes
f .
Finally,
A,B~
Markov
=
i
if
An
=
0
if
ANB/~
-~ 0
B =
,
and
gB(A,0): :
1 if
I A N BI e v e n
0 if
IA N B I o d d
g B ( A , 1) = 1 - g B ( A , 0 ) ,
gB(A) ~ 0
,
for bounded
92 A, B ~ S
and
at l e a s t one f i n i t e .
Also,
put
gB(A): gB(A,0)
Ac S,
B~ S O •
In the n e x t s e c t i o n we w i l l u s e m i n i m a l d u a l p r o c e s s e s {fB(A)} and
{gB(A, s)}
and t h e " f u n c t i o n b a s e s "
to o b t a i n u n i q u e n e s s t h e o r e m s for a d d i t i v e and c a n c e l l a t i v e
particle systems. (1.9)
Notes.
(1977),
The m a t e r i a l in t h i s c h a p t e r e x t e n d s r e s u l t s of Gray and G r i f f e a t h
b u t t h e g r a p h i c a l a p p r o a c h is n e w .
Some o t h e r p a p e r s on the u n i q u e n e s s
of p a r t i c l e s y s t e m s w h i c h a p p l y in g r e a t e r g e n e r a l i t y are L i g g e t t S u l l i v a n (1974),
H i g u c h i and Shiga (1975),
(1972),
H o l l e y and Stroock (1976a),
Gray and
G r i f f e a t h (1976) and L i g g e t t (1977).
Z.
Uniqueness theorems. We
n o w state and prove two l e m m a s which connect systems with pregenerator v
G
to the minimal dual with Q-matrix
(Z.1)
Lemma.
If
{(~A)}
G •
is a d d i t i v e with p r e g e n e r a t o r
G,
and
G is t h e
corresponding dual operator, v
GfB(A) : GfA(B)
Similarly, if
{(0
)} is c a n c e l l a t i v e ,
A~
S,
with pregenerator
B ~ SO •
G and d u a l o p e r a t o r
G,
then v
GgB(A)= Proof.
We
GgA(B,0)
check only the additive case,
Ac S,
B~ SO •
since the cancellative computation is v
very similar.
The additive dual operator
: 2 1,X
where
h , x [f(
G
obtained from ~
i,x (sl) - f ( s l ] ,
has the form
93 v
f
9"Ii,x(B) = U
y~B A
= Fix
A~ S ,
B c SO ,
Wi,x(y )
if
Vi,x N B= 9
if
Vi,xN
B/}~
and n o t e t h a t w
9/i,x(A) N B = ~
ifand onlyif
9/i,x(B) N A:JZ
and Vi,x: J~ .
Thus, G f B ( A ) = i~, x ki, x [ fB (~/i, x (A)) - fB(A)] v
ki
~' i,X :
x[fA(~ii,x
(B))- fA (B)]
VI,xN B=~
i,x : nB/ja l~X
xi,
x
[%(a) - %(B)]
v. v
: QfA(B)
[]
For t h e l e m m a w h i c h f o l l o w s ,
and t h e r e s t of t h e c h a p t e r ,
we i n t r o d u c e t h e
notation
Ptf(A) =
E [f([A)]
u~(B) =
PtfB(A ) ,
Ptf(B) :
~[f([t )]
v
A~ S ,
B c SO .
Note that
captures the basic cancellative
G .
Lemma. Forall
Let
t_> 0 ,
{([A)} Ac S,
B
PtfB(A)= P ( [ A N B = £ { )
p r o b a b i l i t i e s of t h e a d d i t i v e t h e o r y .
(Z.Z)
v
Similarly
basic cylinder
ptgB(A ) : Z P(I~] A N B[ e v e n ) - 1
probabilities.
be a d d i t i v e ,
with p r e g e n e r a t o r
B ( SO ,
du A (B) v t dt - GUA~B;"' ~ and
are s i m p l y t h e
G and d u a l o p e r a t o r
94
u1(B ) = fA(B) • Analogous equations hold in the cancellative setting, with ed by
gB(A) and
Proof. v
We
g A B , 0)
fB(A) and
fA(B) replac-
respectively.
present only the additive case.
Fix
A ~ S ,
B ~ S O , and write
v
Then by standard semigroup theory, L e m m a
YB(A) = GfA(B ) •
(Z.I) and Fubini's
theorem,
dut(B)
dptfB(A )
dt
dt
: pt G fB(A)
= Pt~B(A )
: GUA(B ) . The equation for t = 0 is trivial.
Thus,
u (B)
and
[]
vptf A(B)
satisfy the s a m e "backward" differential
equation with the s a m e boundary condition at t = 0 . follows from this fact.
A general uniqueness theorem
To state it, w e introduce
VB VB )c vT B= i n f { t < TA : I t N bn(O . / J f f } n
(the empty
inf is + co ) in t h e a d d i t i v e c a s e ,
w i t h t h e a n a l o g o u s d e f i n i t i o n in t h e
cancellative ca se. A
(Z.3) Theorem.
If for every additive system
substructure
(i.e. for every system with the additive pregenerator
by
{(St')} induced by a given G
induced
P),
(Z. 4)
lim n~oo
VB t-T n vB ~ B [uA (~v B ), n -< t] : 0 T n
t h e n t h e r e i s a u n i q u e a d d i t i v e s y s t e m i n d u c e d by
defined by
(II.l.l).
w h e n unique,
{(~?tA)}
VA ( S ,
.
It i s F e l l e r ,
B ( SO ,
and may b e
An a n a l o g o u s a s s e r t i o n h o l d s for c a n c e l l a t i v e s y s t e m s ; is Feller,
a n d may b e d e f i n e d by
( I I I . 1.1).
95
Before p r o c e e d i n g to p r o v e T h e o r e m (Z . 3 ) , (1.7) (2.5)
we d e r i v e the i m p o r t a n t f a c t t h a t
(or e q u i v a l e n t l y (1.1)) y i e l d s u n i q u e n e s s . Corollary.
If
~(no explosions) = 1 ,
s y s t e m and a u n i q u e c a n c e l l a t i v e Proof.
The e x p e c t a t i o n in
VTn =~VnB A t ,
(Z.3). v B V%r = %r "
P •
and i t s a n a l o g u e in t h e c a n c e l l a t i v e s e t t i n g are
~.vB t~(T n -< t ) ,
~ ( TV nB -< t ) =
lim n~oo
Proof of T h e o r e m
s y s t e m i n d u c e d by
(2.4)
m a j o r i z e d in a b s o l u t e v a l u e by
t h e n t h e r e is a u n i q u e a d d i t i v e
and
~ (explosion from
Fix
A~
S,
B~
For any function
(B,0)
,~ s A Tn
is a
P-martingale for each
0 .
[]
if w e set
v ) f ( t - r , ~ rv ) d r , + G v
A
M
t)=
S O , t > 0 , and write v f (t-r, %r) ' 0 -< r -< t ,
M s = f((t-s) + , ~(s A t)) - fS A t ( d 0 then
bytime
n .
Take
t-r v
f(t-r, ~r ) = u A
(~r) ,
v
and note that for
r ~ [0, ~n]
, v
(~? +d by L e m m a
G)f(t-r,
d
Thus the e q u a t i o n
(2.2).
v
t-r
v
%r) = (~rr + G) UA
(~r) = 0
M0 = ~ [ M~n ]
becomes
v
A
v
~
t-T n v
u t ( B ) = E [ f A ( % t ) ' ~ n > t ] + E[u A If ( Z . 4 )
holds,
t
/NvB
u (B) = P [ ~ t
(2.6)
Thus
then letting
Mpt
n~ ~
v "~n -~ t ]
•
we get V
f? A = @, "[n > t e v e n t u a l l y in n ] .
is uniquely defined for all
appropriate representation.
(~n)'
~ c ~ , t -> 0 ,
To see that
or derive the Feller property directly from setting is virtually identical.
{(~A)} (2.6) .
and
(II.l.l)
is Feller, either use
must be an Problem
The proof in the cancellative
[]
It turns out that uniqueness
can arise even w h e n explosions occur.
illustrate this possibility with a uniqueness result for proximity systems. analogy to the definitions preceding
VCe By
(II. 1.4), say that the minimal dual process
(1.5)
96 v B (It)
has a weak explosion
at
vT B
VB l~v B T
and a strong explosion
I<
~
,
-
vB z
a_tt
if
if
v B
I~VB
I=
~,
T
where
vB ~v B T
= -
v B ~t "
lira t f V~B
Roughly speaking,
if all explosions
are strong and
spontaneous births occur at a positive minimal rate, then uniqueness holds.
( z . 7)
Theorem.
Let
flip rates of the form
(i)
inf
Kx=
{(It)}
be a (canonical)
(II .Z . i Z ) ,
~
P
extralineal
its underlying
proximity process,
substructure.
with
If
O,
>
X
(ii)
sup x,A: x~A
Cx(A) = K < ~
,
and (iii)
v P (weak explosion
then there is a unique system
Proof:
It suffices to check
vB T )= 0
at
{([A)}
(Z .4) .
VB ~ S O ,
with pregenerator
G
induced
by
P •
An appropriate decomposition yields
vB
E'[UA
(~vB)'
n
-< t ]
Tn
AvB -< P ( ' c n
(a n )
c [t-6,
t])
(b n)
A vB vB + P ( T n < t- 6, I ~ v B 1 -> M). sup ~cn B:IBI-> M
(c n)
+ P(T n
< t,
I[vB T
for arbitrary
6 e (O,t]
,
M
~
0 .
Now
n
I < M)
sup u Z ( B ) s -> 6
97
lira s u p n--=
an
VT.. B
Let
=f
vB
P(~n ~ [t-6,t]
for infinitely
many
n):'P('~Se
v B (~t)
be the time of the first jump by
[t-6,t])
v B vB vB m : T¢ + ( ' ~ B _ m..) i s t h e
Since
independent s u m of an exponential variable and the remaining time, of
VB T
that
is absolutely continuous on .<
E
lim sup a n - ~n
(0, =) .
Next w e take
M
.
the distribution
Thus w e can choose
large enough that
bn
6 > 0 <
g
~
so
for all n .
~
To see that this is possible,
w e first estimate
d u ; (B) ds = E[GfB([A)]
x~B
E[Cx([ A ), i sA n (B-x)= ~
+ ~
x~
sA]
x~B
-I I ,u;
<
x~B
u AS(B)]
-IS 1 KU/~(B)+ K [ I -
.
By G r o n w a l l ' s i n e q u a l i t y ,
K
S
UA(B)<which tends term of
and
M
bn
to ,
0
uniformly
in
so chosen,
note that
Example.
Thus
s -> 6
Consider
1
lim n~
(Z.4)
-(IBi ~ + K ) s
+ IBI K + K
bound the first by
again by hypothesis.
(z.8)
]BI K
IBI ~ + K
as
e
IBI ~
to e s t a b l i s h
c n : ?('~B -< t ,
holds,
the extralineal
co
This controls
the chain.
the second
Finally,
I~'B vB_ i -<M)= T
with O,
and uniqueness is proved.
proximity
system
on
Z
6
[]
with flip rates
of the form c x(A) = 0
=
I
if
x < 0
if
0 > x/
or
A
x ( A
or
and
An
at each
site
x -> 0
[0,x+l]
: J~
Z = i00 x
The substructure
~
for this
otherwise.
system
has
~'s
x
at rate
1 ,
and
98
Z for
x >- 0 ,
arrows arrive at
x
from every site in [0, x+l ] at rate I00 x
It is e a s y to c h e c k the h y p o t h e s e s of T h e o r e m e x a m p l e exhibits an unusual p h e n o m e n o n w h i c h merits a brief discussion. G
of
G
(Z.7), so u n i q u e n e s s holds.
This
in the theory of M a r k o v i a n semigroups,
G i v e n pregenerator
G,
one defines the closure
by B
graph ( G ) = Thus if
G
has domain
suchthat
llh-fnll--
is u n i q u e n e s s for
~9(-G) and
0
G,
graph (G)
and
h c ~9(-G) ,
II~h-Gfnil--
t h e n "G
(in C x C) .
t h e n t h e r e are f u n c t i o n s
0
as
is t h e g e n e r a t o r of
the c a s e w h e n e v e r t h e H i l l e - Y o s i d a T h e o r e m a p p l i e s . however,
if G e : ~ ( G e) -- C
~ ~ ~ ( G e)
such that w h e n e v e r
1 llGe~ - G fll > i-~ ' extending
(Z.9)
G
is not
Notes.
i.e. G
is the generator of fc ~
and
3.
Nonuniqueness
ifthere
In p a r t i c u l a r t h i s is
For t h e p r e s e n t e x a m p l e , {([ A )} , one can find a function , then
Thus the unique generator
in this case.
T h e o r e m (Z.3)
and E x a m p l e (Z.8)
Asarule,
{(%A)} .
II~- fll < ~1
9 c ~ ( G e) - ~(G) .
and C o r o l l a r y (Z.5)
a d d i t i v e s e t t i n g of r e s u l t s from H o l l e y , (2.7)
n--~
fn ~ ~
are a d a p t a t i o n s to t h e
S t r o o c k and W i l l i a m s (1977).
Theorem
are t a k e n from Gray and G r i f f e a t h (1977).
examples.
In this final section w e briefly discuss n o n u n i q u e n e s s possibilities for particle systems. considered.
To k e e p matters simple, only the additive setting will be
O n e of the simplest n o n u n i q u e n e s s e x a m p l e s w a s encountered already
in Problem (1.4) . in
~
For those flip rates, the presence of w e a k influence from
gives rise to distinct s y s t e m s defined by (II.l.l) and
there is a c o n t i n u u m of s y s t e m s with the flip rates of (1.4) . ture P
with w e a k influence from
~
(1.3) . Indeed,
In fact, a n y substruc-
gives rise to an infinite family of Feller
additive systems.
(3. i) Theorem. substructure
Let
f~ •
If
G
be the additive pregenerator induced by a percolation
99
~.vB /~[
< ~ ,
vB I~B
_] < = ) > 0
then there is a continuum
of distinct
More precisely,
be the maximal set in
let
A
for some
Feller additive
B~ S O ,
systems
with pregenerator G • vB such that A C ~vB ~ - a.s.
Zd
37
Then to each probability system
{ ( ~ A t) }
.Izd_
Sketch of proof: t ~ (0,~)
isolated
~
(Z d U {co})× T A t~
SO ,
w-distributed to
Zd
G
and semigroup
independent
If
draw arrows from
x ~ %A
S O U {A} ,
measure
and extend
as follows.
allowing for "influence
on
-
there corresponds ( P tw) ,
a Feller
where
W lzd_A
Given a probability be
point
w
with pregenerator
4/if A t,
measure
At=
(A t , t )
through
~
co . "
on
S O U {A} ,
random variables.
to a percolation
A ,
to
~
label
(~,t)
(co,t)
.
let Adjoin an
substructure
with a
~ ,
~
on
while if
We may think of these
arrows as
Now say that
if
(i)
there is a path up to
(x,t)
from
(A,O) ,
(ii)
there is a path up to
(x,t)
from some
possibly
"through
co , "
or
y ~ Zd U { ~ } ,
the path again possibly
( y , s)
labelled
"through
~ ,
~ , "
or m
(iii)
there is strong influence
(iv)
there is a path d o w n f r o m
from
=
to
( x , t)
or
visits to
A path only enters at time
s .
We
o~
Zd × T
(x, t) in the reverse substructure w h o s e
h a v e an accumulation
from
(~ , s)
point.
if the reverse path " w a n d e r s off to ~
leave the precise formulation of the effects involving
as the details of the construction,
to the interested reader.
~
,
"
as well
O n e c a n c h e c k that
100
the system
hypotheses
{(%A
t)}
so defined is Feller with pregenerator
of the theorem,
different
Tr's
G,
and that under the
g i v e r i s e to d i f f e r e n t s y s t e m s .
[3
D~
(3.Z)
Problems.
(1.Z)?
Which measure
Which
~
Problem (1.4), are traps,
~
g i v e s r i s e to t h e s y s t e m
yields the system
{(~t)}
of
(1.3)?
{(It+)}
For t h e f l i p r a t e s of
construct a translation invariant system such that both
and one such that neither
of T h e o r e m ( 3 . 1 ) ,
]~
nor
Z
find additional nonuniqueness
is a trap.
defined by
}~
and
Z
Under the hypotheses
examples which are not covered
by the construction sketched above.
(3.3)
Problem.
c
for s o m e
Let
x
be a spin system on
Z
with flip rates x--< -i,
(i) : 0
rx > 0 ,
additive.
{( A)}
: r0[A(0 ) + (I-ZA(0))A(1)]
x=
: rx[A(x ) + (I-ZA(x)) (PxA(X+l) +qxA(X-l))]
x-> i,
0 < Px < 1 ,
with
Describe the dual processes
qx : i - Px • vA (%t) '
S h o w that
{(~A)}
O,
is
in particular the one-particle duals
Vx
(It) '
X c Z •
ness e xa mp le s
For general
as you can find.
Dynkin and Yushkevich
(3.4)
Notes.
r's and
p's ,
discuss as m a n y kinds of nonunique-
(You m a y want to m a k e use of Chapter IV of
(1969).)
The material of this section is b a s e d on Gray and Griffeath (1977),
although the graphical approach is new.
The simple nonuniqueness
(1.4) first appeared in Gray and Griffeath (1976). m a y be found in Holley and Stroock (1976a).
example of
Another nonuniqueness
example
Bibliography O m e r A d e l m a n (1976).
S o m e use of some "symmetries" of some random processes,
.
I
Ann. Inst. Henri Polncare IZ, 193-197. %
F. Bertein and A. Galves (1978). association,
Z. Wahrscheinlichkeitstheorie Verw. Geb. 41, 73-85.
D. Blackwell (1958). states,
U n e classe de systemes de particules stable par
Another countable M a r k o v process with only instantaneous
Annals of Mathematical Statistics Z9, 313-316.
M . Bramson and D. Griffeath (1978a). model,
Annals of Probability,
Renormalizing the 3-dimensional voter
to appear.
M . Bramson and D. Griffeath (1978b).
Clustering and dispersion rates for s o m e
interacting particle systems on Z , Annals of Probability, to appear. S. Broadbent and ]. H a m m e r s l e y (1957). mazes,
Percolation processes I. Crystals and
Proc. Cambridge Phil. Soc. 53, 6Z9-645.
I. Chover (1975).
Convergence of a local lattice process,
Stochastic Processes
and their Applications 3, 115-135. P. Clifford and A. Sudbury (1973).
A model for spatial conflict,
Biometrika 60,
581-588. D. D a w s o n
(1974a).
Information flow in discrete M a r k o v systems,
~ournal of
Applied Probability ii, 594-600. D. A. D a w s o n no. i0,
(1974b).
Discrete M a r k o v Systems,
Carleton Math. Lecture Notes
Carleton University, Ottawa.
D. D a w s o n
(1975).
Synchronous and asynchronous'reversible M a r k o v systems.
Canadian Mathematical Bulletin 17, 633-649. D. A. D a w s o n
(1978).
The critical measure diffusion process,
Z. Wahrscheinlichkeitstheorie Verw. Geb. 40, IZ5-145. D. D a w s o n and G. Ivanoff (1978).
Branching diffusions and random measures,
Advances in Probability 5, ed. A. yoffe, P. Ney,
Dekker, N e w York.
R. L. Dobrushin (1971).
Markovian processes with a large number of locally
interacting components,
Problems of Information Transmission 7, 149-164 and
Z35-Z41. R. Durrett (1978).
An infinite particle system with additive interactions, to appear.
E. B. Dynkin and A. A. Yushkevich (1969). Problems,
Plenum Press, N e w York.
P. Erdos and P. N e y (1974). particles,
M a r k o v Processes. Theorems and
Some problems on random intervals and annihilating
Annals of Probability Z, 8Z8-839.
102
I. Fleischmann
(1978).
T . A . M . S . Z39,
353-389.
Limit theorems for critical branching random fields,
H. O. Georgii (1976).
Stochastische Prozesse F{~r Interaktionssysteme.
Heidelberg. R. Glauber (1963).
The statistics of the stochastic Ising model,
Iournal of
Mathematical Physics 4, 294-307. L. Gray
(1978).
Controlled spin systems,
L. Gray and D. Griffeatb (1976). systems,
953-974.
O n the uniqueness of certain interacting particle
Z. Wahrscheinlichkeitstheorie verw. Geb. 35, 75-86.
L. Gray and D. Griffeath (1977). processes,
Annals of Probability 6,
O n the uniqueness and nonuniqueness of proximity
Annals of Probability 5, 678-69Z.
D. Griffeath (1975).
Ergodic theorems for graph interactions,
Advances in Applied
Probability 7, 179-194. D. Grlffeath (1977). .
An ergodlc theorem for a class of spin systems,
Ann. Inst.
I
Henri Pozncare 13, 141-157. D. Griffeath (1978a).
Limit theorems for nonergodic set-valued M a r k o v processes.
Annals of Probability 8, 379-387. D. Griffeath (1978b).
Annihilating and coalescing random walks on Z d .
Z. Wahrscheinlichkeitstheorie verw. Geb. 46, 55-65. D. Griffeath (1979). Probability 7,
Pointwise ergodicity of the basic contact process,
Annals of
13 9-143 o
R. Griffiths (1972).
The Peierls argument for the existence of phase transitions,
Mathematical Aspects of Statistical Mechanics,
~.C.T. Pool (ed.), S I A M - A M S
Proceedings, Providence, Amer. Math. Soc. 5, 13-Z6.
~. Hammersley
/
(1959).
processus de filtration.
process,
.
.
s"
Le Calcul des Probabilites et ses Applications.
National de la Recherche Scientifique, T. E. Harris (1960).
.
Bornes superzeures de la probablhte critique dans un Centre
Paris, 17-3 7.
Lower bound for the critical probability in a certain percolation
Proc. Cambridge Phil. Soc. 56, 13-Z0.
T. E. Harris (197Z).
Nearest neighbor M a r k o v interaction processes on multi-
dimensional lattices, Advances in Mathematics T. E. Harris (1974).
9, 66-89.
Contact interactions on a lattice,
Annals of Probability 2,
969-988. T. E. Harris (1976). Probability 4, 175-194.
O n a class of set-valued M a r k o v processes,
Annals of
103
T. E. Harris (1977).
A correlation inequality for Markov processes in partially
ordered state spaces,
Annals of Probability 5, 451-454.
T. E. Harris (1978). Additive set-valued Markov processes and percolation methods, Annals of Probability 6, 355-378. L. L. Helms
(1974). Ergodic properties of several interacting Poisson particles,
Advances in Mathematics IZ, 3Z-57. Y. Higuchi and T. Shiga (1975). Some results on Markov processes of infinite lattice spin systems, R. Holley (1970).
Journal of Mathematics of Kyoto Universit Y 15, ZII-ZZ9.
A class of interactions in an infinite particle system,
Advances
in Mathematics 5, Z91-309. R. Holley (1971).
Free energy in a Markovian model of a lattice spin system,
Communications in Mathematical Physics Z3, 87-99. R. Holley (197Za).
Markovian interaction processes with finite range interactions,
Annals of Mathematical Statistics 43, 1961-1967. R. Holley (197Zb). interactions,
An ergodic theorem for interacting systems with attractive
Z. Wahrscheinlichkeitstheorie verw. Geb. Z4, 325-334.
R. Holley (1974). Recent results on the stochastic Ising model, Rocky Mountain ~ournal of Mathematics 4, 479-496. R. Holley and T. M. Liggett (1975). Ergodic theorems for weakly interacting infinite systems and the voter model,
Annals of Probability 3, 643-663.
R. Holley and T. M. Liggett (1978). The survival of contact processes,
Annals of
P[obability 6, 198-206. R. Holley and D. Stroock (1976a). interacting processes,
A martingale approach to infinite systems of
Annals of Probability 4, 195-ZZ8.
R. Holley and D. Stroock (1976b). Applications of the stochastic Ising model to the Gibbs states,
Communications in Mathematical Physics 48, 249-266.
R. Holley and D. Stroock (1976c).
L Z theory for the stochastic Ising model,
Z. Wahrscheinlichkeitstheorie verw. Geb. 35, 87-101. R. Holley and D. Stroock (1976d). Dual processes and their application to infinite interacting systems,
Advances in Mathematics,
R. Holley and D. Stroock (1978).
to appear.
Nearest neighbor birth and death processes on the
real llne, Acta Math. 140, 103-154. R. Holley, D. Stroock and D. ~Villiams (1977). Applications of dual processes to diffusion theory, Proc. Sympos. Pure Math. 31, 23-36. Providence, R.I.
Amer. Math. Soc.,
104
F. P. Kelly
(1977).
The a s y m p t o t i c b e h a v i o r of an i n v a s i o n p r o c e s s ,
Journal of
.Applied Probability 14, 584-590. W. C. Lee
(1974).
Random stirring of the real l i n e ,
.Annals of Probability Z,
58O-592. T. M. Liggett (1972).
Existence theorems for infinite particle systems,
T.A.M.S.
165, 471-481. T. M. Liggett (1973).
A characterization of the invariant measures for an infinite
particle system with interactions, T. M. Liggett (1974).
T.A.M.S.
A characterization of the invariant measures for an infinite
particle system with interactions If, T. M. Liggett (1975). process,
T.A.M.S.
179, 433-453.
T.A.M.S.
198, Z01-ZI3.
Ergodic theorems for the asymmetric simple exclusion
ZI3, Z37-Z61.
T. M. Liggett (1976).
Coupling the simple exclusion process, Annals of Probability
4, 339-356. T. M. Liggett (1977). particles,
The stochastic evolution of infinite systems of interacting
Lecture Notes in Mathematics 598, 187-Z48.
T. M. Liggett (1978).
Attractive nearest neighbor spin systems on the integers,
Annals of Probability 6, K. Logan
(1974).
Springer-Verlag, N e w York.
6Z9-636.
Time reversible evolutions in statistical mechanics,
Cornell
University, Ph. D. dissertation. I. C. Lootgieter (1977).
Probl~mes de r~currence concernant des mouvements
aleatolres de particules sur Z avec destruction,
Ann. Inst. Henri Pomcare 13,
IZ 7-139. V. A. Malysev
(1975).
The central limit theorem for Gibbsian random fields,
Soviet
.Math. Dokl. 16, 1141-1145. N. Matloff (1977).
Ergodicity conditions for a dissonant voter model, Annals of
Probability 5, 371-386. D. Mollison
(1977).
Spatial contact models for ecological and epidemic spread,
]. Royal Statistical Soc. B, 39, 283-326. C. 7. Preston (1974). D. Richardson 74, 515-5Z8.
(1973).
Gibbs states on countable sets, R a n d o m growth in a tesselation,
S. Sawyer
(1976).
genetics,
Annals of Probability 4, 699-728.
S. Sawyer
(1978).
model,
to appear.
Cambridge University Press. Proc. Cambridge Phil. Soc.
Results for the stepping stone model for migration in population
A limit theorem for patch sizes in a selectively-neutral migration
~05
D. S c h w a r t z deaths,
(1976).
Ergodic t h e o r e m s for a n i n f i n i t e p a r t i c l e s y s t e m w i t h b i r t h s a n d
A n n a l s of P r o b a b i l i t y 4 ,
D. S c h w a r t z
(1977),
783-801.
A p p l i c a t i o n s of d u a l i t y to a c l a s s of M a r k o v p r o c e s s e s ,
Annals of Probability 5, 5ZZ-53Z. D. Schwartz
(1978).
O n hitting probabilities for an annihilating particle model,
Annals of Probability 6, 398-403. V. K. Shante and S. Kirkpatrick (1971). Introduction to percolation theory,
Advances
in Physics ZO, 325-357. F. Spitzer (1970).
Interaction of M a r k o v processes,
Advances in Mathematics 5,
Z46-zgo. F. Spitzer (1971). R a n d o m fields and interactingparticle systems, Seminar Notes, Williamstown, F. Spitzer (1974a).
M.A.A. Summer
Mass.
Recurrent random walk of an infinite particle system, T . A . M . S .
19__~8, 191-199. F. Spitzer (1974b).
Introduction aux processus de M a r k o v ~ parametre" s dans
Lecture Notes in Mathematics 390,
Z
v
Springer-Verlag, N e w York.
F. Spitzer (1976).
Principles of R a n d o m W a l k ,
F. Spitzer (1977).
Stochastic time evolution of one dimensional infinite particle
systems,
,
Znd ed. , Springer-Verlag, N e w York.
B . A . M . S . 83, 880-890.
O. N. Stavskaya
(1975).
Sufficient conditions for the uniqueness of a probability
field and estimates for correlations,
Matematicheskie Zametki 18, 609-6Z0.
O. N. Stavskaya and I. I. Pyatetskii-Shapiro (1968). spontaneously active elements, D . Stroock (1978).
O n h o m o g e n e o u s networks of
Problemy kibernetiki, N a u k a M o s c o w
ZO, 91-106.
Lectures on Infinite Interacting Systems, Kyoto University
Lectures in Math. no. Ii. W.
G. Sullivan (1974).
of random fields,
A unified existence and ergodic theorem for M a r k o v evolution
Z. Wahrscheinlichkeitstheorie verw. Geb. 31, 47-56.
W . G. Sullivan (1975).
M a r k o v processes for random fields, Communications Dublin
Inst., "Advanced Studies A, No. 23. W . G. Sullivan (1976).
Processes with infinitely m a n y jumping particles, P . A . M . S .
54, 3Z6-330. A. L. T o o m 9,
(1968).
A family of uniform nets of formal systems, Soviet Mathematics
1338-1341.
A. L. T o o m
(1974).
Nonergodic multidimensional systems of automata, Problemy
Peredachi Informatsii i0, Z39-Z46.
106
L. N. Vasershtein
(1969).
Markov processes over denumerable products of spaces,
describing large systems of automata,
Problemy Peredachi Informatsii 5 (3), 64-73.
L. N. Vasershtein and A. M . Leontovich
(1970).
Invariant measures of certain
Markov operators describing a homogeneous random medium,
Problemy Peredachi
Informatsil 6 (i), 71-80. N. B. Vasilev
(1969).
Limit behavior of one random medium,
Problemy Peredachl
Informatsii 5 (4), 68-74. N. B. Vasll'ev, L. G. Mityushin,
I. I. Pyatetskii-Shapiro and A. L. T o o m
(1973).
Stavskaya Operators (in Russian), Preprint no. IZ, Institute of Applied Math. , A c a d e m y of Sciences,
U.S.S.R. , M o s c o w .
T. Williams and R. Bjerknes
(1972).
Stochastic model for abnormal clone spread
through epithelial basal layer, Nature Z36, 19-ZI.
Subject Index Additive pregenerator 89 additive system 14 annihilating branching processes with parity annihilating random walks 5, 81 anti-voter model 67 Biased voter model box 1
55
Cancellative pregenerator 89 cancellative system 66 coalescing branching processes 24 coalescing random walks 3, 47, 58 configuration 1 contact systems 5, 44 critical phenomenon 30 cylinder function 2.2. Dense configuration 45 distribution Z domain of attraction 8 dual processes 16, 67 dual substructure ii duality equations 17, 68 Edge 5Z equilibrium 6 ergodic 7 exclusion system (additive) 64 explosion 90 exponentially decaying correlations exponentially ergodic system 19 extralineal substructure i0 extralineal system 14 extreme invariant measure 8 Feller system
7
Generalized voter models 77 Gibbs measures 74 graphical representation 3 Influence from oo 14 invariant measure 6, 7 [ump rates
Z
Lineal substructure I0 lineal system 14 local substructure i0 local system 14 Monotone system 14 minimal dual processes Neighbor
91
44
One-sided contact systems
29
20
73
108
Particle process 1 particle system Z path up 3, i0 percolation substructure pointwis e ergodicity 8 proximity system Z4 pure births 67
5,9
R a n d o m stirring 63 recurrent density 47 regular distribution 45 Self-dual substructure Z9 self-dual system Z9 site 1 spin system Z stochastic Ising model 74 strong correlations 53 strong explosion 96 strong influence from o0 14 strongly ergodic 7 substructure 5 T a m e function ZZ time reversible system 14 transient density 47 translation invariant substructure translation invariant system 14 Unique system Voter model Weak weak weak weak
89
ii, 46
convergence 6 correlations 53 explosion 96 influence from co 15
i0
