\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