Äîêóìåíò âçÿò èç êýøà ïîèñêîâîé ìàøèíû. Àäðåñ îðèãèíàëüíîãî äîêóìåíòà : http://www.philol.msu.ru/~lex/khmelev/local/jacks.ps Äàòà èçìåíåíèÿ: Thu Oct 17 00:00:00 2002 Äàòà èíäåêñèðîâàíèÿ: Sat Dec 22 06:33:15 2007 Êîäèðîâêà:

Infinite closed Jackson networks
Dmitri Khmelev \Lambda
Eugene Spodarev y
Abstract
In this paper we prove the results concerning the limiting behaviour (as time
parameter t ! 1) of closed Jackson networks with an infinite number of nodes and possibly
infinite number of customers. As this system appears to be not ergodic we describe the class of
stationary distributions and explore the character of non--stability in particular cases.
Keywords: particle systems, zero--range interaction process, Bose--Einstein speeds, Jackson
networks, Markov chains, excessive measures, potential, supermartingales, majorizing
1 Introduction
For the moment not so much is known about the long--time behaviour of closed Jackson
networks with an infinite number of nodes (ICJN) and customers inside. Although this
consideration would be a logical continuation of the finite case (ordinary closed Jackson
networks (later on CJN) with N nodes and m customers), which is always ergodic (see [1]),
it turns out that the notion of infinity is here essential, and ICJN is never ergodic. The
first attempt to investigate the behaviour of finite CJN as N ! 1, m ! 1, m
N
! c ? 0
was made in [2]. Papers [3, 4] consider the mean--field approximation for the stochastical
dynamics of CJN.
ICJN could be also viewed as a transport network system: Poisson streams of customers
with intensities fl i enter the nodes i 2 J (J is a countable set of nodes) where the vehicles
carrying them to certain destinations (other nodes) are stationed,
P
i2J
fl i = fl Ÿ 1: If there
is a car in a node i, it carries a passenger to node j with probability p ij . Then the customer
leaves the system. Case fl ! 1 was considered in [5].
Our approach here is to consider ICJN as an interaction particle process (see, e.g., [6]),
namely, as a zero--range process introduced by Spitzer [7]. The case of homogeneous zero--
range interaction at Bose -- Einstein speeds was investigated by E. Waymire [8], E. D. Andjel
[9], A. Galves and H. Guiol [10]. Here we also allow the transition speeds to be dependent
on the location of a cell (non--homogeneity).
The paper is organized as follows: in section 2 the model of zero--range interaction is
introduced, necessary definitions are made and the existence theorem is proved. The results
of section 3 yield invariant measures and the character of transience. Section 4 is devoted
to the investigation of special case fl ! 1.
\Lambda Moscow State University, Russia. E­mail: dima@vvv.srcc.msu.su
y Friedrich­Schiller Universit¨at Jena, Deutschland. E­mail: seu@minet.uni­jena.de
1

2 Model: Existence and Monotonicity
Consider the following non--homogeneous zero--range interaction model at Bose -- Einstein
speeds: a number of indistinguishable particles is located in a countable set of sites J .
Transitions of particles at a site i 2 J are made after random periods of time Ü --- i. i.
exponentially d. r. v. with parameter fl i : if site i is not empty, then one (and only one)
particle chosen randomly at this site instantly moves to any site j with probability p ij .
Transitions are made independently for any i 2 J . Probabilities of jumps from i to j form
together single particle law matrix P = (p ij ) i;j2J ; 8 i 2 J
P
j2J
p ij = 1: One can describe the
state of the system by process j(t) = fj i (t)g i2J ; t – 0; where j i (t) is a number of particles
in cell i at time t.
Let Z+ = N [ f0g; Z+ = Z+[f1g: Then the state space of our system W =Z J
+ is a
compact metrizable space. Let B be a oe -- algebra generated by open sets in the product
topology. Let C(W) be the Banach space of all real--valued continuous functions on W with
the uniform norm.
Let 8 f 2 C(W) 8 i 2 J the ''measure of dependence on coordinate i'' be
\Delta f (i) = sup fj f(j) \Gamma f(i) j: j; i 2 W; j j = i j 8 i 6= jg :
Introduce D(W) =
(
f 2 C(W) : jjj f jjj def
=
P
i2J
\Delta f (i) ! 1
)
: D(W) is dense in C(W)
(see [6]): Define the following operator on D(W) :
A f(j) =
X
i2J
X
j2J
[Ifj i ? 0gfl i p ij (f(: : : j i \Gamma 1 : : : j j + 1 : : :) \Gamma f(j))] :
Theorem 2.1 (Existence) If
sup
i2J
fl i ! 1; sup
i2J
X
j2J
fl j p ji ! 1; (2.1)
then
1. There exists unique Feller process j(t)
:(\Omega ; =; P) ! (W;B) that describes our system;
(\Omega ; =; P) --- some probability space.
2. Operator A (closure of A) is an infinitesimal operator for process j: D(W) is a core
of A:
Proof:
The infinitesimal properties of any particle system are described by the collection of tran­
sition intensity measures c T (j; ¸) on Z T
+ : here j = (j i ) i2J ; T = fi 1 ; : : : i n g is any fi­
nite subset of J , and c T (j; ¸) is the intensity of transition from state j of the system to
j ¸ = (i j ; j 2 J : i j = j j 8j =
2 T; i i k
= ¸ k 8k = 1 : : : n) involving only T = fi 1 ; : : : i n g coor­
dinates. We have for
jT j ? 2; jT j = 1 : c T (j; ¸) = 0
jT j = 2; T = fi; jg : c T (j; ¸) =
8 ? !
? :
fl i p ij I fj i ? 0g ; if ¸ 1 = j i \Gamma 1; ¸ 2 = j j + 1
fl j p ji I fj j ? 0g ; if ¸ 1 = j i + 1; ¸ 2 = j j \Gamma 1
0; otherwise
: (2.2)
2

Construct A f(j) =
P
T
R
Z T
+
c T (j; di)
i
f(j i ) \Gamma f(j)
j
. Let
c T (i) = supfkc T (j 1 ; di) \Gamma c T (j 2 ; di)k T
j j 1 ; j 2 : j 1 (j) = j 2 (j) 8j 6= ig where k\Deltak T is a total
variation norm of a measure on Z T
+ : Let us define š(i; j) = P
T3i
c T (j); i 6= j; and š(i; i) = 0:
In order to apply existence theorem 3.9 [6] we need to verify the following conditions:
sup
i2J
X
T3i
sup
j2Z T
+
c T
i
j; Z T
+
j
! 1; (2.3)
sup
i2J
X
j2J
š(i; j) ! 1
Taking into account (2.2) one can rewrite these conditions as follows:
sup
i2J
X
j2J
(fl i p ij + fl j p ji ) ! 1: (2.4)
Since by our assumptions
P
j2J
p ij = 1 8i, condition (2.4) is obviously equivalent to (2.1).
Then A is a pregenerator of the semigroup of transition operators that uniquely define the
desired Markov process. The application of the general existence theory in [6] fulfils the
proof.
Corollary 2.1 If one of the following holds:
ffl sup
i2J
fl i ! 1; sup
i2J
P
j2J
p ji ! 1
ffl P
i2J
fl i ! 1,
then conditions (2.1) are satisfied.
Later on assume that (2.1) holds.
Introduce a partial ordering on W: we say that ¸ OE ¸ 0 for ¸, ¸ 0 2 W if ¸ i Ÿ ¸ 0
i for all
i 2 J (if ¸ 0
i = 1 the last inequality always holds).
Lemma 2.1 (Monotonicity) Consider two ICJN processes j(t) and j 0 (t) with the same
fl = ffl i g i2J and single particle law P such that j(0) = ¸ 2 W, j 0 (0) = ¸ 0 2 W, and
¸ OE ¸ 0 . Then there exists a process S(t) = (¸(t); ¸ 0 (t)) on the phase space W \Theta W such that
S(0) = (¸; ¸ 0 ) and ¸(t) OE ¸ 0 (t) a.s., and processes ¸(t) and ¸ 0 (t) are the stochastic copies of
j(t) and j 0 (t), respectively (in the sense of finite­dimensional distributions).
The proof of the lemma is standard and involves the construction of processes j(t) and
j 0 (t) on the same probability space (see [8], theorem 4.2 and [13], lemma 2).
We shall say (under the conditions of lemma 2.1) that j 0 (t) stochastically majorizes j(t):
j(t) OE j 0 (t).
Suppose the Markov chain with state space J and transition matrix P to be homoge­
neous, aperiodic, and irreducible. Introduce
3

Conjecture A: There exists a non--trivial invariant measure ú = (ú i ) i2J for P (not neces­
sarily finite).
Conjecture B: There exists unique non--trivial invariant probability measure ú = (ú i ) i2J
for P (later on called stationary).
Conjecture C: A countable Markov chain with transition matrix P is transient.
3 General case fl Ÿ 1
Denote
a def
= sup
i2J
ú i
fl i
! 1: (3.1)
Let ae max = 1=a: For any ae 2 [0; ae max ] and ae = 1 introduce product measures L ae (\Delta) on
(W;B) with marginal factors l i
ae (\Delta); i 2 J defined in the following two cases:
if ae 2 [0; ae max ] and ae(ú i =fl i ) ! 1, then
l i
ae (k) =
(
(1 \Gamma ae(ú i =fl i )) (ae(ú i =fl i )) k ; k 2 Z+ ;
0; k = 1
else we have ae = ae max , ae(ú i =fl i ) = 1 or ae = 1, and
l i
ae (k) =
(
0; k 2 Z+ ;
1; k = 1:
Introduce L = fL ae (\Delta) : ae 2 [0; ae max ]; ae = 1g. Denote by ~
L the closed convex hull of L:
~
L =
``
K--closed convex set, K'L
K:
Let M be the class of all invariant measures for Markov process fj(t)g t–0 :
The following four assertions could be proved by slight modification of the proofs of
propositions 2.14, 3.1, 2.15, 2.16 given in [8]; to see that one should take measure
n ú i
fl i
o
i2J
instead of ¯a = (¯a(x) : x 2 J) (using the notations of [8]) there.
Theorem 3.1 (Invariant measures) Suppose that conjecture A and (3.1) hold. Then the
closed convex hull ~
L of the set of measures fL ae (\Delta) : ae 2 [0; ae max ]; ae = 1g belongs to the class
M of all invariant measures for Markov process fj(t)g t–0 .
Proof:
The class of measures L belongs to M according to theorem 2.14 [8]. But M itself is a
compact closed subset of the set P of all probability measures on (W;B) (see [6],
proposition 1.8). Then ~
L ` M by definition of ~
L.
Let X
i2J
ú i
fl i
! 1: (3.2)
4

Proposition 3.1 Suppose that conjecture A and (3.2) hold. Then 8 ae 2 [0; ae max ]
L ae
/
j :
X
i2J
j i ! 1
!
= 1:
Theorem 3.2 (Clustering) Let conjecture A and 3.2 hold. Suppose j 0 2 J satisfies
ú j 0 =fl j 0 = max
i2J
ú i =fl i . Then 8 k 2 Z+ 8j 0 :
P
i2J
j 0
i = 1
lim
t!1
P
n
j j 0
(t) ? k j j(0) = j 0
o
= 1:
Corollary 3.1 (All invariant measures on
i
Z J
+ ; B``Z J
+
j
)
If conjecture A and (3.2) hold, then
(
L N
ae (\Delta) = L ae
/
\Delta j
X
i2J
j i = N
!
: N 2 N; ae 2 (0; ae max )
)
are all invariant measures on
i
Z J
+ ; B``Z J
+
j
:
Say G ij =
1
P
n=0
p (n)
ij 8i; j 2 J where p (n)
ij is the probability to reach state i from state j in
n steps.
Denote by j ¯
J (t) the restriction of j(t) to some subset ¯
J of the nodes of J . Let fJ n g 1
n=1
be the sequence of non--decreasing finite subsets of J : J 1 ae J 2 ae J 3 : : :,
S
n
J n = J , chosen so
that matrices P (n) = (p ij ) i;j2Jn are irreducible. For given ffl i g i2J , P and ¸ 2 Z J
+ let j(t) be
the ICJN--process starting from j(0) = ¸, and j (n) (t) be the one that starts from
j (n) (0) =
(
¸ j ; j 2 J n ;
1; j =
2 J n :
It follows from lemma 2.1 that j(t) OE j (n) (t). One can see that the restriction j (n)
Jn (t) is an
opened Jackson network on the set J n with input intensities \Delta (n) = (\Delta (n)
j ) j2Jn ,
\Delta (n)
j =
P
i2JnJn
fl i p ij . Let ae (n) = (ae (n)
j ) j2Jn be the unique solution of the stream conservation
equation (see [1]):
ae (n) = ae (n) P (n) + \Delta (n) :
Matrix I \Gamma P (n) is invertible as P (n) is an irreducible submatrix of P (n+1) with the spectral
radius not greater then 1. Due to that one can write
ae (n) = \Delta (n) (I \Gamma P (n) ) \Gamma1 = \Delta (n) (I + P (n) + (P (n) ) 2 + : : :):
Now we are ready to formulate the following proposition that would give us the tool to
obtain the conditions under which all particles in the system vanish as t !1.
Proposition 3.2 Suppose j(0) = ¸. If for any n 0 and k 2 J n 0 ae (n)
k ! 0 as n ! 1, then
for all ¸ 2 Z J
+ j(t) \Gamma! 0 weakly as t !1.
5

Proof:
As the convergence of any finite marginal distributions of j(t) is obviously equivalent to the
weak convergence of the distribution measures of j(t) we shall actually prove that for any
finite ¯
J ae J
lim
t!1
P (j ¯
J (t) = 0 j j(0) = ¸) = 1:
In what follows we shall use the next result given in [11]: let u n;j be the unique solution of
the finite system of equations
u n;j =
X
k2Jn
min[1; u n;k ]p ij + \Delta (n)
j :
Say J 0
n = fj 2 J n : u n;j ! 1g, J 1
n = fj 2 J n : u n;j – 1g. Then the distributions of
j (n)
Jn (t) 2 Z Jn
+ weakly converge to the invariant measure
ú un (z) =
Y
j2J 0
n
(1 \Gamma u n;j )u z j
n;j
Y
j2J 1
n
ffi 1 (z j );
where ffi 1 (\Delta) is a Dirac measure concentrated in 1. The inequality u n Ÿ ae (n) yields u n;k ! 0
for any k 2 J n 0
.
It follows from j(t) OE j (n) (t) that
P (j Jn 0
(t) = 0 j j(0) = ¸) – P (j (n)
Jn 0
(t) = 0 j j(0) = ¸):
Consequently,
lim inf
t!1
P (j Jn 0
(t) = 0 j j(0) = ¸) – lim
t!1
P (j (n)
Jn 0
(t) = 0 j j(0) = ¸):
The r.h.s. term tends to 1 as n ! 1. Therefore, P (j Jn 0
(t) = 0 j j(0) = ¸) ! 1 as t ! 1.
Then we note that for arbitrary finite subset ¯
J one can choose n 0 such that J n 0
oe ¯
J ; thus
the proposition is proven.
Theorem 3.3 (Devastation) Suppose that one of the following conditions holds:
1. fl ! 1 and conjecture C
2. fl ! 1 and 8j 2 J
P
i2J
p ij Ÿ 1
3. 8j 2 J
P
i2J
p ij Ÿ 1 and there exists a sequence of non--decreasing finite sets fJ n g 1
n=1 ,
J 1 ae J 2 ae : : :,
S
n
J n = J such that sup
j2JnJn
fl j \Gamma! 0 as n !1 and matrices
P (n) = (p ij ) i;j2Jn are irreducible
4. Let 8j 2 J
P
i2J
p ij Ÿ 1. Introduce the terminating Markov chain Y = fYmg 1
m=1 with
state space J and transition matrix P T = (p ji ) i;j2J . Denote by ¯
P j (J) the probability of
terminating for Y provided that Y 0 = j. Let ¯
P j (J) = 1 for all j 2 J and sup
j2J
fl j ! 1.
Then for any j(0) 2 Z J
+ the process j(t) ! 0 weakly as t !1.
6

Proof:
Let us verify that the conditions of proposition 3.2 hold in any of the cases 1) -- 4). Then
immediately applying the above proposition one can come to the desired conclusion.
1) Because of the transience of P the sum I +P +P 2 + : : : = G = (G ij ) i;j2J ! 1 is finite
(i. e. G ij ! 1 8i; j 2 J): Obviously,
G (n) = (I \Gamma P (n) ) \Gamma1 = I + P (n) + (P (n) ) 2 + : : : Ÿ G Jn = (G ij ) i;j2Jn :
It is a well--known fact (see [12], theorem 13 of Chapter 2) that G jk Ÿ G kk 8j; k 2 J .
The explicit form of ae (n)
k is
ae (n)
k = (\Delta (n) G (n) ) k =
X
i2JnJn
X
j2Jn
fl i p ij G (n)
j;k : (3.3)
It follows from the inequalities G (n)
j;k Ÿ G jk Ÿ G kk that
ae (n)
k Ÿ G kk
X
i2JnJn
X
j2Jn
fl i p ij ;
and as
P
j2Jn
p ij Ÿ 1, we get
ae (n)
k Ÿ G kk
X
i2JnJn
fl i : (3.4)
Due to the convergence of the series
P
i2J
fl i the right--hand side of (3.4) tends to zero as
n !1. Hence ae (n)
k ! 0 as n !1.
2) Let for any i 2 J n L n;j be the set of all sequences (j; j 1 ; : : : ; j l ) of arbitrary length l
such that j k 2 J n ; k ! l, while j l 2 J n J n . Then one can rewrite (3.3) in the following way:
ae (n)
j =
X
L n;j
(
l\Gamma2 Y
k=0
p T
j k j k+1
)p T
j l\Gamma1 j l
fl j l
;
where p T
ij are the elements of the transpose of P : p T
ij = p ji . Evidently,
ae (n)
j Ÿ ¯ fl Jn
X
L n;j
(
l\Gamma2 Y
k=0
p T
j k j k+1
)p T
j l\Gamma1 j l
= ¯ fl Jn x (n)
j ;
where ¯ fl Jn = sup
j2JnJn
fl j . One can interpret x (n)
j as the probability of the event that the
terminating Markov chain Y with state space J and transition matrix P T starting from j
ever enters the set J n J n . In view of that x (n)
j Ÿ 1. Hence, ae (n)
j Ÿ ¯ fl Jn . Then ¯
fl Jn ! 0 as
n !1 because of the convergence of
P
j2J
fl j , that yields ae (n)
k ! 0 as n !1.
3) The above reasoning holds also for this case, as the requirement ¯
fl Jn ! 0 is stated now
in the assumptions of 3).
4) One can adopt the proof in 2) for the case fl = 1. Namely, it is clear that
x (n)
j ! 1 \Gamma ¯
P j (J) as n ! 1. Then it is sufficient to require ¯
P j (J) = 1, sup
j2J
fl j ! 1 to get
ae (n)
j ! 0.
7

Definition 3.1 The i­th coordinate j i (\Delta) of the process j (the i­th cell of the system) is
stochastically bounded if lim
m!1
sup
t2R+
Pfj i (t) ? mg = 0:
Theorem 3.4 (Stochastical boundedness) If 9i 0 2 J : fl i 0
?
P
j2J
fl j p ji 0
and j i 0
(0) 2 Z+ ,
then j i 0
(t) is stochastically bounded, and
lim sup
t!1
Ej i 0
(t) Ÿ
P
j2J; j 6=i 0
fl j p ji 0
fl i 0
\Gamma P
j2J
fl j p ji 0
:
Proof:
Construct the process j 0 (t) such that
j 0 (0) =
(
j j (0); j = i 0 ;
1; j 6= i 0 :
Again, using lemma 2.1, we obtain j(t) OE j 0 (t). Note that j 0 (0) is an opened finite Jackson
network with only one node i 0 . The intensity of the input stream \Delta (1)
i 0
of this network is
equal to
P
j2J; j 6=i 0
fl j p ji 0
, the intensity of service equals fl i 0
. The probability to quit the system
is 1 \Gamma p i 0 i 0
. Then the stream conservation equation would be ae (1)
i 0
= \Delta (1)
i 0
+ ae (1)
i 0
p i 0 i 0
, and j 0
i 0
(\Delta)
is ergodic iff ae (1)
i 0
! fl i 0
, i. e., \Delta (1)
i 0
=(1 \Gamma p i 0 i 0
) ! fl i 0
, or
X
j2J; j 6=i 0
fl j p ji 0 ! fl i 0 (1 \Gamma p i 0 i 0 ):
The last inequality holds due to the assumptions of the theorem. Consequently, j 0
i 0
(\Delta) is er­
godic and stochastically bounded. Therefore, j i 0
(\Delta) is stochastically bounded. Let j 0
i 0
(1) =
lim
t!1
j 0
i 0
(t). Then j 0
i 0
(1) has a geometrical distribution P
n ¸
j i 0
(1) = n
o
= (1 \Gamma ff)ff n ; n 2 Z+
with parameter (see [1])
ff =
P
j2J; j 6=i 0
fl j p ji 0
(1 \Gamma p i 0 i 0
)fl i 0
:
It follows from j(t) OE j (n) (t) that Ej i 0 (t) Ÿ Ej 0
i 0
(t) for all t – 0 and
lim sup
t!1
Ej i 0 (t) Ÿ Ej 0
i 0
(1) = ff
1 \Gamma ff
:
Substituting ff, we obtain the last statement of the theorem.
4 Case fl ! 1
In this case one can prove that the transitions of particles occur a. s. only in discrete random
moments of time t n ; t n \Gamma t n\Gamma1 = Ü n ¸ i. i. exponentially d. r. v. with parameter fl =
P
i2J
fl i ;
n --- number of transition since t = 0: Then
P fn--th transition is made from cell i j j i (t n \Gamma 0) ? 0g = fl i
fl
def
= fi i ;
X
i2J
fi i = 1:
8

Introduce embedded Markov chain j(n) = fj i (t n )g i2J
8n2 N. Later on we shall write j i (n)
instead of j i (t n ). Suppose j i (0) = x i 8 i;
P
i2J
x i = 1: Let us introduce the non--decreasing
family of oe \Gammaalgebras fF n g n2N ,
F n = oe (j(m); m Ÿ n) = oe (j i (m); i 2 J; m Ÿ n) 8n :
Definition 4.1 Measure ¯(\Delta) on J (possibly oe­finite) is called (strictly) excessive for tran­
sition matrix P = (p ij ) i;j2J iff ¯ – ¯P : 8i ¯ i – P
j2J
¯ j p ji (¯ ? ¯P , respectively).
Definition 4.2 Function f on J is called harmonious (resp. excessive) for transition matrix
P = (p ij ) i;j2J iff Pf = f : 8i f i =
P
j2J
p ij f j (Pf Ÿ f).
Lemma 4.1 Let ¯(\Delta) and š(\Delta) be finite measures on the same measurable
space(\Omega ; L),
¯(\Omega\Gamma =
š(\Omega\Gamma = a ! 1. If 8A 2 L š(A) – ¯(A), then ¯(\Delta) = š(\Delta).
Proof:
Suppose the contrary holds: 9A 2 L : š(A) ? ¯(A): But by condition of the lemma
š( ¯
A) – ¯( ¯
A). Summing these inequalities up one can obtain a ? a. We arrived at a contra­
diction. Thus the statement of lemma is proved.
Lemma 4.2 If conjecture B holds and ffi i g i2J 6= fú i g i2J or if conjecture B does not hold,
then
9 i 0 ; j 0 : fl i 0
?
X
j2J
fl j p ji 0
; fl j 0
!
X
j2J
fl j p jj 0
Proof:
If fl ! 1, then measures fi(\Delta) : fi(i) = fi i ; ¯(\Delta) = (fiP ) (\Delta) : ¯ i =
P
j2J
fi j p ji are probability
measures on J . Suppose one of the following inequalities holds:
fi – ¯ (4.1)
fi Ÿ ¯ (4.2)
Then lemma 4.1 yields fi = ¯; fi = fiP . If conjecture B is true, it means fi = ú, otherwise
it implies that fi is a stationary distribution for P . Both cases are prohibited by the condi­
tions of lemma 4.2. Then none of the inequalities (4.1), (4.2) holds which fulfils the proof.
Remark 4.1 In case fl ! 1 under general assumptions on ffl i g i2J (see lemma 4.2) there
exists i 0 such that the conditions of theorem 3.4 are satisfied. So at least one node of the
system is always stochastically bounded. On the other hand, lemma 4.2 shows that this
situation might not hold for all i 2 J .
Remark 4.2 Lemma 4.2 states that if fl ! 1 then excessive probability measures fi do not
exist for P . But if fl = 1, conjecture C holds, then there exist infinitely many oe \Gammafinite
strictly excessive measures ¯ :
P
i2J
¯ i = 1; ¯ ? ¯P: Then in case fl = 1 for ffl i g i2J :
fl i ?
P
j2J
fl j p ji 8i 2 J all coordinates j i (t) are stochastically bounded.
9

Proof:
If conjecture C holds, then for some i G ii ! 1. The assumptions concerning the proper­
ties of a Markov chain with the transition matrix P guarantee the last inequality to hold
8i 2 J . Then for any fš i g i2J : š i – 0 8i 2 J construct the measure ¯ = f¯ i g i2J in the
following way: ¯ i =
P
j2J
š j G ji : One can choose fš i g i2J such that 8i ¯ i ! 1 (for example,
š j = ffi jj 0
) ¯ i = G j 0 i ! 1 8i), f¯ i g i2J is strictly excessive. The application of theorem
3.4 fulfils the proof.
For some fa i g i2J ; a i – 0;
P
i2J
a i ! 1 and for all x 2 W define f(x) =
P
i2J
a i x i Ÿ 1.
Theorem 4.1 (Existence of supermartingales) If conjecture C holds and there exist
numbers f' i g i2J : ' i – 0;
P
i2J
P
j2J
G ij ' j ! 1, then for a i = (G') i =
P
j2J
G ij ' j and ini­
tial distributions of Markov chain j such that
P
i2J
a i j i (0) ! 1 a. s. and E
P
i2J
a i j i (0) ! 1
sequence (f(j(n)); F n ) 1
n=1 is a supermartingale.
Proof:
First let us prove that f (j(n)) defined above is finite 8n 2 N provided that the conditions
of theorem 4.1 hold: f (j(0)) is clearly finite; then on each step n at most two coordinates
are changed. It means that if j(0) = x, then j j i (n) \Gamma x i jŸ n a. s. for all i. Therefore
f (j(n)) is also finite 8n. (f(j(n)); F n ) 1
n=1 is a supermartingale iff by definition
E (f (j(n + 1)) j F n ) \Gamma f (j(n)) Ÿ 0 a. s.
This inequality could be rewrited as
X
i: j i (n)?0
fl i
0
@ X
j2J
p ij a j \Gamma a i
1
A Ÿ 0 (4.3)
So if
8i a i – 0;
X
j2J
p ij a j Ÿ a i ; (4.4)
X
i2J
a i ! 1 (4.5)
(function a i is summable and excessive for P ), then inequality (4.3) holds and our theorem
is proved. By the well­known criterion of ergodicity of countable Markov chains if P is
transient, then there exist finite excessive functions for P that are not constant. Then by
Riesz theorem (see [14], p.22) and condition (4.5) this function a i must have the following
representation:
a i = (G') i =
X
j2J
G ij ' j ! 1 (4.6)
for some f' i g i2J : ' i – 0 8i: And vice versa, all fa i g i2J introduced in (4.6) are excessive.
This representation is correct as 8i; j G ij ! 1. For fa i g i2J to be summable we require the
following condition: X
i2J
X
j2J
G ij ' j ! 1:
10

Then the function a i introduced in the statement of theorem 4.1 satisfies (4.4) and (4.5),
thus f(j(n)) appears to be a supermartingale.
Proposition 4.1 If 9 j 0 :
P
i2J
G ij 0
! 1, then there exist numbers f' i g i2J : ' i – 0 such
that the conditions of theorem 4.1 hold.
Proof:
It is sufficient to choose ' j = ffi jj 0
. If the statement of proposition 4.1 holds, then
P
i2J
P
j2J
G ij ' j ! 1, and thus the conditions of theorem 4.1 are satisfied.
Proposition 4.2 There exist matrices P for which the conditions of proposition 4.1 are
satisfied.
Proof:
Consider J = N,
P =
0
B B B B B @
q p 0 0 0 0 0 0 : : :
q 0 p 0 0 0 0 0 : : :
0 q 0 p 0 0 0 0 : : :
0 0 q 0 p 0 0 0 : : :
: : : : : : : : : : : : : : : : : : : : : : : : : : :
1
C C C C C A
;
p + q = 1
p; q ? 0
p ? q
:
This matrix P as a transition operator of a Markov chain describes the behaviour of the
integer--valued random walk with impenetrable barrier at origin:
W k = max(0; W k\Gamma1 +B k ); k – 1; W 0 = i; B k =
(
1; with probability p;
\Gamma1; with probability q:
This random walk is an irreducible aperiodic homogeneous Markov chain. According to the
well--known results for random walks it is also transient (as p ? q; see [15], p.28). Therefore
for i; j 2 J G ij ! 1. Suppose j 0 = 1 and prove that
1
P
i=1
G i;j 0 ! 1: G i;1 = E (A j W (0) = i)
where A = ] fk : W (k) = 1g denotes the number of k such that W (k) = 1: Introduce the
following sequence of moments
n
Ü (i)
k
o 1
k=1
:
Ü (i)
1 = inf fn – 1 : W (n) = 1g ; Ü (i)
k = inf
n
n ? Ü (i)
k\Gamma1 : W (n) = 1
o
; k ? 1; in which our
chain W returns to state 1 provided that W (0) = i: These moments Ü (i)
k form the sequence
of regeneration times for W (which could be also viewed as a regeneration process). Then
` 1 = Ü (i)
1 ; ` k = Ü (i)
k \Gamma Ü (i)
k\Gamma1 ; k ? 1 are independent and f` k g k–2 are also identically distributed
as the duration of regeneration cycles (see [16], p.90). If p ? q, then ` 1 ; ` 2 ; ` 3 ; : : : consist
together the terminating renewal process. Let
b 1 = P f` 1 = 1g ? 0; b = P f` k = 1g ? 0; k ? 1:
Then the number of the last renewal has a distribution P fA = kg = (1\Gammab 1 )b(1\Gammab) k\Gamma1 ; k – 1;
P fA = 0g = b 1 : b 1 depends on W (0) = i; but b does not. Calculate E (A j W (0) = i) :
11

E (A j W (0) = i) = b(1 \Gamma b 1 )
P
k–1
k(1 \Gamma b) k\Gamma1 = (1 \Gamma b 1 )
/ P
k–0
kb(1 \Gamma b) k\Gamma1 + b
P
k–0
(1 \Gamma b) k
!
=
(1 \Gamma b 1 )
i 1\Gammab
b + b
1\Gamma(1\Gammab)
j
= 1\Gammab 1
b :
Then
G i;1 =
P
n
Ü (i)
1 ! 1
o
b
:
Let us prove that P
n
Ü (i)
1 ! 1
o
=
i q
p
j i\Gamma1
8i – 1: In order to do that we shall use the method
of generating functions developed in [17], p.84, lemma 1. Denote
Ü (i)
1 (n) =
(
inf fk – 1 : W (k) = 1g ; if W k ! n 8k ! Ü (i)
1
1; otherwise :
(as before W (0) = i). Let C n =
n
Ü (i)
1 (n) ! 1
o
; C n ` C n+1 8n; 1 S
n=1
C n =
n
Ü (i)
1 ! 1
o
;
hence P fC n g \Gamma!
n!1
P
n
Ü (i)
1 ! 1
o
: Let us calculate P fC n g 8n: Introduce the generating
function of Ü (i)
1 (n) :
F n
i (z) = E
`
z Ü (i)
1 (n) j Ü (i)
1 (n) ! 1
'
= 1
P
k=1
z k P
n
Ü (i)
1 (n) = k
o
: Then the following recurrent
formulae could be deduced by means of the total probability formula:
F n
i (z) =
8 ? !
? :
pzF n
i+1 (z) + qzF n
i\Gamma1 (z); 1 ! i ! n
1; i = 1
0; i = n
: (4.7)
Solving this equation one can see that F n
i (z) = A(z)
`
1\Gamma
p
1\Gamma4pqz 2
2pz
' i
+ B(z)
`
1+
p
1\Gamma4pqz 2
2pz
' i
;
where A(z) and B(z) could be found from boundary conditions (4.7). And as
P fC n g = F n
i (1) one can calculate that P fC n g = ( q
p ) n
\Gamma ( q
p ) i
( q
p
) n
\Gamma q
p
\Gamma!
n!1
i q
p
j i\Gamma1
: Then
1
P
i=1
G i;1 = 1
b
1
P
i=1
i q
p
j i\Gamma1
= p
b(p\Gammaq) ! 1; so the conditions of proposition (4.1) are satisfied.
5 Acknowledgements
The authors would like to thank Prof. L. Afanas'eva (Moscow State University), Prof. V.
Oseledets (Moscow State University) and Prof. H.­J. Engelbert (Friedrich--Schiller University
of Jena) for helpful comments and discussions.
References
[1] J. Walrand ''An introduction to queueing networks'' Prentice Hall, 1988
[2] G. Fayolle, G. ­ M. Lasgouttes ''Asymptotics and scalings for large product­form net­
works via the Central Limit Theorem'' Preprint, 1996
[3] D. V. Khmelev, V. I. Oseledets ''Mean­field approximation for stochastic transportation
network and stability of dynamical system'' Preprint N 445 of the University of Bremen,
Bremen, June 1999
12

[4] V. Scherbakov ''Time scales hierarchy in large closed Jackson networks'' Preprint N 4,
French­Russian A.M. Liapunov Institute of Moscow State University, Moscow, 1997
[5] E. Spodarev ''Transport networks with an infinite number of nodes'' to appear in the
conference issue of Zeitschrift f¨ur angewandte Mathematik und Mechanik, 1999
[6] T. M. Liggett ''Interacting particle systems'' Springer, 1985
[7] F. Spitzer ''Interaction of Markov processes'' Advances in Math. 5, 246­290 (1970)
[8] E. Waymire ''Zero -- range interaction at Bose -- Einstein speeds under a positive recur­
rent single particle law'' Ann. Prob. 8, 3, 441­450 (1980)
[9] E. D. Andjel ''Invariant measures for the zero -- range process'' Ann. Prob. 10, 525­547
(1982)
[10] A. Galves, H. Guiol ''Relaxation time of the one--dimensional symmetric zero--range
process with constant rate'' Markov Processes Relat. Fields 3, 323­332 (1997)
[11] J. B. Goodman, W. A. Massey ''The non--ergodic Jackson networks'' J. Appl. Prob. 21,
N 4, 860­869 (1984)
[12] I. I. Gikhman, A. V. Skorokhod ''Theory of stochastical processes'', v. 1. Moscow, Nauka,
1971 (in russian)
[13] M. Ya. Kelbert, M. L. Kontsevich, A. N. Rybko ''Jackson networks on countable graphs''
Teoriya veroyatnostei i ee prilozheniya XXXIII, 2, 379­382, (1988) (in russian)
[14] E. B. Dynkin, A. A. Yushkevich ''Theorems and problems in the theory of Markov
chains'' Moscow, Nauka, 1967 (in russian)
[15] G. Fayolle, V. A. Malyshev, M. V. Menshikov ''Topics in the constructive theory of
countable Markov chains'' Cambridge University Press, 1995
[16] L. Afanas'eva, E. Bulinskaya ''Stochastic processes in queueing and inventory theory''
Moscow, Izd. MGU, 1980 (in russian)
[17] E. Bulinskaya ''On high -- level crossing for a class of discrete -- time stochastic processes''
Fundamentalnaya i prikladnaya matematika 1, 81­107 (1995)
13