\overfullrule0pt \magnification=\magstep1 \def\spa{\parindent=0pt} \def\npa{\parindent=20pt} \font\tif = cmcsc10 scaled \magstep2 \font\reff = cmcsc10 scaled \magstep1 \font\auf = cmr8 scaled \magstep1 \font\erm = cmr8 \font\csc = cmcsc10 \def\bs{\bigskip} \def\bn{\bigskip\noindent} \def\ep{\epsilon} \def\mn{\medskip\noindent} \def\rf{\smallskip\noindent\hangindent\parindent} \def\RR{{\bf R}} \def\ZZ{{\bf Z}} \def\today{\ifcase\month\or January \or February \or March \or April \or May \or June \or July \or August \or September \or October \or November \or December \fi \number\day, \number\year} \def\pf{\bigskip\noindent{\csc Proof: }} \def\square{\vcenter{\vbox{\hrule height .4pt \hbox{\vrule width .4pt height 5pt \kern 5pt \vrule width .4pt} \hrule height .4pt}}} \def\eopt{\hfill$\square$} \def\eopf{\eqno\square} \def\sqz{\kern -0.2em} \def\uv{{\underline v}} %\hfill{\erm\today} %\vskip 0.5in \centerline{\tif Dynamics of a Spin-Exchange Model} \vskip 0.3in \centerline{\auf {\sl Joel L. Lebowitz}, Rutgers University$^1$ } \centerline{\auf {\sl Claudia Neuhauser}, University of Wisconsin$^2$ } \centerline{\auf {\sl Krishnamurthi Ravishankar}, State University of New York$^{1,3}$ } \vskip 0.4in \def\mn{\medskip\noindent} \def\rf{\smallskip\noindent\hangindent\parindent} \def\stararrow{\buildrel\star\over\rightarrow} \def\cS{\cal S} \def\square{\vcenter{\vbox{\hrule height.4pt \hbox{\vrule width .4pt height 5pt \kern 5pt \vrule width .4pt} \hrule height .4pt}}} \def\eop{\hfill $\square $} \def\rf{\smallskip\noindent\hangindent\parindent} \def\mn{\medskip\noindent} \def\etac{\eta^c} \def\xic{\xi^c} {\bf Abstract:} We study a model on the non-negative half line ${\bf Z}_0^+$, $\lbrace 0,1,2,\dots\rbrace $ in which particles created at the origin at rate 1 jump to the right at rate 1. If a particle jumps onto an already occupied site the two particles annihilate each other. In addition, whenever a particle jumps its closest neighbor to the right jumps along with it. We find that the spatial decay rate of the particle density in the stationary state is of order $1/\sqrt{x}$ at distance $x$ from the origin. This model provides an approximation to the dynamics of an anchored Toom interface which can be represented as a spin-exchange model. \vfill {\parindent=0pt { \it AMS 1991 subject classifications.} Primary 60K35, 82C22; secondary 82B24, 82C24. } \bigskip {\parindent=0pt Short title: Spin Exchange Model} \bigskip {\parindent=0pt Key words and phrases: Interacting particle systems, coalescing random walk, annihilating random walk, voter model, Toom model, interface problems. \bigskip $^1$ Supported in part by the National Science Foundation under grant DMR-92-13424. $^2$ Alfred P. Sloan Research Fellow. Supported in part by the National Science Foundation under grant DMS-94-03644. The second author wishes to acknowledge support from the Institute for Mathematics and its Applications during the winter and spring quarter 1994. $^3$ The third author wishes to acknowledge support from the Courant Institute, New York, the Universita di Roma Tor vergata, and SPIC Science Foundation Madras.} \eject {\bf 1. Introduction.} The process we consider here, is motivated by a seemingly unrelated model, namely the probabilistic cellular automaton known as the Toom model (Toom, 1974). The system consists of Ising spins ($\sigma_{ij}=\pm 1$) located on the two-dimensional integer lattice which evolve in discrete time. At each time step, all spins $\sigma_{ij}$ are updated according to the rule $$\sigma_{ij}(t+1)=\cases{{\rm sign}\lbrack \sigma_{i,j+1}(t)+ \sigma_{i+1,j}(t)+\sigma_{ij}(t)\rbrack &with probability $1-p-q$\cr +1 &with probability $p$\cr -1 &with probability $q$\cr}\leqno(1.1)$$ with $0\leq p+q\leq 1$. The parameters $p+q$ and $(p-q)/(p+q)$ are called {\it noise} and {\it bias}, respectively. For $p=q=0$, the evolution is deterministic: each updated spin becomes equal to the majority of itself, its northern, and its eastern neighbor. Toom (1974) proved that for $p$ and $q$ sufficiently small (low noise), but otherwise unrestricted, two phases exist, in which the spins are predominantely $+1$ or $-1$, respectively; these two phases are called {\it low noise phases}. (See also Bramson and Gray (1991) for a different proof of this fact. For further discussion of this model we refer the reader to Bennett and Grinstein (1985) and Lebowitz et al. (1990).) Using suitable initial or boundary conditions, one can introduce a non-equilibrium interface between the two low-noise phases. Such interfaces were studied by Derrida et al. (1991). They considered the system in the third quadrant only and imposed the following boundary conditions: $\sigma_{i0}=+1$ and $\sigma_{0i}=-1$ for all $i<0$ and all $t$. That is, the spins were all fixed as $+1$ along the negative $x$-axis and $-1$ along the negative $y$-axis. With these boundary conditions, the Toom model with low noise exhibits an interface which separates the $+$ phase in the upper portion of the quadrant from the $-$ phase in the lower portion. Derrida et al. (1991) introduced a low-noise approximation of this interface which we now describe (see Figure 1.1). The interface is anchored at the origin and, at the zero-noise level $(p=q=0)$, forms a staircase with all spins equal to $+1$ above the staircase and $-1$ below the staircase. All such staircases are stationary and can be represented as a sequence of spins $ \lbrace S_n: n\geq 0 \rbrace$ with $S_n$ = $0$ or $1$ where ``0'' represents a horizontal edge and ``1'' a vertical edge in the staircase. Under the effect of noise there will be spin flips. When the noise is very weak flips away from the interface will have a very short lifetime whereas flips adjacent to the interface will typically change the staircase rapidly to another staircase. This change of the interface is described by exchanging the spin $S_n$, which corresponds to the edge adjacent to the spin $\sigma_{ij}$ flipped by noise, with the first spin following $S_n$ which has a value different from $S_n$ (see Figure 1.2). Derrida et al. (1991) showed that under suitable scaling of noise and time the time evolution of the interface can be represented by a continuous time Markov process where a 1 (respectively, a 0) is exchanged with the first 0 (respectively, 1) to its right at rate $\lambda_1$ (respectively, $\lambda_0$). Rigorous results for the semi-infinite model are difficult to come by. Derrida et al. (1991) performed computer simulations which indicate that fluctuations in this system are much smaller than in equilibrium interfaces. Furthermore, the system exhibits long-range correlations. Various approximations for the interface are studied in their paper which reproduce the observed behavior at least qualitatively. In Appendix 3 of their paper, a family of related spin exchange models, $\lbrace S^{(k)}(n): n\geq 0\rbrace_{k\geq 1}$, is defined which can be thought of either as a sequence of approximations to the original spin-exchange model or as a scaling limit of a modified Toom model in the unbiased case (i.e., $\lambda_1=\lambda_0$). In the $k$th approximation of this spin-exchange model, $\lbrace S^{(k)}(n): n\geq 0\rbrace$, only the $k$ left-most spins in any block of 0's or 1's in a configuration may exchange spins. We will investigate the first approximation, $\lbrace S^{(1)}(n): n\geq 0\rbrace$, in which only the left-most spin in any block of 0's or 1's may exchange spins. Instead of studying $\lbrace S^{(1)}(n): n\geq 0\rbrace$, we keep track of the borders between blocks of 0's and 1's. We denote this border process by $\lbrace \eta^c_t: t\geq 0\rbrace $ (the significance of the superscript ``c'' in $\eta_t^c$ will become clear after we define the dynamics). The process $\eta_t^c$ is a set-valued process defined on the non-negative half line ${\bf Z}_0^+=\lbrace 0,1,2, \dots \rbrace$. For $x\in {\bf Z}_0^+$ we set $x\in\eta^c$ if $S^{(1)}(x)\not= S^{(1)} (x+1)$ and $x\notin \eta^c$, otherwise. If $x\in\etac$, we say $x$ is occupied by a particle; if $x\notin\etac$, we say $x$ is vacant. The dynamics are as follows: \vskip .15in \parindent =0pt (i) Each particle and its closest neighbor to the right jump one unit to the right at rate 1. We call this coupled jumping {\it co-jumping}. \vskip .10in (ii) Particles are born at the origin at rate 1 and, together with their closest neighbor to the right, jump immediately one unit to the right. \vskip .10in (iii) If a particle jumps to an already occupied site, annihilation occurs. \vskip .15in We refer to this process as {\it annihilating random walks with co-jumping and source at the origin}. \parindent=20pt It is not hard to see that the process $\eta_t^c$ (the superscript ``c'' refers to co-jumping) is indeed the border process of the first approximation of the spin-exchange model described above. Figure 1.3 illustrates three successive transitions in both processes $S^{(1)}$ and $\eta^c$. The 0's and 1's are the values in the process $S^{(1)}$; the {\bf .}'s and x's are the values in the border process $\eta^c$, i.e., a ``{\bf .}'' stands for a vacant site and an ``x'' for an occupied site in the process $\eta^c$. The underlined digits initiate the exchange with the first spin to the right that has a different value (indicated by an arc). For instance, when the underlined 0 in the first line exchanges with the first 1 to the right, we see that the x to the left of the 0 jumps one unit to the right and, simultaneously, the closest x to the right jumps to the right as well annihilating the $x$ at the neighboring site. Spontaneous births in the process $\eta^c$ correspond to exchanges initiated by the first spin as can be seen in the second and third transition. We are interested in properties of the equilibrium measure. (A simple coupling argument, which we sketch at the end of this section, shows that there exists a unique equilibrium.) Derrida et al. (1991) observed in simulations that at distance $n$ from the origin, the typical block size in the first approximation of the spin-exchange model is of order $\sqrt{n}$ or -- in terms of the process $\eta_{t}^c$ -- the distance between nearest particles in $\eta_\infty^c$ is of order $\sqrt{x}$ at distance $x$ from the origin. Our main theorem confirms this observation: \vskip .30in {\parindent=0pt {\bf Theorem 1.} {\sl Let $\lbrace\eta_t^c: t\geq 0 \rbrace$ be the annihilating random walk with co-jumping defined above. Then starting from any initial configuration, the process converges (weakly) to a unique equilibrium, denoted by $\eta^c_\infty$. Furthermore, $$\lim_{x\to\infty}2\sqrt{\pi x} P(x\in \etac_\infty)=1.\leqno(1.2)$$} } \vskip .30in \parindent=20pt This behavior is already displayed by a simplified version of this model, namely one in which there is no co-jumping. We denote the simplified process by $\lbrace \eta_t: t\geq 0\rbrace $ (the lack of the superscript ``c'' indicates that there is no co-jumping) and call it {\it annihilating random walks with source at the origin}. The process $\lbrace \eta_t: t\geq 0\rbrace $ is a set-valued process on ${\bf Z}_0^+$ as well and its dynamics are given by \vskip .20in {\parindent=0pt (i) If a particle is at $x$, it jumps to $x+1$ at rate 1. \vskip .10in (ii) Particles are born at the origin at rate 1 and jump immediately to $+1$. \vskip .10in (iii) If a particle jumps to an already occupied site, then the particles annihilate each other. } \vskip .20in \parindent=20pt The analogue of Theorem 1 is contained in the following result: \vskip .30in {\parindent=0pt {\bf Theorem 2.} {\sl Let $\lbrace\eta_t: t\geq 0 \rbrace$ be the annihilating random walk defined above. Then starting from any initial configuration, the process converges (weakly) to a unique equilibrium, denoted by $\eta_\infty$. Furthermore, $$\lim_{x\to\infty}2\sqrt{\pi x} P(x\in \eta_\infty)=1.\leqno(1.3)$$} } \vskip .30in \parindent=20pt The reason for investigating both $\eta_t^c$ and $\eta_t$ is two-fold: Firstly, it shows that the limiting behavior of the density of particles is not changed by introducing the more complicated coupled jumping of particles (at least at the scale we are looking at). Secondly, the ideas that go into the proofs of Theorems 1 and 2 are basically the same, however, the proof of Theorem 2 is more transparent since we do not have to deal with some of the technical difficulties due to the co-jumping of particles. Existence and uniqueness of the equilibrium distribution follows from the following simple observation. We couple the process with given initial configuration to the process starting from the empty configuration and observe that for any interval $\lbrack 0,l\rbrack\cap {\bf Z}$, the two processes will agree for all sufficiently large times since the process on $\lbrack 0,l\rbrack\cap {\bf Z}$ is a finite state Markov chain. The paper is organized as follows: In Section 2 we investigate the simplified model $\eta_t$ and prove Theorem 2. The key to proving Theorem 2 is that (i) if we replace annihilation in the process $\eta_t$ by coalescence, we obtain a process $\xi_t$ whose equilibrium density is twice that of $\eta_t$ and (ii) the process $\xi_t$ has a dual which is easier to deal with than the dual of $\eta_t$ and which allows us to compute the density of particles in $\xi_t$. Section 3 is devoted to the proof of Theorem 1. \vskip .50in {\bf 2. The simplified model.} In this section we study the simplified version of the first approximation of the spin exchange model introduced in the last section, namely the annihilating random walk $\eta_t$ with source at the origin. It will be useful to introduce two other processes as well which are closely related to $\eta_t$, namely the coalescing random walk with source at the origin and the completely asymmetric voter model. The three processes are each defined on the non-negative half line ${\bf Z}_0^+ =\lbrace 0,1,2,\dots \rbrace $. We denote the annihilating random walk with source at the origin by $\lbrace \eta_t: t\geq 0\rbrace$, the coalescing random walk with source at the origin by $\lbrace\xi_t: t\geq 0\rbrace$, and the completely asymmetric voter model with drift by $\lbrace\zeta_t: t\geq 0\rbrace$. The state space of each system is ${\cal S}=\lbrace$all subsets of ${\bf Z}^+_0\rbrace $, where $x\in\eta_t$ or $x\in\xi_t$ or $x\in\zeta_t$ if there is a particle present at site $x$ at time $t$. The dynamics of the random walk $\eta_t$ were given in the introduction. We repeat them here since the dynamics of $\xi_t$ are very similar and can easily be described together: \vskip .20in {\parindent=0pt (i) Particles are born at the origin at rate 1 and jump immediately to $+1$. \vskip .10in (ii) If a particle is at $x$, it jumps to $x+1$ at rate 1. \vskip .10in (iii) If a particle jumps to an already occupied site, then in the process $\eta_t$, the particles annihilate each other, whereas in the process $\xi_t$, the particles coalesce. } \vskip .20in \parindent=0pt The dynamics of the completely asymmetric voter model with drift, $\zeta_t$, are as follows: \parindent=20pt \vskip .20in {\parindent=0pt (i) If $x$ is vacant and $x+1$ is occupied, then at rate 1, $x$ becomes occupied. \vskip .10in (ii) If $x$ is occupied and $x+1$ is vacant, then at rate 1, $x$ becomes vacant. } \vskip .20in \parindent=0pt If we think of vacant and occupied as opinions of voters, then the dynamics of $\zeta_t$ can be formulated as follows: At rate 1, the voter at $x$ imitates the opinion of the voter at $x+1$. The voter model on ${\bf Z}^d$ was introduced independently by Holley and Liggett (1975) and by Clifford and Sudbury (1973). \parindent=20pt The three processes can be defined using a graphical representation, a technique which was introduced in Harris (1972). This is standard fare (see, e.g., Durrett (1988) for an account on graphical representation). Since the graphical representation will be used explicitely throughout the paper, we present the details. The percolation substructure for the graphical representation is defined on ${\bf Z}_0^+\times\lbrack 0, \infty )$ which is thought of as giving a time line to each $x\in {\bf Z}_0^+ $. We begin with constructing the annihilating random walk $\eta_t$. For each $x\in{\bf Z}_0^+$, let $\lbrace U_n^x: n\geq 1\rbrace $ be the successive arrival times of independent Poisson processes with rate 1. At each time $U_n^x$, draw an arrow from $x$ to $x+1$ and place the symbol $\delta$ at $x$, the tail of the arrow. The coalescing random walk $\xi_t$ is constructed in exactly the same way. For the completely asymmetric voter model $\zeta_t$, we only need to reverse the direction of the arrows, that is, arrows go from $x+1$ to $x$, the symbol $\delta$ is at $x$, the tip of the arrow. An idea of Harris (1972) allows us to construct each process starting from any initial configuration in ${\bf Z}_0^+$. For $x,y\in{\bf Z}_0^+ $ and $0\leq s\leq t$, say there is a {\it path} from $(x,s)$ to $(y,t)$ (notation: $(x,s)\to (y,t)$) if $(y,t)$ can be reached along an alternating sequence of upward and horizontal edges (traversed in the direction of the arrow) in such a way that no $\delta$ lies in the interior of an upward edge, and there is no $\delta$ at $(y,t)$ itself. By reversing time, we can define dual paths, which will be used below to relate the completely asymmetric voter model to both the coalescing and the annihilating random walk with source at the origin. For $x,y\in {\bf Z}_0^+$ and $0\leq s\leq t$, say that there is a {\it dual path} from $(x,t)$ to $(y,s)$ (notation: $(x,t) {\buildrel\star\over \rightarrow}(y,s)$) if $(y,s)$ can be reached along an alternating sequence of downward and horizontal (traversed in the opposite direction of the arrow) edges in such a way that no $\delta$ lies in the interior of a downward edge, and there is no $\delta$ at $(y,s)$ itself. We are now ready to give the relationship between the three processes. Let $\xi_t^\emptyset$ (respectively, $\eta_t^\emptyset$) denote the coalescing (respectively, annihilating) random walk with source at the origin in which all sites in ${\bf Z}_0^+$ are initially vacant. Let $\zeta_t^x$ denote the completely asymmetric voter model in which initially $y\notin\zeta_0^x$ if $y\not= x$ and $x\in\zeta_0^x$. The voter model with drift and the coalescing random walk with source at the origin are related via the following duality equation $$\eqalign{\lbrace x\in\xi_t^\emptyset \rbrace &=\lbrace (0,s)\to (x,t)\ \hbox{for some}\ 0\leq s\leq t \rbrace\cr &=\lbrace (x,t)\stararrow (0,s) \ \hbox{for some}\ 0\leq s\leq t\rbrace \cr &=\lbrace 0\in\zeta_s^x\ \hbox{ for some}\ 0\leq s\leq t\rbrace\cr }\leqno(2.1)$$ where the dual paths $(x,t)\stararrow (0,s)$ are constructed on the graphical representation of $\xi_t$. Similarly, the voter model with drift and the annihilating random walk with source at the origin are related via the following duality equation $$\lbrace x\in\eta_t^\emptyset \rbrace =\lbrace \hbox{the number of dual paths from $(x,t)$ to $(0,s)$, $0\leq s\leq t$, is odd}\rbrace .\leqno(2.2)$$ The duality equations (2.1) and (2.2) are extensions of the well-known duality equations for the voter model (see, e.g., Liggett (1985), Chapter V, or Durrett (1988), Chapter 2) and follow easily from the graphical representation. We wish to show the following result which was stated as Theorem 2 in the introduction. $$\lim_{x\to\infty}2\sqrt{\pi x}P(x\in\eta_\infty)=1. \leqno(2.3)$$ Two main ideas go into the proof of this Theorem and we will explain them first before embarking on the proof. Looking at (2.1) and (2.2), it seems to be easier to prove results about coalescing random walks than about annihilating random walks. So, we will first prove the analogous result for the coalescing random walk $\xi_t$. This is the content of the following proposition. \vskip .20in {\parindent=0pt {\bf Proposition 1.} {\sl Let $\xi_t$ be the coalescing random walk with source at the origin defined above with equilibrium distribution $\xi_\infty$. Then $$\lim_{x\to\infty}\sqrt{\pi x} P(x\in\xi_\infty ) =1.\leqno(2.4)$$} }\vskip .20in As the reader can see, the only difference between (2.3) and (2.4) is the factor of 2. So, we need to show that asymptotically, as $x$ tends to infinity, the ratio of the densities of particles in equilibrium in the two processes $\eta_t$ and $\xi_t$ goes to one half. That this is true, can be explained intuitively as follows: Twice as many particles are eliminated in a collision in the annihilating random walk compared to the coalescing random walk, therefore, the density in the annihilating random walk should be one half the density of the coalescing random walk. This ``one-half thinning'' is contained in the following proposition. (This has actually been made rigorous for a class of coalescing/annihilating random walks by Griffeath (1979) (see, Proposition 5.4, Chapter III) and Arratia (1981).) It turns out that the proof of our result needs a different argument, primarily since in our process there is a source of particles at the origin.) \vskip .20in {\parindent=0pt {\bf Proposition 2.} $$\lim_{x\to\infty} {P(x\in\eta_\infty )\over P(x\in\xi_\infty)}={1\over 2}.$$ \vskip .30in } \vskip .20in \parindent=0pt Combining the two propositions thus implies Theorem 2. \parindent=20pt >From now on we define the graphical representation so that the coalescing (annihilating) random walks evolve downwards on the graph and the voter model evolves upwards on the graph. We need to introduce some notation. The completely asymmetric voter model starting at $x$ at time 0 remains a ``block'' (i.e., a completely occupied interval) until absorption at $\emptyset$. We denote the location of the left edge of this interval at time $t$ by $L(t)$ and the right edge by $R(t)$. (To keep the notation simple, we drop the dependence on $x$.) Let $N_t=|\zeta_t^x|$. Then, $N_t=R(t)- L(t)+1$. The left edge and the right edge each perform independent random walks which jump one unit to the left at rate 1 until $\zeta_t^x$ is absorbed at $\emptyset$. (Note, $\zeta_t^x$ is absorbed at $\emptyset$ at the first time when $R(t)0)}= {P(V_\infty\ {\rm odd})\over P(T >\tau)}.\leqno(2.12)$$ To compute the numerator in (2.12), we decompose the event $\lbrace V_\infty \ {\rm odd}\rbrace $ according to the location of the right edge of the voter model at time $\tau$. We denote by $\sigma_m$ the additional time it takes $R(\cdot )$ to reach 0 when starting from $m$ and by $M(s)$ the number of occurrences by time $s$ in a Poisson process with rate 1. Then $$\eqalign{P(V_\infty\ {\rm odd})&=P(V_\infty\ {\rm odd}; V_\infty >0) =\sum_{m=0}^\infty P(V_\infty \ {\rm odd};T>\tau ;R(\tau )=m)\cr &=\sum_{m=0}^\infty P(M(\sigma_m)\ {\rm even}; T>\tau ; R(\tau )=m )\cr &=\sum_{m=0}^\infty P( M(\sigma_m)\ {\rm even} \mid T>\tau ; R(\tau )=m ) P(T>\tau ; R(\tau )=m )\cr &=\sum_{m=0}^\infty P(M(\sigma_m )\ {\rm even} ) P(T>\tau ; R(\tau )=m) .\cr}\leqno(2.13)$$ We switched from $\lbrace V_\infty$ odd$\rbrace $ to $\lbrace M(\sigma_m)\ {\rm even}\rbrace $ since there is already one particle at the origin at the time when the left edge hits the origin and we do not count this particle in the process $M(\cdot )$. To continue our computation of (2.13) (and hence (2.12)) we show the following lemma. \vskip .20in {\parindent=0pt {\bf Lemma 1.} $$P(M(\sigma_m)\ {\rm even})={1\over 2} \lbrack 1+({1\over 3})^m\rbrack.$$ \vskip .20in {\bf Proof.} Note that $\sigma_m$ is the time of the $m$th arrival in a Poisson process with rate 1. Hence $\sigma_m$ is Gamma distributed with parameters $m$ and 1. We can therefore write $$\eqalign{&P(M(\sigma_m)\ {\rm even})=\int_0^\infty P(M(s)\ {\rm even}) dP(\sigma_m=s)\cr &\int_0^\infty e^{-s}\sum_{k=0}^\infty {s^{2k}\over (2k)!} {s^{m-1}e^{-s}\over (m-1)!}ds\cr &\int_0^\infty e^{-s}{1\over 2} (e^s+e^{-s}){s^{m-1}e^{-s}\over (m-1)!}ds\cr &={1\over 2}\int_0^\infty {s^{m-1}e^{-s}\over (m-1)!}ds +{1\over 2} \int_0^\infty {s^{m-1}e^{-3s}\over (m-1)!}ds .\cr}$$ The first integral is simply 1 since the integrand is the density of a Gamma distribution with parameters $m$ and 1. The second integral can be evaluated by change of variables and we obtain $$\eqalign{&={1\over 2}+{1\over 2}\int_0^\infty {u^{m-1}e^{-u}\over 3^{m-1}(m-1)!}{du\over 3}\cr &={1\over 2}+{1\over 2}({1\over 3})^m\int_0^\infty {u^{m-1} e^{-u}\over (m-1)!}du\cr &={1\over 2}+{1\over 2}({1\over 3})^m\cr}$$ since the integrand obtained after the change of variables is again the density of a Gamma distribution with parameters $m$ and 1. \eop } \parindent=20pt \vskip .30in Using Lemma 1, it is easy to obtain a lower bound on (2.13): $$\eqalign{P(V_\infty\ {\rm odd})&\geq \sum_{m=0}^\infty {1\over 2} P(T>\tau ; R(\tau )=m) = {1\over 2} P(T>\tau ; R(\tau )\geq 0)\cr &={1\over 2} P(T>\tau )\cr}\leqno(2.14)$$ since $\lbrace T>\tau\rbrace \subset \lbrace R(\tau)\geq 0\rbrace$. After dividing by $P(T>\tau )$, this shows that $1/2$ is a lower bound for (2.12). To obtain an upper bound on (2.13) we let $g(x)= x^{0.2}$ and use Lemma 1. This yields $$\eqalign{P(V_\infty \ {\rm odd})&=\sum_{m=0}^\infty {1\over 2} \lbrack 1+({1\over 3})^m\rbrack P(T>\tau ; R(\tau )=m )\cr &\leq P(T>\tau ; R(\tau )\leq g(x) )+{1\over 2} \lbrack 1+({1\over 3})^{g(x)}\rbrack P(T>\tau ; R(\tau )>g(x))\cr &\leq P(T>\tau ;R(\tau )\leq g(x))+{1\over 2} \lbrack 1+({1\over 3})^{g(x)}\rbrack P(T>\tau )\cr}\leqno(2.15)$$ To obtain an upper bound on $ P(T>\tau ;R(\tau )\leq g(x))$, we will use the discrete time embedding defined above (before the proof of Proposition 1). In addition, let $S_n\equiv A_n-B_n$ with $S_0=0$ and let $\tilde S_n$ be an independent copy of $S_n$, that is, $\tilde S_0=0$ and $\tilde S_n$ evolves according to the same law as $S_n$. Note that if $A_W-B_W\leq g(x)$, then $2x-W\leq g(x)$ which is the same as $W\geq 2x-g(x)$. We denote by $\tilde T$ the first time $n$ where $A_n < B_n$. Since $\lbrace \tilde T>W\rbrace =\lbrace \tilde T>2x\rbrace $, it follows $$\eqalign{P(A_W-B_W\leq g(x);\tilde T>W)\leq P(S_{2x}&\leq g(x)+\lbrack g(x) \rbrack^{0.6};\tilde T>2x)\cr &+P(|\tilde S_{g(x)}|>\lbrack g(x) \rbrack^{0.6}).}\leqno(2.16)$$ To estimate $ P(S_{2x}\leq g(x)+\lbrack g(x) \rbrack^{0.6};\tilde T>2x)$, we need the following discrete time version of a result by Bramson and Griffeath (1980): \vskip .20in {\spa {\bf Lemma 2.} {\sl There exists $C_1>0$ so that $$P\lbrack S_{2x}\leq u\sqrt{x}\mid\tilde T>2x\rbrack\leq C_1 u^2.$$ } \vskip .20in \npa Using Lemma 2, we can estimate the first term on the right hand side of (2.16) and obtain for sufficiently large $x$ $$\eqalign{&P(S_{2x}\leq g(x)+\lbrack g(x)\rbrack^{0.6};\tilde T >2x)=P(S_{2x}\leq x^{0.2}+x^{0.12}\mid\tilde T>2x)P(\tilde T>2x)\cr &\leq P(S_{2x}\leq x^{0.3}\mid\tilde T>2x)P(\tilde T>2x) \leq C_1\lbrack x^{-0.2}\rbrack^2 P(\tilde T>2x) \cr}\leqno(2.17)$$ The second term on the right hand side of (2.16) can be bounded in the following way $$\eqalign{P(|\tilde S_{g(x)}|>\lbrack g(x) \rbrack^{0.6}) &\leq C_2\int_{\lbrack g(x)\rbrack^{0.1}}^\infty e^{-u^2/2}du \leq C_2 {1\over \lbrack g(x)\rbrack^{0.1}}e^{- \lbrack g(x)\rbrack^{0.2}/2} \cr}\leqno(2.18)$$ for some appropriate constant $C_2<\infty$. Combining (2.17) and (2.18) we can bound (2.15): $$\leq C_1 x^{-0.4}P(\tilde T>2x)+C_2 x^{-0.02}e^{-x^{0.04}/2} +{1\over 2}\lbrack 1+({1\over 3})^{g(x)}\rbrack P(T>\tau).\leqno(2.19)$$ We need the following Lemma which follows immediately from a simple large deviations estimate and we omit the proof. \vskip .20in {\parindent=0pt {\bf Lemma 3.} {\sl For any $\epsilon >0$, there exists $\gamma (\epsilon)>0$ so that $$P(|\tau -x| >\epsilon x\mid T>\tau)\leq e^{-\gamma (\epsilon)x}. \leqno(2.20)$$} \vskip .20in } Now $$\eqalign{{P(T>\tau)\over P(\tilde T>2x)}&= {P(T>\tau ; |\tau -x| \leq \epsilon x)\over P(\tilde T>2x)}+ {P(T>\tau ; |\tau -x| > \epsilon x)\over P(\tilde T>2x)} \cr &\leq {P(T>(1-\epsilon )x)\over P(\tilde T>2x)} +{P(|\tau -x| > \epsilon x) \over P(\tilde T>2x)}\cr}\leqno(2.21)$$ Using (2.8) and Lemma 3, there are constants $C_3, C_4 >0$ so that $$C_3\leq {P(T>(1-\epsilon )x)\over P(\tilde T>2x)} \leq C_3 +C_4\sqrt{x} e^{-\gamma (\epsilon)x} . \leqno(2.22)$$ A similar argument together with (2.8) also shows that the second term in (2.19) goes to 0 after dividing by $P(T>\tau)$ and letting $x\to\infty$. Therefore, after dividing (2.19) by $P(T>\tau )$, the upper bound for (2.13) tends to $1/2$ as $x\to\infty$. This proves Proposition 2. \vskip .50in {\bf 3. The co-jumping case.} In this section we prove Theorem 1. We begin by introducing two processes which are analogous to the processes $\eta_t$ and $\xi_t$ defined in the previous section. The processes are again defined on the non-negative half line ${\bf Z}_0^+=\lbrace 0,1,2,\dots\rbrace $. We denote the annihilating random walk with co-jumping and source at the origin by $\lbrace \etac_t : t\geq 0\rbrace $ and the coalescing random walk with co-jumping and source at the origin by $\lbrace\xic_t :t\geq 0 \rbrace $. The state space of each system is ${\cal S}=\lbrace \hbox{all subsets of}\ {\bf Z}_0^+\rbrace $ where $x\in\etac_t$ or $x\in\xic_t$ if and only if there is a particle present at site $x$ at time $t$. The dynamics of the random walks $\etac_t$ and $\xic_t$ are as follows: \vskip .20in {\parindent=0pt (i) Particles are born at rate 1 at the origin and jump immediately to $+1$. \vskip .10in (ii) If a particle is at $x$, then at rate 1, the particle at $x$ and its closest neighboring particle to the right each jump (simultaneously) one unit to the right. \vskip .10in (iii) If a particle jumps to an already occupied site, then in the process $\etac_t$, the particles annihilate each other, whereas in the process $\xic_t$, the particles coalesce. \vskip .20in } \parindent=0pt One can again use the graphical representation introduced in the previous section to define the processes. We omit the details. \parindent=20pt The basic strategy in proving Theorem 1 is the same as in the previous section. Asymptotically, the annihilating random walk $\etac_t$ will again be a ``one half thinning'' of the coalescing random walk $\xic_t$ (this is the content of Proposition 6, which is the analogue of Proposition 2). Proving the analogue of Proposition 1 (which is contained in Proposition 5) is harder. In the simplified version there was a simple relationship (2.1) which allowed us to relate the coalescing random walk $\xi_t$ to a voter model $\zeta_t$. That is, a site $x$ was occupied in the coalescing random walk if and only if the voter model starting at $x$ reached the origin at some time $s\leq t$. The survival of the voter model until it hit the origin could be investigated by studying the left and the right edge in the voter model. The difference between the right and the left edge behaved like a random walk. We can again define a ``cone'' with a left edge and a right edge which is the analogue of the voter model dual in Section 2 and relate the survival of this cone to occupancy of a site in the coalescing random walk process (this is equation (3.3) below). But, as we will see, due to co-jumping events, the motion of the left and the right edges are not always necessarily independent. In analogy with the previous section, we call this backward process the {\it modified voter model} and denote it by $\zeta^c_t$. >From now on, we stipulate that the modified voter model starts at $x$ at time 0 and moves upwards on the graphical representation, whereas the particles move downward on the graphical representation. Figure 3.1 shows a realization of coalescing random walks with co-jumping and source at the origin. For ease of reading, we drop the $\delta$'s at the tails of the arrows. Particles in the coalescing random walk are born at the origin. Their movement is downward on the graphical representation and to the right whenever they encounter an arrow or are forced to jump due to a co-jumping event. In Figure 3.1, the thickened lines are paths taken by particles, the dashed horizontal segments indicate jumps due to co-jumping events. The hatched area is the cone defined by the modified voter model. Note that particles in the coalescing random walk move to the right, whereas the edges of the cone jump to the left. To keep the notation simple, we drop all dependency on $x$. We denote the left edge at time $t$ by $L^c(t)$ and the right edge at time $t$ by $R^c(t)$ and set $L^c(0)= R^c(0)=x$. Let $I(t)\equiv \lbrack L^c(t), R^c(t)\rbrack $ and let $N(I(t))$ denote the number of particles in $I(t)$. We would like to point out that the movement of the edges is not defined by just giving the graphical representation but also includes the realization of the particle process. Given the particle configuration at time $t$ and the locations of the left and the right edge, we can now describe the movement of the edges and hence the movement of the difference process $Z(t)=R^c(t)-L^c(t)$. The dynamics of the edges are as follows. \vskip .10in \parindent=0pt The left edge $L^c(t)$ jumps one unit to the left whenever it encounters an arrow from $L^c(t)-1$ to $L^c(t)$ or whenever the rightmost particle in $\lbrack 0, L^c(t)-2\rbrack$ jumps. \vskip .05in The right edge $R^c(t)$ jumps one unit to the left whenever it encounters an arrow from $R^c(t)$ to $R^c(t)+1$ or whenever the rightmost particle in $\lbrack 0,R^c(t)-1\rbrack$ jumps. \vskip .1in \parindent=20pt It is clear from the above rules that there are cases where the left and the right edge jump simultaneously, namely, (i) when at least one of the edges is occupied and the interval $\lbrack L^c(t)+1, R^c(t)-1\rbrack $ is empty, and (ii) when $\lbrack L^c(t), R^c(t)\rbrack $ is empty. In all other cases, the left and the right edge evolve independently of each other. In the first case, the left and the right edge jump simultaneously if either the left edge is occupied, $\lbrack L^c(t)+1, R^c(t)-1\rbrack $ is empty (the right edge may or may not be occupied) and the particle on the left edge jumps, that is, there is an arrow from $L^c(t)-1$ to $L^c(t)$, or the left edge is vacant, the right edge is occupied, $\lbrack L^c(t)+1, R^c(t)-1\rbrack $ is empty and the rightmost particle in $\lbrack 0, L^c(t)-2\rbrack $ jumps. The second case will not be important to us since if $\lbrack L^c(t),R^c(t)\rbrack $ is empty, it will remain empty. The evolution of the left edge process $L^c(s)$, $0\leq s\leq t$, is defined in such a way that when we follow the evolution from $t$ to 0, the following two conditions hold true: (1) A particle starting on or to the right of the left edge at time $t$ remains on or to the right of the left edge during $\lbrack 0,t\rbrack $, and (2) a particle which starts to the left of the left edge at time $t$, remains to the left of the left edge during $\lbrack 0,t\rbrack $. The evolution of the right edge process $R^c(s)$, $0\leq s\leq t$, is defined in such a way that when we follow the evolution from $t$ to 0, the following two conditions hold true: (1) A particle starting on or to the left of the right edge at time $t$ remains on or to the left of the right edge during $\lbrack 0,t\rbrack $, and (2) a particle which starts to the right of the right edge at time $t$, remains to the right of the right edge during $\lbrack 0,t\rbrack $. This allows us to define the above mentioned cone. We observe that the evolution of $R^c(s)+1$ is defined by rules which are identical to the rules defining the evolution of $L^c(s)$. Therefore, we conclude that $R^c(s)$, $0\leq s\leq t$, evolves like $L^c(s)$, $0\leq s\leq t$, and statements about the evolution of the left edge hold as well for the right edge. Our first lemma states that the path of the left edge between time 0 and time $t$ does not depend on the exact location of the particles to its left at time $t$. That is, if we denote by ${\cal L}(\lbrack 0,t\rbrack )$ the random variable which describes the path of $L^c(s)$ for $0\leq s\leq t$, by $l_{(x,0)}^{(y,t)}$ a realization of the left edge starting at $(x,0)$ and ending at $(y,t)$, and by $\eta^c_t$ the configuration of the coalescing random walks at time $t$, then the following holds: \vskip .20in \parindent=0pt {\bf Lemma 4.} {\sl Let $\eta_1^c$ and $\eta_2^c$ be two subsets of $\lbrack 1, y\rbrack$. Then $$P({\cal L}(\lbrack 0,t\rbrack )=l_{(x,0)}^{(y,t)}\mid \eta^c_t\cap\lbrack 1,y\rbrack =\eta_1^c)= P({\cal L}(\lbrack 0,t\rbrack )=l_{(x,0)}^{(y,t)}\mid \eta^c_t\cap\lbrack 1,y\rbrack =\eta_2^c).$$ } \vskip .20in {\bf Proof.} Assume $L^c(s)=z$. The movement of the left edge is governed by two independent processes: (i) arrows from $z-1$ to $z$ and (ii) jumps of the rightmost particle in $\lbrack 0,z-2\rbrack $ if $\lbrack 0,z-1\rbrack\cap{\bf Z} \not= \emptyset $, and a birth at 0 otherwise. If $\eta_1^c\cap \lbrack 1,y-1 \rbrack\not=\emptyset$, then there are particles to the left of the left edge throughout $\lbrack 0,t\rbrack $ and hence there is always a rightmost particle which jumps at rate 1 (following arrows) regardless of its position. \eopt \vskip .20in \parindent=20pt The next lemma describes the movement of the left (or right) edge. \vskip .20in \parindent=0pt {\bf Lemma 5.} {\sl The left edge jumps at rate 2, that is, $$P(L^c(t+h)=y-1, L^c(t)=y)=2h P(L^c(t)=y)+o(h).$$ } \vskip .20in {\bf Proof.} The key ingredient is Lemma 4 which states that the movement of $L^c(s)$, $0\leq s\leq t$, is independent of the particle configuration to the left of it at time $t$. The statement in Lemma 5 then follows immediately from $$\eqalign{P(L^c(t+h)=y-1, L^c(t)=y)&=P(L^c(t)=y; N_{t+h}(\lbrack 1, y-2 \rbrack )\geq 1)\cdot 2h\cr &+P(L^c(t)=y; N_{t+h}(\lbrack 1, y-2 \rbrack )=0)\cdot 2h +o(h)\cr}$$ since the left edge jumps at rate 1 whenever it encounters an arrow, or - if there are particles to its left - whenever the rightmost particle to its left jumps, or - if there are no particles to its left - whenever a birth occurs at the origin. The last two events each happen at rate 1. \eopt \parindent=20pt \vskip .20in We conclude that the motion of the difference process $Z(t)=R^c(t) -L^c(t)$ is thus a rate 4 random walk as long as the edges are not in states where they jump simultaneously (in which case $Z(t)$ stays put and hence $Z(t)$ only jumps at rate 2). Note that it follows from the above construction that if there is a particle in the interval $I(t)$, then $Z(t)$ will never become negative. However, if there is no particle in $I(t)$, then the right edge can jump over the left edge in which case $Z(t)<0$ and we say that the cone has died. To obtain a ``duality'' equation we let $$T^c=\inf\lbrace t: \zeta_t^c=\emptyset\rbrace =\inf\lbrace t: Z(t)<0\rbrace \leqno(3.1)$$ and $$\tau^c=\inf\lbrace t: L^c(t)\leq 0\rbrace .\leqno(3.2)$$ Then the following will serve as the duality equation: $$\lbrace x\in\xic_t\rbrace =\lbrace\tau^c < T^c\rbrace . \leqno(3.3)$$ As in the case without co-jumping we need the asymptotic behavior of the probability of survival of the interval $I(t)$ and the asymptotic behavior of the length of the interval $I(t)$ conditioned on survival. This is made more difficult by the fact that the left and the right edge may co-jump. The first step will therefore be to find an a priori estimate on the total number of times the left edge and the right edge co-jump. Let $K(x)$ denote the total number of co-jumping events in the dual process when starting from $\zeta_0^c =\lbrace x\rbrace $ until either the left edge hits the origin or the dual process dies out. The following result provides us with an a priori estimate on $EK(x)$. \vskip .20in {\spa {\bf Proposition 3.} There exists $\gamma >0$ so that $$EK(x)\leq \gamma\sqrt{x}.\leqno(3.4)$$ \vskip .20in } The proof of Proposition 3 involves several steps of which the first one is to find an a priori estimate on the total amount of time the left edge and the right edge may co-jump. We will suppress the dependency on $x$ below to simplify notation. Let $$\chi_s={\bf 1}_{\lbrace \hbox{co-jumping possible at time $s$} \rbrace}\leqno(3.5)$$ and $$T_t=\int_0^t\chi_s ds. \leqno(3.6)$$ As explained above, co-jumping can have different sources: When there are particles in $I(s)$, then co-jumping can only occur when both edges are occupied by neighboring particles or when there is only one particle in $I(s)$ and the particle is at either $L^c(s)$ or $R^c(s)$. We can decompose $\chi_s$ into two parts: $$\eqalign{ \chi_s&= {\bf 1}_{\lbrace L^c(s)\ {\rm or}\ R^c(s)\ {\rm occupied}, N(\lbrack L^c(s), R^c(s)\rbrack )=1, R^c(s)\geq L^c(s)\rbrace }\cr &+{\bf 1}_{\lbrace L^c(s)\ {\rm and} \ R^c(s)\ {\rm occupied}, N(\lbrack L^c(s), R^c(s)\rbrack )=2, R^c(s)>L^c(s)\rbrace }\cr &\equiv\chi_s^{(1)}+\chi_s^{(2)}\cr}\leqno(3.7)$$ and write $$T_t=T_t^{(1)}+T_t^{(2)}\hskip 1in {\rm with}\ T_t^{(i)}=\int_0^t\chi_s^{(i)}ds.\leqno(3.8)$$ We need the following definition. If $z$ is occupied in the forward process (i.e., the coalescing random walk $\xi^c_t$) then set $$C(z)=\hbox{location of the nearest neighbor to the right}. \leqno(3.9)$$ Then we can rewrite $\chi_s^{(2)}$ as $$\chi_s^{(2)}={\bf 1}_{\lbrace C(L^c(s))=R^c(s), L^c(s)\ \hbox{ occupied} \rbrace }.\leqno(3.10)$$ The following lemma contains an estimate on $ET_t^{(1)}$ and $ET_t^{(2)}$. \vskip .20in {\parindent=0pt {\bf Lemma 6.} {\sl There exists $C >0$ so that $$ET_t^{(1)}\leq {C\over 2}\sqrt{t}.\leqno(3.11)$$ $$ET_t^{(2)}\leq {C\over 2}\sqrt{t}.\leqno(3.12)$$ } \vskip .20in } \parindent=0pt {\bf Proof.} The idea of the proof is the following. We start a voter model at $x$ at time 0 and run it for $s$ units of time. If it is still alive at time $s$, then it is an interval of length $N_s$. The length is random and if we denote by $Z(s)$ the random walk defined above, and set $$T^c =\inf\lbrace r: N_r <0\rbrace ,\leqno(3.13)$$ then $$P(N_s=z)=P^0 (Z(s)=z;\tau >s)\leq P^0 (Z(s)=z-1)\leqno(3.14)$$ where the superscript at $P$ is the starting point. It follows from the local central limit theorem that there exists a constant $C >0$ which does not depend on $s$ or $z$ such that $$P^0(Z(s)=z)\leq {C\over4\sqrt{s}}.\leqno(3.15)$$ Note that for the estimate in (3.15), we do not need to know the exact distribution of $\chi_s$. It suffices to know that $Z(s)$ is a mixture of the two random walks described. \npa We stop the voter model at time $s$ and think of it as ``landing'' on the stationary distribution of the coalescing random walk with source at the origin. Of course, neither $L^c(s)$ nor $R^c(s)$ need to be occupied by a particle. We estimate $E_t^{(1)}$ and $E_t^{(2)}$ separately. We begin with $E_t^{(2)}$. Then $$\eqalign{ &P\lbrack C(L^c(s))=R^c(s), L^c(s)\ \hbox{occupied}\rbrack \cr &=\sum_{y\geq 1} P\lbrack R^c(s)=L^c(s)+y ,L^c(s)\ \hbox{occupied}, C(L^c(s))=L^c(s)+y\rbrack \cr &=\sum_{y\geq 1} P\lbrack R^c(s)=L^c(s)+y \mid L^c(s)\ \hbox{occupied}, C(L^c(s))=L^c(s)+y\rbrack \cr &\hskip 1in \times P\lbrack C(L^c(s))=L^c(s)+y \mid L^c(s)\ \hbox{occupied} \rbrack P\lbrack L^c(s)\ \hbox{occupied}\rbrack . \cr }\leqno(3.16)$$ Given that the left edge lands on an occupied site and that the co-jumper of that particle is $y$ steps to the right of it, the probability that the width of the interval created by the modified voter model is $y$, is bounded by $C/ 4\sqrt{s}$. The reason why this is true is the following. We first run the forward process long enough so that we get a stationary distribution at time $s$. The graphical representation in $\lbrack 0,s)$ is independent of that. We just need to put down rate 1 arrows. What is not independent, is the amount of time co-jumping events occur in the modified dual in $\lbrack 0,s)$. We know from Lemma 4 that the motion of the left and right edges in [0,s) given the occupation number of the edges at time s are rate 2 random walks. Since no matter how often both edges are occupied by neighboring particles, the difference is either a rate 2 or a rate 4 random walk. The estimate (3.15) holds for any mixture of that sort. Hence, using (3.15), $$\eqalign{&ET_t^{(2)}\leq\int_0^t P\lbrack C(L^c(s))=R^c(s), L^c(s)\ \hbox{occupied}\rbrack ds \cr &\leq\int_0^t {C\over 4\sqrt{s}} \sum_{y\geq 1}P\lbrack C(L^c(s))- L^c(s) = y\mid L^c(s)\ \hbox{occupied} \rbrack P\lbrack L^c(s)\ \hbox{occupied}\rbrack ds \cr &=\int_0^t {C\over 4\sqrt{s}} P\lbrack C(L^c(s))- L^c(s)\geq 1 \mid L^c(s)\ \hbox{occupied}\rbrack P\lbrack L^c(s)\ \hbox{occupied}\rbrack ds \cr &=\int_0^t {C\over 4\sqrt{s}} P\lbrack L^c(s)\ \hbox{occupied}\rbrack ds \leq \int_0^t {C\over 4\sqrt{s}}ds ={C\over 2} \sqrt{t}. \cr}\leqno(3.17)$$ To estimate $ET_t^{(1)}$, we define $D(z)=\sup\lbrace y\in {\bf Z}^+, y\leq z: y\ \hbox{is occupied}\rbrace $. Then $$\eqalign{ &P(L^c(s)\ {\rm occupied}, N(\lbrack L^c(s), R^c(s)\rbrack )=1)\cr &=P(R^c(s)\ \hbox{empty}, D(R^c(s))=L^c(s))\cr &=\sum_{y=1}^{R^c(s)-1} P(R^c(s)\ \hbox{empty}, R^c(s)-L^c(s)=y, D(R^c(s))=R^c(s)-y). \cr}\leqno(3.18)$$ Since the events $\lbrace D(R^c(s))=R^c(s)-y)\rbrace $ and $\lbrace R^c(s)\ \hbox{empty}\rbrace $ are independent of $\lbrace R^c(s)-L^c(s)=y\rbrace $ by Lemma 4, we obtain, using the a priori estimate (3.15), the following upper bound on (3.18). $$\eqalign{ &\leq {C\over 8\sqrt{s}}\sum_{y=1}^{R^c(s)-1} P(R^c(s)\ \hbox{empty}, D(R^c(s))=y)\cr &={C\over 8\sqrt{s}}\sum_{z\geq 1}\sum_{y=1}^{z-1} P(R^c(s)\ \hbox{empty}, R^c(s)=z, D(z)=y)\cr &={C\over 8\sqrt{s}}\sum_{z\geq 1}\sum_{y=1}^{z-1} P(z\ \hbox{empty}, D(z)=y \mid R^c(s)=z ) P(R^c(s)=z )\cr &\leq {C\over 8\sqrt{s}}\sum_{z\geq 1}P(R^c(s)=z )\leq {C\over 8\sqrt{s}} . \cr}$$ A similar argument proves an identical estimate in the case when the right edge is occupied and $N(\lbrack L^c(s), R^c(s)\rbrack )=1$. Hence, $$\eqalign{ET_t^{(1)}&\leq 2 \int_0^t P(L^c(s)\ {\rm occupied}, N(\lbrack L^c(s), R^c(s)\rbrack )=1)ds\cr &\leq {C\over 4}\int_0^t {1\over \sqrt{s}}ds ={C \over 2} \sqrt {t}.\cr} \leqno(3.19)$$ \spa This completes the proof of Lemma 6. \eop \vskip .20in \npa It is now straightforward to prove Proposition 3. \vskip .20in \spa {\bf Proof of Proposition 3.} Lemma 6 implies that $$ET_t\leq C\sqrt{t}.$$ If $M(t)$ is a Poisson process with rate $\lambda$, then $M(t)-\lambda t$ is a martingale. Applying the optional stopping theorem to $K(x)$ and observing that the rate at which co-jumping occurs is finite (in fact, $\leq 4$) then finishes the proof. \eop \vskip .20in \npa The a priori estimate in Proposition 3 will be used to show a local central limit theorem for the discrete time embedding of $Z(t)$. This is the analogue of (2.8) and one of the key estimates in the proof. Let $Z(t)$ be the continuous time random walk defined above as a mixture of a rate 4 and rate 2 random walk. It changes by $+1$ or $-1$ with equal probabilities. We can also think of $Z(t)$ as run by a rate 4 exponential clock and, whenever $Z(t)$ is in one of the co-jumping cases, it stays put with probability $1/2$, thus yielding the rate 2 random walk; we denote by $S_n^c$ its discrete time embedding. We can then write $S_n^c$ as a sum of $X_i$'s and $Y_i$'s where the $X_i$'s take values $\pm 1$ with equal probabilities and the $Y_i$'s take value 0 with probability $1/2$ and values $\pm 1$ with probability $1/4$ each. That is, the $X_i$'s correspond to the jumps in the rate 4 random walk and the $Y_i$'s to the jumps in the rate 2 random walk. Denote by $M$ the number of occurrences of the $Y_i$'s by time $n$. Then $$S_n^c=\sum_{k=1}^{n-M} X_k +\sum_{k=1}^{M} Y_k .\leqno(3.20)$$ We cannot say much about the order in which the $X_i$'s and the $Y_i$'s occur. But this is not needed. All we need is an estimate on the total expected number of times the random walk stays put (that is, when co-jumping occurs). This is provided by Proposition 3. That is, we assume that there exists a constant $\gamma >0$ so that $$EK(x)\leq \gamma \sqrt{x}.\leqno(3.21)$$ As in Section 2 we denote by $A_n^c$ ($B_n^c$) the number of times the left (right) edge jumps by time $n$. (Note in a co-jumping event, both $A_n^c$ and $B_n^c$ increase by one simultaneously so that the change in $S_n$ is zero.) Let $W^c =\inf \lbrace n: A_n^c =x\rbrace $ and $T^c=\inf\lbrace n: A_n^c 2x)=P(S_{2x}^c=y)-P(S_{2x}^c=y+2)$$ for $y\geq 0$. Therefore, $$\eqalign{P(S_n^c\geq 0\ \hbox{for all }\ n\leq 2x)&=\sum_{y\geq 0} \lbrack P(S_{2x}^c=y)-P(S_{2x}^c=y+2)\rbrack \cr &=P(S_{2x}^c=0)-P(S_{2x}^c=1)\cr}\leqno(3.22)$$ That is, we need to investigate the asymptotic behavior of $\sqrt{\pi x}\lbrack P(S_{2x}^c=0)-P(S_{2x}^c=1)\rbrack $. We will use a standard harmonic analysis argument to do this (see, e.g., Spitzer (1964), Section 7). We set $$\phi_1(\theta)=Ee^{i\theta X_k}={1\over 2} (e^{i\theta}+ e^{-i\theta})=\cos\theta \leqno(3.23)$$ and $$\phi_2(\theta)=Ee^{i\theta Y_k}={1\over 2}+{1\over 4} (e^{i\theta}+ e^{-i\theta})={1\over 2}(1+\cos\theta) \leqno(3.24)$$ Since $S_0^c=0$, it follows that $$\eqalign{Ee^{i\theta S_n^c}=&Ee^{i\theta\lbrack\sum_{k=1}^{n-M} X_k+\sum_{k=1}^MY_k\rbrack}=E\lbrace E\lbrack e^{i\theta\lbrack\sum_{k=1}^{n-M} X_k+\sum_{k=1}^MY_k\rbrack}\mid M=m\rbrack\rbrace\cr &=\sum_{m=0}^n\phi_1(\theta)^{n-m}(\theta)\phi_2^m(\theta)P(M=m)\cr.} \leqno(3.25)$$ A standard argument then yields $$P(S_n^c=y)={1\over 2\pi}\int_{-\pi}^\pi e^{-i\theta y} \sum_{m=0}^n\phi_1(\theta)^{n-m}(\theta)\phi_2^m(\theta)P(M=m) d\theta . \leqno(3.26)$$ Setting $n=2x$ and using (3.23) and (3.24), we get $$P(S_{2x}^c=y)=\sum_{m=0}^{2x}P(M=m){1\over 2\pi}\int_{-\pi}^\pi e^{-i\theta y} (\cos\theta )^{2x-m}\lbrack {1\over 2}(1-\cos\theta) \rbrack^m d\theta .\leqno(3.27)$$ To carry out the integration, we use the same trick as on page 78 in Spitzer (1964) together with the observation that terms for odd $m$ do not contribute in the limit and obtain $$P(S_{2x}^c=y)=2\sum_{m=0}^{x}P(M=2m){1\over 2\pi}\int_{-\pi /4}^{\pi /4} e^{-i\theta y} (\cos\theta )^{2(x-m)}\lbrack {1\over 2}(1-\cos\theta) \rbrack^{2m} d\theta .\leqno(3.28)$$ We make the substitution $\theta \sqrt{2x}=\lambda$, then the right hand side of (3.28) is $$\eqalign{&=2\sum_{m=0}^{x}P(M=2m){1\over 2\pi}{1\over \sqrt{2x}} \cr &\times \int_{-\pi \sqrt{2x} /4}^{\pi \sqrt{2x}/4} e^{-i\lambda y/\sqrt{2x}} (\cos{\lambda \over \sqrt{2x}} )^{2(x-m)}\lbrack {1\over 2}(1-\cos {\lambda \over \sqrt{2x}}) \rbrack^{2m} d\lambda .\cr}\leqno(3.29)$$ We split the sum into two parts, namely $\sum_{m=0}^{\lfloor x^{0.6} \rfloor}\dots +\sum_{m>x^{0.6}}\dots $. It follows from Proposition 3 that $$P(M>x^{0.6})\leq {EM\over x^{0.6}}\leq Cx^{-0.1}$$ from which it follows that the second term will not contribute. For the first sum, note that for $0\leq m\leq\lfloor x^{0.6}\rfloor $, $${1\over \sqrt{2\pi}}\int_{-\pi \sqrt{2x} /4}^{\pi \sqrt{2x}/4} e^{-i\lambda y/\sqrt{2x}} (\cos{\lambda \over \sqrt{2x}} )^{2(x-m)}\lbrack {1\over 2}(1-\cos {\lambda \over \sqrt{2x}}) \rbrack^{2m} d\lambda \to 1$$ as $x$ tends to infinity. Hence the right hand side of (3.29) is asymptotically $$\sim2\sum_{m=0}^{x}P(M=2m){1\over 2\pi}{1\over \sqrt{2x}}\sim {1\over \sqrt{4\pi x}}\leqno(3.30)$$ since $P(M$ even$)/P(M$ odd$)\to 1$ as $x\to\infty$. Combining (3.22) and (3.30) shows the claim. \eop \vskip .30in \npa Following the program in Section 2, the next step is to modify Lemma 2. Not surprisingly, the result looks the same. \vskip .20in \spa {\bf Lemma 7.} {\sl Under assumption (3.21), there exists $C_1>0$ so that $$P(S^c_{2x}\leq u\sqrt{x}\mid T^c >2x)\leq C_1u^2 .\leqno(3.31)$$ } \vskip .20in The proof is essentially the same as for Lemma 2 whose proof can be found in Liggett (1985), Chapter V, Theorem 4.9(b). The only modification needed is that (3.26) replaces the simpler form of $P(S_n=y)$ in the case without co-jumping. The same tricks as in the proof of Proposition 4 then allow us to obtain the result. We omit the details. \npa It is now easy to prove the analogue of Proposition 1. \vskip .30in \spa {\bf Proposition 5.} $$\lim_{x\to\infty}\sqrt{\pi x } P(x\in\xic_\infty)=1.$$ \vskip .30in {\bf Proof.} By duality (equation (3.3)), $$\lbrace T^c\leq W^c\rbrace =\lbrace x\notin\xi_\infty^c\rbrace$$ Hence using Proposition 4, we can obtain $\lim_{x \to\infty}\sqrt{\pi x}P(x\in\xi_\infty^c)$: $$\lim_{x\to\infty}\sqrt{\pi x}P(x\in\xi_\infty^c)= \lim_{x\to\infty}\sqrt{\pi x}P(T^c>W^c)=1.\leqno(3.32)$$ \eop \vskip .30in The analogue of Proposition 2 is contained in the following proposition: \vskip .30in {\parindent=0pt {\bf Proposition 6.} $$\lim_{x\to\infty} {P(x\in\etac_\infty)\over P(x\in\xic_\infty)}= {1\over 2}.$$ } \vskip .30in The proof of Proposition 6 is the same as the proof of Proposition 2. Putting everything together as in Section 2 then implies Theorem 1. \vskip .50in {\bf Acknowledgements.} The authors wish to thank Maury Bramson and E. Speer for fruitful discussions in the beginning of the project. \vskip .50in \centerline{\bf References} \vskip .20in \frenchspacing \mn \rf Arratia, R. (1981). Limiting point processes for rescalings of coalescing and annihilating random walks on ${\bf Z}^d$. {\it Ann. Probab.} {\bf 9}, 909--936. \mn \rf Bennet, C. and Grinstein, G. (1985). Role of irreversibility in stabilizing complex and nonergodic behavior in local interacting particle systems. {\it Phys. Rev. Lett.} {\bf 55}, 657--660. \mn \rf Bramson, M. and Gray, L. (1991). A useful renormalization argument. In {\it Random Walks, Brownian Motion, and Interacting Particle Systems. A Festschrift in Honor of Frank Spitzer.} Eds., Rick Durrett and Harry Kesten. Progress in Probability, vol. 28. Birkh\"auser. \mn \rf Bramson, M. and Griffeath, D. (1980). Asymptotics for interacting particle systems on ${\bf Z}^d$. {\it Z. Wahrscheinlichkeitstheorie verw. Gebiete} {\bf 53}, 183--196. \mn \rf Clifford, P. and Sudbury, A. (1973). A model for spatial conflict. {\it Biometrika} {\bf 60}, 581--588. \mn \rf Derrida, B., Lebowitz, J.L., Speer, E.R., and Spohn, H. (1991). Dynamics of an anchored Toom interface. {\it J. Phys. A: Math. Gen.} {\bf 24}, 4805--4834. \mn \rf Durrett, R. (1988). {\it Lecture Notes on Particle Systems and Percolation}, Wadsworth, California. \mn \rf Durrett, R. (1992). {\it Probability: Theory and Examples.} Wadsworth, California. \mn \rf Griffeath, D. (1979). {\it Additive and Cancellative Interacting Particle Systems}, Lecture Notes in Mathematics 724, Springer, New York. \mn \rf Harris, T.E. (1972). Nearest neighbor Markov interaction processes on multidimensional lattices. {\it Adv. Math} {\bf 9}, 66--89. \mn \rf Holley, R. and Liggett, T.M. (1975). Ergodic theorems for weakly interacting systems and the voter model. {\it Ann. Probab.} {\bf 3}, 643--663. \mn \rf Lebowitz, J.L., Maes, C., and Speer, E.R. (1990). Statistical mechanics of probabilistic cellular automata. {\it J. Stat. Phys.} {\bf 59}, 117--168. \mn \rf Liggett, T. (1985). {\it Interacting Particle Systems}, Springer, New York. \mn \rf Spitzer, F. (1964). {\it Principles of Random Walk}, Springer, New York. \mn \rf Toom, A. (1974). Nonergodic multidimensional systems of automata. {\it Problems Inform. Transmission} {\bf 10}, 239--246. \vskip .50in %\vfill\eject {\settabs 4 \columns \+Department of Mathematics &&Department of Mathematics \cr \+(also Department of Physics) &&University of Wisconsin \cr \+Rutgers University &&480 Lincoln Drive \cr \+New Brunswick, NJ 08903 &&Madison, WI 53706 \cr \+ \cr \+Department of Mathematics and Computer Science \cr \+State University of New York \cr \+College at New Paltz \cr \+New Paltz, NY 12561 \cr} \vfill\eject \centerline{FIGURE CAPTIONS} \vskip .30in \parindent=0pt Figure 1.1. Staircase configuration of the anchored interface in the third quadrant as described in Derrida et al. (1991). A fluctuation at the circled site causes the staircase to quickly change into a new staircase indicated by the broken line. \vskip .20in Figure 1.2. The staircase from Figure 1.1 written as a sequence of spins. A fluctuation at the circled spin in Figure 1.1 together with the subsequent change of the staircase corresponds to the exchange of the underlined spins on the first line resulting in the configuration on the second line. \vskip .20in Figure 1.3. Successive transitions in the first approximation of the spin exchange model together with the border process. \vskip .20in Figure 3.1. Coalescing random walks with co-jumping and source at the origin. \end