The Reversible Nearest Particle System on a Finite Interval *   *   Supported in part by Grant G1999075106 from the Ministry of Science and Technology of China

Dayue Chen, Juxin Liu and Fuxi Zhang † † corresponding author, E-mail: zhangfxi@math.pku.edu.cn.

Abstract: In this paper we study a one-parameter family of attractive reversible nearest particle system on a finite interval. As the length of the interval increases, the time that the nearest particle system first hits the empty set increases in different order, from logarithmic to exponential, according to the intensity of interaction. In particular, at the critical case, the first hitting time increases in a polynomial order.
Keywords: first hitting time, nearest particle system.

1 Introduction

A nearest particle system on S = { 1 , 2 , ⋯ , N }   is a continuous time Markov chain with the state space { A : A ⊂ S }   . The jump rates are specified as follows:
q ( A , A \ { x } ) = 1 i f x ∈ A ;
q ( A , A ∪ { x } ) = β ( l x ( A ) , r x ( A ) ) i f x ∈ S \ A ;
q ( A , B ) = 0 o t h e r w i s e .
Here l x ( A )   and r x ( A )   are the distances from x   to the nearest points in A   to the left and right respectively, with convention that l x ( A )   (or r x ( A )   ) is ∞   if y > x   (or y < x   , respectively) for all y ∈ A   . We assume that 1. β ( l , r ) = β ( r , l )   ; 2. β ( l , r )   is decreasing in l   and in r   ; 3. β ( ∞ , ∞ ) = 0 , β ( l , ∞ ) > 0   ; 4. ∑ l β ( l , ∞ ) < ∞   .
There are many choices of β ( ⋅ , ⋅ )   satisfying the above assumptions.
Example 1. (The 1-dim contact process) β ( 1 , 1 ) = 2 λ   , β ( 1 , r ) = β ( l , 1 ) = λ   for l , r > 1   , and β ( l , r ) = 0   otherwise.
Example 2. (The uniform birth rate) β ( l , r ) = λ / ( l + r − 1 )   .
Example 3. (The reversible case) β ( l , r ) = λ ψ ( l ) ψ ( r ) ψ ( l + r ) , β ( l , ∞ ) = β ( ∞ , l ) = λ ψ ( l ) ,   where
ψ ( ⋅ ) > 0 , ∑ n = 1 ∞ ψ ( n ) = 1 , and ψ ( n ) ψ ( n + 1 ) ↘ 1 . (1)
Assume further that
∑ n n 2 ψ ( n ) < ∞ . (2)
For example, ψ ( n ) = c n − α   for some α > 3   satisfies the above requirement.
It is helpful to associate a subset A   of S   with an element ξ   of { 0 , 1 } S   and use them interchangeably: ξ ( x ) = 1   if and only if x ∈ A   . Configuration ξ   will be given an occupancy interpretation. We say there is a particle in x   if ξ ( x ) = 1   , and we say the site is vacant if ξ ( x ) = 0   . Then the above transition mechanisms can be interpreted as follows: Each particle disappears at rate 1 independently, and a particle is born at vacant site x   at rate β ( l x ( A ) , r x ( A ) )   .
The transition mechanisms also make sense if we replace { 1 , 2 , ⋯ , N }   with the integer lattice Z   . However, because of Assumption 4, the state space { 0 , 1 } Z   consists of four disjoint parts:
1) all finite subsets of Z   ; 2) all subsets of Z   with infinite many particles both to the left and to the right of the origin; 3) all infinite subsets of Z   with finite many particles to the right of the origin; and 4) all infinite subsets of Z   with finite many particles to the left of the origin.
The first two cases are extensively studied, and are called finite and infinite nearest particle systems respectively. A comprehensive account can be found in Chapter 7 of Liggett (1985). The last two cases share many properties of the first two cases, and are indispensable in some occasions, e.g., Lemma 4.1.
For interacting particle systems people are most concerned with the existence of phase transition and the critical value. For the infinite nearest particle system with the uniform birth rate (Example 2), the critical value is 1, see Mountford (1992).
For the reversible nearest particle system (Example 3), the critical value is also 1.
For the contact process (Example 1), the critical value is unknown but is between 1.5 and 2, and is denoted as λ c   throughout this paper.
Can the critical value of an infinite model be detected by the counterpart on a finite interval? This interplay was first explored for the contact process in a series paper by Durrett et al. The main results are summerized as follows. Let { ζ t N : t ≥ 0 }   be the contact process on { 1 , 2 , ⋯ , N }   with the parameter λ   starting from all sites occupied, and τ N   be the first time it hits the empty set.
Theorem 1.1 (i) If λ < λ c   , then there is a constant γ 1 ( λ ) > 0   so that as N → ∞   , τ N / log N → 1 / γ 1 ( λ )   in probability (Durrett and Liu (1988), Theorem 1).
(ii) If λ > λ c   , then there is a constant γ 2 ( λ ) > 0   so that as N → ∞   , ( log τ N ) / N → γ 2 ( λ )   in probability (Durrett and Schonmann (1988), Theorem 2). (iii) If λ = λ c   and a , b ∈ ( 0 , ∞ )   , then P ( a N ≤ τ N ≤ b N 4 ) → 1   as N → ∞   (Durrett et al (1989), Theorem 1.6).
We believe that these statements hold for a large class of interacting particle systems. In this paper we like to study the asymptotical behavior of the hitting time σ N   of the reversible nearest particle systems (Example 3) on a finite interval, as the length of interval increases. The results read as follows. Let { C N : N ≥ 1 }   be any sequence of increasing numbers such that lim N → ∞ C N = ∞   .
Theorem 1.2 Suppose the initial state is { 1 , 2 , ⋯ , N }   .
(1) If λ < min { 1 , min n ψ ( n ) ∑ l + r = n ψ ( l ) ψ ( r ) } ,   then E σ N ≤ C log N   for some constant C   which is independent of N   , and lim N → ∞ P ( σ N ≤ C N log N ) = 1 ;   (2) If λ > 1   , then there is a constant γ > 0   such that lim N → ∞ P ( σ N ≥ e γ N ) = 1 .  
Remarks: It is not difficult to establish estimates of the opposite direction, see Theorems  2.3 and  2.4 . Together we have shown that σ N   increases logarithmically if λ   is small enough and exponentially if λ > 1   .
For any non-empty set A = { x 1 , x 2 ⋯ , x k }   , we assume without loss of generality that x 1 < x 2 < ⋯ < x k   and define ν ψ ( A ) = { ψ ( x 2 − x 1 ) ψ ( x 3 − x 2 ) ⋯ ψ ( x k − x k − 1 ) i f k > 1 ; 1 i f k = 1 .   Let S N = { 0 , 1 } { 1 , ⋯ , N }   , K N = ∑ A ∈ S N \ { ∅ } ν ψ ( A )   , and π ( A ) = ν ψ ( A ) / K N .   Then π   is a probability measure on S N   .
Theorem 1.3 Suppose that λ = 1   and the initial distribution is π   . Then lim N → + ∞ P ( N C N ≤ σ N ≤ C N N 2 ) = 1 .  
We now proceed to prove Theorems  1.2 and  1.3 by three different approaches.

2 Comparison by Coupling

We will prove the first part of Theorem  1.2 by establishing a more general conclusion (Theorem  2.2 ). Let { X t : t ≥ 0 }   be a birth and death process on { 0 , 1 , ⋯ , N }   with
death rate : a i = i , for i = 1 , ⋯ , N ;
birth rate : b i = ( i + 1 ) α , for i = 0 , ⋯ , N − 1 .
Let τ = inf { t > 0 : X t = 0 }   be the first time that { X t : t ≥ 0 }   hits 0   . Let E N   be the conditional expectation on X 0 = N   .
Lemma 2.1 Suppose that X 0 = N   . For large N   , E N τ ≤ { ( 2 log N ) / ( 1 − α ) i f α < 1 ; 2 N log N i f α = 1 ; α N α / ( α − 1 ) 2 i f α > 1 .   Furthermore
E N τ 2 ≤ 2 ( E N τ ) 2 . (3)
Proof. Let P i   be the conditional probability distribution on the initial state i   , E i   be the expectation with respect to P i   , and m i = E i τ   for i = 0 , ⋯ , N   . It is shown in Wang (1980) that E N τ = ∑ i = 1 N e i , E N τ 2 = ∑ i = 1 N ɛ i ,   where
e i = 1 a i + ∑ k = 0 N − 1 − i b i b i + 1 ⋯ b i + k a i a i + 1 ⋯ a i + k a i + k + 1 (4)
= 1 i ( 1 + α + α 2 + ⋯ α N − i ) . (5)
ɛ i = 2 m i a i + ∑ k = 0 N − 1 − i 2 b i b i + 1 ⋯ b i + k m i + k + 1 a i a i + 1 ⋯ a i + k a i + k + 1
Notice that m i ≤ m N   for any i ≤ N   . It follows that ɛ i ≤ 2 m N e i   . Therefore, E N τ 2 = ∑ i = 1 N ɛ i ≤ 2 m N ∑ i = 1 N e i ≤ 2 m N E N τ = 2 ( E N τ ) 2 .   If α = 1   , by ( 5 ), e i = ( N − i + 1 ) / i   , and for large N   , E N τ = ∑ i = 1 N e i ≤ N ∑ i = 1 N i − 1 ≤ 2 N log N .   If α < 1   , E N τ = ∑ i = 1 N e i ≤ ( 1 − α ) − 1 ∑ i = 1 N i − 1 ≤ ( 2 log N ) / ( 1 − α ) ;   If α > 1   , then E N τ = ∑ i = 1 N e i ≤ ( α − 1 ) − 1 ∑ i = 1 N α N − i + 1 ≤ α N + 1 / ( α − 1 ) 2   . □   Consider a nearest particle system { ξ t N : t ≥ 0 }   on { 1 , 2 , ⋯ , N }   starting from { 1 , 2 , ⋯ , N }   (not necessarily reversible). Let σ N   be the first hitting time of the empty set by ξ t N   , and M = max { max n ∑ l + r = n β ( l , r ) , ∑ l β ( l , ∞ ) } .  
Theorem 2.2 Suppose the initial state is { 1 , 2 , ⋯ , N }   . If M < 1   , then E σ N ≤ ( 2 log N ) / ( 1 − M )   ; and for any sequence { C N : N ≥ 1 }   of increasing numbers such that lim N → ∞ C N = ∞   , lim N → ∞ P ( σ N ≤ C N l o g N ) = 1   .
Proof. Let | A |   be the cardinality of set A   . For any configuration ξ   such that | ξ | = i   , there are at most i + 1   intervals of consecutive vacant sites, separated by occupied sites; the rate that a new particle in each interval is born is no more than M   . Hence the rate that | ξ t N |   increases by 1 is no more than ( i + 1 ) M   . On the other hand, when | ξ t | = i   , the rate that | ξ t |   decreases by 1 is equal to i   , the total number of particles. Compare | ξ t |   with a birth and death process X t   with parament α = M   . Since initially X 0 = | ξ N |   , there is a coupling of { X t : t ≥ 0 }   and { ξ t N : t ≥ 0 }   such that
P N , ξ N ( X t ≥ | ξ t N | , ∀ t ≥ 0 ) = 1 , (6)
where P N , ξ N   is the coupling measure with the initial state ( N , ξ N )   . By ( 6 ), σ N   is stochastically dominated by τ   , i . e   ., for any t ≥ 0   ,
P ( σ N > t ) ≤ P N ( τ ≥ t ) . (7)
By the Chebyshev inequality and ( 3 ), for any c N > 0   ,
P ( σ N > c N E N τ ) ≤ P N ( τ ≥ c N E N τ ) ≤ E N τ 2 ( c N E N τ ) 2 ≤ 2 c N 2 . (8)
For any sequence C N → ∞   as N → ∞   , choose c N = C N ( 1 − M ) / 2   . Then an upper estimate of σ N   may be taken as c N E N τ   , and the claims in Theorem  2.2 hold by ( 8 ) and Lemma 2.1. □   By the same argument it is not difficult to establish following estimates, though a renormalization argument is used in the proof of the second part of Theorem  2.4 .
We will skip the proof, since they are not needed in proving Theorems  1.2 and  1.3 .
Theorem 2.3 Suppose the initial state is { 1 , 2 , ⋯ , N }   .
(1) If M = 1   , then E σ N ≤ N log N   ; and lim N → ∞ P ( σ N ≤ C N N l o g N ) = 1 ;   (2) If M > 1   , then E σ N ≤ M N + 1 / ( M − 1 ) 2   ; and there is a constant γ 1 > 0   such that lim N → ∞ P ( σ N ≤ e γ 1 N ) = 1 .  
Theorem 2.4 Suppose the initial state is { 1 , 2 , ⋯ , N }   .
(1) For any ɛ > 0   , lim N → ∞ P ( σ N > ( 1 − ɛ ) log N ) = 1   ; (2) If max n min { 1 2 ∑ l = n 2 n β ( l , 3 n − l ) , ∑ l = n 2 n β ( l , ∞ ) }   is larger than the critical value of the contact process on Z   , then there is a constant γ > 0   such that lim N → ∞ P ( σ N ≥ e γ N ) = 1 .  

3 A Lower Estimate of σ N  

We first extend the notation introduced before Theorem  1.3 . For any non-empty set A = { x 1 , x 2 ⋯ , x k }   , x 1 < x 2 < ⋯ < x k   , define ν ψ , λ ( A ) = { λ k − 1 ψ ( x 2 − x 1 ) ψ ( x 3 − x 2 ) ⋯ ψ ( x k − x k − 1 ) i f k > 1 ; 1 i f k = 1 .   Let S N = { 0 , 1 } { 1 , ⋯ , N }   , K N ( λ ) = ∑ A ∈ S N \ { ∅ } ν ψ , λ ( A )   , and π ( A ) = ν ψ , λ ( A ) / K N ( λ )   .
Then π   is a probability measure on S N   .
Lemma 3.1 K N ( λ ) ≥ C N 2 e γ ( λ ) N   for λ ≥ 1   , where γ ( 1 ) = 0   and γ ( λ ) > 0   if λ > 1   .
Proof.
K N ( λ ) = ∑ ξ ∈ S N \ { ∅ } ν ψ , λ ( ξ ) ≥ ∑ x = 0 [ N / 3 ] ∑ y = [ 2 N / 3 ] N ∑ ξ ∈ S N ( x , y ) λ | ξ | − 1 ν ψ ( ξ ) , (9)
where S N ( x , y ) = { ξ ∈ S N : ξ ( x ) = ξ ( y ) = 1 , ξ ( z ) = 0 , ∀ 1 ≤ z < x , o r y < z ≤ N } .   In light of ( 2 ), by the Renewal Theorem, ν ψ ( S N ( x , y ) ) ≥ 1 / ( 2 ∑ n n ψ ( n ) )   whenever y − x   is large enough. If λ = 1   , then K N ≥ C N 2   when N   is large, and we are done.
If λ > 1   , we can choose constant δ > 0   such that ν ψ ( { ξ ∈ S N ( x , y ) ; | ξ | ≥ δ | y − x | } ) ≥ ν ψ ( S N ( x , y ) ) 2 .   This together with ( 9 ) implies the desired conclusion. In particular we may choose γ ( λ ) = ( δ / 3 ) log λ   . □   We now use an idea in proving Theorem 7.1.20 of Liggett (1985) to prove
lim N → ∞ P π ( σ N ≥ K N C N N ) = 1 . (10)
The first half of Theorem  1.3 readily follows from ( 10 ) and Lemma  3.1 . Notice that the hitting time of the nearest particle system starting from { 1 , 2 , ⋯ , N }   is stochastically larger than that starting from the initial distribution π   . Therefore the second part of Theorem  1.2 also follows, with a little change in γ   .
Proof of ( 10 ). The reversible nearest particle system { ξ t N : t ≥ 0 }   is a Markov process taking values in S N   with jump rate q ( A , B ) = { 1 i f x ∈ A , B = A \ { x } ; λ ψ ( l x ( A ) ) ψ ( r x ( A ) ) ψ ( l x ( A ) + r x ( A ) ) i f x / ∈ A , B = A ∪ { x } ; 0 o t h e r w i s e .   It is reversible with respect to π   in the sense that π ( A ) q ( A , B ) = π ( B ) q ( B , A )   for A , B ∈ S N \ { ∅ }   .
Let { ξ t N ~ : t ≥ 0 }   be a Markov process on S N   , which is a modification of { ξ t N : t ≥ 0 }   so that particles can be born from the empty set. More specifically, the transition rates of { ξ t N ~ : t ≥ 0 }   is defined as follows.
q ~ ( A , B ) = { q ( A , B ) i f A ≠ ∅ ; q i f A = ∅ a n d | B | = 1 ; 0 o t h e r w i s e ,   where q > 0   is a constant to be determined later. Let K N   stand for K N ( λ )   , ν ψ ( { ∅ } ) = q − 1 , and π ~ = ν ψ / ( K N + q − 1 ) .   Then { ξ t N ~ : t ≥ 0 }   is reversible with respect to π ~   in the sense that π ~ ( A ) q ( A , B ) = π ~ ( B ) q ( B , A )   for any A , B ∈ S N   . Let P ~   be the distribution of { ξ t N ~ : t ≥ 0 }   with initial distribution π ~   , and E ~   be the expectation with respect to P ~   . Notice that { ξ t N ~ : t ≥ 0 }   is stationary under P ~   .
For any t > 0   , 2 t π ~ ( { ∅ } ) = E ~ ∫ 0 2 t 1 { ξ s N ~ = ∅ } d s .   Introduce the stopping time τ = inf { t ≥ 0 : ξ t N ~ = ∅ } .   By the Strong Markovian Property, the right side above equals
E ~ E ~ ( ∫ 0 2 t 1 { ξ s N ~ = ∅ } d s | ℱ τ ) ≥ E ~ E ~ ( 1 { τ < t } ∫ 0 2 t 1 { ξ s N ~ = ∅ } d s | ℱ τ )
≥ E ~ E ~ ( 1 { τ < t } ∫ τ τ + t 1 { ξ s N ~ = ∅ } d s | ℱ τ ) = P ~ ( τ < t ) E ~ ( ∫ 0 t 1 { ξ s N ~ = ∅ } d s | ξ 0 N ~ = ∅ )
Denote by σ   the first time { ξ t N ~ : t ≥ 0 }   jumps. Then
E ~ ( ∫ 0 t 1 { ξ s N ~ = ∅ } d s | ξ 0 N ~ = ∅ ) ≥ E ~ ( σ 1 { σ ≤ t } | ξ 0 N ~ = ∅ ) = ∫ 0 t s q ~ ∅ e − q ~ ∅ s d s ,
where q ~ ∅ = ∑ ξ q ~ ( ∅ , ξ ) = N q   . Hence
P ~ ( τ < t ) ≤ 2 t π ~ ( { ∅ } ) ∫ 0 t s q ~ ∅ e − q ~ ∅ s d s = 2 t q − 1 K N + q − 1 ⋅ N q 1 − e − N q t − N q t e − N q t . (11)
On the other hand,
P ~ ( τ < t ) ≥ P ~ ( τ < t , ξ 0 N ~ ≠ ∅ ) = P ~ ( ξ 0 N ~ ≠ ∅ ) P ~ ( τ < t | ξ 0 N ~ ≠ ∅ )
= K N K N + q − 1 P ( σ N < t ) .
This together with  11  ( )   yields that P ( σ N < t ) ≤ 2 t N K N ( 1 − e − N q t − N q t e − N q t ) .   Let q → ∞   , then P ( σ N < t ) ≤ 2 t N K N .   This implies ( 10 ), by choosing t = K N / ( C N N )   . □  

4 The Critical Case

In this section we will prove the second half of Theorem  1.3 , i . e .   , when λ = 1   ,
lim N → ∞ P π ( σ N ≤ C N N 2 ) = 1 . (12)
Let { η t : t ≥ 0 }   be an infinite reversible nearest particle system on Z   with finite many particles to the right of the origin (The third case on page 2); and r t   the rightmost particle in { η t : t ≥ 0 }   , i.e. r t : = sup { x : η t ( x ) = 1 }   . The properties of r t   of the critical nearest particle system are studied in Schinazi (1992). For a recent survey, see Mountford (2003).
Lemma 4.1 (Schinazi (1992), Theorem 1) Let { η t : t ≥ 0 }   be the critical reversible nearest particle system on Z   . Suppose the initial configurations have a particle at the origin and no particle to the right of the origin, and follows the renewal measure R e n ( ψ )   with density ψ ( ⋅ )   . Then, as a → ∞   , r a 2 t / a   converges in distribution to a Brownian motion with diffusion constant D > 0   in the Skorohod space.
Proof of ( 12 ). Partition the configuration space S N   according to the position of the rightmost particle. Namely, let A x = { ξ ∈ S N : ξ ( x ) = 1 , and ξ ( y ) = 0 for any y > x }   be the set of configurations whose rightmost particle is at x   . Denote by P   the distribution of { ξ t N : t ≥ 0 }   with initial distribution π   , and by P N , x   the conditional distribution of the nearest particle system on { 1 , 2 , ⋯ , N }   whose initial configurations are in A x   . Then
P = ∑ x = 0 N P ( A x ) P N , x . (13)
Denote by P   the distribution of the nearest particle system on Z   with the initial distribution in Lemma  4.1 , and P x   the translation of P   by x   . Thanks to the attractive property, there is a coupling of P x   and P N , x   such that for all t > 0   and all i ∈ Z   ,
ξ t N ( i ) ≤ η t ( i ) . (14)
Then under this coupling, ξ t N ≡ ∅   once r t < 1   , hence σ N ≤ inf { t : r t < 1 }   .
Suppose that lim N → ∞ C N = ∞   . For any C > 0   and large N   ,
P N , x ( σ N ≤ C N N 2 ) ≥ P N , x ( σ N ≤ C ( x − 1 ) 2 )
≥ P x ( ∃ t ≤ C ( x − 1 ) 2 s . t . r t < 1 )
= P ( ∃ t ≤ C ( x − 1 ) 2 s . t . r t < − ( x − 1 ) )
= P ( ∃ t ≤ C s . t . r ( x − 1 ) 2 t / ( x − 1 ) < − 1 ) .
Here the first equality holds because P x   is the translation of P   by x   . This together with Lemma  4.1 implies that liminf N , x → + ∞ P N , x ( σ N ≤ C N N 2 ) ≥ P ( ∃ t ≤ C s . t . B t < − 1 ) , ∀ C > 0 ,   where { B t : t ≥ 0 }   is a Brownian motion with diffusion constant D   . Let C → + ∞   , the right side of the above equation converges to 1. Hence lim N , x → + ∞ P N , x ( σ N ≤ C N N 2 ) = 1 .   Consequently, for any ɛ > 0   , there exists N 0 > 0   such that for any N ≥ x ≥ N 0   P N , x ( σ N ≤ C N N 2 ) > 1 − ɛ .   This together with ( 13 ) implies that
P ( σ N ≤ C N N 2 ) = ∑ x = 1 N P ( A x ) P N , x ( σ N ≤ C N N 2 ) ≥ ( 1 − ɛ ) ∑ x = N 0 N P ( A x ) . (15)
On the other hand, ∑ x = 1 N 0 − 1 ν ψ ( A x ) ≤ ∑ x = 1 N 0 − 1 ∑ y = 1 x ν ψ ( S N ( y , x ) ) ≤ N 0 2 .   Therefore, as N → ∞   , ∑ x = N 0 N P ( A x ) ≥ 1 − N 0 2 / ( C N 2 ) → 1 .   This together with ( 15 ) implies that liminf N → ∞ P ( σ N ≤ C N N 2 ) ≥ 1 − ɛ .   Let ɛ → 0   and the result follows. □   References Durrett, R. and Liu, X. F. (1988). The contact process on a finite set. Ann. Probab. 16 1158–1173.
Durrett, R. and Schonmann, R. H. (1988). The contact process on a finite set II. Ann. Probab. 16 1570–1583.
Durrett, R., Schonmann, R. H. and Tanaka, N. I. (1989). The contact process on a finite set III: The critical case. Ann. Probab. 17 1303–1321.
Liggett, T. M. (1985). Interacting particle systems. New York, Springer-Verlag. Mountford, T.S. (1992). A critical value for the uniform nearest particle system, Ann. Probab. 20 2031–2042.
Mountford, T.S. (2003). Critical reversible attractive nearest particle systems, In Topics in Spatial Stochastic Processes, Lecture Notes in Mathematics 1802, Springer, Berlin. Schinazi, R. (1992). Brownian fluctuations of the edge for critical reversible nearest particle systems. Ann. Probab. 20 194–205.
Wang Z. K. (1980). Birth and Death Processes and Markov Chains (in Chinese). Beijing, Science Publishing House. LMAM, School of Mathematical Sciences, Peking University, Beijing 100871, China