Approximation for extinction probability of the contact process based on
  the Gr\"obner basis
Approximation for extinction probability of
the contact process based on the Gröbner basis
Norio Konno
Department of Applied Mathematics
Yokohama National University
Abstract. In this note we give a new method for getting a series of approxi-
mations for the extinction probability of the one-dimensional contact process by
using the Gröbner basis.
1 Introduction
Let X = {0, 1}Zd denote a configuration space, where Zd is the d-dimensional
integer lattices. The contact process {ηt : t ≥ 0} is an X-valued continuous-
time Markov process. The model was introduced by Harris in 1974 [1] and
is considered as a simple model for the spread of a disease with the infection
rate λ. In this setting, an individual at x ∈ Zd for a configuration η ∈ X is
infected if η(x) = 1 and healthy if η(x) = 0. The formal generator is given
Ωf(η) =
c(x, η)[f(ηx)− f(η)],
where ηx ∈ X is defined by ηx(y) = η(y) (y 6= x), and ηx(x) = 1−η(x). Here
for each x ∈ Zd and η ∈ X, the transition rate is
c(x, η) = (1− η(x))× λ
y:|y−x|=1
η(y) + η(x),
http://arxiv.org/abs/0704.0019v2
with |x| = |x1|+ · · ·+ |xd|. In particular, the one-dimensional contact process
001 → 011 at rate λ,
100 → 110 at rate λ,
101 → 111 at rate 2λ,
1 → 0 at rate 1.
Let Y = {A ⊂ Zd : |A| < ∞}, where |A| is the number of elements in A.
Let ξAt (⊂ Zd) denote the state at time t of the contact process with ξA0 = A.
There is a one-to-one correspondence between ξAt (⊂ Zd) and ηt ∈ X such
that x ∈ ξAt if and only if ηt(x) = 1. For any A ∈ Y , we define the extinction
probability of A by limt→∞ P (ξ
t = ∅). Define νλ(A) = νλ{η : η(x) = 0
for any x ∈ A}, where νλ is an invariant measure of the process starting
from a configuration: η(x) = 1 (x ∈ Zd) and is called the upper invariant
measure. In other words, let δ1S(t) denote the probability measure at time t
for initial probability measure δi which is the pointmass η ≡ i(i = 0, 1). Then
νλ = limt→∞ δ1S(t). Then self-duality of the process implies that νλ(A) =
limt→∞ P (ξ
t = ∅). The correlation identities for νλ(A) can be obtained as
follows:
Theorem 1.1 For any A ∈ Y ,
y:|y−x|=1
νλ(A ∪ {y})− νλ(A)
νλ(A \ {x})− νλ(A)
From now on we consider the one-dimensional case. We introduce the fol-
lowing notation:
νλ(◦) = νλ({0}), νλ(◦◦) = νλ({0, 1}), νλ(◦ × ◦) = νλ({0, 2}), . . . .
By Theorem 1.1, we obtain
Corollary 1.2
2λνλ(◦◦)− (2λ+ 1)νλ(◦) + 1 = 0,(1)
λνλ(◦ ◦ ◦)− (λ+ 1)νλ(◦◦) + νλ(◦) = 0,(2)
2λνλ(◦ ◦ ◦◦) + νλ(◦ × ◦)− (2λ+ 3)νλ(◦ ◦ ◦) + 2νλ(◦◦) = 0,(3)
λνλ(◦ ◦ ×◦)− (2λ+ 1)νλ(◦ × ◦) + λνλ(◦ ◦ ◦) + νλ(◦) = 0.(4)
The detailed discussion concerning results in this section can be seen in
Konno [2, 3]. If we regard λ, νλ(◦), νλ(◦◦), νλ(◦ ◦ ◦), . . . as variables, then
the left hand sides of the correlation identities by Theorem 1.1 are polyno-
mials of degree at most two. In the next section, we give a new procedure
for getting a series of approximations for extinction probabilities based on
the Gröbner basis by using Corollary 1.2. As for the Gröbner basis, see [4],
for example.
2 Our results
Put x = νλ(◦), y = νλ(◦◦), z = νλ(◦ ◦ ◦), w = νλ(◦ × ◦), s = νλ(◦ ◦
◦◦), u = νλ(◦ ◦ ×◦). Let ≺ denote the lexicographic order with λ ≺ x ≺
y ≺ w ≺ z ≺ u ≺ s. For m = 1, 2, 3, let Im be the ideals of a polynomial
ring R[x1, x2, . . . , xn(m)] over R as defined below. Here x1 = λ, x2 = x, x3 =
y, x4 = z, x5 = w, x6 = s, x7 = u and n(1) = 3, n(2) = 4, n(3) = 7.
2.1 First approximation
We consider the following ideal based on Corollary 1.2 (1):
I1 = 〈 2λy − 2λx− x+ 1, y − x2 〉 ⊂ R[λ, x, y].(5)
Here y−x2 corresponds to the first (or mean-field) approximation: ν(1)
(◦◦) =
λ (◦))2. Then
G1 = {(x− 1)(2λx− 1), y − x2}(6)
is the reduced Gröbner basis for I1 with respect to ≺. Therefore the solution
except a trivial one x(= y) = 1 is x = ν
(◦) = 1/(2λ). Remark that the
trivial solution means that the invariant measure is δ0. From this, we obtain
the first approximation of the density of the particle, ρλ = Eνλ(η(x)), as
follows:
= 1− ν(1)
(◦) = 2λ− 1
for any λ ≥ 1/2. This result gives the first lower bound λ(1)c of the critical
value λc of the one-dimensional contact process, that is, λ
c = 1/2 ≤ λc.
However it should be noted that the inequality is not proved in our approach.
The estimated value of λc is about 1.649.
2.2 Second approximation
Consider the following ideal based on Corollary 1.2 (1) and (2):
I2 = 〈 2λy − 2λx− x+ 1, λz − λy − y + x, xz − y2 〉 ⊂ R[λ, x, y, z].
Here xz−y2 corresponds to the second (or pair) approximation: ν(2)
(◦)ν(2)
◦) = (ν(2)λ (◦◦))2. Then
G2 = {(x− 1)((2λ− 1)x− 1), 1 + 2λ(y − x)− x,
−y − yx+ 2x2,−z − y(2 + y) + 4x2}
is the reduced Gröbner basis for I2 with respect to ≺. Therefore the solution
except a trivial one x(= y = z) = 1 is x = ν
(◦) = 1/(2λ − 1). As in a
similar way of the first approxaimation, we get the second approximation of
the density of the particle:
2(λ− 1)
2λ− 1 ,
for any λ ≥ 1. This result implies the second lower bound λ(2)c = 1. We
should remark that if we take
I ′2 = 〈 2λy − 2λx− x+ 1, λz − λy − y + x, y − x2, z − x3 〉 ⊂ R[λ, x, y, z],
then we have
G′2 = {z − 1, y − 1, x− 1}
is the reduced Gröbner basis for I ′2 with respect to ≺. Here y−x2 and z−x3
correspond to an approximation: ν
(◦◦) = (ν(2
(◦))2 and ν(2
(◦ ◦ ◦) =
(◦))3, respectively. Then we have only trivial solution: x = y = z = 1.
2.3 Third approximation
Consider the following ideal based on Corollary 1.2 (1)–(4):
I3 = 〈 2λy − 2λx− x+ 1, λz − λy − y + x,
2λs+ w − (2λ+ 3)z + 2y, λu− (2λ+ 1)w + λz + x,
ys− z2, xu− yw 〉 ⊂ R[λ, x, y, z, w, s, u].
Here ys−z2 and xu−yw correspond to the third approximation: ν(3)
(◦◦)ν(3)
◦◦) = (ν(3)
(◦ ◦ ◦))2 and ν(3)
(◦)ν(3)
(◦ ◦×◦) = ν(3)
(◦◦)ν(3)
(◦× ◦), respectively.
G3 = {(x− 1)((12λ3 − 5λ− 1)x2 − 2λ(2λ+ 3)x− λ+ 1), . . .}
is the reduced Gröbner basis for I3 with respect to ≺. Therefore the solution
except a trivial one x = 1 is x = ν
λ (◦) = (λ(2λ+3)+
D)/(12λ3−5λ−1),
where D = 16λ4 + 4λ2 + 4λ+ 1. Then we obtain the third approximation of
the density of the particle:
4λ(3λ2 − λ− 3)
12λ3 − 2λ2 − 8λ− 1 +
for any λ ≥ (1 +
37)/6. This result corresponds to the third lower bound
c = (1 +
37)/6 ≈ 1.180.
3 Summary
We obtain the first, second, and third approximations for the extinction
probability, the density of the particle, and the lower bound of the one-
dimensional contact process by using the Gröbner basis with respect to a
suitable term order. These results coincide with results given by the Harris
lemma (more precisely, the Katori-Konno method, see [3]) or the BFKL
inequality [5] (see also [3]). As we saw, the generators of Im in Section 2
have degree at most two in x1, x2, . . ., such as 2λy − 2λx− x+ 1, ys− z2 in
the case of I3. We expect that this property will lead to get the higher order
approximations of the process (and other interacting particle systems having
a similar property) effectively.
Acknowledgment. The author thanks Takeshi Kajiwara for valuable dis-
cussions and comments.
References
[1] T. E. Harris, Contact interactions on a lattice, Ann. Probab. 2: 969–988
(1974).
[2] N. Konno, Phase Transitions on Interacting Particle Systems, World
Scientific, Singapore (1994).
[3] N. Konno, Lecture Notes on Interacting Particle Systems,
Rokko Lectures in Mathematics, Kobe University, No.3 (1997),
http://www.math.kobe-u.ac.jp/publications/rlm03.pdf.
[4] D. A. Cox, J. B. Little, and D. O’Shea, Ideals, Varieties, And Al-
gorithms: An Introduction to Computational Algebraic Geometry And
Commutative Algebra, 3rd edition, Undergraduate Texts in Mathemat-
ics, Springer Verlag (2007).
[5] V. Belitsky, P. A. Ferrari, N. Konno, and T. M. Liggett, A strong corre-
lation inequality for contact processes and oriented percolation, Stochas-
tic. Process. Appl. 67: 213–225 (1997).
http://www.math.kobe-u.ac.jp/publications/rlm03.pdf
	Introduction
	Our results
	First approximation
	Second approximation
	Third approximation
	Summary
