Stability of Markovian Processes III: Foster-Lyapunov Criteria for Continuous-Time Processes
Author(s): Sean P. Meyn and R. L. Tweedie
Source: Advances in Applied Probability, Vol. 25, No. 3 (Sep., 1993), pp. 518-548
Published by: Applied Probability Trust
Stable URL: http://www.jstor.org/stable/1427522
Accessed: 19/09/2010 01:59
Your use of the JSTOR archive indicates your acceptance of JSTOR's Terms and Conditions of Use, available at
http://www.jstor.org/page/info/about/policies/terms.jsp. JSTOR's Terms and Conditions of Use provides, in part, that unless
you have obtained prior permission, you may not download an entire issue of a journal or multiple copies of articles, and you
may use content in the JSTOR archive only for your personal, non-commercial use.
Please contact the publisher regarding any further use of this work. Publisher contact information may be obtained at
http://www.jstor.org/action/showPublisher?publisherCode=apt.
Each copy of any part of a JSTOR transmission must contain the same copyright notice that appears on the screen or printed
page of such transmission.
JSTOR is a not-for-profit service that helps scholars, researchers, and students discover, use, and build upon a wide range of
content in a trusted digital archive. We use information technology and tools to increase productivity and facilitate new forms
of scholarship. For more information about JSTOR, please contact support@jstor.org.
Applied Probability Trust is collaborating with JSTOR to digitize, preserve and extend access to Advances in
Applied Probability.
http://www.jstor.org
Adv. Appl. Prob. 25, 518-548 (1993)
Printed in N. Ireland
( Applied Probability Trust 1993
STABILITY OF MARKOVIAN PROCESSES III: FOSTER-
LYAPUNOV CRITERIA FOR CONTINUOUS-TIME
PROCESSES
SEAN P. MEYN,* University of Illinois
R. L. TWEEDIE,** Colorado State University
Abstract
In Part I we developed stability concepts for discrete chains, together with
Foster-Lyapunov criteria for them to hold. Part II was devoted to developing related
stability concepts for continuous-time processes. In this paper we develop criteria for
these forms of stability for continuous-parameter Markovian processes on general
state spaces, based on Foster-Lyapunov inequalities for the extended generator.
Such test function criteria are found for non-explosivity, non-evanescence, Harris
recurrence, and positive Harris recurrence. These results are proved by systematic
application of Dynkin's formula.
We also strengthen known ergodic theorems, and especially exponential ergodic
results, for continuous-time processes. In particular we are able to show that the test
function approach provides a criterion for f-norm convergence, and bounding
constants for such convergence in the exponential ergodic case.
We apply the criteria to several specific processes, including linear stochastic
systems under non-linear feedback, work-modulated queues, general release storage
processes and risk processes.
FOSTER'S CRITERION;
FUNCTIONS;
MODELS; RISK MODELS; OUEUES; HYPOELLIPTIC DIFFUSION
STOCHASTIC LYAPUNOV
STORAGE
IRREDUCIBLE MARKOV PROCESSES;
EXPONENTIAL
ERGODICITY;
ERGODICITY;
RECURRENCE;
AMS 1991 SUBJECT CLASSIFICATION: PRIMARY 60J10
1. Introduction
1.1. Criteria for stability and recurrence. Our objectives in this paper are to
obtain a unified approach to the stability classification of continuous-time Markov
processes via Foster-Lyapunov inequalites applied to the generators of the process.
In Part II of this series of papers [25], we developed various such forms of
'stability' for Markov processes. These are analogous to and based on stability
concepts in discrete time, developed in Part I [24]. In [24] we also developed
(extending [35], [27], [20]) drift or Foster-Lyapunov conditions on the transition
Urbana, IL 61801, USA.
Received 28 August 1991; revision received 13 August 1992.
* Postal address: University of Illinois, Coordinated Science Laboratory, 1101 W. Springfield Ave.,
** Postal address: Department of Statistics, Colorado State University, Fort Collins, CO 80523, USA.
This work was commenced at Bond University, and developed there, at the Australian National
University, the University of Illinois, and Colorado State University.
Work supported in part by NSF initiation grant #ECS 8910088.
518
Stability of Markovian processes III
519
probability kernels governing the motion of the chain and these served to classify
the chain as non-evanescent, recurrent, positive recurrent and so on. Consideration
of the generator of the process is natural in continuous time, as the generator is
usually more accessible than the transition function.
In this paper we develop a similar approach for stability of general right processes
evolving on locally compact separable metric spaces, based upon the extended
generator for the process. We obtain criteria for non-explosivity, non-evanescence,
Harris recurrence, and positive Harris recurrence, as well as (and perhaps most
importantly, in practice) ergodicity and geometric ergodicity. The processes covered
by our approach include diffusions and jump-deterministic processes as special
cases.
Criteria for stability of continuous-time processes on countable spaces, based on
Foster-Lyapunov inequalities (drift conditions) for the infinitesimal generator, have
been developed in [34], [36], [6]. For diffusion processes there are precedents for
this work to be found in Kushner's work [19], which is primarily concerned with
criteria for various generalizations of stability in the sense of Lyapunov using drift
conditions associated with the infinitesimal generator, together with the application
of Dynkin's formula. Our work is more closely related to that of Khas'minskii [17]
who deals with stochastic generalizations of stability in the sense of Lyapunov in a
fashion similar to [19], and presents criteria for various forms of recurrence, based
again upon Dynkin's formula.
The paper is organized as follows. In the remainder of this section we describe the
basic assumptions, present a version of Dynkin's formula and describe a truncation
scheme which is required for its application. Section 2 presents a drift condition for
the process which is shown to imply 'non-explosion'; that is, that the escape time for
the process is infinite with probability 1. In Section 3 a stronger condition is used to
obtain non-evanescence of the sample paths of the process. Using results from [25],
this gives a criterion for Harris recurrence. In Section 4 we use a continuous-time
version of Foster's criterion to obtain sufficient conditions for the existence of an
invariant probability 7r, together with finiteness of 7r(f) for general functions f, and
positive Harris recurrence or generalizations of positive recurrence.
Sections 5 and 6 contain the most important results in the paper. We obtain
criteria for total variation norm convergence of the distributions of the process,
convergence of the expectation of unbounded functions of the process, and criteria
under which such convergence takes place at a geometric rate.
In the final part of the paper, we apply all of these results to jump-deterministic
processes, including work-modulated queues, general release storage processes and
risk processes, and diffusion processes, where we obtain new convergence results
for passive linear stochastic systems under static non-linear feedback.
1.2. The processes 4 and m". Here we provide a brief description of the context
which we treat, which is intended to make the paper relatively self-contained. We
520
SEAN P. MEYN AND R. L. TWEEDIE
do not discuss many of the concepts in detail, since the background to this paper
and the processes we consider is given in [24] and [25].
= {I,:
We suppose that
t R+} is a time-homogeneous Markov process with
state space (X, A(X)), and transition functions (P'). When (o = x the process 0
evolves on the probability space (Q,
, Px), where Q denotes the sample space. It is
assumed that the state space X is a locally compact and separable metric space, and
that 1(X)
is the Borel field on X.
The operator P' acts on bounded measurable functions f and a-finite measures s
on X via
PYf(x) =
dy)f(y),
fP'(x,
P'(A) = f p(dx)P'(x, A).
For a measurable set A we let
rA = inf
{t-0:!
, EA},
A
oA = f
dt.
tA}
The Markov process is called qg-irreducible if for the a-finite measure qg,
p{B} > 0Ex[rlB]>
0,
x eX
< oo) = 1 for any x eX. Whilst some of our
and Harris recurrent if 9 {B} > 0=
results hold only for irreducible (i.e. (9-irreducible for some 9p) processes, many
hold without this restriction. The most interesting of our stability results will
however be based on Harris recurrence or stronger forms of recurrence.
>Px(rB
Throughout this paper we let {O, :n E Z,} denote a fixed family of open
precompact sets for which O, X as n -- oo. By precompact we mean that the closure
of O, is a compact subset of X for each n. We let Tm
to:;, denote the first-entrance
time to Of, (set to oo if the process does not leave the set Om), and denote by ? the
exit time for the process, defined as
(1)
? A lim Tm
We assume without further comment that the process {Q,: 05t < ?} killed at time (
is a (Borel) right process [28].
In the sense of stability used in this paper, the first property of importance is
explosivity, or rather non-explosivity.
Non-explosivity. We call the process 4 non-explosive if Px { = c} = 1 for all
x E X.
The non-explosivity property is often called regularity (see [34] in the countable space
case, [16] in the piecewise linear context, and [17] for diffusions). Unfortunately,
regularity for sets in Markov chain theory can mean something quite different ([26],
[23]), so we have adopted this nomenclature, calling the time " the time of
explosion, essentially as in Kliemann [18].
Stability of Markovian processes III
521
If the process 0 is a non-explosive right process, then 0 is strongly Markovian
implies that the set
with right-continuous sample paths, and non-explosivity
{t,:0 _ t S
In order to develop drift criteria for non-explosivity or recurrence based on the
generator of the process introduced in the next section, we need to consider
truncations of the process 0.
T} is precompact with probability 1 for any TE R .
For mE
Z+,
let Am denote any fixed state in Oc, and define Om by
(2)
[M(N t< Tm
Tm"
>m
t
7= A
Theorem 12.23 of [28] implies that the resulting process is a non-explosive right
process. For the theory developed in this paper, we may in fact let
tm denote any
non-explosive right process with the property that Qm7 = F, whenever t < Tm. For
instance, we may take Q)7m =
ATm where s A t denotes the minimum of s and t. This
is the approach which is taken in [19]. For applications, however, the specification of
a 'graveyard state' Am as in (2) appears most suitable.
(4^
1.3. The extended generator and Dynkin's formula. Our central goal in this paper
is to provide conditions, couched in terms of the defining characteristics of the
process 0, for the various forms of stability developed in [25] to hold.
In general the characteristics used in practice to define the process are not
couched in terms of the semigroup P't, but rather of the extended generator of the
process. The following definition is a slightly restricted form of that in Davis [9].
the set of all functions V : Xx
The extended generator. We denote by D(,4)
R
R --> R for which there exists a measurable function U:X x U
each x EX, t > 0,
R such that for
--
(3)
(4)
Ex[V(D,, t)] = V(x, 0) + Exf U(D,, s) ds
Ex [I U(,, s)l] ds < oo.
We write 4sV U and call s the extended generator of the process 0.
The identity (3) states that the adapted process (My, 'F)
is a martingale, where
MV= V(Dt, t)- V(QD0, 0) -
U(s,, s)ds.
This definition is an extension of the infinitesimal generator (see [19]) for Hunt
processes: the more common definition of this is in terms of a differentiation
operation as in (5) below.
For general functions f, it is not easy to know if f is in the domain of
i. For
example, one way to proceed is to first construct the strong generator (see [17] in
522
SEAN P. MEYN AND R. L. TWEEDIE
the context of diffusions), whose domain typically contains bounded functions with
appropriate differentiability properties, and then note that the domain of the strong
generator is contained in the domain of the extended generator. To circumvent this
difficulty and allow the straightforward use of unbounded functions we use a
truncation approach which we now describe.
We write ASm for the extended generator of
'm. Under general conditions, 4,m is
an extension of 4S on the set Om in the sense that if V is in the domain of 4, then it
, s V = 4V. However, such conditions do not
is in the domain of 4,m, and on Om
concern us, as we do not require that Sm extend 4.
Typically, the domain of 4,,m will give us a rich choice of functions for test
functions. Three typical examples are:
A. If X is discrete, then the domain of the extended generator for the process (2)
includes any finite-valued function on X. This fact is used in Theorem 7.1 below
which gives criteria for exponential ergodicity for a Markov process on a countable
state space.
B. If 0
is an Ito process then the domain of
contains C2 (the class of
functions on X x R + with continuous first and second partial derivatives), while the
domain of sd may be far smaller: see Section 8 and [19], [17].
4,m
lm denote the weak infinitesimal generator for the space-time process
IER}. A measurable function V on X x
is in D(,sim), the domain of
C. Let
{((Q', t):t E
4mIm, if the limit
h
(5)
', V(x, t)
lim
_
hJo
Ex[V(Q(m, t + h)] - V(x, t)
exists pointwise and satisfies
(6)
lim Ex[im V((',
hJO
t + h)] = ?mV(x, t).
If furthermore
(7)
sup Ilim V(X, t)l <
(x,t)EC
0o,
whenever CcX x R+ is compact, then we have that D(,4m) c D(,4m) (see [19]).
We note that when (7) holds, as it typically will in applications where the generator
is derived through the form (5), then the integrability condition (4) is satisfied for
the truncated process Om since the time-integral is almost surely bounded.
Throughout the remainder of this paper we assume that V :X-~ -
is a positive,
measurable function which is in the domain of Slm for all m. Such a function
m; this means that the
V:X-- R+ is called a norm-like function if V(x)-- oo as
level sets {x :V(x) B} are precompact for each B >0. Functions on 11k which are
norm-like include the Euclidean norm
and any monotone, unbounded function
of
I1"11
x---
I*I'I.
Stability of Markovian processes III
523
All of our criteria for stability will rely on a detailed usage of Dynkin's formula,
which is a direct consequence of the optional stopping theorem [10].
Dynkin's formula. Let r be a stopping time for the right process 0, and suppose
is in the domain of the extended generator 4m. Let
that V:X x R+-*
Tm A min {m, r, Tm}. Then
(8)
rm)] = V(x, 0) + Ex ~[
Ex[V(Qmm,
imV(t,
t) dt
,
xE X.
If r is bounded by a fixed deterministic constant, then we take rm = T A Tm in
Dynkin's formula without further comment.
A simple but important consequence of Dynkin's formula is the following
comparison theorem.
Theorem 1.1 (comparison theorem). Suppose that 0
is a non-explosive right
process, and that V, g+ and g_ are positive measurable functions. If for each m,
1m V ' g+ - g_ on Om then for any x E X, sE R +,
PsV(x) + Ptg_(x) dt V(x) + fPtg+(x) dt.
Hence for each x X,
lim sup - P'tg _ (x) dt
s-300
S
lim sup -
-
s----
S o
dt
P'g+(x)
lim inf -
s-300 S
P'g_(x) dt 5 lim inf - P'g+(x) dt.
S-300 S o
Proof. For fixed s E R+ denote sm = s A Tm. It follows from Dynkin's formula
that for x E O,,
Ex[V('Qm')] = V(x) + Ex
Am V (t) dt
(9)f
V(x) +
Ex[f
{g+(t)
-
A
m(~t)} dt]
-
where g_ A m denotes the minimum of g_ and m. We bound g_ in this way to avoid
a possibly infinite negative term.
By (9) and the conditions of the theorem, whenever x E Om,
g_
Ex[V(m.)] +Ex
Ag_ m(4,) dt
V(x) +Ex
-
fg+(tb
) dt
V(x) + Ex[ g+(Qit) dt .
-
524
SEAN P. MEYN AND R. L. TWEEDIE
Since from non-explosivity smTs as m -- *c, we have from Fatou's lemma
P"V(x)
lim inf Ex[V(Q~m)].
m---)oo
<-
Combining these inequalities, we may apply the monotone convergence theorem to
obtain the result.
To apply Dynkin's formula in the comparison theorem we relied on the fact that,
under non-explosivity of 0, we have rm --* r as m -- oo, where in this instance r = s.
Since so many of the results of this paper crucially depend on non-explosivity in this
way, we first give a general sufficient condition under which non-explosivity holds.
2. Criteria for finite escape times
In this section our aim is to find conditions which ensure that the sample paths of
0 remain bounded on bounded time intervals, so that the process is non-explosive.
Our first criterion on the extended generator of the process 0 is the following.
(CDO) Condition for non-explosion. There exists a norm-like function V and a
constant c >0 such that
4m mV(X) _ cV(x)
x E Om, m EZ ,.
It is easy to see that if the apparently weaker bound
AsmV(x) icV(x)
is satisfied for constants c, d ?0,
norm-like function V + d/c, which satisfies (CDO).
XEOm,
+d
m EE+,
then (CDO) is satisfied: if c >0, consider the
The abbreviation CD stands for continuous drift. The conditions CD we introduce
will in general have matching discrete drift conditions DD in [24], but explosion is
not a possibility in discrete time so CDO has no such analogue. We see in the next
result that (CDO) puts an upper limit on the rate of positive drift for the process.
Theorem 2.1. If 0 is a right process and (CDO) is satisfied, then
(i) ? = oo, so that 0 is non-explosive.
(ii) There exists an a.s. finite random variable D such that
(10)
The random variable D satisfies the bound
V(Q~,) - D exp (ct),
05 t <
.
Px{Di -a}
a
V(x)
-
a > O, x EX.
(iii) The expectation Ex[V(Q~,)] is finite for each x and t, and the following bound
holds:
Ex[V(Q,)] =
exp (ct)V(x).