Z e i t s c h r i f t ftir
Z. Wahrscheinlichkeitstheorieverw. Gebiete 58, 423-432 (1981)
Wahrscheinlichkeitstheorie und v e r w a n d t e G e b i e t e
9 Springer-Verlag 1981
The Asymmetric Simple Exclusion Process on
Z a
Enrique Daniel Andjel* Universidade de $5o Paulo, Instituto de Matemfitica e Estatistica Caixa Postal 20.570 CEP-05508 S~toPaulo-Brasil
1. Introduction In 1-7] Spitzer introduced the simple exclusion process. This process describes the evolution of infinitely many interacting particles on a countable set S of sites on which a transition function for a Markov chain p(x, y) is given. The state space of this process is X = { 0 , 1 } s and the particles move according to the following rule: a particle at a site x waits an exponential time with parameter one and then attempts to move to y with probability p(x, y), this movement is allowed if y is vacant, otherwise the particle stays at x. All the exponential times and all choices of sites according to p(., .) are mutually independent. The existence of such a process is guaranteed by Liggett's existence theorem (Theorem l.2 in 1-13) under the mild assumption: sup~p(x,y)
x
process r/t obtained is a Feller process and its infinitesimal generator is the closure in C(X) of an operator F defined on functions f depending on a finite number of coordinates by:
r f ( ~ ) = y~ p(x, y) (f(t/xy) -fit/)) x, y e S
where t/xy is t/if r/(x)=0 or ~/(y)= 1 and t/xy is the configuration obtained from t/ by moving the particle at x to y if r/(x)= l and t/(y)= 0. Of course, for any given configuration of particles t/eX and a site x~S ~l(x) denotes the number particles the configuration t/ has at x. In this paper we will call S(t) the semigroup of operators having F as generator and #S(t) will be the distribution of the process by time t when the initial distribution is/~. Obviously I~S(t) satisfies
~fd(#S(t)) = ~S(t)fd#
for all
feC(X)
The long time behaviour of the simple exclusion process is well understood when p(x, y) is symmetric. This is due to the fact, pointed out by Spitzer in [-7], *
Partially supported by FAPESP-Grant 80-1161
0044- 3719/81/0058/0423/$02.00
424
E.D. Andjel
that the process is, in this case, self dual and that this duality allows us to reduce problems concerning and infinite number of particles to problems involving only a finite number of particles. For a survey of results in this case see [5]. However, very little is known when p(x,y) is asymmetric: in [2] it is shown that if p(x,y) is positive recurrent and reversible then all non trivial invariant measures concentrate on finite configurations and if the process starts with infinitely many particles it's distribution converges to the point mass at t/-= 1. Here again, the study of systems with a finite number of particles gives enough information to determine the behaviour of the infinite particle system. In [3] Liggett considered the case in which S = Z and p corresponds to a nearest neighbor random walk. Theorem 1.3 in [3] determines the limit of #S(t) when # is a product measure on X such that lim/~{t/:t/(x)=l}
and
X~Oo
lira #{t/:t/(x)=l} X~
--Oo
exist but are not necesarily equal. These results were later extended by the same author in [6] by dropping the condition p(x, y ) = 0 if ] x - y ] > 1. The interest of proving ergodic theorems, for the asymmetric case, with more general initial distributions is mentioned by Liggett in [6]. In particular it is pointed out there that if g is translation invariant it is only known that the weak limits of #S(t) are exchangeable and have the same density as #. In connection with this we prove the following two theorems: Theorem 1.1. I f S = Z e, p ( x , y ) = p ( O , y - x ) is the transition function for a random walk on Z e which is irreducible, in the sense that for all x e Z e there exists an n such that p(")(O,x)+ p(")(x,O) >0, and # is a translation invariant probability measure on X then #S(t)--,S#odg(p ) where g is a distribution function such that g ( 0 - ) = 0 and g(1)= 1 and go is the product probability measure on X satisfying: #o{t/: tl(x)= l } = p for all x s Z e. Moreover S pdg(p)=p{rl: r/(0)= 1}. Theorem 1.2. I f S =Z, p(x, x + 1) =p, p(x, x - 1) =q, p + q = 1 and # is translation invariant, ergodic and satisfies p{t/: r / ( 0 ) = l } = p o then pS(t)--*#o o where #oo is the product probability measure on X such that /~oo{t/: ~ ( x ) = l } = p o
for all x s Z .
The proofs of Theorems 1.1 and 1.2 are given in Sects. 2 and 3 respectively. It follows from Theorem 1.1 that all invariant measures which are translation invariant are mixtures of #o's 0 < p <1. This has already been proved in [4]. Note also that Theorem 1.2 permits to identify lim #S(t) for all translation invariant probability measures/~ on X. t~ To prove these theorems we will use a process on X x X having the following properties: 1) both marginals have generator F, 2) particles of different marginals occupying the same site move together as much as possible. This process, called the coupled process, has already been used in [4] and its genera t o r / ~ applied to a function f on X x X which depends on a finite number of coordinates is given by:
The AsymmetricSimple Exclusion Process on Z e
ff(~, ~)=
2
425
p(x, y) ( f (tlx,, ~) - f (tl, 4))
,1(x)=1,~(y)=o and ( ( x ) ~ ~(y) or {(x) = O, ~(y) = 1
+ E
p(x, y) (f(tl, ~y) --f(rl, ~))
~(x) = 1, g(y) =O and ~l(x) = rl(y ) or rl(x ) - 0 , q(y)~ 1
p(x, y) (f(~xy, ~xy) -f(tl, ~)) ~(x)-~(x)=
~(y)=~(y)=o
The existence of the coupled process follows from the results of [1]. S(t) will be the semigroup on C(X x X) generated by f and vS(t) will be distribution of the coupled process at time t given that the initial distribution was v.
2. The R a n d o m W a l k on Z d
In this section S=Za, p(x,y) corresponds to an irreducible random walk on Z d and #p denotes the product probability measure on X with marginals given by #p{~/: t/(x)= 1} = p for all x ~ Z d. The following proposition was already known (see [-5]). We include, however, a proof of it since none has been published. Proposition 2.1. I f # is a translation invariant probability measure on X then all
weak limits of #S(t) are of the form: ~ #p dg(p) for some distribution function g such that g(O- ) = 0 and g ( 1 ) = l . Proof. Let vp be the product measure/~ x/~o on X • X. Given a weak limit fi of #S(t) there exists a sequence tn--+oo and such that vo'3(t,, ) converges to a measure Fp with marginals fi and #p. On X • X we define the following functions: fy(r/. {)= l{,(y)=o. r
fxy(tl. r = l{,(x)=r
1} 1. r/(y)=~(x)=O}
where x and y are arbitrary elements of Z a. From the construction of the process it follows that: t
S(t) f('l, 4) =f(r/, {) + 5 S(s) fff(r], ~) ds
for all f
0
depending only on a finite number of coordinates. This implies:
t
(2.2) 0
426
E.D. Andjel
Due to the translation invariance of p(x, y) and v o S(s) we have:
fff,(rl, 4) d(v o S(s))= - ~ p(x, y) (vp S(s)) ({t/(x) = 1, ~(x)=0, ~c
tl(y) = 0, 4(Y)= 1 } ) - ~ p(y, z) (vp S(s)) ({r/(y)= 0, ~(y)= 1, ~/(z)= 1, z
~(z) =0}) = -~ Y~p(x, y) L,(~, ~) d(vp ~(s)) x
-- ~ Z P(Y, z) f~r(rl, ~) d(v o S(s)) g
= - S Z (p(x,
y) +p(y, x)) L,(~, ~) d(vo ~(s)).
(2.3)
x
Now (2.2) and (2.3) imply: t
f,(rl, ~) d(v o S(t)) = ~ fr(rl, ~) d v o - ~ [ ~ 2 (p(x, y) 0
§
x
x)) f~r(~/, 4) d(vp S(s))] ds
(2.4)
Since the left hand side of 2.4 is >_0 for all t > 0 it follows that
F(s) = ~ ~ (p(x, y)+ p(y, x)) f~y(rl, ~) d(vp S(s))~L 1 [0, oe). x
But
F'(s) = ~ ~ (p(x, y) + p(y, x)) ff f~y(rl, 4) d(vp S(s)) and Ifff~y[<4, hence [F'(s)l<8. This and the fact that F(s)~L 1 show that F(s)~O as s~oo. Therefore ~f~y(rl,~)d(vpS(s))~O as s-~oo whenever p(x,y)
+p(y,x)>0. Now the irreducibility of p(x, y), a routine induction and a similar argument to the one just used show that ~f~y(rl, 4)d(vpS(s))~O as s~oQ for all x, y s Z a. Hence ~ f~y(t/, 4) d~-p--0 for all x, y e Z d and Vp({(r/,4): r/> ~ or ~ > t/}) = 1 where ~/__>~ means q(x)>~(x) for all x e Z ~. Let S: X--+[0, 1] and I: X ~ [ 0 , 1] be given by: 1
S(~/)=lim suP(2n+l)d ~A, ~ r/(x) and
1 I(t/)=lim, inf(2n+ ~ x ~ a .1) ~
r/(x)
where
An= {(xl , ...,xd)eZa: Ixil ~n, l < i <=d} The strong law of large numbers implies that /zp({~/: I(rl)=S(rl)=p})=l. It follows from this and the existence and properties of 9-p that fi({t/: S(rl)
p})= 1. Hence fi{~/: S(r/)>p and I(tl)
The Asymmetric Simple Exclusion Process on Z e
427
l<_i<_n-1 and denote by A~ the set: {~/: ai_~ 0, letting Vaj_,( [Aj x X) be the conditional measure we get: ~j_~=Rj~aj_~( [Aj x X ) + ( 1 - A j ) ~ j _ ~ ( [Aj xX) ~) where v~-l( IAj xX) ~) is a probability measure on (X x X ) \ (A~ x X). p~_~ is ergodic, hence extremal in the set of translation invariant probability measure on X. Therefore, since Aj x X is translation invariant the second marginal of Va~_l( ]Aj x X) is #~_ 1" The first marginal is/7(]A~). Since V,~_,( [Aj x X) is absolutely continuous with respect to V~_I we must have: [ ~ 1( [A~xX)] [{(t/,~): t/>~ or ~ > t / J = l . Given the properties of the marginals we conclude that [~,~_~( [AjxX)] [{(t/, (): r / > ( } ] = l . Therefore fi( [Aj)>#,~_ 1 where #~>#z (both probability measures on X) means that Sf(rl)d#~(rl)>ff(rl)d#2(rl) for all feC(X) such that f(~/) > f ( 0 whenever q > ~. Similarly one shows that/~(IAj) <#,~. Since /7= ~ 2j/7([Aj) we must have: ~ 2j#,~_1
j=l
j=l
when/7(Aj)--O the meaning of fi([Aj) is irrelevant since, in that case, 2)=0). For each p we pick a probability measure ~-~ on X • X with marginals fi and #~ and such that ~-p({(~/,~): ~/_>~ or ~__>~/})=1. We then define: , {(r/, ~): ~>r/} f(p)=
if0
if p_-<0 if p > l
Clearly
2j=f(aj)-f(aj_a), j=l
therefore
(f(aj)- f(aj_ 01%_1
(2.5)
Since there is at most a countable number of a's such that /~({~:S(q) =I(~)=c~})>0 we can let n go to infinity in (2.5) in such a way that lira max (al-ai_l)=O. Hence/7=~#~dg(~) where g(c0 is the (right continuous) l<_i<_n
distribution function equal to l i m f ( ~ + 0. e~0
Proof of Theorem 1.1. Suppose fil and fi2 are weak limits of #S(t) and vm, vp2 are weak limits of vpS(t) having fi~ and /22 respectively as first marginals. By Proposition 2.1 there exist distribution functions g~(p) (right continuous) such that/2~=~ gpdg~(p) i=1,2. To prove the first statement of Theorem 1.1 it suffices to show that ga(p) =g2(P) for all p's which are points of continuity of both g~ and g2Since ~-p,({(t/,~): t/>~ or ~>~/})--1 we can decompose 7p, in the following way: where
a~=~.,({(~, r r
.~(((~,0. ~_---~})=1
and
~,({(~, O: ~_-__~})= 1.
428
E.D. A n d j e l
If a~=0 then ~, can be taken in an arbitrary way and, in this proof, it will b e / t o x/t o, Similarly if ai = 1 ~2 will be #~ x #p. Let 0 < p < l and S and I be as in the proof of Proposition 2.1. Assuming g~ continuous at p we must have ~({t/: S(rl)=l(rl)p})= 1. Now denoting by /Y~, and fi2 the first marginals of 9-~, and 9-~, respectively, it follows from the properties of 9-p, that fi~,({t/: S(rl)=l(rl) p}) = 1. Since fii=aifi~,+(1-ai) fi2 w e must have: aifi~= S #~dgi(e). [o, p]
S(rl)=I(rl)
But ai=%,({(r/,~): ~>tl})=fi~({rl: we get:
9o,(((rl, ~): t/(y)--0, ~(y)= 1})= aigot ({(r/, 3): tl(Y)=0, ~(y)= 1}) =aiT~,(((rI, ~): ~(y)= 1})- ai V~({(r/, ~): t/(y) = 1}) =a~p- S t~({rl:rl(y)=l})dg,(~)=a~p- S c~dg~(~)= ~ (p-~)dg~(~). [0, p]
[0, p]
The equality ~-p~({(t/,~): t/(y)=0,~(y)=l})=
[o, p]
(p-cQdgi(c~), just proved for
~ [o, p]
0 < p < l , also holds if p = 0 or p = l . In the first case both terms are 0 and in the second they are both equal to fi~({(tl: tl(y)=0}). From 2.4 we see that Sfy(rl,~)d(voS(t)) is a decreasing function of t, hence ~o,({(t/, ~): t/(y)=0, ~(y)=l}) is independent of i. Since this last expression is equal to ~ (p-cQdgi(c 0 if gi is continuous at p we must have: [O,p]
(p-c~)dgl(cQ= ~ (p-~)dg2(~) [0, pl
(2.6)
[o, p]
for all p's which are points of continuity of ga and g2. Let p be a point of continuity of both g~ and g2 and pick a sequence of positive numbers e, converging to 0 and such that g~ is continuous at p +e, for all n and i = 1, 2. Then by (2.6) [O,p +e~]
(,~176
=
(P+e,-~)dg2(a)
S
[0, p+cn]
and (p-c~)dgj(cQ= ~ (p-cQdg2(c Q [o, p]
[o, p]
Subtracting we get:
(P-cQdgl(cO+e,'gl(P+e.)= [p; p + e~]
~ (P-a)dgz(a)+e.'g2(P+e,) [p; p + ~.1
Hence e, l g l ( P + e , ) - g 2 ( P + e , ) l ~
.(
Ip-~ldgl(~)
[p, p + en]
qTherefore
S
[p, p + a.]
[P--c~ldg2(~x)K=sn
S
d g l ( ~ ) q- d'g2(~x)
[p, p + e.]
Igl(p+e,)-g2(p+e,)] ~ 0 as n--* oo and gl(p)=gz(p).
T h e A s y m m e t r i c Simple Exclusion Process on Z d
429
To prove the second statement of Theorem 1.1 let fit/) be t/(0) and note
~f(tl)d(l~S(t))=~ Ff(tl)dt~S(t)=O because I~S(t) is Hence l~S(t) {r/: r/(0) = 1} =/~{I/: r/(0) = 1} and letting t go
that
translation invariant. to oo we get
SP dg(p)
=~{~: ,7(o)= 1}. 3. The Nearest Neighbor Random Walk on Z
In this section S=Z, p(x,x+l)=p, vious section vp = # x/~p.
p(x,x-1)=q
and p + q = l .
As in the pre-
Proof of 7heorern 1.2. Let
/~ be a translation invariant ergodic measure with density Po
if ~(0)=1, 4(0)=0
fk,1(r/,~)=~ sup ~
and
(tl(x)-~(x))>k
I O<=r<=lx=O t0
otherwise.
The main idea in the proof is that the interval [1,l]. A direct calculation gives:
ffs
(
fk,~ does
not increase if particles move in
1, 4(0)=0, sup ~ O
tl(x)-~(x)
0
=y~(x)-4(x)=k-1, tl(l+ 1)= 1, ~(/+1)=0, ~(/)=4(/)=0 0
+pvoS(t )
t/(0)=l, 4(0)=0,
sup
~tl(x)-~(x)
0 <-r<-I 0
}
= Y ~ ( ~ ) - ~ ( x ) = k - ~, 7(1)= 4(1)= 1, ,7(I+ 1)= 1, 4(1 + 1)=0 0
sup
_1
r
+pvpS(t) {,1(0) = 4(0)= 1, r/(1)= 1, ~(1)=0, sup 2 ~(x)-r ONr<~l
+qvoS,(t){rl(O)=~(O)=O, r/(1)=l,
4(1)=0,
0
~up ~ ~(~)- ~(~)>=k} O<=r <-1 0
1 r sup -pvpS(t)
r/(0)=l, 4(0)=0, r/(1)=((1)=0,
sup
~(x)-~(x)>k
O
430
E.D. Andjel
-pvpS(t){tl(-1)=4(-1)=l,
r/(O)=l, 4(0)=0, -l<_,_qsup-iL rl(x)-4(x)>k}
-qv oS(t){tl(-1):{(-1)=O, tl(O)=l , ~(0)=0, -qvoS(t){rl(O)=l, 4(0)=0,
-lsup_<~_ k}
r/(1)={(1)= 1, o=<~__qsup Lrl(X)-{(x)>k}.o
Using the translation invariance of voS(t ) we can combine each of the last four positive terms with a negative term (The third positive term with the first negative term, the fourth positive term with the second negative term and so on) and get:
{
~FfkzdvS(t)
{(0)=0,
sup O
y,~(x)-~(x) 0
= ~ ~(x)- ~(x)=k- 1, ~q+ I)= i, 4q+ i)=o, ~q)=4q)=o 0
+pvoS(t)
r/(O)--l, {(0)=0,
sup
y'rl(X)--4(x)
0 <-r<-I 0
=~ n(x)-g(x)=k- 1, n(/)= 4(0= 1, 11(t+1)= 1, g(t+ i)=o 0
+pvpS(t)
r/(O)=l, 4(0)=0, r/(1)=r
sup
}
~rl(x)-{(x)
O<--r<~l 0
z+l
)
z~ r
-pvp S(t){r/(O)= 4(0)= 1, ~(1)= 1, 4(1)=0,
sup
2rl(X)-r
O<_r
/+1 E ~(xl-4(xl=k t O
-qvpS(t) {r/(O)= ~(0)=0, r/(1)= 1, ~(1)=0,
r
sup ~ ~ (x)- ~(x) < k,
Os
0
/+1
} ~ (x) - 4 (x) = k
0
+qvoS(t){q(O)= 1, {(0)=0,
r
r/(1)= {(i)= 1, sup
~ tl(x)-{(x)
O
l+1 (3,
To simplify notation let lim supgkl(t)<0 for all t<0. l~OO
gk~(t)=jfffkzd(vpS(t)). By (3.1) gkl(t)<2 and
The Asymmetric Simple Exclusion Process on Z d
431
Now, by Fatou's lemma: t
t
lim sup ~ gk, (S) ds < I lim sup gu (s) ds < 0 0
(3.2)
0
But: t
t
= IX, dvo + f (f fA, d(vo ~(~)1)d~ 0 t
= ffk, dvp + I gk,(S) ds. 0
Hence, by (3.2), lim ~fkZd(vpS(t)) <- lim ~fk, dvp l~o0
l~oo
and
~L d(v~&t)) < J'Ldv~
(3.3)
where i fk(~,r
if ~ (0) =r 1, ~ (0) = 0 nd
sup ~tl(X)-~(x)>=k O=
otherwise. # is ergodic and has density Po, hence
#{tl:lim!~tl(x)=po}=l but #p t / : l i m n ~ q ( x ) = p =1; therefore, since we picked P>Po for all e > 0 t. n 1 ) there exists a k such that Ifk d vo < e. Using (3.3) and the fact that fk~
Ifk~ d(v o S (t)) < Ilk d(voS (t)) <=IX dv o < e for all t > 0 and all 1. Picking a sequence t , ~ o o and such that voS(t,) converges we get Ifud~p
limit exists and is of that form by Theorem 1.1). #p is, of course, the second marginal of 9-0. Now ffkt d 9-0< e for all l implies ffk d gp =
~(0)=1, r
supy,~(x)-~(x)____k
0
432 therefore
E.D. Andjel
{
,
17(0)=1, 3 ( 0 ) = 0 , s u p ~ t / ( x ) - ~ ( x ) =
+oo
}
0_-
Since e is a r b i t r a r y
T h e r e f o r e g ( p ) = 1 for all P>Po. S i n c e g is right c o n t i n u o u s g ( p o ) = 1. A r g u i n g as we d i d to p r o v e the last p a r t of t h e o r e m 1.1 we see t h a t Po = # { t / : ~l(O)=l}=#S(t){tl:(O)=l } a n d t a k i n g l i m i t s we get po=liml~S(t) {t/: t j ( 0 ) = 1} = S e d g ( ~ ) . H e n c e
g(po-6)=O
for all 6 > 0 a n d l i m # S ( t ) = ~ p o .
Acknowledgements. I
would like to thank Thomas M. Liggett for his encouragement while this work was in progress and a referee for his helpful suggestions.
References 1. Liggett, T.M.: Existence theorems for infinite particle systems. Trans. Amer. Math. Soc. 165, 471-481 (1972) 2. Liggett, T.M.: Convergence to total occupancy in an infinite particle system with interactions. Ann. Probability 2, 989-998 (1974) 3. Liggett, T.M.: Ergodic theorems for the asymmetric simple exclusion process. Trans. Amer. Math. Soc. 213, 237-261 (1975) 4. Liggett, T.M.: Coupling the simple exclusion process. Ann. Probability 4, 339-356 (1976) 5. Liggett, T.M.: The stochastic evolution of infinite systems of interacting particles. Lecture notes in Mathematics, 598. Berlin-Heidelberg-New York: Springer 1977 6. Liggett, T.M.: Ergodic theorems for the asymmetric simple exclusion process II. Ann. Probability 5, 795-801 (1977) 7. Spitzer, F.: Interaction of Markov processes. Advances in Math. 5, 246-290 (1970) Received December 10, 1980; in revised form July 16, 1981
